Skip to content

Reinforcement Learning Basics

What you’ll learn. The reinforcement learning (RL) problem formulation as a Markov decision process; value functions and the Bellman equations; dynamic programming, Monte Carlo, and temporal-difference learning; Q-learning and DQN; the policy gradient theorem, REINFORCE, actor-critic, and PPO; and how these ideas carry over to RLHF and RL with verifiable rewards for language models. Includes runnable tabular Q-learning and a REINFORCE sketch.

Supervised learning gets labeled examples (x,y)(x,y). In RL an agent interacts with an environment, choosing actions and receiving only a scalar reward, often delayed. It must discover which actions produced good outcomes (the credit assignment problem), explore to gather information, and exploit what it knows (the exploration-exploitation trade-off). The data distribution depends on the agent’s own behavior, so data is non-i.i.d. and non-stationary as the policy improves.

An MDP is a tuple (S,A,P,R,γ)(\mathcal S,\mathcal A,P,R,\gamma):

  • states s∈Ss\in\mathcal S, actions a∈Aa\in\mathcal A;
  • transition dynamics P(s′∣s,a)P(s'\mid s,a) and reward R(s,a)R(s,a) (or rt+1r_{t+1});
  • discount γ∈[0,1)\gamma\in[0,1).

Markov property: the next state and reward depend only on the current state and action, not the earlier history. A policy π(a∣s)\pi(a\mid s) gives action probabilities. The return from time tt is the discounted sum

Gt=∑k=0∞γkrt+k+1=rt+1+γGt+1.G_t=\sum_{k=0}^\infty\gamma^kr_{t+k+1}=r_{t+1}+\gamma G_{t+1}.

The goal: find π\pi maximizing expected return J(π)=Eπ[G0]J(\pi)=\mathbb{E}_\pi[G_0]. Discounting makes infinite sums finite and encodes preference for earlier reward; γ\gamma also sets an effective horizon ≈1/(1−γ)\approx1/(1-\gamma).

Value functions.

Vπ(s)=Eπ[Gt∣st=s],Qπ(s,a)=Eπ[Gt∣st=s,at=a],Aπ(s,a)=Qπ(s,a)−Vπ(s).V^\pi(s)=\mathbb{E}_\pi[G_t\mid s_t=s],\qquad Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid s_t=s,a_t=a],\qquad A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s).

The advantage AA says how much better action aa is than the policy’s average action in ss.

The recursive structure of the return gives the Bellman expectation equations:

Vπ(s)=∑aπ(a∣s)∑s′P(s′∣s,a)[R(s,a)+γVπ(s′)],V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\big[R(s,a)+\gamma V^\pi(s')\big], Qπ(s,a)=R(s,a)+γ∑s′P(s′∣s,a)∑a′π(a′∣s′)Qπ(s′,a′).Q^\pi(s,a)=R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\sum_{a'}\pi(a'\mid s')Q^\pi(s',a').

The Bellman optimality equation for the best achievable value:

Q⋆(s,a)=R(s,a)+γ∑s′P(s′∣s,a)max⁡a′Q⋆(s′,a′),π⋆(s)=arg⁡max⁡aQ⋆(s,a).Q^\star(s,a)=R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\max_{a'}Q^\star(s',a'),\qquad\pi^\star(s)=\arg\max_aQ^\star(s,a).

The Bellman optimality operator is a γ\gamma-contraction in the max norm, so repeated application (value iteration) converges to Q⋆Q^\star from any start. Policy iteration alternates policy evaluation (solve for VπV^\pi) and greedy improvement. These dynamic programming methods need the model P,RP,R. RL algorithms learn from sampled experience instead.

  • Monte Carlo (MC): run full episodes and average observed returns, V(s)←V(s)+α(Gt−V(s))V(s)\leftarrow V(s)+\alpha(G_t-V(s)). Unbiased but high variance; needs episodes to end.
  • Temporal-difference (TD) learning: bootstrap from the current estimate. TD(0):
V(st)←V(st)+α[rt+1+γV(st+1)−V(st)⏟δt (TD error)].V(s_t)\leftarrow V(s_t)+\alpha\big[\underbrace{r_{t+1}+\gamma V(s_{t+1})-V(s_t)}_{\delta_t\ \text{(TD error)}}\big].

Lower variance, biased (relies on the estimate), online. nn-step returns and TD(λ\lambda) interpolate between TD and MC; GAE (below) is the policy-gradient analogue.

Off-policy TD control: learn Q⋆Q^\star directly while following any exploratory behavior policy:

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)].Q(s,a)\leftarrow Q(s,a)+\alpha\Big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\Big].

