Markov Decision Processes and Stochastic Dynamic Programming

Intuition Beginner

The previous unit on endless decision problems assumed the world reacts to you in a fixed, known way: pick an action and you land in a definite next situation. Reality is rarely that obedient. A delivery drone that turns left might drift in the wind; a patient given a drug might or might not improve; a robot vacuum that bumps a wall might reroute or get stuck. The action you choose tilts the odds of what happens next, but it does not decide the outcome. A Markov decision process is the model for exactly this: deciding under chance.

The ingredients are a list of situations (states), a menu of choices in each situation (actions), a rule of chance saying how likely each next state is once you act, and a reward or cost for each choice. The chance rule has the memoryless feature from the earlier chains unit: where you go next depends only on where you are now and what you do now, not on the whole road behind you. That single property is what keeps the model honest and computable.

What you are looking for is a policy: a rule that tells you which action to take in each state. Because the setup looks the same forever and the future is discounted, the best policy is one fixed rule used every time, and it can be a plain rule with no dice of its own. The value of a state is the best expected discounted reward you can collect starting there.

The payoff mirrors the deterministic case. The value of a state equals the best, over actions, of the immediate reward plus the discounted average value of where you might land. You still find the values by repeating one update until they stop moving, and you still read the best policy off the settled values.

Visual Beginner

Picture a single state with two available actions. Each action is a fan of arrows: one arrow per possible next state, each arrow labeled with its chance, and the chances out of one action add to one. To score an action you add its immediate reward to the discounted average value over its fan, weighting each landing spot by its chance. You compare the two action scores and keep the better one. That better score becomes the state's updated value, and the action that won becomes the recommended choice there.

The only change from the deterministic version is the chance-weighted average inside each action's score. A deterministic problem is the special case where each action's fan has a single arrow of chance one. The discount factor, a number between $0$ and $1$, shrinks the future the same way as before, so the values still settle, and faster when the discount is smaller.

ingredient	what it is	everyday picture
state	the current situation	which room the robot is in
action	a choice available now	which door to try
transition chance	odds of each next state	the door sometimes sticks
reward	payoff for the choice	time saved or battery spent

Worked example Beginner

A small machine is working or broken each day. When working, you may run it (reward $3$ today) or service it (reward $1$ today). Running a working machine leaves it working with chance $0.5$ and breaks it with chance $0.5$. Servicing a working machine keeps it working for sure. When broken, the only choice is repair (reward $0$), which returns it to working for sure the next day. The discount factor is $0.5$, and we collect rewards, so we want the largest long-run discounted total.

We find the values by repeated updates, starting both at $0$. Write $V(\text{work})$ and $V(\text{broke})$.

Sweep 1. From work, score "run": $3+0.5(0.5\cdot V(\text{work})+0.5\cdot V(\text{broke}))=3+0.5(0)=3$. Score "service": $1+0.5V(\text{work})=1+0=1$. Keep the larger, $3$. From broke, "repair": $0+0.5V(\text{work})=0$. New table: $V(\text{work})=3$, $V(\text{broke})=0$.

Sweep 2. From work, "run": $3+0.5(0.5\cdot 3+0.5\cdot 0)=3+0.5(1.5)=3.75$. "Service": $1+0.5\cdot 3=2.5$. Keep $3.75$. From broke, "repair": $0+0.5\cdot 3=1.5$. New table: $V(\text{work})=3.75$, $V(\text{broke})=1.5$.

Sweep 3. From work, "run": $3+0.5(0.5\cdot 3.75+0.5\cdot 1.5)=3+0.5(2.625)=4.31$. "Service": $1+0.5\cdot 3.75=2.875$. Keep $4.31$. From broke, "repair": $0+0.5\cdot 3.75=1.875$.

The "work" value is climbing toward a settled number near $4.5$, and "run" beats "service" every sweep. What this tells us: even though running risks a breakdown, its higher reward and the chance-weighted look-ahead make it the better choice while working; the same one-step rule, now averaging over chance, drives the table to the optimal values, and "run when working, repair when broken" is the best forever-policy read off from them.

Check your understanding Beginner

Formal definition Intermediate+

