Infinite-Horizon Discounted Dynamic Programming: Bellman Contraction, Value and Policy Iteration

Intuition Beginner

The previous unit planned over a fixed number of stages by working backward from a known end. But many decision problems have no end in sight: a power company balancing a reservoir forever, a robot wandering a warehouse indefinitely, an investor reinvesting without a final date. There is no last stage to start the backward sweep from. Infinite-horizon dynamic programming is the method for these never-ending problems, and the surprise is that endlessness can make the problem cleaner, not messier.

The first issue is that adding up costs over infinitely many stages could give an infinite total, which would make every plan look equally bad. The fix is discounting: a cost paid one stage from now counts a little less than a cost paid right now, two stages out counts less still, and so on, each future stage shrunk by a factor smaller than one. Distant costs fade toward nothing, so the whole infinite sum settles on a finite number. This matches how people and companies actually value the future, and it is what keeps the mathematics finite.

Because the problem looks the same at every stage — the same options, the same rule for what happens next — the best plan does not depend on what stage you are at. You can describe the optimal behavior by a single rule that says, for each situation, what to do, used forever. And the value of each situation satisfies one self-referential equation: the value of being here equals the best immediate cost plus the discounted value of wherever you land next. That single equation, applied to itself, is the whole story.

The payoff is a method that finds those values by repetition. Start with any guess for the value of every situation, apply the one-stage rule once to update them all, and repeat. The guesses march steadily toward the true values, and because future costs are discounted, they march fast.

Visual Beginner

Picture one update of the value table. You hold a current guess for the value of every situation. To improve the guess for a single situation, you look one step ahead: for each available action, add its immediate cost to the discounted current guess at wherever that action sends you, then keep the smallest such total. Do this for every situation at once, and you have a new, better table. Repeat.

The discount factor, a number between $0$ and $1$, multiplies the next-step value before you add it on. A factor near $0$ means you barely care about the future, so the table settles almost instantly. A factor near $1$ means the future matters a lot, so the table takes more sweeps to settle but still settles.

discount factor	how much the future counts	how fast the table settles
close to $0$	almost not at all	settles in a few sweeps
middling, like $0.9$	the near future counts a lot	settles steadily
close to $1$	nearly as much as the present	settles slowly but surely

Each sweep shrinks the gap between your table and the true values by the discount factor, so the error falls by that fixed proportion every time.

Worked example Beginner

A machine is either up or down each day. Each morning, if it is up you may leave it (cost $0$) or inspect it (cost $2$); if it is down you must repair it (cost $5$). Leaving an up machine, it stays up the next day; here, to keep arithmetic clean, assume inspecting an up machine also keeps it up, and repairing a down machine makes it up the next day. We want the cheapest long-run discounted cost with discount factor $0.5$.

This setup makes leaving always at least as cheap as inspecting from the up state, so we expect "leave" to win there. Let us find the values by repeated updates. Write $V(\text{up})$ and $V(\text{down})$ for the current guesses, and start both at $0$.

Sweep 1. From up, the cheapest action is "leave": cost $0$ plus $0.5$ times next value $V(\text{up})=0$, total $0$. From down, the only action is "repair": cost $5$ plus $0.5\times V(\text{up})=0$, total $5$. New table: $V(\text{up})=0$, $V(\text{down})=5$.

Sweep 2. From up, leave: $0+0.5\times 0=0$. From down, repair: $5+0.5\times 0=5$. New table: $V(\text{up})=0$, $V(\text{down})=5$.

The table did not change, so we have reached the true values: $V(\text{up})=0$ and $V(\text{down})=5$. An always-up machine you simply leave alone costs nothing in the long run; a machine that starts down costs $5$ once to fix and then nothing.

What this tells us: the same one-step rule, applied over and over, drove the value table to a place where one more application changes nothing. That unmoving table is the solution, and the rule "leave when up, repair when down" is the optimal forever-policy read off from it.

Check your understanding Beginner

Formal definition Intermediate+

A stationary discounted controlled problem is specified by a state space $S$, a control space $C$, a nonempty admissible-control set $U(x)\subseteq C$ for each $x\in S$, a disturbance space $D$, a system map $f:S\times C\times D\to S$, a disturbance law $P(\cdot \mid x,u)$ on $D$ depending only on $(x,u)$ — the controlled-Markov structure of 37.05.01 — a bounded stage cost $g:S\times C\times D\to \mathbb{R}$, and a discount factor $\alpha \in (0,1)$. Nothing depends on the stage index; this is the infinite-horizon stationary counterpart of the finite-horizon problem 44.08.01. A stationary policy is a single map $\mu :S\to C$ with $\mu (x)\in U(x)$ used at every stage; the expected discounted cost of $\mu$ from $x_0$ is

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

