Why can acting greedily with respect to a policy's value function never make it worse?

## The statement Let `v_pi(s)` be the expected discounted return from state `s` when following policy `pi` forever, and let `q_pi(s,a)` be the expected return from taking action `a` once in `s` and following `pi` thereafter. Note the definitional link: `v_pi(s) = q_pi(s, pi(s))` for a deterministic policy. **Policy improvement theorem.** If `pi'` is any policy such that ``` q_pi(s, pi'(s)) >= v_pi(s) for every state s ``` then ``` v_pi'(s) >= v_pi(s) for every state s ``` and if the first inequality is strict anywhere, the second is strict in at least one state. ## Why the greedy policy satisfies the premise Define `pi'(s) = argmax_a q_pi(s,a)`. Then ``` q_pi(s, pi'(s)) = max_a q_pi(s,a) >= q_pi(s, pi(s)) = v_pi(s) ``` The maximum over a set is at least any member of the set, and the current policy's action is a member. So the premise holds automatically — no assumption, no condition on the MDP beyond the values being the true values of `pi`. ## The unrolling argument This is the part interviewers want to hear, and it is genuinely simple. Start with `v_pi(s) <= q_pi(s, pi'(s))`. Read the right-hand side in words: *take `pi'`'s action now, then follow `pi` forever*. Expand it one step: ``` v_pi(s) <= E[ r + gamma * v_pi(s') ] with the first action from pi' ``` Now apply the same inequality to `v_pi(s')` inside the expectation, replacing it with *take `pi'`'s action there, then follow `pi`*: ``` v_pi(s) <= E[ r + gamma * ( r' + gamma * v_pi(s'') ) ] first two actions from pi' ``` Each substitution pushes the switch-back point one step further into the future while keeping the inequality pointing the same way. Repeat. Because rewards are bounded and `gamma < 1`, the tail term `gamma^n * v_pi(...)` vanishes, and what remains is the expected discounted return of following `pi'` from the start: ``` v_pi(s) <= v_pi'(s) ``` The intuition to say out loud: a single-step improvement that is available *from every state* is available again at the next step, so you never have to switch back. ## The corollary that terminates policy iteration Suppose greedy improvement returns the same policy: `pi' = pi`. Then for every state ``` v_pi(s) = max_a sum_s' P(s'|s,a) [ r + gamma * v_pi(s') ] ``` That is exactly the condition satisfied by the optimal value function, and it has a unique solution, so `v_pi = v*` and `pi` is optimal. This is why "the improvement pass changed nothing" is a *proof* of optimality and not merely a heuristic stopping rule. ## Practical consequences and caveats **Partial improvement is fine.** The premise is stated per state, so you may change the action in one state and leave the rest alone; the untouched states satisfy the premise with equality. This licenses asynchronous and prioritised improvement, updating whichever states look most promising. **The theorem needs the values to be the values of `pi`.** The whole argument leans on `v_pi(s) = q_pi(s, pi(s))`. If your evaluation was truncated or approximated, that identity holds only approximately, and monotone improvement is no longer guaranteed — with function approximation, policies can oscillate between candidates rather than settle. What survives is a bound, not monotonicity: if your value estimates are within `epsilon` in max-norm of the optimal values, the policy greedy with respect to them loses at most about `2 * gamma * epsilon / (1 - gamma)` relative to optimal. Note how that degrades as the discount factor approaches one. **Ties are harmless.** If several actions tie for the maximum, any tie-breaking rule preserves the theorem; picking a consistent rule just prevents the algorithm cycling between equally good policies and failing to detect its own stopping condition. **Stochastic improvements count too.** Nothing requires `pi'` to be deterministic. Any policy that raises the probability of higher-`q` actions satisfies the premise, which is the doorway to soft, gradual improvement schemes rather than hard greedy switches. ## The common misunderstanding Candidates often assume greedy improvement is a local hill-climb that could get stuck or move backwards, by analogy with greedy search in optimisation. It is not: because the improvement is evaluated against the *long-run* value of the current policy rather than the immediate reward, one greedy step already accounts for the entire discounted future. The greediness is only in the choice of the first action; everything after it is priced in by `v_pi`.