Dynamic Programming: Value Iteration and Policy Iteration

A delivery robot that must decide whether its battery can take one more order

Picture a small delivery robot working out of a quick-commerce dark store — the kind of automated fulfilment hub Bengaluru and Gurugram operators have begun trialling for hyperlocal grocery delivery. Every few minutes the robot's controller must choose one of a small set of actions: go out and deliver an order, idle at its current spot, or return to the charging dock. The catch is that battery state is uncertain in its effect — a delivery might leave the battery high or low depending on distance and traffic, and delivering on a low battery sometimes means the robot strands itself mid-route and has to be rescued by a human, an expensive, embarrassing outcome for the platform.

This is not a search problem in the usual graph-traversal sense, because the "next state" after an action is not fixed — it is a probability distribution. It is not a supervised-learning problem either, because there is no labelled dataset of "correct" decisions to imitate. What the controller needs is a way to compute, for every battery state, the long-run expected return of every possible action, accounting for the fact that today's decision reshapes tomorrow's options. This is exactly the problem a Markov Decision Process (MDP) formalizes, and value iteration and policy iteration are the two classical dynamic-programming algorithms that solve it exactly, when the model of the world (transition probabilities and rewards) is fully known.

Formalizing the problem

An MDP is the tuple (S, A, P, R, γ). S is a finite set of states — here S = {H, L} for "battery High" and "battery Low". A(s) is the set of actions available in state s. P(s′|s, a) is the probability of landing in state s′ after taking action a in state s — this is the Markov property: the distribution over s′ depends only on the current (s, a), not on how the robot got there. R(s, a) is the expected immediate reward for taking action a in state s. γ ∈ [0, 1) is the discount factor, which shrinks the value of rewards received further in the future and, as shown later, is also the mathematical reason these algorithms are guaranteed to converge.

A policy π assigns an action to every state; for now we consider deterministic policies, π(s) = a. The state-value function V^π(s) is the expected discounted sum of rewards obtained by starting in state s and following π forever: V^π(s) = E_π[ R_t + γR_t+1 + γ²R_t+2 + … | S_t = s ]. The goal of planning in an MDP is to find an optimal policy π* whose value function V* = V^π* is at least as large as every other policy's value function, in every state simultaneously. This is a stronger claim than "best on average" — a single deterministic optimal policy exists that dominates state-by-state, which is one of the foundational theorems of MDP theory.

The Bellman equations

The recursive structure that makes this tractable is the same recursive structure you already use for DAG shortest paths and tree-DP: the value of a state can be written in terms of the values of its successor states. For any fixed policy π, the Bellman expectation equation holds:

V^π(s) = R(s, π(s)) + γ Σ_s′ P(s′|s, π(s)) V^π(s′)

Swap "follow π" for "take whichever action is best," and you get the Bellman optimality equation, a nonlinear fixed-point equation whose solution is V* itself:

V*(s) = max_{a ∈ A(s)} [ R(s, a) + γ Σ_s′ P(s′|s, a) V*(s′) ]

Both value iteration and policy iteration are ways of solving this system of |S| simultaneous nonlinear equations without inverting anything symbolically. They differ only in how aggressively they exploit the max.

The robot's MDP, made concrete

To make every number checkable, fix the model exactly. In state H, the robot can Deliver or Idle. Delivering succeeds and pays a fixed incentive of 5 units regardless of outcome; with probability α = 0.6 the battery stays High (a short hop), and with probability 0.4 it drops to Low (a longer route). Idling earns a small standby credit of 1 unit (a minimum-guarantee-style payment some gig platforms use to keep partners on-call) and leaves the battery High with certainty.

In state L, three actions exist. Delivering on a low battery succeeds with probability β = 0.7, paying 5 and remaining Low; with probability 0.3 the battery depletes mid-route, triggering a manual rescue that costs the platform the equivalent of 6 units — after the rescue the robot is picked up, recharged, and returned to High. So the expected reward for Delivering in L is a weighted average of these two outcomes, not the reward of either alone: R(L, Deliver) = 0.7(5) + 0.3(−6) = 3.5 − 1.8 = 1.7. Idling in L earns the same 1-unit standby credit and stays Low (no further drain, no gain). Recharge forces an immediate trip to the dock — no delivery income, reward 0, but a guaranteed transition to High.