A Markov decision process (MDP) is a tuple $(S,A,\{A(s){\}}_{s\in S},P,r,\alpha )$: a state space $S$, an action space $A$, a nonempty set of admissible actions $A(s)\subseteq A$ for each $s$, a transition kernel $P(\cdot \mid s,a)$ that assigns to each state-action pair $(s,a)$ with $a\in A(s)$ a probability distribution over $S$ — the controlled-Markov structure generalizing the transition matrix of 37.05.01, here indexed by the chosen action — a bounded reward $r:S\times A\to \mathbb{R}$ with $|r|\le M$, and a discount factor $\alpha \in [0,1)$. The state space is taken finite or, more generally, a Polish (complete separable metric) space with $P$ a measurable kernel and $A(s)$ compact-valued; in the master tier the finite case carries the structure unobscured. The process evolves as $s_{t+1}\sim P(\cdot \mid s_t,a_t)$, and we maximize the expected total discounted reward (signs flip the cost convention of 44.08.02).

A decision rule at time $t$ may depend on the full history $h_t=(s_0,a_0,\dots ,s_t)$ and may randomize; the policy classes nest as ${\Pi }^{SD}\subseteq {\Pi }^{MD}\subseteq {\Pi }^{MR}\subseteq {\Pi }^{HR}$, namely stationary deterministic, Markov deterministic, Markov randomized, and history-dependent randomized. A stationary deterministic policy is a single map $\mu :S\to A$ with $\mu (s)\in A(s)$ used at every stage. For a policy $\pi$ the value function and, for stationary deterministic $\mu$, the action-value function are

$$V^{\pi }(s)={\mathbb{E}}^{\pi }[\sum _{t=0}^{\infty }{\alpha }^{t}r(s_t,a_t)|s_0=s],Q^{\mu }(s,a)=r(s,a)+\alpha \sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)V^{\mu }(s^{\prime }),$$

both finite because $|r|\le M$ gives $|V^{\pi }|\le M/(1-\alpha )$. The optimal value is $V^{\ast }(s)={\sup }_{\pi }{V}^{\pi }(s)$ over ${\Pi }^{HR}$.

On the Banach space $B(S)$ of bounded functions with sup-norm $\Vert V{\Vert }_{\infty }={\sup }_s|V(s)|$ 02.01.05, define the policy operator $T_{\mu }$ and the optimality (Bellman) operator $T$ by

$$(T_{\mu }V)(s)=r(s,\mu (s))+\alpha \sum _{s^{\prime }}P(s^{\prime }\mid s,\mu (s))V(s^{\prime }),(TV)(s)=\underset{a\in A(s)}{\sup }\{r(s,a)+\alpha \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })\}.$$

The Bellman expectation equation is the fixed-point relation $V^{\mu }=T_{\mu }{V}^{\mu }$; the Bellman optimality equation is $V^{\ast }=T{V}^{\ast }$. A stationary deterministic policy $\mu$ is greedy with respect to $V$ if $T_{\mu }V=TV$, i.e. $\mu (s)$ attains the supremum defining $(TV)(s)$ for every $s$. The symbols $T$ (optimality operator), $T_{\mu }$ (policy operator), $V^{\ast }$ (optimal value), $V^{\pi }$ (policy value), $Q^{\mu }$ (action-value), $A(s)$ (admissible actions), $P(\cdot \mid s,a)$ (transition kernel), and $\alpha$ (discount factor) are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "An optimal policy might need to randomize or remember history." For the discounted criterion with $V^{\ast }=T{V}^{\ast }$ and an attained supremum, a stationary deterministic policy greedy for $V^{\ast }$ is optimal over the whole history-dependent randomized class. Randomization and memory buy nothing here; they matter for constrained MDPs, partial observability, or the average-cost multichain case, none of which is the present setting.

• "The action-value $Q$ and the state-value $V$ are independent objects to be solved separately." They are tied by $V^{\mu }(s)=Q^{\mu }(s,\mu (s))$ and $Q^{\mu }(s,a)=r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\mu }(s^{\prime })$; the optimal pair satisfies $V^{\ast }(s)={\max }_{a\in A(s)}{Q}^{\ast }(s,a)$. Solving one yields the other by a single Bellman backup.

• "The optimality operator is not a contraction because of the supremum over actions." The supremum is taken after the $\alpha$-discounted future-value term, and $|{\sup }_{a}f(a)-{\sup }_{a}g(a)|\le {\sup }_a|f(a)-g(a)|$; the $\alpha$ factor passes through, so $T$ is an $\alpha$-contraction exactly as the policy operators are. The supremum cannot inflate the modulus.