which converges because $|g|\le M$ gives $|J_{\mu }|\le M/(1-\alpha )$. The optimal cost is $J^{\ast }(x)={\inf }_{\mu }{J}_{\mu }(x)$, the infimum over (in general, history-dependent) policies; under discounting it is attained within stationary policies.

Let $B(S)$ denote the space of bounded functions $J:S\to \mathbb{R}$ with the supremum norm $\Vert J{\Vert }_{\infty }={\sup }_{x\in S}|J(x)|$, a Banach space (a complete normed space; the metric/completeness substrate is 02.01.05). Define the Bellman (dynamic-programming) operator $T:B(S)\to B(S)$ and the policy operator $T_{\mu }:B(S)\to B(S)$ by

$$(TJ)(x)=\underset{u\in U(x)}{\inf }{\mathbb{E}}_w[g(x,u,w)+\alpha J(f(x,u,w)\left)\right],(T_{\mu }J)(x)={\mathbb{E}}_w[g(x,\mu (x),w)+\alpha J(f(x,\mu (x),w)\left)\right],$$

the expectations over $w\sim P(\cdot \mid x,\cdot )$. Both map $B(S)$ into itself: boundedness of $g$ and $\Vert J{\Vert }_{\infty }<\infty$ keep the outputs within $M+\alpha \Vert J{\Vert }_{\infty }$. The discounted Bellman equation is the fixed-point equation $J^{\ast }=T{J}^{\ast }$, and the policy-evaluation equation is $J_{\mu }=T_{\mu }{J}_{\mu }$. A stationary policy $\mu$ is greedy with respect to $J\in B(S)$ if $T_{\mu }J=TJ$, i.e. $\mu (x)$ attains the infimum defining $(TJ)(x)$ for every $x$. The symbols $T$ (Bellman operator), $T_{\mu }$ (policy operator), $J^{\ast }$ (optimal cost), $J_{\mu }$ (policy cost), $\alpha$ (discount factor), and $\Vert \cdot {\Vert }_{\infty }$ (sup-norm) are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "The optimal policy depends on the stage, as in the finite-horizon problem." It does not. Stationarity of the data plus discounting make the problem identical at every stage, so the optimal behavior is one stage-independent map ${\mu }^{\ast }$ used forever. The finite-horizon $J_k$ varied with $k$ only because the remaining horizon shrank; an infinite remaining horizon is the same from every stage.

• "Without a terminal stage there is no backward recursion, so dynamic programming cannot apply." The backward recursion is replaced by iteration of the same operator: $J_{k+1}=T{J}_k$ from any start converges to $J^{\ast }$. The finite-horizon $J_k$ are exactly the iterates $T^{N-k}(g_N)$; removing the horizon turns a finite backward sweep into an infinite forward iteration of one operator.

• "Any bounded function solving $J=TJ$ might fail to be the optimal cost." Under $\alpha <1$ the operator $T$ has a unique fixed point in $B(S)$, and that fixed point is $J^{\ast }$. Uniqueness is what makes "solve Bellman's equation" a complete method: there is no spurious second solution to rule out.

• "Policy iteration could cycle or improve forever without stopping." For a finite-state, finite-action MDP each improvement step strictly lowers the cost of at least one state unless the policy is already optimal, and there are only finitely many stationary policies, so the process terminates at an optimal policy in finitely many steps. The discount-induced monotonicity $J_{{\mu }_{k+1}}\le J_{{\mu }_k}$ forbids cycling.

Key theorem with proof Intermediate+

The signature result is that the Bellman operator is a sup-norm contraction of modulus $\alpha$, from which existence, uniqueness, value-iteration convergence, and greedy optimality all follow by the Banach fixed-point theorem 02.01.05. It is the single statement that converts an infinite-stage optimization into the search for one operator's fixed point.

Theorem (Bellman contraction and the discounted optimality equation). On $B(S)$ with the sup-norm, both $T$ and every $T_{\mu }$ are contractions of modulus $\alpha$:

