Reinforcement Learning — A Rigorous Treatment for Mathematicians

Chapter 0

Prologue, Notation & Mathematical Prerequisites

This course develops the theory of Reinforcement Learning (RL) with full mathematical rigour. We assume fluency in real analysis, measure-theoretic probability, functional analysis, and optimisation — the standard toolkit of a mathematics PhD. No prior exposure to RL or machine learning is required.

0.1 The RL Problem — Informal Overview

An agent interacts sequentially with an environment. At each discrete time $t \in \{0,1,2,\dots\}$, the agent observes a state $S_t$, selects an action $A_t$, receives a scalar reward $R_{t+1} \in \R$, and transitions to a new state $S_{t+1}$. The agent's objective is to choose actions so as to maximise the expected cumulative discounted reward $\E\!\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\right]$, where $\gamma \in [0,1)$ is the discount factor.

The central mathematical challenge: the agent does not know the transition dynamics or reward function of the environment — it must learn from sampled trajectories.

0.2 Notation

Notation Convention

Symbol	Meaning
$\S$	State space (finite or compact metric space)
$\A$	Action space (finite or compact)
$P(s'\|s,a)$	Transition kernel; when $\S$ is measurable: $P:\S \times \A \to \mathcal{P}(\S)$
$r(s,a)$ or $R(s,a,s')$	Reward function
$\gamma \in [0,1)$	Discount factor
$\pi(a\|s)$	Stochastic policy; $\pi: \S \to \mathcal{P}(\A)$
$V^\pi(s)$	State-value function under policy $\pi$
$Q^\pi(s,a)$	Action-value function under policy $\pi$
$V^(s), Q^(s,a)$	Optimal value functions
$\T^\pi, \T^*$	Bellman operators (policy-evaluation / optimality)
$d_\mu^\pi$	Discounted state-occupancy measure under $\pi$ starting from $\mu$

0.3 Measure-Theoretic Foundations

For general (continuous) state-action spaces, the trajectory $(S_0, A_0, R_1, S_1, A_1, \ldots)$ lives on the canonical probability space $(\Omega, \F, \P^\pi_\mu)$ where $\Omega = (\S \times \A \times \R)^{\mathbb{N}}$, the $\sigma$-algebra $\F$ is the product Borel $\sigma$-algebra, and $\P^\pi_\mu$ is the unique measure determined by the Ionescu-Tulcea extension theorem from the initial distribution $\mu$, the policy $\pi$, and the kernel $P$. In the finite case ($|\S|, |\A| < \infty$), everything collapses to ordinary probability mass functions and we work in $\R^{|\S|}$.

Remark

Throughout Chapters 1–5, we restrict to finite MDPs ($|\S|, |\A| < \infty$) for clarity. Chapter 6 handles the function-approximation setting where $\S$ may be uncountable.

Chapter 1

Markov Decision Processes — The Formal Framework

1.1 Definition and Structure

Definition 1.1 — Markov Decision Process

A (finite, discounted) Markov Decision Process is a tuple $\mathcal{M} = (\S, \A, P, r, \gamma)$ where:

$\S$ is a finite set of states with $|\S| = n$.
$\A$ is a finite set of actions with $|\A| = m$.
$P: \S \times \A \times \S \to [0,1]$ is the transition probability: $P(s'|s,a) = \P(S_{t+1}=s' \mid S_t=s, A_t=a)$.
$r: \S \times \A \to \R$ is the expected reward function: $r(s,a) = \E[R_{t+1} \mid S_t = s, A_t = a]$, assumed bounded.
$\gamma \in [0,1)$ is the discount factor.

The Markov property: $\P(S_{t+1} \in B \mid S_0, A_0, \ldots, S_t, A_t) = \P(S_{t+1} \in B \mid S_t, A_t)$ for all Borel $B \subseteq \S$.

1.2 Policies

Definition 1.2 — Policies

A Markov (stationary) policy is a mapping $\pi: \S \to \mathcal{P}(\A)$. A deterministic policy satisfies $\pi(\cdot|s) = \delta_{a}$ for some $a \in \A$.

More generally, a history-dependent randomised policy is a sequence $(\pi_t)_{t \geq 0}$ where $\pi_t: (\S \times \A)^t \times \S \to \mathcal{P}(\A)$. A foundational result (Theorem 1.5 below) shows that restricting to stationary deterministic policies is without loss of optimality for discounted infinite-horizon MDPs.

1.3 Value Functions

Definition 1.3 — State-Value and Action-Value

$$ V^\pi(s) \;=\; \E^\pi\!\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\Big|\; S_t = s\right] $$ $$ Q^\pi(s,a) \;=\; \E^\pi\!\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\Big|\; S_t = s,\; A_t = a\right] $$

Note $V^\pi(s) = \sum_{a} \pi(a|s)\, Q^\pi(s,a)$, and bounded rewards ($|r(s,a)| \leq R_{\max}$) ensure $|V^\pi(s)| \leq R_{\max}/(1-\gamma)$, so $V^\pi \in \R^{|\S|}$.

1.4 Bellman Equations

Theorem 1.4 — Bellman Expectation Equation

For any stationary policy $\pi$, $V^\pi$ is the unique solution in $\R^{|\S|}$ of:

$$ V^\pi(s) = \sum_{a \in \A} \pi(a|s) \left[ r(s,a) + \gamma \sum_{s' \in \S} P(s'|s,a)\, V^\pi(s') \right] $$

Equivalently, defining the Bellman operator $\T^\pi: \R^{|\S|} \to \R^{|\S|}$ by

$$ (\T^\pi V)(s) = \sum_a \pi(a|s)\Big[r(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V(s')\Big], $$

we have $V^\pi = \T^\pi V^\pi$ and $\T^\pi$ is a $\gamma$-contraction in the $\|\cdot\|_\infty$ norm.

Existence & Uniqueness via Banach Fixed-Point Theorem. For any $U, V \in \R^{|\S|}$:

$$ \|(\T^\pi U) - (\T^\pi V)\|_\infty = \gamma \max_s \Big|\sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[U(s') - V(s')]\Big| \leq \gamma \|U - V\|_\infty. $$

Since $\gamma < 1$, $\T^\pi$ is a strict contraction on the complete metric space $(\R^{|\S|}, \|\cdot\|_\infty)$. By the Banach fixed-point theorem, there exists a unique fixed point $V^\pi = \T^\pi V^\pi$. That $V^\pi$ equals the value function defined via the expectation follows by unrolling the recursion and using the dominated convergence theorem (the series converges geometrically). $\blacksquare$

1.5 Bellman Optimality & Existence of Optimal Policies

Definition — Optimal Value Functions

$$ V^*(s) = \sup_\pi V^\pi(s), \qquad Q^*(s,a) = \sup_\pi Q^\pi(s,a). $$

Theorem 1.5 — Bellman Optimality Equation

$V^*$ is the unique solution of:

$$ V^*(s) = \max_{a \in \A}\left[r(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s')\right] = (\T^* V^*)(s), $$

where $\T^*$ is the Bellman optimality operator, which is likewise a $\gamma$-contraction in $\|\cdot\|_\infty$. Moreover, the greedy policy

$$ \pi^*(s) \in \argmax_{a \in \A}\left[r(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s')\right] $$

is a (stationary, deterministic) optimal policy: $V^{\pi^*} = V^*$.

The key ingredient is that $\T^*$ is a $\gamma$-contraction:

$$ \|\T^* U - \T^* V\|_\infty \leq \gamma \|U - V\|_\infty $$

(use the fact that $|\max_a f(a) - \max_a g(a)| \leq \max_a |f(a) - g(a)|$). Banach gives unique fixed point $V^*$. That the greedy policy is optimal follows from $V^{\pi^*} = \T^{\pi^*} V^{\pi^*}$ and $\T^{\pi^*} V^* = \T^* V^* = V^*$ implying $V^{\pi^*} = V^*$ by uniqueness. $\blacksquare$

Remark — Partial Order on Policies

The set of stationary policies carries a partial order: $\pi \geq \pi'$ iff $V^\pi(s) \geq V^{\pi'}(s)\;\forall s$. The Bellman optimality theorem asserts the existence of a greatest element in this order. For infinite or continuous action spaces, one needs measurable selection theorems (e.g., Kuratowski–Ryll-Nardzewski).

1.6 Linear-Algebraic View

For a fixed policy $\pi$, define the $n \times n$ transition matrix $P_\pi$ with entries $(P_\pi)_{ss'} = \sum_a \pi(a|s) P(s'|s,a)$, and reward vector $r_\pi \in \R^n$ with $(r_\pi)_s = \sum_a \pi(a|s) r(s,a)$. The Bellman equation becomes:

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

The matrix $(I - \gamma P_\pi)$ is invertible since $\rho(\gamma P_\pi) \leq \gamma < 1$ (spectral radius of a sub-stochastic matrix). The inverse equals the Neumann series $\sum_{k=0}^\infty \gamma^k P_\pi^k$, which is the discounted state-occupancy operator.

Exercise 1.1

Let $\mathcal{M}$ be a finite MDP. Prove that for any two policies $\pi, \pi'$:

$$ \|V^\pi - V^{\pi'}\|_\infty \leq \frac{2 R_{\max}}{(1-\gamma)^2}\, \max_s \|\pi(\cdot|s) - \pi'(\cdot|s)\|_1. $$

Hint: Simulation lemma.

Chapter 2

Dynamic Programming

2.1 Policy Evaluation (Iterative)

Given a policy $\pi$, compute $V^\pi$ by iterating the Bellman operator: $V_{k+1} = \T^\pi V_k$, starting from arbitrary $V_0$. By the contraction property, $\|V_k - V^\pi\|_\infty \leq \gamma^k \|V_0 - V^\pi\|_\infty \to 0$ geometrically.

Algorithm 2.1 — Iterative Policy Evaluation

Input: MDP (S, A, P, r, γ), policy π, tolerance ε > 0
Initialize V(s) = 0 for all s ∈ S
Repeat:
    δ ← 0
    For each s ∈ S:
        v ← V(s)
        V(s) ← Σ_a π(a|s) [r(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]
        δ ← max(δ, |v − V(s)|)
Until δ < ε(1−γ)/(2γ)
Return V ≈ V^π

2.2 Policy Improvement

Theorem 2.1 — Policy Improvement Theorem

Let $\pi$ be a stationary policy. Define $\pi'$ greedily w.r.t. $Q^\pi$: $\pi'(s) = \argmax_a Q^\pi(s,a)$. Then $V^{\pi'}(s) \geq V^\pi(s)$ for all $s$, with equality iff $\pi$ is already optimal.

By construction, $\T^{\pi'} V^\pi \geq \T^\pi V^\pi = V^\pi$ componentwise. Define the sequence $U_0 = V^\pi$, $U_{k+1} = \T^{\pi'} U_k$. By monotonicity of $\T^{\pi'}$ (it preserves componentwise inequality since all coefficients are nonneg.), $U_1 \geq U_0$ implies $U_{k+1} \geq U_k$ by induction. Since $U_k \to V^{\pi'}$ (contraction), we get $V^{\pi'} \geq V^\pi$. $\blacksquare$

2.3 Policy Iteration

Algorithm 2.2 — Policy Iteration

Initialize π₀ arbitrarily (deterministic)
For k = 0, 1, 2, …:
    (Evaluation)    V^{πₖ} ← (I − γP_{πₖ})⁻¹ r_{πₖ}
    (Improvement)   πₖ₊₁(s) ← argmax_a [r(s,a) + γ Σ_{s'} P(s'|s,a) V^{πₖ}(s')]
    If πₖ₊₁ = πₖ: break
Return π* = πₖ

Proposition 2.2 — Finite Convergence

Policy iteration terminates in at most $|\A|^{|\S|}$ iterations (the number of deterministic policies). In practice, convergence is far faster — often in $O(|\S||\A|/(1-\gamma))$ value-improving steps. Each step requires $O(|\S|^3)$ for the matrix solve, giving a total of $O(|\S|^3 \cdot |\A|^{|\S|})$ in the worst case (though the Ye-Post simplex-policy-iteration result gives a strongly polynomial bound for fixed $|\A|$).

2.4 Value Iteration

Algorithm 2.3 — Value Iteration

Initialize V₀ arbitrarily
For k = 0, 1, 2, …:
    V_{k+1}(s) ← max_a [r(s,a) + γ Σ_{s'} P(s'|s,a) Vₖ(s')]    ∀s
    (i.e., V_{k+1} = T* Vₖ)
    If ‖V_{k+1} − Vₖ‖_∞ < ε(1−γ)/(2γ): break
Extract greedy policy: π(s) = argmax_a [r(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]

By the contraction property: $\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty$. To get an $\varepsilon$-optimal policy, we need $k = O\!\left(\frac{1}{1-\gamma} \log \frac{R_{\max}}{\varepsilon(1-\gamma)}\right)$.

⬡ Interactive: Value Iteration on a 4×4 Gridworld

Watch $\T^*$ converge. Blue = agent start, Green = goal (+1), Red = pit (−1), Grey = wall. Cell numbers show $V_k(s)$.

$\gamma$: 0.90 Iteration: 0

Exercise 2.1

Prove that value iteration and policy iteration produce the same sequence of value functions if policy iteration uses a single Bellman backup (instead of exact evaluation) at each step. This combined algorithm is called modified policy iteration. Under what conditions on the number of evaluation sweeps $m$ does it retain the contraction rate? (Show the rate is $\gamma^m$.)

Exercise 2.2

Let $\T^*$ be the Bellman optimality operator. Prove the monotonicity property: if $U \leq V$ componentwise, then $\T^* U \leq \T^* V$. Deduce that if $V \leq \T^* V$, then $V \leq V^*$.

Chapter 3

Monte Carlo Methods

3.1 From DP to Sample-Based Estimation

Dynamic programming requires full knowledge of $P$ and $r$. When the model is unknown, we estimate expectations from sample trajectories $\tau = (S_0, A_0, R_1, S_1, A_1, R_2, \ldots)$ generated by running policy $\pi$ in the environment.

Definition 3.1 — Return

The (discounted) return from time $t$ is:

$$ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}. $$

For episodic tasks (termination at step $T$), $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$.

By definition, $V^\pi(s) = \E^\pi[G_t \mid S_t = s]$. The Monte Carlo (MC) idea: estimate this expectation by the sample mean of observed returns.

3.2 First-Visit MC Policy Evaluation

Algorithm 3.1 — First-Visit MC

Initialize V(s), Returns(s) ← empty list, for all s
Repeat for many episodes:
    Generate episode: S₀, A₀, R₁, S₁, …, S_T
    G ← 0
    For t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        If S_t not in {S₀, …, S_{t−1}}:    # first visit
            Append G to Returns(S_t)
            V(S_t) ← mean(Returns(S_t))

Theorem 3.1 — Strong Consistency of MC Estimates

Under the first-visit MC method, $V(s) \xrightarrow{\text{a.s.}} V^\pi(s)$ as the number of episodes $\to \infty$, for each $s$ visited infinitely often.

The returns $G_t^{(1)}, G_t^{(2)}, \ldots$ from first visits to $s$ are i.i.d. with mean $V^\pi(s)$ and finite variance (bounded rewards). The strong law of large numbers gives a.s. convergence. $\blacksquare$

3.3 Monte Carlo Control & Exploring Starts

Combine MC evaluation with greedy improvement. The exploring starts assumption guarantees that every $(s,a)$ pair is a starting state infinitely often, ensuring convergence to $Q^*$. In practice, we relax this via $\varepsilon$-greedy policies.

3.4 Off-Policy MC via Importance Sampling

Definition 3.2 — Importance Sampling Ratio

Let $b$ be a behaviour policy and $\pi$ the target policy, with $b(a|s) > 0$ whenever $\pi(a|s) > 0$ (coverage). The importance-sampling ratio for a trajectory segment is:

$$ \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}. $$

Then $\E_b[\rho_{t:T-1} G_t | S_t = s] = V^\pi(s)$ (ordinary IS). The weighted IS estimator $\hat{V}(s) = \frac{\sum_{i} \rho^{(i)} G^{(i)}}{\sum_i \rho^{(i)}}$ has lower variance but is biased (consistent). This bias-variance tradeoff is a core theme in RL.

Exercise 3.1

Show that the variance of the ordinary IS estimator can be infinite even when $V^\pi(s)$ is bounded. Construct an explicit MDP example. Then prove that the weighted IS estimator always has finite variance when $|G_t|$ is bounded.

Chapter 4

Temporal-Difference Learning

4.1 The TD(0) Update

The key insight: bootstrap the value estimate using the current estimate $V(S_{t+1})$ instead of waiting for the full return $G_t$.

Definition 4.1 — TD Error

$$ \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t). $$

This is the sample analogue of the Bellman residual $(\T^\pi V)(S_t) - V(S_t)$.

Algorithm 4.1 — TD(0) (Tabular)

Initialize V(s) for all s, choose step size schedule {αₜ}
For each episode:
    Initialize S₀
    For t = 0, 1, 2, …:
        A_t ~ π(·|S_t)
        Observe R_{t+1}, S_{t+1}
        V(S_t) ← V(S_t) + α_t(S_t) · [R_{t+1} + γV(S_{t+1}) − V(S_t)]

Theorem 4.1 — Convergence of TD(0)

Under the Robbins-Monro conditions on step sizes — $\sum_t \alpha_t(s) = \infty$ and $\sum_t \alpha_t(s)^2 < \infty$ for each $s$ — and the assumption that every state is visited infinitely often, $V_t(s) \xrightarrow{\text{a.s.}} V^\pi(s)$ for all $s$.

This is an instance of the stochastic approximation theorem (Robbins-Monro / ODE method). The TD(0) update can be written as:

$$ V_{t+1}(s) = V_t(s) + \alpha_t(s) [(\T^\pi V_t)(s) - V_t(s) + w_t(s)] $$

where $w_t$ is a martingale difference noise with $\E[w_t | \F_t] = 0$. Since $\T^\pi$ is a contraction, the ODE $\dot{v} = \T^\pi v - v$ has the unique globally asymptotically stable equilibrium $V^\pi$. By the Borkar-Meyn theorem (or Jaakkola et al. '94), convergence follows. See Appendix B for the general framework. $\blacksquare$

4.2 TD vs MC: Bias-Variance Analysis

MC uses $G_t$ as the target — unbiased but high variance (sum of many random variables). TD(0) uses $R_{t+1} + \gamma V(S_{t+1})$ — biased (if $V \neq V^\pi$) but lower variance (only one step of randomness beyond the current estimate). Formally:

$$ \text{Var}(G_t) = \text{Var}\left(\sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}\right) = O\!\left(\frac{\sigma_R^2}{(1-\gamma)^2}\right), $$ $$ \text{Var}(R_{t+1} + \gamma V^\pi(S_{t+1})) = O(\sigma_R^2 + \gamma^2 \text{Var}_{s'}(V^\pi)). $$

4.3 SARSA and Q-Learning

Algorithm 4.2 — SARSA (On-Policy TD Control)

Initialize Q(s,a) for all (s,a)
For each episode:
    S ← initial state; A ~ ε-greedy(Q(S,·))
    For each step:
        Take action A, observe R, S'
        A' ~ ε-greedy(Q(S',·))
        Q(S,A) ← Q(S,A) + α[R + γQ(S',A') −  Q(S,A)]
        S ← S'; A ← A'
    Until S is terminal

Algorithm 4.3 — Q-Learning (Off-Policy TD Control)

Initialize Q(s,a) for all (s,a)
For each episode:
    S ← initial state
    For each step:
        A ~ ε-greedy(Q(S,·))    (behaviour policy)
        Take action A, observe R, S'
        Q(S,A) ← Q(S,A) + α[R + γ max_{a'} Q(S',a') − Q(S,A)]
        S ← S'
    Until S is terminal

Theorem 4.2 — Convergence of Q-Learning (Watkins & Dayan, 1992)

Under the Robbins-Monro step-size conditions and the assumption that every state-action pair is visited infinitely often, Q-learning converges a.s. to $Q^*$:

$$ Q_t(s,a) \xrightarrow{\text{a.s.}} Q^*(s,a) \quad \forall\, (s,a) \in \S \times \A. $$

The Q-learning update is a stochastic approximation to the Bellman optimality operator $\T^*$:

$$ Q_{t+1}(s,a) = Q_t(s,a) + \alpha_t(s,a)\big[(\T^* Q_t)(s,a) - Q_t(s,a) + w_t(s,a)\big] $$

where $w_t(s,a) = R_{t+1} + \gamma \max_{a'} Q_t(S_{t+1}, a') - (\T^* Q_t)(s,a)$ is a martingale difference noise. The operator $\T^*$ is a $\gamma$-contraction in $\|\cdot\|_\infty$. The convergence then follows from the general stochastic approximation result for contraction operators (Theorem B.2 in Appendix B), specifically the extension by Jaakkola, Jordan & Singh (1994) that handles the $\max$ nonlinearity. $\blacksquare$

⬡ Interactive: Q-Learning vs SARSA on Cliff-Walking

Classic cliff-walking gridworld (Sutton & Barto, Ex 6.6). Compare the on-policy (SARSA) safe path vs the off-policy (Q-Learning) optimal but risky path. Click Run to train both simultaneously.

Episodes: 500 $\varepsilon$: 0.10 $\alpha$: 0.50

4.4 Maximisation Bias & Double Q-Learning

Q-learning uses $\max_a Q(s',a)$ as an estimate of $\max_a \E[Q(s',a)]$. By Jensen's inequality applied to the convex $\max$ function:

$$ \E\!\left[\max_a Q(s',a)\right] \geq \max_a \E\!\left[Q(s',a)\right], $$

leading to maximisation bias. Double Q-learning (Hasselt, 2010) maintains two independent estimates $Q^A, Q^B$ and uses one to select the action and the other to evaluate it, eliminating the bias:

$$ Q^A(S,A) \leftarrow Q^A(S,A) + \alpha\!\left[R + \gamma\, Q^B\!\left(S',\, \argmax_a Q^A(S',a)\right) - Q^A(S,A)\right]. $$

Exercise 4.1

Construct an MDP with two states and $k$ actions where Q-learning's maximisation bias causes the initial policy to be suboptimal for $\Theta(\sqrt{k})$ episodes. Precisely, show that the expected overestimation is $\Theta(\sigma / \sqrt{k})$ where $\sigma^2$ is the variance of the reward noise.

Exercise 4.2

Prove that SARSA with $\varepsilon$-greedy exploration converges to $Q^{\pi_\varepsilon^*}$ (the optimal $\varepsilon$-greedy policy value), not to $Q^*$, even in the limit. What is the suboptimality gap $\|V^{\pi_\varepsilon^*} - V^*\|_\infty$ as a function of $\varepsilon$?

Chapter 5

N-Step Methods & Eligibility Traces

5.1 N-Step Returns

Definition 5.1 — N-Step Return

The $n$-step return from time $t$ is:

$$ G_t^{(n)} = \sum_{k=0}^{n-1} \gamma^k R_{t+k+1} + \gamma^n V(S_{t+n}). $$

Note: $n=1$ gives the TD(0) target; $n=\infty$ gives the MC return $G_t$. The $n$-step return interpolates between TD and MC.

5.2 The $\lambda$-Return and TD($\lambda$)

Definition 5.2 — $\lambda$-Return

The $\lambda$-return is the geometrically-weighted average of all $n$-step returns:

$$ G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1}\, G_t^{(n)}, \qquad \lambda \in [0,1]. $$

For $\lambda = 0$: $G_t^0 = G_t^{(1)}$ (TD(0)). For $\lambda = 1$: $G_t^1 = G_t$ (MC).

5.3 Eligibility Traces — The Backward View

Rather than computing the $\lambda$-return (which requires looking forward), the backward view maintains an eligibility trace vector $z_t \in \R^{|\S|}$ that records the recency and frequency of state visits:

$$ z_t(s) = \gamma \lambda\, z_{t-1}(s) + \mathbf{1}[S_t = s]. $$

Algorithm 5.1 — TD($\lambda$) with Eligibility Traces

Initialize V(s), z(s) = 0 for all s
For each episode:
    S ← initial state
    z ← 0 (reset traces)
    For each step:
        A ~ π(·|S), observe R, S'
        δ ← R + γV(S') − V(S)          # TD error
        z(S) ← z(S) + 1                 # accumulating trace
        For all s:
            V(s) ← V(s) + α · δ · z(s)
            z(s) ← γλ · z(s)
        S ← S'

Theorem 5.1 — Forward-Backward Equivalence

For the offline (batch) case: the sum of TD($\lambda$) backward-view updates over a complete episode produces the same total update to each $V(s)$ as the forward-view update using the $\lambda$-return $G_t^\lambda$:

$$ \sum_{t=0}^{T-1} \alpha\, \delta_t\, z_t(s) = \sum_{t: S_t = s} \alpha\left(G_t^\lambda - V(S_t)\right). $$

For a state $s$ visited at times $t_1 < t_2 < \cdots$, we compute the sum of eligibility-weighted TD errors. At time $t \geq t_i$ (and before the next visit $t_{i+1}$), the trace contribution from visit $t_i$ is $(\gamma\lambda)^{t - t_i}$. Therefore:

$$ \sum_{t=t_i}^{T-1} \delta_t (\gamma\lambda)^{t-t_i} = \sum_{t=t_i}^{T-1} \left[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\right] (\gamma\lambda)^{t-t_i}. $$

Expanding and telescoping, this equals $(1-\lambda)\sum_{n=1}^{T-t_i-1}\lambda^{n-1} G_{t_i}^{(n)} + \lambda^{T-t_i-1} G_{t_i}^{(T-t_i)} = G_{t_i}^\lambda - V(S_{t_i})$ (after careful algebra with the truncated geometric series). Summing over all visits $t_i$ gives the result. $\blacksquare$

5.4 The Operator-Theoretic View of TD($\lambda$)

Define the $\lambda$-operator:

$$ \T^\pi_\lambda = (1-\lambda) \sum_{n=0}^{\infty} \lambda^n (\T^\pi)^{n+1}. $$

This is a weighted average of iterated Bellman operators. One can show that $\T^\pi_\lambda$ is also a contraction with modulus $\frac{\gamma(1-\lambda)}{1-\gamma\lambda}$, which improves (decreases) as $\lambda \to 1$, at the cost of higher variance.

Exercise 5.1

Prove that $\T^\pi_\lambda$ is a $\frac{\gamma(1-\lambda)}{1-\gamma\lambda}$-contraction in $\|\cdot\|_\infty$. Show that its unique fixed point is $V^\pi$.

Chapter 6

Function Approximation

6.1 Motivation & the Curse of Dimensionality

When $|\S|$ is large or continuous (e.g., $\S \subseteq \R^d$), tabular methods are infeasible. We approximate $V^\pi$ or $Q^\pi$ using a parametric family $\{V_\theta : \theta \in \R^p\}$ where $p \ll |\S|$.

6.2 Linear Function Approximation

Definition 6.1 — Linear Value Function Approximation

Let $\phi: \S \to \R^p$ be a feature map. The linear approximation is:

$$ V_\theta(s) = \phi(s)^\top \theta = \sum_{i=1}^p \phi_i(s)\, \theta_i, \qquad \theta \in \R^p. $$

In matrix form, $V_\theta = \Phi \theta$ where $\Phi \in \R^{n \times p}$ is the feature matrix.

6.3 The Projection Framework

Let $d^\pi \in \mathcal{P}(\S)$ be the stationary distribution of the Markov chain under $\pi$ (or the discounted state distribution $d_\mu^\pi$). Define the weighted $L^2$ norm:

$$ \|V\|_{d^\pi}^2 = \sum_s d^\pi(s)\, V(s)^2 = V^\top D_\pi V, $$

where $D_\pi = \text{diag}(d^\pi)$. The projection operator onto the column space of $\Phi$ is:

$$ \Pi_\pi = \Phi (\Phi^\top D_\pi \Phi)^{-1} \Phi^\top D_\pi. $$

Theorem 6.1 — TD(0) with Linear FA Converges to the TD Fixed Point

Under linear FA, TD(0) converges to the unique $\theta^*$ satisfying:

$$ \Phi \theta^* = \Pi_\pi \T^\pi (\Phi \theta^*), $$

i.e., the fixed point of the projected Bellman operator $\Pi_\pi \T^\pi$.

The approximation error satisfies:

$$ \|V_{\theta^*} - V^\pi\|_{d^\pi} \leq \frac{1}{\sqrt{1-\gamma^2}}\, \min_\theta \|\Phi\theta - V^\pi\|_{d^\pi}. $$

$\Pi_\pi$ is a non-expansion in $\|\cdot\|_{d^\pi}$ and $\T^\pi$ is a $\gamma$-contraction in $\|\cdot\|_{d^\pi}$ (this uses the fact that $d^\pi$ is the stationary distribution). Their composition $\Pi_\pi \T^\pi$ is a $\gamma$-contraction, hence has a unique fixed point.

For the error bound: let $\bar{V} = \Pi_\pi V^\pi$ be the best approximation. Then $\|V_{\theta^*} - V^\pi\|^2 = \|V_{\theta^*} - \bar{V}\|^2 + \|\bar{V} - V^\pi\|^2$ (Pythagorean, since $\Pi$ is an orthogonal projection). Bounding the first term using the contraction gives the $1/\sqrt{1-\gamma^2}$ amplification factor. $\blacksquare$

6.4 Semi-Gradient Methods

The TD(0) update with FA is a semi-gradient method — it takes the gradient only through the predicted value, not through the bootstrap target:

$$ \theta_{t+1} = \theta_t + \alpha_t \underbrace{\left[R_{t+1} + \gamma V_{\theta_t}(S_{t+1}) - V_{\theta_t}(S_t)\right]}_{\delta_t}\, \nabla_\theta V_{\theta_t}(S_t). $$

For linear FA: $\nabla_\theta V_\theta(s) = \phi(s)$, so the update is linear in $\theta$.

6.5 The Deadly Triad & Divergence

Warning — The Deadly Triad

The combination of (1) function approximation, (2) bootstrapping, and (3) off-policy learning can cause divergence. The projected Bellman operator $\Pi_\mu \T^\pi$ may not be a contraction when $\mu \neq d^\pi$.

Famous counterexample: Baird's counterexample — TD(0) with linear FA diverges even with a simple 7-state MDP and on-policy-like features, due to distribution mismatch.

6.6 Gradient-TD Methods

To achieve true (full) gradient descent, we minimise the Mean Squared Projected Bellman Error (MSPBE):

$$ \text{MSPBE}(\theta) = \|\Phi\theta - \Pi_\mu \T^\pi (\Phi\theta)\|_\mu^2 = \delta_\theta^\top D_\mu \Phi (\Phi^\top D_\mu \Phi)^{-1} \Phi^\top D_\mu \delta_\theta, $$

where $\delta_\theta = \T^\pi(\Phi\theta) - \Phi\theta$. The gradient of MSPBE involves a product of three expectations, leading to the GTD2 and TDC algorithms (Sutton, Maei, et al., 2009) that use a secondary weight vector $w$ to track the product.

Exercise 6.1

Derive the MSPBE gradient explicitly. Show that naively sampling the gradient gives a biased estimate (double-sampling problem). Then show how introducing the auxiliary variable $w$ that tracks $(\Phi^\top D_\mu \Phi)^{-1} \Phi^\top D_\mu \delta_\theta$ resolves this via a two-timescale stochastic approximation scheme.

Exercise 6.2

Prove that for nonlinear FA (e.g., neural networks), the projected Bellman operator may have no fixed point. Construct a counterexample with $\S = \{s_1, s_2\}$ and a one-parameter nonlinear approximation $V_\theta(s) = \theta^2 \cdot \phi(s)$.

Chapter 7

Policy Gradient Theory

7.1 Motivation: Direct Policy Optimisation

Instead of learning $Q^*$ and extracting a policy, parameterise the policy directly: $\pi_\theta(a|s)$, $\theta \in \R^p$. Define the objective:

$$ J(\theta) = V^{\pi_\theta}(s_0) = \E_{\pi_\theta}\!\left[\sum_{k=0}^\infty \gamma^k R_{k+1}\right] $$

(or $J(\theta) = \sum_s d_0(s) V^{\pi_\theta}(s)$ for a distribution $d_0$ over starts). We seek $\theta^* = \argmax_\theta J(\theta)$ via gradient ascent.

7.2 The Policy Gradient Theorem

Theorem 7.1 — Policy Gradient Theorem (Sutton et al., 1999)

For the discounted objective with start-state distribution $d_0$:

$$ \nabla_\theta J(\theta) = \frac{1}{1-\gamma}\sum_{s} d^{\pi_\theta}(s) \sum_{a} Q^{\pi_\theta}(s,a)\, \nabla_\theta \pi_\theta(a|s), $$

where $d^{\pi_\theta}(s) = (1-\gamma) \sum_{t=0}^\infty \gamma^t \P(S_t = s \mid d_0, \pi_\theta)$ is the discounted state visitation distribution.

Equivalently, using the score function $\nabla_\theta \log \pi_\theta(a|s)$:

$$ \nabla_\theta J(\theta) = \E_{s \sim d^{\pi_\theta},\, a \sim \pi_\theta}\!\left[Q^{\pi_\theta}(s,a)\, \nabla_\theta \log \pi_\theta(a|s)\right]. $$

We compute $\nabla_\theta V^{\pi_\theta}(s)$ recursively:

$$ \nabla_\theta V^{\pi_\theta}(s) = \sum_a \Big[\nabla_\theta \pi_\theta(a|s)\, Q^{\pi_\theta}(s,a) + \pi_\theta(a|s)\, \nabla_\theta Q^{\pi_\theta}(s,a)\Big]. $$

Now expand $Q^{\pi_\theta}(s,a) = r(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{\pi_\theta}(s')$, so:

$$ \nabla_\theta Q^{\pi_\theta}(s,a) = \gamma \sum_{s'} P(s'|s,a) \nabla_\theta V^{\pi_\theta}(s'). $$

Substituting back:

$$ \nabla_\theta V^{\pi_\theta}(s) = \sum_a \nabla_\theta \pi_\theta(a|s)\, Q^{\pi_\theta}(s,a) + \gamma \sum_{s'} P_{\pi_\theta}(s'|s)\, \nabla_\theta V^{\pi_\theta}(s'). $$

Unrolling the recursion $k$ times and taking $k \to \infty$:

$$ \nabla_\theta V^{\pi_\theta}(s) = \sum_{t=0}^\infty \gamma^t \sum_{s'} \P^{\pi_\theta}(S_t = s'|S_0 = s) \sum_a \nabla_\theta \pi_\theta(a|s')\, Q^{\pi_\theta}(s',a). $$

Averaging over $s \sim d_0$:

$$ \nabla_\theta J(\theta) = \sum_{s} d_0(s) \nabla_\theta V^{\pi_\theta}(s) = \sum_{s'} \left[\sum_{t=0}^\infty \gamma^t \sum_s d_0(s) P^t_{\pi_\theta}(s'|s)\right] \sum_a \nabla_\theta \pi_\theta(a|s') Q^{\pi_\theta}(s',a). $$

The bracketed term is $\frac{1}{1-\gamma} d^{\pi_\theta}(s')$, completing the proof. $\blacksquare$

7.3 REINFORCE Algorithm

Algorithm 7.1 — REINFORCE (Williams, 1992)

Initialize θ
For each episode:
    Generate trajectory τ = (S₀, A₀, R₁, …, S_T) ~ π_θ
    For t = 0, …, T−1:
        G_t ← Σ_{k=0}^{T−t−1} γ^k R_{t+k+1}
        θ ← θ + α γ^t (G_t − b(S_t)) ∇_θ log π_θ(A_t|S_t)
    # b(S_t) is a baseline (e.g., V̂(S_t)) — reduces variance without bias

Proposition 7.2 — Baseline Does Not Introduce Bias

For any function $b: \S \to \R$:

$$ \E_{a \sim \pi_\theta(\cdot|s)}\!\left[b(s)\, \nabla_\theta \log \pi_\theta(a|s)\right] = b(s) \sum_a \nabla_\theta \pi_\theta(a|s) = b(s) \nabla_\theta 1 = 0. $$

$\sum_a \pi_\theta(a|s) \nabla_\theta \log \pi_\theta(a|s) = \sum_a \nabla_\theta \pi_\theta(a|s) = \nabla_\theta \sum_a \pi_\theta(a|s) = \nabla_\theta 1 = 0.$ $\blacksquare$

7.4 Natural Policy Gradient

Standard gradient ascent $\theta \leftarrow \theta + \alpha \nabla_\theta J$ depends on the parameterisation. The natural gradient (Kakade, 2001; Amari, 1998) uses the Fisher information metric on policy space:

$$ \tilde{\nabla}_\theta J(\theta) = F(\theta)^{-1} \nabla_\theta J(\theta), $$

where the Fisher information matrix is:

$$ F(\theta) = \E_{s \sim d^{\pi_\theta},\, a \sim \pi_\theta}\!\left[\nabla_\theta \log \pi_\theta(a|s)\, \nabla_\theta \log \pi_\theta(a|s)^\top\right]. $$

Theorem 7.3 — Compatible Function Approximation

If the critic uses a compatible approximation $A_w(s,a) = w^\top \nabla_\theta \log \pi_\theta(a|s)$ and minimises the squared error against $A^{\pi_\theta}(s,a)$, then:

$$ F(\theta)^{-1} \nabla_\theta J(\theta) = w^*, $$

i.e., the natural gradient equals the compatible critic parameters.

7.5 Variance Reduction: GAE (Generalised Advantage Estimation)

Definition 7.1 — GAE($\lambda$) (Schulman et al., 2016)

The Generalised Advantage Estimator is:

$$ \hat{A}_t^{\text{GAE}(\lambda)} = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}, $$

where $\delta_t = R_{t+1} + \gamma V_\phi(S_{t+1}) - V_\phi(S_t)$ is the TD error with critic $V_\phi$.

This is an exponentially-weighted average of $n$-step advantage estimates. The parameter $\lambda \in [0,1]$ controls the bias-variance trade-off: $\lambda = 0$ gives the one-step TD advantage (low variance, some bias); $\lambda = 1$ gives the MC advantage (no bias, high variance).

⬡ Interactive: REINFORCE on a Bandit Problem

Softmax policy over $k$ arms. Watch $\pi_\theta$ converge to the optimal arm. The chart shows the probability assigned to each arm over training iterations.

Arms (k): $\alpha$: 0.10 Steps: 1000

Exercise 7.1

Prove the policy gradient theorem for the average-reward setting: $J(\theta) = \lim_{T \to \infty} \frac{1}{T} \E\!\left[\sum_{t=0}^{T-1} R_{t+1}\right]$. Show that $\nabla_\theta J(\theta) = \sum_s d^{\pi_\theta}(s) \sum_a Q^{\pi_\theta}_{\text{diff}}(s,a) \nabla_\theta \pi_\theta(a|s)$ where $Q_{\text{diff}}$ is the differential action-value function.

Chapter 8

Deep Q-Networks & Extensions

8.1 DQN (Mnih et al., 2015)

Approximate $Q^*$ with a deep neural network $Q_\theta(s,a)$. Two key innovations stabilise training:

Experience Replay: store transitions $(s,a,r,s')$ in a buffer $\mathcal{D}$; sample mini-batches i.i.d. to break temporal correlation.
Target Network: maintain a slowly-updated copy $\theta^-$ and use $y = r + \gamma \max_{a'} Q_{\theta^-}(s', a')$ as the regression target.

Algorithm 8.1 — DQN

Initialize Q_θ, target Q_{θ⁻} with θ⁻ = θ, replay buffer D
For each step:
    With prob ε: A ← random; else: A ← argmax_a Q_θ(S, a)
    Execute A, observe R, S'. Store (S, A, R, S') in D.
    Sample mini-batch {(sⱼ, aⱼ, rⱼ, s'ⱼ)} ~ D
    Compute targets: yⱼ = rⱼ + γ max_{a'} Q_{θ⁻}(s'ⱼ, a')
    Update θ by SGD on L = (1/B) Σⱼ (Q_θ(sⱼ,aⱼ) − yⱼ)²
    Every C steps: θ⁻ ← θ

8.2 Theoretical Analysis

Remark — DQN is Not Gradient Descent

DQN does not minimise any fixed loss function, because the target $y_j$ depends on $\theta^-$ which tracks $\theta$. It is better understood as a fitted Q-iteration (a sequence of supervised-learning problems). Convergence guarantees for neural fitted Q-iteration remain an active research area. The target network can be seen as an implicit regularisation that makes the operator approximately contractive on a slow timescale.

8.3 Double DQN

To address the maximisation bias (§4.4), Double DQN (van Hasselt et al., 2016) uses:

$$ y = r + \gamma\, Q_{\theta^-}\!\left(s',\, \argmax_{a'} Q_\theta(s', a')\right). $$

8.4 Dueling DQN

Decompose the network into value and advantage streams:

$$ Q_\theta(s,a) = V_\xi(s) + \left(A_\psi(s,a) - \frac{1}{|\A|}\sum_{a'} A_\psi(s,a')\right), $$

where $\theta = (\xi, \psi)$. This architecture learns the state value $V$ and the relative advantage $A$ separately, which is beneficial when many actions have similar values.

8.5 Prioritised Experience Replay

Sample transitions with probability proportional to their TD error magnitude: $p_i \propto |\delta_i|^\alpha$. This non-uniform sampling introduces bias, corrected by importance-sampling weights $w_i = (N \cdot p_i)^{-\beta}$ with $\beta \to 1$ annealed during training.

8.6 Distributional RL (C51, QR-DQN)

Instead of learning $\E[G_t | s, a]$, learn the full return distribution $Z(s,a)$ where $Q(s,a) = \E[Z(s,a)]$. The distributional Bellman operator:

$$ Z(s,a) \stackrel{D}{=} R(s,a) + \gamma Z(S', A^*), $$

where $A^* = \argmax_{a'} \E[Z(S', a')]$. The C51 algorithm represents $Z$ as a categorical distribution over 51 atoms and minimises the KL divergence after the distributional Bellman projection.

Theorem 8.1 — Distributional Bellman Operator is a Contraction

The distributional Bellman operator $\mathcal{T}^\pi$ mapping return distributions to return distributions is a $\gamma$-contraction in the $p$-Wasserstein metric $\bar{d}_p$ for $p \geq 1$:

$$ \bar{d}_p(\mathcal{T}^\pi Z_1, \mathcal{T}^\pi Z_2) \leq \gamma\, \bar{d}_p(Z_1, Z_2), $$

where $\bar{d}_p(Z_1, Z_2) = \sup_{s,a} d_p(Z_1(s,a), Z_2(s,a))$ and $d_p$ is the $p$-Wasserstein distance on $\mathcal{P}(\R)$.

Exercise 8.1

Prove Theorem 8.1 using the coupling characterisation of Wasserstein distance. Show that the result fails for KL divergence and total variation, making the choice of metric crucial.

Chapter 9

Actor-Critic Methods, A3C, and PPO

9.1 Actor-Critic Framework

Combine a policy (actor) $\pi_\theta$ and a value function (critic) $V_\phi$ (or $Q_\phi$). The actor is updated via the policy gradient, using the critic to estimate the advantage $A^{\pi_\theta}(s,a) = Q^{\pi_\theta}(s,a) - V^{\pi_\theta}(s)$.

Algorithm 9.1 — Advantage Actor-Critic (A2C)

Initialize actor θ, critic φ
For each batch of trajectories:
    Collect {(s_t, a_t, r_{t+1}, s_{t+1})} using π_θ
    Compute advantages: Â_t = GAE(λ) using V_φ
    Compute returns: R̂_t = Â_t + V_φ(s_t)

    # Critic update (regression)
    φ ← φ − α_c ∇_φ (1/B) Σ_t (V_φ(s_t) − R̂_t)²

    # Actor update (policy gradient)
    θ ← θ + α_a (1/B) Σ_t Â_t ∇_θ log π_θ(a_t|s_t)

9.2 Asynchronous Advantage Actor-Critic (A3C)

Run multiple parallel actors in separate copies of the environment, each computing gradients and asynchronously updating shared parameters. This replaces the replay buffer of DQN with parallelism-induced decorrelation.

9.3 Trust Region Policy Optimisation (TRPO)

The policy improvement theorem guarantees improvement, but large steps can be catastrophic. TRPO (Schulman et al., 2015) solves a constrained optimisation:

$$ \max_\theta \;\; \hat{\E}_t\!\left[\frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)} \hat{A}_t\right] \quad \text{s.t.} \quad \hat{\E}_t\!\left[\KL\!\left(\pi_{\theta_\text{old}}(\cdot|s_t) \,\|\, \pi_\theta(\cdot|s_t)\right)\right] \leq \delta. $$

Theorem 9.1 — Monotonic Improvement Guarantee (Kakade & Langford, 2002; Schulman, 2015)

Let $\pi_\text{old}$ and $\pi_\text{new}$ be two policies. Define the surrogate advantage:

$$ L_{\pi_\text{old}}(\pi_\text{new}) = J(\pi_\text{old}) + \frac{1}{1-\gamma}\E_{s \sim d^{\pi_\text{old}},\, a \sim \pi_\text{new}}\!\left[A^{\pi_\text{old}}(s,a)\right]. $$

Then:

$$ J(\pi_\text{new}) \geq L_{\pi_\text{old}}(\pi_\text{new}) - \frac{2\gamma \epsilon}{(1-\gamma)^2} \cdot \max_s \KL\!\left(\pi_\text{old}(\cdot|s) \,\|\, \pi_\text{new}(\cdot|s)\right), $$

where $\epsilon = \max_{s,a} |A^{\pi_\text{old}}(s,a)|$.

Start from the performance difference lemma: $J(\pi') - J(\pi) = \frac{1}{1-\gamma} \E_{s \sim d^{\pi'}, a \sim \pi'}\!\left[A^\pi(s,a)\right]$. Replace $d^{\pi'}$ with $d^\pi$ (the surrogate) and bound the error using the TV distance between $d^{\pi'}$ and $d^\pi$, which is controlled by $\KL(\pi \| \pi')$ via Pinsker's inequality and a telescoping argument over the trajectory. $\blacksquare$

9.4 Proximal Policy Optimisation (PPO)

PPO (Schulman et al., 2017) replaces the hard KL constraint of TRPO with a clipped surrogate:

$$ L^{\text{CLIP}}(\theta) = \hat{\E}_t\!\left[\min\!\left(r_t(\theta) \hat{A}_t,\;\; \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t\right)\right], $$

where $r_t(\theta) = \pi_\theta(a_t|s_t) / \pi_{\theta_\text{old}}(a_t|s_t)$.

The clipping prevents the ratio $r_t(\theta)$ from moving too far from 1, providing a pessimistic lower bound on the unclipped objective. When $\hat{A}_t > 0$, the objective is $\min(r_t \hat{A}_t, (1+\epsilon)\hat{A}_t)$ — capping the benefit of increasing $r_t$. When $\hat{A}_t < 0$, it caps the benefit of decreasing $r_t$.

Algorithm 9.2 — PPO (Clip Version)

Initialize actor θ, critic φ
For iteration = 1, 2, …:
    Collect T timesteps using π_{θ_old}
    Compute GAE advantages Â_t and returns R̂_t
    For epoch = 1, …, K:
        For each mini-batch:
            r_t(θ) = π_θ(a_t|s_t) / π_{θ_old}(a_t|s_t)
            L_actor = −mean[ min(r_t Â_t, clip(r_t, 1−ε, 1+ε) Â_t) ]
            L_critic = mean[ (V_φ(s_t) − R̂_t)² ]
            L = L_actor + c₁ L_critic − c₂ H(π_θ)    # entropy bonus
            Update θ, φ by gradient descent on L
    θ_old ← θ

⬡ Interactive: PPO Clipping Objective

Visualise $L^{\text{CLIP}}$ as a function of the ratio $r = \pi_\theta / \pi_{\theta_\text{old}}$ for different advantage signs. Adjust $\varepsilon$ and $\hat{A}$.

$\varepsilon$: 0.20 $\hat{A}$: 1.00

Exercise 9.1

Prove the performance difference lemma directly: $J(\pi') - J(\pi) = \frac{1}{1-\gamma} \sum_s d^{\pi'}(s) \sum_a \pi'(a|s) A^\pi(s,a)$.

Hint: Start from the Bellman equation for $V^\pi$ and use the identity $\sum_a \pi'(a|s) A^\pi(s,a) = \sum_a \pi'(a|s) Q^\pi(s,a) - V^\pi(s)$.

Chapter 10

Advanced Topics

10.1 Model-Based RL

Learn a model $\hat{P}, \hat{r}$ of the environment and plan using it. The Dyna architecture (Sutton, 1991) interleaves real experience with simulated experience from the learned model. Modern approaches (MuZero, Dreamer) learn latent-space dynamics models.

Definition 10.1 — Simulation Lemma (Model Error Bound)

If $\hat{P}$ and $P$ satisfy $\max_{s,a} \|P(\cdot|s,a) - \hat{P}(\cdot|s,a)\|_1 \leq \epsilon_P$ and $\max_{s,a} |r(s,a) - \hat{r}(s,a)| \leq \epsilon_r$, then for any policy $\pi$:

$$ \|V^\pi_{\text{true}} - V^\pi_{\text{model}}\|_\infty \leq \frac{\epsilon_r + \gamma \epsilon_P R_{\max} / (1-\gamma)}{1-\gamma}. $$

10.2 Exploration: Theory & Algorithms

10.2.1 Regret Bounds and PAC-MDP

The regret of an algorithm after $T$ steps: $\text{Regret}(T) = \sum_{t=1}^T \left[V^*(S_t) - V^{\pi_t}(S_t)\right]$. Information-theoretic lower bound: $\Omega(\sqrt{|\S||\A|T})$ for episodic MDPs.

10.2.2 UCB for RL (UCRL2)

Construct confidence sets for the transition kernel and reward, then solve the optimistic MDP (extended value iteration). Achieves $\tilde{O}(|\S|\sqrt{|\A|T})$ regret.

10.2.3 Count-Based Exploration & Intrinsic Motivation

In large/continuous state spaces, maintain pseudo-counts via density models. Add exploration bonus $r^+ = \beta / \sqrt{N(s,a)}$ (or $\beta / \sqrt{\hat{n}(s)}$ for pseudo-counts). Related: Random Network Distillation (RND) — the prediction error of a random target network serves as a novelty signal.

10.3 Multi-Agent RL (MARL)

Extend MDPs to stochastic games / Markov games: $(\S, \{\A_i\}_{i=1}^N, P, \{r_i\}_{i=1}^N, \gamma)$. Key solution concepts: Nash equilibrium, correlated equilibrium. Algorithms: independent learners, centralised training with decentralised execution (CTDE), MAPPO, QMIX.

10.4 Inverse RL & Reward Learning

Given expert demonstrations $\mathcal{D} = \{(s_t, a_t)\}$, recover a reward function $r$ such that the expert's policy is optimal. The LP formulation (Ng & Russell, 2000): the feasible set of reward functions consistent with optimality is characterised by $(I - \gamma P_{\pi^*})^{-1}(r_{\pi^*} - r_\pi) \geq 0$ for all policies $\pi$. Maximum-entropy IRL (Ziebart et al., 2008) regularises with causal entropy.

10.5 Offline / Batch RL

Learn a policy from a fixed dataset $\mathcal{D}$ without further environment interaction. Key challenge: distributional shift — the learned policy may visit states not covered by $\mathcal{D}$, causing catastrophic extrapolation errors. Algorithms: Conservative Q-Learning (CQL), which adds a penalty $\alpha \cdot \E_{s \sim \mathcal{D}}\!\left[\log \sum_a \exp Q_\theta(s,a) - \E_{a \sim \hat{\pi}_\beta}[Q_\theta(s,a)]\right]$ to push down Q-values of out-of-distribution actions.

10.6 RL as Probabilistic Inference (Control as Inference)

Introduce binary "optimality" variables $\mathcal{O}_t$ with $p(\mathcal{O}_t = 1 | s_t, a_t) \propto \exp(r(s_t, a_t))$. The optimal policy is the posterior $p(a_t | s_t, \mathcal{O}_{t:T} = 1)$. This framework unifies maximum-entropy RL (Soft Actor-Critic), expectation-maximisation approaches, and variational inference perspectives on RL. The soft Bellman equation:

$$ V^*_{\text{soft}}(s) = \log \sum_a \exp\!\left(Q^*_{\text{soft}}(s,a)\right) = \text{soft}\max_a Q^*_{\text{soft}}(s,a). $$

10.7 Soft Actor-Critic (SAC)

Algorithm 10.1 — SAC (Haarnoja et al., 2018)

Initialize: Q_{θ₁}, Q_{θ₂} (twin critics), policy π_φ, target Q_{θ̄₁}, Q_{θ̄₂}
Temperature α (or auto-tuned)
For each step:
    a ~ π_φ(·|s), observe r, s'
    Store (s, a, r, s') in replay buffer D
    # Sample mini-batch from D
    ã' ~ π_φ(·|s')
    y = r + γ [min(Q_{θ̄₁}(s', ã'), Q_{θ̄₂}(s', ã')) − α log π_φ(ã'|s')]
    Update θ₁, θ₂ by minimizing (Q_{θᵢ}(s,a) − y)²
    Update φ by minimizing:
        E_{ã~π_φ(·|s)}[α log π_φ(ã|s) − min(Q_{θ₁}(s,ã), Q_{θ₂}(s,ã))]
    (Optional) Update α to target entropy: α ← α − β ∇_α E[−log π_φ − H̄]
    Soft-update targets: θ̄ᵢ ← τθᵢ + (1−τ)θ̄ᵢ

Exercise 10.1

Derive the soft policy iteration convergence proof. Specifically, show that the soft Bellman operator $\T^*_{\text{soft}}$ with $(\T^*_{\text{soft}} Q)(s,a) = r(s,a) + \gamma \E_{s'}[V_{\text{soft}}(s')]$ where $V_{\text{soft}}(s) = \alpha \log \sum_{a'} \exp(Q(s,a')/\alpha)$ is a $\gamma$-contraction in $\|\cdot\|_\infty$, and that soft policy improvement holds: $Q^{\pi_\text{new}}_{\text{soft}} \geq Q^{\pi_\text{old}}_{\text{soft}}$.

Exercise 10.2 (Research-Level)

In the offline RL setting, consider the CQL objective with Lagrange multiplier $\alpha$:

$$ \min_Q \; \alpha \left(\E_{s \sim \mathcal{D}}\!\left[\log \sum_a e^{Q(s,a)}\right] - \E_{s,a \sim \mathcal{D}}[Q(s,a)]\right) + \frac{1}{2}\E_{(s,a,r,s') \sim \mathcal{D}}\!\left[\left(Q(s,a) - \hat{\T}^\pi Q(s,a)\right)^2\right]. $$

Show that in the tabular case with infinite data, the minimiser $\hat{Q}^{\text{CQL}}$ satisfies $\hat{Q}^{\text{CQL}} \leq Q^\pi$ pointwise (a pessimistic estimate). Quantify the gap as a function of $\alpha$ and the data distribution mismatch.

Appendix A

Contraction Mappings & Fixed-Point Theory

Theorem A.1 — Banach Fixed-Point Theorem

Let $(X, d)$ be a complete metric space and $T: X \to X$ a contraction with modulus $\gamma < 1$ (i.e., $d(Tx, Ty) \leq \gamma\, d(x,y)$ for all $x,y$). Then:

$T$ has a unique fixed point $x^*$.
For any $x_0 \in X$, $d(T^n x_0, x^*) \leq \frac{\gamma^n}{1-\gamma}\, d(x_0, Tx_0)$.

Proposition A.2 — Monotone Contractions on $\R^n$

If $T: \R^n \to \R^n$ is a $\gamma$-contraction in $\|\cdot\|_\infty$ and is monotone ($x \leq y \implies Tx \leq Ty$ componentwise), then $T^n x \to x^*$ monotonically from any initial $x$ satisfying $x \leq Tx$ (or $x \geq Tx$).

Both Bellman operators $\T^\pi$ and $\T^*$ satisfy these conditions.

Appendix B

Stochastic Approximation Theory

Theorem B.1 — Robbins-Monro Theorem (Classical)

Consider the iteration $\theta_{t+1} = \theta_t + \alpha_t [h(\theta_t) + w_{t+1}]$ where:

$h: \R^p \to \R^p$ is continuous with a unique zero $\theta^*$: $h(\theta^*) = 0$.
$h$ is a stable vector field: $\langle \theta - \theta^*, h(\theta) \rangle < 0$ for $\theta \neq \theta^*$ (pointing inward).
Step sizes satisfy the Robbins-Monro conditions: $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$.
$\{w_{t+1}\}$ is a martingale difference sequence adapted to $\{\F_t\}$ with $\E[\|w_{t+1}\|^2 | \F_t] \leq C(1 + \|\theta_t\|^2)$.

Then $\theta_t \xrightarrow{\text{a.s.}} \theta^*$.

Theorem B.2 — Stochastic Approximation for Contraction Operators

(Jaakkola, Jordan & Singh, 1994; Borkar & Meyn, 2000). Consider the asynchronous iteration:

$$ Q_{t+1}(x) = (1 - \alpha_t(x))\, Q_t(x) + \alpha_t(x)\left[(\T Q_t)(x) + w_t(x)\right], $$

where $\T: \R^d \to \R^d$ is a $\gamma$-contraction in $\|\cdot\|_\infty$. Under:

$\sum_t \alpha_t(x) = \infty$, $\sum_t \alpha_t(x)^2 < \infty$ for all $x$.
$\E[w_t(x) | \F_t] = 0$, $\E[w_t(x)^2 | \F_t] \leq C(1 + \|Q_t\|_\infty^2)$.

Then $Q_t \xrightarrow{\text{a.s.}} Q^*$, the unique fixed point of $\T$.

The ODE method (Borkar & Meyn, 2000) relates the stochastic recursion to the ordinary differential equation:

$$ \dot{\theta}(t) = h(\theta(t)) = \T\theta(t) - \theta(t). $$

Since $\T$ is a $\gamma$-contraction, consider the Lyapunov function $L(\theta) = \|\theta - \theta^*\|_\infty$. Along trajectories of the ODE:

$$ \frac{d}{dt} L(\theta(t)) \leq \|\T\theta - \theta^*\|_\infty - \|\theta - \theta^*\|_\infty \leq (\gamma - 1)\|\theta - \theta^*\|_\infty = -(1-\gamma) L(\theta(t)). $$

So $L(\theta(t)) \leq e^{-(1-\gamma)t} L(\theta(0)) \to 0$, i.e., $\theta^*$ is globally asymptotically stable. The general theory of stochastic approximation (Kushner-Clark, Borkar) then shows that the interpolated process $\bar{\theta}(t)$ constructed from $\{\theta_n\}$ tracks this ODE asymptotically, implying $\theta_n \to \theta^*$ a.s.

The key technical conditions are: (a) the step-size conditions ensure the noise is averaged out, (b) the martingale difference condition ensures the noise does not systematically push the iterates away, (c) a stability/tightness argument (often the hardest part) ensures the iterates remain bounded. For contractions, boundedness follows from the Lyapunov argument. $\blacksquare$

B.3 Two-Timescale Stochastic Approximation

Many actor-critic and GTD algorithms use two coupled iterations with different step sizes:

$$ \theta_{t+1} = \theta_t + \alpha_t f(\theta_t, \phi_t, w_t), \qquad \phi_{t+1} = \phi_t + \beta_t g(\theta_t, \phi_t, \xi_t), $$

where $\alpha_t / \beta_t \to 0$ (the $\theta$-update is on the slow timescale; $\phi$ on the fast timescale). Intuitively, $\phi$ equilibrates quickly relative to $\theta$, so $\phi$ "sees" a quasi-static $\theta$, and $\theta$ "sees" the equilibrium $\phi^*(\theta)$.

Theorem B.3 — Borkar Two-Timescale Convergence

Under appropriate regularity conditions:

The fast iterate converges: $\phi_t \to \phi^*(\theta^*)$ a.s.
The slow iterate converges: $\theta_t \to \theta^*$ a.s., where $\theta^*$ is determined by the ODE $\dot{\theta} = \bar{f}(\theta, \phi^*(\theta))$.

This provides the convergence framework for actor-critic algorithms (actor = slow, critic = fast) and for GTD methods (primary weight = slow, secondary weight = fast).

B.4 Finite-Time Bounds

Modern RL theory emphasises non-asymptotic (finite-time) convergence rates. For TD(0) with linear FA and constant step size $\alpha$:

$$ \E\!\left[\|V_{\theta_T} - V^\pi\|_{d^\pi}^2\right] = O\!\left(\frac{1}{(1-\gamma)^3 T} + \frac{\alpha}{(1-\gamma)^4}\right). $$

Optimal choice $\alpha \asymp 1/T$ gives rate $O(1/((1-\gamma)^4 T))$. For Q-learning, the minimax-optimal sample complexity for finding an $\varepsilon$-optimal policy is $\tilde{\Theta}\!\left(\frac{|\S||\A|}{(1-\gamma)^3 \varepsilon^2}\right)$ (Li et al., 2021).

Exercise B.1

Prove that synchronous Q-learning with step size $\alpha_t = \frac{H+1}{H+t}$ (where $H = 1/(1-\gamma)$) satisfies $\E[\|Q_t - Q^*\|_\infty] = O\!\left(\frac{H^3 \log t}{t}\right)$.

Hint: Use the contraction property and the recursion $e_{t+1} \leq (1-\alpha_t) e_t + \alpha_t \gamma e_t + \alpha_t \sigma_t$ where $e_t = \|Q_t - Q^*\|_\infty$ and $\sigma_t$ is the noise term. Apply the technical lemma for weighted averages.

References

Key References & Further Reading

Textbooks

Sutton, R.S. & Barto, A.G. (2018). Reinforcement Learning: An Introduction, 2nd ed. MIT Press. [The canonical textbook]
Bertsekas, D.P. (2019). Reinforcement Learning and Optimal Control. Athena Scientific. [Rigorous optimisation perspective]
Szepesvári, C. (2010). Algorithms for Reinforcement Learning. Morgan & Claypool. [Concise mathematical treatment]
Puterman, M.L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. [MDP bible]
Bertsekas, D.P. & Tsitsiklis, J.N. (1996). Neuro-Dynamic Programming. Athena Scientific.
Agarwal, A., Jiang, N., Kakade, S.M. & Sun, W. (2021). Reinforcement Learning: Theory and Algorithms. [Modern theoretical monograph, available online]

Foundational Papers

Watkins, C.J.C.H. & Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4), 279-292.
Tsitsiklis, J.N. & Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE TAC.
Sutton, R.S., McAllester, D., Singh, S. & Mansour, Y. (1999). Policy gradient methods for RL with function approximation. NeurIPS.
Kakade, S.M. (2001). A natural policy gradient. NeurIPS.
Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature.
Schulman, J. et al. (2015). Trust region policy optimization. ICML.
Schulman, J. et al. (2016). High-dimensional continuous control using generalized advantage estimation. ICLR.
Schulman, J. et al. (2017). Proximal policy optimization algorithms. arXiv.
Haarnoja, T. et al. (2018). Soft actor-critic. ICML.
Bellemare, M.G., Dabney, W. & Munos, R. (2017). A distributional perspective on RL. ICML.

Convergence Theory

Jaakkola, T., Jordan, M.I. & Singh, S.P. (1994). On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation.
Borkar, V.S. & Meyn, S.P. (2000). The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim.
Borkar, V.S. (2008). Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge.
Bhandari, J., Russo, D. & Singal, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. COLT.

© 2024 — Reinforcement Learning: A Rigorous Treatment for Mathematicians
Built as a self-contained interactive reference. All mathematical content is original exposition.

Loading node

Html node

Node discussion