• "With an infinite or continuous action set the optimal action always exists." Existence of an optimal stationary deterministic policy needs the supremum in $T{V}^{\ast }$ to be attained. Compactness of $A(s)$ plus upper-semicontinuity of $a\mapsto r(s,a)+\alpha \int P(d{s}^{\prime }\mid s,a)V^{\ast }(s^{\prime })$ delivers attainment by a measurable selection; without such a hypothesis only $\epsilon$-optimal stationary policies are guaranteed.

Key theorem with proof Intermediate+

The signature result specializes the abstract Bellman contraction of 44.08.02 to the MDP optimality operator and adds what is new to the stochastic-control setting: that the optimum is achieved by a single stationary deterministic policy. The contraction itself is inherited; the new content is attainment of the supremum and the resulting greedy-optimality dictionary between $V^{\ast }$ and the optimal decision rule.

Theorem (MDP optimality equation and optimal stationary deterministic policy). Let $(S,A,\{A(s)\},P,r,\alpha )$ be an MDP with $|r|\le M$, $\alpha \in [0,1)$, and either finite $A(s)$ or compact $A(s)$ with $a\mapsto r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })$ upper-semicontinuous for every $V\in B(S)$. Then $T$ is a sup-norm contraction of modulus $\alpha$ on $B(S)$; its unique fixed point is the optimal value $V^{\ast }$, which therefore satisfies the Bellman optimality equation $V^{\ast }=T{V}^{\ast }$; value iteration $V_{n+1}=T{V}_n$ converges geometrically, $\Vert V_n-V^{\ast }{\Vert }_{\infty }\le {\alpha }^n\Vert V_0-V^{\ast }{\Vert }_{\infty }$; the supremum in $T{V}^{\ast }$ is attained, and any stationary deterministic ${\mu }^{\ast }$ greedy for $V^{\ast }$ ($T_{{\mu }^{\ast }}{V}^{\ast }=T{V}^{\ast }$) is optimal over all history-dependent randomized policies, with $V^{{\mu }^{\ast }}=V^{\ast }$.

Proof. Fix $V,V^{\prime }\in B(S)$ and $s\in S$. For each admissible $a\in A(s)$,

$$|\alpha \sum _{s^{\prime }}P(s^{\prime }\mid s,a)(V(s^{\prime })-V^{\prime }(s^{\prime })\left)\right|\le \alpha \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\Vert V-V^{\prime }{\Vert }_{\infty }=\alpha \Vert V-V^{\prime }{\Vert }_{\infty },$$

since $P(\cdot \mid s,a)$ is a probability distribution. Hence the bracketed action score for $V$ exceeds that for $V^{\prime }$ by at most $\alpha \Vert V-V^{\prime }{\Vert }_{\infty }$, uniformly in $a$; taking suprema and using $|{\sup }_{a}f(a)-{\sup }_{a}g(a)|\le {\sup }_a|f(a)-g(a)|$ gives $|(TV)(s)-(T{V}^{\prime })(s)|\le \alpha \Vert V-V^{\prime }{\Vert }_{\infty }$ for every $s$, the contraction bound. The same estimate with the single action $\mu (s)$ in place of the supremum gives it for each $T_{\mu }$.

Because $B(S)$ is complete and $\alpha <1$, the Banach fixed-point theorem 02.01.05 supplies a unique fixed point $V_T=T{V}_T$ together with the geometric estimate $\Vert T^n{V}_0-V_T{\Vert }_{\infty }\le {\alpha }^n\Vert V_0-V_T{\Vert }_{\infty }$; each $T_{\mu }$ likewise has a unique fixed point, which is $V^{\mu }$ (the discounted policy value solves $V^{\mu }=T_{\mu }{V}^{\mu }$, the matrix form $V^{\mu }=r_{\mu }+\alpha P_{\mu }{V}^{\mu }$ for finite models). The abstract contraction-and-monotonicity machinery is taken from 44.08.02; what remains is to identify $V_T$ with $V^{\ast }$ and to produce the optimal policy.

