Generalized policy iteration on a blackboardSeven panels on the Part 1 cliff grid. 1: a random walker's values, −1072 at the start, and the Bellman expectation equation. 2: the greedy policy and one greedy step; no cell gets worse. 3: at the start the best move, −1002, beats the average, −1072. 4: six rounds of policy iteration, −1072 to −12.25. 5: value iteration, 14 sweeps. 6: a spiral between the policy and the value function that closes in on the optimum. 7: what evaluates and what improves in seven methods. 1. How good is a random walker? π(a | s) = 1/4 for each move a policy: chance of move a in cell s G cliff: −100, back to S S vπ(S) = −1072 above G: −482 redder = worse vπ(s) = Σ π(a | s) Σ p(s′, r | s, a) [ r + γ vπ(s′) ] a s′, r value function model: next cell, reward next cell's value r: reward γ = 0.99: discount one equation per cell: 37 equations, 37 unknowns 2. Act greedily on those numbers qπ(s, a) = Σ p(s′, r | s, a) [ r + γ vπ(s′) ] s′, r action value move a once, then follow π π′(s) = argmax qπ(s, a) a new policy the best move in each cell G cliff: −100, back to S S ← the red arrows end here, at the wall S: −1072 → −100 no cell got worse red: −1 a step forever = −1/(1 − γ) = −100 3. Why greedy never hurts at S, the four moves under the random walker: qπ(S, a) −1162 → cliff −1063 ↓ ← walls (2 moves) −1002 ↑ up max average = vπ(S) = −1072 max ≥ average qπ(s, π′(s)) ≥ vπ(s) in every cell one greedy move, then π: never worse ⇓ policy improvement theorem vπ′(s) ≥ vπ(s) in every cell greedy moves every time: never worse at S: −1072 vπ(S) −1002 qπ(S, up) −100 vπ′(S) ≤ ≤ 4. Repeat until nothing changes π0 E vπ0 I π1 E vπ1 I π2 E ⋯ I π* E v* E: evaluate (panel 1) I: improve (panel 2) G cliff: −100, back to S S round 4: 17 steps round 6: 13 steps vπ(S) −10 −100 −1000 0 −1072 1 −100 2 3 4 −15.7 5 6 −12.25 round a greedy step changes nothing, so in every cell vπ(s) = max qπ(s, a) a Bellman optimality: only v* solves it, so π = π* 5. Evaluation can stop early evaluate improve policy iteration ⋯ evaluate to the end, then improve: 6 rounds value iteration one sweep, then improve: 14 sweeps on the cliff grid anything between a few sweeps, one cell, one sample ... vk+1(s) = max Σ p(s′, r | s, a) [ r + γ vk(s′) ] a s′, r improve: best move evaluate: one sweep the max replaces the average over π(a | s) in panel 1 from v = 0, exact v* after 14 sweeps 6. GPI: two processes, one loop π policy v value function evaluate: v → vπ improve: π → greedy(v) π*, v* v = vπ values fit π π = greedy(v) π acts best on v full steps, as in policy iteration after evaluate after improve at π*, v* each step usually undoes the other, until the optimum 7. Same loop, different parts evaluate improve policy iteration solve for vπ greedy, all cells value iteration one sweep max in the sweep Monte Carlo average returns greedy per episode Sarsa one TD step on Q ε-greedy on Q Q-learning one TD step on Q max in the target actor-critic critic: TD error actor: gradient step AlphaGo Zero self-play winner z tree search (MCTS) AlphaGo Zero's training loss l = (z − v)2 − πT log p + c‖θ‖2 evaluate: v → winner z improve: p → search π regularizer p, v: the network's move probabilities and value

Take Part 1's 4 by 12 cliff grid. Every move gives −1, and a step into the cliff gives −100 and sends you back to the start S. This time you know all the rules before you move. So can you just work out the best way to the flag G?

Trying all 437≈1.9×10224^{37} \approx 1.9 \times 10^{22} rules, one move in each of the 37 cells, is hopeless. You'd rather take one rule and improve it, and for that you have to score it first. This side article to my reinforcement learning series follows Chapter 4 of Sutton and Barto, cited at the end.

How good is a random walker?

Start with a walker that picks moves at random. A rule like that is a policy π\pi, and a cell's value is the discounted sum of rewards you collect from there, on average. Scoring a policy is called policy evaluation, and since you know the rules, it comes down to a linear system.

Solving for the values

My script (linked under "Every round") solves the 37 equations directly. You can also sweep: start from any guess with the flag at 0, plug the current guesses into the right-hand side, and repeat.

