Reinforcement Learning

Contents

• Introduction and overview
• 0. Review: Markov chains, contractions and concentration
• 1. Markov decision processes and dynamic programming
• 2. The first algorithms of reinforcement learning
• 3. The actors: policy iteration and policy gradient
• 4. The critics: reinforcement learning with function approximation
• 5. Scaling up: towards deep RL and continuous MDPs
• 6. Exploration and exploitation
• 7. Average-reward RL and instance-optimal algorithms
• 8. Bandit methods for pure exploration and planning
• 9. Complements for self-study
• 10. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with a good M1 in mathematics or computer science who knows Markov chains and gradient descent, and who wants to understand how an agent can learn to act from rewards alone, with guarantees.

Empirical first: on a six-state “river” whose current pushes the swimmer back, the large reward sits at the far bank and a tiny one at the start. Over 2000 episodes of 20 steps, Q-learning with \varepsilon-greedy exploration settles on the tiny reward: its regret is 5929, almost all of the 3.06 available per episode.

The optimistic algorithm UCB-VI (ch. 6), given the same 2000 episodes, has regret 73 and ends with the optimal policy. Exploration, not optimisation, made the difference.

Reinforcement learning studies an agent that interacts with an unknown environment, modelled as a Markov decision process, and learns a policy that maximises its cumulative reward. The course starts from dynamic programming, where the model is known, and moves to learning from samples, to policies and value functions represented by parametric models and deep networks, and to the exploration–exploitation trade-off with its regret and sample-complexity guarantees.

The bandit chapters share their tools with Sequential Learning, and the deep-RL chapter uses the networks of Deep Learning. The linear-quadratic regulator of ch. 5 is the control problem of Robotics.

What you will be able to do

• Model a sequential decision problem as a Markov decision process and write its Bellman equations.
• Prove that the Bellman operators are contractions and derive the convergence of value iteration and policy iteration.
• Implement Monte Carlo, temporal-difference, Q-learning and SARSA updates, and explain their convergence through stochastic approximation.
• Derive the policy gradient theorem, implement REINFORCE with a baseline, and state when policy gradient reaches a global optimum.
• Analyse temporal-difference learning with linear function approximation, LSTD and fitted Q-iteration, and recognise the “deadly triad”.
• Build a deep Q-network with replay and a target network, and solve a linear-quadratic regulator by its Riccati equation.
• Design optimistic and posterior-sampling algorithms for bandits and MDPs, and bound their regret.
• Solve the average-reward optimality equation, and explain instance-dependent lower bounds and the algorithms that match them.
• Identify the best arm with a fixed confidence, compute the characteristic time of a bandit problem, and plan with a simulator by tree search.
• Read a reinforcement learning theory paper and place its result on the map of this course.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com states that the class aims at providing a comprehensive and modern introduction to reinforcement learning concepts and algorithms. It endeavours to provide a solid formal basis on the foundational notions of reinforcement learning.

The description announces eight lectures and one written exam, with the titles listed below. The Université Paris-Saclay course detail, titled “Deep reinforcement learning”, gives only the type of assessment (“Evaluation Continue non Intégrale”), with no programme of its own.

Every official lecture has a chapter in these notes, in the official order. The extensions beyond the syllabus are the review of ch. 0, the linear-quadratic regulator as the worked continuous MDP of ch. 5, the complements of ch. 9 (proofs of the stochastic approximation theorem and of the Lai–Robbins bound, and a detailed sketch of the UCB-VI regret) and the research directions of ch. 10.

Where this course fits in the programme

Official prerequisites: not displayed. The course uses finite Markov chains, conditional expectations, concentration inequalities, gradients and a little linear programming; ch. 0 reviews them.

• Refreshers — Probability and Statistics (Markov chains, martingales, Hoeffding’s inequality), Linear Algebra, Analysis and Optimization (norms, fixed points, gradients, linear programming) and Scientific Python, NumPy and PyTorch (the code).
• Semester 1 courses that prepare it — Convex Optimization and Applications in Machine Learning (gradient methods, duality), Deep Learning (the networks of ch. 5), Computational Statistics (Monte Carlo and stochastic approximation), Robotics (control and the linear-quadratic regulator) and Foundations of Large Language Models (for RL from human feedback, ch. 10).
• Related courses of semester 2 — Sequential Learning (bandits and online learning, the closest neighbour), Stopping Times and Online Algorithms (stopping rules, as in ch. 8), Bayesian Machine Learning (posterior sampling), Graphical Models: Discrete Inference and Learning (dynamic programming on graphs), Deep Learning in Practice and Training and Deploying Large-Scale Models (deep RL at scale, preference fine-tuning).
• Afterwards — the research internship: ch. 10 lists open problems of internship size.

Course outline

• 0. Review — finite Markov chains, contractions and the Banach fixed-point theorem, Hoeffding’s inequality, stochastic approximation.
• 1. MDPs and dynamic programming — policies and value functions, Bellman equations and operators, optimality, value iteration, policy iteration, linear programming, finite horizon.
• 2. The first RL algorithms — Monte Carlo and temporal-difference evaluation, Q-learning and SARSA, their convergence, exploration rules.
• 3. The actors — performance difference, approximate policy iteration, the policy gradient theorem, REINFORCE, natural gradient, TRPO and PPO.
• 4. The critics — linear value approximation, the projected Bellman equation, LSTD, fitted Q-iteration, divergence, actor–critic.
• 5. Scaling up — deep Q-networks, overestimation, continuous MDPs and the linear-quadratic regulator, deterministic and entropy-regularised policy gradients.
• 6. Exploration and exploitation — bandit regret, UCB, Lai–Robbins, Thompson sampling, optimism and posterior sampling in episodic MDPs.
• 7. Average reward and instance optimality — gain and bias, the optimality equation, diameter, UCRL2, gap-dependent lower bounds and the algorithms that match them.
• 8. Pure exploration and planning — best-arm identification with fixed confidence, the characteristic time, Track-and-Stop, sparse sampling and Monte Carlo tree search.
• 9. Complements for self-study — the proofs and sketches deferred from ch. 2, 3, 6 and 7.
• 10. Research directions and open problems — offline RL, preference-based RL, theory of function approximation, reward-free exploration, open questions.

Session plan

24 h in class (assumed) = 8 sessions of 3 h.

The volume is assumed from the organisation published on master-mva.com (eight lectures and one written exam), with 3 h per lecture; the Université Paris-Saclay programme table displays no volume. The written exam, after the eighth lecture, is not counted in the 24 h. The plan follows the official order of the lectures, one per session; the content of each session is a proposal.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material. The level never goes down from one session to the next.

Self-study, outside the 24 h (about 8 h in total): ch. 9 Complements for self-study (≈ 5 h, with Ex. 16) · ch. 10 Research directions and open problems (≈ 3 h, with Ex. 18).

How to study this module

• Read ch. 0 before session 1 if contractions or Hoeffding’s inequality feel distant; every later chapter uses them without warning.
• After each session, do the exercises of its row, then run the code of the chapter and change one ingredient (the discount, the step size, the exploration rate) to see its effect.
• Write value iteration, Q-learning, REINFORCE and UCB-VI yourself once, in NumPy, before reading a library; each is a dozen lines.
• Keep the two running examples in mind: the two-state MDP of Example 1.10 for every computation by hand, and the river chain of ch. 6 for every exploration question.
• The code uses NumPy, SciPy and PyTorch (CPU) on synthetic MDPs; every block runs in under 30 seconds on a laptop.
• Read ch. 9 after session 7 for the proofs that the sessions only sketch, and use ch. 10 to choose a paper for a project.

0. Review: Markov chains, contractions and concentration

Reinforcement learning combines three M1-level tools: Markov chains describe the dynamics, contractions give the existence and computation of value functions, and concentration inequalities with stochastic approximation turn samples into guarantees. This chapter states the facts used later. The Probability and Statistics refresher covers the same ground at a slower pace.

Finite Markov chains

Contractions and fixed points

Concentration

The proof bounds the moment generating function of a bounded variable (Hoeffding’s lemma) and applies Markov’s inequality to e^{\lambda(\bar X_n - \mathbb{E}\bar X_n)}; see Boucheron, Lugosi and Massart (2013), ch. 2. Every confidence bonus of ch. 6–ch. 8 is a version of this width.

import numpy as np

rng = np.random.default_rng(0)
n, eps, p, reps = 100, 0.1, 0.5, 200_000
heads = rng.binomial(n, p, size=reps)
freq = np.mean(np.abs(heads - n * p) >= n * eps)   # integer counts: no rounding at the boundary
bound = 2 * np.exp(-2 * n * eps**2)
print(f"empirical P(|mean - p| >= {eps}) = {freq:.4f}")
print(f"Hoeffding bound                 = {bound:.4f}")
delta = 0.05                       # half-width of a 95% confidence interval
print(f"95% Hoeffding half-width, n={n}: {np.sqrt(np.log(2/delta)/(2*n)):.3f}")

For 100 fair coins the deviation probability is 0.057 and the bound 0.271: Hoeffding’s inequality is loose by a constant factor, but it holds for any bounded law. The 95 % half-width is 0.136 .

Stochastic approximation

The running mean \bar X_n = \bar X_{n-1} + \frac{1}{n}(X_n - \bar X_{n-1}) is the simplest learning rule: move the estimate a step \alpha_n = 1/n towards the new sample. Robbins and Monro (1951) showed that the same rule finds the root of an unknown function observed with noise.

The first condition lets the iterates travel any distance; the second makes the accumulated noise \sum_n \alpha_n w_n converge. Steps \alpha_n = n^{-\beta} satisfy both exactly when 1/2 < \beta \le 1.

1. Markov decision processes and dynamic programming

When the environment is known, choosing how to act over time is a planning problem. This chapter defines Markov decision processes, shows that optimal behaviour is characterised by a fixed-point equation, and gives the two classical algorithms that solve it.

Markov decision processes and policies

The discount makes every return finite and every Bellman operator a contraction; 1/(1 - \gamma) acts as an effective horizon.

Bellman equations and operators

By Theorem 0.4, T^\star has a unique fixed point. The central result of the theory is that this fixed point is the optimal value, and that acting greedily with respect to it is optimal.

The theorem reduces a search over all history-dependent policies to a fixed-point problem in dimension S. It also says that Q^\star is enough to act: \pi^\star(s) \in \arg\max_a Q^\star(s, a) needs no model.

Value iteration

With rewards in [0, 1] and V_0 = 0, an accuracy \varepsilon is reached after a number of sweeps k \ge \frac{\log\big(1/(\varepsilon(1 - \gamma))\big)}{1 - \gamma} , each costing O(S^2 A) operations. The factor 1/(1 - \gamma) is the price of a long effective horizon.

Policy iteration

The bound A^S is very pessimistic. Ye (2011) proved that policy iteration needs a number of iterations polynomial in S and A for a fixed discount.

import numpy as np

def bellman_q(P, r, gamma, V):
    """Q(s,a) = r(s,a) + gamma * sum_s' P(s'|s,a) V(s'); P has shape (S, A, S)."""
    return r + gamma * P @ V

