Stochastic Shortest Path and Total-Cost Dynamic Programming

Intuition Beginner

Some decision problems do not run forever and do not fade out by discounting; instead they aim at a destination. A robot wants to reach a charging dock, a board game wants to reach a finishing square, a project wants to reach completion. Once you arrive, the problem is over and nothing more is charged. Every step before arrival has a cost, and the chance of where you land next depends on what you do. The question is how to act so that the total cost of getting to the destination is as small as possible.

Because there is a real ending — the destination — you do not need to shrink future costs to keep the total finite. The total stays finite for another reason: a good plan actually reaches the destination, and once there, the bill stops. This is the stochastic shortest path idea. The destination is a special situation that costs nothing and that you never leave. A plan that is sure to reach it eventually pays a finite total; a plan that might wander away from the destination forever can pile up cost without end.

This splits all plans into two kinds. A proper plan is one that, no matter where you start, will reach the destination with full certainty given enough steps. An improper plan can get stuck circling among the other situations, never arriving. Proper plans are the well-behaved ones, and the whole method works when at least one proper plan exists and every improper plan is genuinely bad — costing an unbounded amount from somewhere.

The reward for setting things up this way is that the same repeat-until-settled method from earlier still finds the answer. The value of each situation is the cheapest expected total cost to reach the destination from there, and it satisfies one self-referential equation: value here equals best immediate cost plus the average value of where you land next.

Visual Beginner

Picture a small map of situations with one marked as the destination. From each non-destination situation, each action is a fan of arrows to possible next situations, each arrow carrying a chance and the situation carrying a one-step cost. Arrows can point toward the destination or away from it. A plan is proper when, following its chosen arrows, every situation has a path of nonzero chance that eventually lands on the destination, so you are sure to arrive in the long run.

The contrast in the side panel is the heart of it. A proper plan always drains into the destination, so its total cost is a finite number for every starting situation. An improper plan can trap you in a loop that never reaches the destination; if that loop carries any positive cost, the total grows without bound.

plan type	reaches destination?	total cost
proper	yes, with certainty	finite from every start
improper	not from some start	can be infinite

Worked example Beginner

A delivery bot is at situation $A$ or $B$, and wants to reach the depot $D$, which costs nothing and is the end. From $A$ the only action is drive: cost $2$, and it reaches $D$ with chance $0.5$ or slips to $B$ with chance $0.5$. From $B$ the only action is drive: cost $3$, and it reaches $D$ with chance $1$. There is no discounting; we want the cheapest expected total cost to reach $D$. This plan is proper: from either start the bot is sure to arrive.

Write $J(A)$ and $J(B)$ for the expected total cost to reach $D$. At the depot $D$ the value is $0$. Let us find the values by repeated updates, starting both at $0$.

Sweep 1. From $A$: cost $2$ plus the average of next values, $0.5J(D)+0.5J(B)=0.5(0)+0.5(0)=0$, total $2$. From $B$: cost $3$ plus $J(D)=0$, total $3$. New table: $J(A)=2$, $J(B)=3$.

Sweep 2. From $A$: $2+(0.5\cdot 0+0.5\cdot 3)=2+1.5=3.5$. From $B$: $3+0=3$. New table: $J(A)=3.5$, $J(B)=3$.

Sweep 3. From $A$: $2+(0.5\cdot 0+0.5\cdot 3)=3.5$. From $B$: $3$. The table did not change, so we have the answer: $J(A)=3.5$, $J(B)=3$.

What this tells us: with no discounting, the values still settle to finite numbers because the plan is sure to reach the depot, where the bill stops. Starting at $B$ costs $3$; starting at $A$ costs $3.5$, the $2$ to drive plus the half-chance of a $3$ detour through $B$.

Check your understanding Beginner

Formal definition Intermediate+

A stochastic shortest path (SSP) problem is a finite-state controlled Markov chain with states $\{1,\dots ,n\}$ together with a cost-free absorbing terminal state $t$. For each non-terminal state $i$ there is a nonempty admissible-control set $U(i)$, transition probabilities $p_{ij}(u)$ (including $p_{it}(u)$ to the terminal state) summing to one over $j\in \{1,\dots ,n,t\}$, and a bounded one-stage expected cost $g(i,u)$; the terminal state satisfies $p_{tt}=1$ and $g(t,\cdot )=0$. There is no discounting: $\alpha =1$. This is the undiscounted, terminating counterpart of the discounted MDP 44.08.03. A stationary policy is a map $\mu$ with $\mu (i)\in U(i)$, and its total expected cost from $i$ is

$$J_{\mu }(i)=\underset{N\to \infty }{\lim }\mathbb{E}\left[\sum _{k=0}^{N-1}g(x_k,\mu (x_k))|x_0=i\right],x_{k+1}\sim p_{x_k,\cdot }(\mu (x_k)),$$

with $J_{\mu }(t)=0$; the limit may be $+\infty$.

