Generalized Policy Iteration (GPI)

Why Does This Exist?

You need values to improve a policy, and you need a policy to define values. That circle is the whole difficulty. Policy evaluation fixes behavior and measures return. Greedy improvement fixes values and picks better actions. Doing either one perfectly before touching the other wastes work, because each step invalidates the other.

Sutton and Barto named the general pattern GPI. It says the two processes can interleave at any grain, from full sweeps to single samples, and still head to the same optimum. That one idea turns policy iteration, value iteration, SARSA, Q-learning and actor critic into settings on one dial rather than separate tricks.

The one idea you need first

The Bellman expectation for fixed $\pi$ says $v_{\pi}(s)$ equals mean reward plus $\gamma$ times next values. The greedy policy picks the action with the largest one step lookahead under current $V$. GPI is those two updates chasing each other.

Think of It Like This

How It Actually Works

Hold $\pi$, move $V$ toward $v_{\pi}$ with Bellman backups. Hold $V$, move $\pi$ toward greedy $V$ by picking $\arg\max_a$ one step returns. The improvement theorem says a policy that looks better under old values is no worse in truth, so return does not go down.

Picture two lines crossing. One line is $V = v_{\pi}$, where values match the policy. The other is $\pi = \text{greedy}(V)$, where the policy matches values. Each update moves toward one line and off the other, making a zigzag. The only joint rest point satisfies the Bellman optimum, hence $(\pi_*, v_*)$.

Where common methods sit

• Full sweeps to convergence then greedy replacement behaves like policy iteration.
• One sweep then greedy replacement behaves like value iteration.
• One state at a time in any order behaves like asynchronous dynamic programming.
• One sampled transition with epsilon greedy behavior behaves like SARSA or Q-learning.
• Small critic and actor gradient steps together behave like actor critic.

No table needed: smaller evaluation grain means faster policy turns at noisier values.

Worked example

Two states $\{s_1, s_2\}$, actions $\{a_1, a_2\}$, $\gamma = 0.5$. Rewards are fixed: in $s_1$, $a_1$ stays in $s_1$ for $1.0$, $a_2$ goes to $s_2$ for $3.0$; in $s_2$, $a_1$ goes to $s_1$ for $0.0$, $a_2$ stays in $s_2$ for $2.0$. Start $\pi_0 = [a_1, a_1]$, $V_0 = [0.0, 0.0]$.

First evaluation sweep under $\pi_0$: $V_1(s_1) = 1.0 + 0.5 \times 0.0 = 1.0$, $V_1(s_2) = 0.0 + 0.5 \times 0.0 = 0.0$, so $V_1 = [1.0, 0.0]$.

Greedy step on $V_1$: in $s_1$, $Q(a_1) = 1.0 + 0.5 \times 1.0 = 1.5$ and $Q(a_2) = 3.0 + 0.5 \times 0.0 = 3.0$, pick $a_2$; in $s_2$, $Q(a_1) = 0.0 + 0.5 \times 1.0 = 0.5$ and $Q(a_2) = 2.0 + 0.5 \times 0.0 = 2.0$, pick $a_2$. So $\pi_1 = [a_2, a_2]$, already optimal.

Next evaluation under $\pi_1$: $V_2(s_1) = 3.0 + 0.5 \times 0.0 = 3.0$, $V_2(s_2) = 2.0 + 0.5 \times 0.0 = 2.0$. The policy stays put. True fixed point solves $v_*(s_2) = 2.0 + 0.5 v_*(s_2) = 4.0$ and $v_*(s_1) = 3.0 + 0.5 \times 4.0 = 5.0$. Later sweeps give $[4.0, 3.0]$, $[4.5, 3.5]$, $[4.75, 3.75]$, closing on $[5.0, 4.0]$.

Code

One sweep plus greedy choice, matching the hand trace:

1def eval_sweep(V: list[float], policy: list[int], gamma: float) -> list[float]:2    """One Bellman expectation sweep for the 2 state MDP."""3    # next state and reward tables: [state][action] -> (next_state, reward)4    nxt = [[0, 1], [0, 1]]5    rew = [[1.0, 3.0], [0.0, 2.0]]6    out = [0.0, 0.0]7    for s in (0, 1):8        a = policy[s]9        out[s] = rew[s][a] + gamma * V[nxt[s][a]]10    return [round(x, 2) for x in out]11
12
13def greedy(V: list[float], gamma: float) -> list[int]:14    """Greedy policy over one step lookahead."""15    nxt = [[0, 1], [0, 1]]16    rew = [[1.0, 3.0], [0.0, 2.0]]17    pol = [0, 0]18    for s in (0, 1):19        qs = [rew[s][a] + gamma * V[nxt[s][a]] for a in (0, 1)]20        pol[s] = max((0, 1), key=lambda a: qs[a])21    return pol22
23
24V1 = eval_sweep([0.0, 0.0], [0, 0], 0.5)25print(V1)  # -> [1.0, 0.0]26print(greedy(V1, 0.5))  # -> [1, 1]27print(eval_sweep(V1, [1, 1], 0.5))  # -> [3.0, 2.0]

Here $0$ means $a_1$ and $1$ means $a_2$, so $[1, 1]$ is $[a_2, a_2]$. Numbers match $V_1$ and $V_2$ above.

Watch Out For

The Quick Version

• GPI alternates $V$ toward $v_{\pi}$ and $\pi$ toward greedy $V$ at any grain.
• Each move helps one side and disturbs the other, tracing a zigzag to one rest point.
• That rest point satisfies Bellman optimality, hence $(\pi_*, v_*)$.
• On the two state MDP with gamma 0.5, one sweep finds the optimal policy and values close on 5.0 and 4.0.
• Policy iteration, value iteration, SARSA, Q-learning and actor critic are grain choices on this loop.

What to Read Next

• Policy Iteration
• Value Iteration in RL
• Policy Evaluation