Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

MDPs: Value & Policy Iteration

Bellman equations and why they converge.

Value iteration converges because the Bellman operator shrinks distances by a factor γ\gamma; policy iteration converges because improving a policy can never hurt. Those two facts, a fixed-point theorem and a monotonicity argument, carry the whole theory of planning in Markov decision processes: optimal stationary policies, error bounds you can stop on, a linear program with a meaningful dual, and complexity questions that are still open.

What you’ll learn

  • Define the Bellman operators TπT^\pi and TT, prove that they are monotone γ\gamma-contractions, and deduce that a stationary deterministic policy is optimal among all history-dependent randomized policies.
  • Derive value iteration's a priori and a posteriori error bounds, the ε(1−γ)/2γ\varepsilon(1-\gamma)/2\gamma stopping rule, and the greedy-policy loss bound 2γε/(1−γ)2\gamma\varepsilon/(1-\gamma).
  • Prove the policy improvement theorem, show that policy iteration dominates value iteration, and interpret it as Newton's method.
  • Write an MDP as primal and dual linear programs over values and occupancy measures, and state its complexity: P-completeness, strong polynomiality for fixed γ\gamma, and the error amplification of approximate dynamic programming.

Operators, fixed points and optimal policies

DerivationProof of (v)
  1. Vˉ=TVˉ=lim⁡k→∞TkV0\bar V=T\bar V=\lim_{k\to\infty}T^kV_0

    By (iii) and Banach's fixed-point theorem, TT has a unique fixed point Vˉ\bar V, the limit of TkV0T^kV_0 from any start, with ∥Vˉ∥∞≤Rmax⁡/(1−γ)\norm{\bar V}_\infty\le R_{\max}/(1-\gamma).

  2. Vˉ=Vπ≤V∗\bar V=V^\pi\le V^*

    Attained. Let π\pi be greedy for Vˉ\bar V. Then TπVˉ=TVˉ=VˉT^\pi\bar V=T\bar V=\bar V, so Vˉ\bar V is the fixed point of TπT^\pi, which by (iv) is VπV^\pi:

  3. Esπ′[∑t<nγtr(St,At)+γn Vˉ(Sn)]≤Vˉ(s)\E^{\pi'}_s\Big[\sum_{t<n}\gamma^tr(S_t,A_t)+\gamma^n\,\bar V(S_n)\Big]\le\bar V(s)

    Not beaten. Take any π′∈ΠHR\pi'\in\Pi^{\mathrm{HR}}. Given the history hth_t, its action distribution averages over actions, and an average is at most the maximum, so Eπ′[rt+γVˉ(St+1)∣ht]≤(TVˉ)(St)=Vˉ(St)\E^{\pi'}[r_t+\gamma\bar V(S_{t+1})\mid h_t]\le(T\bar V)(S_t)=\bar V(S_t). Telescoping over nn steps:

  4. V∗=Vˉ=Vπ,π greedy for V∗V^*=\bar V=V^\pi,\qquad\pi\ \text{greedy for }V^*

    Let n→∞n\to\infty: the last term vanishes because Vˉ\bar V is bounded. So Vπ′≤VˉV^{\pi'}\le\bar V for every policy, and history and randomization buy nothing:

The Markov property does the work in the third line: the future after time tt depends on the history only through StS_t, so a single function on states bounds the continuation value of every policy. Other criteria change the picture. Under average reward, finite MDPs still have stationary deterministic optimal policies, but the operators are no longer contractions. With constraints on several reward streams (constrained MDPs), optimal policies may need randomization (Altman, 1999).

Value iteration: how fast, and when to stop

DerivationProofs of 3 and 4
  1. V∗−Vπ=(Tπ∗V∗−Tπ∗V)+(Tπ∗V−TπV)+(TπV−TπV∗)+(TπV∗−TπVπ)V^*-V^\pi=\big(T^{\pi^*}V^*-T^{\pi^*}V\big)+\big(T^{\pi^*}V-T^\pi V\big)+\big(T^\pi V-T^\pi V^*\big)+\big(T^\pi V^*-T^\pi V^\pi\big)

    Greedy loss. Greediness gives TπV=TV≥Tπ∗VT^\pi V=TV\ge T^{\pi^*}V. Add and subtract:

  2. ∥V∗−Vπ∥∞≤2γ∥V−V∗∥∞+γ∥V∗−Vπ∥∞ ⟹ ∥V∗−Vπ∥∞≤2γ1−γ∥V−V∗∥∞\norm{V^*-V^\pi}_\infty\le2\gamma\norm{V-V^*}_\infty+\gamma\norm{V^*-V^\pi}_\infty\ \Longrightarrow\ \norm{V^*-V^\pi}_\infty\le\frac{2\gamma}{1-\gamma}\norm{V-V^*}_\infty

    The second bracket is ≤0\le0; the first and third are at most γ∥V−V∗∥∞\gamma\norm{V-V^*}_\infty in every state, and the last at most γ∥V∗−Vπ∥∞\gamma\norm{V^*-V^\pi}_\infty. Since V∗−Vπ≥0V^*-V^\pi\ge0, take the maximum and rearrange:

  3. ∥Vπ−V∗∥∞≤∥Vπ−Vk+1∥∞+∥Vk+1−V∗∥∞<ε\norm{V^\pi-V^*}_\infty\le\norm{V^\pi-V_{k+1}}_\infty+\norm{V_{k+1}-V^*}_\infty<\varepsilon

    Stopping rule. Let π\pi be greedy for Vk+1V_{k+1}, so TπVk+1=TVk+1T^\pi V_{k+1}=TV_{k+1}, and recall Vk+1=TVkV_{k+1}=TV_k. Then ∥Vπ−Vk+1∥≤∥TπVπ−TπVk+1∥+∥TVk+1−TVk∥≤γ∥Vπ−Vk+1∥+γ∥Vk+1−Vk∥\norm{V^\pi-V_{k+1}}\le\norm{T^\pi V^\pi-T^\pi V_{k+1}}+\norm{TV_{k+1}-TV_k}\le\gamma\norm{V^\pi-V_{k+1}}+\gamma\norm{V_{k+1}-V_k}. So ∥Vπ−Vk+1∥\norm{V^\pi-V_{k+1}}, and by bound 2 also ∥Vk+1−V∗∥\norm{V_{k+1}-V^*}, are at most γ1−γ∥Vk+1−Vk∥<ε2\frac{\gamma}{1-\gamma}\norm{V_{k+1}-V_k}<\frac\varepsilon2:

  4. kε=⌈11−γln⁡Rmax⁡ε (1−γ)⌉k_\varepsilon=\left\lceil\frac{1}{1-\gamma}\ln\frac{R_{\max}}{\varepsilon\,(1-\gamma)}\right\rceil

    Iteration count. From V0=0V_0=0, bound 1 and ln⁡(1/γ)≥1−γ\ln(1/\gamma)\ge1-\gamma give ε\varepsilon-accurate values after this many sweeps, each costing O(∣S∣2∣A∣)\order{|S|^2|A|}. The dependence on the horizon 1/(1−γ)1/(1-\gamma) is genuine, so value iteration is not a strongly polynomial algorithm:

Check your understanding

Value iteration at γ=0.99\gamma=0.99 is stopped with ∥V−V∗∥∞≤0.01\norm{V-V^*}_\infty\le0.01. How much value can the greedy policy lose, in the worst case, according to the greedy-loss bound?

  1. 0.01: the policy is as accurate as the values
  2. 0.02
  3. About 2
  4. About 200
Show the answer

C. About 2

2γ1−γε=1.980.01×0.01=1.98\frac{2\gamma}{1-\gamma}\varepsilon=\frac{1.98}{0.01}\times0.01=1.98. Value errors are amplified by the effective horizon: a small error can tip the argmax in some state, and the cost of that wrong action compounds over roughly 1/(1−γ)=1001/(1-\gamma)=100 steps. The bound is worst-case; greedy policies are often optimal long before the values converge.

Policy iteration: monotone, finite and Newton-fast

DerivationProof
  1. Vπk≤TVπk=Tπk+1Vπk≤(Tπk+1)2Vπk≤⋯→Vπk+1V^{\pi_k}\le TV^{\pi_k}=T^{\pi_{k+1}}V^{\pi_k}\le\big(T^{\pi_{k+1}}\big)^2V^{\pi_k}\le\cdots\to V^{\pi_{k+1}}

    Greediness gives Tπk+1Vπk=TVπk≥TπkVπk=VπkT^{\pi_{k+1}}V^{\pi_k}=TV^{\pi_k}\ge T^{\pi_k}V^{\pi_k}=V^{\pi_k}. Monotonicity of Tπk+1T^{\pi_{k+1}} propagates the inequality along its iterates, which converge to its fixed point Vπk+1V^{\pi_{k+1}}:

  2. Vk+1=TVk≤TVπk≤Vπk+1V_{k+1}=TV_k\le TV^{\pi_k}\le V^{\pi_{k+1}}

    Domination. Induct: if Vk≤VπkV_k\le V^{\pi_k}, then monotonicity of TT and (i) give

  3. Vπ0≤Vπ1≤⋯≤VπK=V∗,K≤∣A∣∣S∣V^{\pi_0}\le V^{\pi_1}\le\cdots\le V^{\pi_K}=V^*,\qquad K\le|A|^{|S|}

    So policy iteration is never behind value iteration started from the same values, round for round. Termination: if no state improves strictly, TVπk=VπkTV^{\pi_k}=V^{\pi_k} and πk\pi_k is optimal by uniqueness of the fixed point; otherwise the values rise strictly somewhere, so no policy repeats.

Newton's method. With π′\pi' greedy for V=VπV=V^\pi, the Bellman residual is TV−V=rπ′−(I−γPπ′)VTV-V=r^{\pi'}-(I-\gamma P^{\pi'})V, and (I−γPπ′)−1rπ′=Vπ′(I-\gamma P^{\pi'})^{-1}r^{\pi'}=V^{\pi'}. Hence Vπ′=V−(γPπ′−I)−1(TV−V)V^{\pi'}=V-(\gamma P^{\pi'}-I)^{-1}(TV-V): a Newton step on the piecewise-linear equation TV−V=0TV-V=0, whose Jacobian on the current linear piece is γPπ′−I\gamma P^{\pi'}-I (Puterman & Brumelle, 1979). Like Newton's method, it typically needs very few steps.

How many iterations? The ∣A∣∣S∣|A|^{|S|} bound is far from the truth. For a fixed discount, Ye (2011) proved that Howard's policy iteration, and the simplex method with Dantzig's rule on the LP below, are strongly polynomial; Hansen, Miltersen and Zwick (2013) sharpened the bound to O(m1−γlog⁡n1−γ)\order{\frac{m}{1-\gamma}\log\frac{n}{1-\gamma}} iterations for nn states and mm state–action pairs. Without discounting (total or average reward), Fearnley (2010) built MDPs on which Howard's algorithm takes exponentially many iterations, and simple policy iteration, which switches one action at a time, is exponential with the smallest-index rule (Melekopoglou & Condon, 1994).

Linear programming, complexity and approximation

Monotonicity gives a third characterization. If V≥TVV\ge TV, then V≥TkV→V∗V\ge T^kV\to V^*, so V∗V^* is the smallest function with V≥TVV\ge TV, and for any weights α(s)>0\alpha(s)>0 it solves a linear program (Manne, 1960; d'Epenoux, 1963). Its dual is a flow problem over state–action pairs:

(P)min⁡V ∑sα(s)V(s)s.t.V(s)≥r(s,a)+γ∑s′P(s′∣s,a)V(s′)∀s,a(D)max⁡μ≥0 ∑s,aμ(s,a) r(s,a)s.t.∑aμ(s′,a)=α(s′)+γ∑s,aP(s′∣s,a) μ(s,a)∀s′\begin{aligned}\text{(P)}\quad&\min_V\ \sum_s\alpha(s)V(s)\quad\text{s.t.}\quad V(s)\ge r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\quad\forall s,a\\ \text{(D)}\quad&\max_{\mu\ge0}\ \sum_{s,a}\mu(s,a)\,r(s,a)\quad\text{s.t.}\quad\sum_a\mu(s',a)=\alpha(s')+\gamma\sum_{s,a}P(s'\mid s,a)\,\mu(s,a)\quad\forall s'\end{aligned}
The feasible dual points are exactly the discounted occupancy measures μπ(s,a)=∑tγtPr⁡π(St=s,At=a)\mu^\pi(s,a)=\sum_t\gamma^t\Pr^\pi(S_t=s,A_t=a) of stationary policies started from α\alpha, and π(a∣s)=μ(s,a)/∑a′μ(s,a′)\pi(a\mid s)=\mu(s,a)/\sum_{a'}\mu(s,a') recovers the policy. Basic feasible solutions are deterministic policies, and a simplex pivot switches the action in one state.

One factor 1/(1−γ)1/(1-\gamma) comes from accumulating backup errors, the other from the greedy step. The sup-norm hypothesis is the weak point: least-squares fits control average errors, not the worst state, and bootstrapped targets with function approximation and off-policy data can diverge outright (the deadly triad; see Convergence of Q-Learning). With a generative model, the statistics are understood precisely: on the order of ∣S∣∣A∣/((1−γ)3ε2)|S||A|/((1-\gamma)^3\varepsilon^2) samples, up to logarithmic factors, are necessary, and for small enough ε\varepsilon sufficient, to estimate Q∗Q^* to accuracy ε\varepsilon (Azar, Munos & Kappen, 2013).

Key takeaways

  • The Bellman operators are monotone γ\gamma-contractions in the sup norm. VπV^\pi and V∗V^* are their unique fixed points, and a greedy policy for V∗V^* is optimal among all history-dependent randomized policies.
  • Value iteration: ∥Vk−V∗∥∞≤γk∥V0−V∗∥∞\norm{V_k-V^*}_\infty\le\gamma^k\norm{V_0-V^*}_\infty. Stopping when ∥Vk+1−Vk∥∞<ε(1−γ)/2γ\norm{V_{k+1}-V_k}_\infty<\varepsilon(1-\gamma)/2\gamma makes the greedy policy ε\varepsilon-optimal, and a value error can cost up to 2γ/(1−γ)2\gamma/(1-\gamma) times as much in policy value.
  • Policy iteration improves monotonically, dominates value iteration round for round, terminates finitely, and is Newton's method on TV−V=0TV-V=0; for fixed γ\gamma it is strongly polynomial.
  • V∗V^* solves a linear program whose dual variables are discounted occupancy measures. MDPs are P-complete; finite-horizon POMDPs are PSPACE-complete.
  • Approximate backups with sup-norm error ε\varepsilon can cost 2γε/(1−γ)22\gamma\varepsilon/(1-\gamma)^2, which is why planning with function approximation needs more than contraction arguments.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In a continuing discounted MDP, adding a constant cc to every reward never changes the optimal policy. In the 4×3 gridworld, changing the living reward does change it. Why?

  1. Because the gridworld uses γ=1\gamma=1
  2. The exits end the reward stream, so the shift adds cc times the discounted time to exit, which differs between policies
  3. Because the gridworld's moves are stochastic
  4. Because the living reward is not added to the exit rewards
Show the answer

B. The exits end the reward stream, so the shift adds cc times the discounted time to exit, which differs between policies

In a continuing MDP every policy collects the shift forever, adding c/(1−γ)c/(1-\gamma) to every value, which preserves the ranking. With absorbing exits a policy collects cc only until it exits, so the shift adds c E[∑t<τγt]c\,\E\big[\sum_{t<\tau}\gamma^t\big], which depends on the policy: a negative living reward favors exiting quickly, a positive one favors never exiting.

Question 2

Policy iteration from π0\pi_0 and value iteration from V0=Vπ0V_0=V^{\pi_0} run side by side. Which statement holds for every kk?

  1. Vk=VπkV_k=V^{\pi_k}
  2. Vk≥VπkV_k\ge V^{\pi_k}
  3. Neither: the two sequences are not comparable
  4. Vπk≥VkV^{\pi_k}\ge V_k, so policy iteration is never behind
Show the answer

D. Vπk≥VkV^{\pi_k}\ge V_k, so policy iteration is never behind

By induction, Vk+1=TVk≤TVπk≤Vπk+1V_{k+1}=TV_k\le TV^{\pi_k}\le V^{\pi_{k+1}}, using the monotonicity of TT and the improvement inequality Vπk+1≥TVπkV^{\pi_{k+1}}\ge TV^{\pi_k}. Both sequences lie below V∗V^*, so policy iteration's error is at most value iteration's, at the price of one linear solve per round.

Question 3

In the dual linear program of a discounted MDP, what do the variables μ(s,a)\mu(s,a) represent at a feasible point?

  1. The optimal action values Q∗(s,a)Q^*(s,a)
  2. The policy's probabilities π(a∣s)\pi(a\mid s)
  3. Discounted occupancies: the discounted expected number of times aa is taken in ss, starting from α\alpha
  4. Lagrange multipliers with no direct meaning
Show the answer

C. Discounted occupancies: the discounted expected number of times aa is taken in ss, starting from α\alpha

The constraint says that the flow out of s′s' equals its initial mass plus the discounted flow in, which characterizes occupancy measures μπ(s,a)=∑tγtPr⁡π(St=s,At=a)\mu^\pi(s,a)=\sum_t\gamma^t\Pr^\pi(S_t=s,A_t=a). The objective ∑μ r\sum\mu\,r is then the expected discounted reward, and normalizing μ(s,⋅)\mu(s,\cdot) gives π(a∣s)\pi(a\mid s). Occupancy measures are the starting point for constrained MDPs and for many offline RL methods.

Question 4

Solving finite MDPs is P-complete. What does that imply?

  1. They can be solved in polynomial time, but probably not by a fast parallel (polylogarithmic-depth) algorithm
  2. No polynomial-time algorithm exists
  3. They are NP-hard
  4. Value iteration runs in polynomial time
Show the answer

A. They can be solved in polynomial time, but probably not by a fast parallel (polylogarithmic-depth) algorithm

P-complete problems are the hardest problems in P under log-space reductions: solvable in polynomial time by linear programming, but an NC algorithm would imply NC = P, which is widely believed false. It says nothing in favor of value iteration, whose number of sweeps grows like 1/(1−γ)1/(1-\gamma).

Further reading

  • R. Bellman, Dynamic Programming (Princeton University Press, 1957).
  • R. A. Howard, Dynamic Programming and Markov Processes (MIT Press, 1960).
  • M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley, 1994), chapter 6.
  • C. H. Papadimitriou & J. N. Tsitsiklis, "The complexity of Markov decision processes," Mathematics of Operations Research 12(3), 441–450 (1987).
  • Y. Ye, "The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate," Mathematics of Operations Research 36(4), 593–603 (2011).