The wider RL landscape

In March 2016 a program called AlphaGo beat Lee Sedol, one of the strongest Go players in the world, four games to one. Nothing in Chapters 1–9 explains how. Q-learning, REINFORCE and PPO all learn from trial and error, one action at a time. AlphaGo also thought ahead: before every move it searched thousands of possible futures. Six years later, ChatGPT learned what “a good answer” means from people comparing pairs of answers, an idea that also isn’t in Chapters 1–9.

So far you have followed one road: learn values (Chapters 3–6), then learn policies (Chapters 7–9). This chapter is a map of the country around that road. It covers seven regions, briefly, and each one turns out to matter for language models. Two of them get full treatment because Part III depends on them: Monte Carlo tree search (the search inside AlphaGo, and the ancestor of test-time search for LLMs), and the KL-regularized optimum $\pi^* \propto \pi_0\, e^{r/\beta}$ (the formula behind RLHF and DPO). For the rest you get the core idea, one concrete example, and a pointer to where it comes back.

A map of the territory

Everything in Chapters 3–9 shares four hidden assumptions:

1. You learn by interacting. You can try actions and see what happens, as often as you like.
2. The reward is given. Someone wrote down $r(s, a)$ for you.
3. You don’t use a model. The agent never asks “what would happen if…” before acting. (Chapter 4’s dynamic programming used a model, but there you had the exact one for free.)
4. You are the only learner. The environment doesn’t adapt to you.

Each region of the landscape drops one of these assumptions, or changes the objective:

Keep this table in mind. The chapter walks down it row by row.

Model-based RL and planning

A model is anything that predicts what the environment will do: given $s$ and $a$, it predicts $s'$ and $r$. With a model you can plan: try actions in your head before trying them in the world. Chapter 4’s value iteration was pure planning with a perfect model. Chapter 5’s Q-learning was pure learning with no model. Model-based RL sits in between: learn a model from experience, then use it.

Dyna: learn a model, then rehearse