vk+1(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γ vk(s′)]\begin{aligned} v_{k+1}(s) &= \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \\ &\qquad \big[r + \gamma\, v_k(s')\big] \end{aligned}

For γ<1\gamma < 1 this converges to vπv_\pi in the limit.

Act greedily on those numbers

What you'd expect from making a move once, then walking randomly again, is its action value. Pick the best move in every cell and you get the greedy policy π′\pi', and switching to it is policy improvement.

The result looks silly. The walker rated the top-left corner a little above its neighbors, so ten cells now march into that corner and bump the top wall forever. Still, every cell's value beats the walker's.

Why greedy never hurts

Was that luck? No, and you can see why from S alone.

The ⇓ step on the board, from qπ(s,π′(s))≥vπ(s)q_\pi(s, \pi'(s)) \ge v_\pi(s) to vπ′(s)≥vπ(s)v_{\pi'}(s) \ge v_\pi(s) in every cell, is the policy improvement theorem, and it takes one more idea: use the greedy move again at the next cell, and the next. After kk steps, all that's left of the old policy is its value kk steps ahead, times γk\gamma^k, which shrinks to zero.

The proof chain

Unroll qπ(s,π′(s))≥vπ(s)q_\pi(s, \pi'(s)) \ge v_\pi(s) one step at a time:

vπ(s)≤qπ(s,π′(s))=E[Rt+1+γvπ(St+1)∣St=s,At=π′(s)]=Eπ′[Rt+1+γvπ(St+1)∣St=s]≤Eπ′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=Eπ′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]≤Eπ′[Rt+1+γRt+2+γ2Rt+3+γ3vπ(St+3)∣St=s]    ⋮≤Eπ′[Rt+1+γRt+2+γ2Rt+3+γ3Rt+4+⋯∣St=s]=vπ′(s)\begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s)) \\ &= \mathbb{E}\big[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = \pi'(s)\big] \\ &= \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\big] \\ &\le \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s\big] \\ &= \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \mid S_t = s\big] \\ &\le \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 v_\pi(S_{t+3}) \mid S_t = s\big] \\ &\;\;\vdots \\ &\le \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \mid S_t = s\big] \\ &= v_{\pi'}(s) \end{aligned}

Here Eπ′\mathbb{E}_{\pi'} averages over following π′\pi', and each ≤\le uses that inequality at the next cell.

Repeat until nothing changes

Score the new policy, improve it again, and keep going. That's policy iteration, and here it takes six rounds. In round 6, S finds the 13-step route along the cliff edge, the same one Q-learning found in Part 1.

Out of 1.9×10221.9 \times 10^{22} policies, it scored six, plus the walker. It also has to stop. With the tie rule in the drawer, every round makes some cell strictly better, so no policy comes back.

Every round
Round v(S) Moves changed Cells improved
0 (random) −1072.24
1 −100.00 all 37 37
2 −100.00 6 6
3 −100.00 5 5
4 −15.71 5 6
5 −15.71 2 2
6 −12.25 2 9

Round 1 breaks ties in the order up, right, down, left, and all 24 orders give the same numbers. After that, when two moves tie, the policy keeps its current move (one fix for the bug in the book's Exercise 4.4). Code: python3 scripts/rl_gpi_figures.py.

Evaluation can stop early

Policy iteration solves for the values exactly before every greedy step. Value iteration stops evaluating after one sweep, a single update of every cell from its neighbors' current values, and takes the greedy max inside it.

In general it reaches the optimal values v∗v_* only in the limit. The book says that evaluation "can be truncated in several ways without losing the convergence guarantees of policy iteration".

Two processes, one loop

So you can split the work between evaluation and improvement in many ways. The book calls any such mix generalized policy iteration (GPI): "letting policy-evaluation and policy-improvement processes interact, independent of the granularity and other details of the two processes".

The two processes "can be viewed as both competing and cooperating". Once evaluation scored round 1's policy, for example, that policy was no longer greedy in 6 cells. Then comes the big claim: "Almost all reinforcement learning methods are well described as GPI".

The same loop inside other methods

Without a model, methods estimate values from experience instead. Monte Carlo averages the returns of whole episodes, and temporal-difference (TD) methods move an estimate toward one reward plus the discounted next estimate.

In AlphaGo Zero, Monte Carlo tree search (MCTS) usually picks much stronger moves than the network's raw move probabilities would, so the paper calls it "a powerful policy improvement operator" and uses search and self-play "repeatedly in a policy iteration procedure". The book agrees that AlphaGo Zero "implemented a form of policy iteration". It never calls actor-critic GPI outright, though (notes under Sources).

What I take from it

In any new method, I now look for the two processes: what judges the policy, what improves it, and how much each does before it hands over. Most methods in the series differ in those three answers.

Sources

Notes on the sources
  • The book gives Q-learning its GPI label in the introduction and summary of Chapter 6, not in the Q-learning section.
  • The book never calls actor-critic a form of GPI. The Chapter 6 summary calls it "a third way in which TD methods can be extended to control", and Chapter 17 lists GPI and actor-critic as separate ways to learn a policy. Haarnoja et al. are more direct: "Actor-critic algorithms are typically derived starting from policy iteration".

← All writing