def value_iteration(P, r, gamma, tol=1e-8):
    V, k = np.zeros(P.shape[0]), 0
    while True:
        V_new = bellman_q(P, r, gamma, V).max(axis=1)
        k += 1
        if np.max(np.abs(V_new - V)) < tol:
            return V_new, k
        V = V_new

def policy_evaluation(P, r, gamma, pi):
    S = P.shape[0]
    P_pi, r_pi = P[np.arange(S), pi], r[np.arange(S), pi]
    return np.linalg.solve(np.eye(S) - gamma * P_pi, r_pi)

def policy_iteration(P, r, gamma):
    pi, k = np.zeros(P.shape[0], dtype=int), 0
    while True:
        V = policy_evaluation(P, r, gamma, pi)
        pi_new = bellman_q(P, r, gamma, V).argmax(axis=1)
        k += 1
        if np.array_equal(pi_new, pi):
            return V, pi, k
        pi = pi_new

# Example 1.10: two states, actions 0 = "safe", 1 = "risky"
P = np.zeros((2, 2, 2))
P[0, 0, 0] = 1.0                       # state 1, safe: stay
P[0, 1, 1] = 1.0                       # state 1, risky: go to state 2
P[1, 0] = [0.2, 0.8]                   # state 2, safe: back w.p. 0.2
P[1, 1, 0] = 1.0                       # state 2, risky: back to state 1
r = np.array([[1.0, 0.0], [2.0, 0.0]])
V, k = value_iteration(P, r, 0.9)
_, pi, k_pi = policy_iteration(P, r, 0.9)
print("two-state MDP: V* =", V.round(3), "after", k, "VI sweeps;",
      "PI policy", pi, "after", k_pi, "iterations")

# a random MDP: VI needs many sweeps, PI a handful of iterations
rng = np.random.default_rng(1)
S, A = 50, 4
P = rng.dirichlet(np.ones(S), size=(S, A))
r = rng.uniform(size=(S, A))
for gamma in (0.9, 0.99):
    V_vi, k_vi = value_iteration(P, r, gamma)
    V_pi, _, k_pi = policy_iteration(P, r, gamma)
    print(f"gamma={gamma}: VI sweeps={k_vi}, PI iterations={k_pi}, "
          f"max |V_VI - V_PI| = {np.max(np.abs(V_vi - V_pi)):.1e}")

The code counts the final check as an iteration: policy iteration evaluates two policies and confirms the second. On a random MDP with 50 states and 4 actions, value iteration needs 174 sweeps for \gamma = 0.9 and 1812 for \gamma = 0.99, while policy iteration stops after 3 iterations in both cases.

Linear programming and the finite horizon

In a problem with horizon H and no discount, the value depends on the remaining time. Backward induction computes V_H = 0 and V_h = T^\star V_{h+1} for h = H - 1, \dots, 0, the greedy action at step h being taken with respect to V_{h+1}.

The optimal policy is then Markov but non-stationary. The proof is Step 2 of Theorem 1.7, and the episodic algorithms of ch. 6 use this recursion.

2. The first algorithms of reinforcement learning

In reinforcement learning the transition kernel and the rewards are unknown: the agent only sees transitions (s_t, a_t, r_t, s_{t+1}). This chapter shows how to estimate values from such samples, and how to learn Q^\star directly, without ever estimating the model.

Monte Carlo and temporal-difference evaluation

Monte Carlo waits until the end of an episode and its variance grows with the horizon. Temporal differences instead use the Bellman equation itself as a target, replacing the unknown future by the current estimate. This is called bootstrapping.

The convergence of TD(0), and of Q-learning below, follows from a single stochastic approximation theorem for contractions.

The parameter \lambda trades bias for variance: small \lambda trusts the current estimate, large \lambda trusts the observed rewards.

Q-learning and SARSA

To act well, the agent needs Q^\star, the fixed point of the operator of Theorem 1.7 on action values. Watkins (1989) proposed to iterate it from samples.

Q-learning is off-policy: the behaviour policy only has to visit every pair, while the target always uses the greedy action. SARSA is its on-policy counterpart.

Two exploration rules are standard. The \varepsilon-greedy rule plays the greedy action with probability 1 - \varepsilon and a uniform action otherwise; the choice \varepsilon = c/n_t(s) with 0 < c < 1, where n_t(s) counts the visits of s, gives a GLIE scheme.

The Boltzmann rule plays a with probability proportional to \exp(Q(s, a)/\tau). Neither rule is driven by uncertainty, which is why both fail on the river of the introduction (ch. 6).

import numpy as np

# the two-state MDP of Example 1.10 (actions 0 = safe, 1 = risky)
P = np.zeros((2, 2, 2))
P[0, 0, 0], P[0, 1, 1], P[1, 1, 0] = 1.0, 1.0, 1.0
P[1, 0] = [0.2, 0.8]
r = np.array([[1.0, 0.0], [2.0, 0.0]])
gamma = 0.9

Q_star = np.zeros((2, 2))
for _ in range(2000):                       # value iteration on Q
    Q_star = r + gamma * P @ Q_star.max(axis=1)

def q_learning(exponent, n_steps=200_000, seed=0):
    """Off-policy Q-learning, uniform behaviour policy, step 1/N(s,a)^exponent."""
    rng = np.random.default_rng(seed)
    Q, N, s = np.zeros((2, 2)), np.zeros((2, 2)), 0
    errors = {}
    for t in range(1, n_steps + 1):
        a = rng.integers(2)
        s_next = rng.choice(2, p=P[s, a])
        N[s, a] += 1
        alpha = 1.0 / N[s, a] ** exponent
        target = r[s, a] + gamma * Q[s_next].max()
        Q[s, a] += alpha * (target - Q[s, a])
        s = s_next
        if t in (1_000, 10_000, 100_000, n_steps):
            errors[t] = round(float(np.max(np.abs(Q - Q_star))), 3)
    return Q, errors

print("Q* =", Q_star.round(2).tolist())
for exponent in (1.0, 0.7):
    Q, errors = q_learning(exponent)
    print(f"alpha = 1/N^{exponent}: errors {errors}, greedy policy {Q.argmax(axis=1)}")

Both runs find the greedy policy (risky, safe), but the errors differ. With \alpha = 1/N the sup-norm error is still 4.78 after 200 000 steps; with \alpha = N^{-0.7} it is 0.021 (ch. 9 explains why).

3. The actors: policy iteration and policy gradient

Value-based methods derive a policy from a value function. Actor methods improve the policy itself, either by exact or approximate policy iteration steps or by gradient ascent on its value. This chapter gives the identity behind both, the policy gradient theorem, and what is known about global convergence.

Performance difference and approximate policy iteration

For a start distribution \mu, write V^\pi(\mu) = \sum_s \mu(s) V^\pi(s), define the advantage A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s), and the discounted occupancy d^\pi_\mu(s) = (1 - \gamma) \sum_{t \ge 0} \gamma^t\, \mathbb{P}^\pi(s_t = s \mid s_0 \sim \mu) .

The lemma explains policy iteration in one line: a greedy policy \pi' has \mathbb{E}_{a \sim \pi'} A^\pi(s, a) \ge 0 in every state, so it cannot be worse. It also shows the difficulty of approximate improvement: the advantage is averaged under the occupancy of the new policy, which is unknown before it is played.

The policy gradient theorem

For the tabular softmax, the score is \frac{\partial \log \pi(a \mid s)}{\partial\theta_{s, b}} = \mathbf{1}_{a = b} - \pi(b \mid s) , and the theorem becomes \frac{\partial J}{\partial \theta_{s, a}} = \frac{1}{1 - \gamma}\, d^{\pi_\theta}_\mu(s)\, \pi_\theta(a \mid s)\, A^{\pi_\theta}(s, a) .

import numpy as np

# two-state MDP of Example 1.10, softmax policy pi(a|s) ∝ exp(theta[s, a])
P = np.zeros((2, 2, 2))
P[0, 0, 0], P[0, 1, 1], P[1, 1, 0] = 1.0, 1.0, 1.0
P[1, 0] = [0.2, 0.8]
r = np.array([[1.0, 0.0], [2.0, 0.0]])
gamma, mu = 0.9, np.array([0.5, 0.5])

def softmax(theta):
    z = np.exp(theta - theta.max(axis=1, keepdims=True))
    return z / z.sum(axis=1, keepdims=True)

def J_and_grad(theta):
    pi = softmax(theta)
    P_pi = np.einsum("sa,sat->st", pi, P)
    r_pi = (pi * r).sum(axis=1)
    V = np.linalg.solve(np.eye(2) - gamma * P_pi, r_pi)
    Q = r + gamma * P @ V
    d = (1 - gamma) * np.linalg.solve(np.eye(2) - gamma * P_pi.T, mu)  # d_mu^pi
    grad = d[:, None] * pi * (Q - V[:, None]) / (1 - gamma)           # Theorem 3.4
    return mu @ V, grad

theta = np.zeros((2, 2))
J, g = J_and_grad(theta)
eps, fd = 1e-6, np.zeros((2, 2))
for i in range(2):
    for j in range(2):
        e = np.zeros((2, 2)); e[i, j] = eps
        fd[i, j] = (J_and_grad(theta + e)[0] - J_and_grad(theta - e)[0]) / (2 * eps)
print("J(uniform policy) =", round(J, 3))
print("policy-gradient theorem:", g.round(4).tolist())
print("finite differences:     ", fd.round(4).tolist())

for step in range(1, 2001):                  # exact gradient ascent, step 1
    J, g = J_and_grad(theta)
    theta += 1.0 * g
    if step in (10, 100, 2000):
        print(f"step {step:4d}: J = {J:.3f}, pi(risky|1) = {softmax(theta)[0, 1]:.3f}")

# REINFORCE on a 3-armed bandit: variance with and without a baseline
rng = np.random.default_rng(0)
means, offset = np.array([1.0, 1.5, 2.0]), 10.0
pi = np.ones(3) / 3
a = rng.choice(3, p=pi, size=100_000)
R = offset + means[a] + rng.normal(size=a.size)
score = np.eye(3)[a] - pi                       # grad of log softmax at theta = 0
for b, name in [(0.0, "no baseline"), (offset + means.mean(), "baseline = V")]:
    G = (R - b)[:, None] * score
    print(f"{name:13s}: mean grad {G.mean(0).round(3)}, total variance {G.var(0).sum():.2f}")

The finite differences confirm Theorem 3.4 to four digits. On the bandit, whose rewards are shifted by 10, both estimators have the same mean, close to the exact gradient (-1/6, 0, 1/6). The total variance per sample falls from 88.94 without a baseline to

0.73 \text{ with the baseline } b = V .

When does policy gradient find the optimum?

J is not concave in \theta, even for the tabular softmax. Still, a gradient-domination inequality shows that it has no bad stationary points when \mu covers the state space.

If \mu > 0 everywhere, every stationary point over the simplices is therefore globally optimal, and projected gradient ascent converges to an optimal policy. For the softmax, Agarwal and coauthors prove asymptotic convergence, and Mei, Xiao, Szepesvári and Schuurmans (2020) a rate O(1/t).

The bound has no distribution-mismatch coefficient, and as \eta \to \infty the update becomes policy iteration: the natural gradient bridges the two views of the actor.

4. The critics: reinforcement learning with function approximation

