# Reinforcement learning: a synthesis

Draft. A working note, started 2026-10-25 and meant to be edited. Numbers quoted here come from scripts/check-rl-notes.cjs.

This note keeps the spine of reinforcement learning (RL) in one place with one notation, from the Bellman equation to GRPO, and it says how much of each claim I have actually checked. The story told with figures is the essay [Deriving Reinforcement Learning from the Bellman Equation](../posts/rl-derived.html); this note is the longer, flatter version I want to be able to look things up in. ## 0. How to use this note **Status tags.** A result carries one of three tags, and an untagged sentence is exposition. - derived I derived it in the text or checked it numerically on the café MDP below, and the check is in `scripts/check-rl-notes.cjs`. - cited The statement matches a source's abstract or its own statement of the result, which I read; the link is in the reading list. For paywalled papers this means the abstract and bibliographic record, not the full text. - recalled From memory of the literature. Treat as a pointer to verify, not as a fact. A boxed **check** is a numerical confirmation. A boxed **question** is something I do not yet understand. **One running example.** A café is Quiet or Busy; each period you *Serve* or *Prepare*. | State, action | Pays now | Next: Quiet | Next: Busy | | --- | --- | --- | --- | | Quiet, Serve | 0.3 | 0.9 | 0.1 | | Quiet, Prepare | 0 | 0.2 | 0.8 | | Busy, Serve | 1 | 0.7 | 0.3 | | Busy, Prepare | 0 | 0.1 | 0.9 | With $\gamma=0.9$ and a start that is Quiet or Busy with equal chance, the four deterministic policies are worth: | Policy (Quiet, Busy) | $V(\text{Quiet})$ | $V(\text{Busy})$ | $J$ | | --- | --- | --- | --- | | Serve, Serve | 3.77 | 4.62 | 4.20 | | Serve, Prepare | 2.04 | 0.96 | 1.50 | | Prepare, Serve | **4.97** | **5.66** | **5.31** | | Prepare, Prepare | 0 | 0 | 0 | **Notation.** | Symbol | Meaning | | --- | --- | | $S,A$ | finite state and action sets (general spaces are discussed in Chapter 2) | | $P(s'\mid s,a)$, $r(s,a)$, $\gamma$ | transition kernel, expected reward, discount factor in $[0,1)$ | | $\mu$ | initial state distribution | | $\pi(a\mid s)$ | a (stationary) policy; $b$ is a *behaviour* policy that generated data | | $V^\pi,Q^\pi,A^\pi$ | value, action value, advantage; $V^\star,Q^\star$ for the optimum | | $J(\pi)$ | $\mathbb E_{s\sim\mu}V^\pi(s)$, the objective | | $\mathcal T^\pi,\mathcal T$ | Bellman expectation and optimality operators | | $d^\pi(s,a)$ | normalised discounted occupancy; $d^\pi(s)=\sum_a d^\pi(s,a)$ | | $\theta,w$ | policy and value parameters; $\phi(s)$ features | | $\delta_t$ | temporal-difference error $r_t+\gamma V(s_{t+1})-V(s_t)$ | | $\rho(s)$ | state occupancy (flow equations); $\varrho_t$ is the policy ratio $\pi_\theta/\pi_{\text{old}}$ | | $m_a,\hat m_a$ | arm mean and its estimate (bandits) | | $\beta$ | KL coefficient (language-model chapters), never a behaviour policy | | $\lVert\cdot\rVert_\infty$ | max norm over states (or state-action pairs) | A few symbols ($\alpha,\epsilon,w,D,T$) keep their conventional meaning in several chapters; each chapter says which is intended. **Map.** | Part | Chapters | Question | | --- | --- | --- | | Foundations | 1–3 | What is the problem, and what do Bellman equations say? | | Planning | 4–6 | If the model is known, how do we solve it, and what is the geometry? | | Learning from samples | 7–10 | How do we estimate values and explore, in the tabular case? | | Approximation | 11–15 | What breaks when states are too many to enumerate? | | Other settings | 16–20 | Offline data, demonstrations and preferences, language models, games, constraints | | Synthesis | 21–24 | One map, open questions, exercises, reading | ## 1. The problem Supervised learning is given examples of the right answer. RL is given only a score, after the fact, for what it did. Four things follow, and each is the source of a whole subfield. 1. **Feedback is evaluative.** You learn how good an action was, not which action was best. Finding better actions requires trying them: *exploration*. 2. **Consequences are delayed.** A reward may arrive many steps after the action that caused it: *credit assignment*, which the Bellman equation turns into a recursion. 3. **Actions change the data.** The distribution of states the learner sees depends on its own policy, so data are neither independent nor stationary: *off-policy* learning, *distribution shift*. 4. **The objective is a distribution over futures.** The quantity to optimise is an expectation over trajectories that the policy itself shapes. ### The interaction loop At each step the agent observes a state $s_t$, draws an action $a_t\sim\pi(\cdot\mid s_t)$, receives a reward $r_t$ and the environment moves to $s_{t+1}\sim P(\cdot\mid s_t,a_t)$. The return is $G_t=\sum_{k\ge0}\gamma^kr_{t+k}$. ### Axes that organise the field Most of RL's vocabulary is a coordinate on one of these axes. | Axis | Options | | --- | --- | | What is known | Model known (*planning*) or unknown (*learning*) | | Where data come from | Online interaction; a fixed dataset (*offline*); a simulator or generative model that can be queried anywhere | | Whose policy collected the data | The one being evaluated (*on-policy*) or another (*off-policy*) | | What is learned | Values, a policy, a model, or a combination | | Horizon | Discounted, finite-horizon, average-reward, episodic with absorbing end | | State | Tabular, linear features, neural; fully or partially observed | | Reward | Given as a number; learned from demonstrations or preferences; checked by a verifier | | Agents | One, or several interacting | ### Three kinds of guarantee Papers claim one of three things, and they are different. - **Convergence:** the iterates reach the right answer in the limit (Q-learning, TD). - **Sample complexity (PAC):** how many samples until a policy within $\epsilon$ of optimal with probability $1-\delta$. - **Regret:** the total reward lost by learning online, $\sum_t(J^\star-J(\pi_t))$, which also charges for exploring. ## 2. Markov decision processes ### Definition A finite discounted MDP is $(S,A,P,r,\gamma,\mu)$ with the assumptions below. Each is used later, and the places that break are the interesting ones. 1. **Finite $S$ and $A$.** Relaxed in Chapters 11–15. 2. **Markov.** $\Pr(s_{t+1}\mid s_{0:t},a_{0:t})=P(s_{t+1}\mid s_t,a_t)$. 3. **Stationary.** $P$ and $r$ do not depend on $t$. 4. **Bounded rewards.** $|r|\le r_{\max}$, so $\lVert V\rVert_\infty\le r_{\max}/(1-\gamma)$. 5. **Discounting.** $\gamma<1$. 6. **Full-support start**, $\mu(s)>0$, whenever a result needs every state to have positive mass. A policy and an MDP together define a distribution over trajectories, and $J(\pi)=\mathbb E_\pi[\sum_t\gamma^tr_t]$. ### The discount is a survival probability Let a clock stop the process after each step with probability $1-\gamma$. The stopping time $T$ is geometric, $\Pr(T=t)=(1-\gamma)\gamma^t$, with mean $\gamma/(1-\gamma)$ additional steps, and $\mathbb E[\sum_{t\le T}r_t]=\sum_t\gamma^t\mathbb E[r_t]$. So discounted RL is undiscounted RL on a process that dies at a geometric time, and $1/(1-\gamma)$ is the *effective horizon*. For $\gamma=0.9$ it is 10 steps, and a reward 44 steps away is worth under 1% of one now. derived ### What kinds of policy are enough A *history-dependent randomised* policy chooses $a_t$ from the whole past. A *Markov* policy uses only $(s_t,t)$. A *stationary* policy uses only $s_t$. Since history-dependent policies include the others, one might expect them to be strictly more powerful. They are not, for discounted objectives. > **Fact.** For any history-dependent policy $\pi$ there is a stationary randomised policy $\pi'$ with the same discounted occupancy $d$, hence the same $J$. derived *Sketch.* Let $d(s,a)=(1-\gamma)\sum_t\gamma^t\Pr_\pi(s_t=s,a_t=a)$. For any policy, $\Pr(s_{t+1}=s')=\sum_{s,a}\Pr(s_t=s,a_t=a)P(s'\mid s,a)$, because only the environment's dynamics enter. Multiplying by $(1-\gamma)\gamma^{t+1}$ and summing gives the **flow constraint** (Chapter 5), which therefore holds for every policy's occupancy. Every point satisfying the flow constraint is the occupancy of some stationary policy (Chapter 5), so $\pi'(a\mid s)=d(s,a)/\sum_{a'}d(s,a')$ reproduces $d$. $\square$ So memory buys nothing in a known MDP. It buys a lot under partial observability, below. ### Other objectives - **Finite horizon $H$.** Rewards stop at $H$. Optimal policies depend on the time remaining. One recovers a stationary problem by adding the time index to the state. Many regret bounds are stated for this setting with $H$ the horizon. - **Average reward.** Maximise $\lim_{T\to\infty}\frac1T\mathbb E\sum_{trecalled A standard Abelian result; the check below confirms it numerically for one policy. - **Stochastic shortest path.** Episodic with an absorbing goal; discounting is optional. ### Beyond the finite case - **Continuous states and actions.** Same equations with integrals, plus measure-theoretic care: measurable policies, bounded measurable value functions, and (for existence of optimal policies) compactness or other regularity of $A$. recalled - **Partial observability.** In a POMDP the agent sees observations $o_t$, not states. The belief $b_t=\Pr(s_t\mid o_{1:t},a_{1:t-1})$ is a sufficient statistic, and the *belief MDP* is a fully observed MDP over the continuous simplex of beliefs. This is where memory (recurrent policies, transformers over histories) is genuinely needed. recalled - **Special cases.** A **bandit** is $|S|=1$; a **contextual bandit** has states drawn independently of actions; **one-step** problems like a language-model completion have horizon 1 (Chapter 18). ## 3. Value functions and the Bellman equations ### Definitions $$ \begin{gathered} V^\pi(s)=\mathbb E_\pi\Big[\sum_{t\ge0}\gamma^tr_t\ \Big|\ s_0=s\Big],\\ Q^\pi(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s'), \end{gathered} $$ and the **advantage** $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$. Averaging $A^\pi$ under $\pi$ gives zero: $\sum_a\pi(a\mid s)A^\pi(s,a)=0$. ### The Bellman expectation equation Peeling off the first step: $$ V^\pi(s)=\sum_a\pi(a\mid s)\Big[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')\Big]. $$ In vector form $V^\pi=r_\pi+\gamma P_\pi V^\pi$, with $(P_\pi)_{ss'}=\sum_a\pi(a\mid s)P(s'\mid s,a)$. The operator $\mathcal T^\pi V=r_\pi+\gamma P_\pi V$ is affine, so $$ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi=\sum_{t\ge0}\gamma^tP_\pi^t\,r_\pi . $$ The inverse exists because $P_\pi$ is stochastic, so its spectral radius is 1 and that of $\gamma P_\pi$ is $\gamma<1$. derived The series on the right is the discounted sum over time written as matrix powers; the fixed point is the same object seen as an equation. ### The Bellman optimality equation $$ V^\star(s)=\max_a\Big[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\star(s')\Big]. $$ Write $\mathcal T V$ for the right-hand side as a function of $V$. ### Operators: monotone and contracting Both $\mathcal T^\pi$ and $\mathcal T$ are **monotone** ($V\le W\Rightarrow\mathcal TV\le\mathcal TW$) and $\gamma$-**contractions** in $\lVert\cdot\rVert_\infty$: $$ \lVert\mathcal TV-\mathcal TW\rVert_\infty\le\gamma\lVert V-W\rVert_\infty. $$ derived *Proof.* For fixed $(s,a)$ the two brackets differ by $\gamma\sum_{s'}P(s'\mid s,a)(V-W)(s')$, at most $\gamma\lVert V-W\rVert_\infty$ in absolute value because $P(\cdot\mid s,a)$ is a probability vector. And $\lvert\max_ax_a-\max_ay_a\rvert\le\max_a\lvert x_a-y_a\rvert$. $\square$ By Banach's fixed-point theorem each operator has a unique fixed point ($V^\pi$ and $V^\star$), and $\mathcal T^kV_0\to$ it at rate $\gamma^k$: $$ \lVert\mathcal T^kV_0-V^\star\rVert_\infty\le\gamma^k\lVert V_0-V^\star\rVert_\infty . $$ Two practical consequences are worth keeping: **Residual bound.** $\lVert V-V^\star\rVert_\infty\le\dfrac{\lVert\mathcal TV-V\rVert_\infty}{1-\gamma}$, since $\lVert V-V^\star\rVert\le\lVert V-\mathcal TV\rVert+\lVert\mathcal TV-\mathcal TV^\star\rVert\le\lVert V-\mathcal TV\rVert+\gamma\lVert V-V^\star\rVert$. A small Bellman residual means a small error, with a $1/(1-\gamma)$ blow-up. derived **Greedy policy loss.** If $\pi$ is greedy with respect to $V$, then $\lVert V^\pi-V^\star\rVert_\infty\le\dfrac{2\gamma}{1-\gamma}\lVert V-V^\star\rVert_\infty$. derived *Proof.* Greedy means $\mathcal T^\pi V=\mathcal TV$. Then $\lVert V^\pi-\mathcal TV\rVert=\lVert\mathcal T^\pi V^\pi-\mathcal T^\pi V\rVert\le\gamma\lVert V^\pi-V\rVert\le\gamma(\lVert V^\pi-V^\star\rVert+\lVert V^\star-V\rVert)$, and $\lVert\mathcal TV-V^\star\rVert\le\gamma\lVert V-V^\star\rVert$. Adding, $\lVert V^\pi-V^\star\rVert\le\gamma\lVert V^\pi-V^\star\rVert+2\gamma\lVert V-V^\star\rVert$. $\square$ An optimal policy is any policy greedy with respect to $V^\star$, since then $\mathcal T^\pi V^\star=V^\star$ and uniqueness gives $V^\pi=V^\star$. It can be taken deterministic and stationary. derived ### The performance difference lemma This is the identity most proofs in policy optimisation start from. For two policies $\pi,\pi'$ and any start state $s$, $$ V^{\pi'}(s)-V^\pi(s)=\frac{1}{1-\gamma}\sum_{s',a}d^{\pi'}_s(s',a)\,A^\pi(s',a), $$ where $d^{\pi'}_s$ is the discounted occupancy of $\pi'$ started at $s$. derived Averaging over $s\sim\mu$ gives $J(\pi')-J(\pi)=\frac1{1-\gamma}\langle d^{\pi'},A^\pi\rangle$. *Proof.* Along a trajectory of $\pi'$, telescope $V^\pi$: $V^\pi(s_0)=\sum_{t\ge0}\gamma^t\big(V^\pi(s_t)-\gamma V^\pi(s_{t+1})\big)$, valid because $V^\pi$ is bounded and $\gamma^tV^\pi(s_t)\to0$. Subtract it from the return $\sum_t\gamma^tr_t$: $$ \sum_t\gamma^tr_t-V^\pi(s_0)=\sum_t\gamma^t\big(r_t+\gamma V^\pi(s_{t+1})-V^\pi(s_t)\big). $$ Take expectations under $\pi'$. Conditioning on $(s_t,a_t)$ turns $r_t+\gamma V^\pi(s_{t+1})$ into $Q^\pi(s_t,a_t)$, so each term has expectation $\gamma^t\mathbb E[A^\pi(s_t,a_t)]$. Summing and normalising by $1-\gamma$ gives occupancy. $\square$ Three corollaries are used constantly: - **Policy improvement.** If $\sum_a\pi'(a\mid s)A^\pi(s,a)\ge0$ for every $s$, then $V^{\pi'}\ge V^\pi$ (the occupancy weights are nonnegative). Acting greedily on $Q^\pi$ is a special case. - **Optimality criterion.** $\pi$ is optimal iff $A^\pi(s,a)\le0$ for all $(s,a)$ (take $\pi'$ to be any alternative). - **Gradient domination ingredients.** The occupancy under the *new* policy appears on the right, which is why local progress measured under the old policy needs a bound on how far the two occupancies drift (Chapters 13, 15). ### Where this note goes next The Bellman equation says what an answer *is*. Chapter 4 computes it when the model is known; Chapter 5 re-reads it as a linear program over occupancies, which is the geometry that organises the rest; Chapters 7–10 replace the known model by samples. ## 4. Dynamic programming: planning with a known model When $P$ and $r$ are known, finding $V^\star$ is a computation, not a learning problem. The algorithms are the template that every learning algorithm approximates. ### Policy evaluation Solving $V^\pi=(I-\gamma P_\pi)^{-1}r_\pi$ directly costs $O(|S|^3)$. Iterating $V\leftarrow\mathcal T^\pi V$ converges at rate $\gamma$ per sweep and costs $O(|S|^2)$ per sweep. Gauss–Seidel sweeps (use updated values immediately) and asynchronous updates also converge: the sup-norm contraction still holds so long as every state keeps being updated. recalled ### Value iteration $V_{k+1}=\mathcal TV_k$. The error shrinks like $\gamma^k$, so reaching accuracy $\epsilon$ takes about $\log(1/\epsilon)/\log(1/\gamma)\approx\log(1/\epsilon)/(1-\gamma)$ sweeps. Each sweep costs $O(|S|^2|A|)$ for dense $P$. **When to stop.** The Bellman residual $\lVert\mathcal TV-V\rVert_\infty$ is computable without knowing $V^\star$, and by Chapter 3 it controls the error. If $\pi$ is greedy for $V$, then $V^\pi$ is a fixed point of $\mathcal T^\pi$ and $\mathcal T^\pi V=\mathcal TV$, so $\lVert V-V^\pi\rVert\le\lVert\mathcal TV-V\rVert/(1-\gamma)$, and $$ \lVert V^\pi-V^\star\rVert_\infty\le\frac{2\,\lVert\mathcal TV-V\rVert_\infty}{1-\gamma}. $$ derived A residual below $\epsilon(1-\gamma)/2$ therefore certifies an $\epsilon$-optimal greedy policy. (Sharper forms with a factor $\gamma$ in the numerator exist. recalled) ### Policy iteration Alternate *evaluate* ($V^{\pi_k}$) and *improve* ($\pi_{k+1}$ greedy for $Q^{\pi_k}$). - **Monotone.** By the performance difference lemma the greedy step has nonnegative advantage in every state, so $V^{\pi_{k+1}}\ge V^{\pi_k}$. derived - **Finite.** There are $|A|^{|S|}$ deterministic policies, values strictly increase until optimal, so it terminates. - **At least as fast as value iteration.** Because $\mathcal T^{\pi_{k+1}}V^{\pi_k}=\mathcal TV^{\pi_k}\ge V^{\pi_k}$, monotonicity gives $V^{\pi_{k+1}}\ge\mathcal TV^{\pi_k}$. Hence $0\le V^\star-V^{\pi_{k+1}}\le V^\star-\mathcal TV^{\pi_k}\le\gamma\lVert V^\star-V^{\pi_k}\rVert_\infty$. derived - **Often far faster.** Policy iteration is Newton's method applied to the Bellman residual equation $\mathcal TV-V=0$, which explains its local quadratic behaviour. recalled **How many rounds?** No more than $|A|^{|S|}$ trivially. For a fixed discount factor, Howard's policy iteration and the simplex method with Dantzig's rule are strongly polynomial (Ye, 2011). cited With $n=|S|$ states and $m$ state-action pairs in total, the bound for Dantzig's simplex is of order $\frac{mn}{1-\gamma}\log\frac{n^2}{1-\gamma}$, and the bound for Howard's policy iteration was later improved to order $\frac m{1-\gamma}\log\frac n{1-\gamma}$ (Hansen, Miltersen and Zwick, 2013), which I am quoting from memory. recalled The same line of work extends to two-player games. recalled Without a fixed discount factor (undiscounted problems) policy iteration can take exponentially many rounds on constructed instances. recalled ### In between: modified policy iteration Evaluate the policy only approximately, with $m$ sweeps of $\mathcal T^\pi$, instead of exactly. $m=1$ is value iteration; $m=\infty$ is policy iteration; both converge for every $m$. recalled Most practical algorithms (n-step bootstrapping, GAE, fitted value iteration) live on this dial. ### The wall Every method above stores a table over $S$ and sweeps all of it. The number of states of a realistic problem grows exponentially in the number of variables (Bellman's *curse of dimensionality*), which is why the rest of the note replaces tables with samples and functions. recalled ## 5. Occupancy, the dual LP and the polytope This chapter reorganises Chapter 3 around a different unknown: not how good each state is, but how much (discounted) time the agent spends in each state-action pair. It is the geometry the rest of the note refers back to. The essay has it with figures. ### Occupancy measures $$ \begin{gathered} d^\pi(s,a)=(1-\gamma)\sum_{t\ge0}\gamma^t\Pr_\pi(s_t=s,a_t=a)\\ \Big(\textstyle\sum_{s,a}d^\pi(s,a)=1\Big). \end{gathered} $$ It is the law of $(s_T,a_T)$ at the geometric stopping time $T$. Because $\Pr(T\ge t)=\gamma^t$, the expected reward at that moment is $\mathbb E[r_T]=\langle d^\pi,r\rangle=(1-\gamma)J(\pi)$, so $$ J(\pi)=\frac1{1-\gamma}\langle d^\pi,r\rangle . $$ This is the sum $\sum_t\gamma^t\mathbb E[r_t]$ regrouped by *place* instead of by *time*. The objective is linear in $d$. ### The flow constraint For every state $s'$, $$ \sum_a d(s',a)=(1-\gamma)\mu(s')+\gamma\sum_{s,a}P(s'\mid s,a)\,d(s,a). $$ *Derivation.* $\Pr(s_{t+1}=s')=\sum_{s,a}\Pr(s_t=s,a_t=a)P(s'\mid s,a)$. Multiply by $(1-\gamma)\gamma^{t+1}$, sum over $t\ge0$, and add the $t=0$ term $(1-\gamma)\mu(s')$. $\square$ derived Equivalently, $d^\pi$ is the stationary law of the chain that follows $\pi$ and, with probability $1-\gamma$ at every step, restarts from $\mu$. This is the same fact as the geometric clock: in a long run of "play until the clock stops, then restart," the fraction of time spent in $(s,a)$ is $d(s,a)$. derived ### The primal and dual linear programs The optimality equation says $V^\star$ is the smallest $V$ with $V\ge\mathcal TV$. That is a linear program (Manne, 1960): cited $$ \begin{gathered} \min_V\ (1-\gamma)\langle\mu,V\rangle\\ \text{subject to}\quad V(s)\ge r(s,a)\\ +\gamma\sum_{s'}P(s'\mid s,a)V(s')\quad\forall(s,a). \end{gathered} $$ Feasibility means $V\ge\mathcal TV$; applying the monotone operator $\mathcal T$ repeatedly gives $V\ge\mathcal T^kV\to V^\star$, so every feasible point dominates $V^\star$ and the positive weighting $\mu$ selects it exactly. derived Attach multipliers $d(s,a)\ge0$ to the constraints. The Lagrangian is $(1-\gamma)\langle\mu,V\rangle+\sum_{s,a}d(s,a)[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')-V(s)]$. It is bounded below in the free variable $V$ only if the coefficient of every $V(s')$ vanishes, which is the flow constraint, and then equals $\langle d,r\rangle$. So the dual is: $$ \begin{gathered} \max_{d\ge0}\ \langle d,r\rangle\\ \text{subject to the flow constraints.} \end{gathered} $$ Strong duality (both programs are feasible and bounded) gives $\langle d^\star,r\rangle=(1-\gamma)\langle\mu,V^\star\rangle$. derived ### What duality says - **Values are prices.** $V(s)$ is the multiplier of the flow constraint at $s$: how much the objective changes per unit of mass pushed into that state. - **Complementary slackness is the optimality condition.** Define $A^\star(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\star(s')-V^\star(s)\le0$. Then $d^\star(s,a)\,A^\star(s,a)=0$: an optimal agent spends time only on actions with zero advantage. derived - **Reduced costs are advantages.** In the dual, a basis is a deterministic policy, and the reduced cost of the column $(s,a)$ is $A^\pi(s,a)$. A pivot that enters an action with positive advantage and removes the old action in that state is a one-state policy improvement. *Simplex on the dual is policy improvement, one state at a time; policy iteration is the same method with a block pivot over all improving states at once.* derived ### The state-action polytope Let $\mathcal D=\{d\ge0:\ \text{flow constraints}\}$. 1. **Every policy is a point.** $d^\pi\in\mathcal D$ for any stationary $\pi$ (and for any history-dependent one, as in Chapter 2). 2. **Every point is a policy.** For $d\in\mathcal D$ put $\pi_d(a\mid s)=d(s,a)/\sum_{a'}d(s,a')$. For a fixed policy the flow equations $(I-\gamma P_\pi^\top)\rho=(1-\gamma)\mu$ have the unique solution $\rho^\pi$ because $I-\gamma P_\pi^\top$ is invertible, and $d$ solves them for $\pi_d$. So $d=d^{\pi_d}$. derived 3. **The corners are the deterministic policies.** Summing the flow constraint over $s'$ shows every state has mass $\ge(1-\gamma)\mu(s)>0$. A vertex has at most $|S|$ nonzero coordinates because there are $|S|$ independent equations, and each state needs at least one. So it has exactly one action per state. Conversely, the columns of a deterministic policy's support are linearly independent (they are a basis for the flow equations), so it is a vertex. derived Hence a linear objective is optimised at a corner: **a deterministic stationary policy is optimal**, now from geometry. The dimension is $|S|(|A|-1)$. Corners whose policies differ in exactly one state's action are joined by an edge (the converse need not hold in larger problems). ### Variations on the linear program Most extensions of the standard problem are small changes to this program. - **Average reward.** Replace the flow with stationarity: $\sum_ad(s',a)=\sum_{s,a}P(s'\mid s,a)d(s,a)$ and $\sum d=1$. The value is the gain $g$ and the multipliers become a bias function $h$ solving the Poisson equation $g+h(s)=r_\pi(s)+\sum_{s'}P_\pi(s,s')h(s')$. recalled - **Finite horizon.** Use one occupancy per time step; the flow constraints chain consecutive steps. The program has $H|S||A|$ variables. - **Constrained MDPs.** Add $m$ linear constraints $\langle d,c_i\rangle\le b_i$ (a cost budget, a safety limit, a resource). The feasible set is the polytope cut by half-spaces; the optimum is a vertex of the *intersection*, which is generally not a corner of $\mathcal D$. Consequently an optimal policy may need to be **randomised**, in at most $m$ states. recalled (Altman's monograph.) The numerical case below confirms the mechanism. - **Convex RL.** If the objective is a concave function $f(d)$ rather than $\langle d,r\rangle$ (maximise state-visitation entropy for exploration, match an expert's occupancy for imitation) the problem is still convex *in $d$*, but the Bellman operator no longer solves it and optimal policies are generally stochastic. recalled - **Entropy regularisation** makes the program strictly concave and replaces the max in the optimality equation by a log-sum-exp (Chapter 13). ### Duality as an algorithm If the LP is too large, one can run a saddle-point method on the Lagrangian: ascent in $d$ and descent in $V$, with samples replacing the sums. These primal-dual methods, and the *DICE* family that estimates occupancy ratios $d^\pi/d^b$ from data, rest on the Fenchel–Rockafellar view of this program (Nachum and Dai, 2020). cited The *approximate LP* of de Farias and Van Roy (2003) restricts $V$ to a span of features and keeps the constraints, giving error bounds that depend on the weighting of states. cited ## 6. Probability tools A short kit that later chapters call by name. ### Markov chains A chain with kernel $P_\pi$ on a finite set has a stationary distribution $\nu$ with $\nu P_\pi=\nu$, unique if the chain is irreducible. If it is also aperiodic, the distribution at time $t$ converges to $\nu$ geometrically with rate set by the second-largest eigenvalue modulus $|\lambda_2|$, and the *mixing time* is of order $1/(1-|\lambda_2|)$. For the coin-flip policy on the café $\lambda_2=0.15$, so the chain forgets its start in a couple of steps while the discount has an effective horizon of 10. These are different clocks: mixing is a property of the dynamics, the effective horizon of the objective. derived ### Concentration For independent $X_i\in[0,1]$ with mean $m_X$, **Hoeffding**: $\Pr(|\bar X_n-m_X|\ge\epsilon)\le2e^{-2n\epsilon^2}$. **Bernstein** replaces the range by the variance and wins when the variance is small. For dependent data, as in RL where the next state depends on the last action, the same bounds hold for martingale differences (**Azuma–Hoeffding**, **Freedman**). Almost every regret or sample-complexity bound in this note is a union bound over state-action pairs of one of these. recalled ### Importance sampling To estimate $\mathbb E_p[f]$ from samples of $q$: $\mathbb E_p[f]=\mathbb E_q[\frac pq f]$ when $q>0$ wherever $p>0$. The weights $p/q$ have mean 1; their variance grows with the mismatch, and the *effective sample size* is roughly $n/(1+\operatorname{Var}(p/q))$. Over a trajectory the weights multiply, $\prod_t\pi(a_t\mid s_t)/b(a_t\mid s_t)$, so the variance grows exponentially with the horizon (the "curse of horizon"). *Per-decision* importance sampling reduces it by weighting each reward only by the ratios up to its time; *occupancy-ratio* methods replace the product by a single ratio $d^\pi/d^b$. recalled ### Stochastic approximation Many learning algorithms have the form $x_{k+1}=x_k+\alpha_k\,(F(x_k)-x_k+M_{k+1})$, a fixed-point iteration with a noisy, unbiased evaluation. The Robbins–Monro conditions $\sum_k\alpha_k=\infty$, $\sum_k\alpha_k^2<\infty$ say the steps are large enough to travel anywhere and small enough that noise averages out. If $F$ is a contraction in a suitable norm (or the associated ODE $\dot x=F(x)-x$ has a globally stable equilibrium), and the noise is a martingale difference with bounded conditional variance, then $x_k\to x^\star$ almost surely. This is the engine behind the convergence of TD and Q-learning (Jaakkola, Jordan and Singh, 1994; Tsitsiklis, 1994). recalled With a constant step size the iterates do not converge but fluctuate in a neighbourhood of $x^\star$ of size related to $\sqrt\alpha$. ### Distances between distributions - **Total variation** $\mathrm{TV}(p,q)=\tfrac12\sum|p-q|$ equals the smallest probability of disagreement under any coupling of $p$ and $q$. That is how one bounds the chance two policies act differently (Chapter 13). - **KL divergence** $\mathrm{KL}(p\Vert q)=\sum p\log(p/q)\ge0$. **Pinsker:** $\mathrm{TV}\le\sqrt{\mathrm{KL}/2}$. So a KL budget is a TV budget. - **Fisher information** is the local metric $F=\mathbb E[\nabla\log p\,\nabla\log p^\top]$ induced by KL; natural gradient steps use $F^{-1}$. ## 7. Learning to predict: Monte Carlo and temporal difference Now $P$ and $r$ are unknown, and we only see transitions generated by acting. The first question is *prediction*: estimate $V^\pi$ for a fixed $\pi$ from trajectories of $\pi$. ### Monte Carlo Average the observed returns. After an episode, for each visited state, move toward the realised return: $$ V(s_t)\leftarrow V(s_t)+\alpha\,\big(G_t-V(s_t)\big). $$ $G_t$ is an unbiased sample of $V^\pi(s_t)$, so the estimate is unbiased, but a return adds up the randomness of every future step: its variance grows with the horizon, and one must wait until the episode ends. ### Temporal difference The Bellman equation says $V^\pi(s)=\mathbb E[r_t+\gamma V^\pi(s_{t+1})\mid s_t=s]$. Replace the unknown $V^\pi(s_{t+1})$ by the current estimate and use one sampled transition: $$ \delta_t=r_t+\gamma V(s_{t+1})-V(s_t),\qquad V(s_t)\leftarrow V(s_t)+\alpha\,\delta_t . $$ This is TD(0). In the language of Chapter 6 it is a **stochastic approximation of the fixed-point equation $V=\mathcal T^\pi V$**: the sampled backup $r_t+\gamma V(s_{t+1})$ is an unbiased estimate of $(\mathcal T^\pi V)(s_t)$, and averaging with a decaying step size drives $V$ to the fixed point. It *bootstraps*, updating a guess from a guess, so each update has low variance but is biased by the error of $V(s_{t+1})$. Tabular TD(0) converges almost surely to $V^\pi$ under Robbins–Monro step sizes if every state is visited infinitely often. recalled (Sutton, 1988 for the original; Jaakkola–Jordan–Singh and Tsitsiklis, 1994 for the stochastic-approximation proof.) ### n-step returns, $\lambda$-returns and eligibility traces Interpolate between the two with the **$n$-step return** $G_t^{(n)}=\sum_{krecalled The parameter $\lambda\in[0,1]$ tunes a bias-variance trade-off, and the same weighting returns in the advantage estimator of Chapter 13. derived there ### Batch TD and Monte Carlo disagree, and why TD usually wins Given a *fixed* batch of experience, repeatedly applying either update until convergence gives two different answers. Batch Monte Carlo converges to the value estimates that minimise squared error against the observed returns. Batch TD(0) converges to the solution of $V(s)=\hat r(s)+\gamma\sum_{s'}\hat P(s'\mid s)V(s')$ with $\hat P,\hat r$ the empirical transition frequencies and mean rewards: the value of the **maximum-likelihood model**, the *certainty-equivalence* estimate. derived in the text (At a fixed point, the sum of all TD errors observed in state $s$ vanishes, which is that equation.) TD therefore exploits the Markov structure that Monte Carlo ignores, which is why it tends to be more data-efficient when the Markov assumption holds. recalled ## 8. Learning to act: SARSA, Q-learning and friends ### Generalised policy iteration Control interleaves *evaluation* (make $Q$ closer to $Q^\pi$) with *improvement* (make $\pi$ greedier for $Q$). Almost every algorithm in this note is an instance, differing in how exactly each step is done and how data are gathered. Chapter 4's modified policy iteration is the exact version. ### SARSA On-policy TD control: after the tuple $(s,a,r,s',a')$, $$ Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma Q(s',a')-Q(s,a)\big]. $$ It learns $Q^\pi$ for the policy actually followed, including its exploration. Combined with a policy that becomes greedy in the limit while still visiting everything infinitely often (GLIE), it converges to $Q^\star$. recalled ### Q-learning Replace the sampled next action by the maximum: $$ Q(s,a)\leftarrow Q(s,a)+\alpha\Big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\Big]. $$ The target is a sample of the Bellman *optimality* backup, an unbiased estimate of $(\mathcal TQ)(s,a)$ for the state-action version of $\mathcal T$. It is therefore a stochastic approximation of the contraction $\mathcal T$ itself, and it learns $Q^\star$ **whatever policy generates the data**, provided every pair is updated infinitely often and the steps satisfy Robbins–Monro (Watkins and Dayan, 1992, the original, recalled; Tsitsiklis, 1994, the convergence proof, cited). This is what "off-policy" means: the behaviour policy and the target policy differ. **Rates.** The standard analyses give convergence, not a good rate. For synchronous Q-learning with a generative model, sharp analyses show that the vanilla algorithm needs about $(1-\gamma)^{-4}$ samples per pair and that this is tight, a factor $1/(1-\gamma)$ above the model-based minimax rate; variance-reduced variants close the gap. recalled (Wainwright 2019 and Li et al. 2021 are the places to check.) ### Expected SARSA Use the expectation over the target policy, $r+\gamma\sum_{a'}\pi(a'\mid s')Q(s',a')$. It has lower variance than SARSA and contains Q-learning as the case where $\pi$ is greedy. recalled ### Maximisation bias The target uses the maximum of *noisy estimates*, and $\mathbb E[\max_aX_a]\ge\max_a\mathbb E[X_a]$. If two actions both have true value $0$ and our estimates are independent $\mathcal N(0,1)$, then $\mathbb E[\max]=1/\sqrt\pi\approx0.564$. The overestimation is systematic and compounds through bootstrapping. derived **Double Q-learning** decouples *selection* from *evaluation*: pick $a^\star=\arg\max Q_1(s',\cdot)$ and score it with an independent estimate $Q_2(s',a^\star)$, whose conditional mean is the true value, so the bias vanishes in this example (van Hasselt, 2010). recalled ### On-policy versus off-policy, in one example In the classic cliff-walking task the greedy path hugs a cliff edge and the safe path stays far from it. SARSA, whose targets include its own $\varepsilon$-greedy mistakes, learns the safe path; Q-learning learns the optimal edge path and falls off while exploring. They estimate different things: $Q^{\pi_\varepsilon}$ versus $Q^\star$. recalled ### Multi-step off-policy corrections Using $n$-step returns with a behaviour policy $b$ introduces importance ratios $\pi(a_k\mid s_k)/b(a_k\mid s_k)$ whose product has exploding variance (Chapter 6). Fixes trade bias against variance: **tree backup** weights by $\pi$ instead (Precup et al., 2000); **Retrace($\lambda$)** truncates the ratios, $c_k=\lambda\min(1,\pi/b)$, so the operator is safe (a contraction for any $b$) and efficient (uses all of the data when $b$ is close to $\pi$) (Munos et al., 2016). recalled ## 9. Model-based reinforcement learning, tabular ### Certainty equivalence Estimate the model from counts, $\hat P(s'\mid s,a)=N(s,a,s')/N(s,a)$ and $\hat r$ as the empirical mean, then solve the *estimated* MDP exactly with Chapter 4 as if it were the truth. In the occupancy picture you have swapped the true polytope for an estimated one. ### The simulation lemma How far is the value in the estimated model from the truth? For any fixed policy, subtract the two Bellman equations: $$ \hat V^\pi-V^\pi=(I-\gamma\hat P_\pi)^{-1}\Big[(\hat r_\pi-r_\pi)+\gamma(\hat P_\pi-P_\pi)V^\pi\Big]. $$ derived *Proof.* $\hat V-V=\hat r+\gamma\hat P\hat V-r-\gamma PV=(\hat r-r)+\gamma(\hat P-P)V+\gamma\hat P(\hat V-V)$; solve for $\hat V-V$. $\square$ Since $\lVert(I-\gamma\hat P_\pi)^{-1}\rVert_\infty\le\frac1{1-\gamma}$, $$ \lVert\hat V^\pi-V^\pi\rVert_\infty\le\frac{\lVert\hat r_\pi-r_\pi\rVert_\infty+\gamma\lVert(\hat P_\pi-P_\pi)V^\pi\rVert_\infty}{1-\gamma}. $$ The crucial term is $(\hat P-P)V^\pi$: the model error matters only through how it changes the *value* of the next state. That is the idea behind **value-equivalent** models (Chapter 14): errors in directions the value function does not see are free. ### How many samples? Combining the lemma with Hoeffding and a union bound gives an error of order $\frac{r_{\max}}{(1-\gamma)^2}\sqrt{\log(SA/\delta)/N}$ per pair, which is crude. Using the variance of the value function (a *total variance* argument) improves the horizon dependence, and with a generative model the sample complexity of learning an $\epsilon$-accurate $Q^\star$ is $\Theta\big(SA\log(SA/\delta)/((1-\gamma)^3\epsilon^2)\big)$, matching upper and lower bounds in $S,A,\epsilon,\delta$ and $1-\gamma$ (Azar, Munos and Kappen, 2013). cited The original statement holds for small enough $\epsilon$, a restriction that later work relaxes. recalled The lower bound is a statement about *any* algorithm: no method beats it by more than constants in $S$, $A$, $\epsilon$ and $1-\gamma$. ### Dyna and prioritised sweeping A model can generate *simulated* experience. **Dyna** (Sutton, 1990) interleaves real updates with extra updates drawn from a learned model, so each real transition is reused many times; **prioritised sweeping** spends those extra updates on the states where the value is changing most. recalled ### A fair summary of model-based versus model-free Model-based methods tend to be more sample-efficient and can answer new questions with the same model (a different reward, a counterfactual), but they pay in computation and suffer **model bias**: a planner exploits the model's mistakes, and errors compound along imagined rollouts (Chapter 14). Model-free methods avoid modelling the world but throw away the structure that a model exploits. This is a statement about typical behaviour, not a theorem: in the tabular generative-model setting both families can reach the minimax rate when carefully designed. recalled ## 10. Exploration Estimates come from the data the agent itself collects. If it stops trying an action because early noise made it look bad, it never finds out. The cure costs reward in the short run, which is the **exploration–exploitation trade-off**, and the right quantity to study it by is regret. ### Bandits One state, $K$ arms with unknown means $m_a$. Regret after $T$ pulls is $R_T=\sum_t(m^\star-\mu_{a_t})$. - **Greedy and $\varepsilon$-greedy.** Greedy can lock onto a bad arm forever; a fixed $\varepsilon$ explores forever, so regret is linear. - **Lower bound.** For Bernoulli arms, any consistent algorithm must pull a suboptimal arm $a$ at least $(1-o(1))\ln T/\mathrm{KL}(m_a\Vertm^\star)$ times (Lai and Robbins, 1985). recalled For arms with means $0.55$ and $0.62$ the divergence is $\mathrm{KL}=0.0102$, so one needs about $98\ln T$ pulls of the worse arm to rule it out: roughly 900 at $T=10^4$. derived arithmetic, asymptotic statement recalled. - **Optimism (UCB1).** Pull the arm with the largest upper confidence bound $\hat m_a+\sqrt{2\ln N/n_a}$. The bound shrinks as an arm is pulled, so an arm is neglected only when it is confidently worse. Regret grows like $\sum_{a}\ln T/\Delta_a$, logarithmic in $T$ (Auer, Cesa-Bianchi and Fischer, 2002). cited - **Thompson sampling.** Sample a world from the posterior and act as if it were true; the probability of pulling an arm equals the probability it is the best. It matches the lower bound for Bernoulli arms (Agrawal and Goyal; Kaufmann et al., 2012). recalled The two principles reappear in every setting below: **optimism in the face of uncertainty**, and **posterior sampling**. In the occupancy picture, optimism means: *act as if the best plausible polytope were the true one* (see the essay). ### Exploration in MDPs In an MDP, being uncertain about a state is not only a question of the next reward but of what lies beyond it, and exploration must plan across steps ("deep exploration"). **Random exploration is exponentially slow.** In a chain of $N$ states where one action moves right and the other resets to the start, reaching the far end by uniformly random actions takes about $2^N$ attempts (episodes), since it needs $N$ consecutive right moves. derived Provably efficient algorithms add optimism to the planning step: - **R-max** treats poorly known state-action pairs as maximally rewarding until they have been visited enough times; **E$^3$** builds a model of the well-known states and plans either to exploit it or to reach the unknown ones (Brafman and Tennenholtz, 2002; Kearns and Singh, 2002). recalled - **UCRL2** plays the policy that is best in some MDP inside the confidence set around the empirical model, with regret $\tilde O(DS\sqrt{AT})$ for MDPs of diameter $D$ (Jaksch, Ortner and Auer, 2010). cited - **Optimistic value iteration** with a variance-aware bonus has regret $\tilde O(\sqrt{HSAT})$ in episodic problems of horizon $H$, once $T$ is large, close to the lower bound (Azar, Osband and Munos, 2017). cited - **Q-learning with an exploration bonus** reaches $\tilde O(\sqrt{H^3SAT})$ regret with a model-free update, within $\sqrt H$ of optimal (Jin et al., 2018). cited - **Posterior sampling for RL (PSRL)** samples an MDP from the posterior at the start of each episode and follows its optimal policy; it matches optimistic bounds without constructing confidence sets (Strens, 2000; Osband, Russo and Van Roy, 2013). recalled Bounds from different papers differ in whether the MDP is time-homogeneous, in how $T$ and $H$ are defined, and in lower-order terms, so a bound with $H^3$ in one and $H^2$ in another is not necessarily a better algorithm. ### Exploration with function approximation When the state space is too large to count visits, exploration needs a substitute for a count. - **Pseudo-counts** from a density model over states (Bellemare et al., 2016), **prediction-error bonuses** such as ICM and random network distillation (Pathak et al., 2017; Burda et al., 2019), **bootstrapped ensembles** that give randomised value functions and so deep exploration (Osband et al., 2016), and **return-to-frontier** methods like Go-Explore (Ecoffet et al., 2021). recalled - A known pitfall, the *noisy TV*: a prediction-error bonus rewards unpredictable but uninformative stimuli, so an agent can get stuck watching static. recalled ### Exploration as coverage Everything in this chapter is secretly about **coverage** of the part of the polytope that matters. An online algorithm explores until its data cover the occupancy of an optimal policy; *reward-free* exploration collects data once that cover every policy's occupancy well enough to plan for any reward later (Jin et al., 2020, recalled); *maximum-entropy exploration* maximises a concave function of $d$ directly (Chapter 5). The offline chapter (16) is the same story with the data fixed in advance. ## 11. Function approximation: linear first Tables do not scale. Replace $V(s)$ by a parametrised function and learn the parameters. With features $\phi(s)\in\mathbb R^d$ and weights $w$, write $V_w(s)=\phi(s)^\top w$, or $V_w=\Phi w$ with $\Phi\in\mathbb R^{|S|\times d}$. Linear analysis is where the theory is clean, and where the *failure modes* of deep RL first appear. ### Semi-gradient TD TD(0) with features updates $$ \begin{gathered} w\leftarrow w+\alpha\,\delta_t\,\phi(s_t),\\ \delta_t=r_t+\gamma\phi(s_{t+1})^\top w-\phi(s_t)^\top w . \end{gathered} $$ It is *not* the gradient of any objective: the target $r+\gamma V_w(s')$ depends on $w$ too, and the update ignores that (hence **semi**-gradient). In expectation, with $D=\operatorname{diag}(\text{state sampling distribution})$, $$ \begin{gathered} \mathbb E[\Delta w]=\alpha\,(b-Aw),\\ A=\Phi^\top D(I-\gamma P_\pi)\Phi,\quad b=\Phi^\top Dr_\pi . \end{gathered} $$ Its fixed point $Aw^\star=b$ is the **projected Bellman equation**: $\Phi w^\star=\Pi_D\mathcal T^\pi\Phi w^\star$, where $\Pi_D$ is the $D$-weighted least-squares projection onto the span of $\Phi$. TD does not minimise the value error or the Bellman error; it solves the fixed-point equation of *project after backing up*. derived ### On-policy convergence and its error bound If the sampling distribution is the stationary distribution $\nu$ of $P_\pi$ (this is "on-policy"), then $P_\pi$ is nonexpansive in $\lVert\cdot\rVert_D$ and $$ \begin{gathered} x^\top D(I-\gamma P_\pi)x\ \ge\ \lVert x\rVert_D^2-\gamma\lVert x\rVert_D\lVert P_\pi x\rVert_D\\ \ge\ (1-\gamma)\lVert x\rVert_D^2, \end{gathered} $$ so $A$ is positive definite, the mean ODE $\dot w=b-Aw$ is globally stable, and TD converges. derived (Tsitsiklis and Van Roy, 1997, give the stochastic-approximation argument.) recalled The limit satisfies $$ \lVert\Phi w^\star-V^\pi\rVert_D\ \le\ \frac1{\sqrt{1-\gamma^2}}\ \lVert\Pi_DV^\pi-V^\pi\rVert_D . $$ TD is within a factor $1/\sqrt{1-\gamma^2}$ of the *best possible* linear fit (Tsitsiklis and Van Roy, 1997). recalled The bound is confirmed numerically below. ### Off-policy: divergence If transitions are sampled from a distribution $D$ that is *not* stationary for $P_\pi$, $A$ can lose positive definiteness and the expected update can diverge. A two-state example: from Quiet go to Busy and from Busy stay in Busy, with zero reward, and features $\phi(\text{Quiet})=1$, $\phi(\text{Busy})=2$. The true values are $0$ and $w=0$ is exact, but the expected drift of $w$ is $\sum_sD(s)\phi(s)\big(\gamma\phi(s')-\phi(s)\big)w$. With the stationary weighting $D=(0,1)$ it is $-0.4\,w$ at $\gamma=0.9$ (convergence); with equal weights $D=(\tfrac12,\tfrac12)$ it is $+0.2\,w$ (**divergence**), and the threshold is $\gamma=5/6$. derived ### The deadly triad Function approximation, bootstrapping and off-policy data: the danger arises when all three are combined (Sutton and Barto, 2018, Chapter 11). Baird's seven-state counterexample (1995) diverges with exact features and equal weights. recalled Deep Q-learning has all three, and the practical stabilisers of Chapter 12 are ways of living with that. ### Remedies - **Gradient TD** (GTD2, TDC) follows the true gradient of the projected Bellman error with a second set of weights on a faster timescale, restoring convergence off-policy (Sutton et al., 2009). **Emphatic TD** reweights updates so the effective $A$ is positive definite (Sutton, Mahmood and White, 2016). recalled - **Residual gradient** minimises the squared Bellman error $\mathbb E[\delta^2]$. It is a genuine gradient method but, with a single sampled next state, $\mathbb E[\delta^2]=(\mathbb E\delta)^2+\operatorname{Var}(\delta)$ includes a spurious variance term (the *double-sampling* problem), so it is biased unless two independent next states are available. derived - **Least squares:** solve $Aw=b$ directly from sample averages. **LSTD** does this for prediction (Bradtke and Barto, 1996) and **LSPI** wraps it in policy iteration (Lagoudakis and Parr, 2003). recalled ### Fitted value iteration Replace the Bellman backup by *backup, then project*: $V_{k+1}=\Pi\mathcal TV_k$. $\mathcal T$ is a sup-norm contraction but $\Pi$ is not nonexpansive in sup norm in general, so the composition may fail to contract; it does for *averagers* (kernel smoothers, state aggregation), not for least-squares regression in general (Gordon, 1995). With sampled data, the error of fitted value or Q iteration after $K$ rounds is controlled by the per-round regression error, amplified by a concentrability coefficient and by $1/(1-\gamma)^2$ (Munos and Szepesvári, 2008). recalled The assumption that makes the induction go is **Bellman completeness**: if the function class $\mathcal F$ is closed under the backup, $\mathcal T\mathcal F\subseteq\mathcal F$. Realisability of $Q^\star$ alone is not enough (Chapter 15). ## 12. Deep value-based reinforcement learning Replace the linear $Q$ by a neural network $Q_\theta(s,a)$ and run Q-learning on minibatches. The raw version is unstable for the reasons above; the following ideas made it work on Atari. **DQN** (Mnih et al., 2015) minimises $$ \mathcal L(\theta)=\mathbb E_{(s,a,r,s')\sim\mathcal B}\Big[\big(r+\gamma\max_{a'}Q_{\theta^-}(s',a')-Q_\theta(s,a)\big)^2\Big] $$ with two stabilisers. A **replay buffer** $\mathcal B$ of past transitions makes minibatches closer to independent and reuses each transition, which also makes the data off-policy. A **target network** $\theta^-$, a delayed copy of $\theta$, turns each phase into a regression to a fixed target, cited (the two stabilisers) My reading is that the frozen target makes each phase approximate fitted Q-iteration with a few gradient steps per round; that is an interpretation, not a claim of the paper. **Variants that fix particular defects** (all recalled): - **Double DQN** (van Hasselt et al., 2016): select the action with the online network and evaluate it with the target network, to counter the maximisation bias of Chapter 8. - **Dueling networks** (Wang et al., 2016): $Q=V+(A-\overline A)$, which shares learning of the state value across actions. - **Prioritised replay** (Schaul et al., 2016): sample transitions in proportion to $|\delta|^\alpha$, with importance weights to correct the induced bias. - **Distributional RL.** Learn the distribution $Z(s,a)$ of the return rather than its mean. The distributional Bellman operator contracts in the maximal $p$-Wasserstein distance. C51 represents $Z$ on a fixed support (Bellemare, Dabney and Munos, 2017); QR-DQN and IQN learn quantiles (Dabney et al., 2018). The gain seems to come from richer learning signals, not from using the distribution at decision time. - **Rainbow** (Hessel et al., 2018) combines six such improvements; **R2D2** adds recurrence for partial observability; **Ape-X** scales with distributed actors. **Why it works is not settled.** The deadly triad is present, yet training is often stable. Candidates: a large replay buffer and slow target updates approximate a fixed-target regression; networks generalise across similar states in a way that is benign more often than not; careful tuning. When it does fail, one often sees overestimation spiralling upward, or the loss of a representation (Chapter 15). **Continuous actions.** The maximum over actions in the target is intractable for continuous $A$. Either discretise, or learn a separate policy that approximates the maximiser: the actor in an **actor–critic** method (Chapter 13). ## 13. Policy gradient methods ### Parametrise the policy Let $\pi_\theta(a\mid s)$ be a differentiable family and maximise $J(\theta)=J(\pi_\theta)$ by gradient ascent. This handles continuous actions, builds in stochasticity, and optimises the objective directly instead of through a value function. The challenge is to estimate $\nabla J$ from samples. ### The score function and REINFORCE For a trajectory $\zeta$ with return $R(\zeta)$, $$ \nabla J(\theta)=\nabla\,\mathbb E_\zeta[R(\zeta)]=\mathbb E_\zeta\Big[R(\zeta)\sum_t\nabla_\theta\log\pi_\theta(a_t\mid s_t)\Big], $$ because $\nabla p(\zeta)=p(\zeta)\nabla\log p(\zeta)$ and only the policy factors of $p(\zeta)$ depend on $\theta$; the transition probabilities do not. The estimator needs *no model*. derived Since a reward cannot be affected by later actions, replace $R(\zeta)$ with the reward-to-go $G_t$: same expectation, lower variance (Williams, 1992). recalled ### The policy gradient theorem, derived from the performance difference lemma $$ \begin{gathered} \nabla J(\theta)=\frac1{1-\gamma}\sum_{s,a}d^{\pi_\theta}(s,a)\,Q^{\pi_\theta}(s,a)\,\nabla_\theta\log\pi_\theta(a\mid s)\\ =\frac1{1-\gamma}\,\mathbb E_{(s,a)\sim d^{\pi_\theta}}\big[A^{\pi_\theta}(s,a)\,\nabla_\theta\log\pi_\theta(a\mid s)\big]. \end{gathered} $$ *Derivation.* By the lemma of Chapter 3, $J(\theta')-J(\theta)=\frac1{1-\gamma}\sum_sd^{\theta'}(s)\sum_a\pi_{\theta'}(a\mid s)A^\theta(s,a)$. Differentiate in $\theta'$ at $\theta'=\theta$. The factor $d^{\theta'}(s)$ also depends on $\theta'$, but its derivative multiplies $\sum_a\pi_\theta(a\mid s)A^\theta(s,a)=0$. What is left is $\frac1{1-\gamma}\sum_sd^\theta(s)\sum_a\nabla\pi_\theta(a\mid s)A^\theta(s,a)$, which is the formula with $\nabla\pi=\pi\nabla\log\pi$. Replacing $A$ by $Q$ changes nothing because $\mathbb E_{a\sim\pi}[\nabla\log\pi(a\mid s)]=0$. $\square$ derived This is the form of Sutton et al. (2000). recalled For a tabular softmax policy $\pi_\theta(a\mid s)\propto e^{\theta(s,a)}$ the theorem gives, coordinate by coordinate, $$ \frac{\partial J}{\partial\theta(s,a)}=\frac{1}{1-\gamma}\,d^{\pi}(s)\,\pi(a\mid s)\,A^\pi(s,a). $$ derived The factor $\pi(a\mid s)$ is worth staring at: where the policy gives an action probability near $0$ the gradient on its logit is near $0$ too, however good the action is. That is the source of the plateaus below. ### Baselines and variance Subtracting any baseline $b(s)$ that does not depend on the action leaves the gradient unchanged, since $\mathbb E_{a\sim\pi}[b(s)\nabla\log\pi(a\mid s)]=0$, and can reduce variance sharply. A natural choice is $b(s)=V^\pi(s)$, which turns $Q$ into the advantage. derived ### Actor–critic Replace the true $Q^\pi$ (or $A^\pi$) by a learned **critic**. The TD error is an unbiased advantage estimate when the critic is exact: $\mathbb E[\delta_t\mid s_t,a_t]=Q^\pi(s_t,a_t)-V^\pi(s_t)=A^\pi(s_t,a_t)$. derived With an imperfect critic $\delta_t$ is a biased but low-variance estimate. Using $n$-step instead gives $$ \hat A_t^{(n)}=\sum_{lderived ### Natural gradient The vanilla gradient depends on the parametrisation: reparametrise $\theta$ and the direction changes. The **natural gradient** uses the Fisher information of the policy as the metric, $$ \begin{gathered} \tilde\nabla J=F(\theta)^{-1}\nabla J,\\ F(\theta)=\mathbb E_{(s,a)\sim d^\pi}\big[\nabla\log\pi_\theta\,\nabla\log\pi_\theta^\top\big], \end{gathered} $$ which makes the step invariant to smooth reparametrisations (Kakade, 2001). recalled For the tabular softmax the natural gradient has a clean form: the update is a step of $\frac1{1-\gamma}A^\pi(s,a)$ on the logits, up to a constant per state, so $$ \pi_{\text{new}}(a\mid s)\ \propto\ \pi(a\mid s)\,\exp\!\Big(\frac{\eta}{1-\gamma}A^\pi(s,a)\Big), $$ soft policy iteration. As $\eta\to\infty$ it becomes policy iteration. The derivation: within each state the Fisher block is $d^\pi(s)\,(\operatorname{diag}\pi-\pi\pi^\top)$ and the gradient is $\frac1{1-\gamma}d^\pi(s)\,\pi\odot A^\pi$. The block is singular (adding a constant to all logits of a state changes nothing), and $w=\frac1{1-\gamma}A^\pi+c(s)$ solves $F w=\nabla J$ for any constant $c(s)$ because $(\operatorname{diag}\pi-\pi\pi^\top)A=\pi\odot A$ when $\sum_a\pi A=0$. derived The convergence analysis is in Agarwal et al. (2021). cited ### Trust regions: TRPO and PPO A gradient step changes $\theta$ in parameter space, but what matters is how much the *policy* changes, because the occupancy $d^{\pi'}$ in the performance difference lemma is for the *new* policy. Ignoring that change gives a local **surrogate** $$ L_\pi(\pi')=J(\pi)+\frac1{1-\gamma}\sum_{s,a}d^\pi(s)\,\pi'(a\mid s)\,A^\pi(s,a), $$ which agrees with $J(\pi')$ to first order at $\pi'=\pi$. Schulman et al. (2015) bound how far it can be wrong: $$ \begin{gathered} J(\pi')\ \ge\ L_\pi(\pi')-\frac{4\,\epsilon\,\gamma}{(1-\gamma)^2}\,\alpha^2,\\ \epsilon=\max_{s,a}|A^\pi(s,a)|,\\ \alpha=\max_s\mathrm{TV}\big(\pi(\cdot\mid s),\pi'(\cdot\mid s)\big). \end{gathered} $$ The proof couples the two policies so that they act differently with probability at most $\alpha$ at each step and sums the resulting discrepancy over time. recalled Since $\mathrm{TV}^2\le\mathrm{KL}/2$ (Pinsker), a KL penalty also controls the error, and one gets monotone improvement by maximising the surrogate minus a penalty on the KL. **TRPO** maximises $L_\pi(\pi')$ subject to a constraint on the mean KL between $\pi$ and $\pi'$, solved with conjugate gradients and a line search. **PPO** (Schulman et al., 2017) replaces the constraint by a clipped surrogate. With the ratio $\varrho_t=\pi_\theta(a_t\mid s_t)/\pi_{\theta_{\text{old}}}(a_t\mid s_t)$: $$ L^{\mathrm{CLIP}}(\theta)=\mathbb E_t\Big[\min\big(\varrho_t\hat A_t,\ \operatorname{clip}(\varrho_t,1-\varepsilon,1+\varepsilon)\hat A_t\big)\Big]. $$ The $\min$ removes the incentive to push $\varrho_t$ beyond $1\pm\varepsilon$ in the direction that raises the objective, so the gradient vanishes for samples that have already moved far enough. It allows several epochs of minibatch updates on one batch of data, the main source of its sample efficiency over vanilla policy gradient. recalled Whether clipping actually enforces a trust region is doubtful: ratios can leave the clip range, and implementation details (advantage normalisation, value clipping, learning-rate schedules) account for a large share of PPO's performance (Engstrom et al., 2020). recalled ### Deterministic policy gradients and off-policy actor-critic For a deterministic policy $a=\mu_\theta(s)$ the gradient is $\nabla_\theta J=\mathbb E_{s\sim d}\big[\nabla_\theta\mu_\theta(s)\,\nabla_aQ^\mu(s,a)\big|_{a=\mu_\theta(s)}\big]$ (Silver et al., 2014): move the action up the critic's gradient. **DDPG** (Lillicrap et al., 2016) pairs this with DQN's replay and target networks. **TD3** (Fujimoto et al., 2018) adds the fixes the previous chapter predicts: two critics and a minimum to fight overestimation, delayed actor updates, and smoothing of target actions. recalled ### Entropy-regularised RL and soft actor-critic Add an entropy bonus: maximise $J_\tau(\pi)=\mathbb E\sum_t\gamma^t\big(r_t+\tau\mathcal H(\pi(\cdot\mid s_t))\big)$. The Bellman equations change by replacing $\max$ with a smooth maximum: $$ \begin{gathered} V_\tau(s)=\tau\log\sum_a\exp\!\big(Q_\tau(s,a)/\tau\big),\\ \pi_\tau(a\mid s)\propto\exp\!\big(Q_\tau(s,a)/\tau\big). \end{gathered} $$ The soft operator is again a $\gamma$-contraction (log-sum-exp is nonexpansive in the max norm), and the softmax of the soft $Q$ is the optimal policy. derived The reason is that the maximiser of $\langle p,q\rangle+\tau\mathcal H(p)$ over distributions is $p\propto e^{q/\tau}$, with value $\tau\log\sum e^{q/\tau}$ (the Gibbs variational principle). **Soft actor-critic** (Haarnoja et al., 2018) is an off-policy actor-critic for this objective, with two critics and an automatically tuned temperature; **soft Q-learning** (Haarnoja et al., 2017) learns $Q_\tau$ directly. recalled The same structure, maximum reward plus a KL or entropy term, reappears as the objective of RLHF (Chapter 18), and the viewpoint of "RL as probabilistic inference" makes the connection explicit (Levine, 2018). recalled ### When do policy gradients find the optimum? $J$ is not concave in $\theta$ even in the tabular case. Yet for the tabular case, a gradient-domination inequality holds. From the lemma of Chapter 3, writing $\pi^\star$ for an optimal policy, $$ \begin{gathered} J(\pi^\star)-J(\pi)=\frac1{1-\gamma}\sum_sd^{\pi^\star}(s)\sum_a\pi^\star(a\mid s)A^\pi(s,a)\\ \le\ \frac1{1-\gamma}\Big\lVert\frac{d^{\pi^\star}}{d^\pi}\Big\rVert_\infty\sum_sd^\pi(s)\max_aA^\pi(s,a). \end{gathered} $$ The right-hand side is a *distribution mismatch coefficient* times the size of the best feasible improvement direction, which is what a gradient with respect to the direct parameters $\pi(a\mid s)$ measures. Since $d^\pi(s)\ge(1-\gamma)\mu(s)$, the coefficient is at most $1/((1-\gamma)\min_s\mu(s))$. derived Consequences: - With the direct parametrisation, every stationary point is globally optimal if $\mu>0$: no spurious local optima. - With the softmax parametrisation, gradient ascent converges to the global optimum (Agarwal et al., 2021). cited A rate of order $1/t$ for exact softmax policy gradient, depending on the initial policy and on $\min\mu$, is due to Mei et al. (2020); Agarwal et al. give rates for natural policy gradient, the log-barrier and the direct parametrisation. recalled But the time can be exponential in the number of states in constructed examples (Li et al., 2021). recalled The factor $\pi(a\mid s)$ in the gradient above explains why: a nearly deterministic wrong policy has an almost vanishing gradient, a plateau. - With function approximation, the guarantees are of the form "$\epsilon$ suboptimality plus an approximation error under the distribution shift between the optimal policy and the learner's data," which is where the coverage coefficients of the offline chapter come back (Agarwal et al., 2021). cited ### Choosing between value-based and policy-based | | Value-based (DQN-like) | Policy gradient (PPO-like) | | --- | --- | --- | | Data | Off-policy, replayed | Mostly on-policy; reused only through importance weights or clipping | | Actions | Discrete, or needs an actor | Discrete or continuous | | Variance / bias | Low variance, bias from bootstrapping and max | Higher variance, lower bias | | Stability | Deadly triad | Sensitive to step size; trust-region ideas help | | Natural fit | Many cheap samples, discrete actions | Stochastic policies, large action spaces, language | Actor–critic and trust-region methods sit between the two, and SAC and TD3 make the policy-gradient family off-policy. ## 14. Model-based reinforcement learning with function approximation Learn $\hat P$ and $\hat r$ with neural networks and use them to plan or to generate training data. The simulation lemma of Chapter 9 says what can go wrong: model errors multiply by up to $1/(1-\gamma)$ per step of value and compound along rollouts. ### Learning a dynamics model - **Probabilistic ensembles.** A single network trained by maximum likelihood is overconfident away from the data; an *ensemble* of probabilistic networks separates *aleatoric* noise (each member's predicted variance) from *epistemic* uncertainty (disagreement between members) (PETS: Chua et al., 2018). recalled - **Planning with the model.** *Model predictive control* re-plans at every step: sample action sequences (random shooting, the cross-entropy method, MPPI), score them in the model, execute the first action, and repeat. Re-planning limits how far model error can accumulate. - **Short branched rollouts.** MBPO (Janner et al., 2019) trains an off-policy actor-critic on a mix of real data and *short* model rollouts started from real states, trading the bias of the model against the variance of real data. A bound on the return gap depends on the model error and the rollout length, and motivates short horizons. recalled ### Latent world models From pixels one rarely models observations directly. **World Models** (Ha and Schmidhuber, 2018), **PlaNet** and the **Dreamer** family (Hafner et al., 2019–2023) learn a compact latent state with a recurrent state-space model, predict rewards and latent transitions, and train an actor-critic *inside the learned model* ("in imagination"). recalled The model need only be good enough in latent space for the policy it trains. ### Plan with search: AlphaZero and MuZero **Monte Carlo tree search** estimates action values by simulation, growing a tree whose child selection is a UCB rule at each node (UCT: Kocsis and Szepesvári, 2006). recalled **AlphaZero** couples search with a network that proposes moves and evaluates positions; search *improves* the policy (visit counts are a better policy than the network's prior) and the network is trained to imitate the improved policy and the game result. recalled This is policy iteration with search as the improvement operator. **MuZero** (Schrittwieser et al., 2020) removes the need for the rules: it learns a model that predicts only what search needs (reward, value, policy), not the next observation. recalled ### Value equivalence Why model what the value function ignores? Two models are **value-equivalent** with respect to a set of policies and functions if their Bellman backups agree on that set, which suffices for planning (Grimm et al., 2020). recalled This is the simulation lemma read as a design principle: only $(\hat P-P)V^\pi$ matters (Chapter 9), so a model needs to be right in the directions the values see. ### Model bias, and when to use models A planner optimises *against* its model, so it finds and exploits the model's errors. Defences are uncertainty-aware models (ensembles), short horizons, conservative penalties on uncertain transitions (MOPO, MOReL in the offline setting), and replanning. Models help most when samples are expensive and dynamics are learnable and smooth; they struggle with long horizons, stochastic or partially observed environments and high-dimensional observations. recalled ## 15. Representation, generalisation and theory beyond the tabular case ### Why structure is necessary In general, no algorithm can learn efficiently with function approximation: sample complexity can depend exponentially on the horizon or the number of features unless the problem has structure. Even *planning* with a generative model has this character: sparse sampling achieves near-optimal planning with a number of samples independent of $|S|$ but exponential in the effective horizon $1/(1-\gamma)$ (Kearns, Mansour and Ng, 2002). recalled ### Realisability is not enough Suppose the learner is told that $Q^\star$ lies in a known function class (it is *realisable*, e.g. linear in known features). Exponential lower bounds show this alone does not give sample-efficient planning or learning (Weisz, Amortila and Szepesvári, 2021, whose construction needs a large action set; Du et al., 2020; Wang, Foster and Kakade, 2021, for the offline analogue). recalled What fixes it are stronger structural assumptions: - **Bellman completeness.** The class is closed under the backup, $\mathcal T\mathcal F\subseteq\mathcal F$; makes fitted Q-iteration analysable (Chapter 11). - **Linear MDPs.** $P(s'\mid s,a)=\langle\phi(s,a),\mu(s')\rangle$ and $r(s,a)=\langle\phi(s,a),\theta\rangle$ for known features. Then every $Q$ is linear in $\phi$, and optimistic least-squares value iteration (LSVI-UCB) has regret of order $\sqrt{d^3H^3T}$ independent of $|S|$ and $|A|$ (Jin, Yang, Wang and Jordan, 2020). recalled - **Low-rank MDPs.** The same factorisation but with *unknown* features: representation learning is part of the problem (FLAMBE: Agarwal et al., 2020, and successors). recalled - **Low Bellman rank, Bellman-eluder dimension, bilinear classes.** Complexity measures under which optimism-based algorithms (OLIVE and descendants) are sample-efficient: roughly, they bound how many times the Bellman error can be large on new data (Jiang et al., 2017; Jin, Liu and Miryoosefi, 2021; Du et al., 2021). recalled - **Decision-estimation coefficient.** A single quantity that characterises minimax regret for interactive decision making (Foster et al., 2021). recalled The pattern: guarantees exist when there is a low-dimensional structure the learner can both *exploit* (fit with few samples) and *explore* (be systematically optimistic about). ### Successor representations and features If the reward is linear in features, $r(s,a)=\phi(s,a)^\top w$, then by linearity of the Bellman equation $Q^\pi(s,a)=\psi^\pi(s,a)^\top w$, where the **successor features** $\psi^\pi(s,a)=\mathbb E_\pi\big[\sum_t\gamma^t\phi(s_t,a_t)\mid s_0=s,a_0=a\big]$ satisfy their own vector-valued Bellman equation. derived Change the task by changing $w$ and re-evaluate by a dot product, with no relearning of the dynamics (Barreto et al., 2017). recalled When $\phi$ is one-hot on state-action pairs, $\psi$ is the (unnormalised) *successor representation* of Dayan (1993), the table of expected discounted future visits, and its $\mu$-average, times $1-\gamma$, is exactly the occupancy $d^\pi$ of Chapter 5. So the polytope of Chapter 5 is the space of successor representations averaged over the start distribution. ### Bisimulation and abstraction Two states can be merged if they have the same reward and transition to equivalent states: a *bisimulation*. A metric version assigns distance by differences in reward plus Wasserstein distance between next-state distributions, giving value bounds under approximate aggregation (Givan, Dean and Greig, 2003; Ferns, Panangaden and Precup, 2004). recalled Learned embeddings that respect this metric ignore irrelevant visual detail (Zhang et al., 2021). recalled ### Representation failure modes in deep RL - **Capacity and plasticity loss.** Networks trained on non-stationary targets can lose the ability to fit new ones (dormant units, rank collapse), a phenomenon documented in several RL and continual-learning studies (Lyle et al., 2022; Dohare et al., 2024). recalled - **Primacy bias.** Early data are over-fit, especially with a high replay ratio; periodic resets help (Nikishin et al., 2022). recalled - **Overfitting to the training environments.** Agents trained on a fixed set of procedurally generated levels fail on new ones; generalisation needs many more environments than the single-level training suggests (Cobbe et al., 2019, CoinRun; 2020, Procgen). recalled ### Generalising across tasks: meta-RL and in-context RL A learner can be trained on many MDPs drawn from a prior and be asked to adapt within an episode. The Bayes-optimal solution is a policy over *beliefs* about the MDP: the **Bayes-adaptive MDP**, in which exploration and exploitation are one optimisation (Duff, 2002). recalled A sequence model trained on histories from many tasks can approximate that policy *in context* without gradient updates: Algorithm Distillation and supervised pretraining for in-context RL (Laskin et al., 2022; Lee et al., 2023). recalled (Decision Transformer, Chen et al., 2021, conditions on a return within one task's data and does not adapt across tasks; see Chapter 16.) This is the same structural idea as the prior-data fitted network: train on simulated tasks, let the network learn *how to learn*, and read a new task off the context. The PFN essay on this site derives it for prediction ([Deriving the Prior-Data Fitted Network](../posts/pfn-derived.html)); the decision-making version replaces the posterior predictive by the Bayes-optimal policy of the belief MDP. recalled as a framing; I have not checked the in-context RL papers against this description. ## 16. Offline reinforcement learning ### The setting Given a fixed dataset $\mathcal D=\{(s_i,a_i,r_i,s_i')\}$ collected by one or several behaviour policies $b$, with no further interaction, either **evaluate** a target policy $\pi$ (*off-policy evaluation*, OPE) or **learn** a good policy (*offline policy learning*). The data describe the occupancy $d^b$ and nothing else. Everything is a question of how much of the target's occupancy $d^\pi$ is covered by $d^b$. ### Why offline Q-learning breaks Q-learning's target $r+\gamma\max_{a'}Q(s',a')$ evaluates $Q$ at actions $a'$ that the data may never contain. The function approximator extrapolates there, errors are positive in some places by chance, the maximum selects those, and the bootstrapped error compounds with no new data to correct it: **extrapolation error** (Fujimoto et al., 2019). In a tabular case with no data at $(s',a')$ there is simply no information. recalled ### Coverage The central assumptions are about the *ratio* of the target's occupancy to the data's: - **All-policy concentrability** $C=\max_\pi\max_{s,a}d^\pi(s,a)/d^b(s,a)$: the data cover every policy. This is what classical analyses of fitted Q-iteration assume (Munos and Szepesvári, 2008). recalled - **Single-policy concentrability** $C^\star=\max_{s,a}d^{\pi^\star}(s,a)/d^b(s,a)$: the data cover only the comparator. The right assumption when the algorithm is pessimistic (below). cited ### Off-policy evaluation - **Importance sampling** reweights trajectories by $\prod_t\pi(a_t\mid s_t)/b(a_t\mid s_t)$: unbiased, with variance exponential in the horizon. **Per-decision** and **weighted** variants and **doubly robust** estimators that combine a value model with importance weights reduce the variance (Precup et al., 2000; Jiang and Li, 2016; Thomas and Brunskill, 2016). recalled - **Fitted Q-evaluation (FQE)** regresses Bellman targets under $\pi$, no maximum, so the stability problem is milder (Le et al., 2019). recalled - **Marginalised importance sampling and DICE.** Estimate the single ratio $w=d^\pi/d^b$ instead of a product, then $J(\pi)=\frac1{1-\gamma}\mathbb E_{d^b}[w\,r]$. The ratio is characterised by a flow identity (Chapter 5), which can be turned into a saddle-point problem over $w$ and test functions (Liu et al., 2018; Nachum et al., 2019; Nachum and Dai, 2020). cited for the duality framework. ### Offline policy learning Four families, all of which limit how far $\pi$ moves from where the data are: 1. **Policy constraints.** Penalise or constrain divergence from the behaviour policy: BCQ (Fujimoto et al., 2019), BEAR (Kumar et al., 2019), BRAC (Wu et al., 2019), and the minimalist TD3+BC (Fujimoto and Gu, 2021). recalled A KL-constrained improvement step has the closed form $\pi\propto b\,e^{A/\beta}$ (Chapter 13's Gibbs principle), so *advantage-weighted regression* (Peng et al., 2019; Nair et al., 2020) is behaviour cloning with weights $e^{A/\beta}$. derived (the form) recalled (the methods). 2. **Value regularisation.** CQL adds a penalty that pushes down $Q$ on actions not in the data and up on those that are, yielding a lower bound on the true value (Kumar et al., 2020). **IQL** never queries out-of-data actions: it fits the value by *expectile* regression on in-data actions and extracts a policy by weighted cloning (Kostrikov et al., 2022). recalled 3. **Pessimistic model-based.** Learn a model and subtract a penalty proportional to its uncertainty from the reward, so the planner avoids regions where the model is unreliable (MOPO: Yu et al., 2020; MOReL: Kidambi et al., 2020). recalled 4. **Sequence modelling.** Treat the dataset as sequences and condition on a desired return (Decision Transformer: Chen et al., 2021). It sidesteps bootstrapping, but it can only reproduce behaviour present in the data, and "stitching" good sub-trajectories from different episodes is not guaranteed. recalled ### The theory of pessimism **Pessimism** means: choose the policy with the best *lower* confidence bound on its value, so uncertainty counts against a policy. In optimism (Chapter 10) the sign of the bonus flips. The pessimistic value iteration algorithm PEVI penalises the Bellman backup by an uncertainty quantifier; its suboptimality is bounded by a data-dependent term that accumulates only along the *optimal* policy's trajectory, with no assumption of coverage of other policies, and in linear MDPs it matches the information-theoretic lower bound up to factors of dimension and horizon (Jin, Yang and Wang, 2021). cited A lower confidence bound reaches the rate $1/N$ on nearly expert data, against the usual $1/\sqrt N$ (Rashidinejad et al., 2021), interpolating between imitation learning and offline RL. cited ### What offline RL cannot do Without coverage of the comparator, no algorithm can succeed: evaluating or optimising over policies that the data never touch is a guess. Lower bounds show that even evaluation can need exponentially many samples under only realisability (Wang et al., 2021; Zanette, 2021). recalled There is also a *model-selection* problem peculiar to offline RL: with no environment to test in, how does one tune hyperparameters? OPE is itself noisy, so choices can be unreliable. recalled ## 17. Imitation, inverse RL and preferences When no reward is given, it may be inferred from behaviour, or from human judgements. ### Behaviour cloning and compounding error **Behaviour cloning** fits $\pi(a\mid s)$ to expert pairs by supervised learning. If the learner's per-step error under the *expert's* state distribution is $\epsilon$, the error under the *learner's* distribution can be much larger, because one mistake leads to states the expert never visited, where the learner has no data. With a horizon $T$ and a worst-case cost of 1 per step after an error, the chance of having erred by step $t$ is at most $t\epsilon$, giving total cost of order $T^2\epsilon$, quadratic in the horizon (Ross and Bagnell, 2010). **DAgger** fixes this by interaction: run the learner, ask the expert what it would have done in the learner's states, aggregate, retrain; the cost becomes order $T\epsilon$ (Ross, Gordon and Bagnell, 2011). recalled The quadratic bound can be reasoned out as above, with $\epsilon$ the per-step probability of disagreeing with the expert. derived as a sketch ### Imitation as occupancy matching The expert induces an occupancy $d_E$. Imitation is finding a policy whose occupancy is close to $d_E$: *the point of the state-action polytope nearest to the expert's*, in some divergence. **GAIL** (Ho and Ermon, 2016) shows that maximum-entropy inverse RL followed by RL is the dual of exactly such an occupancy-matching problem, and trains a discriminator between expert and learner state-action pairs whose output serves as the reward. recalled The same view explains why BC fails off the expert's support: $d_E$ says nothing about states outside it. ### Inverse reinforcement learning Infer a reward under which the expert is optimal. The problem is ill-posed: $r\equiv0$ makes every policy optimal, and many rewards explain the same behaviour (Ng and Russell, 2000). **Maximum-entropy IRL** chooses, among rewards explaining the expert's feature expectations, the one whose maximum-entropy (soft-optimal, Chapter 13) policy matches them, which resolves the ambiguity by a principle of least commitment (Ziebart et al., 2008). *Apprenticeship learning* matches feature expectations directly (Abbeel and Ng, 2004). recalled ### Preferences Often it is easier to *compare* two behaviours than to write a reward or demonstrate. The **Bradley–Terry model** posits $\Pr(y_1\succ y_2\mid x)=\sigma\big(r(x,y_1)-r(x,y_2)\big)$ and trains $r$ by maximum likelihood on comparisons, $-\log\sigma\big(r(x,y_w)-r(x,y_l)\big)$ (Christiano et al., 2017, for RL from human feedback). recalled Two consequences: - The reward is identified only **up to a constant per prompt**, because only differences enter: $r(x,y)+c(x)$ gives the same probabilities. derived - The learned reward is a *proxy*. Optimising it hard exploits its errors (Chapter 18). ## 18. Reinforcement learning for language models ### Formulation A prompt $x$ is drawn from a distribution $p_X$. The model generates a completion $y=(y_1,\dots,y_L)$ token by token, $\pi_\theta(y\mid x)=\prod_t\pi_\theta(y_t\mid x,y_{recalled - **Verifiable rewards** (RLVR): a program checks the answer of a math problem, runs unit tests on code, or checks an instruction-following constraint. The reward is exact and cheap and has no learned model to exploit (Lambert et al., 2024, the Tülu 3 report, which introduced the name). cited - **AI feedback** from a model following written principles (Bai et al., 2022). recalled - **Process rewards** score intermediate reasoning steps rather than only the final answer (Lightman et al., 2023). recalled ### The KL-regularised objective and its closed form Because the reward is a fallible proxy and the policy should stay fluent, the standard objective penalises divergence from a reference model $\pi_{\mathrm{ref}}$ (the supervised-fine-tuned model): $$ \max_\pi\ \mathbb E_{x\sim p_X,\,y\sim\pi(\cdot\mid x)}\big[r(x,y)\big]-\beta\,\mathrm{KL}\big(\pi(\cdot\mid x)\,\Vert\,\pi_{\mathrm{ref}}(\cdot\mid x)\big). $$ For each prompt, over distributions on completions, the maximiser is the reference **tilted** by the exponentiated reward: $$ \begin{gathered} \pi^\star(y\mid x)=\frac{\pi_{\mathrm{ref}}(y\mid x)\,e^{\,r(x,y)/\beta}}{Z(x)},\\ \max=\beta\log Z(x),\\ Z(x)=\sum_y\pi_{\mathrm{ref}}(y\mid x)e^{\,r(x,y)/\beta}. \end{gathered} $$ *Why.* For any $\pi$, $\mathbb E_\pi[r]-\beta\mathrm{KL}(\pi\Vert\pi_{\mathrm{ref}})=\beta\log Z-\beta\,\mathrm{KL}(\pi\Vert\pi^\star)$, and KL is nonnegative and zero only at $\pi=\pi^\star$. derived This is the one-step form of the **soft Bellman equation** of Chapter 13: the hard maximum over actions is replaced by a log-sum-exp (the soft maximum $\beta\log Z$). Two further facts: - The sequence-level KL decomposes over tokens (the chain rule of KL): $\mathrm{KL}(\pi\Vert\pi_{\mathrm{ref}})=\sum_t\mathbb E_{y_{derived - The penalty can be put in the reward (as $-\beta\log\frac{\pi}{\pi_{\mathrm{ref}}}$ per token, then handled by the value function) or added to the loss. GRPO chooses the loss, to keep the advantage a function of the outcome reward alone. cited A low-variance, unbiased, always-nonnegative estimator of the KL from samples $y\sim\pi$ uses the ratio $u=\pi_{\mathrm{ref}}/\pi$ as $u-\log u-1$. cited ### The RLHF pipeline with PPO (1) Fine-tune a base model on demonstrations to get $\pi_{\mathrm{ref}}$. (2) Fit a reward model on human preference comparisons. (3) Run PPO (Chapter 13) against that reward with a per-token KL penalty, using a learned value head (the critic) for advantages. recalled The cost is four large models in memory (policy, reference, reward model, critic). The critic is the awkward part: with only a terminal reward, it must predict the final outcome from every prefix, and in language models it is usually a network as large as the policy. cited (the DeepSeekMath paper makes both points). ### Critic-free methods: REINFORCE, RLOO and GRPO If the problem is treated as a one-step bandit over whole completions, the policy gradient of Chapter 13 needs only a baseline $b(x)$ for each prompt, and the best-behaved baseline is the prompt's value $V(x)=\mathbb E_{y\sim\pi}[r(x,y)]$. One can *estimate that value from samples of the same prompt*. Sample a group of $G$ completions $y_1,\dots,y_G\sim\pi(\cdot\mid x)$ with rewards $r_1,\dots,r_G$: - **RLOO** (REINFORCE leave-one-out): $\hat A_i=r_i-\frac1{G-1}\sum_{j\ne i}r_j$. The baseline for sample $i$ does not depend on sample $i$, so the gradient estimate is unbiased. Ahmadian et al. (2024) argue this simple critic-free method beats PPO on RLHF tasks. cited - **GRPO** (Shao et al., 2024): $\hat A_i=\dfrac{r_i-\operatorname{mean}(r)}{\operatorname{std}(r)}$, applied to every token of completion $i$ in the paper's outcome-supervised form, inside a PPO-style clipped objective with a loss-level KL term: $$ \begin{gathered} \mathcal J_{\mathrm{GRPO}}(\theta)=\mathbb E\Big[\frac1G\sum_{i=1}^G\frac1{|y_i|}\sum_{t=1}^{|y_i|}\Big\{\\ \min\big(\varrho_{i,t}\hat A_i,\ \operatorname{clip}(\varrho_{i,t},1\pm\varepsilon)\hat A_i\big)\\ -\beta\,\mathrm{KL}_{i,t}\Big\}\Big], \end{gathered} $$ with ratio $\varrho_{i,t}=\pi_\theta(y_{i,t}\mid x,y_{i,cited The objective, the advantage and the loss-level KL are from the paper's text. (The population or sample standard deviation is not specified there; implementations differ by $\sqrt{G/(G-1)}$.) **What the algebra says about GRPO** (all derived): 1. **Advantages sum to zero** in every group and have unit second moment unless the group is constant. Correct answers are pushed up and incorrect ones down, with magnitudes set by how rare each outcome is. 2. **A constant group gives no gradient.** If every completion earns the same reward, $\operatorname{std}(r)=0$ and all advantages vanish. With a binary reward and per-prompt success rate $p$, the chance that a group of $G$ is constant is $p^G+(1-p)^G$: for hard prompts ($p$ near 0) and easy prompts ($p$ near 1) most groups carry no signal. This is the motivation for *dynamic sampling* that discards such groups (Yu et al., 2025, recalled). 3. **The group mean is a slightly biased baseline.** It includes the sample it is baselining, so the expected gradient is scaled by $(G-1)/G$; the leave-one-out mean removes that bias. Indeed $r_i-\operatorname{mean}(r)=\frac{G-1}G\big(r_i-\operatorname{mean}_{j\ne i}r_j\big)$, so the mean-baselined advantage is exactly $(G-1)/G$ times the RLOO advantage. The clean factor holds for the mean-only baseline; with standard-deviation normalisation the advantage depends on all samples and the scaling is no longer exact. derived 4. **Normalising by the standard deviation reweights prompts.** Without it, the advantages' second moment is the variance $p(1-p)$, largest for medium-difficulty prompts; with it, every non-constant group has unit second moment, so very easy and very hard prompts (rare but non-constant outcomes) get as much weight as medium ones. Whether that is desirable is empirical. derived (the algebra) recalled (the debate) 5. **Length normalisation.** The $1/|y_i|$ factor spreads one advantage over the tokens of a completion, so each token of a long incorrect answer is penalised less than each token of a short one. Liu et al. (2025) argue that this term, and the standard-deviation term, bias GRPO toward longer incorrect responses, and propose removing both ("Dr. GRPO"). I have confirmed the title and authors of that paper but not its claims. recalled 6. **At the first step the update is vanilla policy gradient plus a KL term.** When $\pi_\theta=\pi_{\theta_{\text{old}}}$, $\varrho=1$, nothing is clipped, and the gradient is $\frac1{|y_i|}\hat A_i\nabla\log\pi_\theta(y_{i,t}\mid\cdot)$ with the group baseline, minus $\beta\nabla\mathrm{KL}$, which is nonzero unless $\pi_\theta=\pi_{\mathrm{ref}}$. Clipping only matters on later minibatch steps, as policies drift. derived **Descendants.** Variants adjust clipping asymmetrically, filter groups, use token-level or sequence-level ratios, or change how long outputs are penalised (DAPO: Yu et al., 2025; GSPO; Dr. GRPO). I have not verified their details. recalled ### Direct preference optimisation DPO (Rafailov et al., 2023) uses the closed form above to *avoid RL altogether*. Invert it: $r(x,y)=\beta\log\frac{\pi^\star(y\mid x)}{\pi_{\mathrm{ref}}(y\mid x)}+\beta\log Z(x)$. Substitute into the Bradley–Terry likelihood, with $\pi_\theta$ in place of $\pi^\star$; $Z(x)$ cancels in the difference: $$ \begin{gathered} \mathcal L_{\mathrm{DPO}}(\theta)=-\mathbb E\Big[\log\sigma\Big(\beta\log\frac{\pi_\theta(y_w\mid x)}{\pi_{\mathrm{ref}}(y_w\mid x)}\\ -\beta\log\frac{\pi_\theta(y_l\mid x)}{\pi_{\mathrm{ref}}(y_l\mid x)}\Big)\Big]. \end{gathered} $$ derived The model is its own implicit reward model. cited (Rafailov et al. state the closed form and the reparametrisation in the abstract.) What it assumes and where it can fail: the Bradley–Terry model is right; the preference data cover the completions the optimised policy will produce (DPO is an **offline** method, so Chapter 16's coverage question applies); and the optimum is representable. Known behaviours (recalled): the log-likelihood of *both* chosen and rejected completions can decrease; the policy can drift off the data distribution; online and iterated variants that sample from the current policy help. recalled ### Reasoning with verifiable rewards With an exact reward (a final-answer check), a critic-free method such as GRPO can improve a base model's math and code accuracy. DeepSeek-R1-Zero reported RL from a *base* model with rule-based rewards (accuracy and format) alone, with response length and self-checking behaviour increasing during training. recalled Open questions I want to settle: ### Exploration, entropy and difficulty Exploration in LM-RL is sampling: temperature and the diversity of prompts. Policy entropy falls quickly during RL, which reduces the diversity within a group and so the fraction of non-constant groups, a feedback loop toward fewer informative samples (the "entropy collapse" reported in recent work, recalled). Prompts whose success rate is neither $0$ nor $1$ carry the signal, which is why curricula and filtering by difficulty matter: it is the same *coverage* principle as exploration and offline RL, applied to prompts instead of states. recalled ### Overoptimisation and reward hacking A learned reward is a proxy. Optimising it harder (more KL from the reference, more samples in best-of-$n$) raises the proxy reward monotonically, but the *true* (gold) reward first rises and then falls: Goodhart's law, measured with a synthetic gold reward model for both RL and best-of-$n$ (Gao, Schulman and Hilton, 2022). cited The KL coefficient $\beta$ controls how far optimisation proceeds. As I recall, the paper reports that a KL penalty does not improve the frontier of gold reward against KL distance but only changes where along it one stops; I have not re-checked that. recalled Verifiable rewards remove the learned proxy but not hacking: models can special-case the tests, exploit the format check, or produce answers that pass a weak verifier. recalled ### Credit assignment and test-time compute Outcome supervision gives every token of a completion the same advantage, so the learning signal for *which step* mattered is implicit and noisy. Process reward models and Monte Carlo estimates of the value of a prefix (roll out from the prefix and average the final reward) provide denser signals at greater cost. recalled Inference-time methods (best-of-$n$, majority vote, search guided by a verifier) spend compute to improve a fixed policy, an *improvement operator* that RL can then distil, as AlphaZero distils search (Chapter 14). ### Dictionary | LLM RL | In this note | | --- | --- | | Prompt | Start state | | Completion | Trajectory (or, treated as one action, a bandit arm) | | Reward model / verifier | Reward function | | Reference model | Prior / behaviour policy | | KL penalty | Soft (entropy- or KL-regularised) optimality | | Group mean | Monte Carlo estimate of the value, a baseline | | Clipped ratio | Trust region (Chapter 13) | | DPO | Offline method with the soft-optimal closed form | | RLVR | Exact reward, no learned proxy | | Best-of-$n$ | Policy improvement by search at test time | ## 19. Multi-agent reinforcement learning and games *Status: a stub. Almost everything here is recalled; treat it as a map of what to read.* ### Markov games With $N$ agents, a **Markov game** is $(S,\{A_i\},P,\{r_i\},\gamma)$: the transition depends on the joint action and each agent has its own reward. For two-player zero-sum games the Bellman equation survives with a *minimax* in place of the max: each state is a small matrix game, and the operator is a $\gamma$-contraction (Shapley, 1953; Littman, 1994, minimax-Q). recalled For general-sum games, stationary Nash equilibria exist but computing them is computationally hard (PPAD-complete in general). recalled A zero-sum matrix game's value is a linear program over the *strategy simplex*, a different program from Chapter 5's but with the same strong-duality mechanism: von Neumann's minimax theorem is LP strong duality. recalled as a standard fact. ### What is different - **Non-stationarity.** From one agent's view the environment includes the others, who are also learning, so the MDP assumption fails. - **Credit assignment across agents.** A shared reward does not say whose action mattered. - **Equilibrium selection.** Many equilibria exist; self-play may converge to an exploitable one. - **Partial observability.** Each agent sees its own view. Cooperative decentralised problems (Dec-POMDPs) are intractable in the worst case (NEXP-complete: Bernstein et al., 2002). recalled ### Methods - **Cooperative.** *Centralised training, decentralised execution*: use global information to train, local information at test. MADDPG (Lowe et al., 2017), value factorisation with monotonic mixing (QMIX: Rashid et al., 2018) and PPO with a centralised critic (MAPPO: Yu et al., 2022). recalled - **Competitive and self-play.** AlphaGo, AlphaZero (Silver et al., 2016, 2017) learn by playing themselves with search. For imperfect-information games (poker), *counterfactual regret minimisation* (Zinkevich et al., 2007) and its descendants converge to equilibrium by no-regret learning, since in two-player zero-sum games the average of no-regret strategies converges to a Nash equilibrium. League-style training and policy-space response oracles (PSRO: Lanctot et al., 2017) manage diversity of opponents. recalled ## 20. Other objectives: constraints, risk, robustness, several rewards *Status: a stub, except for the constrained-MDP and multi-objective arguments, which are derived in Chapter 5 and below.* ### Constrained MDPs Maximise $J_r(\pi)$ subject to $J_c(\pi)\le b$. In occupancy space it is an LP with extra constraints (Chapter 5): the optimum may need randomisation, and in the worked case of Chapter 5 exactly one state randomises. Practical algorithms use the Lagrangian $\max_\pi\min_{\lambda\ge0}J_r-\lambda(J_c-b)$ (primal-dual methods) or trust-region updates that enforce the constraint (CPO: Achiam et al., 2017). Strong duality holds for the linear program in occupancy space, not in general for the problem posed over policies. The two difficulties are *safe exploration* (constraints must hold while learning, not only at the end) and the oscillation of Lagrangian dynamics. recalled ### Risk sensitivity The expected return ignores variability. Alternatives: exponential utility, which has its own Bellman operator (Howard and Matheson, 1972); mean-variance, which breaks dynamic programming (variance is not additive over time); and **CVaR**, the mean of the worst $\alpha$-fraction of outcomes, optimised by augmenting the state with a risk level (Chow et al., 2015). Distributional RL learns the whole return distribution, making such risk measures readable at decision time (IQN). recalled ### Robust MDPs Let the transition kernel be unknown within an uncertainty set and maximise the *worst-case* value. If the set is *rectangular* (a product over states or state-action pairs) a robust Bellman operator with an inner minimum is still a contraction and dynamic programming works (Iyengar, 2005; Nilim and El Ghaoui, 2005). recalled Optimism (Chapter 10) takes the best element of such a set and pessimism (Chapter 16) the worst, so the two are $\sup$ and $\inf$ over the same plausible models. recalled as framing. ### Several rewards Given $m$ reward functions, the set of achievable return vectors $\{(J_1(\pi),\dots,J_m(\pi))\}$ over stochastic policies is the image of the polytope $\mathcal D$ under a linear map, hence **convex**. So every Pareto-optimal return vector (among stochastic stationary policies) is optimal for some linear scalarisation $\sum_iw_iJ_i$ with nonnegative weights. derived The usual warning that linear scalarisation misses concave parts of the Pareto front applies to *deterministic* policies, not to randomised ones: allowing randomisation fills the gap. Mixing two policies at the start of an episode gives the convex combination of their occupancies, which is again a point of $\mathcal D$, so a single stationary policy realises it. derived ### Average reward and the discount as a design choice In continuing tasks the average-reward criterion (Chapter 2) is natural, with its own Bellman equation (the Poisson equation) and relative value iteration. In practice the discount is a hyperparameter: a smaller $\gamma$ shortens the planning horizon, lowers variance and can regularise a model with errors, at the price of bias towards the short term. recalled ## 21. One map ### What each method estimates, and what it assumes | Family | Estimates | Core equation or operator | Needs | Typical failure | | --- | --- | --- | --- | --- | | Dynamic programming (VI, PI) | $V^\star$ from a known model | Fixed point of $\mathcal T$ | Known $P,r$; small $S$ | Curse of dimensionality | | Monte Carlo | $V^\pi$ from returns | Sample average of $G_t$ | Episodes | Variance; waits for episodes | | TD($\lambda$) | $V^\pi$ from transitions | Noisy $\mathcal T^\pi$; traces mix $n$-step returns | Markov state | Bias from bootstrapping | | SARSA / Q-learning | $Q^{\pi}$ / $Q^\star$ | Noisy $\mathcal T^\pi$ / $\mathcal T$ | Visit every pair | Maximisation bias; slow rates | | LSTD, FQI | $V$ or $Q$ in a function class | Projected Bellman equation | Completeness; coverage | Divergence if off-policy | | DQN family | $Q_\theta$ | Regression to a frozen $\mathcal T$ target | Replay, targets | Overestimation; deadly triad | | Policy gradient | $\theta$ directly | $\nabla J=\mathbb E[A\nabla\log\pi]/(1-\gamma)$ | On-policy data (or ratios) | Variance; plateaus | | TRPO / PPO | $\theta$ with bounded change | Surrogate $L_\pi$ plus KL or clip | Reasonable advantages | Trust region not enforced | | SAC | $Q_\tau,\pi$ with entropy | Soft Bellman | Off-policy replay | Temperature tuning | | Model-based | $\hat P,\hat r$, then plan | Simulation lemma | Learnable dynamics | Model bias, compounding | | Optimistic exploration | Values with bonuses | $\mathcal T$ plus a bonus | A valid confidence set | Large state spaces | | Offline + pessimism | Values with penalties | $\mathcal T$ minus a penalty | Coverage of the comparator | No coverage, no guarantee | | DICE | Occupancy ratio $d^\pi/d^b$ | Flow identity (saddle point) | Realisable ratio class | Unstable min-max | | Imitation (BC, GAIL) | $\pi$ near the expert | Occupancy matching | Expert data | Compounding error | | RLHF, GRPO, DPO | $\pi$ near a tilted reference | KL-regularised soft optimum | A reward signal | Reward hacking; entropy collapse | ### Recurring ideas 1. **Contraction and fixed points.** Everything that bootstraps is trying to find the fixed point of an operator. Stability is a question of whether the approximate operator still contracts in some norm. 2. **Bias and variance in the target.** Monte Carlo, TD, $n$-step, $\lambda$, GAE, baselines, group means: one trade-off. 3. **Optimism and pessimism.** Sup versus inf over the models the data allow. Online exploration needs the first, offline learning the second. 4. **Coverage.** The occupancy of what you want to learn must be inside the occupancy of what you saw: exploration (online), concentrability (offline), the support of the behaviour policy (imitation), the success rate of prompts (LM-RL). 5. **Duality.** Values are prices of flow constraints; occupancy ratios are dual variables for OPE; reward models and DPO share a closed form from Gibbs duality. 6. **Regularisation as a Bayesian prior.** Entropy and KL terms turn the max into a soft max and the optimum into a tilt of a reference. 7. **Trust regions.** Local approximations (the surrogate, the model, the critic) are valid only nearby, so bound the step. 8. **Amortisation.** Learn a policy (or a prior over tasks) so that decisions cost a forward pass: from policy distillation of search to in-context RL. ### Which guarantee needs which assumption | Guarantee | Assumptions (in the sense of Chapter 15–16) | | --- | --- | | Tabular convergence (TD, Q-learning) | Visit every pair infinitely often; Robbins–Monro steps | | TD with linear features converges | On-policy sampling; linear architecture | | FQI / fitted VI error bound | Bellman completeness; concentrability | | Online regret with function approximation | Linear/low-rank MDP, low Bellman rank, or similar structure | | Offline $\epsilon$-optimality | Single-policy coverage plus pessimism | | Policy gradient global convergence | Tabular softmax or direct parametrisation; positive $\mu$; step-size conditions | | KL-regularised optimum (RLHF) | The reward is the objective; the optimum lies in the policy class | ## 22. Open questions and a research agenda Questions I could not answer while writing, and a few I want to explore. These are the part of the note most likely to change. 1. **When should $\lambda$ be near 1?** A clean characterisation under non-Markov or aliased state (Chapter 7). 2. **Diagnostics for deep Q-learning.** A cheap quantity that detects entry into a divergence regime before the value explodes; a sufficient stability condition weaker than completeness (Chapter 12). 3. **Unifying coverage.** Online exploration costs and offline concentrability coefficients look like different views of one quantity measuring how well data cover the optimal occupancy (Chapters 10, 16). 4. **Coverage for language models.** What plays the role of a concentrability coefficient for a preference dataset over long completions? How do on-policy and off-policy methods differ (Chapter 16, 18)? 5. **Search and training.** AlphaZero distils search into a network. Which parts of that recipe transfer to LM post-training, and what is the analogue of the game's rules as a known, deterministic transition (Chapters 14, 18)? 6. **Sharpening versus discovery.** In RL with verifiable rewards, how can one tell whether a gain is a sharper distribution over solutions the base model could already sample, or a move outside its support (Chapter 18)? 7. **What does clipping do?** A clean statement of what PPO's clip enforces, and of how much of its success comes from other implementation choices (Chapter 13). 8. **Marketing as offline decision-making.** A media mix model is an offline policy-learning problem whose behaviour policy (past budgets) responded to unobserved demand. That is an instance of offline RL with unobserved confounding: coverage is not enough, one also needs identification. See the earlier essay [Deriving the Media Mix Model](../posts/mmm-derived.html), and the proposal in the PFN essay to amortise such inference with a prior over simulated worlds. recalled as a framing; nothing here is tested. 9. **Amortised Bayes-adaptive agents.** Can a prior-data fitted network over MDPs be trained so that in-context exploration approximates the Bayes-optimal policy of the belief MDP? How would one evaluate it against posterior sampling (Chapter 15)? 10. **Geometry of the optimisation.** Gradient methods move in policy space while the objective is linear in occupancy space. Is there a practical algorithm that exploits the linearity (mirror descent in $d$), and when does it beat PPO-type updates? ## 23. Exercises Each has an answer folded below it. The numbers can be reproduced with `assets/rl-model.js` and `scripts/check-rl-notes.cjs`. **1.** Solve the Bellman equation by hand for the café policy "Prepare when Quiet, Serve when Busy". Then compute $J$.
Answer With $P_\pi=\begin{pmatrix}0.2&0.8\\0.7&0.3\end{pmatrix}$ and $r_\pi=(0,1)^\top$, $(I-0.9P_\pi)V=r_\pi$ gives $V(\text{Quiet})=4.966$, $V(\text{Busy})=5.655$, and $J=\tfrac12(4.966+5.655)=5.310$.
**2.** Compare serving every period ($J=4.195$) with the optimum. How large is the gap in discounted reward, and which of $\mathcal T$'s properties guarantees that value iteration finds the optimum from any start?
Answer The gap is $5.310-4.195=1.115$. $\mathcal T$ is a $\gamma$-contraction in $\lVert\cdot\rVert_\infty$ (Chapter 3), so by Banach's theorem value iteration converges to the unique fixed point from any start, with $\lVert V_k-V^\star\rVert\le\gamma^k\lVert V_0-V^\star\rVert$.
**3.** Compute the occupancy of "Prepare when Quiet, Serve when Busy" and verify $J=\langle d,r\rangle/(1-\gamma)$.
Answer Solving $(I-\gamma P_\pi^\top)\rho=(1-\gamma)\mu$ gives $\rho=(0.469,0.531)$. The policy is deterministic, so $d(\text{Quiet},\text{Prepare})=0.469$, $d(\text{Busy},\text{Serve})=0.531$, and the others are zero. Then $\langle d,r\rangle=0.531\times1=0.531$ and $0.531/0.1=5.31$.
**4.** Prove that policy iteration never decreases the value, using the performance difference lemma.
Answer Let $\pi'$ be greedy for $Q^\pi$. Then $\sum_a\pi'(a\mid s)A^\pi(s,a)=\max_aA^\pi(s,a)\ge0$ for every $s$ (the maximum of numbers whose $\pi$-average is zero). The lemma gives $V^{\pi'}(s)-V^\pi(s)=\frac1{1-\gamma}\sum d^{\pi'}_s(s',a)A^\pi(s',a)\ge0$ as the occupancy is nonnegative.
**5.** In the two-state off-policy TD example of Chapter 11, find the threshold $\gamma$ above which equal state weighting diverges.
Answer With weights $(\tfrac12,\tfrac12)$ and features $(1,2)$ the expected drift of $w$ is $\big(\tfrac12(2\gamma-1)+\tfrac12\cdot2(2\gamma-2)\big)w=(3\gamma-2.5)w$. It is positive, hence unstable, exactly when $\gamma>5/6$.
**6.** Show that $\mathbb E[\max(Z_1,Z_2)]=1/\sqrt\pi$ for iid standard normals.
Answer $\max(a,b)=\tfrac12(a+b)+\tfrac12|a-b|$, and $\mathbb E[Z_1+Z_2]=0$. $Z_1-Z_2\sim\mathcal N(0,2)$, so $\mathbb E|Z_1-Z_2|=\sqrt2\sqrt{2/\pi}=2/\sqrt\pi$. Hence $\mathbb E\max=\tfrac12\cdot2/\sqrt\pi=1/\sqrt\pi\approx0.564$.
**7.** A GRPO group has $G=8$ and $3$ correct answers. Compute the two advantages and check they sum to zero.
Answer $\hat p=3/8$, population standard deviation $\sqrt{\hat p(1-\hat p)}=0.484$. Correct: $(1-\hat p)/0.484=1.291$; incorrect: $-\hat p/0.484=-0.775$. Check: $3\times1.291-5\times0.775=3.873-3.873=0$.
**8.** For $\pi_{\mathrm{ref}}=(0.5,0.3,0.2)$, rewards $(0,1,2)$ and $\beta=0.7$, compute the KL-regularised optimum and its value.
Answer Weights $\pi_{\mathrm{ref}}e^{r/\beta}=(0.5,\,1.251,\,3.482)$, sum $Z=5.234$. The optimum is $\pi^\star=(0.096,\,0.239,\,0.665)$ and the value is $\beta\log Z=0.7\times1.6552=1.159$.
**9.** In the constrained café (cost 1 for serving when Busy, budget $b=0.30$ on its discounted occupancy), why does the optimal policy randomise, and in which state?
Answer The unconstrained optimum spends $0.531$ of its occupancy serving when Busy, above the budget. The constraint cuts the polytope along the line $d(\text{Busy},\text{Serve})=0.3$, and the best point on the cut lies on the edge joining the corners "Prepare when Quiet" and "Serve when Quiet" (with Busy always serving), so only the Quiet decision is randomised: serve with probability $0.76$, giving $J=4.60$.
**10.** Derive the policy gradient for a single-state, softmax-parametrised, $K$-arm bandit and explain why a nearly deterministic wrong policy learns slowly.
Answer With $p_a=e^{\theta_a}/\sum e^{\theta}$ and $J=\sum_ap_ar_a$: $\partial J/\partial\theta_a=p_a(r_a-J)$, which is the formula of Chapter 13 with a single state and $\gamma=0$ (so the factor $1/(1-\gamma)$ and $d^\pi(s)$ are both 1). If $p_a\approx0$ for the best arm, the gradient on its logit is about $p_a\times(\text{its advantage})\approx0$: the update that would help is scaled by the probability the policy already assigns.
## 24. Glossary | Term | Meaning | | --- | --- | | Advantage | $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$ | | Bellman completeness | The function class is closed under the Bellman operator | | Bootstrapping | Updating an estimate from another estimate | | Certainty equivalence | Plan in the estimated model as if it were true | | Concentrability | Bound on the ratio $d^\pi/d^b$ | | Critic / actor | The value estimator / the policy | | Deadly triad | Function approximation, bootstrapping and off-policy learning together | | Effective horizon | $1/(1-\gamma)$ | | GAE | Generalised advantage estimation: geometric average of $n$-step advantages | | GLIE | Greedy in the limit with infinite exploration | | Occupancy | Normalised discounted state-action visitation $d^\pi$ | | Off-policy | Learning about one policy from data of another | | OPE | Off-policy evaluation | | Regret | Total reward lost relative to the optimal policy | | Semi-gradient | An update that ignores the dependence of the target on the parameters | | Successor features | Expected discounted future features; make value linear in reward weights | ## Further reading Verified against a source I opened (abstract or text) are linked; the rest are recalled from memory and should be looked up before being relied on. **Books and surveys** - [Sutton and Barto — *Reinforcement Learning: An Introduction*](http://incompleteideas.net/book/the-book-2nd.html). - [Puterman — *Markov Decision Processes*](https://onlinelibrary.wiley.com/doi/book/10.1002/9780470316887). The reference for the LP formulation and for dynamic programming. - Bertsekas and Tsitsiklis — *Neuro-Dynamic Programming* (1996); Szepesvári — *Algorithms for Reinforcement Learning* (2010); Lattimore and Szepesvári — *Bandit Algorithms* (2020); Agarwal, Jiang, Kakade and Sun — *Reinforcement Learning: Theory and Algorithms*. Levine, Kumar, Tucker and Fu — *Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems*. **Duality, planning and complexity** - [Manne — *Linear programming and sequential decisions*](https://doi.org/10.1287/mnsc.6.3.259) (1960). - [de Farias and Van Roy — *The linear programming approach to approximate dynamic programming*](https://doi.org/10.1287/opre.51.6.850.24925) (2003). - [Nachum and Dai — *Reinforcement Learning via Fenchel-Rockafellar Duality*](https://arxiv.org/abs/2001.01866) (2020). - [Ye — *The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate*](https://pubsonline.informs.org/doi/fpi/10.1287/moor.1110.0516) (2011). **Learning and exploration** - [Tsitsiklis — *Asynchronous stochastic approximation and Q-learning*](https://doi.org/10.1007/BF00993306) (1994); Watkins and Dayan — *Q-learning* (1992). - [Azar, Munos and Kappen — *Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model*](https://arxiv.org/abs/1206.6461) (2013). - [Auer, Cesa-Bianchi and Fischer — *Finite-time analysis of the multiarmed bandit problem*](https://doi.org/10.1023/A:1013689704352) (2002). - [Jaksch, Ortner and Auer — *Near-optimal regret bounds for reinforcement learning*](https://jmlr.org/papers/v11/jaksch10a.html) (2010). - [Azar, Osband and Munos — *Minimax regret bounds for reinforcement learning*](https://arxiv.org/abs/1703.05449) (2017). - [Jin, Allen-Zhu, Bubeck and Jordan — *Is Q-learning provably efficient?*](https://arxiv.org/abs/1807.03765) (2018). **Policy gradients** - [Agarwal, Kakade, Lee and Mahajan — *On the theory of policy gradient methods: optimality, approximation, and distribution shift*](https://arxiv.org/abs/1908.00261) (2021). - Sutton, McAllester, Singh and Mansour (2000), Kakade (2001), Schulman et al. (TRPO 2015, GAE 2016, PPO 2017), Silver et al. (DPG 2014), Haarnoja et al. (SAC 2018). **Offline RL** - [Jin, Yang and Wang — *Is pessimism provably efficient for offline RL?*](https://arxiv.org/abs/2012.15085) (2021). - [Rashidinejad, Zhu, Ma, Jiao and Russell — *Bridging offline reinforcement learning and imitation learning: a tale of pessimism*](https://arxiv.org/abs/2103.12021) (2021). - Fujimoto et al. (BCQ 2019), Kumar et al. (CQL 2020), Kostrikov et al. (IQL 2022), Munos and Szepesvári (2008). **Language models** - [Shao et al. — *DeepSeekMath* (GRPO)](https://arxiv.org/abs/2402.03300) (2024). - [Rafailov et al. — *Direct Preference Optimization*](https://arxiv.org/abs/2305.18290) (2023). - [Ahmadian et al. — *Back to basics: revisiting REINFORCE-style optimization for learning from human feedback in LLMs*](https://arxiv.org/abs/2402.14740) (2024). - [Gao, Schulman and Hilton — *Scaling laws for reward model overoptimization*](https://arxiv.org/abs/2210.10760) (2022). - [Lambert et al. — *Tülu 3*](https://arxiv.org/abs/2411.15124) (2024), which introduced RLVR. - [Liu et al. — *Understanding R1-Zero-like training: a critical perspective*](https://arxiv.org/abs/2503.20783) (2025). Title and authors confirmed; claims not. **On this site** - [Deriving Reinforcement Learning from the Bellman Equation](../posts/rl-derived.html): the geometric story with figures. - [Deriving the Prior-Data Fitted Network](../posts/pfn-derived.html) and [Deriving the Media Mix Model](../posts/mmm-derived.html): the in-context and marketing threads of Chapters 15 and 22. ## Changelog - 2026-10-25: first version. Chapters 0–24 drafted; numerical checks in `scripts/check-rl-notes.cjs`; Chapters 15, 18 and 19 rely most on recalled material and are the first to verify against sources.