Attainment: under either hypothesis the function $a\mapsto r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V_T(s^{\prime })$ attains its supremum on $A(s)$ — immediately for finite $A(s)$, and by upper-semicontinuity on the compact $A(s)$ otherwise — and a measurable maximizing selection ${\mu }^{\ast }(s)$ exists (Kuratowski–Ryll-Nardzewski in the Polish case). Thus $T_{{\mu }^{\ast }}{V}_T=T{V}_T=V_T$, so $V_T$ is the fixed point of $T_{{\mu }^{\ast }}$, whence $V_T=V^{{\mu }^{\ast }}$ by uniqueness.

Optimality and identification: monotonicity of $T$ (inherited from the increasing, $\alpha$-weighted integrand of 44.08.02) gives, for any history-dependent randomized $\pi$ with one-step decision rule $d_0$, the bound $V^{\pi }\le T{V}^{\pi }$ is not needed; instead use that for every policy the value satisfies $V^{\pi }\le T{V}^{\pi }$ pointwise via the dynamic-programming inequality, so iterating the monotone $T$ yields $V^{\pi }\le T^n{V}^{\pi }\to V_T$, giving $V^{\pi }\le V_T$ and hence $V^{\ast }={\sup }_{\pi }{V}^{\pi }\le V_T$. Conversely $V_T=V^{{\mu }^{\ast }}\le {\sup }_{\pi }{V}^{\pi }=V^{\ast }$. The two inequalities force $V_T=V^{\ast }$, attained by the stationary deterministic ${\mu }^{\ast }$. Finally a stationary deterministic $\mu$ is optimal iff $V^{\mu }=V^{\ast }$ iff (applying $T_{\mu }$ to its own fixed point) $T_{\mu }{V}^{\ast }=T_{\mu }{V}^{\mu }=V^{\mu }=V^{\ast }=T{V}^{\ast }$, i.e. iff $\mu$ is greedy for $V^{\ast }$. $\square$

Bridge. This theorem is the foundational reason stochastic sequential decision-making reduces to one equation: the $\alpha$-contraction collapses the supremum over all history-dependent randomized policies into the unique fixed point $V^{\ast }=T{V}^{\ast }$, and the greedy selection $T_{{\mu }^{\ast }}{V}^{\ast }=V^{\ast }$ both certifies optimality and reads off the optimal stationary deterministic rule. This is exactly the abstract Bellman contraction of 44.08.02 with the transition law replaced by the action-indexed kernel $P(s^{\prime }\mid s,a)$ of 37.05.01; the only genuinely new ingredient is the measurable selection that attains the supremum, the central insight being that discounting alone fixes well-posedness while compactness fixes existence of the maximizer. The framework generalises the deterministic infinite-horizon problem and builds toward the reinforcement-learning algorithms that estimate $T$ from samples, where the same operator reappears as the target of a stochastic approximation. Putting these together, value iteration, policy iteration, and the linear-programming formulation are three routes to the one fixed point, and the bridge is that $Q^{\ast }(s,a)=r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })$ packages the optimality equation in the action-value form that model-free learning later samples; this appears again in temporal-difference and Q-learning as the operator whose expectation the updates track.

Exercises Intermediate+

Advanced results Master

The discounted MDP theory extends in four directions: policy iteration as a Newton-type method with finite termination for finite models, the action-value (Q) formulation that the model-free algorithms target, the primal-dual linear-programming formulation with its occupation-measure dual, and the bridge to reinforcement learning where the Bellman operators become the means of stochastic-approximation iterations.

Theorem 1 (policy iteration: monotone improvement and finite termination). Policy iteration over stationary deterministic policies alternates exact evaluation — solve $V^{{\mu }_k}=T_{{\mu }_k}{V}^{{\mu }_k}$, equivalently the linear system $V^{{\mu }_k}=(I-\alpha P_{{\mu }_k}{)}^{-1}{r}_{{\mu }_k}$ for finite models, where $I-\alpha P_{{\mu }_k}$ is invertible because $\alpha \rho (P_{{\mu }_k})\le \alpha <1$ — with improvement — set ${\mu }_{k+1}(s)\in \arg {\max }_{a\in A(s)}{Q}^{{\mu }_k}(s,a)$. Then $V^{{\mu }_{k+1}}\ge V^{{\mu }_k}$ pointwise with strict increase at some state unless ${\mu }_k$ is optimal. For finite $S$ and $A$ there are finitely many stationary deterministic policies and the value strictly increases until optimality, so the algorithm terminates at an optimal policy in finitely many iterations; it is the Newton step for the equation $V-TV=0$ and converges at least as fast as value iteration, typically far faster ^{[Puterman Ch. 6]}.

