= Solution
Write $V(x)=F(\pi,x)$. The <Bellman equation> implies $V(x)\geq r(x,u)+\beta\mathbb E[V(x_1)\mid x,u]$ for every available action. Under any competing policy, repeated conditioning gives
$$
V(x)\geq\mathbb E_{\pi'}\left[\sum_{t=0}^{n-1}\beta^tr(x_t,u_t)+\beta^nV(x_n)\right]\geq\mathbb E_{\pi'}\sum_{t=0}^{n-1}\beta^tr(x_t,u_t).
$$
The last inequality uses $V\geq0$. The <monotone convergence theorem> now gives \b[$V(x)\geq F(\pi',x)$], even when $\beta\geq1$. If $V(x)=\infty$ the comparison is immediate; otherwise the nonnegative conditional bounds justify each finite induction step. This proves <Bellman comparison with nonnegative rewards and superunit discount> without a vanishing-terminal-term assumption.
For the unit-bet policy in this <gambler's ruin> problem, put $\beta=\sqrt{9/8}=3/(2\sqrt2)$. The value satisfies
$$
V_x=\beta\left(\frac13V_{x+1}+\frac23V_{x-1}\right),\qquad V_0=0,\quad V_{100}=100.
$$
The characteristic equation has the repeated root $\sqrt2$, so $V_x=(A+Bx)2^{x/2}$. The boundary values give
$$
\boxed{V_x=x\,2^{(x-100)/2}.}
$$
To justify that this finite recurrence solution is the expected reward despite $\beta>1$, let $Q$ be the transition matrix on transient states $1,\ldots,99$. The matrix $\beta Q$ is diagonally similar, with diagonal factors $2^{x/2}$, to the symmetric tridiagonal matrix with off-diagonal entries $1/2$. Its <eigenvalues> are $\cos(j\pi/100)$, $1\leq j\leq99$, with absolute value below one. Thus its <Neumann series> converges and yields exactly the absorbed-payoff expectation and the unique recurrence solution.
When $p_2=1/4$, at wealth $2$ bet $2$ once and then follow the unit-bet policy. Its expected value is $\beta V_4/4=\beta V_2>V_2$, since $V_4=4V_2$. Therefore \b[the unit-bet policy is not optimal].
Back to article page
