Markov Decision Processes: The Math of Making Good Choices

The core idea: memoryless state plus the Bellman fixed point

An MDP is a 5-tuple ⟨S, A, P, R, γ⟩: a set of states S, a set of actions A, a transition kernel P(s′ | s, a), a reward function R(s, a), and a discount factor γ ∈ [0, 1). The name comes from the Markov property: the distribution over the next state depends only on the current state and action, not on the entire history. That single assumption — memorylessness — is what makes the whole problem tractable, because it lets the future be summarized by one number per state.

That number is the value function V(s): the expected discounted return if you start in s and act optimally forever. The invariant every solver maintains is the Bellman optimality equation, a self-consistency condition the optimal V* must satisfy:

V*(s) = max over a ∈ A of [ R(s,a) + γ · Σ over s′ of P(s′|s,a) · V*(s′) ]

Read it as: the best you can do from s is the best immediate reward plus the discounted best-you-can-do from wherever you land. Because γ < 1, the operator that maps V to the right-hand side is a γ-contraction in the sup-norm — apply it repeatedly and successive value functions get closer by a factor of γ each time, so a unique fixed point exists (Banach). Solving the MDP means finding that fixed point, then reading off the greedy action per state as the optimal policy π*.

Value iteration, step by step

Value iteration just applies the Bellman operator as an assignment until it stops changing. Start from any V₀ (zeros work), then repeatedly compute a full Bellman backup for every state:

function ValueIteration(S, A, P, R, γ, ε):
    V = array of 0.0, size |S|
    repeat:
        Δ = 0
        for s in S:
            v_old = V[s]
            V[s] = max over a of ( R[s,a] + γ · Σ_s′ P[s′|s,a] · V[s′] )
            Δ = max(Δ, |v_old − V[s]|)
    until Δ < ε·(1−γ)/γ          # stopping rule bounds ‖V − V*‖_∞
    π[s] = argmax over a of ( R[s,a] + γ · Σ_s′ P[s′|s,a] · V[s′] )
    return π, V

• Backup: the inner max/argmax over actions is a one-step lookahead; each action's value is a dot product of the transition row P(·|s,a) with the current V.
• Sweep: one pass over all states is one iteration; you may do it in-place (Gauss–Seidel, often faster) or with a fresh copy (Jacobi).
• Stopping rule: when the max change Δ per sweep is small, the Bellman residual bound guarantees ‖V − V*‖∞ ≤ γΔ/(1−γ). This is the precise handle on "close enough."

The output policy is greedy with respect to the converged value. Crucially, you extract π only once at the end — the algorithm never stores a policy while iterating, which is what distinguishes it from policy iteration.

Policy iteration: evaluate, then improve

Policy iteration (Howard, 1960) alternates two phases and typically converges in far fewer outer iterations than value iteration:

• Policy evaluation: fix the current policy π and solve for its exact value Vπ. Since π picks one action per state, the Bellman equation becomes linear: Vπ = Rπ + γPπVπ, i.e. (I − γPπ)Vπ = Rπ. Solve this |S|×|S| system directly in O(|S|³), or iterate it cheaply.
• Policy improvement: for each state, set π(s) to the greedy action under Vπ. The policy improvement theorem guarantees the new policy is at least as good in every state, and strictly better somewhere unless it's already optimal.

The loop is: evaluate → improve → repeat until the policy stops changing. The key invariant is monotonic improvement — the value never decreases across iterations, and because there are only finitely many deterministic policies (|A|^|S| of them), the process must terminate at π*. The classic bound was exponential in the worst case, but Ye (2011) proved policy iteration (and the simplex method it generalizes) is strongly polynomial for fixed γ, needing O(|S|²·|A|/(1−γ) · log(|S|/(1−γ))) iterations.

Modified policy iteration splits the difference: instead of solving evaluation exactly, run k sweeps of the linear Bellman backup, giving a knob between value iteration (k=1) and full policy iteration (k=∞).

Complexity: why it converges geometrically

Per-sweep time. A single value-iteration sweep evaluates, for every state–action pair, a sum over successor states: |S| states × |A| actions × |S| successors = O(|S|²·|A|) time, O(|S|) space for V (plus the transition table you already hold). If P is sparse with at most b successors per (s,a) — common in gridworlds and games — a sweep drops to O(|S|·|A|·b), a huge constant-factor win.

