2.The Mathematical Toolkit

2.1 Probability, quickly but honestly

Chapter 1 said the world "advances" after an action. Making that precise requires almost no machinery, but it does require the right machinery.

A probability space is a triple $(\Omega, \mathcal{F}, \mathbb{P})$: a set of outcomes $\Omega$, a collection $\mathcal{F}$ of events we can assign probabilities to, and a measure $\mathbb{P}$ assigning each event a number in $[0,1]$ with $\mathbb{P}(\Omega) = 1$. A random variable $X$ is a function from $\Omega$ to $\mathbb{R}$ — not a number, a function. When we write $X = 3$ we mean the event $\{\omega : X(\omega) = 3\}$.

This matters for us because Rusty's next position is exactly such a function: it depends on the wheel slip that happened to occur, which is the outcome $\omega$. Two identical commands from two identical positions produce two different results, and the difference is not error — it is the environment.

The expectation of $X$ is its probability-weighted average, $\mathbb{E}[X] = \sum_\omega \mathbb{P}(\omega) X(\omega)$ in the discrete case. Expectation is linear, which is the property we will lean on constantly:

$\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]$

— and note this holds whether or not $X$ and $Y$ are independent. A surprising amount of reinforcement learning is linearity of expectation applied patiently.

The single most useful fact about conditional expectation is that averaging it recovers the unconditional average.

Every Bellman equation in this book is the tower property applied to a return, conditioned on the first action. That is genuinely all it is. When Chapter 4 derives

$v_\pi(s) = \mathbb{E}_\pi\!\left[R_{t+1} + \gamma\, v_\pi(S_{t+1}) \,\middle|\, S_t = s\right],$

the derivation will consist of splitting the return into "first reward" plus "the rest", conditioning on where you land, and invoking Theorem 2.2.

2.2 Markov chains and the memory assumption

A sequence of random variables $S_0, S_1, S_2, \ldots$ has the Markov property if the future is conditionally independent of the past given the present:

$\mathbb{P}(S_{t+1} = s' \mid S_t, S_{t-1}, \ldots, S_0) = \mathbb{P}(S_{t+1} = s' \mid S_t).$

The state is then a sufficient statistic for prediction: knowing it, the history adds nothing.

2.3 Contraction mappings and the theorem behind everything

Here is the mathematical heart of the chapter — the result that will justify value iteration, Q-learning, and half of Part I.

Applying $T$ moves any two points strictly closer together. Intuitively, repeated application must crush everything toward a single point. The theorem says exactly that, and adds a computable error bound.

Three payoffs, all collected later: existence (an optimal value function exists), uniqueness (there is only one, so "the" optimal value function is well defined), and an algorithm with a stopping rule (iterate, and the bound tells you when to stop).

2.4 From continuous physics to discrete decisions

Robots obey differential equations. Reinforcement learning acts at discrete time steps. Something must bridge them, and the bridge is not free.

Meet Pendle, a torque-actuated pendulum, measured with $\theta = 0$ at the upright position:

$m \ell^2 \ddot\theta = m g \ell \sin\theta - b\,\dot\theta + \tau.$

Writing the state as $x = [\theta, \dot\theta]^\top$ turns this into a first-order system $\dot x = f(x, \tau)$. To simulate it we need to advance $x$ by a finite step $\Delta t$. The simplest choice is explicit Euler:

$x_{k+1} = x_k + \Delta t \cdot f(x_k, \tau_k),$

which is exact if $f$ is constant over the interval and wrong otherwise, with local error $O(\Delta t^2)$ and global error $O(\Delta t)$. Fourth-order Runge–Kutta samples the derivative four times per step:

$x_{k+1} = x_k + \frac{\Delta t}{6}\left(k_1 + 2k_2 + 2k_3 + k_4\right),$

with global error $O(\Delta t^4)$ — four extra derivative evaluations buying three extra orders of accuracy.

The difference is not academic. With $\tau = 0$ the true pendulum conserves total mechanical energy exactly. Explicit Euler does not merely approximate that conservation — it systematically violates it, injecting energy at every step until the pendulum spins up out of nothing.

use nalgebra::Vector2;
 
pub struct PendleParams {
    pub mass: f64,
    pub length: f64,
    pub gravity: f64,
    pub damping: f64,
}
 