$$\Vert TJ-T{J}^{\prime }{\Vert }_{\infty }\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty },\Vert T_{\mu }J-T_{\mu }{J}^{\prime }{\Vert }_{\infty }\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }.$$

Consequently $T$ has a unique fixed point $J^{\ast }\in B(S)$, which equals the optimal cost; value iteration $J_{k+1}=T{J}_k$ from any $J_0\in B(S)$ converges geometrically, $\Vert J_k-J^{\ast }{\Vert }_{\infty }\le {\alpha }^k\Vert J_0-J^{\ast }{\Vert }_{\infty }$; each $T_{\mu }$ has a unique fixed point $J_{\mu }$; and a stationary policy ${\mu }^{\ast }$ is optimal if and only if it is greedy with respect to $J^{\ast }$, i.e. $T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }$.

Proof. Fix $J,J^{\prime }\in B(S)$ and $x\in S$. For each admissible $u\in U(x)$, the disturbance integrand satisfies $\alpha {\mathbb{E}}_w[J(f(x,u,w))]-\alpha {\mathbb{E}}_w[J^{\prime }(f(x,u,w))]=\alpha {\mathbb{E}}_w[J(\cdot )-J^{\prime }(\cdot )]$, bounded in absolute value by $\alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ since $|J(y)-J^{\prime }(y)|\le \Vert J-J^{\prime }{\Vert }_{\infty }$ pointwise and the expectation is an average. Hence for every $u$,

$${\mathbb{E}}_w[g+\alpha J(\cdot )]\le {\mathbb{E}}_w[g+\alpha J^{\prime }(\cdot )]+\alpha \Vert J-J^{\prime }{\Vert }_{\infty }.$$

Taking the infimum over $u\in U(x)$ on both sides (the constant survives the infimum) gives $(TJ)(x)\le (T{J}^{\prime })(x)+\alpha \Vert J-J^{\prime }{\Vert }_{\infty }$; the symmetric argument gives the reverse, so $|(TJ)(x)-(T{J}^{\prime })(x)|\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ for all $x$, which is the contraction bound for $T$. The same estimate without the infimum (a single fixed control $\mu (x)$) yields it for $T_{\mu }$.

Because $B(S)$ is complete and $\alpha <1$, the Banach fixed-point theorem 02.01.05 gives a unique fixed point $J^{\ast }=T{J}^{\ast }$, the convergence $T^k{J}_0\to J^{\ast }$ with the geometric a-priori estimate $\Vert T^k{J}_0-J^{\ast }{\Vert }_{\infty }\le {\alpha }^k\Vert J_0-J^{\ast }{\Vert }_{\infty }$ (specialize the metric bound to $d(J,J^{\prime })=\Vert J-J^{\prime }{\Vert }_{\infty }$), and a unique $J_{\mu }=T_{\mu }{J}_{\mu }$ for each $\mu$.

That the fixed point $J^{\ast }$ equals the optimal cost: for any stationary $\mu$, $T_{\mu }{J}^{\ast }\ge T{J}^{\ast }=J^{\ast }$ pointwise (the infimum is $\le$ any particular control), and monotonicity of $T_{\mu }$ (if $J\le J^{\prime }$ then $T_{\mu }J\le T_{\mu }{J}^{\prime }$, since the integrand is increasing in $J$ and $\alpha >0$) iterated gives $J_{\mu }={\lim }_k{T}_{\mu }^k{J}^{\ast }\ge J^{\ast }$; thus ${\inf }_{\mu }{J}_{\mu }\ge J^{\ast }$. Conversely, choose ${\mu }^{\ast }$ greedy for $J^{\ast }$ (so $T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }=J^{\ast }$, meaning $J^{\ast }$ is the fixed point of $T_{{\mu }^{\ast }}$, i.e. $J^{\ast }=J_{{\mu }^{\ast }}$ by uniqueness); then ${\inf }_{\mu }{J}_{\mu }\le J_{{\mu }^{\ast }}=J^{\ast }$. The two inequalities give $J^{\ast }={\inf }_{\mu }{J}_{\mu }$, the optimal cost, attained by ${\mu }^{\ast }$. Finally, if $\mu$ is optimal then $J_{\mu }=J^{\ast }$, and applying $T_{\mu }$ to its own fixed point, $T_{\mu }{J}^{\ast }=T_{\mu }{J}_{\mu }=J_{\mu }=J^{\ast }=T{J}^{\ast }$, so $\mu$ is greedy for $J^{\ast }$; the converse was just shown. $\square$

