Chapter 27 · Part VI: Frontier Techniques
Reinforcement Learning
An agent acts, the world responds, and a reward arrives, perhaps much later. Reinforcement learning turns that loop into an optimization problem; this chapter covers planning with known models, optimal control, learning values and policies from experience, language-model post-training, and robot learning.
After this chapter you will be able to
- Formalize sequential decision making as a Markov decision process with returns, value functions, and Bellman equations.
- Solve known MDPs with value iteration and policy iteration, and prove convergence with the contraction argument.
- Use fitted value iteration for continuous states, and derive the linear quadratic regulator with the Riccati recursion.
- Explain iLQR, model predictive control, and LQG control with a Kalman filter.
- Implement tabular Q-learning and explain the stabilizers of deep Q-networks.
- Derive the policy-gradient theorem (REINFORCE), the role of baselines, and the PPO objective, and map language-model post-training onto them.
- Describe imitation learning, DAgger, sim-to-real transfer, world models, and vision–language–action models for robots.
In supervised learning a teacher supplies the right answer for every input. In reinforcement learning (RL) an agent receives only a scalar reward for the actions it takes, often long after the actions that earned it, and must discover good behavior by trial and error. RL and its relative, optimal control, drive game-playing systems, robot controllers, and the post-training stages of modern language models (Sections 24.6 and 24.7). We begin with problems whose dynamics are known, which can be solved by planning, then turn to learning from experience.
27.1The Reinforcement Learning Problem
In reinforcement learning (RL), an agent interacts with an environment over time. At each step $t$ it observes a state $s_t$, chooses an action $a_t$, receives a reward $r_{t+1}$, and the environment moves to a new state $s_{t+1}$. Nobody tells the agent the correct action; it must discover which actions lead to high reward, possibly much later. This creates two problems absent from supervised learning: credit assignment (which earlier action deserves credit for a reward) and exploration (trying actions that might be better than the best known).
Markov decision processes. An MDP specifies states $\mathcal S$, actions $\mathcal A$, transition probabilities $p(s'\mid s,a)$, a reward function, and a discount factor $\gamma\in[0,1)$. “Markov” means the next state depends only on the current state and action. A policy $\pi(a\mid s)$ gives the probability of each action in each state. The goal is to maximize the expected return, the discounted sum of future rewards:
$$G_t = r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+\dots = \sum_{k=0}^\infty\gamma^kr_{t+k+1} . \tag{27.1}$$Discounting makes the sum finite and expresses a preference for sooner rewards.
Value functions and the Bellman equation. The state value $V^\pi(s)=\E_\pi[G_t\mid s_t=s]$ is the expected return from state $s$ when following $\pi$; the action value $Q^\pi(s,a)=\E_\pi[G_t\mid s_t=s,a_t=a]$ is the expected return after taking action $a$ in $s$ and following $\pi$ afterward. Because $G_t=r_{t+1}+\gamma G_{t+1}$, values satisfy a recursive consistency condition, the Bellman equation:
$$\begin{gathered} Q^\pi(s,a) = \E\big[r_{t+1}+\gamma\,Q^\pi(s_{t+1},a_{t+1})\ \big|\ s_t=s,a_t=a\big],\\ V^\pi(s)=\sum_a\pi(a\mid s)\Big(R(s)+\gamma\sum_{s'}p(s'\mid s,a)V^\pi(s')\Big). \end{gathered} \tag{27.2}$$The optimal action values $Q^*(s,a)=\max_\pi Q^\pi(s,a)$ satisfy the Bellman optimality equation
and once $Q^*$ is known, the optimal policy is simply greedy: in each state, take $\argmax_aQ^*(s,a)$.
Here and in the next sections we write $R(s)$ for the expected reward received in state $s$; rewards that depend on the action as well change only the notation.
27.2Planning with a Known Model: Value and Policy Iteration
Suppose first that the MDP is known: we have the transition probabilities and rewards, and want the optimal policy. This is planning, and dynamic programming (Bellman 1957) solves it for finite state spaces.
Value iteration. Turn the Bellman optimality equation for $V^*(s)=\max_aQ^*(s,a)$ into an update and apply it to every state, repeatedly:
$$V_{k+1}(s)\gets R(s)+\gamma\max_a\sum_{s'}p(s'\mid s,a)\,V_k(s') . \tag{27.4}$$Write the right-hand side as an operator, $V_{k+1}=\mathcal TV_k$. For any two value functions $V$ and $V'$, and every state,
$$\big|(\mathcal TV)(s)-(\mathcal TV')(s)\big|\le\gamma\max_a\sum_{s'}p(s'\mid s,a)\,\big|V(s')-V'(s')\big|\le\gamma\norm{V-V'}_\infty , \tag{27.5}$$because the difference of two maxima is at most the maximum of the differences. So $\mathcal T$ is a contraction in the max-norm with factor $\gamma$. By the Banach fixed-point theorem it has exactly one fixed point, which is $V^*$, and value iteration converges to it from any starting point, with the error shrinking by at least a factor $\gamma$ per sweep: $\norm{V_k-V^*}_\infty\le\gamma^k\norm{V_0-V^*}_\infty$. The optimal policy is greedy with respect to $V^*$: $\pi^*(s)=\argmax_a\sum_{s'}p(s'\mid s,a)V^*(s')$.
Policy iteration. Alternate two steps. Policy evaluation: for the current policy $\pi$, solve the linear Bellman equations Equation (27.2) exactly; in matrix form, with $\mathbf P^\pi$ the transition matrix under $\pi$,
$$\vv^\pi=\vr+\gamma\mathbf P^\pi\vv^\pi\quad\Longrightarrow\quad\vv^\pi=(\mI-\gamma\mathbf P^\pi)^{-1}\vr . \tag{27.6}$$Policy improvement: make the policy greedy with respect to $\vv^\pi$. The improved policy is at least as good in every state (the policy improvement theorem), and since there are finitely many deterministic policies and none can repeat, policy iteration terminates with an optimal policy, typically after very few iterations, each more expensive than a value-iteration sweep.
Learning the model. If the transition probabilities are unknown but the state space is small, estimate them from experience: $\hat p(s'\mid s,a)$ is the fraction of the times action $a$ in state $s$ led to $s'$, and $\hat R(s)$ the average reward observed in $s$. Then plan in the estimated MDP, act with the resulting policy (with some exploration), and repeat. This model-based approach uses data efficiently, and the idea scales up when the model is a neural network (Section 27.8).
27.3Continuous States: Fitted Value Iteration
Value iteration needs a table entry per state, which is impossible when the state is continuous (the angle and angular velocity of a pendulum, the joint positions of a robot). Fitted value iteration represents $V$ with a function approximator, for example $V(s)=\vtheta\T\bm\phi(s)$ with features $\bm\phi$, and uses a simulator or learned model that can sample next states. Repeat:
- Sample $m$ states $s^{(1)},\dots,s^{(m)}$.
- For each state and action, sample $k$ next states $s'_1,\dots,s'_k$ from the model and estimate $q(a)=R(s^{(i)})+\gamma\frac1k\sum_jV(s'_j)$; set the target $y^{(i)}=\max_aq(a)$.
- Fit $\vtheta$ by least squares (Chapter 4) to make $V(s^{(i)})\approx y^{(i)}$.
Each iteration is a value-iteration step followed by a regression. Unlike exact value iteration, the combination of the max-backup with function approximation is not guaranteed to converge, but with good features it works well in practice, and it is the template for the neural-network methods of Section 27.5.
27.4Linear Quadratic Regulation
One continuous problem can be solved exactly: linear dynamics with quadratic costs, the workhorse of classical control. The state evolves as
$$s_{t+1}=\mA s_t+\mB a_t+w_t,\qquad \text{cost}=\sum_{t=0}^{T-1}\big(s_t\T\mathbf Us_t+a_t\T\mW a_t\big)+s_T\T\mathbf U_Ts_T, \tag{27.7}$$with positive semidefinite state cost $\mathbf U$, positive definite action cost $\mW$, and zero-mean noise $w_t$. (We minimize cost instead of maximizing reward, as is conventional in control.) For example, a cart at position $x$ with velocity $v$ driven by an acceleration $a$, discretized with time step $\Delta t$, has $s=(x,v)$, $\mA=\left(\begin{smallmatrix}1&\Delta t\\0&1\end{smallmatrix}\right)$, and $\mB=\left(\begin{smallmatrix}\Delta t^2/2\\\Delta t\end{smallmatrix}\right)$.
Dynamic programming on quadratics. Guess that the optimal cost-to-go from time $t$ is quadratic, $V_t(s)=s\T\mathbf P_ts+c_t$, which holds at $t=T$ with $\mathbf P_T=\mathbf U_T$. One step of the Bellman recursion minimizes $s\T\mathbf Us+a\T\mW a+\E[V_{t+1}(\mA s+\mB a+w)]$ over $a$. The expression is quadratic in $a$; setting its gradient to zero gives a linear optimal policy, and substituting back shows that $V_t$ is again quadratic:
$$\begin{gathered} a_t^*=-\mK_ts_t,\qquad \mK_t=\big(\mW+\mB\T\mathbf P_{t+1}\mB\big)^{-1}\mB\T\mathbf P_{t+1}\mA,\\ \mathbf P_t=\mathbf U+\mA\T\mathbf P_{t+1}\big(\mA-\mB\mK_t\big). \end{gathered} \tag{27.8}$$This backward recursion for $\mathbf P_t$ is the discrete Riccati equation. Iterated to a fixed point it gives the stationary gain of the infinite-horizon problem. Two facts are worth noticing. The noise $w_t$ only adds a constant to the cost-to-go and does not change the optimal action (certainty equivalence). And the trade-off is set by $\mathbf U$ and $\mW$: a large action cost gives gentle, slow control; a small one gives aggressive control.
Nonlinear systems: iLQR and DDP. For nonlinear dynamics $s_{t+1}=f(s_t,a_t)$ and non-quadratic costs, start from a nominal trajectory, linearize the dynamics and take a second-order expansion of the cost around it, solve the resulting LQR problem for the deviations, update the trajectory, and repeat. This is the iterative LQR (iLQR); differential dynamic programming (DDP) also keeps second-order terms of the dynamics. Re-solving the problem from the current state at every time step and executing only the first action is model predictive control (MPC), the standard way to control robots, vehicles, and chemical plants with a model.
Partial observability: LQG. Often the state is not observed directly, only noisy measurements $y_t=\mathbf Cs_t+v_t$. With Gaussian noise, the Kalman filter maintains the exact Gaussian posterior over the state by alternating a prediction step (push the mean and covariance through the dynamics) and an update step (correct them with the new measurement). The linear quadratic Gaussian (LQG) controller applies the LQR gain to the Kalman filter’s state estimate, and the separation principle guarantees that this combination is optimal: estimation and control can be designed independently.
27.5Model-Free Value Learning: Q-Learning and DQN
Q-learning (Watkins and Dayan 1992) estimates $Q^*$ from experience, without knowing the transition probabilities. Keep a table $Q(s,a)$. After each transition $(s,a,r,s')$, move $Q(s,a)$ toward the one-step target suggested by Equation (27.3):
$$Q(s,a)\gets Q(s,a)+\eta\Big(\underbrace{r+\gamma\max_{a'}Q(s',a')}_{\text{target}}-Q(s,a)\Big). \tag{27.9}$$The bracketed difference is the temporal-difference (TD) error. This is a stochastic-gradient-like step that uses the current estimate of the next state’s value as a stand-in for the unknown future (“bootstrapping”). Under standard conditions (every state–action pair is visited infinitely often and the step sizes decay appropriately), $Q$ converges to $Q^*$.
Exploration. If the agent always takes the action that currently looks best, it may never discover a better one. The $\epsilon$-greedy policy takes a random action with probability $\epsilon$ and the greedy action otherwise, with $\epsilon$ often decayed over training. Q-learning is off-policy: it learns about the greedy policy while behaving $\epsilon$-greedily.
- initialize $Q(s,a)=0$ for all $s,a$
- for each episode:
- $s\gets$ initial state
- while $s$ is not terminal:
- $a\gets$ random action with probability $\epsilon$, else $\argmax_aQ(s,a)$
- take $a$, observe $r,s'$
- $Q(s,a)\gets Q(s,a)+\eta\big(r+\gamma\max_{a'}Q(s',a')-Q(s,a)\big)$ $\max$ term is 0 if $s'$ terminal
- $s\gets s'$
Deep Q-networks. For large state spaces (the pixels of a video game), replace the table by a neural network $Q_{\vtheta}(s,a)$ and minimize the squared TD error over transitions $(s,a,r,s')$ sampled from a replay buffer of past experience:
$$\Loss(\vtheta)=\E_{(s,a,r,s')\sim\mathcal D}\Big[\big(r+\gamma\max_{a'}Q_{\vtheta^-}(s',a')-Q_{\vtheta}(s,a)\big)^2\Big]. \tag{27.10}$$Two stabilizers made this work on Atari games, where a single network learned dozens of games from pixels (Mnih et al. 2015): the replay buffer, which breaks the strong correlation between consecutive transitions and reuses each one many times, and a target network $\vtheta^-$, a copy of the weights updated only every few thousand steps, so that the regression target does not move with every gradient step. Because the max over noisy estimates is biased upward, double DQN (van Hasselt et al. 2016) chooses the next action with the online network and evaluates it with the target network. The combination of bootstrapping, off-policy data, and function approximation (the “deadly triad”) can diverge, which is why these stabilizers matter.
27.6Policy Gradients
Value-based methods are awkward when actions are continuous (a robot’s joint torques) or when the policy itself is the object of interest, as for a language model. Policy-gradient methods instead parameterize the policy $\pi_{\vtheta}(a\mid s)$ directly and do gradient ascent on the expected return $J(\vtheta)=\E_{\tau\sim\pi_{\vtheta}}[R(\tau)]$, where $\tau=(s_0,a_0,r_1,s_1,\dots)$ is a whole trajectory and $R(\tau)$ its return.
The log-derivative trick. The difficulty is that $\vtheta$ affects which trajectories are sampled. Write the expectation as a sum over trajectories and use $\nabla p=p\,\nabla\log p$:
$$\nabla_{\vtheta}J = \sum_\tau R(\tau)\,\nabla_{\vtheta}p_{\vtheta}(\tau) = \sum_\tau p_{\vtheta}(\tau)\,R(\tau)\,\nabla_{\vtheta}\log p_{\vtheta}(\tau) = \E_{\tau\sim\pi_{\vtheta}}\big[R(\tau)\,\nabla_{\vtheta}\log p_{\vtheta}(\tau)\big].$$The probability of a trajectory is a product of policy probabilities and environment transitions, $p_{\vtheta}(\tau)=p(s_0)\prod_t\pi_{\vtheta}(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t)$. Only the policy terms depend on $\vtheta$, so the unknown environment dynamics drop out of the gradient:
This is the REINFORCE estimator (Williams 1992): sample trajectories, and increase the log-probability of every action taken, in proportion to the return that followed. Compare with supervised learning: it is a cross-entropy gradient on the agent’s own actions, weighted by how good the outcome was.
Baselines and advantages. The estimator is unbiased but very noisy. Subtracting a baseline $b(s_t)$ that does not depend on the action leaves the expectation unchanged (because $\E_{a\sim\pi}[\nabla\log\pi(a\mid s)]=\nabla\sum_a\pi(a\mid s)=\nabla1=0$) and can reduce the variance greatly. The natural choice is the value $V(s_t)$, giving the advantage $A_t=G_t-V(s_t)$: how much better the outcome was than expected. Actor-critic methods learn $V$ with a second network (the critic). GRPO (Section 24.7) instead uses the mean reward of a group of samples for the same prompt as the baseline.
PPO. Large policy updates can collapse performance. Proximal policy optimization (Schulman et al. 2017) reuses each batch of samples for several gradient steps while limiting how far the policy moves. With the probability ratio $\rho_t(\vtheta)=\pi_{\vtheta}(a_t\mid s_t)/\pi_{\vtheta_{\text{old}}}(a_t\mid s_t)$, it maximizes the clipped objective
$$\E_t\Big[\min\big(\rho_t(\vtheta)A_t,\ \mathrm{clip}(\rho_t(\vtheta),1-\varepsilon,1+\varepsilon)A_t\big)\Big], \tag{27.12}$$which removes the incentive to change any action’s probability by more than a factor of about $1\pm\varepsilon$ (typically $\varepsilon=0.2$) in one update.
27.7Reinforcement Learning for Language Models
The language-model post-training methods of Chapter 24 are RL in this framework:
| RL concept | Language model |
|---|---|
| State $s_t$ | the prompt plus the tokens generated so far |
| Action $a_t$ | the next token (one of $V$ choices) |
| Policy $\pi_{\vtheta}(a\mid s)$ | the model’s softmax over the vocabulary |
| Transition | deterministic: append the token |
| Reward | at the end: a learned reward model (RLHF) or an automatic check (RLVR) |
| Regularization | KL penalty toward a reference model |
With a single reward at the end of a response, the REINFORCE gradient increases the log-probability of every token of a high-reward response and decreases it for a low-reward one. RLHF typically used PPO with a learned value network; GRPO drops the value network in favor of group-relative advantages. Because rewards are sparse and responses long, credit assignment is the central difficulty, and much current research concerns denser feedback (rewarding intermediate steps) and rewards for tasks without automatic checks.
Earlier landmark systems combined RL with search: AlphaGo (Silver et al. 2016) learned policy and value networks for Go from human games and self-play, and used them to guide a tree search, defeating a world champion in 2016.
27.8Robot Learning
Robots make reinforcement learning hard in every way at once. Real-world trials are slow, expensive, and can break hardware; states come from cameras and other noisy sensors; actions are continuous and high-dimensional; and rewards for tasks like “fold the shirt” are hard to specify. Robot learning therefore relies on a mixture of the methods of this chapter with supervised learning from demonstrations, simulation, and pretrained vision and language models.
Imitation learning. The simplest approach collects demonstrations from a human operator (by teleoperation) and trains a policy by supervised learning to predict the demonstrated action from the observation, $\min_{\vtheta}\E_{(s,a^*)\sim\mathcal D}[-\log\pi_{\vtheta}(a^*\mid s)]$. This behavior cloning is simple and widely used, but it has a characteristic failure: a small mistake takes the robot to a state the expert never visited, where the policy is more likely to err again, and errors compound. If the cloned policy errs with probability $\varepsilon$ in the states the expert visits, its expected cost over a horizon of $T$ steps can grow as $\varepsilon T^2$ rather than $\varepsilon T$. DAgger (Ross et al. 2011) fixes the distribution mismatch: run the current policy, ask the expert to label the states the policy actually visits with the correct actions, add them to the data set, retrain, and repeat. Its guarantee is linear in $T$. Demonstrations are often multimodal (go around an obstacle on the left or on the right), and averaging them gives a bad action; modern policies therefore model the full action distribution, for example with a diffusion model over short sequences of future actions (Chi et al. 2023).
Simulation and sim-to-real. Physics simulators produce unlimited, safe, parallel experience, and policies for locomotion and in-hand manipulation are now routinely trained with RL in simulation. Simulators are imperfect, however, so a policy can exploit simulation artifacts and fail on hardware. Domain randomization (Tobin et al. 2017) randomizes textures, lighting, masses, friction, and delays during training, so that the real world looks like just another variation.
Learned models. Model-based RL learns the dynamics, increasingly as a world model that predicts future observations or latent states from actions, and plans with it (with MPC, Section 27.4) or trains a policy inside it on imagined trajectories (Hafner et al. 2020). This uses real data far more efficiently than model-free RL.
Vision–language–action models. The newest approach starts from a vision–language model (Section 23.4) pretrained on web data and fine-tunes it on robot demonstrations to output actions. RT-2 (Brohan et al. 2023) represented actions as text tokens of a VLM, and showed that web knowledge transferred to robot control: the robot could follow instructions involving objects and concepts absent from its robot data. OpenVLA (Kim et al. 2024), an open model with 7 billion parameters, combines a Llama 2 language model with DINOv2 and SigLIP visual features and was trained on 970,000 robot demonstrations pooled across many robots and labs. Such generalist policies are limited mainly by the scarcity of robot data, which is orders of magnitude smaller than the text and image data behind foundation models, and by the need for reliability far beyond that of a chatbot.
27.9Implementation
Value iteration and policy iteration on a grid world with slippery moves, and the LQR controller of a cart (double integrator) computed by iterating the Riccati recursion to its fixed point:
import numpy as np
# ---- A 4x4 grid world with a known model: reach the goal (+1) and avoid the pit (-1) ----
n, gamma, slip = 4, 0.95, 0.1
S, A = n * n, 4 # actions: up, right, down, left
goal, pit = 15, 5
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
P = np.zeros((A, S, S)); R = np.full(S, -0.04) # small cost per step
R[goal], R[pit] = 1.0, -1.0
for s in range(S):
for a in range(A):
if s in (goal, pit):
P[a, s, s] = 1.0; continue # terminal states absorb
for b, p in [(a, 1 - 2 * slip), ((a + 1) % 4, slip), ((a + 3) % 4, slip)]: # slips sideways
r, c = divmod(s, n); dr, dc = moves[b]
r2, c2 = min(max(r + dr, 0), n - 1), min(max(c + dc, 0), n - 1)
P[a, s, r2 * n + c2] += p
R_term = R.copy(); R_term[[goal, pit]] = R[[goal, pit]] / (1 - gamma) # value of absorbing terminals
def value_iteration(tol=1e-8):
V, it = np.zeros(S), 0
while True:
Q = R[None, :] + gamma * P @ V # (A, S): Bellman backup, Eq. (27.4)
V_new = Q.max(0); V_new[[goal, pit]] = R_term[[goal, pit]]
it += 1
if np.max(np.abs(V_new - V)) < tol:
return V_new, Q.argmax(0), it
V = V_new
def policy_iteration():
pi, it = np.zeros(S, int), 0
while True:
P_pi = P[pi, np.arange(S)] # (S, S) transitions under pi
V = np.linalg.solve(np.eye(S) - gamma * P_pi, R) # exact policy evaluation
V[[goal, pit]] = R_term[[goal, pit]]
pi_new = (R[None, :] + gamma * P @ V).argmax(0) # greedy improvement
it += 1
if np.array_equal(pi_new, pi):
return V, pi, it
pi = pi_new
V1, pi1, it1 = value_iteration()
V2, pi2, it2 = policy_iteration()
arrows = np.array(list("^>v<"))[pi1].reshape(n, n); arrows.flat[goal], arrows.flat[pit] = "G", "X"
print(f"value iteration: {it1} sweeps; policy iteration: {it2} improvements; "
f"max |V_VI - V_PI| = {np.max(np.abs(V1 - V2)):.1e}")
print("\n".join(" ".join(row) for row in arrows))
# ---- LQR for a double integrator: state (position, velocity), action = acceleration ----
dt = 0.1
Adyn = np.array([[1, dt], [0, 1]]); Bdyn = np.array([[0.5 * dt**2], [dt]])
U, W = np.diag([1.0, 0.1]), np.array([[0.5]]) # state and action costs
Pm = U.copy()
for _ in range(500): # Riccati recursion to a fixed point, Eq. (27.8)
K = np.linalg.solve(W + Bdyn.T @ Pm @ Bdyn, Bdyn.T @ Pm @ Adyn)
Pm = U + Adyn.T @ Pm @ (Adyn - Bdyn @ K)
s = np.array([5.0, 0.0]); cost = 0.0
for t in range(100): # closed loop a = -K s
a = -K @ s
cost += s @ U @ s + a @ W @ a
s = Adyn @ s + Bdyn @ a
print("LQR gain K =", np.round(K, 3), "| state after 10 s:", np.round(s, 4),
"| cost", round(cost, 2), "vs predicted s0' P s0 =", round(np.array([5., 0]) @ Pm @ np.array([5., 0]), 2))
Value iteration needs 38 sweeps to converge to $10^{-8}$, policy iteration only 5 improvements, and both give the same values (the policies differ only where two actions tie). The optimal policy detours around the pit. The LQR controller brings the cart from $x=5$ to rest at the origin, and the cost of the simulated trajectory equals the Riccati prediction $s_0\T\mathbf Ps_0$ exactly.
27.10Where the Field Is Heading
Reinforcement learning, after a period in which its biggest successes were in games, is now central to training language models that reason and act: as of late 2026, much research concerns stable large-scale RL on long reasoning traces and multi-step agent tasks, and learning from rewards that are sparse, delayed, or only partly verifiable. In robotics, the field is betting on scale: large cross-embodiment demonstration data sets, vision–language–action models, learned world models that support planning, and RL fine-tuning on top of imitation. Classical control remains indispensable wherever a good model exists, and the most capable systems combine learned perception and policies with model-based planning.
27.11Summary
- RL maximizes expected discounted return in an MDP; values satisfy Bellman equations, and a policy greedy with respect to $Q^*$ is optimal.
- With a known model, value iteration converges because the Bellman operator is a $\gamma$-contraction; policy iteration alternates exact evaluation and greedy improvement and terminates in few iterations.
- Fitted value iteration combines Bellman backups with regression for continuous states.
- LQR: linear dynamics and quadratic costs give a linear optimal policy $a=-\mK s$ from the Riccati recursion; iLQR/DDP and MPC extend it to nonlinear systems, and LQG adds a Kalman filter.
- Q-learning moves $Q(s,a)$ toward $r+\gamma\max_{a'}Q(s',a')$ while exploring; DQN adds a replay buffer and a target network.
- Policy gradients: $\nabla J=\E[\sum_t\nabla\log\pi(a_t\mid s_t)\,R]$; baselines reduce variance; PPO clips policy changes; LLM post-training is RL with tokens as actions.
- Robots learn from demonstrations (behavior cloning, DAgger, diffusion policies), simulation with domain randomization, world models, and vision–language–action models.
27.12Exercises
- MathIn a deterministic chain of 4 states where only reaching the last state gives reward 1, compute $V^*$ for each state with $\gamma=0.9$, by hand with value iteration.
- MathComplete the proof of Equation (27.5), including the inequality $|\max_af(a)-\max_ag(a)|\le\max_a|f(a)-g(a)|$, and conclude that value iteration needs about $\log(\epsilon_0/\epsilon)/\log(1/\gamma)$ sweeps to reduce the error from $\epsilon_0$ to $\epsilon$.
- MathDerive the Riccati recursion Equation (27.8) by minimizing $s\T\mathbf Us+a\T\mW a+(\mA s+\mB a)\T\mathbf P_{t+1}(\mA s+\mB a)$ over $a$. Show that adding zero-mean noise $w_t$ with covariance $\bm\Sigma_w$ adds $\tr(\mathbf P_{t+1}\bm\Sigma_w)$ to the cost-to-go but does not change $\mK_t$.
- MathProve that subtracting a baseline $b(s)$ does not change the expected policy gradient.
- MathFor a one-step problem (a bandit) with two actions and a softmax policy over logits $(\theta_1,\theta_2)$, write the REINFORCE gradient explicitly and show that it increases the probability of the action with higher expected reward.
- CodingImplement tabular Q-learning on the cliff-walking grid of the
gridworld-qwidget (4$\times$12 cells). Plot the return per episode for $\epsilon=0.01,0.1,0.3$. Which learns the safest path and which the shortest? - CodingCompare behavior cloning and DAgger on a toy problem: an expert steers a point along a line to the origin with $a=-0.5x$; the learner is a linear policy fitted to noisy demonstrations and executed with small action noise. Plot the final distance from the origin against the number of demonstrations for both methods.