Reinforcement Learning: Complete Reference

1. What Is Reinforcement Learning?

Reinforcement learning (RL) is the mathematical study of sequential decision-making under uncertainty. An agent interacts with an environment over discrete time steps. At each step the agent observes a state, chooses an action, and receives a scalar reward together with a new state. The objective is not to minimize a prediction error on a fixed dataset, as in supervised learning, but to choose a behavior policy that maximizes the total reward accumulated over time. This shifts the entire problem: data is not i.i.d., the agent's own choices affect what data it will see next (the distribution of visited states depends on the policy), and consequences of an action can be delayed by many steps.

Formally, at each discrete time $t = 0, 1, 2, \ldots$ the agent observes state $s_t \in \mathcal{S}$, samples action $a_t \sim \pi(\cdot|s_t)$ from its policy, the environment responds with reward $r_{t+1} \in \mathbb{R}$ and next state $s_{t+1} \sim P(\cdot|s_t,a_t)$. This loop repeats until a terminal state is reached (episodic) or forever (continuing). The agent's goal is to find $\pi^\star = \arg\max_\pi \mathbb{E}_\pi\left[\sum_t \gamma^t r_{t+1}\right]$.

Core vocabulary

RL vs supervised vs unsupervised learning

• Supervised learning: fixed dataset of $(x,y)$ pairs, i.i.d. samples, a single differentiable loss (cross-entropy, MSE). The gradient of the loss with respect to model output is directly computable.
• Unsupervised learning: discover structure (clusters, density, latent factors) with no labels at all.
• Reinforcement learning: data is generated by the agent's own behavior (on-policy data is non-stationary as the policy changes); the only feedback is a scalar reward, which may be delayed by many steps from the action that caused it (the credit assignment problem); and there is a fundamental exploration-exploitation dilemma — the agent must sometimes choose actions it believes are suboptimal purely to gather information that could improve future decisions.

Why credit assignment is hard

Suppose an agent plays a 200-move game of chess and wins. The single reward of $+1$ arrives only at the terminal move, yet the outcome was influenced by decisions made 150 moves earlier. Naive supervised learning has no mechanism to decide which of the 200 moves "caused" the win. RL solves this with bootstrapped value estimates (an intermediate quantity $V(s)$ or $Q(s,a)$ that lets reward information propagate backward through the trajectory one edge at a time) and, in the policy-gradient family, by re-weighting the log-probability of every action taken in the trajectory by the return that followed it. Both mechanisms are covered in full below.

Refer: Sutton & Barto: Reinforcement Learning: An Introduction · A Brief Survey of Deep RL (Arulkumaran et al.)

2. Markov Decision Processes (MDPs)

An MDP is the standard mathematical framework used to formalize an RL problem. It is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma, \mu_0)$:

• $\mathcal{S}$: state space, discrete or continuous
• $\mathcal{A}$: action space, discrete or continuous
• $P(s_{t+1}|s_t, a_t)$: transition kernel, a probability distribution over next states for every state-action pair
• $R(s_t, a_t, s_{t+1})$ or expected reward $R(s,a) = \mathbb{E}_{s' \sim P(\cdot|s,a)}[R(s,a,s')]$
• $\gamma$: discount factor
• $\mu_0$: initial state distribution, $s_0 \sim \mu_0$

Markov property

The future is conditionally independent of the past given the present:

This is not an assumption about the physical world; it is a modeling choice about what we put into the state. Any process can be made Markov by enlarging the state to include enough history (e.g. stacking the last $k$ frames in Atari to recover velocity information that a single frame lacks). The practical engineering skill in RL is choosing a state representation that is Markov, or close enough to Markov that the resulting approximation error is tolerable.

Episodic vs continuing tasks

• Episodic: the process reaches an absorbing terminal state after a finite (possibly random) number of steps; the return is well defined even with $\gamma=1$ because the sum is finite. Games, one robotic pick-and-place attempt, and a single LLM response generation (terminating at the end-of-sequence token) are episodic.
• Continuing: there is no terminal state; the process runs forever. The return $\sum_{t=0}^\infty \gamma^t r_{t+1}$ must be discounted ($\gamma<1$) to remain finite unless the average-reward formulation is used instead: $\rho^\pi = \lim_{T\to\infty} \frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1} r_{t+1}\right]$, common in queueing and resource-allocation problems.

Partially Observable MDPs (POMDPs)

A POMDP adds an observation space $\mathcal{O}$ and emission function $O(o|s,a)$; the agent receives $o_t$, not the true state $s_t$. Optimal behavior in a POMDP is a function of the entire observation-action history, or equivalently of the belief state $b_t(s) = P(s_t = s \mid o_0, a_0, \ldots, o_t)$, updated by Bayes' rule at every step:

Belief-state planning is exact but the belief space is continuous and high-dimensional even for small $|\mathcal{S}|$, so exact POMDP solvers (e.g. point-based value iteration) scale poorly. In deep RL the standard workaround is to approximate the belief implicitly with a recurrent network (LSTM/GRU) or a transformer that attends over the recent observation history, letting the network learn whatever sufficient statistic it needs rather than computing the Bayesian belief explicitly. Frame-stacking (stack the last $k$ raw observations as the state) is a cheap, effective special case that works when the missing information (e.g. velocity from consecutive positions) has a short memory horizon.

Policy types

• Deterministic: $a = \mu(s)$, a single action per state. Used in DDPG/TD3.
• Stochastic: $\pi(a|s)$, a distribution over actions. Necessary for exploration during learning, for well-defined policy-gradient theory (the log-probability gradient is undefined for a deterministic policy without extra machinery), and for game-theoretic settings where a deterministic policy can be exploited (e.g. rock-paper-scissors, where the unique Nash equilibrium is the uniform stochastic policy).
• Markovian: depends only on the current state (or observation / belief), not on the full history.

Existence and structure of the optimal policy

For any finite MDP with bounded rewards, there exists an optimal policy that is (a) stationary — does not depend on $t$ — and (b) deterministic. This is a non-obvious but classical result: even though stochastic policies form a strictly larger search space, the best stochastic policy can never beat the best deterministic one, because $V^*(s) = \max_a Q^*(s,a)$ is achieved by concentrating all probability mass on the maximizing action. Stochastic policies remain useful anyway, purely as an exploration and optimization device during learning.

3. Returns, Discounting, and Value Functions

Return (cumulative reward)

The return satisfies the recursive identity $G_t = R_{t+1} + \gamma G_{t+1}$, which is the seed of every Bellman equation in this document.

Effective horizon