Let $P_{\mu }=[p_{ij}(\mu (i)){]}_{i,j=1}^n$ be the substochastic matrix of transitions among the non-terminal states under $\mu$ (mass $1-{\sum }_j{p}_{ij}(\mu (i))$ leaks to $t$), and $g_{\mu }=(g(i,\mu (i)){)}_i$. A stationary policy $\mu$ is proper if, starting from every state, the terminal state is reached with probability one under $\mu$; equivalently there exist $m$ and $\rho <1$ with $\mathbb{P}(x_m\ne t\mid x_0=i,\mu )\le \rho$ for all $i$, equivalently the spectral radius of $P_{\mu }$ is strictly below one, so $I-P_{\mu }$ is invertible and ${\sum }_{k\ge 0}{P}_{\mu }^k=(I-P_{\mu }{)}^{-1}$ converges. A policy that is not proper is improper. For proper $\mu$, $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$ is finite.

On the space $B(S)={\mathbb{R}}^n$ of functions on the non-terminal states (with $J(t)=0$ fixed), define the policy operator $T_{\mu }$ and the Bellman operator $T$ by

$$(T_{\mu }J)(i)=g(i,\mu (i))+\sum _{j=1}^n{p}_{ij}(\mu (i))J(j),(TJ)(i)=\underset{u\in U(i)}{\min }\{g(i,u)+\sum _{j=1}^n{p}_{ij}(u)J(j)\},$$

the terminal term $p_{it}(u)J(t)=0$ omitted. The optimality (Bellman) equation is $J^{\ast }=T{J}^{\ast }$ and policy evaluation is $J_{\mu }=T_{\mu }{J}_{\mu }$. A policy $\mu$ is greedy for $J$ if $T_{\mu }J=TJ$. The two standing SSP assumptions are: (3.1) at least one proper policy exists; (3.2) every improper policy has $J_{\mu }(i)=+\infty$ for some $i$. The weighted sup-norm with weights $v=(v_1,\dots ,v_n)>0$ is $\Vert J{\Vert }_v={\max }_i|J(i)|/v_i$. The symbols $T$, $T_{\mu }$, $J^{\ast }$, $J_{\mu }$, $P_{\mu }$ (substochastic policy matrix), $\Vert \cdot {\Vert }_v$ (weighted sup-norm), and the terminal state $t$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "With no discount factor the Bellman operator cannot be a contraction in any sup-norm." In the plain sup-norm it generally is not — a proper policy's substochastic $P_{\mu }$ can have row sums equal to one for states far from the terminal. But the SSP assumptions deliver a positive weight vector $v$ and a modulus $\beta <1$ making $T$ a contraction in the weighted sup-norm $\Vert \cdot {\Vert }_v$. The weighting is the whole point; without it the contraction fails.

• "Bellman's equation might have several solutions once $\alpha =1$." Under the two assumptions $T$ has a unique fixed point among functions on the non-terminal states (with $J(t)=0$), and it is $J^{\ast }$. The terminal-state normalization $J(t)=0$ removes the additive-constant ambiguity that plagues the undiscounted average-cost problem; here the absorbing state pins the level.

• "Improper policies are merely suboptimal, so they can be ignored." Assumption (3.2) is what rules them out, and it is a genuine hypothesis: if some improper policy had finite cost everywhere, $J^{\ast }$ could fail to satisfy the contraction-based uniqueness, value iteration could converge to the wrong limit, and policy iteration could stall at an improper policy. The assumption forces every improper policy to be visibly infinite-cost somewhere.

• "A greedy policy for the optimal cost could be improper." Under the assumptions, any policy greedy for $J^{\ast }$ is proper and optimal. Were a greedy policy improper, assumption (3.2) would give it infinite cost from some state, contradicting $J_{\mu }=J^{\ast }<\infty$ obtained from greediness; properness of optimal policies is a consequence, not a separate hypothesis.

Key theorem with proof Intermediate+

The signature result is that, under the two SSP assumptions, the undiscounted Bellman operator is a contraction in a suitable weighted sup-norm, recovering for the total-cost problem the entire fixed-point apparatus — existence, uniqueness, value-iteration convergence, greedy optimality — that the discount factor supplied automatically in the discounted case 44.08.02. The discount modulus $\alpha$ is replaced by a constructed modulus $\beta <1$ and a constructed weight vector $v>0$.

Theorem (SSP weighted-sup-norm contraction and the total-cost optimality equation). Let an SSP satisfy assumptions (3.1) and (3.2). Then there exist a vector $v=(v_1,\dots ,v_n)$ with $v_i>0$ and a scalar $\beta \in [0,1)$ such that for every proper $\mu$ and for $T$,

$$\Vert T_{\mu }J-T_{\mu }{J}^{\prime }{\Vert }_v\le \beta \Vert J-J^{\prime }{\Vert }_v,\Vert TJ-T{J}^{\prime }{\Vert }_v\le \beta \Vert J-J^{\prime }{\Vert }_v,J,J^{\prime }\in {\mathbb{R}}^n.$$

