MDPs: Value & Policy Iteration
Bellman equations and why they converge.
Value iteration converges because the Bellman operator shrinks distances by a factor ; 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 and , prove that they are monotone -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 stopping rule, and the greedy-policy loss bound .
- 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 , and the error amplification of approximate dynamic programming.
Operators, fixed points and optimal policies
By (iii) and Banach's fixed-point theorem, has a unique fixed point , the limit of from any start, with .
Attained. Let be greedy for . Then , so is the fixed point of , which by (iv) is :
Not beaten. Take any . Given the history , its action distribution averages over actions, and an average is at most the maximum, so . Telescoping over steps:
Let : the last term vanishes because is bounded. So for every policy, and history and randomization buy nothing:
The Markov property does the work in the third line: the future after time depends on the history only through , 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
Greedy loss. Greediness gives . Add and subtract:
The second bracket is ; the first and third are at most in every state, and the last at most . Since , take the maximum and rearrange:
Stopping rule. Let be greedy for , so , and recall . Then . So , and by bound 2 also , are at most :
Iteration count. From , bound 1 and give -accurate values after this many sweeps, each costing . The dependence on the horizon is genuine, so value iteration is not a strongly polynomial algorithm:
Value iteration at is stopped with . How much value can the greedy policy lose, in the worst case, according to the greedy-loss bound?
- 0.01: the policy is as accurate as the values
- 0.02
- About 2
- About 200
Show the answer
C. About 2
. 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 steps. The bound is worst-case; greedy policies are often optimal long before the values converge.
Policy iteration: monotone, finite and Newton-fast
Greediness gives . Monotonicity of propagates the inequality along its iterates, which converge to its fixed point :
Domination. Induct: if , then monotonicity of and (i) give
So policy iteration is never behind value iteration started from the same values, round for round. Termination: if no state improves strictly, and is optimal by uniqueness of the fixed point; otherwise the values rise strictly somewhere, so no policy repeats.
Newton's method. With greedy for , the Bellman residual is , and . Hence : a Newton step on the piecewise-linear equation , whose Jacobian on the current linear piece is (Puterman & Brumelle, 1979). Like Newton's method, it typically needs very few steps.
How many iterations? The 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 iterations for states and 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 , then , so is the smallest function with , and for any weights it solves a linear program (Manne, 1960; d'Epenoux, 1963). Its dual is a flow problem over state–action pairs:
One factor 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 samples, up to logarithmic factors, are necessary, and for small enough sufficient, to estimate to accuracy (Azar, Munos & Kappen, 2013).
Key takeaways
- The Bellman operators are monotone -contractions in the sup norm. and are their unique fixed points, and a greedy policy for is optimal among all history-dependent randomized policies.
- Value iteration: . Stopping when makes the greedy policy -optimal, and a value error can cost up to times as much in policy value.
- Policy iteration improves monotonically, dominates value iteration round for round, terminates finitely, and is Newton's method on ; for fixed it is strongly polynomial.
- 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 can cost , 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.
In a continuing discounted MDP, adding a constant to every reward never changes the optimal policy. In the 4×3 gridworld, changing the living reward does change it. Why?
- Because the gridworld uses
- The exits end the reward stream, so the shift adds times the discounted time to exit, which differs between policies
- Because the gridworld's moves are stochastic
- 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 times the discounted time to exit, which differs between policies
In a continuing MDP every policy collects the shift forever, adding to every value, which preserves the ranking. With absorbing exits a policy collects only until it exits, so the shift adds , which depends on the policy: a negative living reward favors exiting quickly, a positive one favors never exiting.
Policy iteration from and value iteration from run side by side. Which statement holds for every ?
- Neither: the two sequences are not comparable
- , so policy iteration is never behind
Show the answer
D. , so policy iteration is never behind
By induction, , using the monotonicity of and the improvement inequality . Both sequences lie below , so policy iteration's error is at most value iteration's, at the price of one linear solve per round.
In the dual linear program of a discounted MDP, what do the variables represent at a feasible point?
- The optimal action values
- The policy's probabilities
- Discounted occupancies: the discounted expected number of times is taken in , starting from
- Lagrange multipliers with no direct meaning
Show the answer
C. Discounted occupancies: the discounted expected number of times is taken in , starting from
The constraint says that the flow out of equals its initial mass plus the discounted flow in, which characterizes occupancy measures . The objective is then the expected discounted reward, and normalizing gives . Occupancy measures are the starting point for constrained MDPs and for many offline RL methods.
Solving finite MDPs is P-complete. What does that imply?
- They can be solved in polynomial time, but probably not by a fast parallel (polylogarithmic-depth) algorithm
- No polynomial-time algorithm exists
- They are NP-hard
- 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 .
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).