skip to content

How does policy iteration alternate evaluation and improvement to reach an optimal policy?

level: middleimportance: must knowfreq 65%

answer

  1. two sweeps in a loop
  2. one of them has no maximum
  3. sweep until values stop moving
  4. then act greedily on those values
  5. stop when no action changes

basics

~20 s

Policy iteration repeats two steps. Evaluation sweeps every state, replacing its value with the expected return of the current policy. Improvement then rebuilds the policy greedily from those values; when no action changes, the policy is optimal.

solid answer

~50 s

Policy iteration alternates two distinct sweeps until they agree. **Iterative policy evaluation** starts from arbitrary values and repeatedly applies `v(s) <- sum_s' P(s'|s,pi(s)) * [r + gamma * v(s')]` — note there is no maximum here, the action is whatever the current policy takes — stopping when the largest change in any state during a sweep falls below a small threshold. **Policy improvement** then sets `pi(s)` to the action with the best one-step value using those converged numbers. On a slippery 4x4 gridworld you can watch this: evaluating the uniform-random policy gives values that decay away from the goal, and a single greedy pass turns most tiles to point along the safest route. You then re-evaluate the new policy and repeat. If an improvement pass changes no action anywhere, the policy is greedy with respect to its own value function, which means it is optimal and the loop halts.

code

python · 21 lines
python
# tiny MDP: states 0, 1, 2 (2 is terminal); actions "stay" and "go"
P = {  # (state, action) -> list of (probability, next_state, reward)
    (0, "stay"): [(1.0, 0, -1.0)],
    (0, "go"):   [(0.8, 1, -1.0), (0.2, 0, -1.0)],
    (1, "stay"): [(1.0, 1, -1.0)],
    (1, "go"):   [(0.7, 2, 10.0), (0.3, 0, -1.0)],
}
gamma = 0.9
V = {0: 0.0, 1: 0.0, 2: 0.0}     # value of the terminal state stays 0
policy = {0: "stay", 1: "go"}    # the policy we are evaluating

def backup(s, a):                # one full-width expectation over successors
    return sum(p * (r + gamma * V[s2]) for p, s2, r in P[(s, a)])

for _ in range(300):             # iterative policy evaluation, synchronous sweeps
    V.update({s: backup(s, policy[s]) for s in policy})

# one greedy policy-improvement step using the values just computed
improved = {s: max(("stay", "go"), key=lambda a: backup(s, a)) for s in policy}
print({s: round(v, 2) for s, v in V.items()})   # {0: -10.0, 1: 4.0, 2: 0.0}
print(improved)                                 # {0: 'go', 1: 'go'}

go deeper

for a junior

Recall the two names and their order: evaluate the current policy, then improve it greedily, and repeat. Know that the loop ends when an improvement pass changes nothing.

for a middle

Write both backups on the board and point out that evaluation has no maximum while improvement does. Explain the sweep-until-values-settle stopping rule and why finitely many deterministic policies force termination.

for a senior

Talk about cost: evaluation dominates, so people truncate it, and the number of outer improvements is usually tiny. Be able to say when you would solve evaluation as a linear system instead of sweeping.

for a principal

Frame the choice of granularity as an engineering decision — how much evaluation to buy per improvement, whether sweeps run synchronously or asynchronously, and what accuracy the downstream decision actually needs.