Bridge. This theorem is the foundational reason infinite-horizon control reduces to solving a single equation: the $\alpha$-contraction collapses the limit over infinitely many stages into the unique fixed point of one operator, and the geometric estimate $\Vert J_k-J^{\ast }{\Vert }_{\infty }\le {\alpha }^k\Vert J_0-J^{\ast }{\Vert }_{\infty }$ is exactly the rate at which value iteration homes in. The central insight is that the discount factor is the contraction modulus — the same $\alpha$ that keeps the infinite cost sum finite is the number that shrinks the error each sweep — so convergence speed and well-posedness have one common cause. This is exactly the structure of the finite-horizon backward recursion 44.08.01 run to its limit: the $J_k$ there are the iterates $T^{N-k}$ here, and the stage-wise monotonicity used in that optimality proof is the same monotonicity of $T_{\mu }$ used here. It generalises the Banach fixed-point theorem 02.01.05 from an abstract metric space to the concrete sup-norm space of value functions, and it builds toward the Markov decision process 44.08.03, where $T$ becomes the optimality operator over actions and transition kernels. Putting these together, value iteration, policy iteration, and the linear-programming formulation are three algorithms for one fixed point, and the bridge is that the greedy operator $T{J}^{\ast }=J^{\ast }$ both certifies optimality and reads off the optimal stationary policy; this appears again in the Hamilton–Jacobi–Bellman equation 44.07.02, the continuous-time, undiscounted-limit shadow of the same fixed-point principle.

Exercises Intermediate+

Advanced results Master

The discounted theory extends in four directions: the policy-iteration algorithm with its monotone convergence and finite termination for finite models, the error bounds that make approximate value iteration usable, the linear-programming reformulation of the optimality equation, and the average-cost criterion recovered from the discounted one as $\alpha \uparrow 1$.

Theorem 1 (policy iteration: monotone improvement and finite termination). Policy iteration generates a sequence of stationary policies ${\mu }_0,{\mu }_1,\dots$ by alternating exact policy evaluation — solve $J_{{\mu }_k}=T_{{\mu }_k}{J}_{{\mu }_k}$, the unique fixed point of the $\alpha$-contraction $T_{{\mu }_k}$ (a linear system $J_{{\mu }_k}=g_{{\mu }_k}+\alpha P_{{\mu }_k}{J}_{{\mu }_k}$ for finite models) — with policy improvement — let ${\mu }_{k+1}$ be greedy for $J_{{\mu }_k}$, i.e. $T_{{\mu }_{k+1}}{J}_{{\mu }_k}=T{J}_{{\mu }_k}$. Then $J_{{\mu }_{k+1}}\le J_{{\mu }_k}$ pointwise, with strict decrease at some state unless ${\mu }_k$ is optimal. For a finite-state, finite-action MDP there are finitely many stationary policies and the cost strictly decreases until optimality, so policy iteration terminates with an optimal policy in finitely many iterations; in fact it converges at least as fast as value iteration and typically far faster, since each step performs an exact infinite-horizon evaluation ^{[Bertsekas Vol. 2 Ch. 1]}.

Theorem 2 (value-iteration error bounds and approximate DP). For value iteration $J_{k+1}=T{J}_k$, the contraction gives the a-priori bound $\Vert J_k-J^{\ast }{\Vert }_{\infty }\le {\alpha }^k\Vert J_0-J^{\ast }{\Vert }_{\infty }$ and the computable a-posteriori bound $\Vert J_k-J^{\ast }{\Vert }_{\infty }\le \frac{\alpha }{1-\alpha }\Vert J_k-J_{k-1}{\Vert }_{\infty }$, and the greedy policy ${\mu }_k$ extracted from $J_k$ is near-optimal: $\Vert J_{{\mu }_k}-J^{\ast }{\Vert }_{\infty }\le \frac{2\alpha }{1-\alpha }\Vert J_k-J^{\ast }{\Vert }_{\infty }$. When each iterate carries an approximation error $\Vert {\tilde{J}}_{k+1}-T{\tilde{J}}_k{\Vert }_{\infty }\le \epsilon$ (the regime of approximate dynamic programming and reinforcement learning with function approximation), the errors accumulate to a controlled steady state ${\mathrm{limsup}}_k\Vert {\tilde{J}}_k-J^{\ast }{\Vert }_{\infty }\le \frac{\epsilon }{1-\alpha }$, and the greedy-policy loss is bounded by $\frac{2\alpha \epsilon }{(1-\alpha {)}^2}$. The factor $1/(1-\alpha )$, the effective horizon, governs how approximation error inflates ^{[Bertsekas Vol. 2 Ch. 2]}.