Tables of values do not scale: a state may be an image or a robot configuration. This chapter replaces V and Q by parametric “critics”, studies what temporal differences converge to, and shows when approximation errors stay controlled and when they explode.

Linear value approximation and the projected Bellman equation

TD with approximation cannot reach V^\pi itself when it is outside the span. It solves the projected Bellman equation, which is well posed for the right norm.

The TD solution is not the best approximation \Pi V^\pi, but it is within a factor 1/\sqrt{1 - \gamma^2} of it. The factor grows with the horizon: at \gamma = 0.95 it is 3.2.

Sample-based critics

By the ergodic theorem (Theorem 0.2), \hat A_n/n \to A and \hat b_n/n \to b, so LSTD converges to w_{\mathrm{TD}} with no step size. Each step costs O(k^2) operations. LSPI (Lagoudakis and Parr, 2003) uses its action-value version as the evaluation step of approximate policy iteration.

The sup norm is unrealistic for a regression. Munos (2007) and Munos and Szepesvári (2008) prove L_p versions, in which concentrability coefficients measure how far the occupancy of future policies is from the data distribution. These coefficients are the central difficulty of offline RL (ch. 10).

The deadly triad

Sutton and Barto (2018, sec. 11.3) call the combination of function approximation, bootstrapping and off-policy data the deadly triad: any two are safe, all three can diverge. Baird (1995) built a seven-state example where even expected updates diverge.

Remedies replace the semi-gradient by a true gradient of the projected Bellman error \|\Pi T^\pi V_w - V_w\|_d^2, as in gradient-TD methods (Sutton et al., 2009), or slow the bootstrap target down, as the target networks of ch. 5 do.

import numpy as np

rng = np.random.default_rng(0)
S, gamma = 50, 0.95
# Markov chain of a fixed policy on a ring: right w.p. 0.6, left w.p. 0.4
P = np.zeros((S, S))
for s in range(S):
    P[s, (s + 1) % S], P[s, (s - 1) % S] = 0.6, 0.4
r = (np.arange(S) < 10).astype(float)          # reward 1 on states 0..9
V = np.linalg.solve(np.eye(S) - gamma * P, r)   # true value function
d = np.ones(S) / S                              # stationary distribution (uniform)
D = np.diag(d)
centres = np.linspace(0, S, 5, endpoint=False)
dist = np.abs(np.arange(S)[:, None] - centres)
dist = np.minimum(dist, S - dist)
Phi = np.exp(-(dist / 6.0) ** 2)                # 5 Gaussian bumps on the ring

def d_norm(v):
    return np.sqrt(v @ D @ v)

w_proj = np.linalg.solve(Phi.T @ D @ Phi, Phi.T @ D @ V)                # Pi V
A = Phi.T @ D @ (Phi - gamma * P @ Phi)
w_td = np.linalg.solve(A, Phi.T @ D @ r)                                # TD fixed point
print(f"||V - Pi V||_d     = {d_norm(V - Phi @ w_proj):.3f}")
print(f"||V - Phi w_TD||_d = {d_norm(V - Phi @ w_td):.3f}"
      f"  (bound {d_norm(V - Phi @ w_proj) / np.sqrt(1 - gamma**2):.3f})")

# sample-based LSTD and TD(0) along one trajectory of length n
n, s = 100_000, 0
A_hat, b_hat, w = np.zeros((5, 5)), np.zeros(5), np.zeros(5)
for t in range(1, n + 1):
    s_next = (s + 1) % S if rng.random() < 0.6 else (s - 1) % S
    phi, phi_next = Phi[s], Phi[s_next]
    A_hat += np.outer(phi, phi - gamma * phi_next)
    b_hat += r[s] * phi
    w += (2.0 / t ** 0.6) * (r[s] + gamma * phi_next @ w - phi @ w) * phi   # TD(0)
    s = s_next
w_lstd = np.linalg.solve(A_hat, b_hat)
print(f"LSTD  from samples: ||w - w_TD|| = {np.linalg.norm(w_lstd - w_td):.3f}")
print(f"TD(0) from samples: ||w - w_TD|| = {np.linalg.norm(w - w_td):.3f}")

# Example 4.7: off-policy updates on the transition 1 -> 2 only (features 1 and 2)
for g in (0.4, 0.9):
    w = 1.0
    for _ in range(100):
        w += 0.1 * (0.0 + g * 2 * w - w) * 1.0
    print(f"gamma = {g}: w after 100 off-policy TD updates = {w:.3g}")

On the ring, the best approximation has error 1.692 in the d-norm. The TD fixed point has error 1.889, well inside the bound 5.419 of Theorem 4.4. After 10^5 transitions, LSTD is at distance 0.149 from w_{\mathrm{TD}} and TD(0) at 0.195.

Actor–critic methods

An actor–critic algorithm runs a critic, learnt by TD, and an actor that follows the policy gradient with the critic in place of Q^\pi. Konda and Tsitsiklis (2000) proved its convergence with two time scales, the critic moving faster. The critic may bias the gradient, unless its features are chosen to match the actor.

The same condition reads F(\theta)\, w^\star = (1 - \gamma) \nabla J(\theta): the compatible critic’s weights are, up to the factor 1 - \gamma, the natural gradient of Definition 3.8 (Kakade, 2001).

5. Scaling up: towards deep RL and continuous MDPs

Deep networks can represent value functions and policies on images or high-dimensional states, but they make the bootstrapped regressions of ch. 4 unstable. Continuous actions make the maximum over actions an optimisation problem of its own. This chapter shows how deep Q-networks and deep actor–critic methods handle both, and solves the classical continuous MDP with a closed form, the linear-quadratic regulator.

Deep Q-networks

Between two refreshes the target is fixed, so the inner loop is a regression: DQN is a stochastic version of fitted Q-iteration (Definition 4.5), one iteration every C steps. The replay buffer reuses data and breaks the correlation of consecutive samples.

With K actions of equal value and independent standard Gaussian errors, the bias of the maximum is about 0.56 for K = 2 and 1.54 for K = 10. Bootstrapping propagates this bias through the states.

Double DQN (van Hasselt, Guez and Silver, 2016) chooses the action with the online network and evaluates it with the target network: y = r + \gamma\, Q_{\theta^-}\big(s', \arg\max_{a'} Q_\theta(s', a')\big) .

import numpy as np
import torch
from torch import nn

torch.set_num_threads(1)
torch.manual_seed(0)
rng = np.random.default_rng(0)

# chain MDP: 8 states, action 0 = left, 1 = right (succeeds w.p. 0.9)
S, A, gamma = 8, 2, 0.9
P = np.zeros((S, A, S)); R = np.zeros((S, A))
for s in range(S):
    P[s, 0, max(s - 1, 0)] = 1.0
    P[s, 1, min(s + 1, S - 1)] += 0.9
    P[s, 1, s] += 0.1
R[0, 0], R[S - 1, 1] = 0.2, 1.0
Q_star = np.zeros((S, A))
for _ in range(1000):
    Q_star = R + gamma * P @ Q_star.max(axis=1)

net = nn.Sequential(nn.Linear(S, 64), nn.ReLU(), nn.Linear(64, A))
target = nn.Sequential(nn.Linear(S, 64), nn.ReLU(), nn.Linear(64, A))
target.load_state_dict(net.state_dict())
opt = torch.optim.Adam(net.parameters(), lr=1e-3)
eye = torch.eye(S)
buffer, s = [], 0
for step in range(1, 8001):
    a = int(rng.integers(A))                       # uniform behaviour policy
    s_next = int(rng.choice(S, p=P[s, a]))
    buffer.append((s, a, R[s, a], s_next)); s = s_next
    if len(buffer) < 256:
        continue
    idx = rng.integers(len(buffer), size=64)       # experience replay
    bs, ba, br, bn = map(np.array, zip(*[buffer[i] for i in idx]))
    with torch.no_grad():                          # frozen target network
        y = torch.tensor(br, dtype=torch.float32) + gamma * target(eye[bn]).max(1).values
    q = net(eye[bs]).gather(1, torch.tensor(ba)[:, None]).squeeze(1)
    loss = ((q - y) ** 2).mean()
    opt.zero_grad(); loss.backward(); opt.step()
    if step % 200 == 0:                            # refresh the target
        target.load_state_dict(net.state_dict())
Q_dqn = net(eye).detach().numpy()
print("max |Q_DQN - Q*| =", round(float(np.abs(Q_dqn - Q_star).max()), 3))
print("greedy DQN policy:", Q_dqn.argmax(1), " optimal:", Q_star.argmax(1))

# discounted scalar LQR: x' = a x + b u + noise, cost q x^2 + rho u^2
a, b, q, rho, g = 1.2, 1.0, 1.0, 1.0, 0.95
p = q
for _ in range(500):                               # Riccati fixed-point iteration
    p = q + g * a**2 * p - (g * a * b * p) ** 2 / (rho + g * b**2 * p)
K = g * a * b * p / (rho + g * b**2 * p)
print(f"Riccati: p = {p:.4f}, gain K = {K:.4f}, closed loop a - bK = {a - b * K:.4f}")

On the chain, Q^\star ranges up to 10, and the network learnt from 8000 uniformly random transitions is within 0.29 of it in every pair, with the optimal greedy policy.

Continuous MDPs and the linear-quadratic regulator

Quadratic costs are unbounded, so the linear-quadratic regulator falls outside this setting, but it has an explicit solution.

Two features of this solution matter for learning. The optimal gain does not depend on the noise, which is certainty equivalence for control. And the Riccati iteration, P_0 = 0 then the right-hand side, is exactly value iteration on quadratic functions.

In the scalar example of the code, a = 1.2, b = q = \rho = 1 and \gamma = 0.95. The fixed point is p = 1.9322, the gain K = 0.7768, and the closed loop is stable although a > 1:

a - bK = 0.4232 .

Policy gradients for continuous actions

DDPG (Lillicrap et al., 2016) combines this gradient with a deep critic, a replay buffer and slowly moving target networks. TD3 (Fujimoto, van Hoof and Meger, 2018) adds the minimum of two critics in the target, a deterministic counterpart of the double estimator of Proposition 5.2.

Since 0 \le \mathcal{H} \le \log A, the regularised and unregularised optimal values differ by at most \tau\log A/(1 - \gamma). Soft actor–critic (Haarnoja, Zhou, Abbeel and Levine, 2018) applies this principle to continuous actions, with a Gaussian actor trained to minimise, in each state, \mathrm{KL}\big(\pi(\cdot \mid s) \,\big\|\, \exp(Q(s, \cdot)/\tau)/Z(s)\big) .

PPO in practice combines parallel rollouts, GAE advantages, and several epochs of minibatch steps on the clipped objective of Definition 3.9.

The programming assignment announced on master-mva.com comes after this session; its content is not displayed. The solo projects of Projects and assessment are sized like such an assignment.

6. Exploration and exploitation

A learning agent must try actions whose value it does not know, at a cost, and exploit those it knows to be good. This chapter measures the cost by the regret, solves the trade-off for bandits, and extends the principle of optimism to MDPs, where it explains the river of the introduction.

Multi-armed bandits