Consequently $T$ has a unique fixed point $J^{\ast }\in {\mathbb{R}}^n$, which equals the optimal cost; value iteration $J_{k+1}=T{J}_k$ from any $J_0$ converges to $J^{\ast }$ ($\Vert J_k-J^{\ast }{\Vert }_v\le {\beta }^k\Vert J_0-J^{\ast }{\Vert }_v$); each proper $T_{\mu }$ has the unique fixed point $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$; and a stationary policy ${\mu }^{\ast }$ is optimal if and only if it is greedy for $J^{\ast }$ ($T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }$), in which case ${\mu }^{\ast }$ is proper.

Proof. First construct $v$. Modify the SSP by charging a cost of $1$ at every non-terminal state under every control: the modified problem has the same proper policies, and for a proper $\mu$ the modified total cost is the expected number of steps to absorption, $v^{\mu }=(I-P_{\mu }{)}^{-1}1>0$, finite by properness. Let $\hat{J}$ be the optimal cost of the modified problem (minimum expected steps to reach $t$); under the assumptions $\hat{J}$ is finite and satisfies $\hat{J}(i)=1+{\min }_u{\sum }_j{p}_{ij}(u)\hat{J}(j)$, so $\hat{J}(i)\ge 1+{\sum }_j{p}_{ij}(u)\hat{J}(j)$ for every admissible $u$. Set $v_i=\hat{J}(i)>0$. Then for each $i$ and each control $u$,

$$\sum _j{p}_{ij}(u)v_j\le v_i-1\le \beta v_i,\beta :=\underset{i}{\max }\frac{v_i-1}{v_i}=1-\frac{1}{{\max }_i{v}_i}\in [0,1).$$

Now bound $T$. For $J,J^{\prime }$ and any $i$, pick $u$ attaining $(TJ)(i)$; then

$$(TJ)(i)-(T{J}^{\prime })(i)\le \sum _j{p}_{ij}(u)(J(j)-J^{\prime }(j))\le \sum _j{p}_{ij}(u)v_j\Vert J-J^{\prime }{\Vert }_v\le \beta v_i\Vert J-J^{\prime }{\Vert }_v,$$

using $|J(j)-J^{\prime }(j)|\le v_j\Vert J-J^{\prime }{\Vert }_v$ and the bound on ${\sum }_j{p}_{ij}(u)v_j$. The symmetric choice gives the reverse, so $|(TJ)(i)-(T{J}^{\prime })(i)|\le \beta v_i\Vert J-J^{\prime }{\Vert }_v$, i.e. $|(TJ)(i)-(T{J}^{\prime })(i)|/v_i\le \beta \Vert J-J^{\prime }{\Vert }_v$; the maximum over $i$ is the contraction bound for $T$. The single-control version gives it for each proper $T_{\mu }$ (whose own substochastic matrix obeys the same ${\sum }_j{p}_{ij}(\mu (i))v_j\le \beta v_i$).

Because $({\mathbb{R}}^n,\Vert \cdot {\Vert }_v)$ is complete (all norms on ${\mathbb{R}}^n$ are equivalent, so completeness is the metric/Banach substrate of 02.01.05) and $\beta <1$, the Banach fixed-point theorem gives a unique fixed point $J^{\ast }=T{J}^{\ast }$ with the geometric estimate $\Vert J_k-J^{\ast }{\Vert }_v\le {\beta }^k\Vert J_0-J^{\ast }{\Vert }_v$, and a unique $J_{\mu }=T_{\mu }{J}_{\mu }$ for each proper $\mu$; solving the linear fixed point, $J_{\mu }=g_{\mu }+P_{\mu }{J}_{\mu }$ gives $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$.

That $J^{\ast }$ is the optimal cost and is attained by a greedy proper policy: let ${\mu }^{\ast }$ be greedy for $J^{\ast }$, so $T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }=J^{\ast }$. The contraction bound applied to $T_{{\mu }^{\ast }}$ (its substochastic matrix obeys ${\sum }_j{p}_{ij}({\mu }^{\ast }(i))v_j\le \beta v_i<v_i$, forcing strictly positive leakage to $t$ from the recurrent classes, hence ${\mu }^{\ast }$ proper) makes $J^{\ast }$ the unique fixed point of $T_{{\mu }^{\ast }}$, so $J^{\ast }=J_{{\mu }^{\ast }}<\infty$. For any proper $\mu$, monotonicity of $T_{\mu }$ and $T_{\mu }{J}^{\ast }\ge T{J}^{\ast }=J^{\ast }$ iterated give $J_{\mu }={\lim }_k{T}_{\mu }^k{J}^{\ast }\ge J^{\ast }$. For any improper $\mu$, assumption (3.2) gives $J_{\mu }(i)=+\infty \ge J^{\ast }(i)$ for some $i$, and $J_{\mu }\ge J^{\ast }$ pointwise holds because the per-state cost is nonneg-dominated by the proper optimum where finite. Hence ${\inf }_{\mu }{J}_{\mu }\ge J^{\ast }$, while $J_{{\mu }^{\ast }}=J^{\ast }$ shows the infimum is attained; thus $J^{\ast }={\inf }_{\mu }{J}_{\mu }$. Finally $\mu$ optimal ($J_{\mu }=J^{\ast }$) gives, applying $T_{\mu }$ to its fixed point, $T_{\mu }{J}^{\ast }=T_{\mu }{J}_{\mu }=J_{\mu }=J^{\ast }=T{J}^{\ast }$, so $\mu$ is greedy; the converse was shown. $\square$

