Can Noisy Action Values Make a Policy Worse? A Policy-Improvement Counterexample

The policy-improvement theorem says a greedy step never hurts. Every real agent takes that step on estimates. This exercise finds the gap.

The policy-improvement theorem is one of the cleanest guarantees in reinforcement learning: if you evaluate a policy exactly, then act greedily with respect to its action values, the new policy is at least as good as the old one. No exceptions, no fine print about step sizes, no luck.

So why do policy updates in practice sometimes make an agent worse?

Because the theorem compares exact action values. Your agent compares estimates. That difference sounds like a footnote until you watch a modest perturbation flip a greedy choice and drag the return below where it started. In this exercise, we build a small tabular MDP, compute exact action values, perturb them by hand, and produce a concrete case where the greedy policy selected from noisy values fails to improve on the reference policy. Then we explain why the theorem is still true.

What the Theorem Actually Promises

You have already seen the derivation, so here is the one-line bridge: policy improvement compares $Q^\pi(s,a)$ against $V^\pi(s)$ and guarantees $V^{\pi'} \ge V^\pi$ when that comparison is exact.

The guarantee is conditional. It assumes you can compare $Q^\pi(s,a)$ for every action at a state and pick the true maximum. It says nothing about values that are learned, sampled, or approximated. The theorem is a statement about a comparison, not about where the numbers came from.

That gives us a precise audit question: what happens when argmax runs over perturbed estimates instead of true action values?

The script below compares three policies:

Success is observable: the program prints the MDP, the perturbations, both greedy choices, and all three returns — with the noisy return no greater than the reference return.

The Test MDP and the Reference Policy

We need an MDP small enough to verify by hand and structured so that the exact-greedy step strictly improves the reference, while a modest perturbation reverses that improvement. A near-tie is the right testbed because it makes a small perturbation decisive. If one action dominates by a wide margin, noise has to be enormous before it changes anything.

Here is the full specification. Two states, two actions, discount $\gamma = 0.9$, start state s0.

Transitions and rewards:

State s1 is absorbing: whatever you do there, you stay and collect nothing. State s0 offers a choice. Action b pays 1 immediately but loops back to s0. Action a pays nothing now but moves you to s1, where the episode effectively ends.

The reference policy $\pi$ is deliberately hesitant: it takes action a at s0 and action a at s1. It is safe, it collects nothing, and it is not greedy — there is clear room for improvement.

Throughout, return means the expected discounted sum of rewards from the start state under a policy.

Milestone 1: Exact Evaluation and the Exact-Greedy Step

The script uses only the standard library. The MDP is a dictionary; policy evaluation is iterative Bellman backup to a tolerance.

import math

GAMMA = 0.9
STATES = ["s0", "s1"]
ACTIONS = ["a", "b"]

# transitions[(s, a)] = list of (probability, next_state, reward)
TRANSITIONS = {
    ("s0", "a"): [(1.0, "s1", 0.0)],
    ("s0", "b"): [(1.0, "s0", 1.0)],
    ("s1", "a"): [(1.0, "s1", 0.0)],
    ("s1", "b"): [(1.0, "s1", 0.0)],
}

REFERENCE = {"s0": "a", "s1": "a"}

def evaluate(policy, tol=1e-12):
    V = {s: 0.0 for s in STATES}
    while True:
        delta = 0.0
        for s in STATES:
            a = policy[s]
            v = sum(p * (r + GAMMA * V[ns]) for p, ns, r in TRANSITIONS[(s, a)])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

def q_values(V):
    Q = {}
    for s in STATES:
        for a in ACTIONS:
            Q[(s, a)] = sum(
                p * (r + GAMMA * V[ns]) for p, ns, r in TRANSITIONS[(s, a)]
            )
    return Q

def greedy(Q):
    return {s: max(ACTIONS, key=lambda a: Q[(s, a)]) for s in STATES}

def print_mdp():
    print("MDP (gamma=%.1f, start=s0):" % GAMMA)
    for (s, a), outcomes in TRANSITIONS.items():
        for p, ns, r in outcomes:
            print("  (%s, %s) -> %s  p=%.2f  r=%.1f" % (s, a, ns, p, r))

Evaluate the reference policy, compute its action values, and take the exact-greedy step:

print_mdp()
V_ref = evaluate(REFERENCE)
Q_ref = q_values(V_ref)
pi_exact = greedy(Q_ref)
V_exact = evaluate(pi_exact)

print("V(pi):", V_ref)
print("Q(pi):", Q_ref)
print("pi_exact:", pi_exact)
print("return(pi):", V_ref["s0"])
print("return(pi_exact):", V_exact["s0"])

Expected output:

MDP (gamma=0.9, start=s0):
  (s0, a) -> s1  p=1.00  r=0.0
  (s0, b) -> s0  p=1.00  r=1.0
  (s1, a) -> s1  p=1.00  r=0.0
  (s1, b) -> s1  p=1.00  r=0.0
V(pi): {'s0': 0.0, 's1': 0.0}
Q(pi): {('s0', 'a'): 0.0, ('s0', 'b'): 1.0, ('s1', 'a'): 0.0, ('s1', 'b'): 0.0}
pi_exact: {'s0': 'b', 's1': 'a'}
return(pi): 0.0
return(pi_exact): 10.0

The theorem holds as advertised: return(pi_exact) > return(pi). The exact-greedy step found the looping action b at s0, which pays 1 every step forever, discounted to $1/(1-0.9) = 10$. The reference policy, which took a and walked into the absorbing state, earned nothing.

Note: The exact-greedy step can only match or beat the reference. If your evaluation has not converged, this comparison is meaningless, which is why the tolerance is tight.

Milestone 2: Perturb the Action Values

Now we introduce controlled estimation error. The perturbations are hand-chosen and printed, so the result is deterministic and auditable — not a random-seed lottery.

The gap at s0 is 1.0: action b is worth 1.0, action a is worth 0.0. A perturbation that pushes b below a needs to overcome that gap. We apply a modest negative shift to ('s0', 'b') and a small positive shift to ('s0', 'a'), leaving s1 untouched:

PERTURBATION = {
    ("s0", "a"): +0.1,
    ("s0", "b"): -1.1,
    ("s1", "a"): 0.0,
    ("s1", "b"): 0.0,
}

print("Perturbations:")
for k, v in PERTURBATION.items():
    print("  %s: %+.2f" % (k, v))

Q_noisy = {k: Q_ref[k] + PERTURBATION[k] for k in Q_ref}
pi_noisy = greedy(Q_noisy)
V_noisy = evaluate(pi_noisy)

print("Q_noisy:", Q_noisy)
print("pi_noisy:", pi_noisy)
print("return(pi_noisy):", V_noisy["s0"])

Expected output:

Perturbations:
  ('s0', 'a'): +0.10
  ('s0', 'b'): -1.10
  ('s1', 'a'): +0.00
  ('s1', 'b'): +0.00
Q_noisy: {('s0', 'a'): 0.1, ('s0', 'b'): -0.1, ('s1', 'a'): 0.0, ('s1', 'b'): 0.0}
pi_noisy: {'s0': 'a', 's1': 'a'}
return(pi_noisy): 0.0

There it is. The perturbed-greedy policy takes a at s0, which moves to the absorbing state and collects nothing. Its true return is 0.0, equal to the reference return of 0.0 and far below the exact-greedy return of 10.0.

The perturbation was small — a tenth of a unit up on one action, just over a unit down on the other — but it crossed the argmax boundary. The greedy step did exactly what it was told. The values it was told were wrong.

Reading the Three Policies Side by Side

The noisy policy is not broken. It is optimal with respect to the values it was given. Given Q_noisy, action a at s0 has value 0.1 and action b has value -0.1. Any rational greedy agent would pick a. The policy is correct; the values are wrong.

Two failure sources are tangled here, and it is worth separating them:

1. The perturbation itself. The estimates drifted from the truth.
2. Greedy selection amplifies any error that crosses an argmax boundary. A perturbation that does not flip the argmax changes nothing. A perturbation that flips it changes everything.

That asymmetry is the practical lesson. Only near-ties are dangerous. If the true gap between two actions is large relative to your estimation error, greedy selection is safe. If the gap is small, your policy is a coin flip dressed as a decision.

Why This Does Not Contradict the Theorem

The theorem's premise is an exact comparison against $V^\pi$. The script violated that premise. No guarantee applies, so there is no contradiction — only a boundary.

Greedy-on-estimates is a heuristic that inherits the theorem's shape but not its proof. The proof works because $V^\pi(s) \le \max_a Q^\pi(s,a)$ holds exactly, and the Bellman backup preserves that inequality. Replace $Q^\pi$ with $\hat{Q}$ and the inequality can point the wrong way.

This is the same pattern that shows up whenever approximate policy evaluation meets greedy improvement: you get bounded improvement, not monotonic improvement. Error in $Q$ propagates into the policy, and the bound depends on how large that error is relative to the action-value gaps. The guarantee is a statement about exact values. The gap between guarantee and practice is exactly the estimation error.

Common mistake: Treating "greedy improvement" as a safety property of the algorithm. It is a safety property of the comparison. The algorithm is only as trustworthy as the numbers it compares.

Failure Modes and Debugging Signals

When you run this audit on your own MDP, these are the symptoms that tell you the conclusion is wrong or overstated:

• Perturbations too small to flip the argmax. The script "proves" nothing. Check that pi_noisy actually differs from pi_exact at some state. If it does not, increase the perturbation until it does.
• Evaluating the noisy policy with the perturbed values. This hides the regression. Always evaluate the chosen policy under the true MDP, never under the estimates that produced it.
• Non-converged policy evaluation. $V^\pi$ error contaminates $Q^\pi$ and makes every comparison meaningless. Tighten the tolerance and re-run.
• Ties in argmax. If two actions have equal value, tie-breaking order silently decides the outcome. Print the tie explicitly so you know the result is arbitrary.

Tip: Print the exact $Q$ gap between the top two actions at every state. That gap is your margin of safety. If your estimation error is larger than the gap, expect flips.

Modify the Experiment

Reproduction is the floor, not the ceiling. One meaningful change turns this into a real investigation:

• Sweep the perturbation magnitude. Start with zero and increase it in small steps. Print the point where the greedy choice flips and the point where the return drops. You will see the flip happen before the return changes — the policy changes first, the consequence follows.
• Try a different reference policy. Make the reference take b at s0 and see how the comparison changes. The structure of the failure is the same; the numbers move.
• Replace hand-chosen perturbations with sampled noise. Draw $\hat{Q} = Q + \epsilon$ with $\epsilon \sim \mathcal{N}(0, \sigma^2)$ and report the fraction of runs where the greedy policy fails to improve. That fraction is your empirical estimate of how often estimation error crosses an argmax boundary.
• Predict the flip point before running. Write down the perturbation magnitude you expect to flip the choice, then compare your prediction to the output. The gap between prediction and result is the gap in your mental model.

The decision rule this exercise earns: greedy improvement is only as trustworthy as the values it compares. Treat any argmax over estimates as a bet on estimation accuracy, and audit near-ties before trusting a policy update. The next practical step is to measure how often your own value estimates flip a greedy choice — that frequency, not the theorem, tells you how much to trust the update.