A constant exploration rate \varepsilon pulls each arm about \varepsilon T/K times, a regret linear in T. The principle of optimism in the face of uncertainty instead plays the arm whose plausible value is highest.

Lai and Robbins showed that this order is necessary, with an instance-dependent constant that is the model of the results of ch. 7 and ch. 8.

With Proposition 6.2, the theorem bounds the regret of every consistent algorithm from below.

Pinsker’s inequality, \mathrm{kl}(\mu_a, \mu^\star) \ge 2\Delta_a^2, bounds the constant by \sum_a 1/(2\Delta_a). Conversely, the KL divergence is at most the \chi^2 divergence, \Delta_a^2/(\mu^\star(1 - \mu^\star)), so UCB1 is optimal up to a constant factor when the means stay away from 0 and 1.

KL-UCB (ch. 7) and Thompson sampling reach the constant itself. Thompson sampling (Thompson, 1933) samples a mean for each arm from its posterior and plays the best sample. For Bernoulli arms with uniform priors it is asymptotically optimal (Kaufmann, Korda and Munos, 2012; Agrawal and Goyal, 2013).

Optimism in episodic MDPs

A lower bound of order \sqrt{HSAT} holds for every algorithm (Domingues, Ménard, Kaufmann and Valko, 2021), so the Bernstein version is minimax optimal up to logarithmic factors.

The Bayesian alternative is posterior sampling (PSRL; Osband, Russo and Van Roy, 2013). At each episode, sample an MDP from the posterior, for example Dirichlet laws on the transitions, and play its optimal policy. Its Bayesian regret is \tilde O(HS\sqrt{AT}), and it is often better than optimism in practice.

import numpy as np

# RiverSwim-type chain (Strehl and Littman, 2008): 6 states, 0 = left, 1 = right
S, A, H, K = 6, 2, 20, 2000
P = np.zeros((S, A, S)); R = np.zeros((S, A))
for s in range(S):
    P[s, 0, max(s - 1, 0)] = 1.0                       # swimming with the current
    if s == 0:
        P[s, 1, [0, 1]] = [0.6, 0.4]
    elif s == S - 1:
        P[s, 1, [s - 1, s]] = [0.4, 0.6]
    else:
        P[s, 1, [s - 1, s, s + 1]] = [0.05, 0.6, 0.35]
R[0, 0], R[S - 1, 1] = 0.005, 1.0

def backward_induction(P, R, bonus=0.0):
    """Optimal H-step policy of the model (P, R + bonus); values clipped at H - h."""
    V, pi = np.zeros((H + 1, S)), np.zeros((H, S), dtype=int)
    for h in range(H - 1, -1, -1):
        Q = np.minimum(R + bonus + P @ V[h + 1], H - h)
        pi[h], V[h] = Q.argmax(1), Q.max(1)
    return pi, V

def policy_value(pi):
    V = np.zeros(S)
    for h in range(H - 1, -1, -1):
        V = R[np.arange(S), pi[h]] + P[np.arange(S), pi[h]] @ V
    return V[0]

V_star = backward_induction(P, R)[1][0, 0]

def run(agent, c=0.5, seed=0):
    rng = np.random.default_rng(seed)
    N, Nsas, Rsum = np.zeros((S, A)), np.zeros((S, A, S)), np.zeros((S, A))
    Q, regret = np.zeros((H, S, A)), 0.0
    for k in range(K):
        if agent == "ucbvi":                           # optimism in the face of uncertainty
            n = np.maximum(N, 1)
            P_hat = np.where(N[..., None] > 0, Nsas / n[..., None], 1.0 / S)
            bonus = c * np.sqrt(np.log(S * A * H * K) / n)
            pi = backward_induction(P_hat, Rsum / n, bonus)[0]
        else:                                          # epsilon-greedy Q-learning
            pi = Q.argmax(2)
        regret += V_star - policy_value(pi)
        s = 0
        for h in range(H):
            a = pi[h, s]
            if agent == "qlearning" and rng.random() < 0.1:
                a = rng.integers(A)
            s2 = rng.choice(S, p=P[s, a])
            N[s, a] += 1; Nsas[s, a, s2] += 1; Rsum[s, a] += R[s, a]
            if agent == "qlearning":
                alpha = (H + 1) / (H + N[s, a])
                target = R[s, a] + (Q[h + 1, s2].max() if h + 1 < H else 0.0)
                Q[h, s, a] += alpha * (target - Q[h, s, a])
            s = s2
    return regret, pi

print(f"V*(start) = {V_star:.3f}")
for agent, c in [("qlearning", None), ("ucbvi", 0.5), ("ucbvi", 20.0)]:
    regret, pi = run(agent, c)
    print(f"{agent:10s} c={c}: regret after {K} episodes = {regret:7.1f}, "
          f"policy at step 1 = {pi[0]}")

Swimming right is optimal in every state, with V^\star_1(s_1) = 3.064. Q-learning with \varepsilon = 0.1 starts from pessimistic values, finds the small reward at the left bank first and never revisits that belief: its regret, 5929, grows linearly. UCB-VI with c = 0.5 has regret 73.3 and plays the optimal policy at the end.

With the worst-case scale c = H = 20 the bonuses dominate for the whole run, and the regret after 2000 episodes is 6088. The theory gives the rate, not the constants: practical implementations shrink the bonus or use posterior sampling.

7. Average-reward RL and instance-optimal algorithms

A robot or a recommender that runs indefinitely has no natural discount. This chapter defines the long-run average reward, its optimality equation, and regret in this setting, then asks what the best possible regret is on a given MDP, not in the worst case.

Gain, bias and the optimality equation

The diameter, or the span of the bias, replaces the horizon 1/(1 - \gamma) of the discounted setting: it is the scale of the values, and the regret bounds below depend on it.

import numpy as np

# the river chain of ch. 6, now as a continuing (average-reward) MDP
S, A = 6, 2
P = np.zeros((S, A, S)); R = np.zeros((S, A))
for s in range(S):
    P[s, 0, max(s - 1, 0)] = 1.0
    if s == 0:
        P[s, 1, [0, 1]] = [0.6, 0.4]
    elif s == S - 1:
        P[s, 1, [s - 1, s]] = [0.4, 0.6]
    else:
        P[s, 1, [s - 1, s, s + 1]] = [0.05, 0.6, 0.35]
R[0, 0], R[S - 1, 1] = 0.005, 1.0

h = np.zeros(S)                                  # relative value iteration
for it in range(5000):
    Th = (R + P @ h).max(axis=1)
    g, h_new = Th[0] - h[0], Th - Th[0]
    if np.max(np.abs(h_new - h)) < 1e-12:
        break
    h = h_new
gaps = g + h[:, None] - (R + P @ h)              # Delta(s,a) >= 0, zero for optimal a
print(f"gain g* = {g:.4f} after {it} sweeps; bias h* = {h.round(3)}")
print("gaps Delta(s, left) =", gaps[:, 0].round(3))

D = 0.0                                          # diameter: worst fastest hitting time
for target in range(S):
    T = np.zeros(S)
    for _ in range(10_000):
        T_new = 1 + (P @ T).min(axis=1)
        T_new[target] = 0.0
        if np.max(np.abs(T_new - T)) < 1e-10:
            break
        T = T_new
    D = max(D, T.max())
print(f"span of h* = {h.max() - h.min():.3f} <= diameter D = {D:.2f}")

for gamma in (0.9, 0.99, 0.999):                 # vanishing discount: (1-gamma) V* -> g*
    V = np.zeros(S)
    for _ in range(200_000):
        V_new = (R + gamma * P @ V).max(axis=1)
        if np.max(np.abs(V_new - V)) < 1e-10:
            break
        V = V_new
    print(f"gamma = {gamma}: (1 - gamma) V*(0) = {(1 - gamma) * V[0]:.4f}")

def kl_bern(p, q):
    p, q = np.clip(p, 1e-12, 1 - 1e-12), np.clip(q, 1e-12, 1 - 1e-12)
    return p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q))

def kl_ucb(mean, n, t):
    lo, hi = mean, 1.0                           # bisection: largest q with n kl <= log t
    for _ in range(60):
        mid = (lo + hi) / 2
        lo, hi = (mid, hi) if n * kl_bern(mean, mid) <= np.log(t) else (lo, mid)
    return lo

for mean in (0.3, 0.95):
    print(f"mean {mean}, n = 20, t = 1000: KL-UCB index {kl_ucb(mean, 20, 1000):.4f}, "
          f"UCB1 index {mean + np.sqrt(2 * np.log(1000) / 20):.4f}")

On the river chain, relative value iteration converges in 140 sweeps to g^\star = 0.4286. The bias rises from 0 at the left bank to 6.727 at the right bank, below the diameter 15.69. The values (1 - \gamma)V^\star_\gamma(s_0) approach g^\star slowly: 0.120, 0.375 and 0.423 for \gamma = 0.9, 0.99 and 0.999.

Regret, optimism and instance optimality

These are worst-case statements. On a fixed MDP, the regret can be logarithmic, and the right constant comes from the gaps of the optimality equation, exactly as for bandits.

For a bandit, \Delta(s, a) is the gap \Delta_a and the proposition is Proposition 6.2. On the river chain, the gaps of the action “left” are 0.424 at the left bank and between 1.5 and 1.86 elsewhere.

The bound is the MDP version of Theorem 6.6. Algorithms that match such constants are called instance optimal; they replace Hoeffding bonuses by KL divergences.

The KL index adapts to the variance of the arm. With n = 20 pulls at t = 1000 (and c = 0), an empirical mean 0.3 gets the KL-UCB index 0.703 and the UCB1 index 1.131. For a mean of 0.95 the KL-UCB index is just below 1, while the UCB1 index is 1.781, larger than any possible mean.

The same ideas extend to MDPs. KL-UCRL (Filippi, Cappé and Garivier, 2010) uses KL confidence sets in UCRL2. IMED-RL (Pesquerel and Maillard, 2022) extends IMED to ergodic MDPs and attains the Burnetas–Katehakis constant.

8. Bandit methods for pure exploration and planning

Sometimes rewards collected during learning do not count: only the final decision does. This chapter studies how few samples suffice to identify the best arm with a prescribed confidence, and uses the same ideas to plan in an MDP with a simulator.

Best-arm identification with fixed confidence

The maximising weights w^\star(\mu) are the proportions in which an optimal strategy samples the arms. For two Gaussian arms of variance \sigma^2 and gap \Delta, w^\star = (1/2, 1/2) and T^\star = 8\sigma^2/\Delta^2.

import numpy as np
from scipy.optimize import minimize

mu, delta = np.array([0.5, 0.45, 0.4, 0.3]), 0.05     # Bernoulli arms, arm 0 is best
K = mu.size

def successive_elimination(rng):
    active, sums, n, pulls = list(range(K)), np.zeros(K), 0, 0
    while len(active) > 1:
        n += 1                                         # one more pull of each active arm
        sums[active] += rng.random(len(active)) < mu[active]
        pulls += len(active)
        means = sums / n
        radius = np.sqrt(np.log(4 * K * n**2 / delta) / (2 * n))
        best = max(active, key=lambda a: means[a])
        active = [a for a in active if means[best] - means[a] < 2 * radius]
    return active[0], pulls                            # recommendation, total samples

