Reinforcement learning essentials

The setting

An agent interacts with an environment in discrete steps: it observes a state $s_t$, chooses an action $a_t$ from a policy $\pi(a\mid s)$, receives a reward $r_{t+1}$ and moves to $s_{t+1}$. The environment is a Markov decision process $(\mathcal{S},\mathcal{A},P,R,\gamma)$: transition probabilities $P(s'\mid s,a)$, reward function $R(s,a,s')$ and discount factor $\gamma\in[0,1)$, with the Markov property that the future depends only on the current state and action. The agent's goal is to maximize the expected return,

where the discount keeps the sum finite for continuing tasks and expresses a preference for sooner rewards ($\gamma=0.99$ means a horizon of roughly $1/(1-\gamma)=100$ steps). Unlike supervised learning there is no correct action given to us — only a scalar reward, often delayed and sparse — so the central difficulty is credit assignment: which of the many earlier actions caused this reward?

Value functions and the Bellman equations

The state value $V^{\pi}(s)=\mathbb{E}_\pi[G_t\mid s_t=s]$ is the expected return from $s$ when following $\pi$; the action value $Q^{\pi}(s,a)=\mathbb{E}_\pi[G_t\mid s_t=s,a_t=a]$ commits to the first action. Because $G_t = r_{t+1}+\gamma G_{t+1}$, values satisfy a recursive Bellman expectation equation:

The optimal value functions $V^*=\max_\pi V^\pi$ and $Q^*$ satisfy the Bellman optimality equation, which replaces the average over the policy by a max:

Knowing $Q^*$ solves the problem: act greedily. Every RL algorithm is a way of estimating $Q^*$ (or $V^*$), or of improving $\pi$ directly.

Dynamic programming: when you know the model