Theorem 2 (the action-value optimality equation and Q-iteration). The optimal action-value $Q^{\ast }(s,a)=r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })$ satisfies $V^{\ast }(s)={\max }_{a\in A(s)}{Q}^{\ast }(s,a)$ and the self-referential Bellman optimality equation in $Q$-form,

$$Q^{\ast }(s,a)=r(s,a)+\alpha \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\underset{a^{\prime }\in A(s^{\prime })}{\max }{Q}^{\ast }(s^{\prime },a^{\prime }).$$

The operator $(\mathcal{H}Q)(s,a)=r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a){\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ is an $\alpha$-contraction on $B(S\times A)$, so $Q^{\ast }$ is its unique fixed point and $Q$-value iteration $Q_{n+1}=\mathcal{H}{Q}_n$ converges geometrically; the greedy policy ${\mu }^{\ast }(s)\in \arg {\max }_a{Q}^{\ast }(s,a)$ is optimal. The advantage of the $Q$-form is that the greedy policy is read off without the model, since $\arg {\max }_a{Q}^{\ast }(s,a)$ needs no transition kernel — the structural reason model-free control is possible ^{[Sutton Barto Ch. 4-6]}.

Theorem 3 (linear-programming formulation and the occupation-measure dual). For a finite discounted MDP, $V^{\ast }$ is the unique optimal solution of the primal LP ${\min }_V{\sum }_s\beta (s)V(s)$ subject to $V(s)\ge r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })$ for all $(s,a)$, for any $\beta >0$. Its dual is ${\max }_x{\sum }_{s,a}r(s,a)x(s,a)$ subject to ${\sum }_{a}x(s^{\prime },a)=\beta (s^{\prime })+\alpha {\sum }_{s,a}P(s^{\prime }\mid s,a)x(s,a)$ and $x\ge 0$, where the variable $x(s,a)$ is the discounted state-action occupation measure induced by a policy. Complementary slackness ties the dual support to the greedy actions, so an optimal stationary deterministic policy is recovered as ${\mu }^{\ast }(s)=\{a:x^{\ast }(s,a)>0\}$; this exhibits the MDP as a polyhedral optimization problem and connects it to the theorems-of-alternative / duality theory of 44.04.01 ^{[Puterman Ch. 6]}.

Theorem 4 (reinforcement learning as stochastic approximation to the Bellman operators). When the kernel $P$ and reward $r$ are unknown but samples $(s_t,a_t,r_t,s_{t+1})$ are available, the exact backups of value and Q-iteration are replaced by sampled updates. Temporal-difference learning updates $V(s_t)\leftarrow V(s_t)+{\eta }_t[r_t+\alpha V(s_{t+1})-V(s_t)]$, a stochastic approximation whose mean field is $T_{\mu }V-V$; Q-learning updates $Q(s_t,a_t)\leftarrow Q(s_t,a_t)+{\eta }_t[r_t+\alpha {\max }_{a^{\prime }}Q(s_{t+1},a^{\prime })-Q(s_t,a_t)]$, whose mean field is $\mathcal{H}Q-Q$. Under the Robbins–Monro step-size conditions ${\sum }_t{\eta }_t=\infty$, ${\sum }_t{\eta }_t^2<\infty$ and sufficient exploration, these iterates converge to $V^{\mu }$ and $Q^{\ast }$ respectively, the contraction modulus $\alpha$ and the effective horizon $1/(1-\alpha )$ governing the convergence rate and the sample complexity ^{[Bertsekas Vol. 2 Ch. 2]}.