Take γ = 0.9. This whole model fits in a table:

Value iteration: applying the optimality equation as an update rule

Value iteration starts from an arbitrary V₀ (usually all zeros) and repeatedly applies one synchronous sweep of the Bellman optimality equation as an assignment, using the previous sweep's values throughout:

V_k+1(s) ← max_a [ R(s, a) + γ Σ_s′ P(s′|s, a) V_k(s′) ]

Trace the first three sweeps by hand, starting from V₀(H) = V₀(L) = 0.

Sweep 1. Q(H,Deliver) = 5 + 0.9(0.6·0 + 0.4·0) = 5. Q(H,Idle) = 1 + 0.9(1·0) = 1. So V₁(H) = max(5, 1) = 5. For L: Q(L,Deliver) = 1.7 + 0.9(0) = 1.7, Q(L,Idle) = 1 + 0.9(0) = 1, Q(L,Recharge) = 0 + 0.9(0) = 0. So V₁(L) = max(1.7, 1, 0) = 1.7.

Sweep 2. Using V₁ = (5, 1.7): Q(H,Deliver) = 5 + 0.9(0.6·5 + 0.4·1.7) = 5 + 0.9(3 + 0.68) = 5 + 3.312 = 8.312. Q(H,Idle) = 1 + 0.9·5 = 5.5. V₂(H) = 8.312. For L: Q(L,Deliver) = 1.7 + 0.9(0.7·1.7 + 0.3·5) = 1.7 + 0.9(1.19 + 1.5) = 1.7 + 2.421 = 4.121. Q(L,Idle) = 1 + 0.9·1.7 = 2.53. Q(L,Recharge) = 0 + 0.9·5 = 4.5. V₂(L) = max(4.121, 2.53, 4.5) = 4.5.

Notice something already: at sweep 2, Recharge (4.5) has overtaken Deliver (4.121) as the best action in L — the greedy policy implied by V₂ has already settled on its final answer for state L, even though V₂ itself is nowhere near converged. This is a genuine, well-documented property of value iteration: the induced policy typically stabilizes many sweeps before the values themselves stop moving.

Sweep 3. Using V₂ = (8.312, 4.5): Q(H,Deliver) = 5 + 0.9(0.6·8.312 + 0.4·4.5) = 5 + 0.9(4.9872 + 1.8) = 5 + 6.10848 = 11.10848. Q(H,Idle) = 1 + 0.9·8.312 = 8.4808. V₃(H) = 11.1085. For L: Q(L,Deliver) = 1.7 + 0.9(0.7·4.5 + 0.3·8.312) = 1.7 + 0.9(3.15 + 2.4936) = 1.7 + 5.07924 = 6.77924. Q(L,Idle) = 1 + 0.9·4.5 = 5.05. Q(L,Recharge) = 0 + 0.9·8.312 = 7.4808. V₃(L) = 7.4808.

Continuing this sweep mechanically (verified by direct computation, not by eyeballing) the values keep climbing and the gap between successive sweeps keeps shrinking geometrically:

The sequence converges to V*(H) = 625/17 = 36.764706, V*(L) = 1125/34 = 33.088235 — exact fractions, not rounding artifacts, as the algebra below confirms. Reading off the argmax at convergence: Q(H,Deliver) = V*(H) = 36.7647 beats Q(H,Idle) = 1 + 0.9(36.7647) = 34.0882, and for L, Q(L,Recharge) = 0.9(36.7647) = 33.0882 beats Q(L,Deliver) = 32.4721 and Q(L,Idle) = 30.7794. The optimal policy is: Deliver in H, Recharge in L.

Policy iteration: alternating full evaluation with improvement

Policy iteration takes a different route. Instead of chasing V* directly with one-step lookaheads, it starts with any policy, evaluates that policy's value function exactly, then improves the policy by acting greedily with respect to that exact value function, and repeats until the policy stops changing.

Step 0 — initialize. Start with the deliberately weak policy π₀: Idle in both states.

Step 1 — policy evaluation. Under π₀, both states are self-loops paying 1 forever: V(s) = 1 + 0.9V(s) ⟹ V(s) = 1/(1−0.9) = 10. So V^π0(H) = V^π0(L) = 10.