With $P$ and $R$ known, policy evaluation iterates the Bellman expectation equation to convergence (it is a contraction with factor $\gamma$); policy improvement makes $\pi$ greedy with respect to the resulting $Q^\pi$, which never makes it worse (the policy improvement theorem); alternating the two is policy iteration. Value iteration fuses them: $V_{k+1}(s)=\max_a\sum_{s'}P(s'\mid s,a)[R+\gamma V_k(s')]$. Dynamic programming is exact but needs the model and a table over states — fine for a gridworld, impossible for Go or language.

Model-free learning: Monte Carlo, TD and Q-learning

Without a model, learn from sampled experience. Monte Carlo methods run whole episodes and average the observed returns: unbiased but high-variance and only usable at episode end. Temporal-difference learning bootstraps from the current estimate after a single step:

The TD error is "what I got plus what I now expect, minus what I expected before" — it is the quantity dopamine neurons appear to encode, and the quantity every modern RL algorithm is built from. Q-learning applies the same idea to $Q^*$ directly, using the optimality equation as the target:

It is off-policy: the target uses the greedy action while the data can come from an exploratory behaviour policy (typically $\varepsilon$-greedy: random with probability $\varepsilon$, greedy otherwise), so old experience remains useful. SARSA instead uses the action actually taken next, $Q(s',a')$, and is on-policy. In the tabular case Q-learning converges to $Q^*$ provided every pair is visited infinitely often and the step sizes satisfy the Robbins–Monro conditions ($\sum\alpha_t=\infty$, $\sum\alpha_t^2<\infty$).

Worked example. In a gridworld, $Q(s,\text{right})=0.2$, the step gives $r=0$ and lands in $s'$ where $\max_{a'}Q(s',a')=0.5$; with $\gamma=0.9$, $\alpha=0.1$: target $=0+0.9\times0.5=0.45$; TD error $=0.45-0.2=0.25$; new $Q(s,\text{right})=0.2+0.1\times0.25=0.225$. Values propagate backward from the goal one step per visit — watch it happen in the rl-gridworld demo.

Deep Q-networks

Replace the table by a network $Q_\theta(s,a)$ and regress it toward the Q-learning target with the loss $\big(r+\gamma\max_{a'}Q_{\theta^-}(s',a') - Q_\theta(s,a)\big)^2$ (Huber in practice, 4.3 Loss functions catalog). Naively this diverges: consecutive samples are correlated and the target moves every time the weights do. DQN (Mnih et al., 2013/2015) added two stabilizers — an experience replay buffer sampled uniformly to decorrelate the data and reuse it (possible precisely because Q-learning is off-policy), and a target network $\theta^-$ that is a frozen copy updated only every few thousand steps — and learned Atari games from pixels. Double DQN, dueling heads, prioritized replay and distributional values followed (combined in Rainbow). DQN handles discrete actions; continuous control and stochastic policies need the policy-gradient family.

The policy-gradient theorem

Parameterize the policy directly, $\pi_\theta(a\mid s)$ (a softmax over actions, or a Gaussian for continuous actions), and maximize $J(\theta)=\mathbb{E}_{\tau\sim\pi_\theta}[R(\tau)]$, the expected return of trajectories $\tau=(s_0,a_0,r_1,s_1,\dots)$. We cannot differentiate through the environment, but we can differentiate the probability of the trajectory. Using the log-derivative trick $\nabla_\theta p_\theta = p_\theta\,\nabla_\theta\log p_\theta$:

Now $p_\theta(\tau)=\rho(s_0)\prod_t\pi_\theta(a_t\mid s_t)\,P(s_{t+1}\mid s_t,a_t)$, and the dynamics terms do not depend on $\theta$, so they vanish from the gradient of the log:

This is the policy-gradient theorem: increase the log-probability of the actions taken, weighted by how good the trajectory turned out. Two refinements make it usable. Causality: an action cannot affect rewards that came before it, so replace $R(\tau)$ by the reward-to-go $G_t=\sum_{k\ge t}\gamma^{k-t}r_{k+1}$. Baselines: subtracting any state-dependent $b(s_t)$ leaves the expectation unchanged because

but it can slash the variance. The natural baseline is $V(s_t)$, giving the advantage $A_t = G_t - V(s_t)$: "how much better than expected was this action?" The resulting estimator is

REINFORCE uses Monte Carlo returns for $G_t$ and (optionally) a learned baseline. Actor–critic methods learn the critic $V_w$ by TD and use the TD error $\delta_t=r_{t+1}+\gamma V_w(s_{t+1})-V_w(s_t)$ as a one-step advantage estimate (or GAE, an exponentially-weighted mix of $k$-step estimates, $\hat A_t=\sum_{l\ge0}(\gamma\lambda)^l\delta_{t+l}$), trading the Monte Carlo variance for a little bias. In code it is startlingly small: compute $\log\pi_\theta(a_t\mid s_t)$ with the network, multiply by $\hat A_t$ (detached), and call backward() on the negative mean (4.4 Backpropagation, fully derived).

PPO: don't move too far at once

Policy gradients are on-policy (each batch of trajectories is used once) and fragile: one large step can collapse the policy, and the data collected by the old policy becomes useless. Proximal Policy Optimization (Schulman et al., 2017) lets you take several gradient epochs on the same batch while limiting how far the policy moves. With the probability ratio $r_t(\theta)=\dfrac{\pi_\theta(a_t\mid s_t)}{\pi_{\theta_{\text{old}}}(a_t\mid s_t)}$,

Read it as a pessimistic bound: when the advantage is positive, the objective stops rewarding increases of $r_t$ beyond $1+\epsilon$; when negative, it stops rewarding decreases below $1-\epsilon$. The policy is improved only within a trust region around the old one. The full loss adds a value-function term and an entropy bonus for exploration. PPO is the workhorse of robotics, games — and language-model alignment.

Why this returns in LLMs

In RLHF (8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI) the policy is the language model, a state is the prompt plus the tokens generated so far, an action is the next token, the reward comes from a learned reward model at the end of the response, and a KL penalty to the pre-trained reference model plays the role of the trust region; PPO is run almost exactly as above. GRPO (8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI, 8.6 Reasoning models and test-time compute) drops the learned critic and uses the mean reward of a group of sampled responses to the same prompt as the baseline — the baseline trick from the derivation above, applied at the level of whole answers — which is how DeepSeek-R1 learned to reason from verifiable rewards. And an agent (10.3 Reasoning and planning for agents) that chooses tools, observes results and continues is an MDP in which the tool outputs are the environment's transitions; the same credit-assignment problem, reward hacking (8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI, 10.10 Agent safety and security) and exploration questions apply.

Where this shows up later

• Huber loss for value regression and the softmax policy head — 4.3 Loss functions catalog; optimizers and clipping — 4.5 Optimizers and learning-rate schedules.
• RLHF with PPO, reward models and KL penalties; DPO as the alternative that avoids RL — 8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI; RL with verifiable rewards and GRPO in reasoning models — 8.6 Reasoning models and test-time compute.
• Agents as decision processes, planning as search over actions, reward hacking and safety — 10.3 Reasoning and planning for agents, 10.9 Evaluating agents, 10.10 Agent safety and security.