Synthesis. The foundational reason a Markov decision process is solvable is the same fact that powered the deterministic case: the discount factor $\alpha$ is at once what renders the infinite reward sum finite and the contraction modulus that makes the optimality operator $T$ have a unique fixed point — these are one fact, not two. The central insight is the interchange this licenses, that a supremum over all history-dependent randomized policies becomes the search for $V^{\ast }=T{V}^{\ast }$, and the optimal stationary deterministic policy is the greedy selection $T_{{\mu }^{\ast }}{V}^{\ast }=V^{\ast }$; the only ingredient genuinely new to the stochastic setting is the measurable selection that attains that supremum. This is exactly the abstract Bellman contraction of 44.08.02 specialized to the action-indexed transition kernel of 37.05.01, so the present unit is what infinite-horizon discounted control becomes when the disturbance law is promoted to a controlled-Markov kernel. Value iteration (geometric rate ${\alpha }^n$), policy iteration (the Newton step, finitely terminating for finite models), and the linear program ($V\ge TV\Rightarrow V\ge V^{\ast }$ with its occupation-measure dual) are three algorithms for the one fixed point, and the action-value reformulation $Q^{\ast }$ is dual to $V^{\ast }$ in the sense that the greedy policy reads off from $Q^{\ast }$ without the model.

Putting these together, the same algebraic move — collapsing a sum over all futures into a one-step optimization against a stored value summary — generalises from exact dynamic programming to sampled, model-free learning, where temporal-difference and Q-learning are stochastic approximations whose mean dynamics are precisely the Bellman operators developed here; the bridge from planning to learning is that one operator, estimated rather than computed.

Full proof set Master

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

Proof. For fixed $s,a$ with $a\in A(s)$, $|\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)(V(s^{\prime })-V^{\prime }(s^{\prime }))|\le \alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)|V(s^{\prime })-V^{\prime }(s^{\prime })|\le \alpha \Vert V-V^{\prime }{\Vert }_{\infty }$, the last step because $|V(s^{\prime })-V^{\prime }(s^{\prime })|\le \Vert V-V^{\prime }{\Vert }_{\infty }$ pointwise and ${\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)=1$. So the action score for $V$ differs from that for $V^{\prime }$ by at most $\alpha \Vert V-V^{\prime }{\Vert }_{\infty }$, uniformly in $a$. For $T_{\mu }$ the single action $\mu (s)$ gives the bound directly. For $T$, the supremum is $1$-Lipschitz: from $f(a)\le g(a)+c$ for all $a$ (with $c=\alpha \Vert V-V^{\prime }{\Vert }_{\infty }$) one gets ${\sup }_{a}f(a)\le {\sup }_{a}g(a)+c$, and swapping $V,V^{\prime }$ gives $|(TV)(s)-(T{V}^{\prime })(s)|\le c$ for all $s$. The supremum over $s$ is the claim. $\square$

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

Proof. $B(S)$ with the sup-norm is a complete metric space under $d(V,V^{\prime })=\Vert V-V^{\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 $V^{\ast }=T{V}^{\ast }$ and the geometric estimate $d(T^n{V}_0,V^{\ast })\le {\alpha }^{n}d(V_0,V^{\ast })$; ${\alpha }^n\to 0$ forces convergence. The same theorem applied to $T_{\mu }$ gives a unique $V^{\mu }=T_{\mu }{V}^{\mu }$. $\square$

Proposition 3 (monotonicity and $V^{\ast }$ dominates every policy value). $T$ and each $T_{\mu }$ are monotone: $V\le V^{\prime }\Rightarrow TV\le T{V}^{\prime }$ and $T_{\mu }V\le T_{\mu }{V}^{\prime }$. For every history-dependent randomized policy $\pi$, $V^{\pi }\le V^{\ast }$.

Proof. Monotonicity: if $V\le V^{\prime }$ then ${\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })\le {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\prime }(s^{\prime })$ for each $(s,a)$ since $P(\cdot \mid s,a)\ge 0$ and $\alpha >0$; adding $r(s,a)$ and taking the supremum over $a$ (or the single action $\mu (s)$) preserves the order, giving $TV\le T{V}^{\prime }$ and $T_{\mu }V\le T_{\mu }{V}^{\prime }$. For the domination, fix $\pi$ with first decision rule $d_0$. The dynamic-programming inequality for the discounted value gives $V^{\pi }(s)\le {\sup }_a\{r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })\}=(T{V}^{\pi })(s)$, because the time-shifted continuation value of $\pi$ from any next state is at most $V^{{\pi }^{\prime }}\le {\sup }_{{\pi }^{\prime }}{V}^{{\pi }^{\prime }}$ and the one-step reward-plus-discounted-continuation is bounded above by the supremum over actions. Iterating the monotone $T$, $V^{\pi }\le T{V}^{\pi }\le T^2{V}^{\pi }\le \cdots \le T^n{V}^{\pi }\to V^{\ast }$, so $V^{\pi }\le V^{\ast }$. $\square$