Step 1 — policy improvement. Q(H,Deliver) = 5 + 0.9(0.6·10 + 0.4·10) = 5 + 9 = 14, beating Q(H,Idle) = 1 + 9 = 10, so π₁(H) = Deliver. Q(L,Deliver) = 1.7 + 0.9(0.7·10 + 0.3·10) = 1.7 + 9 = 10.7, Q(L,Idle) = 10, Q(L,Recharge) = 0.9·10 = 9 — so π₁(L) = Deliver. New policy: Deliver everywhere.

Step 2 — policy evaluation. Solve exactly rather than sweep to convergence. With both actions Deliver: V(H) = 5 + 0.9(0.6V(H) + 0.4V(L)) and V(L) = 1.7 + 0.9(0.7V(L) + 0.3V(H)). Simplifying: 0.46V(H) = 5 + 0.36V(L), and 0.37V(L) = 1.7 + 0.27V(H). Substituting the first into the second: 0.37V(L) = 1.7 + 0.586957(5 + 0.36V(L)) = 4.634783 + 0.211304V(L), giving 0.158696V(L) = 4.634783, so V(L) = 29.2055 and V(H) = (5 + 0.36·29.2055)/0.46 = 33.7260.

Step 2 — policy improvement. Q(H,Deliver) = 5 + 0.9(0.6·33.726 + 0.4·29.2055) = 33.726 (equal to V(H), so H stays Deliver). Q(L,Deliver) = 1.7 + 0.9(0.7·29.2055 + 0.3·33.726) = 29.2055 (equals V(L)). Q(L,Idle) = 1 + 0.9·29.2055 = 27.285. Q(L,Recharge) = 0.9·33.726 = 30.3534 — this is larger than staying with Deliver, so the policy switches: π₂(L) = Recharge, π₂(H) = Deliver.

Step 3 — policy evaluation. Now V(L) = 0.9V(H) exactly (Recharge always moves to H with reward 0), and V(H) = 5 + 0.9(0.6V(H) + 0.4·0.9V(H)) = 5 + 0.864V(H), so 0.136V(H) = 5, V(H) = 5/0.136 = 625/17 = 36.764706, and V(L) = 0.9·625/17 = 1125/34 = 33.088235.

Step 3 — policy improvement. Re-checking both states against this V confirms Deliver still dominates in H and Recharge still dominates in L (the same arithmetic as the value-iteration convergence check above). The policy does not change, so policy iteration halts at π* = {H: Deliver, L: Recharge} — the identical policy and, to the last decimal, the identical value function value iteration produced. This is not a coincidence; a finite MDP with γ < 1 has a unique optimal V*, and any correct DP method must land on it.

Both algorithms, implemented and cross-checked

The following code encodes exactly the table above and runs both algorithms; the printed output matches every hand-derived number in the trace, which is the actual verification, not just an assertion that it "should" work.

mdp = {
    "H": {
        "Deliver": (5.0, {"H": 0.6, "L": 0.4}),
        "Idle":    (1.0, {"H": 1.0}),
    },
    "L": {
        "Deliver":  (1.7, {"L": 0.7, "H": 0.3}),
        "Idle":     (1.0, {"L": 1.0}),
        "Recharge": (0.0, {"H": 1.0}),
    },
}
GAMMA = 0.9

def value_iteration(mdp, gamma=GAMMA, theta=1e-9):
    V = {s: 0.0 for s in mdp}
    while True:
        new_V = {}
        for s in mdp:
            new_V[s] = max(
                r + gamma * sum(p * V[s2] for s2, p in trans.items())
                for r, trans in mdp[s].values()
            )
        delta = max(abs(new_V[s] - V[s]) for s in mdp)
        V = new_V
        if delta < theta:
            break
    policy = {
        s: max(mdp[s], key=lambda a: mdp[s][a][0] + gamma * sum(
            p * V[s2] for s2, p in mdp[s][a][1].items()))
        for s in mdp
    }
    return V, policy

def policy_evaluation(mdp, policy, gamma=GAMMA, theta=1e-9):
    V = {s: 0.0 for s in mdp}
    while True:
        new_V = {}
        for s in mdp:
            r, trans = mdp[s][policy[s]]
            new_V[s] = r + gamma * sum(p * V[s2] for s2, p in trans.items())
        delta = max(abs(new_V[s] - V[s]) for s in mdp)
        V = new_V
        if delta < theta:
            break
    return V

