14  Reinforcement Learning

In supervised learning, a prediction typically does not affect which test example is observed next. In reinforcement learning, an action changes the state of the environment and therefore affects subsequent observations and rewards. The agent consequently influences both its performance and the data from which it learns.

Figure 14.1 shows this interaction. Unrolling the agent–environment loop over time produces a trajectory \(\tau=(s_0,a_0,r_0,s_1,\ldots)\). This feedback introduces the central difficulties studied in this chapter: exploration determines which data are collected, errors alter later state distributions, and policy updates change the distribution used for subsequent learning. The same formulation also applies to language-model generation, where the context is a state and the next token is an action; Section 15.7 develops that correspondence.

Figure 14.1: At time \(t\), the agent selects action \(a_t\) (blue), and the environment returns reward \(r_t\) and next state \(s_{t+1}\) (orange). Unrolling this interaction produces the trajectory \(\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots)\).

The sections progress from settings with the most information to settings with the least. Section 14.1 defines the Markov decision process, and Section 14.2 solves a known finite MDP by dynamic programming. Section 14.3 replaces the model with expert demonstrations. Section 14.4 then removes the expert and learns action values from sampled transitions. Section 14.5 optimizes the policy directly, while Section 14.6 develops lower-variance estimators. Finally, Section 14.7 replaces tabular representations with neural networks for continuous state and action spaces.

Chapter 15 continues with bootstrapped critics, controlled reuse of on-policy data, replay buffers, regularized objectives, and offline learning. Figure 14.2 organizes the methods in both chapters by what they learn and which data they use.

Figure 14.2: Reinforcement-learning methods organized by what they estimate and which data they use. Solid boxes denote methods introduced in this chapter; dashed boxes and gray labels denote methods from Chapter 15. Behavior cloning trains on a fixed expert dataset, whereas DAgger trains on learner-generated states relabeled by an expert. Value iteration consumes a known transition kernel rather than sampled transitions. The arrow from policy gradients to PPO denotes limited reuse of recent trajectories through importance ratios.

Table 14.1 provides a more detailed guide to the algorithms in both chapters. It records what each method estimates, which data it can use, and where it is introduced.

Table 14.1: The algorithm map of these two chapters. “Named in” marks methods this book describes but does not implement.
algorithm what it estimates which data may drive the update where
value iteration \(V^*\) exactly, by sweeping the Bellman operator none: it consumes the kernel \(P\) and reward \(r\) Section 14.2
behavior cloning \(\pi(a \mid s)\) by cross-entropy on demonstrations a fixed expert dataset Section 14.3
DAgger the same fit the learner’s own states, relabeled by an expert on call Section 14.3
Q-learning (tabular) \(Q^*\) from sampled backups any behavior’s transitions (off-policy) Section 14.4
SARSA the behavior’s own \(Q\), exploration included its own transitions (on-policy) named in Section 14.4
UCB, Thompson sampling arm means plus their uncertainty its own pulls (the bandit) Section 14.4
REINFORCE \(\nabla_\theta J\) by the score function fresh trajectories from the current policy only Section 14.5
REINFORCE with baselines, RLOO the same gradient at lower variance fresh trajectories from the current policy Section 14.6
GRPO group-normalized advantages, no value network fresh groups of responses per prompt weights in Section 14.6; machinery in Chapter 15
REINFORCE with a learned critic, on networks \(\pi_\theta\) and \(\hat{V}\) as networks fresh trajectories from the current policy Section 14.7
actor-critic (A2C) \(\pi_\theta\) plus a bootstrapped critic fresh, near-current trajectories Section 15.1
PPO \(\pi_\theta\) under a clipped probability ratio one batch, reused for a few steps Section 15.2
KL-regularized policy optimization, RLHF a policy tilted from a reference by reward rollouts scored by a learned reward Chapter 15
DQN, Double DQN \(Q\) as a network a replay buffer of stale experience Section 15.4
Rainbow DQN plus its measured components a replay buffer named in Section 15.4
DDPG, TD3 a critic, and a deterministic actor trained to maximize it a replay buffer (off-policy) named in Section 14.7 and Section 15.5
SAC twin soft critics, and a stochastic squashed actor maximizing reward plus entropy a replay buffer (off-policy) Section 15.5
offline Q-learning with pessimism, CQL \(Q\) penalized where the data is thin a fixed logged dataset, no interaction at all Section 15.6
Decision Transformer a return-conditioned sequence model a fixed logged dataset named in Section 15.6
MuZero, Dreamer a learned model of the environment, to plan or imagine in its own interaction, replayed through the model named in Chapter 15
DPO the regularized optimum directly from preferences a fixed preference dataset Chapter 15 and the Language Models part

The experiments use small environments so that results can be evaluated against exact solutions and repeated across random seeds on a CPU. Numerical conclusions are reported with their relevant uncertainty and limitations in the sections where they arise. This chapter does not cover multi-agent, meta-, hierarchical, or goal-conditioned reinforcement learning, and it introduces partial observability only briefly. Model-based learning, large-scale RLHF, and preference optimization are treated elsewhere in the book.

Resources and Further Reading

The following freely available resources provide theoretical treatments, courses, implementations, and empirical guidance.

Textbooks

  • Sutton and Barto, Reinforcement Learning: An Introduction (Sutton and Barto 2018) provides a comprehensive introduction to value methods, policy methods, planning, and function approximation. Sutton and Barto received the 2024 Turing Award for their foundational contributions to reinforcement learning.
  • Szepesvári, Algorithms for Reinforcement Learning (Szepesvári 2010) states this chapter’s algorithms and their guarantees in under a hundred pages.
  • Bertsekas, A Course in Reinforcement Learning (Bertsekas 2025) develops reinforcement learning from the perspective of optimal control and dynamic programming.
  • Agarwal, Jiang, Kakade, and Sun, Reinforcement Learning: Theory and Algorithms (Agarwal et al. 2019) supplies the sample-complexity rates this chapter states qualitatively.
  • Lattimore and Szepesvári, Bandit Algorithms (Lattimore and Szepesvári 2020) is the full theory behind the exploration interlude of Section 14.4.

Courses

Annotated implementations

Empirical practice