What is reinforcement learning?

The formal setting#

Reinforcement learning studies sequential decision making under uncertainty, usually formalised as a Markov decision process $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

• $\mathcal{S}$ — the state space.
• $\mathcal{A}$ — the action space.
• $P(s' \mid s, a)$ — the transition kernel, the probability of landing in $s'$ after taking $a$ in $s$.
• $R(s, a)$ — the reward function, often a distribution with mean $r(s,a)$.
• $\gamma \in [0, 1)$ — the discount factor.

The agent is a policy $\pi(a \mid s)$, a distribution over actions given a state. The quantity being maximised is the expected discounted return:

$$ J(\pi) = \mathbb{E}{\tau \sim \pi}\left[ \sum{t=0}^{\infty} \gamma^t R_{t+1} \right], \qquad G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$

Here $\tau = (s_0, a_0, r_1, s_1, \dots)$ is a trajectory drawn by running $\pi$ in the environment, and $G_t$ is the return from time $t$ onwards.

$\gamma$ does more work than it appears to. It keeps the sum finite for continuing tasks, it encodes a preference for sooner rewards, and it acts as a variance-reduction knob: a smaller $\gamma$ shortens the effective horizon to roughly $1/(1-\gamma)$ and makes credit assignment easier at the cost of bias. See the MDP lesson for the Bellman machinery.

Why this is not supervised learning#

The distinction is not cosmetic. Four properties break the standard statistical learning setup.

1. No supervision, only evaluation. A label states what you should have done. A reward states how well what you did turned out. Evaluative feedback carries strictly less information per sample.
2. The data distribution depends on the parameters. $\pi_\theta$ generates the states it then trains on. The i.i.d. assumption behind most generalisation bounds does not hold, and improving $\theta$ shifts the distribution under which $\theta$ is next evaluated.
3. Delayed credit. The learning signal for an action at time $t$ may only arrive at $t + 1000$. The variance of Monte-Carlo return estimates grows with the horizon.
4. Exploration is part of the objective. A supervised learner cannot improve its own dataset. An RL agent must, and doing so optimally trades against exploiting what it already knows.

Sample complexity, honestly#

For a tabular MDP with $|\mathcal{S}|$ states and $|\mathcal{A}|$ actions, obtaining an $\varepsilon$-optimal policy given a generative model requires on the order of $\tilde{\Theta}!\left( \frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^3 \varepsilon^2} \right)$ samples (Azar, Munos and Kappen, 2013, with a matching lower bound in Azar et al., 2012). The $(1-\gamma)^{-3}$ term is the one that hurts: at $\gamma = 0.99$ that factor alone is $10^6$.

Deep RL has no comparable guarantee. Published Atari results routinely use 200 million frames per game — roughly 38 days of continuous human play — to reach human-level scores. Sample efficiency, not asymptotic performance, is the binding constraint in almost every real deployment.

The reward hypothesis, and its critics#

Sutton's reward hypothesis states that every goal can be described as maximisation of expected cumulative scalar reward. It is a hypothesis, not a theorem, and it is contested. Abel et al. (2021), On the Expressivity of Markov Reward, construct tasks — certain orderings and multi-objective preferences — for which no Markov reward function induces the desired set of optimal policies. Worth reading before assuming any objective can be compressed into one number.

Landmarks#

• Samuel (1959), Some Studies in Machine Learning Using the Game of Checkers — temporal-difference learning before it had the name.
• Sutton (1988), Learning to Predict by the Methods of Temporal Differences — TD($\lambda$).
• Watkins and Dayan (1992), Q-learning — the convergence proof for off-policy control.
• Tesauro (1994), TD-Gammon — a neural network reaching world-class backgammon through self-play.
• Mnih et al. (2015), Human-level control through deep reinforcement learning, Nature 518:529-533 — DQN. The earlier workshop version is Playing Atari with Deep Reinforcement Learning (2013), arxiv.org/abs/1312.5602.
• Silver et al. (2017), Mastering the game of Go without human knowledge — AlphaGo Zero.
• Ouyang et al. (2022), Training language models to follow instructions with human feedback — InstructGPT, arxiv.org/abs/2203.02155.

The standard text is Sutton and Barto, Reinforcement Learning: An Introduction (2nd edition, 2018). It is free online and it is the best book in the field.

Where the field actually is#

Two honest observations about the current state.

Reproducibility is poor. Henderson et al. (2018), Deep Reinforcement Learning that Matters, showed that identical algorithms run with different random seeds produce non-overlapping performance distributions on standard benchmarks. Report your seeds, report variance across at least five of them, and treat any single-run curve with suspicion.

The largest deployed use of RL today is not robotics or games. It is preference optimisation on language models. RLHF and its offline relatives put more reinforcement learning into daily human use than every robot arm combined.

What to learn next#

• Agents, environments and rewards — the three pieces, taken apart properly.
• Exploration vs exploitation — the trade-off that decides whether an agent learns at all.
• What is machine learning? — how the rest of the field is set up, for contrast.