rng = np.random.default_rng(0)
runs = [successive_elimination(rng) for _ in range(50)]
print(f"successive elimination: {sum(rec != 0 for rec, _ in runs)} errors in 50 runs, "
      f"{np.mean([p for _, p in runs]):.0f} samples on average")

def kl(p, q):
    return p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q))

def inner(w):                                          # inf over the alternative set
    vals = []
    for a in range(1, K):
        m = (w[0] * mu[0] + w[a] * mu[a]) / (w[0] + w[a])
        vals.append(w[0] * kl(mu[0], m) + w[a] * kl(mu[a], m))
    return min(vals)

res = minimize(lambda z: -inner(np.exp(z) / np.exp(z).sum()), np.zeros(K),
               method="Nelder-Mead", options={"xatol": 1e-8, "fatol": 1e-12, "maxiter": 5000})
w_opt = np.exp(res.x) / np.exp(res.x).sum()
T_star = 1 / inner(w_opt)
kl_delta = (1 - 2 * delta) * np.log((1 - delta) / delta)   # kl(delta, 1 - delta)
print(f"optimal proportions w* = {w_opt.round(3)}, T*(mu) = {T_star:.0f}")
print(f"lower bound T*(mu) kl(delta, 1 - delta) = {T_star * kl_delta:.0f} samples")

On four Bernoulli arms with means (0.5, 0.45, 0.4, 0.3), the optimal weights put 92 % of the samples on the two best arms, and T^\star(\mu) = 867. At \delta = 0.05 the lower bound is 2297 samples, while successive elimination uses 47 188 on average, with no error in 50 runs.

Most of the factor 20 comes from the threshold: \log(4Kn^2/\delta) \approx 26 at the end of a run, against \mathrm{kl}(\delta, 1 - \delta) = 2.65, and from the factor 2 in the elimination rule. GLR stopping removes both.

Planning with a simulator

The cost does not depend on the number of states, but it is exponential in the horizon; adaptive methods spend the budget only where it matters.

UCT recommends the optimal action with probability tending to 1, but its worst case is bad. Coquelin and Munos (2007) built trees on which it needs a hyper-exponential number of simulations in the depth, because UCB bonuses at inner nodes treat non-stationary returns as i.i.d.

The pure-exploration view leads to planners with guarantees. MDP-GapE (Jonsson, Kaufmann, Ménard, Darwiche Domingues, Leurent and Valko, 2020) stops as soon as an \varepsilon-optimal first action is identified with confidence 1 - \delta. Its sample complexity depends on the gaps of the tree, as Theorem 8.4 suggests.

9. Complements for self-study

This chapter completes the proofs that the sessions only sketch, and adds a few complements: step sizes, conservative policy iteration, the dual linear program. It can be read after session 7; each section names the result it concerns.

Asynchronous stochastic approximation (Theorem 2.3)

The proof follows Tsitsiklis (1994) and Bertsekas and Tsitsiklis (1996, sec. 4.3). Shift coordinates so that x^\star = 0; then \|H x\|_\infty \le \gamma \|x\|_\infty.

Step sizes of Q-learning (ch. 2)

The code of ch. 2 shows the step 1/N to be much slower than N^{-0.7}. Even-Dar and Mansour (2003) explain this: with the step 1/N, the convergence time of Q-learning can be exponential in 1/(1 - \gamma), while polynomial steps N^{-\beta} with 1/2 < \beta < 1 give polynomial bounds.

Approximate policy iteration (Proposition 3.2)

The policies of approximate policy iteration may oscillate. Conservative policy iteration (Kakade and Langford, 2002) moves only a fraction \alpha towards the greedy policy, \pi_{k+1} = (1 - \alpha)\pi_k + \alpha\pi'. The occupancy then changes by O(\alpha), so Lemma 3.1 guarantees an improvement when \alpha is small compared with the estimated advantage.

Softmax policy gradient and the natural gradient (Definition 3.8)

For the tabular softmax, with e_{s,a} the canonical basis vectors, the score and the compatible critic are \nabla\log\pi(a \mid s) = e_{s,a} - \sum_b \pi(b \mid s)\, e_{s,b}, \qquad f_w(s, a) = w_{s,a} - \sum_b \pi(b \mid s)\, w_{s,b} . The critic is a function with mean zero under \pi(\cdot \mid s).

The projection of Q^\pi on such functions is the advantage, and w = A^\pi attains it exactly. By the remark after Proposition 4.8, the natural gradient direction is A^\pi/(1 - \gamma), up to constants per state that do not change the policy.

A step \eta in that direction multiplies \pi(a \mid s) by \exp(\eta A^\pi(s, a)/(1 - \gamma)), which is the update of Definition 3.8. It is mirror ascent with the KL divergence in each state, and its analysis is the multiplicative-weights argument of online learning (Agarwal et al., 2021).

The plain softmax gradient behaves very differently. The constants of its convergence can be very poor: Li, Wei, Chi, Gu and Chen (2021) exhibit MDPs where softmax policy gradient needs a time exponential in the number of states.

Example 3.5 shows two mild versions of this. The first step goes the wrong way in state 1: it lowers \pi(\text{risky} \mid 1) from 0.5 to 0.17, before the improvement of state 2 reverses the sign of the gradient.

Near the optimum, the gradient vanishes as the policy becomes deterministic. The value is 16.092 after 100 steps, but it reaches 16.101 only after 2000 steps.

The dual linear program (Proposition 1.12)

The dual program has one variable \lambda(s, a) \ge 0 per pair. Its constraints say that \lambda is (1-\gamma)^{-1} times a discounted state–action occupancy measure: optimal policies are read off its support. This dual view returns in the constrained and offline problems of ch. 10.

