Optimal Stopping

Example:
Imagine a player keeps rolling a die until they either stop or roll a $6$. Their score is the last die they’ve rolled, or $0$ if they rolled a $6$.

What’s the optimal strategy if the player wants to maximize their expected payoff?

Define $f(k)=k$ if $k\le 5$, $f(6)=0$

Let $v(k)$ be the expected winnings of the player given that the first roll is $k$ if the player takes the optimal strategy

Let $u(k)=\frac{1}{6}(v(1)+v(2)+v(3)+v(4)+v(5)+v(6))$ be the expected payoff continuing after the first roll

If $f(k)>u(k)$, the player should take the money, otherwise the player should roll again

$v(k)=\max \{f(k),u(k)\}$

Since $v(k)\ge f(k)$, we have $u(k)\ge \frac{1}{6}(f(1)+\cdots +f(6))=5/2$

We now know a bit more about this game, that if the first roll is a 1 or a 2 then the player should roll again

$v(1)=v(2)=\frac{1}{6}(v(1)+\cdots +v(4))+\frac{5}{6}$

Suppose the first roll is a 4. If the optimal strategy was continuing, then the game would look like rolling until a 5 or 6 is rolled, meaning the expected winnings is $5/2$. This is less than 4, so clearly the optimal strategy is stopping on 4.

Let $u$ be the expected winnings after continuing and assume we continue after 3, $u=\mathbb{P}\{\text{roll}\le 3\}u+\frac{1}{6}(4+5)⟹u=3$

So we can stop or continue after rolling a 3 for the same result

Optimal Stopping of Markov Chains

Suppose $\mathbf{P}$ is the transition matrix for a discrete-time Markov chain $X_n$ with state space $S$, and define a payoff function $f(s)$ for all $s\in S$

We are interested in cases where $\mathbf{P}$ is not irreducible, since otherwise we can always keep going until any condition is satisfied

A stopping rule or stopping time $T$ is a random variable that gives the time at which the chain is stopped, based only on what has happened up to step $n$

All reasonable rules divide the state space into two sets $S_1$ and $S_2$ and stop when the chain reaches a state in $S_2$

Our aim is to maximize expected payoff over all legal stopping rules
$v(x)={\max }_T\mathbb{E}[f(X_T)\mid X_0=x]$

We generalize the rules defined in the initial example,
$v(x)\ge f(x)$
$v(x)\ge \mathbf{P}v(x)={\sum }_y^{}p(x,y)v(y)$
$v(x)=\max \{f(x),\mathbf{P}v(x)\}$

Assuming the optimal strategy, $T=\min \{j\ge 0:X_j\in S_2\}$ and $v(x)=\mathbb{E}[f(X_T)\mid X_0=x]$

We call a function $u$ superharmonic with respect to $\mathbf{P}$ if $u(x)\ge \mathbf{P}u(x)$
Let $T_n=\min \{T,n\}$
$u(x)\ge \mathbb{E}[u(X_{T_n})\mid X_0=x]$
We can prove this by induction

Since $u$ is a bounded function, we can say $u(x)\ge {\lim }_{n\to \infty }\mathbb{E}[u(X_{T_n})\mid X_0=x]=\mathbb{E}[u(X_T)\mid X_0=x]$

Suppose $u(x)\ge f(x)$ for all $x$,
$u(x)=\mathbb{E}[u(X_T)\mid X_0=x]\ge \mathbb{E}[f(X_T)\mid X_0=x]=v(x)$
Hence every superharmonic function larger than $f$ is greater than or equal to the value function $v$

$v(x)=\text{inf}u(x)$, the infimum over all superharmonic functions $u(x)\ge f(x)$, i.e. $v$ is the smallest superharmonic function with respect to $\mathbf{P}$ that is greater than or equal to $f$

We use this fact to determine $v$. Start with $u_1(x)$ which equals $f(x)$ if $x$ is absorbing and otherwise equals the maximum value of $f$

Let $u_2(x)=\max \{\mathbf{P}{u}_1(x),f(x)\}$
We see $u_2(x)\le u_1(x)$ and therefore $\mathbf{P}{u}_2(x)\le \mathbf{P}{u}_1(x)\le u_2(x)$, meaning $u_2$ is also superharmonic and greater than $f$

$u_n(x)=\max \{\mathbf{P}{u}_{n-1}(x),f(x)\}$
It’s already clear from this equation that $v(x)={\lim }_{n\to \infty }{u}_n(x)$

Suppose we know the optimal strategy $S_1$ and $S_2$,
$u(x)=f(x)$ if $x\in S_2$ otherwise $u(x)=\mathbf{P}u(x)$

For a finite-state Markov chain, the solution can be found directly from this system of linear equations

Now to prove the above, we see that $u(z)={\lim }_{n\to \infty }{u}_n(z)$ is a superharmonic function and $u(z)\ge f(z)$ for all $z$, so $u(z)\ge v(z)$.

Define $S_2=\{z:u(z)=f(z)\}$ and $S_1=\{z:u(z)>f(z)\}$
On $S_1$, $\mathbf{P}u(z)=u(z)$
Therefore, $u(z)=\mathbb{E}[u(X_T\mid X_0=z)]$
Since $v(z)$ is the largest expected value over all possible stopping sets, we get $u(z)\le v(z)$

So $u(z)=v(z)$

Optimal Stopping with Cost

Assume continuing has a cost of $g(x)$
$v(x)={\max }_T\mathbb{E}\left[f(X_T)-{\sum }_{j=0}^{T-1}g(X_j)\mid X_0=x\right]$
$v(x)=\max \{f(x),\mathbf{P}v(x)-g(x)\}$

The optimal stopping rule is to stop when the chain enters $S_2=\{x:v(x)=f(x)\}$

$v$ is the smallest function $u$ greater than $f$ satisfying $u(x)\ge \mathbf{P}u(x)-g(x)$

Our algorithm is similar,
$u_1(x)=f(x)$
$u_n(x)=\max \{f(x),\mathbf{P}{u}_{n-1}(x)-g(x)\}$ and
$v(x)={\lim }_{n\to \infty }{u}_n(x)$

Including a cost function means irreducible Markov chains become more interesting

Optimal Stopping with Discounting

In financial matters, we often assume the value of money decreases over time

$v(x)={\max }_T\mathbb{E}[{\alpha }^{T}f(x_T)\mid X_0=x]$
$v$ is the smallest function $u$ with $u(x)\ge f(x)$ and $u(x)\ge \alpha \mathbf{P}u(x)$
We can use the same recursive algorithm