Bridge. This theorem is the foundational reason undiscounted total-cost control is as tractable as the discounted case: where discounting handed over a contraction modulus for free, the SSP assumptions manufacture one — the constructed weight vector $v$ (minimum expected steps to the terminal state) and modulus $\beta =1-1/{\max }_i{v}_i$ play the role the discount $\alpha$ played in 44.08.02, and this is exactly the same Banach fixed-point machinery 02.01.05 read in a weighted norm. The central insight is that properness is a spectral condition — the substochastic $P_{\mu }$ has spectral radius below one — so $I-P_{\mu }$ inverts and the expected-step function is finite and positive, and that single positive vector simultaneously controls $T$ and every proper $T_{\mu }$. The construction generalises the discounted contraction (which is the SSP weighting with the uniform weight $v\equiv 1/(1-\alpha )$) and is dual, through the substochastic resolvent $(I-P_{\mu }{)}^{-1}$, to the discounted resolvent $(I-\alpha P_{\mu }{)}^{-1}$ of the Markov-chain evaluation step 44.08.03. Putting these together, value iteration, policy iteration over proper policies, and the asynchronous variants are three algorithms for the one fixed point $J^{\ast }=T{J}^{\ast }$, and the bridge is that adding a uniform termination probability $1-\alpha$ to any discounted MDP turns it into an SSP, so the discounted theory is a special case; this builds toward real-time and approximate dynamic programming, and appears again in the neuro-dynamic-programming treatment of reinforcement learning, where SSP is the default episodic model.

Exercises Intermediate+

Advanced results Master

The SSP theory extends in four directions: policy iteration restricted to proper policies with its monotone improvement and finite termination, the Gauss-Seidel and asynchronous value-iteration variants convergent under the same assumptions, real-time dynamic programming over simulated trajectories, and the unifying status of SSP as the model from which discounted DP, deterministic shortest paths, and first-passage problems all descend.

Theorem 1 (policy iteration over proper policies: monotone improvement and finite termination). Starting from any proper policy ${\mu }_0$ (one exists by assumption 3.1), policy iteration alternates exact evaluation — solve $J_{{\mu }_k}=g_{{\mu }_k}+P_{{\mu }_k}{J}_{{\mu }_k}$, i.e. the linear system $J_{{\mu }_k}=(I-P_{{\mu }_k}{)}^{-1}{g}_{{\mu }_k}$, well-posed because $\rho (P_{{\mu }_k})<1$ — with improvement, ${\mu }_{k+1}$ greedy for $J_{{\mu }_k}$. Each ${\mu }_{k+1}$ is again proper, $J_{{\mu }_{k+1}}\le J_{{\mu }_k}$ pointwise, with strict decrease at some state unless ${\mu }_k$ is optimal. With finitely many states and controls there are finitely many proper policies and the cost strictly decreases until optimality, so policy iteration terminates with an optimal proper policy in finitely many iterations; it is the Newton method for $J-TJ=0$ and converges at least as fast as value iteration ^{[Bertsekas Vol. 2 Ch. 3]}.

Theorem 2 (Gauss-Seidel and asynchronous value iteration). Because $T$ is a weighted-sup-norm contraction with a monotone, componentwise structure, value iteration converges even when states are updated one at a time using the most recent values (Gauss-Seidel) or in an arbitrary order with possibly outdated values (asynchronous / chaotic iteration), provided every state is updated infinitely often. The asynchronous convergence follows from the Bertsekas asynchronous-convergence theorem: a sequence of nested boxes $\{J:\Vert J-J^{\ast }{\Vert }_v\le {\beta }^{k}r\}$ shrinking to $J^{\ast }$, each mapped into the next by $T$ componentwise, is exactly the structure a weighted-sup-norm contraction provides, so any update schedule with infinitely-often coverage drives the iterate into every box ^{[Bertsekas Tsitsiklis Neuro-Dynamic Programming Ch. 2]}.

