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.
What makes RL different
Section titled “What makes RL different”Supervised learning gets labeled examples . 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.
Markov decision processes
Section titled “Markov decision processes”An MDP is a tuple :
- states , actions ;
- transition dynamics and reward (or );
- discount .
Markov property: the next state and reward depend only on the current state and action, not the earlier history. A policy gives action probabilities. The return from time is the discounted sum
The goal: find maximizing expected return . Discounting makes infinite sums finite and encodes preference for earlier reward; also sets an effective horizon .
Value functions.
The advantage says how much better action is than the policy’s average action in .
Bellman equations
Section titled “Bellman equations”The recursive structure of the return gives the Bellman expectation equations:
The Bellman optimality equation for the best achievable value:
The Bellman optimality operator is a -contraction in the max norm, so repeated application (value iteration) converges to from any start. Policy iteration alternates policy evaluation (solve for ) and greedy improvement. These dynamic programming methods need the model . RL algorithms learn from sampled experience instead.
Learning from experience
Section titled “Learning from experience”- Monte Carlo (MC): run full episodes and average observed returns, . Unbiased but high variance; needs episodes to end.
- Temporal-difference (TD) learning: bootstrap from the current estimate. TD(0):
Lower variance, biased (relies on the estimate), online. -step returns and TD() interpolate between TD and MC; GAE (below) is the policy-gradient analogue.
Q-learning
Section titled “Q-learning”Off-policy TD control: learn directly while following any exploratory behavior policy:
Exploration via -greedy (random action with probability ). 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 / rightQ = 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^kDeep Q-networks (DQN) (Mnih et al., 2015) replace the table with a neural network 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 . 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.
Policy gradients
Section titled “Policy gradients”Instead of deriving the policy from values, parameterize directly and ascend . This handles continuous actions and stochastic policies naturally.
Policy gradient theorem. Using the log-derivative trick ,
Intuition: increase the log-probability of actions in proportion to the return that followed. The dynamics 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 that does not depend on the action leaves the gradient unbiased and can cut variance greatly. The best common choice is , yielding the advantage:
Actor-critic: the actor is , the critic is a learned used to estimate advantages, e.g. with the TD error or generalized advantage estimation (GAE): , with 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.
Trust regions and PPO
Section titled “Trust regions and PPO”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 :
When the advantage is positive, there is no incentive to raise the ratio beyond ; when negative, none to lower it below . 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): . 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.
Other algorithm families
Section titled “Other algorithm families”- 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).
Link to RLHF and LLM post-training
Section titled “Link to RLHF and LLM post-training”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:
- Supervised fine-tuning (SFT) on demonstrations.
- Reward model: collect human preference comparisons between completions and train using the Bradley-Terry model, , by maximizing log-likelihood (Statistics & Estimation).
- RL optimization (PPO historically) of the policy to maximize reward while staying near the SFT/reference model with a KL penalty:
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:
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.
Practical advice
Section titled “Practical advice”- 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.
Key takeaways
Section titled “Key takeaways”- An MDP is states, actions, transitions, rewards, discount; the objective is expected discounted return.
- Bellman equations express value recursively; optimality gives , whose argmax is the optimal policy.
- TD learning bootstraps; Q-learning is off-policy and learns ; DQN adds replay and target networks.
- Policy gradients ascend ; 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.
Exercises
Section titled “Exercises”- Derivation. Show that subtracting a state-dependent baseline does not bias the policy gradient (use ).
- 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 compute and under this deterministic cycle.
- Hands-on. Implement Q-learning for a 4x4 FrozenLake (Gymnasium); compare -greedy with decaying .
- Hands-on. Train REINFORCE on CartPole with and without a baseline; plot return variance across 5 seeds.
- 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)
- .
- , . Substituting: , so , .
Further reading
Section titled “Further reading”- 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).