Explicitly, the dual is \max_{\lambda \ge 0} \sum_{s,a} \lambda(s, a)\, r(s, a) \quad \text{subject to} \quad \sum_a \lambda(s', a) - \gamma \sum_{s,a} P(s' \mid s, a)\, \lambda(s, a) = \mu(s') \ \text{ for all } s' .

Regret of UCB1 (Theorem 6.4)

The Lai–Robbins lower bound (Theorem 6.6)

The modern proof uses one information inequality (Garivier, Ménard and Stoltz, 2019). For two bandits \mu and \lambda and any random variable Z \in [0, 1] measurable with respect to the observations up to T, \sum_b \mathbb{E}_\mu[N_b(T)]\, \mathrm{kl}(\mu_b, \lambda_b) \ge \mathrm{kl}\big( \mathbb{E}_\mu[Z],\ \mathbb{E}_\lambda[Z] \big) .

The left side is the KL divergence between the laws of the observations (chain rule), and the right side follows from the data-processing inequality.

The same inequality, applied at the stopping time with Z = \mathbf{1}\{\hat a = a^\star(\mu)\}, is the transportation lemma of Theorem 8.4.

Regret of UCB-VI (Theorem 6.10)

Existence for the average-reward equation (Theorem 7.3)

10. Research directions and open problems

This self-study chapter surveys active questions that extend the course, with entry points into the literature. It is a map for choosing a project or an internship topic, not a complete review.

Reading a reinforcement learning theory paper

Before the result, locate the setting. Four questions place most papers on the map of this course:

• Criterion: discounted, episodic or average reward (ch. 1, ch. 6, ch. 7).
• Access to the environment: a generative model (ch. 8), online interaction (ch. 6), or a fixed data set (offline RL below).
• Objective: regret, sample complexity of identifying a near-optimal policy, or the convergence of an optimisation method (ch. 3).
• Type of guarantee: worst case over a class (minimax), or instance-dependent with gaps (ch. 7), and with or without function approximation.

Offline reinforcement learning

In offline RL, the agent learns from a fixed data set collected by other policies, with no further interaction; Levine, Kumar, Tucker and Fu (2020) survey the field. The difficulty is the distribution shift measured by the concentrability coefficients of ch. 4: the data say little about the actions a new policy would take.

The dominant principle is pessimism, the mirror image of the optimism of ch. 6. Conservative Q-learning (Kumar, Zhou, Tucker and Levine, 2020) penalises values outside the data. Jin, Yang and Wang (2021) and Rashidinejad, Zhu, Ma, Jiao and Russell (2021) show that pessimistic value iteration needs coverage of the optimal policy only, not of all policies.

Reinforcement learning from human preferences

When rewards are hard to write down, they can be learnt from comparisons. Christiano, Leike, Brown, Martic, Legg and Amodei (2017) fitted a reward model to human preferences between trajectory segments and optimised it with RL. Ouyang and coauthors (2022) applied the same pipeline, with PPO, to fine-tune language models.

The KL-regularised problem has a closed-form optimal policy: a Boltzmann policy, as in Proposition 5.6 with a reference policy in place of the uniform law. Rafailov and coauthors (2023) inverted this relation to write the reward through the policy, which gives direct preference optimisation, a supervised loss with no RL loop. Which of these methods is preferable, and why, is an open empirical and theoretical question.

Function approximation with guarantees

The tabular rates of ch. 6 depend on S, useless for images. In linear MDPs, P and r are linear in known features of dimension d.

Optimistic algorithms then have regret polynomial in d and H times \sqrt{T} (Jin, Yang, Wang and Jordan, 2020). Structural conditions such as low Bellman rank (Jiang, Krishnamurthy, Agarwal, Langford and Schapire, 2017) extend this to richer classes.

Negative results show the limits. If only Q^\star is linear in the features, efficient planning can be impossible: Weisz, Amortila and Szepesvári (2021) prove a lower bound exponential in the dimension or the horizon. Du, Kakade, Wang and Yang (2020) give related lower bounds for approximately good representations.

Pure exploration in MDPs and reward-free exploration

Best-policy identification extends ch. 8 to MDPs. Al Marjani, Garivier and Proutière (2021) derive instance-dependent lower bounds for identifying the best policy in a discounted MDP, and algorithms close to them. Simchowitz and Jamieson (2019) give gap-dependent regret bounds for optimistic algorithms in tabular MDPs.

In reward-free exploration, the agent explores without rewards, then must output a near-optimal policy for any reward function given afterwards. Jin, Krishnamurthy, Simchowitz and Yu (2020) introduced the problem; Kaufmann and coauthors (2021) and Ménard and coauthors (2021) give adaptive algorithms with sharper sample complexity.

Distributional and model-based deep RL

Distributional RL learns the law of the return, not only its mean, with a distributional Bellman operator that is a contraction in a Wasserstein metric (Bellemare, Dabney and Munos, 2017). Model-based deep RL learns a model for planning: MuZero (Schrittwieser and coauthors, 2020) learns a latent model and plans in it with Monte Carlo tree search.

Variants of the tree search of ch. 8, with learnt priors and values, drive AlphaGo and AlphaZero (Silver et al., 2016, 2018). For deterministic systems, optimistic planning (Hren and Munos, 2008) has a complexity governed by the branching factor of the near-optimal paths.

Open problems

• Instance-optimal algorithms beyond ergodic MDPs: constants matching Burnetas–Katehakis for communicating MDPs, or for episodic regret, with practical computation.
• Optimism or posterior sampling at scale: exploration bonuses or posterior approximations for deep networks that keep a guarantee.
• Offline-to-online: how much interaction is needed to improve on a data set, and how pessimism should give way to optimism.
• The theory of deep RL: why DQN and PPO work as well as they do despite the deadly triad and non-convexity.
• Constraints and safety: regret and identification under constraints, in the constrained MDPs of Altman (1999), whose dual is the occupancy program of ch. 9.

Exercises

Levels: ★ apply the course, ★★ combine results or prove a short statement, ★★★ open-ended or research-flavoured. Exercises 6, 14 and 17 are computational; they reuse the code of the chapters.

1. ★ Evaluating and improving a policy. In the MDP of Example 1.10, with \gamma = 0.9, compute the value of the policy (safe, safe) by solving the Bellman evaluation equation. Then perform one improvement step of policy iteration.

   Solution: in state 1, V(1) = 1 + 0.9\, V(1), so V(1) = 10. In state 2, V(2) = 2 + 0.9\,(0.2 \times 10 + 0.8\, V(2)), so 0.28\, V(2) = 3.8 and V(2) = 13.571.

   Improvement: in state 1, risky is worth 0.9 \times 13.571 = 12.214 > 10; in state 2, safe keeps 13.571 against 0.9 \times 10 = 9. The new policy is (risky, safe), which is optimal (Example 1.10).

2. ★ How many sweeps? Rewards are in [0, 1] and value iteration starts from V_0 = 0. How many sweeps guarantee \|V_k - V^\star\|_\infty \le 0.01 for \gamma = 0.9 and for \gamma = 0.99?

   Solution: \|V_0 - V^\star\|_\infty \le 1/(1 - \gamma), so it suffices that \gamma^k/(1 - \gamma) \le 0.01 (Proposition 1.8), that is k \ge \frac{\log\big(100/(1 - \gamma)\big)}{\log(1/\gamma)} . This gives k = 66 for \gamma = 0.9 and k = 917 for \gamma = 0.99: the cost grows like 1/(1 - \gamma), up to a logarithm.

3. ★ Q-learning against SARSA. The current estimates are Q(1, \text{risky}) = 2 and Q(2, \cdot) = (4, 1) for (safe, risky). The agent plays risky in state 1, receives r = 0 and lands in state 2, where its \varepsilon-greedy rule draws the exploratory action risky.

   With \alpha = 0.5 and \gamma = 0.9, give the Q-learning and the SARSA updates of Q(1, \text{risky}).

   Solution: the Q-learning target uses the maximum, 0 + 0.9 \times 4 = 3.6, so Q \leftarrow 2 + 0.5 \times 1.6 = 2.8.

   The SARSA target uses the action actually drawn, 0 + 0.9 \times 1 = 0.9, so Q \leftarrow 2 + 0.5 \times (-1.1) = 1.45. SARSA evaluates the exploring policy, Q-learning the greedy one.

4. ★ Step sizes. Which of the following step sequences satisfy the Robbins–Monro conditions of Theorem 0.6: 1/t, 1/\sqrt{t}, 1/t^2, 1/(t\log t) for t \ge 2, the constant 0.1, and t^{-0.7}?

   Solution: 1/t, 1/(t\log t) and t^{-0.7} do. The sum of 1/(t\log t) diverges like \log\log t, while its squares are summable.

   The steps 1/\sqrt{t} and 0.1 fail the second condition, since their squares are not summable: the iterates keep fluctuating. The steps 1/t^2 fail the first, so the iterates may stop before reaching the root.

5. ★ UCB indices by hand. After t = 100 rounds of a three-armed bandit, the arms have been pulled (60, 30, 10) times with empirical means (0.55, 0.50, 0.35). Which arm does UCB1 pull next?

   Solution: 2\log 100 = 9.21. The indices are 0.55 + \sqrt{9.21/60} = 0.942, 0.50 + \sqrt{9.21/30} = 1.054 and 0.35 + \sqrt{9.21/10} = 1.310.

   UCB1 pulls arm 3, the worst empirical arm, because it is the most uncertain.

6. ★ SARSA in code. Adapt the Q-learning code of ch. 2 to SARSA with \varepsilon-greedy exploration, \varepsilon = 0.1 fixed and steps N^{-0.7}, for 300 000 steps. Compare the result with Q^\star and explain the difference.

   Hints and expected result: replace the target by r + \gamma Q(s', a'), with a' drawn from the \varepsilon-greedy rule and then played. SARSA gives about [[13.57, 13.99], [15.71, 12.57]], close to the action values of the \varepsilon-greedy policy that is greedy with respect to them, [[13.61, 14.03], [15.74, 12.61]].

   These values lie about 1.1 below Q^\star = [[14.73, 15.25], [16.95, 13.73]]: with \varepsilon fixed, SARSA learns the value of exploring forever. The greedy policy is still (risky, safe).

7. ★★ Overestimation of the maximum. Let X_1, X_2 be independent \mathcal{N}(0, \sigma^2) estimates of two actions of true value 0. Compute \mathbb{E}[\max(X_1, X_2)]. With an independent second pair (Y_1, Y_2), compute the mean of the double estimator Y_{\hat a}, where \hat a = \arg\max_a X_a.

   Solution: \max(X_1, X_2) = (X_1 + X_2)/2 + |X_1 - X_2|/2. Since X_1 - X_2 \sim \mathcal{N}(0, 2\sigma^2) has mean absolute value 2\sigma/\sqrt{\pi}, the expectation is \mathbb{E}[\max(X_1, X_2)] = \frac{\sigma}{\sqrt{\pi}} \approx 0.564\, \sigma .

   The double estimator is unbiased here: given X, Y_{\hat a} has mean 0 (Proposition 5.2). When the true values differ, it can underestimate.

8. ★★ The TD fixed point with one feature. A chain moves uniformly at random between two states (P has all entries 1/2), with rewards r = (1, 0) and \gamma = 0.9. The single feature is \varphi = (1, 2). Compute V^\pi, the best approximation \Pi V^\pi, the TD fixed point, and check Theorem 4.4.

   Solution: the mean value m solves m = 0.5 + 0.9\, m, so m = 5 and V^\pi = (5.5, 4.5). The stationary law is (1/2, 1/2).

   The projection is w = (5.5 + 2 \times 4.5)/(1 + 4) = 2.9, with error \|V - \Pi V\|_d = 2.056.

   For TD, (I - \gamma P)\varphi = (-0.35, 0.65), so A = 0.475 and b = 0.5, and w_{\mathrm{TD}} = 1.053. Its error is \|V - \Phi w_{\mathrm{TD}}\|_d = 3.572 \le 2.056/\sqrt{1 - 0.81} = 4.716 .

9. ★★ Policy improvement from the performance difference. Use Lemma 3.1 to prove that if \pi' is greedy with respect to Q^\pi, then V^{\pi'} \ge V^\pi in every state, with equality everywhere only if \pi is optimal.

   Solution: apply Lemma 3.1 with \mu = \delta_s. The advantage A^\pi(x, \pi'(x)) = \max_a Q^\pi(x, a) - V^\pi(x) is non-negative in every state, so V^{\pi'}(s) \ge V^\pi(s).

   If equality holds at every s, the expectation vanishes. Since d^{\pi'}_{\delta_s}(s) \ge 1 - \gamma > 0, this forces \max_a Q^\pi(s, a) = V^\pi(s) for every s. Then T^\star V^\pi = V^\pi, and \pi is optimal by Theorem 1.7.

10. ★★ The best constant baseline. For the estimator g = (R - b)\, \nabla\log\pi(a) of a one-step problem, find the constant b that minimises \mathbb{E}\|g\|^2. Apply it to the bandit of the code of ch. 3.

    Solution: the mean of g does not depend on b, and its second moment is a quadratic in b: \mathbb{E}\|g\|^2 = \mathbb{E}\big[R^2 \|\nabla\log\pi\|^2\big] - 2b\, \mathbb{E}\big[R\, \|\nabla\log\pi\|^2\big] + b^2\, \mathbb{E}\|\nabla\log\pi\|^2 . The minimiser is b^\star = \frac{\mathbb{E}\big[ R\, \|\nabla\log\pi\|^2 \big]}{\mathbb{E}\, \|\nabla\log\pi\|^2} .

    For the uniform softmax on three arms, \|e_a - \pi\|^2 = 2/3 for every arm. So b^\star = \mathbb{E}[R] = 11.5, the value baseline used in the code.

11. ★★ The regulator and the golden ratio. Solve the scalar Riccati equation of Theorem 5.4 for a = b = q = \rho = 1 and \gamma = 1. Give the gain and the closed loop.

    Solution: the equation p = 1 + p - p^2/(1 + p) reduces to p^2 = p + 1, so p = (1 + \sqrt 5)/2 = 1.618.

    The gain is K = p/(1 + p) = 1/p = 0.618, and the closed loop is 1 - K = 1/p^2 = 0.382. The open-loop system, a = 1, is only marginally stable; feedback makes it contract by 0.382 per step.

12. ★★ Gain and bias of a two-state chain. A chain has P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix} and rewards r = (0, 1). Compute its gain, its bias with h(1) = 0, and compare with (1 - \gamma)V_\gamma for \gamma close to 1.

    Solution: the stationary law solves 0.1\, d(1) = 0.5\, d(2), so d = (5/6, 1/6) and g = 1/6. The Poisson equation in state 1 gives g = 0.1\, h(2), so h = (0, 5/3). State 2 checks: 1/6 + 5/3 = 1 + 0.5 \times 5/3.

    For \gamma = 0.99, (1 - \gamma)V_\gamma = (0.164, 0.180) and V_\gamma(2) - V_\gamma(1) = 1.656.

    For \gamma = 0.999 they are (0.1664, 0.1681) and 1.666, approaching g and h (Definition 7.2).

13. ★★ Characteristic time with unequal variances. Two Gaussian arms have variances \sigma_1^2 and \sigma_2^2 and gap \Delta. Show that the optimal weights are proportional to \sigma_1 and \sigma_2, and that T^\star = 2(\sigma_1 + \sigma_2)^2/\Delta^2.

    Evaluate the lower bound of Theorem 8.4 for \sigma_1 = 1, \sigma_2 = 2, \Delta = 0.5 and \delta = 0.01.

    Solution: the closest alternative moves both means to a common value m. Minimising over m gives \min_m \Big[ \frac{w_1(\mu_1 - m)^2}{2\sigma_1^2} + \frac{w_2(\mu_2 - m)^2}{2\sigma_2^2} \Big] = \frac{\Delta^2}{2(\sigma_1^2/w_1 + \sigma_2^2/w_2)} .

    Minimising \sigma_1^2/w_1 + \sigma_2^2/w_2 under w_1 + w_2 = 1 gives w_i \propto \sigma_i, with minimum (\sigma_1 + \sigma_2)^2.

    Numerically, T^\star = 2 \times 9/0.25 = 72, the weights are (1/3, 2/3), and \mathrm{kl}(0.01, 0.99) = 0.98 \log 99 = 4.503. The bound is \mathbb{E}[\tau_\delta] \ge 72 \times 4.503 \approx 324 .

