Finite positive-cost stochastic shortest-path value

If $S=G$, all costs and values are zero, and the theorem follows. Otherwise let $S\setminus G\mathrm{\ne }\mathrm{\varnothing }$. For any history-dependent policy, finite state/action histories form finite discrete spaces at each time, so the conditional action and transition rules are probability kernels. By [A1] and [F2], the corresponding trajectory law exists with the specified finite-prefix probabilities; this justifies the expectations in the Statement.

Define the Bellman map $T$ by $(Tu)(g)=0$ on goals and $(Tu)(s)={\min }_{a\in A(s)}[c(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)u(s^{\mathrm{\prime }})]$ off goals. Set $f_0(s)=0$ and $f_{n+1}=T{f}_n$. The minimum is attained by [F3]. These are finite-horizon optimal costs: for $n=0$ the continuation cost is zero; if the claim holds at horizon $n$, conditioning on the first action and next state gives the displayed recursion at horizon $n+1$. Any randomized first action gives a convex combination of action costs, which is at least their minimum; a minimizing pure action attains that minimum, so the finite-horizon optimum is the displayed value.

The recursion is monotone in its value argument because all transition weights are nonnegative, and $f_1\ge f_0=0$; induction gives $0\le f_n\le f_{n+1}$. For any stationary policy $\pi$, let $U=S\setminus G$ and define the substochastic matrix $Q^{\pi }$ on $U$ by $Q^{\pi }(s,t)={\sum }_{a\in A(s)}\pi (a\mid s)P(t\mid s,a)$. The properness recursion gives $q_0^{\pi }{\mathrm{\mid }}_U=\mathbf{1}$ and $q_{n+1}^{\pi }{\mathrm{\mid }}_U=Q^{\pi }{q}_n^{\pi }{\mathrm{\mid }}_U$, so $q_n^{\pi }{\mathrm{\mid }}_U=(Q^{\pi }{)}^n\mathbf{1}$; since $Q^{\pi }\mathbf{1}\le \mathbf{1}$, these survival probabilities are nonincreasing. For the proper stationary policy $\bar{\pi }$ in the Given assumptions, choose $N_s\ge 1$ with $q_{N_s}^{\bar{\pi }}(s)<1$ for each state. Since $S$ is finite, $N={\max }_s{N}_s$ and $\rho ={\max }_s{q}_N^{\bar{\pi }}(s)$ satisfy $\rho <1$. Also $q_N^{\bar{\pi }}(s)={\sum }_{t\in U}(Q^{\bar{\pi }}{)}^N(s,t)$ for $s\in U$, and $q_{(k+1)N}^{\bar{\pi }}=(Q^{\bar{\pi }}{)}^N{q}_{kN}^{\bar{\pi }}$. Thus induction gives $q_{kN}^{\bar{\pi }}(s)\le {\rho }^k$ for every state and $k\ge 0$. The finite maximum $c_{\max }=\max \{c(s,a):s\in U,a\in A(s)\}$ exists by [F3]. During block $k$, each stage cost has expectation at most $c_{\max }{q}_{kN}^{\bar{\pi }}(s)\le c_{\max }{\rho }^k$, because survival decreases in time. Hence $J^{\bar{\pi }}(s)\le N{c}_{\max }{\sum }_{k\ge 0}{\rho }^k=N{c}_{\max }\mathrm{/}(1-\rho )$. Since $f_n$ is the $n$-step optimum, $f_n(s)\le J^{\bar{\pi }}(s)$; thus each increasing sequence $f_n(s)$ is bounded above, and [F4] gives a finite limit $f(s)$.

Passing to the limit in the finite sums and finite minima in step 1.2 is valid coordinatewise; the minimum of finitely many convergent real sequences converges to the minimum of their limits. Hence $f(g)=0$ on $G$ and $f(s)={\min }_a[c(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)f(s^{\mathrm{\prime }})]$ off $G$. Therefore $f$ is a finite nonnegative Bellman fixed point.

Enumerate the finite state set as $s_1,\dots ,s_m$. For each nonglobal state, [F3] gives a nonempty finite set of actions minimizing the fixed-point expression in step 3.1. Inductively along this finite list, select one minimizer at each state; at each successor stage one nonempty finite set is added to the already chosen finite tuple, so this finite construction uses no arbitrary-index choice. The selected actions define a deterministic stationary policy ${\pi }^{\ast }$. For $n=0$ the identity is $f(s)=f(s)$. If it holds at $n$, condition on the next state and apply the Bellman equality at the current state to obtain it at $n+1$; hence induction gives $f(s)={\mathbb{E}}_s^{{\pi }^{\ast }}[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+f(S_n)]$ for every $n$. By step 2.1 and [F4], the survival probabilities under ${\pi }^{\ast }$ have a limit; if that limit were $q_{\mathrm{\infty }}>0$, the partial cost expectation would be at least $n{c}_{\min }{q}_{\mathrm{\infty }}$, contradicting the finite left side and nonnegative terminal term. Thus ${\pi }^{\ast }$ is proper. Since $f$ is bounded on finite $S$ and $f=0$ on $G$, properness gives ${\mathbb{E}}_s^{{\pi }^{\ast }}f(S_n)\le {\max }_{x}f(x)q_n^{{\pi }^{\ast }}(s)\to 0$; letting $n\to \mathrm{\infty }$ in the identity yields $J^{{\pi }^{\ast }}(s)=f(s)$.

Fix an initial state $s$ and any policy $\sigma$. The fixed-point equation gives $f(x)\le c(x,a)+{\sum }_{x^{\mathrm{\prime }}}P(x^{\mathrm{\prime }}\mid x,a)f(x^{\mathrm{\prime }})$ for each nonglobal $x$ and every action $a$, with equality at goals. Averaging over each history-dependent action distribution gives the one-step inequality; conditioning successively on the finite-prefix laws and inducting on $n$ gives $f(s)\le {\mathbb{E}}_s^{\sigma }[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+f(S_n)]$. Under $\sigma$, the events $\{S_n\mathrm{\notin }G\}$ decrease because goals are absorbing. If their probabilities tend to zero, boundedness of the terminal term makes $f(s)\le J^{\sigma }(s)$. If they do not tend to zero, their limit is positive, and the positive cost lower bound makes $J^{\sigma }(s)=+\mathrm{\infty }$; again $f(s)\le J^{\sigma }(s)$. Thus $f$ is a lower bound for every policy cost, while step 4.1 exhibits a policy attaining it. Consequently $f=f^{\ast }$.

Let $g$ be any finite nonnegative solution of the same Bellman equations. Since $f_0=0\le g$, the monotonicity of $T$ from step 2.1 gives $f_n=T^{n}0\le T^{n}g=g$ for every $n$, hence $f^{\ast }\le g$. The Bellman minimum for $g$ is no larger than any action value, so $g(x)\le c(x,a)+{\sum }_{x^{\mathrm{\prime }}}P(x^{\mathrm{\prime }}\mid x,a)g(x^{\mathrm{\prime }})$ for every nonglobal $x$ and action $a$. Average this inequality along the proper policy ${\pi }^{\ast }$ from step 4.1 and iterate over $n$ steps to obtain $g(s)\le {\mathbb{E}}_s^{{\pi }^{\ast }}[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+g(S_n)]$. The terminal term tends to zero because $g$ is bounded and ${\pi }^{\ast }$ is proper, so $g(s)\le J^{{\pi }^{\ast }}(s)=f^{\ast }(s)$. Therefore $g=f^{\ast }$, proving uniqueness.