## The loop in one picture ``` pi_0 --eval--> v_pi0 --improve--> pi_1 --eval--> v_pi1 --improve--> ... --> pi* ``` Two different computations, alternating. They are easy to confuse because both sweep over all states, but they answer different questions. ## Step 1: iterative policy evaluation **Question answered:** how good is the policy I currently have? Start with any initial values (zeros are fine). Repeatedly sweep every state and apply ``` v(s) <- sum over s' of P(s'|s, pi(s)) * [ r(s, pi(s), s') + gamma * v(s') ] ``` for a deterministic policy, or the probability-weighted average over `pi(a|s)` for a stochastic one. There is **no maximisation** in this step. You are not asking what the best action is; you are asking what following `pi` forever is worth. This is a contraction with modulus `gamma`, so it converges to the unique `v_pi` from any starting point. In practice you stop when the largest change to any state's value in a full sweep drops below a threshold `theta`; the remaining error is then bounded by roughly `theta * gamma / (1 - gamma)`, which is why the tolerance you accept has to shrink as the discount factor approaches one. For small state spaces there is an alternative: `v_pi` solves a linear system of `|S|` equations in `|S|` unknowns, so you can solve it directly instead of sweeping. ## Step 2: policy improvement **Question answered:** given what following `pi` is worth from every state, can I do better by choosing a different first action? For each state compute the one-step value of every action against the values you just converged, and take the best one: ``` pi_new(s) <- argmax over a of sum over s' of P(s'|s,a) * [ r(s,a,s') + gamma * v_pi(s') ] ``` This single pass over states and actions is cheap compared with evaluation. It cannot make the policy worse — that guarantee is the policy improvement theorem — and it usually makes it strictly better somewhere. ## Step 3: the stopping condition Run improvement. If the resulting policy is identical to the one you evaluated — no state changed its action — stop. That equality says the current policy is greedy with respect to its own value function, which is exactly the optimality condition, so the policy is optimal. **Why it terminates.** In a finite MDP with finitely many actions there are finitely many deterministic policies. Every round produces a policy at least as good as the previous one, and strictly better in at least one state unless it is already greedy with respect to its own values. So no policy can be revisited, and the loop must end after finitely many improvements — typically a surprisingly small number, often single digits even for large state spaces. ## A worked reading of the gridworld On a 4x4 grid where each move slips sideways with some probability and the terminal tile pays out, evaluate the uniform-random policy first. The values form a gradient: tiles near the goal are worth more, tiles near an absorbing hazard are worth much less, and the gradient encodes how likely random wandering is to end well from each tile. Now improve: at each tile, choose the move whose weighted successor value is largest. Tiles next to the hazard start pointing away from it even though the random policy walked into it a third of the time. Re-evaluate that new policy and the gradient sharpens, because the values now reflect deliberate movement rather than wandering. Two or three rounds of this and no action changes any more. ## Variants you should be able to name **Truncated (modified) policy iteration.** Nothing forces evaluation to run to convergence. Run `k` sweeps and improve. With `k = 1` you recover value iteration; with `k` large you recover classic policy iteration. Everything in between works. **Generalized policy iteration.** The umbrella name for the whole family: any interleaving of "make the values consistent with the policy" and "make the policy greedy with respect to the values", at any granularity, in any order. The two processes pull against each other — improvement makes the values stale, evaluation makes the policy stale — and their joint fixed point is the optimal policy and its value function. **Asynchronous versions.** Neither step needs to be a clean full sweep; updating states in place, in a good order, converges as long as no state is starved. ## The mistake to avoid The single most common error is putting a maximum over actions inside the evaluation step. That is not evaluation of your policy — it is a value-iteration backup, and it answers a different question. Evaluation follows the policy you have; improvement is the only place the maximum belongs.

  • What happens if you stop policy evaluation early instead of running it to convergence?
    The loop still converges. This is truncated or modified policy iteration: run `k` evaluation sweeps, then improve. With `k = 1` you have exactly value iteration; with `k` large you have classic policy iteration. The general principle that evaluation and improvement can interleave at any granularity is called generalized policy iteration.
  • How do you know policy iteration terminates?
    A finite MDP has finitely many deterministic policies. Each improvement yields a policy at least as good, and strictly better somewhere unless it is already greedy with respect to its own values — in which case it satisfies the optimality condition and you stop. So no policy repeats and the loop ends in finitely many rounds, usually very few.
  • What stopping rule do you use inside the evaluation sweeps?
    Track the largest absolute change to any state value during a full sweep and stop once it falls below a threshold `theta`. The remaining distance to the true values of the policy is then bounded by about `theta * gamma / (1 - gamma)`, so a discount factor close to one forces a much tighter threshold for the same accuracy.
  • Why must the evaluation step not take a maximum over actions?
    Because evaluation answers "what is this policy worth", and that means following the action the policy actually takes. Inserting a maximum computes something else entirely — the value of always acting greedily — and destroys the guarantee that the subsequent improvement compares against a correctly evaluated baseline.

saying these in an interview costs you the question

  • Puts a maximum over actions inside the evaluation step
  • Cannot state what makes the outer loop stop
  • Thinks evaluation must reach exactly equal values
  • Believes each improvement round can make the policy worse
  • Confuses the evaluation sweep count with the number of policy improvements

context

resolving links…