The simplest version is Sutton’s Dyna (1990). Every real transition $(s, a, r, s')$ gets used twice: once for an ordinary Q-learning update, and once to update a model. The model is just a table that remembers what happened. Then, between real steps, the agent replays $n$ imaginary transitions sampled from that model, and does a Q-learning update on each.

Dyna-Q (tabular)
loop forever:
    take action a in state s (ε-greedy on Q); observe r, s'
    Q(s,a) += α [ r + γ max_a' Q(s',a') − Q(s,a) ]      # learn from the real step
    Model(s,a) ← (r, s')                                # remember what happened
    repeat n times:                                     # planning: rehearse
        pick a previously seen (s̃, ã) at random
        (r̃, s̃') ← Model(s̃, ã)
        Q(s̃,ã) += α [ r̃ + γ max_a' Q(s̃',a') − Q(s̃,ã) ]
    s ← s'

Why does this help? Think of a gridworld where the agent finally reaches the goal after a long random walk. Plain Q-learning updates only the last state’s value; the news travels back one step per episode. With Dyna, the planning updates replay old transitions next to the goal, so the value spreads backwards through many states before the next real step. Real experience is expensive and imaginary experience is cheap, so you squeeze more learning out of each real step. Sutton & Barto’s maze example (section 8.2) shows a large cut in the number of episodes needed once you add planning steps.

The catch is that the model is learned, so it is wrong in places, and a planner will find and exploit those mistakes. If the model wrongly believes a wall has a gap, the planner will happily route through it. This “the optimizer exploits the errors of whatever it is optimizing against” pattern is the single most important failure mode in this course. In Part III the thing being exploited is a learned reward model (Chapter 19).

Monte Carlo tree search

In a board game, the model is free: you know the rules exactly. The problem is size. Tic-tac-toe has only 5,478 legal positions, so you can solve it exactly with Chapter 4’s methods. Go has more than $10^{170}$. You can’t compute a value for every state, so you compute values only for the states that matter right now: the ones reachable from the current position. That is planning at decision time, and the best general method for it is Monte Carlo tree search (MCTS).

Here is the idea in one sentence: grow a search tree from the current position, one path at a time, spending more effort on the moves that look promising, and estimate how good a position is by playing random games from it.

Each node of the tree is a position. It stores two numbers:

• $N$: how many simulations have passed through it (its visit count),
• $W$: the total result of those simulations, counted from the point of view of the player who made the move into this node. A win counts $+1$, a loss $-1$, a draw $0$.

So $Q = W/N$ is the average result of that move for the player who chose it.

One simulation has four phases:

1. Selection. Start at the root. While every legal move from the current node already has a child node (the node is fully expanded), step to the child with the highest score (below). Stop at a node that still has an untried move, or at the end of the game.
2. Expansion. Add one new child for one untried move.
3. Rollout. From the new node, play random moves until the game ends. Call the result $z$: $+1$ if X wins, $-1$ if O wins, $0$ for a draw.
4. Backup. Walk back up the path. Every node gets $N \mathrel{+}= 1$, and $W$ moves by $+z$ or $-z$, depending on whose move led into that node.

After a few hundred simulations, you play the root move with the largest visit count. (Why not the largest $Q$? A move with 3 lucky visits can have the best average. A move that selection kept choosing hundreds of times is one the search trusts.)

Selection is a bandit problem (UCT)

How should selection pick a child? At each node you face exactly Chapter 2’s dilemma. Each child is an arm. Pulling it means running a simulation through it. You want to pull the best arm often (exploit), but you are not sure which arm is best (explore). Kocsis and Szepesvári (2006) had the idea of using UCB1 at every node. The result is called UCT (Upper Confidence bounds applied to Trees):

This is the UCB formula from Chapter 2 almost word for word. $N_\text{parent}$ plays the role of the total number of pulls $t$, and $N$ plays the role of $N_t(a)$. A child that has never been visited gets an infinite score, so every move is tried once before any is tried twice.

A worked example. Suppose the root has been visited $N_\text{parent} = 20$ times, it has three children, and $c = 1.4$:

($\ln 20 \approx 2.996$.) Child C has the worst average so far but is selected next, because with only 4 visits its average is the least trustworthy. With $c = 0.5$ the bonuses shrink to 0.274, 0.353 and 0.433, and A wins with 0.874. The constant $c$ sets the exchange rate between “looks good” and “barely tried”. Since our results live in $[-1, 1]$ (a range of 2, versus UCB1’s $[0, 1]$), values of $c$ around 1 to 2 work well.

Here is the whole algorithm:

MCTS(root position, n simulations, c):
    for i in 1..n:
        node ← root; path ← [root]
        # 1. selection
        while node is not terminal and node has no untried moves:
            node ← child of node maximizing  W/N + c·sqrt(ln N_node / N_child)
            path.append(node)
        # 2. expansion
        if node is not terminal:
            m ← pop a random untried move of node
            node ← new child of node for move m;  path.append(node)
        # 3. rollout
        z ← result of random play from node   (+1 X wins, −1 O wins, 0 draw)
        # 4. backup
        for v in path:
            v.N += 1
            v.W += z × (+1 if X moved into v else −1)
    return the root move with the largest N

See it run

The demo runs exactly the pseudocode above on tic-tac-toe. Step through single simulations phase by phase, then add simulations in bulk and watch the tree grow. The table shows each root move’s $N$, $Q$, exploration bonus and UCT score, so you can check every number against the formula.

The fork trap deserves a closer look, because it shows what the tree adds. The position is X . . / . O . / . . X with O to move (cells numbered 1–9 row by row, as in the demo).

• Perfect play. The free corners (3 and 7) lose. Say O plays 3. That threatens 3-5-7, so X must block at 7. But X’s block also makes two threats at once (1-4-7 and 7-8-9), a fork, and O can only stop one. The edges (2, 4, 6, 8) draw.
• Random play. Now average over random continuations instead. If both players move uniformly at random after O’s move, O’s expected result is exactly $1/6 \approx +0.17$ after a corner and exactly $+0.10$ after an edge. (You can enumerate every random game to check.) A random X rarely finds the fork, so the corners look better.

Flat Monte Carlo (rollouts from each move, no tree) estimates exactly those random-play values. So it picks a corner, and with more rollouts the noise shrinks around the wrong answer: it gets more confidently wrong. MCTS gets it right. The tree grows below O’s corner move, discovers X’s blocking-and-forking reply, and from then on selection plays that reply in every simulation through that branch. The node’s value becomes “what happens if both players play the tree’s moves”, not “what happens under random play”. The lab’s run.py plots this: MCTS’s accuracy climbs to 100% while flat Monte Carlo’s falls.

AlphaGo → AlphaZero → MuZero

Random rollouts are fine for tic-tac-toe and hopeless for Go: a random game of Go says almost nothing about who is ahead. DeepMind’s systems replaced the two weakest parts of MCTS with neural networks.

AlphaGo (Silver et al., 2016) trained a policy network $p_\theta(a \mid s)$, first by supervised learning on expert human games and then by policy-gradient RL through self-play. It also trained a value network $v_\theta(s)$ to predict the winner from a position. Inside MCTS, the policy network’s probabilities guided which moves to explore, and leaf positions were evaluated by mixing the value network with a fast rollout.

AlphaGo Zero (2017) and AlphaZero (Silver et al., 2017/2018, the same algorithm applied to chess, shogi and Go) removed the human data and the rollouts. A single network outputs both $p_\theta(\cdot \mid s)$ and $v_\theta(s)$. Selection uses the PUCT rule, UCT with a prior:

Here $Q(s, a)$ is the average value of the child, $W/N$ as before, and $N(s, a)$ is its visit count. The network’s prior $p_\theta$ tells the search where to look first: a move the network likes gets a large bonus until it has been visited a few times. The leaf value comes from $v_\theta$ instead of a random game.

Training is a loop of self-play games. At every move, MCTS runs and produces visit counts $N(s, a)$, which define a search policy $\pi_\text{MCTS}(a \mid s) \propto N(s, a)^{1/\tau}$. Here $\tau$ is a temperature (not a trajectory, its meaning elsewhere in this course): $\tau = 1$ copies the visit proportions, and $\tau \to 0$ puts all the probability on the most-visited move. When the game ends, let $z = \pm 1$ or $0$ be the result from the point of view of the player to move in $s$. The network is trained on each position $s$ to minimize:

Read the second term carefully: it is a cross-entropy loss that makes the raw network imitate the search. Search with a network is stronger than the network alone. Training the network on the search’s output makes the network stronger, which makes the next search stronger, and so on. This is policy iteration again, with MCTS as the improvement operator, and it is often called expert iteration (Anthony, Tian & Barber 2017): the search is the expert, the network is the apprentice.

MuZero (Schrittwieser et al., 2019/2020) removed the last piece of given knowledge: the rules. It learns a model, but not a model that predicts the next board image. It learns a hidden state $h$ and a dynamics function that maps $(h, a)$ to the next hidden state and the reward, trained only so that its predicted rewards, values and policies match reality. MCTS then runs inside this learned latent space. MuZero matched AlphaZero at Go, chess and shogi without being told the rules, and set a new state of the art on Atari.

Imitation learning: copying an expert

Sometimes writing down a reward is harder than showing what you want. You can’t easily write a reward for “drive like a careful human”, but you can record careful humans driving. Imitation learning learns a policy from demonstrations: a dataset of states and the actions an expert took in them.

The simplest method is behavior cloning (BC): treat it as supervised learning. Fit $\pi_\theta(a \mid s)$ to the expert’s state–action pairs by maximum likelihood:

This works surprisingly often. It also fails in a characteristic way.

Why errors compound

Picture a self-driving car trained by behavior cloning on a human who always stays in the middle of the lane. The training data contains only centered states. At test time the car makes a small mistake and drifts toward the edge. Now it is in a state the expert never visited, so the training data has no example of how to recover. It makes another mistake, drifts further, and the states get stranger. This is covariate shift: the learner’s own mistakes change the distribution of states it sees, away from the training distribution.

Here is the arithmetic. Suppose the cloned policy disagrees with the expert with probability $\epsilon$ on any state from the expert’s distribution, and that one disagreement can knock it off course for the rest of an episode of length $T$. The chance that it has gone off course by step $t$ is at most $t\epsilon$. So the expected number of steps spent off course is at most

With $\epsilon = 0.01$ and $T = 100$, that is up to about 50 bad steps, not the $\epsilon T = 1$ you might naively expect from a 1% error rate. Ross & Bagnell (2010) made this precise: behavior cloning’s cost can grow like $T^2 \epsilon$. That’s the compounding-error problem. Exercise 10.4 walks through the argument.

DAgger (Dataset Aggregation; Ross, Gordon & Bagnell 2011) fixes the root cause. Run the learner’s policy, record the states it actually visits, ask the expert what it would have done in each of them, add those labels to the dataset, retrain, and repeat. Now the training distribution matches the states the learner visits, including its mistakes, and the error grows only linearly in $T$. The price: you need an expert you can query on demand.

Learning the reward

Imitation copies actions. A different idea is to recover the goal and then optimize it with RL. If you know what the expert was trying to do, you can sometimes do it better than they did, or do it in situations they never saw.

Inverse reinforcement learning (IRL; Ng & Russell 2000) asks: given expert behavior, which reward function makes it optimal? The problem is badly underdetermined. The reward $r = 0$ makes every policy optimal, and many different rewards explain the same behavior. Practical IRL methods add assumptions to pick one. A famous one, maximum-entropy IRL (Ziebart et al. 2008), assumes the expert picks trajectories with probability $\propto \exp(\text{return})$. That is a Boltzmann distribution, and you will meet it again shortly.

A more practical way to learn a reward is to ask people to compare. Christiano et al. (2017), “Deep reinforcement learning from human preferences”, showed a human two short video clips of an agent’s behavior and asked which one was better. A reward model $r_\phi$ was trained to predict those choices, and an RL agent maximized $r_\phi$ while more comparisons were collected. Comparisons are much easier for people than writing a reward function or giving a numeric score. The paper reports learning Atari games and simulated robot tasks with human feedback on less than 1% of the agent’s interactions, and teaching a simulated robot novel behaviors such as a backflip from about an hour of human time.

The model of human choice they used is the Bradley–Terry model: the probability that a person prefers clip 1 over clip 2 is

with $\sigma$ the logistic sigmoid. Chapter 12 derives this model and trains reward models with it. That paper’s pipeline (collect comparisons → fit a reward model → run RL against it) is the RLHF pipeline. InstructGPT and ChatGPT ran it on language models five years later.

Offline RL: learning from a fixed dataset

Everything since Chapter 5 assumed you can keep collecting data. In many settings you can’t. A hospital has records of past treatments and outcomes, and nobody will let you experiment on patients to fill in the gaps. Offline RL (also called batch RL) learns a policy from a fixed dataset $\mathcal{D}$ of transitions collected by some other behavior policy $\mu$, with no further interaction.

Q-learning is off-policy (Chapter 5), so you might think you can just run it on $\mathcal{D}$. This fails, and the reason is worth understanding.

A worked example. One state, three actions. The dataset has 4 tries of $a_1$ (rewards 1, 1, 0, 1), 2 tries of $a_2$ (rewards 0.5, 0.5), and no tries of $a_3$. A table gives $Q(a_1) = 0.75$, $Q(a_2) = 0.5$, and $Q(a_3)$ stays at its initial value. With a neural network, $Q(a_3)$ is whatever the network extrapolates, say 1.3. The greedy policy picks $a_3$, the one action you know nothing about. In an online setting this would be harmless: you would try $a_3$, see its real reward, and correct the estimate. Offline, you never find out.

In a sequential problem it gets worse. The Q-learning target $r + \gamma \max_{a'} Q(s', a')$ takes a max over actions, and the max preferentially picks exactly the actions whose values are overestimated, which are often the actions the data never covers. Those errors then get bootstrapped into earlier states. This is the distribution shift problem of offline RL: the learned policy wants to go where the data isn’t, and that’s where its value estimates are least reliable. It is Chapter 5’s maximization bias and Chapter 6’s deadly triad, with no way to collect the data that would correct them.

The fix is pessimism: in the face of uncertainty, assume the worst. Online, Chapter 2’s UCB was optimistic: a bonus for being uncertain, because trying the arm will resolve the uncertainty. Offline nothing gets resolved, so you flip the sign. Use a lower confidence bound, $Q(a) - c/\sqrt{n(a)}$, where $n(a)$ is how often $a$ appears in the data. With $c = 1$ the example gives $0.75 - 1/2 = 0.25$ for $a_1$, $0.5 - 1/\sqrt 2 \approx -0.21$ for $a_2$, and $-\infty$ for the untried $a_3$. Pessimism picks $a_1$.

Deep offline RL methods implement this idea in two main ways:

• Conservative value estimates. Conservative Q-learning (CQL; Kumar et al. 2020) adds a term to the usual TD loss that pushes $Q$ down on actions the current policy likes and up on actions that appear in the data, so out-of-distribution actions can’t look attractive.
• Stay close to the data. Constrain the learned policy to stay near the behavior policy $\mu$, for example with a penalty $\beta\,\mathrm{KL}(\pi \Vert \mu)$. Then it rarely picks the actions whose values are pure extrapolation.

Maximum-entropy and KL-regularized RL

This section is the one Part III leans on most, so we take it slowly. Here is the question.

You have a reference policy $\pi_0$ (think: a language model after SFT) and a reward $r$. You want a new policy with high reward, but you don’t want to stray far from $\pi_0$. What is the best possible policy?

To keep things concrete, start with a single decision (one state: a bandit, as in Chapter 2), so a policy is just a probability distribution $\pi(a)$ over a finite set of actions. We measure “straying” with the KL divergence and trade it off against reward with a coefficient $\beta > 0$:

Call this the KL-regularized objective. Large $\beta$ means “stay very close to $\pi_0$”. Small $\beta$ means “mostly chase reward”.

The answer: tilt the reference by $e^{r/\beta}$

The maximizer has a closed form:

and the best achievable value is $J(\pi^*) = \beta \log Z$.

In words: start from the reference and multiply each action’s probability by $e^{r/\beta}$, then renormalize. Actions with high reward get boosted exponentially. $\beta$ sets how strongly. An action the reference never takes ($\pi_0(a) = 0$) stays impossible, whatever its reward.

A worked example. Three actions with $\pi_0 = (0.5, 0.3, 0.2)$, rewards $r = (0, 1, 2)$ and $\beta = 1$.

• Unnormalized weights $\pi_0(a) e^{r(a)}$: $0.5 \cdot 1 = 0.500$, $\;0.3 \cdot e = 0.816$, $\;0.2 \cdot e^2 = 1.478$.
• $Z = 0.500 + 0.816 + 1.478 = 2.793$.
• $\pi^* = (0.179,\; 0.292,\; 0.529)$.
• Expected reward $\mathbb{E}_{\pi^*}[r] = 0.292 + 2(0.529) = 1.350$.
• $\mathrm{KL}(\pi^* \Vert \pi_0) = 0.179 \ln\frac{0.179}{0.5} + 0.292 \ln\frac{0.292}{0.3} + 0.529 \ln\frac{0.529}{0.2} = 0.323$.
• $J(\pi^*) = 1.350 - 0.323 = 1.027$, and $\beta \log Z = \ln 2.793 = 1.027$. They agree.

Compare with two obvious alternatives. Copying the reference gives $J(\pi_0) = 0.7$ (expected reward $0.3 + 0.4$, zero KL). Going greedy, always action 3, gives reward 2 but pays $\mathrm{KL} = \ln(1/0.2) = 1.609$, so $J = 0.391$. The tilted policy beats both.

Why it’s the maximum

There is a slick proof that also tells you how much worse any other policy is. Take the definition of $\pi^*$ and solve it for the reward:

Substitute this into $J(\pi)$ for an arbitrary policy $\pi$:

In the second line we used $\sum_a \pi(a) = 1$, and the $\pi_0$‘s cancel in the third. So:

That KL is non-negative (Gibbs’ inequality) follows from Jensen’s inequality: $-\mathrm{KL}(p \Vert q) = \sum_a p(a) \log\frac{q(a)}{p(a)} \le \log \sum_a p(a) \frac{q(a)}{p(a)} = \log 1 = 0$, with equality only if $q/p$ is constant, that is $p = q$.

Three ways to read the formula

1. It’s a Boltzmann distribution, and $J$ is a free energy. Write the energy of action $a$ as $E(a) = -r(a)$ and the temperature as $T = \beta$. If $\pi_0$ is uniform, then $\mathrm{KL}(\pi \Vert \pi_0) = \log K - H(\pi)$, with $H$ the entropy and $K$ the number of actions, and maximizing $J$ is the same as minimizing

the Helmholtz free energy $U - TS$. Its minimizer is the Boltzmann distribution $\pi \propto e^{-E/T} = e^{r/\beta}$, with $F_\text{min} = -T \log \sum_a e^{-E(a)/T}$, minus $T$ times the log of the physicist’s partition function. (That sum is $K$ times our $Z$, because our $Z$ includes the weights $\pi_0(a) = 1/K$. The difference, $-T \log K$, is the constant that separates $-F$ from $J$.) That’s the Gibbs variational principle of statistical mechanics, and the identity in the Key callout is its standard proof. A non-uniform $\pi_0$ acts like a density of states, a prior weight on each action before the energy is taken into account.

2. $\beta$ is a temperature knob. As $\beta \to \infty$, $e^{r/\beta} \to 1$ and $\pi^* \to \pi_0$: the leash is so tight you just copy the reference. As $\beta \to 0$, the action with the largest reward dominates and $\pi^*$ becomes greedy (among actions $\pi_0$ allows). In between you get a smooth compromise. With uniform $\pi_0$, $\pi^* = \text{softmax}(r/\beta)$, and $\beta \log Z = \beta \log \frac{1}{K}\sum_a e^{r(a)/\beta}$ is a “soft max” of the rewards that tends to $\max_a r(a)$ as $\beta \to 0$.

3. Reward and policy determine each other. The rearranged form $r(a) = \beta \log\frac{\pi^*(a)}{\pi_0(a)} + \beta \log Z$ says that, up to a constant, the reward is the log-ratio of the optimal policy to the reference. If you know $\pi^*$ and $\pi_0$, you know the reward. Chapter 13 builds DPO on exactly this observation.

Sequential decisions: soft values and SAC

The same idea extends to whole MDPs. Add $-\beta\,\mathrm{KL}(\pi(\cdot \mid s) \Vert \pi_0(\cdot \mid s))$ to the reward at every step (or $+\alpha H(\pi(\cdot \mid s))$ with a uniform $\pi_0$; this is maximum-entropy RL). The Bellman equations of Chapter 4 keep their shape, but the hard $\max$ becomes the soft max you just met:

and the optimal policy at each state is again the tilted reference, $\pi^*(a \mid s) \propto \pi_0(a \mid s)\, e^{Q_\text{soft}(s, a)/\beta}$. Each state solves the one-step problem above, with $Q_\text{soft}$ in place of $r$. For a finite horizon, the proof applies the one-step result backwards in time, from the last step to the first. For an infinite discounted horizon, the soft Bellman operator is a $\gamma$-contraction, just like the ordinary one in Chapter 4, so it has a unique fixed point.

Why add entropy at all, in classic RL? Stochastic policies keep exploring, they don’t put all their eggs in one basket when two actions are nearly equally good, and the soft max makes optimization smoother. The best-known algorithm here is Soft Actor-Critic (SAC; Haarnoja et al. 2018), an off-policy actor-critic for continuous control. It learns a soft Q-function and a Gaussian policy that maximizes reward plus $\alpha$ times entropy, and it is one of the strongest baselines for robot control.

Exploration beyond ε-greedy

Chapter 2’s bandits had a few arms. Optimism (UCB) and posterior sampling (Thompson) handled exploration well. In a large MDP, the problem changes character: rewards can be so rare that random behavior never sees one. The standard example is the Atari game Montezuma’s Revenge, where the first reward requires a long, precise sequence of jumps and ladders. DQN, which explored with ε-greedy, scored essentially zero there (Mnih et al. 2015).

The fix is to give the agent an intrinsic reward for novelty, added to the environment’s reward: $r^+ = r + \kappa \cdot \text{bonus}(s)$, with $\kappa$ a weight. Three families:

• Count-based. $\text{bonus}(s) = 1/\sqrt{N(s)}$, where $N(s)$ counts visits to $s$. This is UCB’s bonus spread over states. In big state spaces you never see the same state twice, so methods estimate pseudo-counts from a density model of states (Bellemare et al. 2016).
• Curiosity / prediction error. Train a model to predict the next state (in a learned feature space), and reward the agent where the model is wrong, because that’s where something new is happening (Pathak et al. 2017).
• Random Network Distillation (RND; Burda et al. 2018). Train a network to match the outputs of a fixed, randomly initialized network on visited states. Its error is low on familiar states and high on new ones, so the error is a novelty signal. RND made large progress on Montezuma’s Revenge.

Prediction-error bonuses have a known failure, the noisy-TV problem. A source of pure randomness (a TV showing static) stays unpredictable forever, so a curious agent can stare at it forever. That’s reward hacking of the exploration bonus, the same pattern as the planner exploiting a wrong model.

Multi-agent RL and self-play

When several agents learn in the same environment, each one’s environment includes the others, and they keep changing. From any single agent’s point of view, the environment is non-stationary, which breaks the convergence guarantees from Chapters 4–5. Settings range from fully cooperative (a team sharing one reward) to fully competitive (two-player zero-sum games, where one’s gain is the other’s loss), with general-sum games in between.

The competitive two-player case has the cleanest success story: self-play, where the agent trains against copies of itself. TD-Gammon (Tesauro, early 1990s) learned backgammon this way, and AlphaZero learned Go, chess and shogi this way. Self-play gives you an automatic curriculum: your opponent is always exactly as strong as you are. It can also cycle. In rock-paper-scissors-like games, a policy that beats the current version may lose to an older one. Systems like DeepMind’s AlphaStar (StarCraft II) therefore trained against a league of past and present agents rather than just the latest copy.

Back to the map

Here is the table from the start of the chapter, now with the link you should remember from each row:

Summary

• Planning uses a model to look ahead. Dyna rehearses imagined transitions from a learned model. Planners exploit model errors, a pattern that returns as reward hacking.
• MCTS grows a tree one simulation at a time: select (UCT, which is UCB1 at every node), expand, roll out, back up. Store each node’s value from the point of view of the player who moved into it. The tree is what makes it better than flat Monte Carlo.
• AlphaZero replaces rollouts with a value network and guides search with a policy prior (PUCT), then trains the network to imitate the search’s visit counts: policy iteration with search as the improvement step. MuZero also learns the model.
• Behavior cloning is supervised learning on demonstrations. Its errors compound (up to about $\epsilon T^2$) because the learner drifts into states the expert never showed. DAgger labels the learner’s own states. SFT is behavior cloning.
• Learning rewards from comparisons (Christiano et al. 2017) is the template for RLHF’s reward models.
• Offline RL must avoid actions the data doesn’t cover. It is pessimistic where online methods are optimistic. DPO is offline, and the KL leash keeps RLHF near the data.
• The KL-regularized optimum: $\max_\pi \mathbb{E}_\pi[r] - \beta\,\mathrm{KL}(\pi \Vert \pi_0)$ is solved by $\pi^* \propto \pi_0 e^{r/\beta}$, with value $\beta \log Z$. For any $\pi$, $J(\pi) = \beta \log Z - \beta\,\mathrm{KL}(\pi \Vert \pi^*)$. This is the Gibbs variational principle (minimize free energy) and the foundation of Chapters 11 and 13.
• Exploration bonuses (counts, curiosity, RND) help with sparse rewards. Self-play gives an automatic curriculum in competitive games.

Exercises

def uct_score(child_W, child_N, parent_N, c):
    if child_N == 0:
        return math.inf
    return child_W / child_N + c * math.sqrt(math.log(parent_N) / child_N)

def backup(path, result):
    for node in path:
        node.N += 1
        node.W += result * node.player_just_moved   # flip sign for O's nodes

def run_simulation(root, c, rng):
    node, path = root, [root]
    while not node.terminal and not node.untried and node.children:          # 1. select
        node = max(node.children, key=lambda ch: uct_score(ch.W, ch.N, node.N, c))
        path.append(node)
    if not node.terminal and node.untried:                                     # 2. expand
        move = node.untried.pop(rng.randrange(len(node.untried)))
        node = Node(play(node.board, move), move, node)
        node.parent.children.append(node)
        path.append(node)
    result = rollout(node.board, rng)                                          # 3. rollout
    backup(path, result)                                                       # 4. backup
    return result

def gibbs_policy(pi0, r, beta):
    with np.errstate(divide="ignore"):
        logits = np.log(pi0) + r / beta      # -inf where pi0 == 0
    logits = logits - logits.max()           # stability: largest weight becomes e^0 = 1
    w = np.exp(logits)
    return w / w.sum()

def kl_objective(pi, pi0, r, beta):
    m = pi > 0                               # 0 log 0 = 0
    kl = np.sum(pi[m] * np.log(pi[m] / pi0[m]))
    return pi @ r - beta * kl

cd 10-landscape
python -m pytest -q          # your code: tests fail until you fill in the TODOs
RL_SOLUTIONS=1 python -m pytest -q   # reference solutions: all pass

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, ch. 8. Planning and learning in one framework: Dyna, prioritized sweeping, decision-time planning and MCTS. Read 8.1–8.3 and 8.11.
• Browne et al. (2012), A Survey of Monte Carlo Tree Search Methods. The standard MCTS reference: UCT, its variants and enhancements, with clear pseudocode.
• Silver et al. (2017), Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. AlphaZero: PUCT search plus a policy-value network trained to imitate the search. Short, and the methods section is the algorithm.
• Schrittwieser et al. (2019), Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model. MuZero: search inside a learned latent model that only predicts reward, value and policy.
• Ross, Gordon & Bagnell (2011), A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. DAgger, and the clearest statement of why behavior cloning’s errors compound.
• Christiano et al. (2017), Deep Reinforcement Learning from Human Preferences. Reward models from pairwise human comparisons; the direct ancestor of RLHF.
• Levine, Kumar, Tucker & Fu (2020), Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. Why offline RL is hard (distribution shift) and the main families of fixes.
• Levine (2018), Reinforcement Learning and Control as Probabilistic Inference. Maximum-entropy RL, soft value functions and the Boltzmann optimum derived carefully; the bridge to SAC and to the KL-regularized view of RLHF.

Next, Part III begins: Chapter 11 treats a language model as a policy and puts the KL-regularized optimum you just derived to work.