  We present a novel model for capturing the behavior of an agent exhibiting
sunk-cost bias in a stochastic environment. Agents exhibiting sunk-cost bias
take into account the effort they have already spent on an endeavor when they
evaluate whether to continue or abandon it. We model planning tasks in which an
agent with this type of bias tries to reach a designated goal. Our model
structures this problem as a type of Markov decision process: loosely speaking,
the agent traverses a directed acyclic graph with probabilistic transitions,
paying costs for its actions as it tries to reach a target node containing a
specified reward. The agent's sunk cost bias is modeled by a cost that it
incurs for abandoning the traversal: if the agent decides to stop traversing
the graph, it incurs a cost of $\lambda \cdot C_{sunk}$, where ${\lambda \geq
0}$ is a parameter that captures the extent of the bias and $C_{sunk}$ is the
sum of costs already invested.
  We analyze the behavior of two types of agents: naive agents that are unaware
of their bias, and sophisticated agents that are aware of it. Since optimal
(bias-free) behavior in this problem can involve abandoning the traversal
before reaching the goal, the bias exhibited by these types of agents can
result in sub-optimal behavior by shifting their decisions about abandonment.
We show that in contrast to optimal agents, it is computationally hard to
compute the optimal policy for a sophisticated agent. Our main results quantify
the loss exhibited by these two types of agents with respect to an optimal
agent. We present both general and topology-specific bounds.