Proposition 4 (existence of an optimal stationary deterministic policy; identification $V^{\ast }={\sup }_{\pi }{V}^{\pi }$). Under finite $A(s)$, or compact $A(s)$ with $a\mapsto r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })$ upper-semicontinuous, the supremum in $T{V}^{\ast }$ is attained by a measurable selection ${\mu }^{\ast }$, and $V^{{\mu }^{\ast }}=V^{\ast }={\sup }_{\pi }{V}^{\pi }$.

Proof. The map $a\mapsto r(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })$ attains its supremum on $A(s)$: immediately when $A(s)$ is finite, and by upper-semicontinuity on compact $A(s)$ otherwise. A measurable maximizing selection ${\mu }^{\ast }(s)$ exists by the Kuratowski–Ryll-Nardzewski selection theorem (immediate in the finite case). Then $T_{{\mu }^{\ast }}{V}^{\ast }=T{V}^{\ast }=V^{\ast }$, so $V^{\ast }$ is the fixed point of $T_{{\mu }^{\ast }}$, whence $V^{\ast }=V^{{\mu }^{\ast }}$ by uniqueness (Proposition 2). Proposition 3 gives ${\sup }_{\pi }{V}^{\pi }\le V^{\ast }$, and $V^{{\mu }^{\ast }}\le {\sup }_{\pi }{V}^{\pi }$ holds because ${\mu }^{\ast }$ is itself a policy; combining, $V^{\ast }=V^{{\mu }^{\ast }}\le {\sup }_{\pi }{V}^{\pi }\le V^{\ast }$, so all are equal and the optimum is attained by the stationary deterministic ${\mu }^{\ast }$. $\square$

Proposition 5 (greedy-optimality criterion). A stationary deterministic policy $\mu$ is optimal ($V^{\mu }=V^{\ast }$) if and only if $T_{\mu }{V}^{\ast }=T{V}^{\ast }$, i.e. $\mu$ is greedy for $V^{\ast }$.

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

Proposition 6 (policy improvement and finite termination of policy iteration for finite MDPs). If $\bar{\mu }$ is greedy for $V^{\mu }$ then $V^{\bar{\mu }}\ge V^{\mu }$, with strict inequality somewhere unless $\mu$ is optimal; for finite $S,A$ policy iteration terminates at an optimal policy in finitely many iterations.

Proof. $T_{\bar{\mu }}{V}^{\mu }=T{V}^{\mu }\ge T_{\mu }{V}^{\mu }=V^{\mu }$ (supremum $\ge$ the particular action $\mu$, and $V^{\mu }=T_{\mu }{V}^{\mu }$ is policy evaluation). Applying the monotone $T_{\bar{\mu }}$ repeatedly, $T_{\bar{\mu }}^{n+1}{V}^{\mu }\ge T_{\bar{\mu }}^n{V}^{\mu }\ge \cdots \ge V^{\mu }$, a nondecreasing sequence; by Proposition 2 for $T_{\bar{\mu }}$ it converges to $V^{\bar{\mu }}$, so $V^{\bar{\mu }}\ge V^{\mu }$. If $V^{\bar{\mu }}=V^{\mu }$ everywhere then $V^{\mu }=T_{\bar{\mu }}{V}^{\mu }=T{V}^{\mu }$, so $V^{\mu }=V^{\ast }$ by uniqueness; hence strict improvement holds somewhere unless $\mu$ is optimal. For finite $S,A$ the values $V^{{\mu }_k}$ strictly increase (in the componentwise order) until optimality, so no policy repeats; there are at most ${\prod }_s|A(s)|<\infty$ stationary deterministic policies, so after finitely many steps a ${\mu }_k$ with $T_{{\mu }_k}{V}^{{\mu }_k}=T{V}^{{\mu }_k}$ is reached, optimal by Proposition 5. $\square$

Connections Master