Theorem 3 (real-time dynamic programming). Real-time dynamic programming (RTDP) interleaves control with computation: at each visited state $i$ it performs one Bellman backup $J(i)\leftarrow (TJ)(i)$, applies the greedy action, and moves to the simulated successor, updating only states along the trajectory. Under the SSP assumptions, with an admissible (lower-bounding) initial $J_0\le J^{\ast }$ and a proper greedy policy maintained, the values of all relevant states converge to $J^{\ast }$ and the generated trajectories reach the terminal state; RTDP focuses computation on states that matter for the start state, the basis of the LRTA* and labeled-RTDP heuristic-search algorithms ^{[Bertsekas Tsitsiklis Neuro-Dynamic Programming Ch. 2]}.

Theorem 4 (SSP as the unifying total-cost model). The SSP problem specializes to the principal finite-state DP models. The discounted MDP with discount $\alpha \in (0,1)$ 44.08.03 is the SSP obtained by adding, from every state, a transition to the terminal state with probability $1-\alpha$ and scaling the surviving transitions by $\alpha$: every policy is then automatically proper (geometric termination), the constant weight $v\equiv 1$ gives modulus $\beta =\alpha$, and the SSP optimality equation reduces to the discounted Bellman equation. The deterministic shortest path problem is the SSP in which each control sends the state to a unique successor with probability one and $g(i,u)$ is the arc length; properness is the existence of a path to the destination, assumption (3.2) is the absence of negative-cost cycles, and value/policy iteration reduce to the Bellman-Ford and label-correcting algorithms. First-passage problems — minimizing expected cost until a target set is first reached — are SSPs with the target set lumped into the terminal state. Thus the weighted-contraction theory subsumes discounting, classical shortest paths, and first-passage as one framework ^{[Bertsekas Vol. 2 Ch. 3]}.

Synthesis. The foundational reason the undiscounted total-cost problem is solvable is that properness manufactures a contraction where discounting once supplied one for free: the SSP assumptions produce a positive weight vector $v$ (minimum expected steps to the terminal state) and a modulus $\beta =1-1/{\max }_i{v}_i<1$, and this is exactly the discounted contraction of 44.08.02 read in a weighted norm, the discount case being the uniform-weight specialization. The central insight is that properness is the spectral condition $\rho (P_{\mu })<1$, so the substochastic resolvent $(I-P_{\mu }{)}^{-1}$ converges and policy evaluation is the finite linear solve $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$; this is dual to the discounted resolvent $(I-\alpha P_{\mu }{)}^{-1}$ of the Markov-chain evaluation step 44.08.03, the discount $\alpha$ reappearing as a uniform survival probability. Putting these together, value iteration (${\beta }^k$ geometric rate), policy iteration over proper policies (the finitely-terminating Newton step), and the asynchronous and real-time variants are algorithms for the one fixed point $J^{\ast }=T{J}^{\ast }$ vanishing at the terminal state, and the two assumptions are what make that fixed point unique — without (3.2) a zero-cost improper loop reintroduces spurious solutions. This is exactly the model that unifies discounted DP, deterministic shortest paths, and first-passage problems, and it builds toward approximate and neuro-dynamic programming, where SSP is the default episodic substrate and the effective horizon ${\max }_i{v}_i$ measures the difficulty the discounted $1/(1-\alpha )$ measured before.

Full proof set Master

Proposition 1 (proper policy: spectral characterization and finite evaluation). A stationary policy $\mu$ is proper if and only if $\rho (P_{\mu })<1$, in which case $I-P_{\mu }$ is invertible, ${\sum }_{k\ge 0}{P}_{\mu }^k=(I-P_{\mu }{)}^{-1}$, and $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$ is finite.

Proof. If $\mu$ is proper, there are $m$ and $\rho <1$ with $\mathbb{P}(x_m\ne t\mid x_0=i)\le \rho$ for all $i$; the row sums of $P_{\mu }^m$ (probability of remaining non-terminal after $m$ steps) are $\le \rho <1$, so $\Vert P_{\mu }^m{\Vert }_{\infty }\le \rho$, giving $\Vert P_{\mu }^{km}{\Vert }_{\infty }\le {\rho }^k\to 0$, hence $\rho (P_{\mu })\le {\rho }^{1/m}<1$. Conversely if $\rho (P_{\mu })<1$ then $\Vert P_{\mu }^k\Vert \to 0$, so the probability of being non-terminal at step $k$ tends to $0$ for every start, i.e. absorption is certain and $\mu$ is proper. With $\rho (P_{\mu })<1$, no eigenvalue of $P_{\mu }$ equals $1$, so $I-P_{\mu }$ is invertible; $(I-P_{\mu }){\sum }_{k=0}^m{P}_{\mu }^k=I-P_{\mu }^{m+1}\to I$ gives ${\sum }_{k\ge 0}{P}_{\mu }^k=(I-P_{\mu }{)}^{-1}$. Solving $J_{\mu }=g_{\mu }+P_{\mu }{J}_{\mu }$ yields the finite $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }={\sum }_{k\ge 0}{P}_{\mu }^k{g}_{\mu }$. $\square$