Iteration count. Because the Bellman operator contracts by γ, the error after n sweeps is ≤ γⁿ·‖V₀ − V*‖∞. To reach accuracy ε you need roughly n = O( log(1/(ε(1−γ))) / (1−γ) ) sweeps. The (1−γ) in the denominator is the villain: as γ → 1 (you care about the far future), the effective horizon 1/(1−γ) blows up and convergence crawls. Total value-iteration cost is therefore about O( |S|²·|A| · log(1/ε) / (1−γ) ).

Policy iteration trades many cheap sweeps for few expensive ones: each outer step pays O(|S|³) for the linear solve (or O(|S|²·|A|) for the improvement), but the outer-iteration count is tiny and, per Ye, polynomial regardless of γ. The curse of dimensionality looms over all of it: |S| is usually the product of state-variable ranges, so a problem with d variables each taking m values has |S| = m^d states — the tables themselves become infeasible long before the per-sweep math does. That's exactly the wall that function approximation (neural nets, tile coding) exists to break.

Where MDPs actually run

The MDP is the substrate under nearly all of modern reinforcement learning, and its exact solvers ship in real systems:

• Reinforcement learning: when P and R are unknown, you can't do Bellman backups directly — so Q-learning and SARSA estimate Q(s,a) from sampled transitions, and Deep Q-Networks replace the table with a CNN. Every one of these is solving an MDP; they just learn the model implicitly. RLHF, which aligns large language models, frames token generation as an MDP and optimizes it with PPO.
• Operations research: inventory control, equipment maintenance/replacement, and queue admission are textbook MDPs solved by policy iteration in tools like Python's pymdptoolbox.
• Robotics and control: motion planning under uncertainty, often as the partially observable extension (POMDP), where the agent maintains a belief distribution over states because it can't see s directly.
• Systems: adaptive bitrate streaming, congestion control, cache admission, and cluster schedulers have all been cast as MDPs; Google's datacenter cooling and several RL-based query optimizers are production examples.

The standard references are Bellman's Dynamic Programming (1957), Puterman's Markov Decision Processes (1994), and Sutton & Barto's Reinforcement Learning: An Introduction — the last being the canonical bridge from MDP theory to learning.

Pitfalls, edge cases, and variants

γ = 1 breaks the contraction. With no discount the Bellman operator is no longer a contraction and value iteration need not converge; returns can be infinite in cyclic MDPs. Undiscounted problems require the average-reward or total-reward (episodic, proper-policy) formulations, or a proof that all policies reach an absorbing terminal state.

• Reward scaling & γ tuning: γ near 1 makes convergence glacial and amplifies estimation error; γ too small makes the agent myopic. The effective horizon is ≈ 1/(1−γ), so γ = 0.99 "looks ahead" about 100 steps.
• Non-Markov state: the entire framework collapses if the true dynamics depend on history. The fix is state augmentation — fold enough history into the state (e.g. frame-stacking in Atari) to restore the Markov property.
• Floating-point & ties: two actions with nearly equal value make argmax flap between sweeps; break ties deterministically to avoid spurious "non-convergence" of the policy while V is already converged.
• Continuous / huge S: exact tables are impossible; you approximate V or Q with a parametric function, giving up the convergence guarantee (approximate value iteration can diverge — the "deadly triad" of bootstrapping + off-policy + approximation).
• Partial observability (POMDP): when you can't observe the true state, solving the belief-state MDP is PSPACE-hard in the finite-horizon case — a categorical jump in difficulty from the polynomial fully-observed MDP.

Value iteration vs. policy iteration vs. linear programming for solving a finite MDP

Method	Cost per iteration	Iterations to ε	Best when
Value iteration	O(|S|²·|A|)	O( log(1/(ε(1−γ))) / (1−γ) )	large |S|, γ not near 1, want simple code
Policy iteration	O(|S|³ + |S|²·|A|)	few (strongly polynomial, Ye 2011)	moderate |S|, γ near 1, few actions
Modified policy iter	O(k·|S|²·|A|)	between the two	balance eval cost vs. improvement
Linear programming	poly(|S|,|A|) (LP solve)	1 solve	need exactness / theoretical guarantees
Q-learning (model-free)	O(1) per sample	no P/R needed; sample-hungry	P and R unknown, learn from experience