def policy_iteration(mdp, gamma=GAMMA):
    policy = {"H": "Idle", "L": "Idle"}   # deliberately weak start
    while True:
        V = policy_evaluation(mdp, policy, gamma)
        new_policy = {
            s: max(mdp[s], key=lambda a: mdp[s][a][0] + gamma * sum(
                p * V[s2] for s2, p in mdp[s][a][1].items()))
            for s in mdp
        }
        if new_policy == policy:
            return policy, V
        policy = new_policy

V_star, pi_vi = value_iteration(mdp)
pi_pi, V_pi = policy_iteration(mdp)
print(V_star)  # {'H': 36.76470588..., 'L': 33.08823529...}
print(pi_vi)   # {'H': 'Deliver', 'L': 'Recharge'}
print(pi_pi, V_pi)  # identical policy, identical V, reached in 3 improvement rounds

The diagram: two loops, one fixed point

Why both algorithms are guaranteed to land on the same answer

This is not a lucky coincidence of the numbers chosen. Define the Bellman optimality operator T by (TV)(s) = max_a[R(s,a) + γΣ_s′P(s′|s,a)V(s′)]. This operator is a γ-contraction under the sup-norm: for any two value functions V₁, V₂, ‖TV₁ − TV₂‖_∞ ≤ γ‖V₁ − V₂‖_∞. By the Banach fixed-point theorem, a contraction on a complete metric space (here, bounded functions on a finite state space) has exactly one fixed point, and repeated application of T from any starting point converges to it geometrically, at rate γ per application. That is precisely what value iteration does — apply T over and over — which is why the max-change column in the sweep table above shrinks by very close to a factor of 0.9 every sweep: between sweep 100 (Δ = 0.00010381) and sweep 150 (Δ = 0.00000054), the ratio is 0.0052, and 0.9⁵⁰ = 0.00516 — the predicted and observed contraction rates agree to within 1%. Policy iteration converges by a different but related argument: each policy-improvement step is guaranteed to produce a policy whose value function is no worse anywhere (the policy improvement theorem), and since there are only finitely many deterministic policies over a finite state and action space, a strictly-improving-or-equal sequence must terminate, and it can only terminate at a policy that is already greedy with respect to its own value function — which is exactly the Bellman optimality condition. Two different proof techniques, one unique target.

A common misconception

Students who meet these two algorithms side by side often conclude they are structurally unrelated — one "just backs up values," the other "works with actual policies" — and treat picking between them as picking between two different families of technique. That is not accurate. Both algorithms are instances of a single template called generalized policy iteration (GPI): alternate an evaluation step that makes V consistent with some policy, and an improvement step that makes the policy greedy with respect to V. Policy iteration runs evaluation all the way to convergence before each single improvement step. Value iteration is the extreme opposite corner of the same template — it runs evaluation for exactly one sweep (equivalently, it interleaves improvement into every single state backup, since the max over actions in the update rule is the improvement step) before moving on. The diagram above makes this concrete: the "Bellman optimality backup" box in the value-iteration loop already contains a max_a, so every sweep is simultaneously a partial evaluation and a full improvement — there is no separate policy stored between sweeps at all, which is exactly why it looks unrelated to policy iteration on first reading. In between these two extremes lies modified policy iteration, which runs a fixed small number of evaluation sweeps (say, 5) before each improvement — a knob that trades off per-iteration cost against the number of outer iterations needed, with value iteration and policy iteration as its two endpoints.

Complexity, and when to reach for which