Proposition 2 (existence of the contraction weight). Under assumptions (3.1)-(3.2) there exist $v>0$ and $\beta \in [0,1)$ with ${\sum }_j{p}_{ij}(u)v_j\le \beta v_i$ for all $i$ and all $u\in U(i)$.

Proof. Charge a unit cost at every non-terminal state under every control; under (3.1)-(3.2) the modified SSP has a finite optimal cost $\hat{J}\ge 1>0$ (a proper policy gives finite expected steps; every improper policy is infinite-cost, so the optimum is proper), satisfying $\hat{J}(i)=1+{\min }_u{\sum }_j{p}_{ij}(u)\hat{J}(j)$. Hence ${\sum }_j{p}_{ij}(u)\hat{J}(j)\le \hat{J}(i)-1$ for every $u$. Set $v=\hat{J}$ and $\beta ={\max }_i(v_i-1)/v_i=1-1/{\max }_i{v}_i$; since $v_i\ge 1$, $\beta \in [0,1)$, and ${\sum }_j{p}_{ij}(u)v_j\le v_i-1\le \beta v_i$. $\square$

Proposition 3 (weighted-sup-norm contraction of $T$ and proper $T_{\mu }$). With $v,\beta$ as in Proposition 2, $\Vert TJ-T{J}^{\prime }{\Vert }_v\le \beta \Vert J-J^{\prime }{\Vert }_v$ and, for every proper $\mu$, $\Vert T_{\mu }J-T_{\mu }{J}^{\prime }{\Vert }_v\le \beta \Vert J-J^{\prime }{\Vert }_v$.

Proof. For $i$ fixed, choose $u$ attaining $(TJ)(i)$. Then $(TJ)(i)-(T{J}^{\prime })(i)\le g(i,u)+{\sum }_j{p}_{ij}(u)J(j)-g(i,u)-{\sum }_j{p}_{ij}(u)J^{\prime }(j)={\sum }_j{p}_{ij}(u)(J(j)-J^{\prime }(j))$. Bounding $|J(j)-J^{\prime }(j)|\le v_j\Vert J-J^{\prime }{\Vert }_v$ and using Proposition 2, this is $\le {\sum }_j{p}_{ij}(u)v_j\Vert J-J^{\prime }{\Vert }_v\le \beta v_i\Vert J-J^{\prime }{\Vert }_v$. The symmetric choice of the minimizer for $J^{\prime }$ gives the reverse inequality, so $|(TJ)(i)-(T{J}^{\prime })(i)|\le \beta v_i\Vert J-J^{\prime }{\Vert }_v$, i.e. $|(TJ)(i)-(T{J}^{\prime })(i)|/v_i\le \beta \Vert J-J^{\prime }{\Vert }_v$ for every $i$; the maximum over $i$ is the claim for $T$. For a proper $\mu$, the same chain with the single control $\mu (i)$ in place of the minimum gives the bound for $T_{\mu }$. $\square$

Proposition 4 (existence, uniqueness, value-iteration convergence). $T$ has a unique fixed point $J^{\ast }\in {\mathbb{R}}^n$, and for any $J_0$, $\Vert T^k{J}_0-J^{\ast }{\Vert }_v\le {\beta }^k\Vert J_0-J^{\ast }{\Vert }_v\to 0$.

Proof. $({\mathbb{R}}^n,\Vert \cdot {\Vert }_v)$ is a complete metric space (finite-dimensional, all norms equivalent; 02.01.05). By Proposition 3, $T$ is a $\beta$-contraction with $\beta <1$, so the Banach fixed-point theorem gives a unique $J^{\ast }=T{J}^{\ast }$ and the geometric estimate $\Vert T^k{J}_0-J^{\ast }{\Vert }_v\le {\beta }^k\Vert J_0-J^{\ast }{\Vert }_v$; ${\beta }^k\to 0$ forces convergence. $\square$

Proposition 5 (identification $J^{\ast }={\inf }_{\mu }{J}_{\mu }$ and greedy-optimality criterion). The fixed point $J^{\ast }$ equals the optimal cost ${\inf }_{\mu }{J}_{\mu }$, attained by any proper policy greedy for $J^{\ast }$; and a stationary policy $\mu$ is optimal ($J_{\mu }=J^{\ast }$) if and only if $T_{\mu }{J}^{\ast }=T{J}^{\ast }$.