Exploration via ϵ\epsilon-greedy (random action with probability ϵ\epsilon). SARSA is the on-policy variant using the next action actually taken.

import numpy as np
# Tiny gridworld: 1D corridor of 6 states; reward 1 for reaching the right end.
n_states, actions = 6, [-1, +1] # move left / right
Q = np.zeros((n_states, 2))
rng = np.random.default_rng(0)
alpha, gamma, eps = 0.1, 0.95, 0.2
for episode in range(500):
s = 0
while s != n_states - 1:
a = rng.integers(2) if rng.random() < eps else int(Q[s].argmax())
s2 = int(np.clip(s + actions[a], 0, n_states - 1))
r = 1.0 if s2 == n_states - 1 else 0.0
target = r + (0 if s2 == n_states - 1 else gamma * Q[s2].max())
Q[s, a] += alpha * (target - Q[s, a])
s = s2
print(np.round(Q, 2)) # "right" values exceed "left"; Q grows toward the goal as gamma^k

Deep Q-networks (DQN) (Mnih et al., 2015) replace the table with a neural network Qθ(s,a)Q_\theta(s,a) trained by regression on the TD target. Naive bootstrapping with function approximation is unstable (“deadly triad”: function approximation, bootstrapping, off-policy data). DQN stabilizes it with an experience replay buffer (decorrelates samples) and a slowly updated target network providing max⁡a′Qθ−(s′,a′)\max_{a'}Q_{\theta^-}(s',a'). Extensions: Double DQN (reduces overestimation from the max), dueling networks, prioritized replay, distributional RL, Rainbow (a combination). Value-based methods require discrete, enumerable actions for the max.

Instead of deriving the policy from values, parameterize πθ(a∣s)\pi_\theta(a\mid s) directly and ascend J(θ)J(\theta). This handles continuous actions and stochastic policies naturally.

Policy gradient theorem. Using the log-derivative trick ∇θp=p∇θlog⁡p\nabla_\theta p=p\nabla_\theta\log p,

∇θJ(θ)=Eτ∼πθ[∑t∇θlog⁡πθ(at∣st) Gt].\nabla_\theta J(\theta)=\mathbb{E}_{\tau\sim\pi_\theta}\Big[\sum_t\nabla_\theta\log\pi_\theta(a_t\mid s_t)\,G_t\Big].

Intuition: increase the log-probability of actions in proportion to the return that followed. The dynamics PP drop out of the gradient. This is the score-function (REINFORCE) estimator, the general tool for differentiating through sampling when the reparameterization trick (Generative Models) does not apply.

Variance reduction. Subtracting a baseline b(st)b(s_t) that does not depend on the action leaves the gradient unbiased and can cut variance greatly. The best common choice is Vπ(st)V^\pi(s_t), yielding the advantage:

∇θJ=E[∇θlog⁡πθ(at∣st) Aπ(st,at)].\nabla_\theta J=\mathbb{E}\big[\nabla_\theta\log\pi_\theta(a_t\mid s_t)\,A^\pi(s_t,a_t)\big].

Actor-critic: the actor is πθ\pi_\theta, the critic is a learned VϕV_\phi used to estimate advantages, e.g. with the TD error δt\delta_t or generalized advantage estimation (GAE): A^t=∑l≥0(γλ)lδt+l\hat A_t=\sum_{l\ge0}(\gamma\lambda)^l\delta_{t+l}, with λ\lambda trading bias for variance.

import torch, torch.nn as nn
class Policy(nn.Module):
def __init__(self, obs, n_act):
super().__init__()
self.net = nn.Sequential(nn.Linear(obs, 64), nn.Tanh(), nn.Linear(64, n_act))
def forward(self, s): return torch.distributions.Categorical(logits=self.net(s))
def reinforce_update(policy, opt, states, actions, rewards, gamma=0.99):
G, returns = 0.0, []
for r in reversed(rewards):
G = r + gamma * G; returns.append(G)
returns = torch.tensor(returns[::-1])
returns = (returns - returns.mean()) / (returns.std() + 1e-8) # simple baseline/normalization
logp = policy(torch.stack(states)).log_prob(torch.tensor(actions))
loss = -(logp * returns).mean()
opt.zero_grad(); loss.backward(); opt.step()

Policy gradient methods are on-policy (data must come from the current policy) and notoriously sample-inefficient, sensitive to step size: one bad update can collapse the policy, and the next batch of data is then bad too.

TRPO (Schulman et al., 2015) maximizes the surrogate objective subject to a KL constraint between old and new policies, guaranteeing (approximately) monotonic improvement, but needs second-order machinery. PPO (Schulman et al., 2017) achieves similar stability with a first-order clipped objective. With the probability ratio ρt(θ)=πθ(at∣st)/πθold(at∣st)\rho_t(\theta)=\pi_\theta(a_t\mid s_t)/\pi_{\theta_{old}}(a_t\mid s_t):

LCLIP(θ)=Et[min⁡(ρtA^t, clip⁡(ρt,1−ε,1+ε)A^t)],ε≈0.1-0.2.L^{CLIP}(\theta)=\mathbb{E}_t\Big[\min\big(\rho_t\hat A_t,\ \operatorname{clip}(\rho_t,1-\varepsilon,1+\varepsilon)\hat A_t\big)\Big],\quad\varepsilon\approx0.1\text{-}0.2.

When the advantage is positive, there is no incentive to raise the ratio beyond 1+ε1+\varepsilon; when negative, none to lower it below 1−ε1-\varepsilon. This removes the gain from moving the policy too far, so you can safely run several epochs of minibatch updates on one batch of data. A full PPO loss adds a value-function loss and an entropy bonus (encouraging exploration): L=−LCLIP+c1LVF−c2H[π]L=-L^{CLIP}+c_1L^{VF}-c_2H[\pi]. PPO is the workhorse for continuous control, games, and (historically) RLHF. Its many implementation details (advantage normalization, value clipping, learning-rate annealing, orthogonal init) matter as much as the objective.

  • Continuous control, off-policy actor-critic: DDPG, TD3, SAC (maximum-entropy RL; strong sample efficiency and robustness).
  • Model-based RL: learn a dynamics model and plan or train inside it (Dyna, MuZero, Dreamer); more sample-efficient, but model errors compound.
  • Imitation learning / behavior cloning, inverse RL: learn from demonstrations; behavior cloning suffers from compounding distribution shift (DAgger addresses it).
  • Offline RL: learn from a fixed dataset without interaction; must avoid overestimating values for out-of-distribution actions (CQL, IQL).
  • Exploration: curiosity/intrinsic motivation, count-based bonuses, Thompson sampling. Bandits are the single-state special case with the same explore/exploit tension.
  • Multi-agent RL, hierarchical RL, partial observability (POMDPs; recurrent policies).

A language model is a policy: state = prompt plus tokens so far, action = next token, an episode = a generated completion. Reinforcement learning from human feedback (RLHF) (Christiano et al., 2017; Ziegler et al., 2019; Ouyang et al., 2022, InstructGPT) pipeline:

  1. Supervised fine-tuning (SFT) on demonstrations.
  2. Reward model: collect human preference comparisons between completions and train rψ(x,y)r_\psi(x,y) using the Bradley-Terry model, P(yw≻yl)=σ(r(yw)−r(yl))P(y_w\succ y_l)=\sigma\big(r(y_w)-r(y_l)\big), by maximizing log-likelihood (Statistics & Estimation).
  3. RL optimization (PPO historically) of the policy to maximize reward while staying near the SFT/reference model with a KL penalty:
max⁡θ Ey∼πθ[rψ(x,y)]−β DKL(πθ(⋅∣x)∥πref(⋅∣x)).\max_\theta\ \mathbb{E}_{y\sim\pi_\theta}\big[r_\psi(x,y)\big]-\beta\,D_{KL}\big(\pi_\theta(\cdot\mid x)\parallel\pi_{ref}(\cdot\mid x)\big).

The KL term (Information Theory) limits drift and reward hacking: optimizing an imperfect proxy reward eventually degrades true quality (Goodhart’s law).

Direct Preference Optimization (DPO) (Rafailov et al., 2023) shows the KL-regularized objective has a closed-form optimal policy and derives a supervised loss on preference pairs directly, with no reward model or RL loop:

LDPO=−log⁡σ(βlog⁡πθ(yw∣x)πref(yw∣x)−βlog⁡πθ(yl∣x)πref(yl∣x)).L_{DPO}=-\log\sigma\Big(\beta\log\tfrac{\pi_\theta(y_w|x)}{\pi_{ref}(y_w|x)}-\beta\log\tfrac{\pi_\theta(y_l|x)}{\pi_{ref}(y_l|x)}\Big).

Simpler and cheaper, so very widely used, though online RL methods can outperform offline preference optimization in some settings.

RL with verifiable rewards (RLVR): for math, code, and other tasks with checkable answers, the reward comes from a verifier (exact match, unit tests) rather than a learned model, which resists reward hacking better. This underlies recent “reasoning” models trained with long chains of thought. Critic-free methods such as GRPO (introduced in the DeepSeekMath work) estimate the advantage by normalizing rewards across a group of sampled completions for the same prompt, avoiding a separate value network; many variants followed. The details of production recipes are mostly not public and change quickly, so treat specifics as moving targets.

Open problems: reward model overoptimization, noisy or biased human preferences, credit assignment across long outputs, exploration collapse (entropy shrinking), and verifying more than the final answer.

  • RL is high-variance; run multiple seeds and report confidence intervals. Differences of a few percent between algorithms are often seed noise.
  • Start with a simple environment (Gymnasium CartPole, then LunarLander) and a trusted implementation (Stable-Baselines3, CleanRL) before writing your own.
  • Reward design is half the problem: sparse rewards are hard to learn from; shaped rewards can be exploited in unintended ways.
  • Monitor episode return, value loss, policy entropy, KL to the old policy, and clipping fraction.
  • Normalize observations and advantages; clip gradients.
  • An MDP is states, actions, transitions, rewards, discount; the objective is expected discounted return.
  • Bellman equations express value recursively; optimality gives Q⋆Q^\star, whose argmax is the optimal policy.
  • TD learning bootstraps; Q-learning is off-policy and learns Q⋆Q^\star; DQN adds replay and target networks.
  • Policy gradients ascend E[∇log⁡π⋅A]\mathbb{E}[\nabla\log\pi\cdot A]; baselines and critics reduce variance.
  • PPO clips the probability ratio to keep updates small and stable.
  • RLHF treats an LLM as a policy optimized against a preference-trained reward with a KL anchor; DPO and verifiable-reward RL are major variants.
  1. Derivation. Show that subtracting a state-dependent baseline b(s)b(s) does not bias the policy gradient (use Ea∼π[∇log⁡π(a∣s)]=0\mathbb{E}_{a\sim\pi}[\nabla\log\pi(a|s)]=0).
  2. Computation. A two-state MDP: from A, action “go” yields reward 0 and moves to B; in B any action yields reward 1 and returns to A. With γ=0.9\gamma=0.9 compute V(A)V(A) and V(B)V(B) under this deterministic cycle.
  3. Hands-on. Implement Q-learning for a 4x4 FrozenLake (Gymnasium); compare ϵ\epsilon-greedy with decaying ϵ\epsilon.
  4. Hands-on. Train REINFORCE on CartPole with and without a baseline; plot return variance across 5 seeds.
  5. Conceptual. Why does the PPO objective use a min with the clipped term rather than clipping alone? Why does RLHF include a KL penalty to a reference model?
Solutions (1, 2)
  1. Ea[∇log⁡π(a∣s)b(s)]=b(s)∑a∇π(a∣s)=b(s)∇∑aπ(a∣s)=b(s)∇1=0\mathbb{E}_a[\nabla\log\pi(a|s)b(s)]=b(s)\sum_a\nabla\pi(a|s)=b(s)\nabla\sum_a\pi(a|s)=b(s)\nabla1=0.
  2. V(A)=0+0.9V(B)V(A)=0+0.9V(B), V(B)=1+0.9V(A)V(B)=1+0.9V(A). Substituting: V(B)=1+0.81V(B)V(B)=1+0.81V(B), so V(B)=1/0.19≈5.26V(B)=1/0.19\approx5.26, V(A)≈4.74V(A)\approx4.74.
  • Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., 2018), free online.
  • Mnih et al., “Human-level control through deep reinforcement learning” (2015).
  • Schulman et al., “Trust Region Policy Optimization” (2015); “High-Dimensional Continuous Control Using Generalized Advantage Estimation” (2015); “Proximal Policy Optimization Algorithms” (2017).
  • Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning” (1992).
  • Haarnoja et al., “Soft Actor-Critic” (2018).
  • Christiano et al., “Deep RL from Human Preferences” (2017); Ouyang et al., “Training language models to follow instructions with human feedback” (2022).
  • Rafailov et al., “Direct Preference Optimization” (2023).
  • Shao et al., “DeepSeekMath” (2024), introducing GRPO.
  • OpenAI, “Spinning Up in Deep RL” (educational resource); Huang et al., “The 37 Implementation Details of Proximal Policy Optimization” (2022).