Foundations of Reinforcement Learning

TL;DR

Intuition

Supervised learning gets a label for every input. Reinforcement learning gets a scalar reward that arrives several decisions later, and the agent must figure out which of those decisions were responsible. The agent observes a state $s_t$, picks an action $a_t$, the environment returns a next state $s_{t+1}$ and a reward $r_t$, and the loop continues. The agent never sees the optimal action; it only sees the consequences of the action it tried. Two problems make this hard. First, credit assignment: a reward at step $T$ depends on every action between $0$ and $T$. Second, exploration vs exploitation: to learn what is good, the agent must sometimes try things it suspects are bad.

The framing that makes the math tractable is the Markov decision process. Pretend the world is memoryless: the next state and reward depend only on the current state and the chosen action, not on the history. Define a discount factor $\gamma \in [0, 1)$ so that distant rewards count for less, and an objective $J = \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^t r_t\right]$. The Bellman equations relate the value of a state to the values of its successors and turn the infinite-horizon planning problem into a fixed-point equation.

1. 1957Bellman: dynamic programmingfoundation

   Richard Bellman names the framework, writes the recursion V(s) = max_a [R(s,a) + gamma * E[V(s prime)]], and gives value iteration as the canonical solver. The whole field is downstream of this equation.

2. 1989Watkins: Q-learningpaper

   Q-learning is the off-policy temporal-difference rule that converges to Q* under mild conditions even when the behavior policy differs from the greedy one. Becomes the workhorse of tabular RL.

3. 1992Williams: REINFORCEpaper

   The first usable Monte Carlo policy-gradient estimator: nabla J = E[nabla log pi(a|s) * G_t]. Unbiased, high variance, and the ancestor of every modern policy-gradient method.

4. 2013DQN (Atari from pixels)paper

   DeepMind shows a single Q-network with experience replay and a target network learns 49 Atari games end-to-end from raw pixels at human-level performance on most of them.

5. 2015TRPOpaper

   Schulman et al. constrain each policy-gradient step to stay within a KL-divergence trust region, eliminating the catastrophic step problem of vanilla policy gradient.

6. 2016AlphaGo defeats Lee Sedolmilestone

   Policy + value networks plus Monte Carlo tree search beat a 9-dan professional 4-1. Demonstrates that deep RL plus search can solve a problem widely believed to be a decade away.

7. 2017PPOpaper

   A first-order, clipped-ratio surrogate that approximates the TRPO trust region with no Hessian-vector products. Becomes the default policy-gradient algorithm in practice.

8. 2017AlphaGo Zeromilestone

   Same architecture as AlphaGo, trained purely from self-play with no human games. Surpasses every prior version of AlphaGo within 40 days.

9. 2018SACpaper

   Soft Actor-Critic adds a maximum-entropy bonus to the standard actor-critic objective. Strong sample efficiency and stability on continuous-control benchmarks; widely deployed in robotics.

10. 2019MuZeropaper

    Model-based RL where the model is learned end-to-end with the value and policy heads, with no ground-truth simulator. Matches AlphaZero on board games and DQN on Atari with no environment model handed in.

Markov decision processes and the Bellman equations