Proof. Let ${\mu }^{\ast }$ be greedy for $J^{\ast }$: $T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }=J^{\ast }$. The contraction bound (Proposition 3, single control) shows the substochastic $P_{{\mu }^{\ast }}$ obeys ${\sum }_j{p}_{ij}({\mu }^{\ast }(i))v_j\le \beta v_i<v_i$; summing against $v>0$ forces $\rho (P_{{\mu }^{\ast }})\le \beta <1$, so ${\mu }^{\ast }$ is proper (Proposition 1) and $J^{\ast }=J_{{\mu }^{\ast }}<\infty$ by uniqueness of the proper $T_{{\mu }^{\ast }}$ fixed point. For any proper $\mu$, monotonicity of $T_{\mu }$ ($J\le J^{\prime }\Rightarrow T_{\mu }J\le T_{\mu }{J}^{\prime }$, since $P_{\mu }\ge 0$) and $T_{\mu }{J}^{\ast }\ge {\min }_{\nu }{T}_{\nu }{J}^{\ast }=T{J}^{\ast }=J^{\ast }$ give, by iteration, $J_{\mu }={\lim }_k{T}_{\mu }^k{J}^{\ast }\ge J^{\ast }$. For any improper $\mu$, assumption (3.2) gives $J_{\mu }(i)=+\infty$ for some $i$, so $J_{\mu }\ge J^{\ast }$ pointwise fails nowhere. Hence ${\inf }_{\mu }{J}_{\mu }\ge J^{\ast }$, while $J_{{\mu }^{\ast }}=J^{\ast }$ attains it; so $J^{\ast }={\inf }_{\mu }{J}_{\mu }$. For the criterion: if $T_{\mu }{J}^{\ast }=T{J}^{\ast }=J^{\ast }$, then $J^{\ast }$ is the fixed point of $T_{\mu }$, so $\mu$ is proper (as for ${\mu }^{\ast }$) and $J^{\ast }=J_{\mu }$, optimal. Conversely if $J_{\mu }=J^{\ast }$, applying $T_{\mu }$ to its fixed point, $T_{\mu }{J}^{\ast }=T_{\mu }{J}_{\mu }=J_{\mu }=J^{\ast }=T{J}^{\ast }$, so $\mu$ is greedy. $\square$

Proposition 6 (policy improvement and finite termination over proper policies). If $\mu$ is proper and $\bar{\mu }$ is greedy for $J_{\mu }$, then $\bar{\mu }$ is proper and $J_{\bar{\mu }}\le J_{\mu }$, with strict inequality somewhere unless $\mu$ is optimal; for finite $S,U$ policy iteration terminates at an optimal proper policy in finitely many iterations.

Proof. Greediness gives $T_{\bar{\mu }}{J}_{\mu }=T{J}_{\mu }\le T_{\mu }{J}_{\mu }=J_{\mu }$. Iterating the monotone $T_{\bar{\mu }}$, $T_{\bar{\mu }}^k{J}_{\mu }$ is nonincreasing and bounded above by the finite $J_{\mu }$. Since $T_{\bar{\mu }}^k{J}_{\mu }={\sum }_{m=0}^{k-1}{P}_{\bar{\mu }}^m{g}_{\bar{\mu }}+P_{\bar{\mu }}^k{J}_{\mu }$ stays bounded above for all $k$, the partial sums ${\sum }_m{P}_{\bar{\mu }}^m{g}_{\bar{\mu }}$ converge, forcing $\Vert P_{\bar{\mu }}^k\Vert \to 0$, hence $\rho (P_{\bar{\mu }})<1$ and $\bar{\mu }$ proper (Proposition 1). Then $T_{\bar{\mu }}$ contracts and $T_{\bar{\mu }}^k{J}_{\mu }\to J_{\bar{\mu }}$, so $J_{\bar{\mu }}\le J_{\mu }$. If $J_{\bar{\mu }}=J_{\mu }$ everywhere, $J_{\mu }=T_{\bar{\mu }}{J}_{\mu }=T{J}_{\mu }$, so $J_{\mu }=J^{\ast }$ by Proposition 4; thus strict improvement somewhere unless $\mu$ is optimal. For finite $S,U$ the costs $J_{{\mu }_k}$ strictly decrease componentwise until optimality, no proper policy repeats, and there are at most ${\prod }_i|U(i)|<\infty$ of them, so a ${\mu }_k$ with $T_{{\mu }_k}{J}_{{\mu }_k}=T{J}_{{\mu }_k}$, optimal by Proposition 5, is reached in finitely many steps. $\square$

Connections Master

• The infinite-horizon discounted dynamic programming of 44.08.02 is the special case of this unit obtained by adding a uniform termination probability $1-\alpha$ to every state: every policy then becomes proper through geometric absorption, the constant weight $v\equiv 1$ yields contraction modulus $\beta =\alpha$, and the SSP optimality equation $J^{\ast }=T{J}^{\ast }$ collapses to the discounted Bellman equation. The discounted theory's free contraction is recovered here as the uniform-weight instance of the constructed weighted-sup-norm contraction; conversely SSP is what the discounted method becomes when the discount is replaced by a genuine absorbing terminal state and a manufactured weight vector restores the contraction.