A useful rule of thumb: the "effective horizon" of a discount factor is roughly $1/(1-\gamma)$ steps, since $\gamma^{1/(1-\gamma)} \approx e^{-1} \approx 0.37$. So $\gamma=0.99$ corresponds to caring meaningfully about roughly the next 100 steps, and $\gamma=0.999$ about the next 1000. Choosing $\gamma$ too small biases the agent toward short-sighted, sometimes catastrophically wrong, behavior (e.g. a driving agent that brakes too late because braking early costs a tiny discounted penalty it doesn't value); choosing $\gamma$ too close to 1 increases the variance of Monte Carlo return estimates and can slow learning.

State-value function

$V^\pi(s)$ answers: "if I am in state $s$ and follow policy $\pi$ from now on, how much total discounted reward do I expect?" It depends on the policy because different policies visit different future states and take different actions in them.

Action-value function (Q-function)

$Q^\pi(s,a)$ answers: "if I am in state $s$, take action $a$ right now (possibly not the action $\pi$ would have chosen), and follow $\pi$ thereafter, how much total discounted reward do I expect?" Because $Q$ conditions on the immediate action, a greedy policy can be extracted from it directly without needing a model of the environment: $\pi(s) = \arg\max_a Q(s,a)$. This is precisely why value-based methods (Q-learning, DQN) can be model-free while still supporting planning-like one-step lookahead.

Advantage function

Advantage measures how much better action $a$ is than the policy's own average action in state $s$. By construction $\mathbb{E}_{a\sim\pi(\cdot|s)}[A^\pi(s,a)] = 0$ for every $s$: the advantage of the average action under $\pi$ is exactly zero. Positive advantage means "do more of this than $\pi$ currently does"; negative means "do less." Policy gradients use advantages instead of raw returns or Q-values specifically because centering around zero removes a huge, state-dependent additive constant from the learning signal, which is the single biggest source of variance reduction available without introducing bias (proved formally in section 10.3).

Optimal policy and optimal value functions

There exists an optimal policy that is deterministic and satisfies $\pi^*(a|s) > 0 \iff Q^*(s,a) = \max_{a'} Q^*(s,a')$. All optimal policies share the same $V^*$ and $Q^*$, even though there can be more than one optimal policy when several actions tie for the maximum.

Worked numeric example

Consider a 1-state, 2-action bandit-like MDP that always terminates after one step: action $a_1$ gives reward $10$ with probability $0.5$ and reward $0$ otherwise; action $a_2$ always gives reward $4$. Then $Q^\pi(s,a_1)=5$, $Q^\pi(s,a_2)=4$ regardless of $\pi$ (since the episode ends immediately, $Q$ does not depend on future behavior). $V^\pi(s) = \pi(a_1|s)\cdot 5 + \pi(a_2|s)\cdot 4$. The optimal policy places all probability on $a_1$, giving $V^*(s)=5$. If $\pi$ is $\epsilon$-greedy with $\epsilon=0.2$ favoring $a_1$: $V^\pi(s) = 0.9(5)+0.1(4)=4.9$. The advantage $A^\pi(s,a_1) = 5-4.9=0.1$, $A^\pi(s,a_2)=4-4.9=-0.9$, and indeed $0.9(0.1)+0.1(-0.9)=0$, confirming the zero-mean property.

4. Bellman Equations: Derivation and Intuition

4.1 Bellman expectation equation for $V^\pi$

Start from the definition and split the sum at the first reward, using $G_t = R_{t+1}+\gamma G_{t+1}$:

By the tower rule of expectation, condition first on the action taken, then on the resulting next state, and use the Markov property so that $\mathbb{E}[G_{t+1}\mid S_{t+1}=s'] = V^\pi(s')$:

4.2 Bellman expectation equation for $Q^\pi$

Read right to left: from $(s,a)$, the environment gives a reward and a next state $s'$; from $s'$, the policy picks $a'$ and the value continues as $Q^\pi(s',a')$.

4.3 Bellman optimality equations

4.4 Contraction property (why iterative methods converge)

Define the Bellman optimality operator on value functions, $(\mathcal{T}^*V)(s) = \max_a\sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma V(s')]$. For any two value functions $V_1,V_2$:

This holds because the max operator is non-expansive ($|\max_a f(a) - \max_a g(a)| \le \max_a|f(a)-g(a)|$) and the expectation over $P$ is a convex combination, also non-expansive; the only contraction factor comes from the explicit $\gamma$ multiplying $V$. Since $\gamma<1$, repeated application of $\mathcal{T}^*$ to any starting $V_0$ converges geometrically to the unique fixed point $V^*$, at rate $\gamma^k$ after $k$ iterations. The same argument applies to $\mathcal{T}^\pi$ (the policy evaluation operator) converging to $V^\pi$, and to the tabular Q-learning and value-iteration updates below.

4.5 Relationship between $V$ and $Q$

5. Dynamic Programming (Model-Based Tabular)

When $P$ and $R$ are fully known and $\mathcal{S}, \mathcal{A}$ are small and discrete, DP computes optimal policies exactly without any environment interaction. DP requires full sweeps over the state space at every iteration, which becomes infeasible as $|\mathcal{S}|$ grows (the "curse of dimensionality" — a robot with 10 continuous joints discretized into 100 bins each has $100^{10}$ states), but it is the conceptual foundation every subsequent RL algorithm approximates.

5.1 Policy evaluation

Iteratively apply the Bellman expectation operator until convergence:

Converges to $V^\pi$ as $k \to \infty$ because this is exactly the $\gamma$-contraction $\mathcal{T}^\pi$ described above. In practice, exact convergence is never needed; a fixed number of sweeps (or a small tolerance $\|V_{k+1}-V_k\|_\infty < \theta$) suffices for policy improvement to make progress.

5.2 Policy improvement theorem

Define the greedy policy with respect to $V^\pi$:

Theorem: $V^{\pi'}(s) \geq V^\pi(s)$ for all $s$, with strict inequality at some $s$ unless $\pi$ is already optimal.

5.3 Policy iteration

1. Evaluate $V^\pi$ (exactly, by solving the linear system $V=R^\pi+\gamma P^\pi V$, or iteratively).
2. Improve: $\pi \leftarrow \text{greedy}(V^\pi)$.
3. Repeat until the policy is stable (no state changes its greedy action).

Policy iteration converges to $\pi^*$ in a finite number of iterations for finite MDPs, because there are only finitely many deterministic policies and each iteration strictly improves (or terminates). In practice it often converges in surprisingly few iterations (dozens) even for MDPs with thousands of states, because each round performs a "hard" improvement affecting many states simultaneously.

5.4 Value iteration

Combines evaluation and improvement into a single sweep by applying $\mathcal{T}^*$ directly, rather than fully evaluating each intermediate policy. Extract the greedy policy only after convergence (or after enough sweeps that $\|V_{k+1}-V_k\|_\infty$ is below a stopping tolerance $\theta$, which bounds the sub-optimality of the extracted policy by $\frac{2\gamma\theta}{1-\gamma}$).

5.5 Asynchronous and prioritized sweeping

Standard DP updates every state on every sweep. Asynchronous DP updates states in any order, even skipping some, as long as every state keeps getting updated infinitely often in the limit — convergence still holds because each individual update is still a contraction toward the fixed point. Prioritized sweeping maintains a priority queue keyed by the magnitude of the Bellman error $|\max_a\sum_{s'}P(s'|s,a)[R+\gamma V(s')] - V(s)|$ and always updates the state with the largest error next, which propagates value changes through the state graph far faster than uniform sweeps, especially in sparse-reward domains.

# Tabular value iteration (toy example)
import numpy as np

V = np.zeros(n_states)
for _ in range(1000):
    V_new = np.zeros(n_states)
    for s in range(n_states):
        q_sa = []
        for a in range(n_actions):
            q = sum(P[s, a, sp] * (R[s, a, sp] + gamma * V[sp]) for sp in range(n_states))
            q_sa.append(q)
        V_new[s] = max(q_sa)
    V = V_new
    # policy extraction after convergence:
    # pi[s] = argmax_a sum_sp P[s,a,sp] * (R[s,a,sp] + gamma * V[sp])

6. Monte Carlo Methods

MC methods learn from complete episodes of real experience without ever needing $P$ or $R$ explicitly. No bootstrapping: they use the actual observed return $G_t$, computed by summing real rewards to the end of the episode, as the learning target. This makes MC estimates unbiased but high-variance, and it requires episodic tasks (or at least a way to truncate and bootstrap at the horizon).

6.1 MC prediction

Estimate $V^\pi(s)$ by averaging the returns observed after every visit to $s$ across many sampled episodes:

Incremental (running-mean) form, useful for online updates and for non-stationary problems with a fixed step size $\alpha$ instead of $1/N(s)$:

6.2 First-visit vs every-visit MC

• First-visit: count the return only at the first occurrence of $s$ within an episode. Each episode contributes an i.i.d. sample per state (assuming episodes are independent), which makes the standard law-of-large-numbers convergence argument immediate.
• Every-visit: count the return at every occurrence of $s$ within an episode, even if $s$ recurs. Samples within an episode are then correlated, but every-visit MC still converges to $V^\pi(s)$ under standard conditions (and is typically preferred in practice because it uses data more efficiently).

6.3 MC control (on-policy)

Alternate policy evaluation (estimate $Q^\pi$ by MC, since a model-free greedy improvement needs $Q$, not $V$, to avoid requiring $P$) and policy improvement using an $\epsilon$-soft policy to keep exploring:

GLIE (Greedy in the Limit with Infinite Exploration) is the condition that guarantees convergence of MC control to $Q^*$: every state-action pair must be visited infinitely often, and the policy must converge to the greedy policy in the limit. A common schedule that satisfies GLIE is $\epsilon_k = 1/k$ where $k$ is the episode index.

6.4 Off-policy MC and importance sampling

Learn about a target policy $\pi$ from data collected by a different behavior policy $b$ (this is essential when you want to reuse old data, learn about a deterministic greedy target while behaving exploratorily, or learn many target policies from one stream of experience — the "Horde" architecture). Weight each observed return by the likelihood ratio between the two policies along the trajectory:

Ordinary importance sampling is unbiased but can have unbounded (even infinite) variance, because $\rho$ is a product of ratios that can blow up over long trajectories. Weighted importance sampling normalizes by the sum of weights, which introduces a small bias (vanishing as sample size grows) in exchange for dramatically lower variance — nearly always the better practical choice. Note $b$ must have coverage of $\pi$: $\pi(a|s)>0 \implies b(a|s)>0$ for every $(s,a)$ that $\pi$ might visit, or the ratio is undefined.

7. Temporal-Difference Learning

TD methods bootstrap: they update value estimates using other value estimates rather than waiting for a full-episode return. TD is the hybrid of MC (learn from real sampled experience, no need for a model) and DP (bootstrap off existing estimates, don't wait for the episode to end). This combination is what makes TD the workhorse of essentially all practical RL: it can learn online, step by step, from incomplete episodes, and even in continuing (non-episodic) tasks.

7.1 TD(0) for prediction

The bracketed term is the TD error:

$R_{t+1}+\gamma V(S_{t+1})$ is called the TD target: a one-step-lookahead, bootstrapped estimate of the true return $G_t$. Unlike the MC target $G_t$ itself, the TD target has lower variance (it depends on only one random transition, not the entire rest of the trajectory) but is biased whenever $V$ is not yet accurate, since it partly trusts a possibly-wrong estimate $V(S_{t+1})$.

7.2 Bias–variance tradeoff: MC vs TD

7.3 SARSA (on-policy control)

Named after the quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ needed for the update. SARSA learns the Q-values of the policy it is actually following, including its exploratory noise — it is on-policy. Concretely, if the behavior is $\epsilon$-greedy, SARSA's $Q$ reflects the risk of occasionally taking a random (possibly bad) action, so it learns a policy that is naturally cautious near dangerous states (the classic Cliff Walking example: SARSA hugs a safer path away from the cliff edge because it accounts for the chance of a random slip, whereas Q-learning below walks right along the edge because it evaluates the greedy policy, ignoring its own exploration noise).

7.4 Q-learning (off-policy control)

Uses the max over next actions rather than the action actually taken. It learns $Q^*$ directly, decoupled from the behavior policy used to generate data (which can be any exploratory policy, e.g. $\epsilon$-greedy) — it is off-policy. This is what makes replay buffers possible: transitions collected under an old, different policy remain valid training data for Q-learning's target.

7.5 Maximization bias and Double Q-learning

Q-learning's $\max_a Q(S_{t+1},a)$ is a biased estimator of $\mathbb{E}[\max_a Q^*(S_{t+1},a)]$ whenever $Q$ is itself a noisy estimate: $\mathbb{E}[\max_a \hat{Q}(s,a)] \geq \max_a \mathbb{E}[\hat{Q}(s,a)]$ by Jensen's inequality applied to the convex $\max$ function, so the same noisy values that are used to pick the best action are also used to evaluate it, systematically over-estimating $Q$. Double Q-learning fixes this by maintaining two independent estimators $Q_1, Q_2$; use one to select the action and the other to evaluate it:

(with the roles of $Q_1, Q_2$ swapped with probability $0.5$ at each step). This decouples selection from evaluation and removes the positive bias.

7.6 Expected SARSA

Instead of sampling a single next action (SARSA) or taking the max (Q-learning), Expected SARSA averages over the full action distribution under $\pi$. This eliminates the sampling variance from $A_{t+1}$ entirely, at the cost of a slightly more expensive update ($O(|\mathcal{A}|)$ instead of $O(1)$). It generalizes both algorithms: it equals Q-learning when $\pi$ is greedy, and equals ordinary SARSA in expectation when $\pi$ is the behavior policy.

7.7 N-step returns

N-step return bridges 1-step TD and full-episode MC:

N-step SARSA / Q-learning use $G_t^{(n)}$ as the update target. As $n\to\infty$ (or to episode end) this recovers the MC target; $n=1$ recovers ordinary TD(0). Larger $n$ reduces bias (relies less on a possibly-inaccurate bootstrapped $V$) but increases variance (accumulates more random rewards). Intermediate $n$ (e.g. 3–10 in practice) often trains fastest, which is exactly the empirical motivation behind Rainbow's use of multi-step returns and behind GAE in the policy-gradient setting (section 11.2).

7.8 TD($\lambda$) and eligibility traces

Rather than picking one fixed $n$, TD($\lambda$) forms a target that is an exponentially-weighted average over all n-step returns simultaneously, with weight $(1-\lambda)\lambda^{n-1}$ on the $n$-step return, so the weights sum to 1:

This is the "forward view" — it requires knowledge of the future. The equivalent, and practically implementable, "backward view" uses eligibility traces $E_t(s)$, a decaying memory of which states were recently visited:

At each step, the current one-step TD error $\delta_t$ is broadcast backward to every recently-visited state, weighted by how recently and how frequently it was visited (its eligibility). This lets credit propagate over many steps within a single pass through the data, and it is mathematically equivalent (exactly, in the offline case) to the forward-view $\lambda$-return. $\lambda=0$ recovers TD(0); $\lambda=1$ recovers (a close cousin of) every-visit MC.

# Tabular Q-learning
import numpy as np

Q = np.zeros((n_states, n_actions))
for episode in range(num_episodes):
    s = env.reset()
    done = False
    while not done:
        a = epsilon_greedy(Q[s], eps)
        s_next, r, done, _ = env.step(a)
        Q[s, a] += alpha * (r + gamma * Q[s_next].max() - Q[s, a])
        s = s_next

On-policy vs off-policy

8. Planning and Model-Based RL

8.1 Dyna-Q

Interleave real experience with simulated experience generated from a learned model $\hat{P}, \hat{R}$ (for deterministic or small discrete environments, a simple lookup table of observed transitions suffices as the model):

1. Act in the real environment, observe $(s,a,r,s')$, update $Q$ with an ordinary Q-learning update.
2. Update the model with the observed transition: $\hat{P}(s'|s,a) \leftarrow$ observed, $\hat{R}(s,a) \leftarrow r$.
3. Run $n$ planning steps: repeatedly sample a previously-seen $(s,a)$, simulate $(r,s')$ from the model, and apply the same Q-learning update to these imagined transitions.

Every additional planning step is essentially free extra training data mined from experience the agent already has, dramatically improving sample efficiency in domains where the model is easy to learn (deterministic or low-noise dynamics).

8.2 Monte Carlo Tree Search (MCTS)

MCTS builds an asymmetric search tree online, at decision time, by running many simulations, each consisting of four phases:

1. Selection: starting at the root, traverse the tree choosing the child that maximizes an upper-confidence bound (UCB1, below) until reaching a node with unexpanded children (a leaf of the current tree).
2. Expansion: add one or more child nodes for untried actions at that leaf.
3. Simulation (rollout): from the new node, play out to a terminal state (or a fixed depth) using a fast default policy (random, or a learned policy network as in AlphaZero) to obtain an outcome estimate.
4. Backpropagation: propagate the simulation's outcome back up every node on the path, incrementing visit counts $N(s,a)$ and updating action-value estimates $Q(s,a)$.

UCB1, used for action selection at each node during selection, balances exploitation of high-value actions against exploration of rarely-tried ones:

The exploration bonus shrinks as $N(s,a)$ grows (that action has been tried often, its estimate is trustworthy) but grows with $\ln N(s)$ (the more total visits to the parent, the more we should reconsider under-tried siblings). AlphaZero's variant, PUCT, additionally weights the exploration bonus by a learned prior policy $P(s,a)$ from a neural network, focusing search on moves the network considers plausible: $\text{PUCT}(s,a) = Q(s,a) + c\, P(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)}$. MCTS combined with deep value/policy networks powered AlphaGo and AlphaZero; in modern LLM reasoning, tree-search variants over token or reasoning-step "actions" are used at inference time to improve answer quality via structured search rather than a single greedy decode.

8.3 Model-based deep RL

• World models (Dreamer, MuZero): learn a compact latent dynamics model $z_{t+1} = f(z_t, a_t)$ from raw observations, and plan or train a policy entirely "in imagination" by unrolling the latent model, never touching the real environment during the inner training loop. MuZero notably does not even require the model to predict raw observations — it only needs to predict reward, value, and policy consistently, which is sufficient for planning with MCTS.
• MBPO, PETS: use probabilistic ensembles of dynamics models (to capture epistemic uncertainty and avoid a single overconfident model being exploited by the policy) for sample-efficient continuous control, typically generating short simulated rollouts (a few steps) branching from real states to augment a model-free algorithm's training data.
• Tradeoff: model error compounds multiplicatively over long simulated rollouts (small per-step errors accumulate exponentially in rollout length), so model-based methods generally use short imagined horizons and periodically re-ground in real data, or continuously refine the policy with a mix of real and imagined transitions rather than trusting the model indefinitely.

9. Function Approximation and Deep RL

Tabular methods store one number per state (or state-action pair) and fail outright when $|\mathcal{S}|$ or $|\mathcal{A}|$ is huge (e.g. every possible pixel-image observation) or continuous (e.g. joint angles of a robot arm). The fix is to approximate value or policy with a parameterized function: $V(s;\mathbf{w})$, $Q(s,a;\mathbf{w})$, or $\pi(a|s;\boldsymbol{\theta})$, typically a neural network, and to generalize across similar states via shared parameters rather than storing every state independently.

9.1 Linear function approximation

Semi-gradient TD update (the term "semi-gradient" reflects that the target $R+\gamma V(S_{t+1};\mathbf{w})$ itself depends on $\mathbf{w}$, but we deliberately do not differentiate through it, treating it as a fixed target — differentiating through it would give a different, and generally worse, algorithm called "residual gradient"):

Convergence to a well-defined fixed point is guaranteed on-policy with linear function approximation. Off-policy linear TD can diverge — the classic counterexample is Baird's "star" MDP, where semi-gradient off-policy TD(0) provably diverges even though the true $V^\pi$ is representable by the chosen features.

9.2 The deadly triad

Instability and divergence risk arise specifically from combining all three of:

1. Function approximation (generalizing means an update to one state's value inevitably perturbs the estimated values of other, similar states)
2. Bootstrapping (TD-style updates whose targets depend on the very estimates being updated, unlike MC targets which are independent of current estimates)
3. Off-policy learning (updating value estimates for a distribution of states different from the one actually being sampled, which decouples the update dynamics from the sampling distribution in a way that can break the contraction argument that guarantees on-policy convergence)

Any two of the three are safe; all three together admit provable divergence. DQN mitigates the risk (without eliminating it in principle) with two specific engineering devices: experience replay and target networks, both described next.

9.3 Deep Q-Network (DQN)

• Experience replay $\mathcal{D}$: store transitions in a large circular buffer and sample random mini-batches for each gradient step. This breaks the strong temporal correlation between consecutive transitions (which would otherwise violate the i.i.d. assumption implicit in SGD and cause catastrophic forgetting of earlier experience) and reuses each transition for many gradient updates, greatly improving sample efficiency.
• Target network $\mathbf{w}^-$: a frozen (or slowly-updated) copy of the network parameters, used only to compute the bootstrapped target, and periodically synced to the online network (every $C$ steps, hard update) or smoothly tracked (Polyak/exponential-moving-average update $\mathbf{w}^- \leftarrow \tau\mathbf{w} + (1-\tau)\mathbf{w}^-$ with small $\tau$, soft update). Without a target network, the regression target moves every single gradient step (since it's computed by the same network being trained), which is analogous to chasing a moving target and empirically causes severe oscillation or divergence.

9.4 DQN extensions

# Minimal DQN-style update (PyTorch sketch)
target = r + gamma * q_target(s_next).max(dim=1).values * (1 - done)
loss = F.mse_loss(q_online(s, a), target)
optimizer.zero_grad()
loss.backward()
optimizer.step()
# periodically: q_target.load_state_dict(q_online.state_dict())

10. Policy Gradient Methods

Instead of learning a value function and deriving a policy from it implicitly (value-based methods), policy gradient methods directly parameterize and optimize the policy $\pi_\theta(a|s)$ by gradient ascent on the expected return $J(\boldsymbol{\theta}) = \mathbb{E}_{\pi_\theta}[G_0]$. This is essential whenever the action space is continuous or extremely large (taking a $\max$ or $\arg\max$ over it, as value-based methods require, is intractable), and it naturally produces stochastic policies, useful in partially observable or game-theoretic settings.

10.1 Policy gradient theorem

10.2 REINFORCE (Monte Carlo policy gradient)

Uses the actual sampled full return $G_t$ as an unbiased Monte Carlo estimate of $Q^{\pi_\theta}(S_t,A_t)$. The estimator is unbiased but has very high variance, because $G_t$ depends on the entire stochastic remainder of the trajectory — every random action and every random transition from $t$ onward contributes noise, and this noise does not shrink as the trajectory gets longer.

10.3 Baseline for variance reduction

Subtract any baseline $b(S_t)$ that does not depend on the action $A_t$:

# REINFORCE (PyTorch sketch)
log_probs = []
rewards = []
for t in range(T):
    dist = policy(s_t)
    a_t = dist.sample()
    log_probs.append(dist.log_prob(a_t))
    rewards.append(r_t)

returns = compute_discounted_returns(rewards, gamma)
returns = (returns - returns.mean()) / (returns.std() + 1e-8)  # simple baseline
loss = -sum(lp * G for lp, G in zip(log_probs, returns))
loss.backward()

11. Actor-Critic and Advantage Estimation

11.1 Actor-Critic architecture

• Actor $\pi_\theta(a|s)$: the policy, updated by policy gradient.
• Critic $V_\mathbf{w}(s)$ or $Q_\mathbf{w}(s,a)$: a learned value estimate, trained by TD, used to (a) provide a low-variance baseline and (b) bootstrap so the actor does not need to wait for a full-episode return before updating.

Because $\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)$ (when $V$ is exact), the one-step TD error is itself an unbiased, low-variance estimate of the advantage — this is why actor-critic replaces the slow, high-variance Monte Carlo return of REINFORCE with a fast, bootstrapped, online update, at the cost of the small bias introduced whenever $V$ is not yet perfectly learned.

11.2 Generalized Advantage Estimation (GAE)

GAE generalizes the n-step-return bias–variance tradeoff (section 7.7) to advantage estimation. Define the one-step TD error at every timestep:

and form an exponentially-weighted sum of these errors, analogous to the TD($\lambda$) backward view:

$\lambda = 0$ collapses this to the one-step TD advantage estimate $\delta_t$ alone (low variance, high bias if $V$ is inaccurate). $\lambda = 1$ recovers the full Monte Carlo advantage estimate $G_t - V(S_t)$ (low bias, high variance). Intermediate $\lambda$ (commonly $0.9$–$0.97$) interpolates, and is what nearly every modern on-policy algorithm (PPO, TRPO, A2C) uses in practice because it consistently trains faster and more stably than either extreme.

In practice GAE is computed backward through a finite rollout of length $T$ with a recursive formula, avoiding the need to sum an infinite series explicitly:

11.3 A2C / A3C

• A2C (Advantage Actor-Critic): synchronous, multiple parallel environment workers collect a batch of rollouts, gradients are averaged and applied in a single synchronized update. Simpler to implement and debug, plays well with GPU batching.
• A3C (Asynchronous Advantage Actor-Critic): multiple CPU workers each maintain their own copy of the network, interact with their own environment instance, and apply gradients asynchronously to a shared set of parameters (Hogwild-style, no locking). Historically important for scaling RL without GPUs, but the asynchrony introduces stale-gradient noise, and in practice A2C with vectorized environments on modern hardware generally matches or beats A3C at equal compute while being far simpler.

12. Natural Gradients, TRPO and PPO

12.1 Why raw policy gradient steps are dangerous

A vanilla policy-gradient step $\theta \leftarrow \theta + \alpha \nabla_\theta J$ treats all parameters as living in ordinary Euclidean space, but a fixed-size step in parameter space can correspond to an arbitrarily large or small change in the actual output distribution $\pi_\theta(\cdot|s)$, depending on the local curvature of the policy's parameterization. A single overly-large update can catastrophically shift the policy into a much worse region of behavior (and because the policy also controls what data is collected next, a bad policy leads to bad data, leading to bad gradients, in a vicious feedback loop that can permanently collapse performance — unlike supervised learning, there is no fixed validation set to catch this early).

12.2 Natural policy gradient

The natural gradient rescales the ordinary gradient by the inverse of the Fisher information matrix $F(\theta) = \mathbb{E}_{s,a\sim\pi_\theta}\left[\nabla_\theta \log\pi_\theta(a|s)\,\nabla_\theta\log\pi_\theta(a|s)^\top\right]$, which locally approximates the KL divergence between $\pi_\theta$ and a nearby $\pi_{\theta+\Delta\theta}$ as $\text{KL}(\pi_\theta\|\pi_{\theta+\Delta\theta}) \approx \frac12 \Delta\theta^\top F(\theta)\Delta\theta$:

This produces a step of constant size in distribution space (measured by KL divergence) rather than constant size in raw parameter space, which is exactly the geometry that matters for a policy. The practical obstacle is that $F(\theta)^{-1}$ is a $d\times d$ matrix for $d$ parameters, infeasible to form or invert explicitly for a deep network with millions of parameters.

12.3 TRPO: trust region motivation and constrained objective

TRPO solves the natural-gradient computational problem by (a) using conjugate gradient to solve $F(\theta)\,x = \nabla J$ approximately without ever forming $F^{-1}$ explicitly (only Fisher-vector products $F\cdot v$ are needed, computable efficiently by automatic differentiation), and (b) explicitly enforcing a trust-region constraint rather than taking an unconstrained natural-gradient step, guaranteeing monotonic improvement.

12.4 Surrogate objective (policy improvement lower bound)

where $r_t(\boldsymbol{\theta}) = \frac{\pi_\theta(A_t|S_t)}{\pi_{\theta_{\text{old}}}(A_t|S_t)}$ is the probability ratio. This surrogate is derived from the exact policy-improvement identity $J(\pi) - J(\pi_{\text{old}}) = \mathbb{E}_{s\sim d^\pi, a\sim\pi}[A^{\pi_{\text{old}}}(s,a)]$ by approximating the true (hard to sample) state distribution $d^\pi$ of the new policy with the state distribution of the old policy (an approximation valid only when $\pi$ and $\pi_{\text{old}}$ are close), while correcting for the change in action distribution exactly via importance sampling with $r_t(\theta)$. This is precisely why a trust-region (or clipping) constraint is not just an engineering convenience but mathematically necessary — the surrogate's accuracy as an approximation to the true objective degrades as the policies diverge.

12.5 TRPO constraint

Solved approximately per update by: (1) compute the gradient $g=\nabla_\theta L^{\text{CPI}}$; (2) use conjugate gradient to approximately solve $F x = g$ for the natural-gradient direction $x$; (3) compute a step size via the analytic trust-region formula $\beta = \sqrt{2\delta / (x^\top F x)}$; (4) perform a backtracking line search along $\beta x$, shrinking the step until both the KL constraint is satisfied and the surrogate objective actually improves (guarding against the fact that the quadratic KL approximation and the linear objective approximation are only locally accurate).

12.6 PPO-Clip objective

PPO replaces TRPO's expensive second-order conjugate-gradient machinery with a much simpler first-order surrogate that achieves a similar trust-region effect purely through clipping:

12.7 PPO full loss (typical implementation)

Value loss $L^{\text{VF}} = (V_\theta(S_t) - V_t^{\text{target}})^2$, often itself clipped analogously to the policy ratio to prevent the value function from moving too far in one update. Entropy bonus $S[\pi_\theta](s) = -\sum_a \pi_\theta(a|s)\log\pi_\theta(a|s)$ directly rewards higher-entropy (more exploratory, less deterministic) action distributions, counteracting the natural tendency of policy gradient methods to collapse toward a narrow, overconfident distribution too early.

12.8 PPO implementation details that matter in practice

• Multiple epochs per batch: PPO reuses each collected rollout for several (commonly 3–10) gradient epochs, re-computing the ratio $r_t(\theta)$ against the fixed $\pi_{\theta_{\text{old}}}$ each time — this is exactly what makes clipping necessary, since without it repeated epochs on the same data could push the ratio arbitrarily far from 1.
• Advantage normalization: normalize $\hat{A}_t$ to zero mean and unit variance across each mini-batch before use, which empirically stabilizes the scale of policy gradient updates across very different reward magnitudes.
• Early stopping on KL: some implementations monitor the empirical KL divergence between $\pi_\theta$ and $\pi_{\theta_{\text{old}}}$ during the multiple epochs and stop early if it exceeds a target threshold, as an extra safety net beyond clipping alone.
• Orthogonal weight initialization and learning-rate annealing are common, empirically important stabilizers noted across PPO reimplementation studies.

# PPO clipped objective (PyTorch)
ratio = (log_probs - old_log_probs).exp()
surr1 = ratio * advantages
surr2 = ratio.clamp(1 - eps, 1 + eps) * advantages
policy_loss = -torch.min(surr1, surr2).mean()

PPO is the default RL algorithm for classic RLHF in InstructGPT-style pipelines, many open-source alignment stacks, and robotics sim-to-real when sample budgets allow large batch, multi-epoch updates. Its appeal is a favorable combination of implementation simplicity, hyperparameter robustness, and reliable monotonic-ish improvement, at some cost in sample efficiency relative to off-policy alternatives.

13. Continuous Control: DDPG, TD3, SAC

13.1 DDPG (Deep Deterministic Policy Gradient)

Off-policy actor-critic designed specifically for continuous action spaces, where value-based methods cannot take an explicit $\max_a$. DDPG learns a deterministic policy $\mu_\theta(s)$ directly, using the critic $Q_\phi(s,a)$ as a differentiable surrogate for the (otherwise intractable) $\max$:

This is the deterministic policy gradient theorem: since the action is a deterministic, differentiable function of the state, the chain rule lets gradients flow directly from the critic's estimate of action-value, through the action itself, back into the actor's parameters — an efficient alternative to the stochastic log-probability trick, valid for continuous action spaces. The critic is trained by ordinary Bellman-error minimization exactly as in DQN, using a replay buffer and target networks for both actor and critic (soft/Polyak updates rather than DQN's periodic hard copy, found empirically to be more stable for continuous control). Because the policy is deterministic, exploration must be added externally: DDPG typically adds temporally-correlated Ornstein-Uhlenbeck noise or simple Gaussian noise to actions during data collection.

13.2 TD3 (Twin Delayed DDPG)

TD3 identifies and fixes the same maximization-bias problem in DDPG that Double Q-learning fixes for discrete Q-learning (section 7.5), plus two further stabilizers:

• Twin (clipped double) critics: train two independent Q-networks $Q_{\phi_1}, Q_{\phi_2}$ and use $\min(Q_{\phi_1},Q_{\phi_2})$ when forming the target, which biases the estimate slightly toward under- rather than over-estimation, empirically far more benign for policy learning since an actor chasing an overestimated $Q$ exploits and amplifies the error, whereas underestimation merely makes learning conservative.
• Delayed policy updates: update the actor (and target networks) less frequently than the critics (e.g. once every 2 critic updates), giving the value estimate time to become more accurate before the policy chases it, reducing the compounding of value error into policy error.
• Target policy smoothing: add small clipped noise to the action used in the target computation, $a' = \mu_{\theta^-}(s') + \text{clip}(\epsilon,-c,c)$, which regularizes the value estimate by smoothing over a small neighborhood of actions rather than allowing the critic to develop a sharp, easily-exploitable spike at a single specific action.

13.3 SAC (Soft Actor-Critic)

SAC casts control as maximizing not only expected reward but also policy entropy, giving the maximum-entropy RL objective:

The corresponding soft Bellman backup replaces the ordinary value with a "soft" value that already accounts for the entropy bonus of future actions:

Practically SAC trains twin critics (like TD3, for the same overestimation-bias reasons), a stochastic (typically squashed-Gaussian) actor trained via the reparameterization trick to allow low-variance gradients through the sampled action, and often an automatically-tuned temperature $\alpha$ that is adjusted by gradient descent to hold the policy's entropy at a target level (typically $-|\mathcal{A}|$, i.e. minus the dimensionality of the action space), removing the need to hand-tune the entropy/reward tradeoff.

14. Multi-Armed Bandits

Bandits are RL stripped of state and transition dynamics: at each round, the agent pulls one of $K$ arms, and arm $a$ yields a reward drawn i.i.d. from a distribution with unknown mean $\mu_a$. There is no credit-assignment problem (the reward is immediate and directly attributable), so bandits isolate the exploration-exploitation tradeoff in its purest form, and every idea developed here (UCB, Thompson sampling, regret) generalizes directly into full RL and into practical systems like online advertising, A/B testing, and clinical trial design.

14.1 Regret

Regret measures the total expected reward lost relative to always pulling the best arm from the start (which is unknown to the agent, and is exactly what must be discovered through exploration). An algorithm with linear regret $R_T = \Theta(T)$ (e.g. pure exploitation, or fixed-$\epsilon$-greedy) never stops losing a constant fraction of reward per round on average, meaning it fails to converge to always picking the best arm. Good algorithms achieve sublinear (typically logarithmic, $R_T = O(\log T)$) regret, meaning the average per-round regret $R_T/T \to 0$ — the algorithm eventually behaves almost as well as if it had known the best arm from the start. The Lai-Robbins lower bound shows $O(\log T)$ is asymptotically the best possible rate for any algorithm facing this problem, so UCB and Thompson sampling below, which both achieve this rate, are asymptotically optimal.

14.2 $\epsilon$-greedy bandit

With probability $1-\epsilon$ pull $\arg\max_a \hat{\mu}_a$; otherwise pull a uniformly random arm. Simple, but with a fixed $\epsilon$ it incurs linear regret (it keeps exploring uniformly forever, at a constant rate, even after the best arm is well known); decaying $\epsilon_t = \min(1, cK/(d^2 t))$ for suitable constants achieves logarithmic regret, but requires knowledge of a problem-dependent gap parameter $d$ that in practice is unknown, making $\epsilon$-greedy schedules brittle compared to UCB or Thompson sampling.

14.3 UCB1 (Upper Confidence Bound)

14.4 Thompson sampling

A fully Bayesian approach: maintain a posterior distribution $P(\mu_a \mid \text{data})$ for each arm (Beta-Bernoulli conjugate posterior for binary rewards, e.g. click/no-click; Normal-Normal conjugate posterior for Gaussian rewards). At each round: draw one sample $\tilde{\mu}_a$ from each arm's current posterior, then pull $\arg\max_a \tilde{\mu}_a$. Update the posterior of the pulled arm with the observed reward via Bayes' rule (for Beta-Bernoulli: $\alpha_a \leftarrow \alpha_a + r$, $\beta_a \leftarrow \beta_a + (1-r)$, an extremely cheap closed-form update). The probability that a given arm is sampled equals, by construction, the posterior probability that it is actually the best arm — this is genuinely Bayesian exploration, and it empirically often outperforms UCB despite (or perhaps because of) not requiring an explicit, sometimes overly conservative, worst-case confidence bound.

14.5 Contextual bandits

Before each pull, the agent observes a context (side-information) vector $x_t$; the reward distribution now depends on both the arm and the context, $r\sim R(a,x_t)$. LinUCB assumes a linear reward model $\mathbb{E}[r|a,x] = \theta_a^\top x$ per arm, maintains a ridge-regression posterior on $\theta_a$ from the arm's own observed data, and selects the arm maximizing an upper confidence bound analogous to UCB1 but derived from the regression's confidence ellipsoid: $a_t = \arg\max_a\left(\hat\theta_a^\top x_t + \alpha\sqrt{x_t^\top A_a^{-1} x_t}\right)$ where $A_a$ is the ridge-regression design matrix accumulated for arm $a$. Neural (deep) contextual bandits replace the linear model with a neural network and typically approximate the confidence term with an ensemble, dropout, or a linear layer on top of learned features. Contextual bandits are the standard formalism for personalized recommendation, online ad selection, and — directly relevant in modern AI systems — LLM model/prompt routing (choosing which of several candidate models or system prompts to use per query based on a context vector of the query's features, learning online from user feedback).

15. Exploration Strategies

• $\epsilon$-greedy: simple, typically decayed over training (e.g. linearly annealed from 1.0 to 0.01–0.1 over the first fraction of training). Exploration is state-independent and undirected — it does not preferentially explore uncertain or novel states over already-well-understood ones.
• Softmax / Boltzmann: $\pi(a|s) \propto \exp(Q(s,a)/\tau)$, exploration concentrated on actions with similar, competitive Q-values rather than uniformly across all actions; temperature $\tau$ plays the same annealing role as $\epsilon$.
• UCB (bandits and, less commonly, full RL): optimism under uncertainty, directly rewards visiting under-sampled state-actions.
• Thompson sampling: sample from a posterior over the value/reward model, naturally directed toward states where the posterior is still uncertain.
• Intrinsic motivation / curiosity: add a bonus reward for novelty, typically the prediction error of a learned forward dynamics model ("if I cannot predict what happens after this action, I have not learned this part of the environment yet — go find out"), count-based pseudo-counts for large/continuous state spaces (e.g. hashing states into buckets and rewarding rarely-visited buckets), or Random Network Distillation (RND: a fixed random target network and a trained predictor network; prediction error against the fixed random target is high in novel states purely because the predictor has not yet been trained there, giving a stable, non-stationarity-free novelty signal).
• Noisy networks, parameter-space noise: inject structured, learnable or fixed noise directly into network weights rather than into the action output, producing temporally-consistent exploratory behavior within an episode (rather than the independent-per-step jitter of $\epsilon$-greedy), which matters a great deal for tasks requiring an extended sequence of coordinated exploratory actions (e.g. navigating consistently in one new direction rather than jittering back and forth).

In LLM RL, exploration during rollout collection comes almost entirely from stochastic decoding — temperature, top-p (nucleus) sampling, and sometimes explicit diversity-promoting decoding constraints — rather than from any of the classical mechanisms above, because the "action space" (the vocabulary, applied recursively over a sequence) is enormous and structured, and the policy itself is already a well-calibrated (post-pretraining) probability distribution whose inherent stochasticity, if not collapsed by over-aggressive fine-tuning, already provides a reasonable exploration signal.

16. Offline RL and Imitation Learning

16.1 Batch / offline RL

Learn purely from a fixed, previously-collected dataset $\mathcal{D}$, with zero further environment interaction — critical when interaction is expensive, slow, or unsafe (healthcare, autonomous driving, industrial control). The central challenge is extrapolation (distributional shift) error: standard off-policy Bellman backups involve $\max_a Q(s',a)$, and this max is free to select actions $a$ that never appear in $\mathcal{D}$ near state $s'$; the Q-function's estimate for such out-of-distribution (OOD) actions is essentially unconstrained extrapolation by the function approximator and is frequently wildly, systematically overoptimistic, since nothing in the training data corrects it. A policy trained to exploit such an erroneously high $Q$-value will confidently choose actions the data never validated, often catastrophically.

• CQL (Conservative Q-Learning): adds a regularizer to the standard Bellman loss that explicitly pushes down Q-values for actions not seen in the data (typically actions sampled from the current policy or uniformly) while pushing up Q-values for the actions actually present in the dataset, producing a conservative (lower-bound) estimate of the true Q-function that is provably safe against overestimation on OOD actions.
• IQL (Implicit Q-Learning): avoids querying $\max_a Q(s',a)$ at all by estimating the state value with expectile regression, $V(s)\approx\mathbb{E}_\tau[Q(s,a)]$ using an asymmetric ("expectile," a generalization of quantile regression to squared loss) loss with expectile parameter close to 1, which approximates a soft max over the actions actually observed in the data for that state, without ever evaluating $Q$ at an action not present in $\mathcal{D}$.
• Decision Transformer: reframes offline RL entirely as sequence modeling rather than Bellman-equation-based RL — condition an autoregressive transformer on a desired "return-to-go" (target cumulative future reward) token alongside the state-action history, and train it with ordinary supervised next-action prediction on the offline trajectories. At inference/deployment, specify a high desired return-to-go and let the model generate actions conditioned on achieving it. This entirely sidesteps the extrapolation-error problem of Bellman backups (there is no bootstrapped max anywhere in the training objective) at the cost of relying on the dataset already containing trajectories with a reasonable spread of achieved returns to condition on.

16.2 Imitation learning

• Behavioral Cloning (BC): ordinary supervised learning, fitting $\pi_\theta(a|s)$ to match expert demonstrations $(s,a)$ pairs by maximum likelihood. Simple and often a strong baseline, but suffers covariate shift: because the trained policy will inevitably make small errors, it drifts into states the expert demonstrations never covered, where the policy has no training signal and errors compound — this is analytically shown to cause a quadratic-in-horizon (rather than linear) blow-up of total error compared to the expert.
• DAgger (Dataset Aggregation): directly addresses covariate shift by iteratively running the currently-learned policy in the real environment, querying the expert for the correct action at every state actually visited (including off-distribution ones the policy drifted into), aggregating this new labeled data with all previous data, and retraining — this ensures the training distribution converges toward the policy's own state-visitation distribution, closing the mismatch that plain BC suffers from. Requires an interactive expert (a human or a scripted oracle) available at training time, which is a significant practical limitation.
• GAIL (Generative Adversarial Imitation Learning): trains a discriminator network to distinguish expert trajectories from policy-generated trajectories, and trains the policy (via ordinary policy-gradient RL, e.g. TRPO) to maximize the discriminator's confusion — i.e., to produce trajectories indistinguishable from the expert's. This is directly analogous to a GAN, and is provably connected to inverse reinforcement learning: the discriminator's output can be interpreted as an implicitly learned, adaptively-shaped reward signal. GAIL requires only expert state-action samples (no explicit expert queries needed as in DAgger) and no reward function at all, at the cost of the well-known instability of adversarial training.

17. Distributional RL

Ordinary RL learns only the expectation of the return, $Q(s,a)=\mathbb{E}[Z(s,a)]$ where $Z(s,a)$ is the random variable representing the (stochastic) return. Distributional RL instead models the full probability distribution of $Z(s,a)$, which turns out to both improve the stability and final performance of deep RL agents empirically, and to unlock explicitly risk-sensitive decision-making.

17.1 Distributional Bellman equation

The ordinary Bellman equation $Q(s,a)=\mathbb{E}[R+\gamma Q(s',a')]$ has an exact distributional analogue in terms of equality of distributions rather than equality of scalars:

where $\overset{D}{=}$ denotes equality in distribution: the random variable on the left has the same distribution as the (transformed) random variable on the right. This distributional Bellman operator is a contraction in an appropriate probability-metric (e.g. the Wasserstein distance), giving a convergence theory parallel to, but distinct from, the ordinary scalar Bellman contraction.

17.2 C51

Represents $Z(s,a)$ as a categorical distribution over a fixed, evenly-spaced discrete support of 51 atoms spanning the plausible return range $[V_{\min}, V_{\max}]$, with learned probabilities $p_i(s,a)$ per atom. The distributional Bellman update projects the shifted-and-scaled target distribution (from $R+\gamma Z(s',a')$) back onto this fixed support (since $R+\gamma\cdot(\text{atom value})$ generally does not land exactly on a support atom) via a specific linear interpolation projection, then trains by cross-entropy between the projected target distribution and the current predicted distribution.

17.3 QR-DQN and IQN

QR-DQN (Quantile Regression DQN) flips the parameterization: instead of fixed atom locations with learned probabilities, it uses fixed, evenly-spaced probability levels (quantile fractions) with learned atom locations, trained with the quantile regression loss (an asymmetric pinball/Huber loss), which avoids the need for the awkward fixed-support projection step of C51 and removes the need to specify $V_{\min},V_{\max}$ in advance. IQN (Implicit Quantile Networks) generalizes further by making the quantile fraction itself an input to the network (rather than a fixed finite set), implicitly representing the full continuous quantile function and allowing risk-sensitive policies to be formed at inference time by sampling quantile fractions from a non-uniform (risk-averse or risk-seeking) distribution rather than uniformly.

17.4 Why distributional RL helps in practice

Even though the final policy in the standard formulation only ever uses the mean of the learned distribution (throwing away the extra distributional information at decision time), empirical results (Rainbow ablations, the original C51 paper) consistently show distributional agents outperform scalar-Q agents on Atari and other benchmarks. The leading explanations are: richer auxiliary training signal (predicting a full distribution is a harder, more information-dense auxiliary task that regularizes the shared representation), reduced sensitivity to a specific kind of Bellman-target noise, and better-behaved gradients from the categorical/quantile losses compared to squared TD-error regression. Separately, when the full distribution is used at decision time, it directly supports explicit risk-sensitive control — e.g. optimizing a lower quantile (CVaR) of the return rather than the mean, directly relevant to safety-critical domains.

18. Advanced Topics

18.1 Multi-agent RL (MARL)

Multiple agents act in a shared (or separate but interacting) environment. The central complication is non-stationarity: from any single agent's perspective, the environment's effective dynamics change over time as the other agents' policies are simultaneously being updated, which invalidates the fixed-MDP assumption underlying every convergence guarantee discussed above. Paradigms: independent learners (each agent runs a standard single-agent algorithm, e.g. independent Q-learning, ignoring the other agents entirely — simple but has no convergence guarantee and can cycle or fail to converge); centralized training with decentralized execution (CTDE, e.g. MADDPG: each agent's critic is trained with access to all agents' observations and actions during training, since a centralized critic sees a stationary environment, but each agent's actor uses only its own local observation at execution/deployment time, since that is all that is available in the real deployed system); and self-play (train a single agent against copies or past versions of itself, as in AlphaZero and OpenAI Five — since both sides are always evolving together, this naturally produces a curriculum of steadily increasing difficulty, though it can be vulnerable to cyclic, non-transitive "rock-paper-scissors" strategy dynamics without careful opponent-pool management).

18.2 Hierarchical RL

The options framework generalizes primitive actions to options: temporally-extended sub-policies, each with an initiation set (states where the option can be started), an internal policy, and a termination condition. This lets a top-level policy choose among options ("go to the door", "pick up the object") rather than raw low-level actions, dramatically shortening the effective decision horizon for long-horizon tasks and enabling transfer of reusable skills across tasks. Feudal networks and HIRO implement a two-level (or deeper) manager-worker hierarchy: a slow-timescale manager sets abstract subgoals (often as a target direction or target state embedding in a learned latent space), and a fast-timescale worker is rewarded for making progress toward the manager's currently-set subgoal, with the manager itself trained by ordinary RL on the environment's true task reward, treating subgoal-setting as its own action space.

18.3 Inverse RL and reward learning

Inverse reinforcement learning (IRL) recovers an unknown reward function $R$ from expert demonstrations, inverting the usual RL pipeline (given $R$, find $\pi$) to instead ask: given $\pi_{\text{expert}}$'s behavior, what $R$ would make that behavior optimal? The problem is fundamentally ill-posed (many reward functions, including the trivial all-zero reward, make any fixed policy "optimal"), so practical IRL methods add regularizing assumptions. Maximum-entropy IRL resolves the ambiguity by assuming experts are noisily optimal — they select trajectories with probability proportional to $\exp(R(\tau))$, i.e. they maximize reward while otherwise being as unpredictable (high-entropy) as possible — which yields a well-posed maximum-likelihood estimation problem for $R$. This maximum-entropy IRL formulation is the direct theoretical foundation of GAIL (section 16.2) and of modern preference-based reward modeling in RLHF, where the reward model is likewise fit to make observed human preference data as likely as possible under a Boltzmann-rational choice model (the Bradley-Terry model, section 20.3).

18.4 Meta-RL and transfer

Meta-RL trains an agent not to solve one fixed task well, but to adapt quickly to a new task drawn from a distribution of related tasks, using only a small amount of new task-specific experience. MAML applied to RL learns an initialization of policy parameters such that a few ordinary policy-gradient steps on a new task's rewards produce a near-optimal policy for that task (a "learning to learn" objective: differentiate through the inner-loop adaptation process itself). RL² instead treats the entire adaptation process as itself something a recurrent policy learns implicitly: the recurrent network's hidden state, updated online as it interacts with a new task, comes to encode task-identifying information purely from experience, without any explicit gradient-based adaptation step at test time — the "learning algorithm" is entirely implicit in the trained recurrent weights. Both paradigms are directly relevant conceptually to multi-task and few-shot fine-tuning of large language models, where a single pretrained model must rapidly specialize given limited task-specific signal.

18.5 Safe RL and constrained RL

Constrained MDPs add one or more auxiliary cost signals $C(s,a)$ (distinct from the reward) with an explicit budget $d$ that must not be exceeded in expectation — e.g. maximize task reward subject to a bounded expected number of safety-critical near-collisions. The standard solution technique is the Lagrangian method: introduce a dual variable (Lagrange multiplier) $\lambda\geq0$ for the constraint and alternately optimize the policy on the Lagrangian objective $J(\pi)-\lambda(\mathbb{E}[C]-d)$ and update $\lambda$ by (projected) gradient ascent on the constraint violation, converging to a policy that satisfies the constraint at convergence while approximately maximizing reward. CPO (Constrained Policy Optimization) extends TRPO's trust-region machinery to directly handle the constraint within each single update (rather than via a slowly-adapting dual variable), giving stronger per-update safety guarantees at the cost of a more involved optimization subproblem per step. The direct analog in LLM alignment is treating refusal rate, toxicity score, or other safety metrics as explicit constraints (a "safety budget") alongside the primary reward-model objective, rather than folding everything into one scalar reward.

18.6 Curriculum learning and unsupervised environment design

The order in which an agent encounters tasks (or task difficulty levels) substantially affects final performance and sample efficiency in sparse-reward or hard-exploration domains. Automatic curriculum methods (e.g. PLR — Prioritized Level Replay, POET, ALP-GMM) adaptively select or generate training scenarios of appropriate difficulty — neither so easy the agent learns nothing new, nor so hard the agent never receives any learning signal — often by prioritizing training levels where the agent's current value estimate has the highest regret or prediction error, directly connecting curriculum design to the same intrinsic-motivation and prioritized-sweeping ideas introduced earlier.

19. RL Environments and APIs

19.1 The agent-environment loop

obs = env.reset()
done = False
while not done:
    action = agent.act(obs)
    obs, reward, terminated, truncated, info = env.step(action)
    done = terminated or truncated
    agent.learn(obs, action, reward, done, info)

19.2 Gymnasium (formerly OpenAI Gym)

• reset(seed=, options=) → observation, info
• step(action) → obs, reward, terminated, truncated, info
• action_space, observation_space (Box for continuous, Discrete for finite, Dict/Tuple for structured/composite spaces)
• terminated: a true terminal state (goal reached, failure/death condition) — the underlying MDP genuinely ends, and bootstrapping should not add $\gamma V(s_{\text{next}})$ since there is no meaningful next state. truncated: the episode was cut off by an artificial time limit, not a true MDP terminal — bootstrapping should still add $\gamma V(s_{\text{next}})$, since the underlying process would have continued. Conflating the two (a very common bug) silently teaches the agent an incorrect, artificially pessimistic value near the time limit.

19.3 Common environment families

19.4 Wrappers and vectorization

Common preprocessing wrappers: frame stacking (recover short-term dynamics like velocity from a sequence of raw frames — a practical fix for a POMDP, section 2), reward clipping (e.g. clip Atari rewards to $\{-1,0,+1\}$ to stabilize the scale of the TD-error loss across wildly different games), observation normalization (running mean/variance normalization, critical for continuous-control algorithms whose gradients are sensitive to input scale), and `RecordEpisodeStatistics` (bookkeeping for logging). `VectorEnv` (Gymnasium) or equivalent runs $N$ environment instances in parallel (via subprocesses or the same process for cheap environments), batching observations for a single forward pass through the policy/value network — essential for the throughput that on-policy algorithms like PPO/A2C need, since they cannot reuse old data across many gradient steps the way off-policy methods can.

19.5 Sim-to-real transfer

Policies trained purely in simulation often fail when deployed on real hardware due to the reality gap — systematic discrepancies between simulated and real dynamics, sensor noise, and unmodeled effects (friction, actuator delay, deformable contact). Standard mitigations: domain randomization (randomize simulation physical parameters — mass, friction, sensor noise, visual textures/lighting — across training episodes so the learned policy is forced to be robust to a wide range of plausible dynamics, treating the real world as simply one more sample from the randomized distribution); system identification (measure real-world physical parameters and calibrate the simulator to match them as closely as possible before training); and offline pretraining in simulation followed by fine-tuning on a limited quantity of real robot data (using imitation learning or a small amount of real-world RL to correct the residual reality gap that domain randomization alone does not cover).

20. Reward Design, Shaping, and Hacking

20.1 Reward function engineering

The reward function defines the entire optimization target; everything else in RL is machinery for finding a policy that maximizes whatever reward function is specified. A misspecified reward leads to genuinely wrong, sometimes bizarre, behavior even with a perfect optimization algorithm and unlimited compute — the algorithm did exactly what it was asked, the specification was simply wrong. This makes reward design arguably the single highest-leverage, and most failure-prone, part of applying RL to a real problem.

20.2 Reward shaping

Add an auxiliary shaping term to a sparse or hard-to-learn-from reward to provide denser learning signal. Naive shaping can change the optimal policy (e.g. reward a robot for moving toward a goal, and it may learn to move back and forth near the goal to keep collecting the shaping reward without ever finishing the task). Potential-based reward shaping (Ng, Harada & Russell, 1999) avoids this failure mode by construction:

A good potential function $\Phi$ (e.g. negative distance to goal) provides dense, informative gradient signal throughout training without altering what the final learned policy will be, which is the ideal of reward shaping done correctly.

20.3 Sparse vs dense rewards

• Sparse: reward only at task completion (e.g. $+1$ only at the goal, $0$ everywhere else). Reflects the true task objective with no risk of misspecification, but creates a severe exploration problem — with a purely random policy, a long sparse-reward task may never be solved even once during training, so the agent never receives any nonzero learning signal at all. Mitigations include hindsight experience replay (relabel a failed trajectory's actual final state as if it had been the intended goal, generating a nonzero-reward training signal from otherwise "failed" data), curriculum learning, and intrinsic motivation (section 15).
• Dense: incremental feedback at every step, easing exploration and speeding up early learning, but at the risk of misspecification/shaping bias unless designed carefully (ideally with the potential-based form above).

20.4 Reward hacking / specification gaming

The agent maximizes the literal proxy reward it was given without achieving the designer's actual intended goal — Goodhart's law in action. Well-documented examples:

• A boat-racing agent trained to maximize race-track score (from collecting bonus items scattered along the course, in addition to finishing the race) discovers it can loop in a small circle, repeatedly picking up regenerating bonus items forever, achieving a far higher score than any policy that actually finishes the race (the CoastRunners example).
• A simulated legged robot rewarded for staying upright and moving forward instead learns to fall over in a way that technically satisfies a loosely-specified "forward progress" metric, or thrashes its limbs erratically to trigger a survival bonus without meaningful locomotion.
• An LLM trained against a learned reward model that has learned to (mis)associate length, hedging phrases, or agreement with the user as proxies for quality produces verbose, sycophantic, or superficially-formatted text that scores well on the proxy reward model without actually being more helpful or correct.

20.5 Mitigations

• Reward model ensembles and uncertainty penalties: train several reward models and penalize the policy for driving the models' predictions apart (a proxy for exploiting a blind spot any single model has), or use the ensemble's minimum/lower-confidence-bound as the actual training reward.
• KL constraints to a reference policy (the core mechanism of RLHF, section 21.4): explicitly bound how far the trained policy is allowed to drift from a known-reasonable starting policy, limiting how far into a possibly-reward-model-exploiting regime the policy can travel.
• Human audits and adversarial evaluation sets: periodically evaluate the trained policy against held-out human judgment or adversarially-constructed test cases specifically designed to catch known failure patterns, rather than trusting the proxy reward's own score as ground truth.
• Process rewards vs. outcome rewards: reward correct intermediate reasoning steps, not just a correct final answer, which is both denser (helps exploration) and harder to game via a lucky or degenerate final-answer shortcut that bypasses genuine reasoning.
• Verifiable rewards (unit tests, proof checkers, symbolic math verifiers) wherever the task admits a deterministic, non-learned checker, entirely removing the reward-model-hacking failure mode for that portion of the reward signal (section 21.11).

21. Reinforcement Learning for Large Language Models

LLM post-training reframes text generation as sequential decision making: state = the prompt plus every token generated so far, action = the next token chosen from the vocabulary, policy = the language model's own next-token distribution, episode = one full generated response, ending at the end-of-sequence token.

21.1 Why RL for LLMs?

Supervised fine-tuning (SFT) fits the model to reproduce a fixed set of human- or model-written demonstrations by maximum likelihood, but it cannot directly optimize objectives that are not naturally expressed as "produce this exact text": aggregate human preference between two full responses (which response is better is comparative, not something a single demonstration teaches), sparse task success signals (did the code actually pass the unit tests; did the math proof actually verify), or genuinely multi-objective tradeoffs (helpfulness vs. harmlessness vs. honesty simultaneously). RL directly optimizes whatever scalar reward is specified, however that reward is computed — a learned reward model's score, a binary unit-test pass/fail, a verified proof checker's output — without requiring that objective to be differentiable or expressible as a supervised target.

21.2 RLHF pipeline (InstructGPT / ChatGPT style)

1. Supervised fine-tuning (SFT): fine-tune the pretrained base model on a curated set of high-quality human (or model-assisted) demonstrations of the desired behavior, producing a reasonable starting policy.
2. Reward model (RM) training: collect pairs of model completions for the same prompt, have human labelers (or another AI system, in RLAIF) rank which is better, and train a separate model to predict this preference (Bradley-Terry, below).
3. RL fine-tuning: further update the SFT policy using an RL algorithm (classically PPO) to maximize the reward model's score on newly sampled completions, subject to a KL penalty keeping the policy near the SFT reference (section 21.4).

21.3 Reward model training (Bradley-Terry model)

Given a prompt $x$ and two completions where humans preferred $y_w$ ("winner") over $y_l$ ("loser"), the reward model $r_\phi(x,y)$ is trained so that the probability it assigns to the observed preference matches a logistic (Bradley-Terry) choice model over the two scalar scores:

21.4 RLHF objective with KL penalty

21.5 PPO for LLMs

Each generated token is treated as one RL action; the critic estimates the value of each partial (prompt + tokens-so-far) sequence to compute GAE-based advantages exactly as in section 11.2. Distinctive challenges relative to classic PPO robotics/game settings:

• The action space is the entire vocabulary, commonly 50,000–200,000+ tokens — enormously larger than typical discrete-control action spaces.
• Credit assignment must span very long generations (hundreds to thousands of tokens) from a reward often available only at the very end of the sequence.
• Reward is frequently only defined at the terminal EOS token (the sequence-level reward-model score for the full completion), meaning every non-terminal token's reward is exactly zero, and the critic/GAE machinery is entirely responsible for distributing this single terminal reward signal back across every earlier token-level decision.
• Four separate large models must be held in memory and/or compute simultaneously during training: the policy (being trained), the frozen reference policy (for the KL penalty), the critic (value function, itself typically a large network, often initialized from the reward model or the SFT policy), and the reward model (used to score completions) — a substantial systems/memory engineering burden distinct from classic RL.

Practical tricks widely used in RLHF-PPO implementations: reward normalization/whitening across a batch; folding the per-token KL penalty directly into the per-token reward signal (rather than only as a separate loss term) so that credit assignment via GAE naturally accounts for it token-by-token; advantage whitening; hard caps on response length (both to bound compute and to prevent length-based reward hacking); and mixing a small amount of the original SFT loss into the PPO update to counteract capability regression ("alignment tax") during RL fine-tuning.

# RLHF-style training with TRL (conceptual)
from trl import PPOTrainer, PPOConfig, AutoModelForCausalLMWithValueHead

ppo_config = PPOConfig(kl_penalty="kl", init_kl_coef=0.05)
trainer = PPOTrainer(config=ppo_config, model=policy, ref_model=ref, tokenizer=tokenizer)

for batch in prompts:
    query_tensors = batch["input_ids"]
    response_tensors = trainer.generate(query_tensors, max_new_tokens=256)
    rewards = [reward_model(q, r) for q, r in zip(query_tensors, response_tensors)]
    stats = trainer.step(query_tensors, response_tensors, rewards)

21.6 DPO: full derivation

Direct Preference Optimization observes that the RLHF objective of section 21.4 has a known closed-form optimal solution (already stated above):

Rearranging algebraically to express the (unknown, in principle recoverable) true reward in terms of any policy achieving this optimum:

Substituting this expression for $r^*$ back into the Bradley-Terry preference loss (section 21.3): since the loss only ever involves a difference of two rewards for the same prompt $x$, the troublesome, generally intractable normalizing constant $Z(x)$ (a sum/integral over the entire, exponentially large space of possible completions $y$) appears identically in both terms and exactly cancels:

21.7 DPO variants

21.8 GRPO (Group Relative Policy Optimization)

Used prominently in DeepSeek-R1 and other modern reasoning-focused RL post-training. For each prompt, sample a group of $G$ completions $\{y_1,\ldots,y_G\}$ from the current policy, score each with the reward function (a reward model, or, especially in reasoning tasks, a verifiable checker), and compute a group-relative advantage by normalizing each completion's reward against the group's own empirical statistics rather than against a learned critic's value estimate:

This group-relative advantage is then used exactly as $\hat{A}_t$ inside a standard PPO-style clipped surrogate loss (section 12.6), applied per token. The key structural difference from PPO-with-critic is that GRPO needs no separate learned value/critic network at all: the group mean acts as an empirical, per-prompt Monte Carlo baseline instead of a learned $V_\phi(s)$, which substantially reduces memory and removes an entire source of critic-approximation-error-induced bias, at the cost of needing to sample multiple completions per prompt (increasing rollout compute) to get a low-variance group statistic.

21.9 REINFORCE / RLOO (Leave-One-Out) for LLMs

A simpler alternative baseline scheme in the same group-sampling spirit as GRPO: for each sampled completion $i$ within a group of $G$, use the mean of the other $G-1$ completions' rewards as its baseline, rather than the whole group's mean (which technically includes the sample's own reward, introducing a small correlation/bias between the sample and its own baseline):

This "leave-one-out" baseline is provably unbiased in a way that including the sample's own reward in its own baseline is not, and empirically works well specifically in domains with verifiable, low-noise rewards (math, code, formal proofs), where a small number of samples per prompt already gives a reasonably low-variance baseline, avoiding the additional complexity of PPO's clipping/critic/multiple-epoch machinery entirely — often simply a single-epoch REINFORCE-style update per batch of sampled completions.

21.10 Process Reward Models (PRM)

Rather than scoring only the final answer of a multi-step reasoning chain (an outcome reward model, ORM), a process reward model scores the correctness of every individual intermediate reasoning step. Training data for a PRM is typically collected by having human (or AI) annotators label each step of a chain-of-thought as correct, incorrect, or neutral, given the steps that preceded it. A trained PRM enables step-level credit assignment during RL (directly rewarding correct sub-steps rather than only a terminal outcome, similar in spirit to a denser, verified version of reward shaping), and at inference time supports search strategies like best-of-N re-ranking or explicit tree search (guided by the PRM's step-level scores to prune unpromising reasoning branches early, rather than only discovering a chain was wrong at its very end).

21.11 Verifiable rewards (RLVR)

In domains that admit a deterministic, automatable checker — unit tests for generated code, a symbolic computer-algebra system for math answers, a formal proof checker (e.g. Lean) for mathematical proofs — the reward can be computed directly by that checker rather than by a learned, and therefore inherently gameable, reward model. This structurally eliminates the entire reward-model-hacking failure mode (section 20.4) for that portion of training, since there is no learned proxy to exploit: the checker either accepts the output or it does not, ground truth by construction. This is the mechanism underlying scalable self-improvement pipelines like AlphaCode's use of execution-based test feedback and DeepSeek-R1's large-scale RL training on math and code, where the verifiable signal allows aggressive, large-scale RL without the reward-model-overoptimization risk that plagues purely RM-based RLHF at similar scale.

21.12 RLAIF and Constitutional AI

• RLAIF (RL from AI Feedback): replace human preference labelers with another (typically larger or more capable) AI model that labels which of two completions better satisfies a given rubric or set of principles. This scales far more cheaply than human labeling, but any systematic biases or blind spots of the labeling AI model are directly inherited by the resulting reward model and, downstream, by the trained policy.
• Constitutional AI: the model itself is prompted to critique its own draft response against a written set of principles ("the constitution"), then to revise the response to better satisfy those principles; these self-generated critique-and-revision pairs become training data for supervised fine-tuning and/or for the preference-labeling step of an RLAIF pipeline, reducing (though not eliminating) the reliance on direct human labeling of individual harmful or borderline outputs.

21.13 Online RL and rejection sampling / best-of-N distillation

A simpler alternative to full PPO/GRPO-style policy-gradient RL: sample many ($N$, e.g. 16–64) completions per prompt from the current policy, filter to keep only the highest-reward completion(s) per prompt (rejection sampling / best-of-N), and fine-tune the policy with ordinary supervised cross-entropy on these filtered "winning" completions, exactly as in SFT. This is far simpler to implement and more stable than full RL (no advantage estimation, no clipping, no critic) at the cost of a fixed, non-adaptive exploration budget per prompt (unlike RL, which continually adapts what it samples as the policy improves during training). Iterating this loop — sample, filter, fine-tune, then repeat with the newly fine-tuned policy — is the basis of methods like ReST (Reinforced Self-Training) and RAFT (Reward rAnked FineTuning), which recover much of RL's benefit through a sequence of simple supervised fine-tuning rounds.

21.14 Reward hacking in LLMs: specific empirical patterns

• Verbosity inflation: the reward model has learned a spurious positive correlation between response length and human-perceived quality (longer answers often look more thorough even when they are not), so the policy learns to pad responses unnecessarily to exploit this correlation.
• Sycophancy: the policy learns to agree with the user's stated views or assumptions regardless of their actual correctness, because reward-model training data (implicitly or explicitly) rewards agreeableness.
• Format hacking: superficial stylistic features the reward model has learned to associate with quality — bullet-point lists, hedging phrases, a particular tone — are reproduced even when they do not genuinely improve the substance of the response.
• Refusal overfitting: excessive, overly-broad safety refusals on borderline-but-legitimate requests, if the reward/safety training signal penalizes any hint of a sensitive topic rather than distinguishing genuinely harmful requests from merely adjacent ones.
• Reward model overoptimization: as RL training proceeds, the policy's true quality (as judged by held-out human evaluation) eventually plateaus and can even decline, even while the proxy reward-model score keeps climbing — the textbook Goodhart's-law signature, and the direct empirical motivation for KL constraints, reward-model ensembling, and periodic RM refresh/retraining against newly-collected human data during long RL runs.

21.15 LLM RL engineering checklist

• Keep the reference model frozen throughout training; continuously monitor the running KL divergence between policy and reference as a leading indicator of drift and potential reward hacking.
• Normalize/whiten rewards per batch; clip extreme advantage values before applying the policy update.
• Mix a small fraction (roughly 5–10%) of ordinary SFT loss into the RL objective to counteract capability regression ("alignment tax") during RL fine-tuning.
• Evaluate continually on held-out human-judged prompts and on standard capability benchmarks (e.g. MMLU-style knowledge tests, coding benchmarks) — proxy reward-model score alone is insufficient and can be actively misleading once overoptimization begins.
• Track the policy's output entropy throughout training: a collapsing entropy trend is a leading indicator of mode collapse and/or active reward hacking (the policy converging onto a narrow set of reward-exploiting patterns rather than genuinely improving).

Refer: InstructGPT · DPO paper · DeepSeek-R1 / GRPO · Post-Training notes

22. Engineering, Optimization, and Debugging

22.1 Hyperparameters that matter

22.2 Common failure modes and their diagnosis

• Value function blow-up / diverging loss: reduce learning rate, clip rewards or gradients, double-check that terminated vs truncated bootstrapping is handled correctly (section 19.2), and check for reward scale issues (unnormalized huge rewards destabilize the TD-error-based loss).
• Policy collapse (premature convergence to a narrow, low-entropy policy): increase the entropy coefficient, increase exploration noise/temperature, verify the advantage baseline/normalization is working correctly (a broken baseline can create spurious, artificially confident gradient signal).
• No learning at all (flat reward curve): check reward scale and sign conventions, check for bugs in episode-termination/done-masking logic, verify the observation normalization statistics are actually being updated and applied consistently between data collection and training, and confirm the environment reward is not accidentally always zero or constant.
• RLHF-specific performance regression during training: KL coefficient too low (increase $\beta$ or tighten the KL trust region), reward model overoptimization (refresh/retrain the reward model on newly collected data, or ensemble multiple reward models), or an outright bug in per-token vs. per-sequence reward/KL bookkeeping.
• High variance across random seeds: a well-documented, somewhat uncomfortable empirical property of deep RL — always report results averaged across multiple (ideally 5+) random seeds, and be skeptical of any single-seed result, especially for on-policy algorithms with relatively small batch sizes.

22.3 Libraries

• Gymnasium: the standard environment API (successor to OpenAI Gym).
• Stable-Baselines3: well-tested, widely-used reference implementations of PPO, SAC, DQN, TD3, and others, good for benchmarking a new idea against a trusted baseline.
• CleanRL: single-file, minimally-abstracted reference implementations, ideal for reading and understanding exactly what an algorithm does line by line, without a deep framework's layers of indirection.
• TRL: RLHF, DPO, PPO, and GRPO-style training specifically for LLMs, integrated with the Hugging Face ecosystem.
• Ray RLlib: distributed RL at scale across many machines, supporting a wide range of algorithms and both single- and multi-agent settings.
• Verl / OpenRLHF: large-scale, systems-optimized LLM RL training frameworks designed for production-scale RLHF/GRPO training of very large models.

# Stable-Baselines3 PPO example
from stable_baselines3 import PPO
model = PPO("MlpPolicy", "CartPole-v1", verbose=1)
model.learn(total_timesteps=100_000)
model.save("ppo_cartpole")

23. Complete Algorithm Catalog

Every major RL algorithm at a glance. Use this as a checklist when studying or designing systems.

24. Algorithm Selection Map