/// ẋ = f(x, τ) for the torque-actuated pendulum, θ = 0 at upright.
pub fn dynamics(x: &Vector2<f64>, tau: f64, p: &PendleParams) -> Vector2<f64> {
    let (theta, omega) = (x[0], x[1]);
    let inertia = p.mass * p.length * p.length;
    let alpha = (p.mass * p.gravity * p.length * theta.sin()
                 - p.damping * omega
                 + tau) / inertia;
    Vector2::new(omega, alpha)
}
 
pub fn euler_step(x: &Vector2<f64>, tau: f64, dt: f64, p: &PendleParams) -> Vector2<f64> {
    x + dt * dynamics(x, tau, p)
}
 
pub fn rk4_step(x: &Vector2<f64>, tau: f64, dt: f64, p: &PendleParams) -> Vector2<f64> {
    let k1 = dynamics(x, tau, p);
    let k2 = dynamics(&(x + 0.5 * dt * k1), tau, p);
    let k3 = dynamics(&(x + 0.5 * dt * k2), tau, p);
    let k4 = dynamics(&(x + dt * k3), tau, p);
    x + (dt / 6.0) * (k1 + 2.0 * k2 + 2.0 * k3 + k4)
}

2.5 Learning from noisy samples: Robbins–Monro

Now the result that makes learning possible at all.

Suppose you want to find the root of a function $h(\theta) = 0$, but you can never evaluate $h$ — only a noisy sample $H(\theta) = h(\theta) + \text{noise}$. This is precisely our situation: we want the expected return, and we only ever observe one noisy trajectory at a time.

Robbins and Monro's answer, from 1951, is to take small steps in the direction each noisy sample suggests, with a step size that shrinks:

$\theta_{k+1} = \theta_k + \alpha_k\, H(\theta_k).$

The two conditions have clean interpretations, and it is worth being able to recite them:

• $\sum \alpha_k = \infty$ — the steps must be able to travel infinitely far. If they sum to something finite, the iterate can never reach a root that lies beyond that distance, no matter how many samples arrive.
• $\sum \alpha_k^2 < \infty$ — the steps must shrink fast enough to average out the noise. Otherwise the iterate rattles around the root forever without settling.

The canonical choice $\alpha_k = 1/k$ satisfies both: the harmonic series diverges, and the sum of $1/k^2$ converges to $\pi^2/6$. A constant $\alpha$ satisfies the first but not the second — which is why constant learning rates track a moving target instead of converging, exactly the trade you want when the environment is non-stationary.

2.6 Linear algebra and gradients, in the amount we need

Two more tools, stated without ceremony because they will be used constantly.

Matrices as operators. Given a policy on a finite state space, the transition probabilities form a matrix $P_\pi$, and expected rewards a vector $r_\pi$. Chapter 4 will show the value function satisfies $v_\pi = r_\pi + \gamma P_\pi v_\pi$, whose solution is

$v_\pi = (I - \gamma P_\pi)^{-1} r_\pi.$

The inverse exists because $\gamma P_\pi$ has spectral radius at most $\gamma < 1$, so the Neumann series $\sum_k (\gamma P_\pi)^k$ converges — the same geometric argument as the Banach bound, wearing matrix clothes.

Gradients. For $J : \mathbb{R}^n \to \mathbb{R}$, the gradient $\nabla J(\theta)$ points in the direction of steepest increase, and gradient ascent takes $\theta \leftarrow \theta + \alpha \nabla J(\theta)$. Chapter 10 spends its entire length computing one specific gradient — that of expected return with respect to policy parameters — which is hard precisely because the distribution you are averaging over depends on the parameters you are differentiating.

2.7 Chapter bridge

The debts of Chapter 1 are paid. "The world advances" is a conditional distribution. "Reward" is a random variable with an expectation. "Eventually finds the best policy" will be Banach's theorem applied to an operator we have not yet built.

Chapter 3 puts the toolkit to work on the smallest problem that still contains the essential difficulty: a single decision, repeated, with no state at all. Stripping away state exposes the exploration–exploitation dilemma in its pure form, and lets us derive real regret bounds with the concentration inequalities we now have the vocabulary for. Reacher joins the cast there, choosing among grasp primitives where every attempt costs hardware wear.

References