The agent–environment loop

Supervised learning learns from labelled examples; reinforcement learning (RL) learns from consequences. An agent observes the state \(s_t\) of its environment, picks an action \(a_t\), then receives a reward \(r_{t+1}\) and a new state \(s_{t+1}\). No "correct answer" is ever provided: a scalar signal, often sparse and delayed, is the only guide.

A founding example: tic-tac-toe

Sutton and Barto open their book with a disarmingly simple example: learning to play tic-tac-toe against an imperfect opponent, without knowing its strategy. The idea: assign each board configuration a value \(V(s)\) — the estimated probability of winning from \(s\) — then, after each greedy move taking \(s\) to \(s'\), nudge the starting value towards the landing one: \[V(s) \leftarrow V(s) + \alpha\,\big[V(s') - V(s)\big].\]

This tiny rule already carries the DNA of the whole field: learn during interaction, with no model of the opponent, propagating information from terminal states (win = 1, loss = 0) back to the states that precede them. It is the first temporal-difference update — the one we will meet again, generalized, in Q-learning.

k-armed bandits: explore or exploit

Even before states enter the picture, RL's central dilemma appears in its purest form: the k-armed bandit (Sutton & Barto, ch. 2). A slot machine with \(k\) levers; each lever \(a\) pays a random reward with unknown mean \(q_*(a)\). Which lever should you pull, knowing that every try informs as much as it pays?

The natural estimator is the sample average of the rewards received: \[Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \,\mathbb{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_i = a}},\] which converges to \(q_*(a)\) by the law of large numbers. The greedy policy \(A_t = \arg\max_a Q_t(a)\) exploits without ever exploring — and frequently gets stuck on a mediocre lever. The \(\varepsilon\)-greedy strategy fixes this by playing at random with probability \(\varepsilon\). Subtler still, the UCB (Upper Confidence Bound) rule explores what is uncertain first: \[A_t = \arg\max_a \left[\, Q_t(a) + c\,\sqrt{\frac{\ln t}{N_t(a)}} \,\right],\] where \(N_t(a)\) counts the pulls of lever \(a\): the exploration bonus melts away as uncertainty is resolved.

Markov decision processes