14. ★★ UCB against \varepsilon-greedy. Simulate UCB1 and \varepsilon-greedy (\varepsilon = 0.1, greedy on empirical means) on Bernoulli arms with means (0.5, 0.4, 0.3), over 10 runs, for T = 10^4 and T = 10^5. Explain the results with Proposition 6.2.

    Hints and expected result: with seeds 0 to 9, the mean regrets are about 114 for \varepsilon-greedy against 154 for UCB1 at T = 10^4, but 1012 against 280 at T = 10^5.

    The exploration of \varepsilon-greedy pulls each suboptimal arm about \varepsilon T/3 times, a regret near 0.1 \times T \times (0.1 + 0.2)/3 = 10^{-2}\, T. UCB1 grows like \log T: it loses at small T, then wins by a growing margin.

15. ★★ The simulation lemma. Let P and \hat P be two transition kernels with the same rewards. For a stationary policy \pi, prove the identity below.

    Deduce a bound on \|V^\pi_P - V^\pi_{\hat P}\|_\infty in terms of the largest L_1 distance \varepsilon between the laws P(\cdot \mid s, a) and \hat P(\cdot \mid s, a). V^\pi_P - V^\pi_{\hat P} = \gamma\, (I - \gamma \hat P^\pi)^{-1} (P^\pi - \hat P^\pi)\, V^\pi_P

    Solution: subtract the two Bellman equations, then invert I - \gamma\hat P^\pi: V_P - V_{\hat P} = \gamma(P^\pi - \hat P^\pi) V_P + \gamma \hat P^\pi (V_P - V_{\hat P}) .

    Each entry of (P^\pi - \hat P^\pi)V_P is at most \varepsilon \|V_P\|_\infty \le \varepsilon/(1 - \gamma), and the inverse has norm 1/(1 - \gamma). Hence the bound \gamma\varepsilon/(1 - \gamma)^2.

    Plugging in an L_1 concentration bound of order \sqrt{S/N} costs a factor S and (1 - \gamma)^{-1} compared with the minimax analysis of Azar, Munos and Kappen (2013).

16. ★★★ Which arms are hardest? Show that for Gaussian arms of variance \sigma^2 the Lai–Robbins constant of arm a is 2\sigma^2/\Delta_a^2, and compare with the 8/\Delta_a^2 of UCB1 for rewards in [0, 1].

    Then, for laws \nu, \nu' on [0, 1], prove the inequality below. What does it say about Bernoulli arms? \mathrm{KL}(\nu, \nu') \ge \mathrm{kl}(\mathbb{E}\nu, \mathbb{E}\nu')

    Hints and expected result: the Gaussian KL is \Delta^2/(2\sigma^2). For Bernoulli arms, Pinsker’s inequality \mathrm{kl} \ge 2\Delta^2 shows that at most 1/(2\Delta_a^2) pulls per unit of \log T are required: the constant of UCB1 is at least 16 times too large.

    For the inequality, map X \in [0, 1] to a Bernoulli(X) variable; the image of a law is the Bernoulli law with the same mean, and KL decreases under a channel (data processing). Hence the Lai–Robbins constant over all laws on [0, 1] is at most the Bernoulli one: Bernoulli arms are the hardest of their means, and KL-UCB with the Bernoulli \mathrm{kl} is safe for all bounded rewards.

17. ★★★ UCT on a deceptive tree. Build a binary tree of depth 6 in which the left action at the root leads to a subtree of rewards 0.5, except one leaf at depth 6 with reward 1, and the right action leads to leaves of reward 0.6. Implement UCT (Algorithm 8.8) and uniform Monte Carlo sampling, and plot the simple regret against the number of simulations. How does the exploration constant change the picture?

    Hints and expected result: with random rollouts, the left subtree looks worse on average, so UCT first concentrates on the right branch. It finds the deep optimal leaf only after a number of simulations that grows quickly with the depth; this is the phenomenon of Coquelin and Munos (2007). A larger exploration constant helps on this tree and hurts on others; there is no free lunch for tree search.

18. ★★★ Instance-dependent regret in episodic MDPs. Read Simchowitz and Jamieson (2019). Express their gap-dependent bound with the gaps Q^\star_h(s, \pi^\star(s)) - Q^\star_h(s, a), and compare it with Proposition 7.8. Which part of the Burnetas–Katehakis constant of Theorem 7.9 has no counterpart, and why is an exact episodic constant still open?

    Hints and expected result: the episodic analogue of Proposition 7.8 writes the regret as an expected sum of gaps along the visited pairs. Gap-dependent bounds then scale like a sum over pairs of \log T divided by the gap, times a power of H.

    The Burnetas–Katehakis constant uses KL projections of the transition laws at each pair. In episodic MDPs, states that the optimal policy rarely visits complicate the change of measure, which is part of why matching upper and lower bounds remain open (ch. 10).

Projects and assessment

The official assessment, per master-mva.com, is one written exam after class 8 and one programming assignment after class 5; no weights are displayed. The Université Paris-Saclay course detail classifies the assessment as “Evaluation Continue non Intégrale”. The content of the programming assignment is not published.

The solo subjects below are sized like such an assignment and use ch. 1–5, except one paper study on ch. 8. The group subjects are longer paper studies in the MVA tradition. The written exam is a proposal for self-testing; none of these proposals is official material.

Solo projects

1. [Solo · ≈ 20 h] Deep Q-learning on a self-written cart-pole. Implement the cart-pole dynamics of Barto, Sutton and Anderson (1983) in NumPy, then DQN (Algorithm 5.1) and Double DQN (van Hasselt, Guez and Silver, 2016) in PyTorch, on a CPU.
   • Question: how large is the overestimation of DQN, and does the double estimator remove it?
   • Success criterion: an average return of at least 195 over 100 consecutive episodes capped at 200 steps, and a plot of the predicted value at the start state against the Monte Carlo return, for both methods and 5 seeds.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters 2, 4, 5.
2. [Solo · ≈ 20 h] Off-policy divergence and gradient-TD: a paper study. Study Sutton, Maei, Precup, Bhatnagar, Silver, Szepesvári and Wiewiora (2009), and Baird (1995).
   • Implement: linear TD(0), GTD2 and TDC with linear features, on Baird’s seven-state star and on Example 4.7.
   • Success criterion: a figure of the projected Bellman error \|\Pi T^\pi V_w - V_w\|_d against the number of updates, with TD diverging and TDC converging, and a short proof that Example 4.7 diverges exactly when \gamma > 1/2.
   • Deliverables: code, report, talk. Chapters 2, 4.
3. [Solo · ≈ 15 h] Track-and-Stop: a paper study. Study Garivier and Kaufmann (2016) and implement Track-and-Stop with the GLR stopping rule (Definition 8.5) for Bernoulli arms.
   • Experiments: the four arms of ch. 8 and one instance of the paper, for \delta \in \{0.1, 0.01, 0.001\}, 500 runs each, against successive elimination (Algorithm 8.2).
   • Success criterion: the empirical error rate stays below \delta, and \mathbb{E}[\tau_\delta]/\log(1/\delta) approaches T^\star(\mu) as \delta decreases.
   • Deliverables: code, report, talk. Chapter 8.

Group projects

1. [Group of 2–3 · ≈ 30 h each] Minimax regret in tabular RL: optimism against posterior sampling. Study Azar, Osband and Munos (2017) and Osband, Russo and Van Roy (2013).
   • Work split: one member implements UCB-VI with Hoeffding and Bernstein bonuses (Algorithm 6.8); one implements PSRL with Dirichlet posteriors; one builds the environments (the river chain of ch. 6 with 6 to 20 states, random MDPs) and the evaluation, with seeds and confidence bands.
   • Success criterion: log–log plots of regret against the number of episodes, with slope close to 1/2 once the regime is reached, and a measured dependence on S compared with Theorem 6.10.
   • Deliverables: code, a 6-page report, a 15-minute talk. Chapters 1, 6, 9.
2. [Group of 2–3 · ≈ 30 h each] Average-reward learning: UCRL2, KL-UCRL and instance optimality. Study Jaksch, Ortner and Auer (2010), Filippi, Cappé and Garivier (2010) and Burnetas and Katehakis (1997).
   • Work split: one member implements extended value iteration and UCRL2; one replaces the L_1 balls by KL balls; one computes the constant C(M) of Theorem 7.9 for small ergodic MDPs.
   • Success criterion: regret curves up to T = 10^6 on an ergodic variant of the river chain, showing the logarithmic regime, compared with C(M)\log T; an honest discussion of the gap.
   • Deliverables: code, report, talk. Chapters 6, 7, 9.
3. [Group of 2–3 · ≈ 30 h each] Planning with a simulator. Study Kearns, Mansour and Ng (2002), Kocsis and Szepesvári (2006) and Jonsson, Kaufmann, Ménard, Darwiche Domingues, Leurent and Valko (2020).
   • Work split: one member implements sparse sampling and uniform Monte Carlo; one implements UCT and studies its exploration constant on the deceptive trees of Exercise 17; one implements MDP-GapE.
   • Success criterion: simple regret against the number of simulator calls on random MDPs with 2 to 4 actions and \gamma = 0.9, with confidence bands, and the empirical correctness rate of MDP-GapE at \delta = 0.1.
   • Deliverables: code, report, talk. Chapters 1, 6, 8.

Written exam (proposal)

Format: 2 h 30, one handwritten A4 sheet allowed, no electronic device; four independent exercises.

1. Course question (5 points). Define the Bellman optimality operator T^\star and prove that it is a \gamma-contraction in the sup norm. Prove that a greedy policy with respect to its fixed point is optimal among stationary policies. State the loss of a greedy policy with respect to an approximation V of V^\star.

   Expected: Definition 1.5; Proposition 1.6 with |\max f - \max g| \le \max|f - g|; Step 1 of Theorem 1.7; Proposition 1.8, with the bound 2\gamma\|V - V^\star\|_\infty/(1 - \gamma).

2. Computation (5 points). In state 1, action a gives reward 0 and leads to state 2, and action b gives reward 0.5 and stays. State 2 has a single action, with reward 1, staying with probability 0.5 and returning to state 1 otherwise. Take \gamma = 0.8.

   (a) Evaluate the two deterministic policies. (b) Give two sweeps of value iteration from V_0 = 0 and the greedy actions. (c) With Q(1, a) = 1, \max_{a'} Q(2, a') = 2 and \alpha = 0.5, give the Q-learning update after the transition (1, a, 0, 2).

   Expected: (a) with a: V(2) = 1/0.28 = 3.571 and V(1) = 2.857; with b: V(1) = 2.5 and V(2) = 3.333.

   So a is optimal, and it is greedy with respect to its own value (2.857 > 0.5 + 0.8 \times 2.857 = 2.786).

   (b) V_1 = (0.5, 1), then V_2 = (0.9, 1.6), with b still greedy in state 1 after two sweeps. (c) The target is 0.8 \times 2 = 1.6, so Q(1, a) = 1.3.

3. Short proof (5 points). Prove the performance difference lemma. Deduce the policy gradient theorem for the tabular softmax: \frac{\partial J}{\partial\theta_{s,a}} = \frac{1}{1 - \gamma}\, d^{\pi_\theta}_\mu(s)\, \pi_\theta(a \mid s)\, A^{\pi_\theta}(s, a) .

   Expected: the telescoping sum of Lemma 3.1. Then either the unrolled Bellman equation of Theorem 3.4, or the first-order expansion of Lemma 3.1 with \pi' = \pi_{\theta + h}, followed by the softmax score \mathbf{1}_{a=b} - \pi(b \mid s).

4. Problem (5 points). Bernoulli bandit with means (0.9, 0.8).

   (a) Prove the regret decomposition. (b) State the Lai–Robbins bound and compute its constant. (c) Compare with the bound of Theorem 6.4 at T = 10^4. (d) Explain in two sentences why identifying the best arm calls for a different sampling rule than minimising regret.

   Expected: (a) Proposition 6.2. (b) \mathrm{kl}(0.8, 0.9) = 0.0444, so the regret is at least (0.1/0.0444)\log T = 2.25\log T, about 20.7 at T = 10^4.

   (c) Theorem 6.4 gives about 80 \log T + 0.43 \approx 737, a factor 35 above. (d) Regret penalises every pull of the worse arm, so it pulls it only O(\log T) times. Identification needs both means precisely: for these two arms the optimal weights of Theorem 8.4 are about (0.52, 0.48), so it samples them almost equally.

Grading rubric (proposal)

References

Official references

The course page on master-mva.com lists no references for this course. The lists below give standard textbooks and the works cited on this page.

Textbooks

• E. Altman. Constrained Markov Decision Processes. Chapman & Hall/CRC, 1999.
• D. P. Bertsekas. Dynamic Programming and Optimal Control, vol. I, 4th edition. Athena Scientific, 2017.
• D. P. Bertsekas and S. E. Shreve. Stochastic Optimal Control: The Discrete-Time Case. Academic Press, 1978.
• D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
• S. Boucheron, G. Lugosi and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
• O. Hernández-Lerma and J. B. Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria. Springer, 1996.
• H. J. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applications, 2nd edition. Springer, 2003.
• T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
• D. A. Levin and Y. Peres. Markov Chains and Mixing Times, 2nd edition. American Mathematical Society, 2017.
• M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
• R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction, 2nd edition. MIT Press, 2018.
• C. Szepesvári. Algorithms for Reinforcement Learning. Morgan & Claypool, 2010.

Dynamic programming and the first algorithms (ch. 0–2)

• M. G. Azar, R. Munos and H. J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning 91(3), 2013.
• E. Even-Dar and Y. Mansour. Learning rates for Q-learning. Journal of Machine Learning Research 5, 2003.
• T. Jaakkola, M. I. Jordan and S. P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation 6(6), 1994.
• H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics 22(3), 1951.
• S. Singh, T. Jaakkola, M. L. Littman and C. Szepesvári. Convergence results for single-step on-policy reinforcement-learning algorithms. Machine Learning 38, 2000.
• S. P. Singh and R. C. Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning 16, 1994.
• A. L. Strehl and M. L. Littman. An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences 74(8), 2008.
• J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning 16, 1994.
• H. van Hasselt. Double Q-learning. Advances in Neural Information Processing Systems 23, 2010.
• C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, University of Cambridge, 1989.
• C. J. C. H. Watkins and P. Dayan. Q-learning. Machine Learning 8, 1992.
• Y. Ye. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research 36(4), 2011.

Actors and critics (ch. 3–4)

• A. Agarwal, S. M. Kakade, J. D. Lee and G. Mahajan. On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22, 2021.
• L. Baird. Residual algorithms: reinforcement learning with function approximation. Proceedings of the 12th International Conference on Machine Learning (ICML), 1995.
• S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning 22, 1996.
• D. Ernst, P. Geurts and L. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6, 2005.
• S. M. Kakade. A natural policy gradient. Advances in Neural Information Processing Systems 14, 2001.
• S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. Proceedings of the 19th International Conference on Machine Learning (ICML), 2002.
• V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. Advances in Neural Information Processing Systems 12, 2000.
• M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal of Machine Learning Research 4, 2003.
• G. Li, Y. Wei, Y. Chi, Y. Gu and Y. Chen. Softmax policy gradient methods can take exponential time to converge. Proceedings of the 34th Conference on Learning Theory (COLT), 2021.
• J. Mei, C. Xiao, C. Szepesvári and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
• R. Munos. Performance bounds in L_p-norm for approximate value iteration. SIAM Journal on Control and Optimization 46(2), 2007.
• R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research 9, 2008.
• J. Schulman, S. Levine, P. Abbeel, M. Jordan and P. Moritz. Trust region policy optimization. Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
• J. Schulman, F. Wolski, P. Dhariwal, A. Radford and O. Klimov. Proximal policy optimization algorithms. arXiv:1707.06347, 2017.
• R. S. Sutton, D. McAllester, S. Singh and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems 12, 2000.
• R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári and E. Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. Proceedings of the 26th International Conference on Machine Learning (ICML), 2009.
• J. N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control 42(5), 1997.
• R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8, 1992.

Deep RL and continuous control (ch. 5)

• A. G. Barto, R. S. Sutton and C. W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics 13(5), 1983.
• S. Fujimoto, H. van Hoof and D. Meger. Addressing function approximation error in actor-critic methods. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
• T. Haarnoja, A. Zhou, P. Abbeel and S. Levine. Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
• T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver and D. Wierstra. Continuous control with deep reinforcement learning. International Conference on Learning Representations (ICLR), 2016.
• V. Mnih et al. Human-level control through deep reinforcement learning. Nature 518, 2015.
• J. Schulman, P. Moritz, S. Levine, M. Jordan and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. International Conference on Learning Representations (ICLR), 2016.
• D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra and M. Riedmiller. Deterministic policy gradient algorithms. Proceedings of the 31st International Conference on Machine Learning (ICML), 2014.
• H. van Hasselt, A. Guez and D. Silver. Deep reinforcement learning with double Q-learning. Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016.

Exploration, regret and average reward (ch. 6–7)

• S. Agrawal and N. Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. Proceedings of the 25th Conference on Learning Theory (COLT), 2012.
• S. Agrawal and N. Goyal. Further optimal regret bounds for Thompson sampling. Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS), 2013.
• P. Auer, N. Cesa-Bianchi and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 2002.
• M. G. Azar, I. Osband and R. Munos. Minimax regret bounds for reinforcement learning. Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
• P. L. Bartlett and A. Tewari. REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), 2009.
• A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for Markov decision processes. Mathematics of Operations Research 22(1), 1997.
• O. Cappé, A. Garivier, O.-A. Maillard, R. Munos and G. Stoltz. Kullback–Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics 41(3), 2013.
• O. D. Domingues, P. Ménard, E. Kaufmann and M. Valko. Episodic reinforcement learning in finite MDPs: minimax lower bounds revisited. Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021.
• S. Filippi, O. Cappé and A. Garivier. Optimism in reinforcement learning and Kullback–Leibler divergence. Proceedings of the 48th Allerton Conference on Communication, Control, and Computing, 2010.
• A. Garivier and O. Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. Proceedings of the 24th Conference on Learning Theory (COLT), 2011.
• A. Garivier, P. Ménard and G. Stoltz. Explore first, exploit next: the true shape of regret in bandit problems. Mathematics of Operations Research 44(2), 2019.
• J. Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. Journal of Machine Learning Research 16, 2015.
• T. Jaksch, R. Ortner and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11, 2010.
• E. Kaufmann, N. Korda and R. Munos. Thompson sampling: an asymptotically optimal finite-time analysis. Proceedings of the 23rd International Conference on Algorithmic Learning Theory (ALT), 2012.
• T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 1985.
• I. Osband, D. Russo and B. Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems 26, 2013.
• F. Pesquerel and O.-A. Maillard. IMED-RL: regret optimal learning of ergodic Markov decision processes. Advances in Neural Information Processing Systems 35, 2022.
• A. Tewari and P. L. Bartlett. Optimistic linear programming gives logarithmic regret for irreducible MDPs. Advances in Neural Information Processing Systems 20, 2007.
• W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3–4), 1933.