Theorem 3 (linear-programming formulation). For a finite discounted MDP, $J^{\ast }$ is the unique solution of the Bellman equation, and the inequalities $J(x)\le {\mathbb{E}}_w[g(x,u,w)+\alpha J(f(x,u,w))]$ for all $(x,u)$ characterize the functions $J\le TJ$, which (by monotonicity, $J\le TJ\Rightarrow J\le T^{k}J\to J^{\ast }$) lie below $J^{\ast }$. Hence $J^{\ast }$ solves the linear program $\max {\sum }_{x}c(x)J(x)$ subject to those linear constraints, for any strictly positive weights $c$. The dual program ranges over discounted state-action occupation measures, giving an exact LP route to the optimal cost and policy and connecting discounted DP to polyhedral optimization ^{[Puterman Ch. 6]}.

Theorem 4 (average cost via the vanishing-discount limit). When future costs are not discounted, the relevant objective is the long-run average cost ${\bar{J}}_{\mu }={\mathrm{limsup}}_N\frac{1}{N}\mathbb{E}[{\sum }_{k=0}^{N-1}g(x_k,\mu (x_k),w_k)]$. Under suitable recurrence (e.g. a unichain finite MDP), the optimal average cost is a constant $g^{\ast }$ (the gain) solving the average-cost optimality equation $g^{\ast }+h(x)={\min }_{u\in U(x)}{\mathbb{E}}_w[g(x,u,w)+h(f(x,u,w))]$ for a bias function $h$ unique up to an additive constant. This equation is the $\alpha \uparrow 1$ limit of the discounted equation: $J_{\alpha }^{\ast }(x)=\frac{g^{\ast }}{1-\alpha }+h(x)+o(1)$, so the discounted value blows up at rate $g^{\ast }/(1-\alpha )$ while its state-dependent part converges to the bias. The contraction modulus $\alpha \to 1$ degenerates, which is why the average-cost theory requires the separate recurrence hypotheses that discounting otherwise renders unnecessary ^{[Puterman Ch. 8]}.

Synthesis. The foundational reason infinite-horizon discounted control is solvable is that the discount factor $\alpha$ is simultaneously what renders the infinite cost sum finite and the contraction modulus that makes the Bellman operator have a unique fixed point — these are one fact, not two. The central insight is the interchange this licenses: an optimization over all policies over all stages becomes the search for $J^{\ast }=T{J}^{\ast }$, and the optimal stationary policy is read off as the greedy policy $T_{{\mu }^{\ast }}{J}^{\ast }=J^{\ast }$. This is exactly the finite-horizon backward recursion 44.08.01 carried to its limit — the $J_k$ there are the iterates $T^{N-k}$ here, and value iteration is that recursion run forward forever. Value iteration (geometric rate ${\alpha }^k$), policy iteration (the Newton-like step, finitely terminating for finite models), and the linear program ($J\le TJ\Rightarrow J\le J^{\ast }$) are three algorithms for the same fixed point. The framework generalises the Banach fixed-point theorem 02.01.05 to the sup-norm space of value functions, is dual to the Pontryagin co-state sweep through the Hamilton–Jacobi–Bellman equation 44.07.02, and builds toward the Markov decision process 44.08.03 and the average-cost criterion whose vanishing-discount limit reattaches the discounted value to a gain-plus-bias decomposition. Putting these together, the same algebraic move that powered the finite-horizon method — collapsing a sum over all futures into a one-step optimization against a stored value summary — appears again as the engine of approximate dynamic programming and value-function-based reinforcement learning, where the effective horizon $1/(1-\alpha )$ measures the difficulty.

Full proof set Master

Proposition 1 (contraction of $T$ and $T_{\mu }$). On $(B(S),\Vert \cdot {\Vert }_{\infty })$, $\Vert TJ-T{J}^{\prime }{\Vert }_{\infty }\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ and $\Vert T_{\mu }J-T_{\mu }{J}^{\prime }{\Vert }_{\infty }\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ for all $J,J^{\prime }\in B(S)$.