A finite-horizon Markov decision process is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where $\mathcal{S}$ is the state set, $\mathcal{A}$ is the action set, $P(s' \mid s, a)$ is the transition kernel, $R(s, a)$ is the (expected) reward, and $\gamma \in [0, 1)$ is the discount factor. A policy $\pi(a \mid s)$ is a (possibly stochastic) mapping from states to actions. The infinite-horizon discounted return from time $t$ is

and the agent maximizes $J(\pi) = \mathbb{E}_\pi[G_0]$ over policies. Because $\gamma < 1$ and rewards are bounded, $G_t$ is always finite.

Two value functions encode “how good is it to be here”. The state-value function is

and the action-value function is

By conditioning on the next state and reward and using the Markov property, both satisfy a one-step recurrence (the Bellman expectation equation):

The optimal value functions are $V^*(s) = \max_\pi V^\pi(s)$ and $Q^*(s, a) = \max_\pi Q^\pi(s, a)$, and they satisfy the Bellman optimality equation:

Once $Q^*$ is known, the optimal policy is the deterministic greedy policy $\pi^*(s) = \arg\max_a Q^*(s, a)$.

Tabular methods: DP, MC, TD, SARSA, Q-learning

When $|\mathcal{S}|$ is small enough to fit in a table and $P, R$ are known, dynamic programming solves the MDP exactly. Value iteration repeats $V \leftarrow T^* V$ until convergence; policy iteration alternates evaluation ($V^\pi$ from the linear Bellman expectation system) and improvement ($\pi(s) \leftarrow \arg\max_a [R(s, a) + \gamma\, \mathbb{E} V^\pi(s')]$). Both are off-policy in the sense that the agent never has to interact with the environment; the model is given.

DP fails the moment the model is unknown or the state space is too large. The next two ideas relax those assumptions.

Monte Carlo (MC) methods estimate $V^\pi$ from sampled returns. Run a full episode under $\pi$, accumulate the actual discounted return $G_t$, and update $V(s_t) \leftarrow V(s_t) + \alpha\, [G_t - V(s_t)]$. MC is unbiased (the target $G_t$ is the true return) but high-variance and only updates at the end of an episode, so it is wasteful in long-horizon problems.

Temporal-difference (TD) methods sit between DP and MC. Instead of waiting for $G_t$, bootstrap from the current value estimate at the next step:

The bracketed term is the TD error $\delta_t = r_t + \gamma\, V(s_{t+1}) - V(s_t)$. TD updates every step, which is why it dominates MC in practice; the cost is bias from bootstrapping off an inexact $V$.

For control (estimating $Q^*$ rather than $V^\pi$), the same TD idea splits into two flavors that differ only in how they pick the next-step action used in the bootstrap. SARSA uses the action the agent actually took:

so it learns the value of the behavior policy. Q-learning uses the greedy action:

so it learns $Q^*$ even when the data is collected by an exploratory policy. SARSA is on-policy; Q-learning is off-policy. Under tabular conditions and a Robbins-Monro learning-rate schedule, both converge to the right fixed point.

DQN: deep Q-learning

Once the state is a $84 \times 84 \times 4$ stack of game-frames there is no table. Mnih et al. [2] replaced the Q-table with a convolutional network $Q_\theta(s, a)$ and trained it by minimizing the mean-squared TD error on a replay buffer of past transitions, with a target network $Q_{\theta^-}$ whose weights lag $Q_\theta$ by thousands of steps:

The replay buffer breaks temporal correlations: consecutive game frames are highly correlated and would make minibatch SGD biased; sampling a random minibatch from a million-transition buffer recovers an approximately i.i.d. estimate. The target network breaks the moving-target problem: if both sides of the TD error used $\theta$, every gradient step would shift the target as well as the estimate, and the value would chase its own tail. Freezing $\theta^-$ for $C$ steps (typically $10000$) and then copying $\theta^- \leftarrow \theta$ stabilizes training to roughly the same degree the target network is “stale” relative to $\theta$.

Three follow-ups cleaned up DQN’s known failure modes. Double DQN [3] noticed that the same network is used to both pick the action and evaluate it inside $\max_{a'} Q_{\theta^-}(s', a')$, which biases the bootstrap upward (the Q-overestimation bug). The fix decouples them: pick the action with the online network, evaluate it with the target network. Dueling DQN [4] splits $Q_\theta$ into a state-value head $V(s)$ and an advantage head $A(s, a)$ with $Q(s, a) = V(s) + A(s, a) - \mathrm{mean}_{a'} A(s, a')$, which decouples “is this state any good” from “which action is best here” and learns faster on states where actions are nearly tied. Rainbow [5] stacks Double DQN, Dueling DQN, prioritized replay, multi-step returns, distributional RL, and noisy nets, and shows that all six together beat any subset on the Atari-57 benchmark.

Policy gradients

DQN learns a value function and reads a policy off it. The other half of the field optimizes the policy directly. Parameterize $\pi_\theta(a \mid s)$ as a neural net (a softmax for discrete actions, a Gaussian for continuous ones) and follow the gradient of the expected return $J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[\sum_t \gamma^t r_t]$.

The unbiasedness of the policy gradient is a real result; the practical issue is variance. A REINFORCE estimator on a single trajectory has variance proportional to the squared range of returns, which is enormous in any non-trivial environment. Three variance-reduction tools are routinely stacked on top of plain REINFORCE: a learned value baseline (turns return into advantage), bootstrapped TD targets (replace $G_t$ with $r_t + \gamma\, V(s_{t+1})$), and GAE $\hat A_t^{\mathrm{GAE}(\gamma, \lambda)} = \sum_{k = 0}^\infty (\gamma \lambda)^k\, \delta_{t+k}$ with $\lambda \in [0, 1]$ tuning the bias-variance trade-off.

Actor-critic, TRPO, and PPO

Actor-critic combines a parametric policy (“actor”, trained by policy gradient) with a parametric value function (“critic”, trained by TD). A2C is the synchronous, batched form: collect $N$ environment steps under $\pi_{\theta_\mathrm{old}}$, fit the critic to bootstrapped returns, take one policy-gradient step on the actor, repeat. Vanilla A2C works when the steps are small; once they are too aggressive the on-policy assumption breaks and the run blows up.

TRPO [7] explicitly bounds the KL divergence between successive policies:

The constraint defines a trust region inside which the linearized objective is reliable. Solving it requires a Hessian-vector product per iteration; TRPO works well but is fiddly to implement.

Continuous control: DDPG, TD3, SAC

In continuous-action spaces, $\max_a Q(s, a)$ is no longer a finite enumeration; you cannot scan the action set every step. DDPG [11] handles this with a deterministic actor $\mu_\theta(s)$ trained by the chain rule through $Q_\phi$: take the gradient of $Q_\phi(s, \mu_\theta(s))$ with respect to $\theta$. The critic is trained off-policy via a target network and replay, exactly as in DQN. DDPG is sample-efficient but notoriously unstable: the actor and critic can chase each other into Q-overestimation territory.

TD3 [12] patches the three known DDPG failure modes. Twin critics: maintain two Q-networks $Q_{\phi_1}, Q_{\phi_2}$ and use the minimum of the two in the bootstrap target, which combats overestimation just like Double DQN does in the discrete case. Delayed policy updates: update the actor every $d$ critic updates (typically $d = 2$), which lets the critic catch up before the actor moves. Target-policy smoothing: add Gaussian noise to the target action $\mu_{\theta^-}(s') + \epsilon$ when computing the bootstrap, which regularizes the value estimate against narrow peaks. The combination is the standard off-policy continuous-control baseline.

SAC [10] takes a different angle: maximum-entropy RL. Augment the reward with the policy entropy:

The entropy bonus encourages the agent to keep its options open: among policies with the same expected return, prefer the one that hedges across actions. This makes exploration automatic (no separate $\epsilon$-greedy or noisy-net mechanism), produces robust policies that transfer better, and gives a soft Q-learning rule whose Bellman backup mixes the standard $\max$ with a softmax weighted by entropy. SAC dominates TD3 on most MuJoCo benchmarks and is the default choice for robotics simulation and sim-to-real.

Model-based RL and the search frontier

Model-free methods learn $\pi$ or $Q$ directly from interaction. Model-based methods learn (or are given) a transition model $\hat P$ and use it to plan. Classical examples include Dyna (interleave real and model-generated transitions) and PILCO (Gaussian-process dynamics + analytic policy evaluation). The modern poster children are AlphaZero [13] and MuZero [14].

AlphaZero combines a policy-and-value network with Monte Carlo tree search (MCTS). At each move, MCTS expands a tree from the current state, evaluating leaves with the value network and biasing rollouts with the policy network. The search itself is a powerful policy-improvement operator: the move distribution at the root is sharper and stronger than the raw policy network, and self-play between the search policy and itself produces training data that bootstraps both networks toward optimal play. The system reached superhuman strength in Go, Shogi, and Chess from a single architecture trained from scratch.

MuZero drops the assumption of a known simulator. The model is learned end to end with the value and policy heads: it predicts only the quantities the search needs (immediate reward, value, policy logits) given a learned latent dynamics function, not the actual next state. This makes the algorithm work on Atari (where there is no simulator at all from the agent’s point of view) at performance comparable to model-free DQN-class methods, while keeping AlphaZero’s strength on board games. MuZero is the proof of concept that deep model-based RL with learned latent dynamics can scale.

Tabular Q-learning and DQN side by side

import numpy as np

# Toy 4x4 Frozen Lake: 16 states, 4 actions (L, D, R, U).
# In a real run, env = gym.make("FrozenLake-v1"); we simulate the API here.
n_states, n_actions = 16, 4
Q = np.zeros((n_states, n_actions))

alpha = 0.1     # learning rate
gamma = 0.99    # discount
epsilon = 0.1   # epsilon-greedy
n_episodes = 5000

rng = np.random.default_rng(0)

def step(s, a):
  # placeholder dynamics: returns (s_next, reward, done)
  s_next = (s + a + 1) % n_states
  reward = 1.0 if s_next == n_states - 1 else 0.0
  done = s_next == n_states - 1
  return s_next, reward, done

for ep in range(n_episodes):
  s = 0
  done = False
  while not done:
      if rng.random() < epsilon:
          a = rng.integers(n_actions)               # explore
      else:
          a = int(np.argmax(Q[s]))                  # exploit
      s_next, r, done = step(s, a)
      td_target = r + gamma * np.max(Q[s_next]) * (not done)
      Q[s, a] += alpha * (td_target - Q[s, a])      # off-policy TD
      s = s_next

policy = Q.argmax(axis=1)

Real-world reinforcement learning

RL outside benchmarks is shaped by three forces: where the simulator comes from, how expensive an interaction is, and how much you trust the reward signal. The 2016 AlphaGo match against Lee Sedol was watershed because the simulator (the rules of Go) was free and exact and the reward (winning a game) was unambiguous. AlphaZero and MuZero pushed the same recipe to chess, shogi, and Atari, with MuZero showing that the simulator itself can be learned from interaction. OpenAI Five (Dota 2) and AlphaStar (StarCraft II) scaled up self-play in much larger action and state spaces, with PPO-style updates and curriculum learning over millions of games.

In robotics, the simulator is approximate and the cost of a real-world step is high. The dominant pattern is sim-to-real transfer: train a policy in simulation with domain randomization (vary masses, frictions, lighting, sensor noise, latency), then deploy the resulting policy on hardware. SAC’s entropy regularizer and TD3’s twin critics are the off-policy backbones of choice; domain randomization is the regularizer that makes the simulator-to-reality gap survivable. OpenAI’s in-hand cube manipulation work is the canonical demonstration that this pipeline can deliver dexterous manipulation from a single policy trained entirely in simulation.

In recommender systems and online platforms, the agent picks an item and gets a click or a conversion. The state is summarized by user features, the action set is the catalog, and the reward is sparse and delayed. The dominant tool is contextual bandits: at each step, observe a context, pick an arm, see a reward; treat each round as independent (no transitions). Thompson sampling and LinUCB dominate when the action set is bounded and stationary; for very large action sets, two-stage ranking (candidate generation + bandit-style re-ranker) is the standard production pattern. Full MDP-style RL appears mainly when there is meaningful long-horizon credit assignment (slate recommendation that must steer toward eventual subscription, not just next click).

In dialog systems and language models, the technique that crossed the chasm is RLHF. Christiano et al. [15] introduced the recipe: collect human preferences on pairs of trajectories, fit a reward model, and optimize the policy with PPO under a KL penalty against a frozen reference. The same machinery is the backbone of InstructGPT and ChatGPT; the dedicated chapter on RLHF and alignment walks through the full pipeline.

Pitfalls

Pop quiz

Interview Q&A

Interactive Demo

Q-Learning Grid World

Value Iteration