Pure exploration and planning (ch. 8)

• P.-A. Coquelin and R. Munos. Bandit algorithms for tree search. Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI), 2007.
• E. Even-Dar, S. Mannor and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research 7, 2006.
• A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
• J.-F. Hren and R. Munos. Optimistic planning of deterministic systems. European Workshop on Reinforcement Learning (EWRL), Lecture Notes in Computer Science 5323, Springer, 2008.
• A. Jonsson, E. Kaufmann, P. Ménard, O. Darwiche Domingues, E. Leurent and M. Valko. Planning in Markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems 33, 2020.
• E. Kaufmann, O. Cappé and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research 17, 2016.
• M. Kearns, Y. Mansour and A. Y. Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine Learning 49, 2002.
• L. Kocsis and C. Szepesvári. Bandit based Monte-Carlo planning. Proceedings of the 17th European Conference on Machine Learning (ECML), 2006.
• D. Silver et al. Mastering the game of Go with deep neural networks and tree search. Nature 529, 2016.
• D. Silver et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 2018.

Research directions (ch. 10)

• A. Al Marjani, A. Garivier and A. Proutière. Navigating to the best policy in Markov decision processes. Advances in Neural Information Processing Systems 34, 2021.
• M. G. Bellemare, W. Dabney and R. Munos. A distributional perspective on reinforcement learning. Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
• P. F. Christiano, J. Leike, T. B. Brown, M. Martic, S. Legg and D. Amodei. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems 30, 2017.
• S. S. Du, S. M. Kakade, R. Wang and L. F. Yang. Is a good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations (ICLR), 2020.
• N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
• C. Jin, A. Krishnamurthy, M. Simchowitz and T. Yu. Reward-free exploration for reinforcement learning. Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
• C. Jin, Z. Yang, Z. Wang and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. Proceedings of the 33rd Conference on Learning Theory (COLT), 2020.
• Y. Jin, Z. Yang and Z. Wang. Is pessimism provably efficient for offline RL? Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
• E. Kaufmann, P. Ménard, O. Darwiche Domingues, A. Jonsson, E. Leurent and M. Valko. Adaptive reward-free exploration. Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021.
• A. Kumar, A. Zhou, G. Tucker and S. Levine. Conservative Q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems 33, 2020.
• S. Levine, A. Kumar, G. Tucker and J. Fu. Offline reinforcement learning: tutorial, review, and perspectives on open problems. arXiv:2005.01643, 2020.
• P. Ménard, O. Darwiche Domingues, A. Jonsson, E. Kaufmann, E. Leurent and M. Valko. Fast active learning for pure exploration in reinforcement learning. Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
• L. Ouyang et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35, 2022.
• R. Rafailov, A. Sharma, E. Mitchell, S. Ermon, C. D. Manning and C. Finn. Direct preference optimization: your language model is secretly a reward model. Advances in Neural Information Processing Systems 36, 2023.
• P. Rashidinejad, B. Zhu, C. Ma, J. Jiao and S. Russell. Bridging offline reinforcement learning and imitation learning: a tale of pessimism. Advances in Neural Information Processing Systems 34, 2021.
• J. Schrittwieser et al. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature 588, 2020.
• M. Simchowitz and K. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. Advances in Neural Information Processing Systems 32, 2019.
• G. Weisz, P. Amortila and C. Szepesvári. Exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions. Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021.