Proof. For fixed $x,u$, $|{\mathbb{E}}_w[\alpha J(f(x,u,w))]-{\mathbb{E}}_w[\alpha J^{\prime }(f(x,u,w))]|=\alpha |{\mathbb{E}}_w[J(\cdot )-J^{\prime }(\cdot )]|\le \alpha {\mathbb{E}}_w|J(\cdot )-J^{\prime }(\cdot )|\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$, the last step because $|J(y)-J^{\prime }(y)|\le \Vert J-J^{\prime }{\Vert }_{\infty }$ for every $y$ and expectation preserves this bound. Therefore ${\mathbb{E}}_w[g+\alpha J(\cdot )]\le {\mathbb{E}}_w[g+\alpha J^{\prime }(\cdot )]+\alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ for each $u$. For $T_{\mu }$ the single control $\mu (x)$ gives the bound directly. For $T$, take the infimum over $u\in U(x)$: ${\inf }_u{A}_u\le {\inf }_u(B_u+c)=c+{\inf }_u{B}_u$ for a constant $c$, so $(TJ)(x)\le (T{J}^{\prime })(x)+\alpha \Vert J-J^{\prime }{\Vert }_{\infty }$; swapping $J,J^{\prime }$ gives the reverse, hence $|(TJ)(x)-(T{J}^{\prime })(x)|\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ for all $x$, and the supremum over $x$ is the claim. $\square$

Proposition 2 (existence, uniqueness, and value-iteration convergence). $T$ has a unique fixed point $J^{\ast }\in B(S)$, and for any $J_0\in B(S)$, $\Vert T^k{J}_0-J^{\ast }{\Vert }_{\infty }\le {\alpha }^k\Vert J_0-J^{\ast }{\Vert }_{\infty }\to 0$.

Proof. $B(S)$ with the sup-norm is a Banach space, in particular a complete metric space under $d(J,J^{\prime })=\Vert J-J^{\prime }{\Vert }_{\infty }$ 02.01.05. By Proposition 1, $T$ is an $\alpha$-contraction with $\alpha <1$. The Banach fixed-point theorem gives a unique fixed point $J^{\ast }=T{J}^{\ast }$ and the geometric estimate $d(T^k{J}_0,J^{\ast })\le {\alpha }^{k}d(J_0,J^{\ast })$, which is the stated bound; ${\alpha }^k\to 0$ forces convergence. $\square$

Proposition 3 (monotonicity and $J^{\ast }={\inf }_{\mu }{J}_{\mu }$). $T$ and each $T_{\mu }$ are monotone: $J\le J^{\prime }\Rightarrow TJ\le T{J}^{\prime }$ and $T_{\mu }J\le T_{\mu }{J}^{\prime }$. The fixed point $J^{\ast }$ equals the optimal cost ${\inf }_{\mu }{J}_{\mu }$, attained by any policy greedy for $J^{\ast }$.

Proof. Monotonicity: if $J\le J^{\prime }$ then $J(f(x,u,w))\le J^{\prime }(f(x,u,w))$ pointwise; multiplying by $\alpha >0$, adding $g$, and taking expectation (order-preserving) gives ${\mathbb{E}}_w[g+\alpha J(\cdot )]\le {\mathbb{E}}_w[g+\alpha J^{\prime }(\cdot )]$; the infimum over $u$ preserves the inequality, so $TJ\le T{J}^{\prime }$, and the single-control case gives $T_{\mu }J\le T_{\mu }{J}^{\prime }$. Now for any $\mu$, $T_{\mu }{J}^{\ast }\ge {\inf }_{\nu }{T}_{\nu }{J}^{\ast }=T{J}^{\ast }=J^{\ast }$; applying $T_{\mu }$ repeatedly and using its monotonicity, $T_{\mu }^k{J}^{\ast }\ge J^{\ast }$ for all $k$, and $T_{\mu }^k{J}^{\ast }\to J_{\mu }$ (Proposition 2 for $T_{\mu }$), so $J_{\mu }\ge J^{\ast }$; thus ${\inf }_{\mu }{J}_{\mu }\ge J^{\ast }$. Let ${\mu }^{\ast }$ be greedy for $J^{\ast }$: $T_{{\mu }^{\ast }}{J}^{\ast }=T{J}^{\ast }=J^{\ast }$, so $J^{\ast }$ is the fixed point of $T_{{\mu }^{\ast }}$, i.e. $J^{\ast }=J_{{\mu }^{\ast }}$ by uniqueness, whence ${\inf }_{\mu }{J}_{\mu }\le J^{\ast }$. Therefore $J^{\ast }={\inf }_{\mu }{J}_{\mu }=J_{{\mu }^{\ast }}$. $\square$