Each value-iteration sweep costs O(|S|²|A|) in the worst case for a dense transition model (or O(|S||A|b) for a model where each state-action pair has at most b reachable successors), and the number of sweeps needed to reach a given tolerance scales with 1/(1−γ) — meaning MDPs with γ close to 1 (agents that plan far into the future) converge slowly, as the robot example already showed: 100+ sweeps to settle four significant figures at γ = 0.9. Policy iteration typically needs far fewer outer iterations — three, here — because each improvement step uses the exact value function of the current policy rather than a one-step estimate, so it makes larger, more confident jumps through policy space. The cost is that exact policy evaluation by solving the linear system directly costs O(|S|³) (Gaussian elimination on |S| equations), which becomes prohibitive once |S| reaches even the tens of thousands — a realistic order-and-routing MDP for a large quick-commerce operator, with state defined by (location, remaining battery, pending-order set), can blow past that easily. In practice, neither pure form is used at that scale: production systems run modified policy iteration (a handful of evaluation sweeps, not a full linear solve), or move to asynchronous DP (backing up states in an arbitrary, prioritized order rather than a fixed full sweep, updating states where the Bellman error is largest first), or abandon tabular DP altogether in favour of sampling-based, model-free methods (Q-learning, and their function-approximation descendants) when the transition model P itself is not known exactly. Value and policy iteration remain the right first tool whenever the state space is small enough to enumerate and the model is known — which is precisely the assumption every downstream reinforcement-learning method eventually relaxes one piece at a time.

Active recall

Attempt each question before reading its answer.

1. In one sentence, what is the essential difference between the policy-evaluation step of value iteration and that of policy iteration?

2. Using the converged values V*(H) = 36.7647, V*(L) = 33.0882 for the robot MDP, compute Q(H, Idle) and explain why Idle is never chosen in state H.

3. Why does value iteration's convergence guarantee specifically require γ < 1 (or a task guaranteed to terminate)?

4. Re-derive R(L, Deliver) = 1.7 from β = 0.7 and the two outcome rewards (5 and −6), showing the weighted sum.

5. A logistics MDP has 50,000 states and 20 actions per state. Would you default to exact policy iteration, exact value iteration, or neither — and why?

6. Starting from the always-Deliver policy with V(H) = 33.726, V(L) = 29.2055, compute all three Q-values for state L during the next policy-improvement step, and state whether the policy at L changes.

Answers.

1. Value iteration performs exactly one Bellman backup (one sweep, using the max over actions) before moving on — it never lets V settle to any single policy's true value function along the way. Policy iteration fixes a policy π and runs evaluation to full convergence, computing the exact V^π, before it is allowed to change the policy even once.

2. Q(H, Idle) = 1 + 0.9 × 36.7647 = 1 + 33.0882 = 34.0882. Since Q(H, Deliver) = V*(H) = 36.7647 > 34.0882, Idle is strictly dominated in state H — no matter how the Bellman equation is evaluated, choosing Idle there sacrifices about 2.68 units of expected discounted return.

3. Convergence relies on the Bellman optimality operator T being a γ-contraction: ‖TV₁ − TV₂‖_∞ ≤ γ‖V₁ − V₂‖_∞. This inequality is only strict (γ < 1) if discounting is active; at γ = 1 with a non-terminating task, T need not be a contraction at all, so the Banach fixed-point argument that guarantees a unique fixed point and geometric convergence no longer applies — value iteration can then diverge or oscillate.

4. R(L, Deliver) = β·(5) + (1 − β)·(−6) = 0.7(5) + 0.3(−6) = 3.5 − 1.8 = 1.7, matching the table.

5. Neither, exactly. Exact policy evaluation via linear solve costs O(|S|³) ≈ 1.25×10¹⁴ operations for |S| = 50,000 — infeasible. Pure value iteration avoids the cubic solve but may still need a very large number of sweeps if γ is close to 1, and each sweep still costs O(|S||A|·branching factor). The practical choice is modified policy iteration (a fixed small number of evaluation sweeps per improvement) or asynchronous/prioritized sweeping, and at genuinely large scale, model-free or function-approximation methods that never enumerate all 50,000 states explicitly.

6. Q(L,Deliver) = 1.7 + 0.9(0.7×29.2055 + 0.3×33.726) = 1.7 + 0.9(20.4439 + 10.1178) = 1.7 + 27.5055 = 29.2055. Q(L,Idle) = 1 + 0.9×29.2055 = 27.2850. Q(L,Recharge) = 0 + 0.9×33.726 = 30.3534. Since 30.3534 is the largest of the three, the policy changes: π(L) switches from Deliver to Recharge.

Think About It

Think about this: How would you explain dynamic programming: value iteration and policy iteration to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind dynamic programming: value iteration and policy iteration, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.