The standard mathematical framework is the Markov decision process (MDP), a quintuple \((\mathcal{S}, \mathcal{A}, P, R, \gamma)\): state space, action space, transition kernel \(P(s' \mid s, a)\), reward function \(R(s,a)\) and discount factor. The Markov assumption requires the state to summarize all relevant history: \[\mathbb{P}(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots) = \mathbb{P}(s_{t+1} \mid s_t, a_t).\]

A policy \(\pi(a \mid s)\) is a distribution over actions conditioned on the state. Solving an MDP means finding the policy \(\pi^*\) that maximizes expected return — an optimization problem over a function space, where random transitions make the objective stochastic.

Value functions and Bellman equations

The state-value function measures "how good it is to be" in \(s\) under policy \(\pi\): \[V^\pi(s) = \mathbb{E}_\pi\!\left[\, G_t \mid s_t = s \,\right].\] The recursive structure of the return, \(G_t = r_{t+1} + \gamma\, G_{t+1}\), immediately yields the Bellman equation: \[V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^\pi(s') \,\right].\]

For the optimal policy, the sum over actions becomes a maximum — the Bellman optimality equation: \[V^*(s) = \max_a \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^*(s') \,\right].\]

Value iteration, in pictures

When the model \(P\) is known, we can apply \(\mathcal{T}\) repeatedly: \(V_{k+1} = \mathcal{T}V_k\). This is value iteration, a pure exercise in dynamic programming. In the gridworld below, value "diffuses" outward from the goal cell (green, \(+1\)), routing around the trap (red, \(-1\)) and the wall, attenuated by \(\gamma\) at every step. Once \(V^*\) is in hand, the greedy policy \(\pi^*(s) = \arg\max_a \mathbb{E}[R + \gamma V^*(s')]\) can be read off directly — and the agent follows it.

Q-learning: learning without a model

In practice \(P\) and \(R\) are unknown — all we can do is interact. The workaround is to estimate the state–action value function \(Q(s,a)\) directly from observed transitions. After every step \((s_t, a_t, r_{t+1}, s_{t+1})\), Q-learning performs the temporal-difference update: \[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[\, \underbrace{r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')}_{\text{TD target}} - Q(s_t, a_t) \,\right].\]

Two ideas hide in there. First, this is a stochastic approximation of the Bellman optimality equation: the expectation over \(P\) is replaced by a single sample. Second, the agent must balance exploration and exploitation — the \(\varepsilon\)-greedy strategy takes a random action with probability \(\varepsilon\), which is annealed over episodes.

Cliff Walking: SARSA vs Q-learning

Example 6.6 in Sutton & Barto makes the on/off-policy distinction visible. An agent must travel from start S to goal G along a cliff edge: every step costs \(-1\), falling into the cliff costs \(-100\) and instantly sends the agent back to the start. SARSA updates with the action it actually takes next: \[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\big[r_{t+1} + \gamma\, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\big],\] where Q-learning uses \(\max_{a'} Q(s_{t+1}, a')\) instead.

The consequence, as long as \(\varepsilon\)-greedy exploration is maintained (\(\varepsilon = 0.1\)): Q-learning learns the optimal policy — hugging the cliff — but its exploratory lurches regularly send it over the edge, and its average online return is worse. SARSA, which "knows" it explores, learns the safe path along the top. Optimality of the learned policy and performance during learning are two different things — a lesson that carries far beyond gridworlds, from algorithmic trading to industrial control.

Towards Deep RL

A \(Q(s,a)\) table becomes untenable as soon as the state space explodes (images, continuous systems, fluid flows…). Deep RL replaces the table with a neural network \(Q_\theta(s,a)\) or a parameterized policy \(\pi_\theta(a \mid s)\). Two main families dominate:

• Value-based methods (DQN and descendants): minimize the Bellman error \(\; \mathcal{L}(\theta) = \mathbb{E}\big[(r + \gamma \max_{a'} Q_{\theta^-}(s',a') - Q_\theta(s,a))^2\big]\), stabilized by a target network \(\theta^-\) and a replay buffer that breaks temporal correlations.
• Policy-based methods: ascend the performance gradient \(\; \nabla_\theta J = \mathbb{E}\big[\nabla_\theta \log \pi_\theta(a \mid s)\, A^\pi(s,a)\big]\) (the policy gradient theorem), where the advantage \(A^\pi\) reduces variance. PPO and its actor–critic variants are the modern representatives.

RL then meets optimal control: the Bellman equation is the discrete-time counterpart of the Hamilton–Jacobi–Bellman equation, and Q-learning can be read as a stochastic, model-free way of solving it. This bridge — dynamic programming, stochastic approximation, non-convex optimization — is what makes the field so mathematically rich. For a concrete application to flow control, see the companion article on physics-based machine learning.

From backgammon to Go: three milestones

TD-Gammon (Tesauro, 1992) was the first shock: a neural network trained by TD(\(\lambda\)) through self-play, starting from random weights, reached the level of the world's best backgammon players — to the point of changing human opening theory. DQN (2015) applied deep Q-learning to 49 Atari games, from raw pixels alone, with a single network and a single set of hyperparameters, reaching human level on most of them. AlphaGo and then AlphaGo Zero (2016–2017) combined policy and value networks with Monte Carlo tree search; Zero, trained purely by self-play with no human games at all, surpassed every previous version.

The common thread of these milestones (Sutton & Barto, ch. 16) is exactly that of this article: a value function learned by temporal difference, a policy improved against that value, and self-play as an inexhaustible generator of experience.

Reproducing these animations with Manim

The animations above run live in the browser (canvas), but their aesthetic comes from Manim. Here is a ManimCE skeleton that renders the value-iteration animation as a video — adapt it and render with manim -pqh rl_scenes.py ValueIteration:

# rl_scenes.py — value iteration in a gridworld
from manim import *
import numpy as np

class ValueIteration(Scene):
    def construct(self):
        rows, cols, gamma = 5, 8, 0.9
        V = np.zeros((rows, cols)); V[1, 6] = 1.0; V[2, 6] = -1.0
        squares = VGroup(*[
            Square(0.75).move_to(RIGHT*(c-3.5)*0.8 + UP*(2-r)*0.8)
            for r in range(rows) for c in range(cols)
        ])
        self.play(Create(squares, lag_ratio=0.02))
        for sweep in range(12):
            V = self.bellman_sweep(V, gamma)          # V ← max_a E[R + γV']
            self.play(*[
                sq.animate.set_fill(
                    interpolate_color(BLUE_E, YELLOW, float(np.clip(v, 0, 1))),
                    opacity=0.85)
                for sq, v in zip(squares, V.flatten())
            ], run_time=0.5)
        self.wait()

The Manim-Examples repository (scenes SquareToCircle, CreateGraph, displayEquations) provides all the templates you need: self.play, Transform, Write for LaTeX equations, and Jupyter rendering. The official ManimCE repository adds a full gallery (docs/source/examples.rst) and the example_scenes/ — Axes, ValueTracker and always_redraw are all you need to reproduce the bandit and the cliff on video.