• The Markov decision process of 44.08.03 supplies the controlled-transition substrate that SSP specializes to the undiscounted, terminating case: an SSP is an MDP with $\alpha =1$, a cost-free absorbing state, and the proper/improper dichotomy replacing the automatic well-posedness that discounting provided. Fixing a proper stationary policy collapses the SSP to a substochastic Markov chain on the non-terminal states whose resolvent $(I-P_{\mu }{)}^{-1}$ is the discounted-resolvent analogue with survival probability one, and the policy-evaluation linear solve $J_{\mu }=(I-P_{\mu }{)}^{-1}{g}_{\mu }$ is the SSP counterpart of the discounted $(I-\alpha P_{\mu }{)}^{-1}{r}_{\mu }$.

• The Banach fixed-point theorem 02.01.05 is again the existence-uniqueness-and-rate engine, but read in a weighted sup-norm on ${\mathbb{R}}^n$ rather than the plain one: the constructed weight $v$ and modulus $\beta$ instantiate the abstract contraction on the finite-dimensional complete space of total-cost functions vanishing at the terminal state. The same fixed-point principle that powers SSP also drives the fixed-point iterations and contraction-based convergence of numerical analysis 43.02.02, so the stochastic shortest path problem is the terminating-control reading of one of analysis's most reused theorems, distinguished only by the weighting that rescues the contraction when discounting is absent.

• The Hamilton-Jacobi-Bellman equation appearing in the linear-quadratic regulator 44.07.02 is the continuous-time, undiscounted-cost shadow of the SSP optimality equation: where the discrete SSP minimizes total cost until absorption and yields $J^{\ast }=T{J}^{\ast }$, the continuous problem yields a first-order partial differential equation for the cost-to-go to a target set, with properness corresponding to controllability to the target and the SSP weight vector to a Lyapunov function certifying finite-time-ish reachability. The discrete weighted contraction is the well-posedness mechanism the continuous HJB problem must replace with verification or viscosity-solution arguments.

Historical & philosophical context Master

The stochastic shortest path problem grew out of two strands of Richard Bellman's 1950s dynamic-programming program: the deterministic shortest-path and routing problems solved by the Bellman-Ford label-correcting recursion, and the undiscounted total-cost control of terminating Markov chains. The rigorous modern treatment, isolating the proper/improper dichotomy and proving existence and uniqueness of the optimal cost together with the weighted-sup-norm contraction, is due to Dimitri Bertsekas and John Tsitsiklis in their 1991 paper An Analysis of Stochastic Shortest Path Problems ^{[Bertsekas Tsitsiklis 1991]}, which established that under the two assumptions the Bellman operator is a contraction in a weighted norm and that value and policy iteration converge, with $J^{\ast }$ the unique solution of Bellman's equation among functions vanishing at the terminal state.

The systematic textbook development — the proper/improper classification, the assumptions, the weighted-contraction construction, value and policy iteration, Gauss-Seidel and asynchronous variants, and the demonstration that discounted DP, deterministic shortest paths, and first-passage problems are SSP special cases — is given by Bertsekas in Dynamic Programming and Optimal Control Volume 2 Chapter 3 ^{[Bertsekas Vol. 2 Ch. 3]}, the anchor for this unit. The SSP framework became the canonical episodic model for approximate and neuro-dynamic programming in Bertsekas and Tsitsiklis's 1996 monograph Neuro-Dynamic Programming ^{[Bertsekas Tsitsiklis Neuro-Dynamic Programming Ch. 2]}, where real-time dynamic programming and simulation-based methods are built on the same assumptions, and it underlies the heuristic-search RTDP and LRTA* algorithms developed in the artificial-intelligence literature by Andrew Barto, Steven Bradtke, and Satinder Singh.

Bibliography Master

@book{bertsekas2012dpvol2,
  author    = {Bertsekas, Dimitri P.},
  title     = {Dynamic Programming and Optimal Control, Volume 2: Approximate Dynamic Programming},
  edition   = {4},
  publisher = {Athena Scientific},
  year      = {2012}
}

@book{bertsekastsitsiklis1996ndp,
  author    = {Bertsekas, Dimitri P. and Tsitsiklis, John N.},
  title     = {Neuro-Dynamic Programming},
  publisher = {Athena Scientific},
  year      = {1996}
}

@article{bertsekastsitsiklis1991ssp,
  author  = {Bertsekas, Dimitri P. and Tsitsiklis, John N.},
  title   = {An Analysis of Stochastic Shortest Path Problems},
  journal = {Mathematics of Operations Research},
  volume  = {16},
  number  = {3},
  year    = {1991},
  pages   = {580--595}
}

@article{bartobradtkesingh1995rtdp,
  author  = {Barto, Andrew G. and Bradtke, Steven J. and Singh, Satinder P.},
  title   = {Learning to Act Using Real-Time Dynamic Programming},
  journal = {Artificial Intelligence},
  volume  = {72},
  number  = {1--2},
  year    = {1995},
  pages   = {81--138}
}

@book{puterman1994mdp,
  author    = {Puterman, Martin L.},
  title     = {Markov Decision Processes: Discrete Stochastic Dynamic Programming},
  publisher = {John Wiley \& Sons},
  year      = {1994}
}