Proposition 4 (greedy optimality criterion). A stationary policy $\mu$ is optimal ($J_{\mu }=J^{\ast }$) if and only if $T_{\mu }{J}^{\ast }=T{J}^{\ast }$ (i.e. $\mu$ is greedy with respect to $J^{\ast }$).

Proof. If $T_{\mu }{J}^{\ast }=T{J}^{\ast }=J^{\ast }$, then $J^{\ast }$ is a fixed point of $T_{\mu }$, so $J^{\ast }=J_{\mu }$ by uniqueness (Proposition 2 applied to $T_{\mu }$): $\mu$ is optimal. Conversely, if $J_{\mu }=J^{\ast }$, then applying $T_{\mu }$ to its fixed point $J_{\mu }$, $T_{\mu }{J}^{\ast }=T_{\mu }{J}_{\mu }=J_{\mu }=J^{\ast }=T{J}^{\ast }$, so $\mu$ is greedy for $J^{\ast }$. $\square$

Proposition 5 (policy improvement). If $\bar{\mu }$ is greedy for $J_{\mu }$ ($T_{\bar{\mu }}{J}_{\mu }=T{J}_{\mu }$), then $J_{\bar{\mu }}\le J_{\mu }$, with strict inequality somewhere unless $\mu$ is optimal.

Proof. $T_{\bar{\mu }}{J}_{\mu }=T{J}_{\mu }\le T_{\mu }{J}_{\mu }=J_{\mu }$ (infimum $\le$ the particular control $\mu$, and $J_{\mu }=T_{\mu }{J}_{\mu }$ is policy evaluation). Applying the monotone $T_{\bar{\mu }}$ repeatedly, $T_{\bar{\mu }}^{k+1}{J}_{\mu }\le T_{\bar{\mu }}^k{J}_{\mu }\le \cdots \le J_{\mu }$, a nonincreasing sequence; by Proposition 2 for $T_{\bar{\mu }}$ it converges to $J_{\bar{\mu }}$, so $J_{\bar{\mu }}\le J_{\mu }$. If $J_{\bar{\mu }}=J_{\mu }$ everywhere, then $J_{\mu }=T_{\bar{\mu }}{J}_{\mu }=T{J}_{\mu }$, so $J_{\mu }$ solves Bellman's equation and $J_{\mu }=J^{\ast }$ by uniqueness; hence strict improvement somewhere holds whenever $\mu$ is not optimal. $\square$

Proposition 6 (finite termination of policy iteration for finite MDPs). For a finite-state, finite-action MDP, policy iteration terminates at an optimal policy in finitely many iterations.

Proof. By Proposition 5 each improvement step gives $J_{{\mu }_{k+1}}\le J_{{\mu }_k}$ with strict decrease at some state unless ${\mu }_k$ is optimal. The costs $J_{{\mu }_k}$ are thus strictly decreasing in the (componentwise) partial order until optimality, so no policy repeats before termination. There are at most ${\prod }_x|U(x)|<\infty$ stationary policies, so the process cannot improve indefinitely; it reaches a ${\mu }_k$ with $T_{{\mu }_k}{J}_{{\mu }_k}=T{J}_{{\mu }_k}$, i.e. $J_{{\mu }_k}=T{J}_{{\mu }_k}=J^{\ast }$ (Proposition 4), an optimal policy, after finitely many steps. $\square$

Connections Master

• The finite-horizon dynamic programming of 44.08.01 is the truncated, non-stationary precursor of this unit: its cost-to-go functions $J_k$ are exactly the value-iteration iterates $T^{N-k}{J}_N$ of the operator $T$ defined here (in the stationary, discounted case), so removing the horizon converts the finite backward recursion into infinite forward iteration of one operator. The stage-wise monotonicity that drove the finite-horizon optimality proof is the same monotonicity of $T_{\mu }$ that proves $J^{\ast }={\inf }_{\mu }{J}_{\mu }$ and powers policy improvement here; the present unit is what the finite-horizon method becomes when the number of stages is sent to infinity and a discount stabilizes the limit.