• The infinite-horizon discounted dynamic programming of 44.08.02 is the abstract parent of this unit: its Bellman operator $T$ on the sup-norm space $B(S)$, the $\alpha$-contraction estimate, value iteration, policy iteration, and the linear-programming route are reused verbatim, with the disturbance-driven system $x_{k+1}=f(x_k,u_k,w_k)$ replaced by the action-indexed transition kernel $P(s^{\prime }\mid s,a)$. The genuinely new theorem here is the attainment-and-selection result that produces an optimal stationary deterministic policy from the fixed point; the contraction machinery is inherited, so this unit specializes rather than re-proves the abstract theory.

• The Markov chain and transition-matrix theory of 37.05.01 supplies the stochastic substrate: fixing a stationary deterministic policy $\mu$ collapses the MDP to an ordinary time-homogeneous Markov chain with transition matrix $P_{\mu }(s^{\prime }\mid s)=P(s^{\prime }\mid s,\mu (s))$, so policy evaluation $V^{\mu }=(I-\alpha P_{\mu }{)}^{-1}{r}_{\mu }$ is a discounted potential of that chain and the recurrence/communication structure of $P_{\mu }$ governs which states the policy actually visits. The Chapman–Kolmogorov semigroup law for $P_{\mu }$ underlies the convergence of the evaluation step.

• The Banach fixed-point theorem 02.01.05 is the existence-uniqueness-and-rate engine for both the optimality operator $T$ and every policy operator $T_{\mu }$, with the discount factor furnishing the contraction modulus on $B(S)$. The same fixed-point principle that solves the MDP also drives Picard–Lindelöf existence for ODEs and the fixed-point iterations of numerical analysis 43.02.02, so stochastic dynamic programming is the decision-theoretic reading of one of analysis's most reused theorems.

• The linear-programming duality and theorems-of-alternative of 44.04.01 underwrite the LP formulation of the MDP: the primal $\min {\sum }_s\beta (s)V(s)$ over $V\ge TV$ has a dual over discounted state-action occupation measures, and complementary slackness recovers the optimal greedy policy from the dual support. The MDP is thereby a polyhedral optimization problem, and the simplex or interior-point machinery of linear programming becomes a third exact solver alongside value and policy iteration.

Historical & philosophical context Master

The Markov decision process emerged from the confluence of Richard Bellman's dynamic-programming program of the 1950s with the theory of controlled Markov chains. Bellman's principle of optimality and the functional equation that bears his name provided the recursive backbone, while the explicit formulation of the sequential decision model with transition probabilities and the policy-iteration algorithm is due to Ronald Howard, whose 1960 monograph Dynamic Programming and Markov Processes ^{[Howard 1960]} introduced policy iteration as a method distinct from successive approximation and named the objects that became the standard MDP vocabulary. David Blackwell's 1965 analysis ^{[Blackwell 1965]} placed discounted dynamic programming on rigorous measure-theoretic footing and proved the optimality of stationary policies, the existence result that this unit's central theorem specializes.

The systematic operator treatment — the optimality operator and policy operators as sup-norm contractions, value-iteration error bounds, modified policy iteration, and approximate dynamic programming — is developed by Dimitri Bertsekas in Dynamic Programming and Optimal Control Volume 2 ^{[Bertsekas Vol. 2 Ch. 1]}, while the comprehensive reference on the discrete stochastic theory, including the policy-class hierarchy, the linear-programming formulation, and the average-reward extension, is Martin Puterman's 1994 monograph ^{[Puterman Ch. 6]}. The same contraction framework became the theoretical foundation of reinforcement learning: temporal-difference learning, introduced by Richard Sutton, and Q-learning, introduced by Christopher Watkins in 1989 with its convergence established by Watkins and Peter Dayan in 1992 ^{[Sutton Barto Ch. 6]}, are stochastic approximations to the value and action-value Bellman operators, learning $V^{\mu }$ and $Q^{\ast }$ from sampled transitions when the model is unknown.

Bibliography Master

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

@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{suttonbarto2018,
  author    = {Sutton, Richard S. and Barto, Andrew G.},
  title     = {Reinforcement Learning: An Introduction},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@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}
}

@article{watkinsdayan1992,
  author  = {Watkins, Christopher J. C. H. and Dayan, Peter},
  title   = {Q-learning},
  journal = {Machine Learning},
  volume  = {8},
  number  = {3--4},
  year    = {1992},
  pages   = {279--292}
}