• The Markov decision process 44.08.03 is this unit's discounted problem with the controlled-Markov disturbance 37.05.01 promoted to the primitive object: states, actions, a transition kernel $P(y\mid x,a)$, and stage rewards/costs, with the Bellman operator $T$ becoming the MDP optimality operator and the greedy stationary policy becoming the optimal decision rule. The contraction, value iteration, and policy iteration proved here are the discounted-MDP solution methods; reinforcement learning replaces the exact expectation in $T$ with sampled estimates, inheriting the effective-horizon factor $1/(1-\alpha )$ as its sample-complexity scale.

• The Banach fixed-point theorem 02.01.05 is the abstract existence-uniqueness-and-rate engine on which the entire unit rests: this unit is its concrete instantiation on the Banach space $B(S)$ of bounded value functions under the sup-norm, with the discount factor supplying the contraction modulus. The same fixed-point principle underlies Picard–Lindelöf existence for ODEs and the fixed-point iterations of numerical analysis 43.02.02, so discounted dynamic programming is the optimal-control reading of one of analysis's most reused theorems.

• The Hamilton–Jacobi–Bellman equation appearing in the linear-quadratic regulator 44.07.02 is the continuous-time counterpart of the discrete Bellman equation $J^{\ast }=T{J}^{\ast }$: where the discrete operator iterates to a fixed point, the continuous problem yields a first-order partial differential equation for the value function whose stationary solution plays the role of $J^{\ast }$. The discounted discrete-time contraction is the well-posedness mechanism that the continuous HJB problem must replace with viscosity-solution or verification arguments, the discount factor reappearing as a zeroth-order term that makes the HJB operator coercive.

Historical & philosophical context Master

The discounted infinite-horizon formulation grew out of Richard Bellman's dynamic-programming program of the 1950s ^{[Bertsekas Vol. 2 Ch. 1]}, with the operator-theoretic treatment — the Bellman operator as a contraction on a function space — crystallizing through the work of Ronald Howard, whose 1960 monograph introduced policy iteration as an algorithm distinct from successive approximation (value iteration), and David Blackwell, whose 1965 analysis placed discounted dynamic programming on rigorous measure-theoretic footing and proved the optimality of stationary policies. The recognition that the discount factor furnishes a contraction modulus, reducing the existence and uniqueness of the optimal value function to the Banach fixed-point theorem, is the structural fact that organizes the modern theory and is the anchor of this unit's central proof.

The systematic operator formulation with $T$ and $T_{\mu }$ on bounded functions, the contraction and monotonicity lemmas, the value-iteration error bounds, and the approximate dynamic-programming extensions are developed by Dimitri Bertsekas in Dynamic Programming and Optimal Control Volume 2 ^{[Bertsekas Vol. 2 Ch. 2]}, the anchor for this unit. The discounted and average-cost Markov decision process theory, including Howard's policy iteration with its finite-termination proof, the linear-programming formulation, and the vanishing-discount limit relating the discounted value to the average-cost gain and bias, receives its standard reference treatment in Martin Puterman's 1994 monograph ^{[Puterman Ch. 6]}. The same contraction framework became the theoretical backbone of reinforcement learning, where temporal-difference and Q-learning methods are stochastic approximations of value iteration on the Bellman operator.

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{puterman1994mdp,
  author    = {Puterman, Martin L.},
  title     = {Markov Decision Processes: Discrete Stochastic Dynamic Programming},
  publisher = {John Wiley \& Sons},
  year      = {1994}
}

@book{howard1960dp,
  author    = {Howard, Ronald A.},
  title     = {Dynamic Programming and Markov Processes},
  publisher = {MIT Press},
  year      = {1960}
}

@article{blackwell1965discounted,
  author  = {Blackwell, David},
  title   = {Discounted Dynamic Programming},
  journal = {The Annals of Mathematical Statistics},
  volume  = {36},
  number  = {1},
  year    = {1965},
  pages   = {226--235}
}

@book{suttonbarto2018,
  author    = {Sutton, Richard S. and Barto, Andrew G.},
  title     = {Reinforcement Learning: An Introduction},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@book{bertsekas2017dpvol1,
  author    = {Bertsekas, Dimitri P.},
  title     = {Dynamic Programming and Optimal Control, Volume 1},
  edition   = {4},
  publisher = {Athena Scientific},
  year      = {2017}
}