Sequential Learning

Contents

• Introduction and overview
• 0. Review: convexity, concentration and divergences
• 1. The online protocol and the notion of regret
• 2. Prediction with expert advice: exponential weights
• 3. Online convex optimization and stochastic optimization
• 4. Adversarial bandits
• 5. Stochastic bandits
• 6. Games and no-regret dynamics
• 7. Blackwell approachability and calibration
• 8. Partial monitoring
• 9. Complements: lower bounds, adaptivity and structured bandits
• 10. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with an M1 in mathematics, computer science or physics who knows basic probability and convex optimization, and who wants to learn how to decide well when the data arrive one at a time and may be chosen by an adversary.

Empirical first: on 10,000 rounds of two alternating losses, the natural rule “follow the leader” loses 5,000 more than the best fixed choice, while exponential weights lose only 30 more (block of ch. 2). A forecaster of binary events that is deterministic can be pushed to a calibration error above 0.5. A randomized one stays below 0.002 against the same adaptive opponent (block of ch. 7). This course explains both numbers.

Sequential learning studies algorithms that receive data on the fly, act, observe a feedback and update themselves before the next round, with no statistical assumption on the data. Their quality is the regret: the gap between their cumulative loss and that of the best fixed decision in hindsight. The course builds the main algorithms (exponential weights, online gradient descent, EXP3, UCB), proves their regret bounds and matching lower bounds, and connects them with stochastic optimization, game theory, calibration and partial monitoring.

The bandit chapters meet the exploration–exploitation lectures of Reinforcement Learning, and the online-to-batch conversion reconnects with Convex Optimization and Applications in Machine Learning and the stochastic gradient algorithm of Computational Statistics. Stopping Times and Online Algorithms also treats data one at a time, but measures algorithms by a competitive ratio against an omniscient benchmark rather than by a regret.

What you will be able to do

• Formalize an online problem (spam filtering, ad selection, repeated auctions, aggregation of forecasters) as a game between a learner and an environment, with its loss and its feedback.
• Define external, swap and pseudo-regret, and explain why deterministic algorithms fail against adversaries.
• Derive the regret bound of exponential weights by the potential method, tune its learning rate, and prove a matching lower bound.
• Analyse online gradient descent and follow-the-regularized-leader, and turn any regret bound into a stochastic optimization rate by online-to-batch conversion.
• Build unbiased loss estimators from bandit feedback, prove the regret of EXP3, and explain the price of partial information.
• Prove the logarithmic regret of UCB for stochastic bandits, state the Lai–Robbins lower bound, and run Thompson sampling.
• Prove the minimax theorem with no-regret dynamics, compute approximate equilibria by self-play, and convert external regret into swap regret.
• State and prove Blackwell’s approachability theorem and derive regret matching from it.
• Define calibration, show that deterministic forecasters cannot be calibrated, and build a randomized calibrated forecaster.
• Model partial-monitoring games, prove a regret bound of order T^{2/3} for a revealing-action game, and state the classification of finite games.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com explains that in online learning, data are acquired and treated on the fly, feedbacks are received and algorithms are updated on the fly. It lists applications coming from the internet: choosing which ads to display, repeated auctions, spam detection, and the aggregation of experts or algorithms, together with boosting.

The stated objective is to introduce and study the main concepts of online learning (regret, calibration and others), to construct algorithms and to show the connection with game theory. The course also covers the bandit setting, with a pointer to the Reinforcement Learning course, and its generalization, partial monitoring. It is organised as six classes on the blackboard. The Université Paris-Saclay course detail displays only the nature of the assessment.

Extensions beyond the syllabus: the change-of-measure proof of the Lai–Robbins bound, small-loss bounds, linear and contextual bandits and best-arm identification (ch. 9), and the research chapter (ch. 10), both in self-study.

Where this course fits in the programme

Official prerequisites: “Probability and Optimization Notion.” In practice the proofs use convexity, subgradients, Hoeffding’s inequality and martingale differences at M1 level, recalled in ch. 0.

• Refreshers — Probability and Statistics (its chapters on concentration inequalities and on martingales), Linear Algebra, Analysis and Optimization (convexity, strong convexity, stochastic gradient) and Scientific Python (NumPy and SciPy for every block).
• Semester 1 courses that prepare it — Convex Optimization and Applications in Machine Learning (subgradients, duality, linear programming), Introduction to Statistical Learning (risk, aggregation and ensemble methods) and Computational Statistics (the stochastic gradient algorithm).
• Related courses of semester 2 — Reinforcement Learning, to which the official description points for bandits; Stopping Times and Online Algorithms (competitive ratio instead of regret); Graphs in Machine Learning (its official programme lists graph bandits and adaptive online learning with graphs); Bayesian Machine Learning (posterior distributions, which Thompson sampling samples from).
• After the course — the Research Internship; the open problems of ch. 10 are typical internship subjects in learning theory.

Course outline

• Review: convexity, concentration and divergences — subgradients, projections, Hoeffding’s lemma, the Azuma–Hoeffding inequality, Kullback–Leibler divergence.
• The online protocol and the notion of regret — the game between learner and environment, examples, regret, why determinism fails, the halving algorithm, the failure of follow-the-leader.
• Prediction with expert advice: exponential weights — the potential proof, randomized play, high probability, anytime tuning, the lower bound, exp-concave losses.
• Online convex optimization and stochastic optimization — online gradient descent, strongly convex losses, follow-the-regularized-leader, online-to-batch conversion.
• Adversarial bandits — importance weighting, EXP3 and its bound, the minimax lower bound.
• Stochastic bandits — the regret decomposition, UCB and its proof, the Lai–Robbins bound, Thompson sampling.
• Games and no-regret dynamics — the minimax theorem by regret, boosting as a game, correlated equilibria and swap regret.
• Blackwell approachability and calibration — vector payoffs, Blackwell’s theorem, regret matching, calibrated forecasting.
• Partial monitoring — loss and feedback matrices, the revealing-action game and its rate, the classification of finite games.
• Complements: lower bounds, adaptivity and structured bandits — change of measure, small-loss bounds, linear and contextual bandits, best-arm identification (self-study).
• Research directions and open problems — best of both worlds, learning in games, calibration rates, partial monitoring (self-study).

Session plan

18 h in class = 6 sessions of 3 h.

The volume is the 18 h of lectures of the Université Paris-Saclay programme table, and master-mva.com announces six classes on the blackboard, so one session of 3 h per class is the natural split. The content of each session below is a proposal.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material; the level never decreases.

Self-study, outside the 18 h (about 8 h in total): ch. 9 Complements: lower bounds, adaptivity and structured bandits (≈ 4 h, with Ex. 18) · ch. 10 Research directions and open problems (≈ 2 h, with Ex. 19) · running and modifying the Python blocks of chapters 2 to 8 (≈ 2 h).

How to study this module

• Read ch. 0 before session 1: Hoeffding’s lemma and the projection inequality are used in almost every proof of the course.
• For every algorithm, ask the same three questions: what is the benchmark, what does the learner observe, and which sequence makes it fail.
• Redo the central proofs on paper after each session (Theorems 2.2, 3.2, 4.4, 5.3, 6.2, 7.2 and 8.2): they are short, and the exam proposal asks for some of them.
• Run each Python block and change one parameter: the horizon, the number of arms, the learning rate.
• The environment is NumPy and SciPy (linprog computes the values of games); nothing else is needed.
• Do the ★ exercises the week of the session, the ★★ proofs before the exam, and keep the ★★★ exercises and ch. 9–10 for the projects.

0. Review: convexity, concentration and divergences

Every regret bound of the course combines three tools: an inequality of convexity, a bound on an exponential moment, and a divergence between probability vectors. This chapter recalls them at M1 level, with short proofs.

0.1 Convex functions and projections

0.2 Exponential moments and concentration

0.3 The simplex and the Kullback–Leibler divergence

The formula explains why exponential weights (ch. 2) are the regularized leader with an entropic penalty (ch. 3.2).

1. The online protocol and the notion of regret

Online learning replaces a fixed data set by a game repeated over time between a learner and an environment. This chapter states the protocol, defines the regret, and shows why the learner needs randomization or convexity.

1.1 The protocol

No statistical assumption is made on the sequence of losses. The applications of the course description fit this protocol.

• Spam detection: x_t is a weight vector, the email has features z_t and label y_t \in \{-1, 1\}, and the logistic loss \ell_t(x) = \ln(1 + e^{-y_t \langle x, z_t \rangle}) is revealed with the label (ch. 3).
• Ad selection: x_t is one of N ads, and only the click on the displayed ad is observed: bandit feedback (ch. 4 and 5).
• Repeated auctions: x_t is a bid; depending on the format, the bidder sees all bids or only whether she won (ch. 6.3 and 8.1).
• Aggregation of experts: x_t is a vector of weights on N forecasters, for example models of electricity consumption (ch. 2).

The benchmark is the best fixed decision in hindsight, not the best sequence of decisions: against the best sequence no guarantee is possible, since the environment can make every action of the learner the worst one.

1.2 Why determinism fails

Two remedies are used throughout the course. A randomized learner predicts 1 with probability p_t, and its expected loss |p_t - y_t| is linear in p_t. A convex problem lets the learner average the experts’ advice instead of choosing one.

1.3 Follow the leader can fail

The simplest rule plays the decision with the smallest cumulative loss so far: x_t \in \operatorname*{arg\,min}_{x \in \mathcal{X}} \sum_{s < t} \ell_s(x) .

The leader jumps because nothing slows it down. Chapters 2 and 3 add a regularization that makes the decision move slowly, and this stability is what bounds the regret.

1.4 A map of feedback models

2. Prediction with expert advice: exponential weights

A learner must combine the advice of N experts whose losses are revealed after each round. This chapter builds the exponentially weighted average forecaster, proves its \sqrt{T \ln N} regret, and shows that this rate cannot be improved.

2.1 The forecaster and its regret

At each round, expert i suffers a loss \ell_t(i) \in [0, 1]. The learner plays a weight vector p_t \in \Delta_N and suffers the mixed loss \langle p_t, \ell_t \rangle. Write the cumulative losses as L_t(i) = \sum_{s \leq t} \ell_s(i) .

With N = 100 experts and T = 10{,}000 rounds, the bound is \sqrt{5000 \times \ln 100} \approx 151.7, an average excess loss of 0.015 per round.

This is the aggregation of experts of the course description: the experts can be whole learning algorithms, such as forecasting models of electricity load.

2.2 Randomized play and high probability

With a finite set of actions and no convexity, the learner draws I_t from p_t (Hedge). Against an oblivious environment, the expected regret obeys Theorem 2.2. Against an adaptive one, the realized regret is controlled as follows.

The next lemma replaces Hoeffding’s lemma when the losses are non-negative but unbounded. It is the engine of the bandit algorithms of ch. 4 and 8.

2.3 Not knowing the horizon

A decreasing rate \eta_t proportional to \sqrt{\ln N / t} also works without restarts, with a similar constant (Cesa-Bianchi and Lugosi, 2006, ch. 2).

2.4 The rate cannot be improved

So some sequence forces a regret of order \sqrt{T}. With N experts and random losses, the minimax regret is equivalent to \sqrt{(T/2) \ln N} when T and then N go to infinity (Cesa-Bianchi and Lugosi, 2006, ch. 3): the constant of Theorem 2.2 is optimal.

2.5 Exp-concave losses

Two examples matter. The logarithmic loss of probability forecasts is 1-exp-concave, and EWA with \eta = 1 is then the Bayesian mixture: regret at most \ln N. The square loss on [0, 1] is 1/2-exp-concave, which gives regret at most 2 \ln N.

The block compares follow-the-leader and EWA on the unstable sequence of Example 1.5 and on 50 stochastic experts.

import numpy as np
rng = np.random.default_rng(0)

def ewa_regret(losses, eta):
    """Exponentially weighted average forecaster; losses has shape (T, N)."""
    L, total = np.zeros(losses.shape[1]), 0.0     # cumulative losses of the experts
    for l in losses:
        w = np.exp(-eta * (L - L.min()))          # shift for numerical stability
        total += (w / w.sum()) @ l
        L += l
    return total - L.min()                        # regret against the best expert

def ftl_regret(losses):
    L, total = np.zeros(losses.shape[1]), 0.0
    for l in losses:
        total += l[np.argmin(L)]                  # follow the current leader
        L += l
    return total - L.min()

T = 10_000
# Adversarial for FTL: (1/2, 0), then (0, 1), (1, 0), (0, 1), ...
adv = np.array([[0.5, 0.0]] + [[0.0, 1.0] if t % 2 == 0 else [1.0, 0.0]
                               for t in range(T - 1)])
# Stochastic: 50 experts with Bernoulli losses of means 0.40, ..., 0.60
sto = (rng.random((T, 50)) < np.linspace(0.4, 0.6, 50)).astype(float)

for name, X in [("adversarial, N = 2", adv), ("stochastic, N = 50", sto)]:
    N = X.shape[1]
    eta = np.sqrt(8 * np.log(N) / T)              # tuning of Theorem 2.2
    bound = np.sqrt(T / 2 * np.log(N))
    print(f"{name}: FTL {ftl_regret(X):7.1f} | EWA {ewa_regret(X, eta):6.1f}"
          f" | bound {bound:5.1f}")

On the unstable sequence, follow-the-leader has regret 5000.0, exactly T/2, and EWA has regret 29.7, below its bound 58.9. On the stochastic experts both have regret near 112, below the bound 139.9: when the data are benign, the leader is stable and regularization costs little.

3. Online convex optimization and stochastic optimization

When the decision is a vector and the losses are convex, gradient steps replace the weights on experts. This chapter proves the regret of online gradient descent, unifies it with exponential weights through regularization, and turns regret bounds into rates for stochastic optimization.

3.1 Online gradient descent

Let K \subset \mathbb{R}^d be closed and convex with diameter D, and let the losses f_t be convex on K with subgradients of norm at most G.

3.2 Follow the regularized leader

Two regularizers recover the algorithms seen so far.

• Half the squared Euclidean norm on \mathbb{R}^d gives x_t = -\eta \sum_{s<t} g_s, a gradient descent that never forgets.
• The negative entropy on the simplex gives weights proportional to e^{-\eta \sum_{s<t} g_s(i)}, by Proposition 0.7: exponential weights are FTRL with an entropic regularizer.

On the simplex with losses in [0, 1], the entropy is 1-strongly convex for the \ell_1 norm (Pinsker’s inequality) and has range \ln N. Theorem 3.5 gives a regret of order \sqrt{T \ln N}. The squared Euclidean norm gives \sqrt{N T} instead, because the gradients have Euclidean norm up to \sqrt{N}. The geometry of the regularizer matters: this is the idea of mirror descent (Shalev-Shwartz, 2012; Hazan, 2016).

3.3 From online to batch: stochastic optimization

The same algorithm thus has an adversarial guarantee and a statistical one. The logarithm of the strongly convex rate can be removed by averaging only the last iterates (Rakhlin, Shamir and Sridharan, 2012). The block runs OGD on a synthetic spam-filtering task with the logistic loss, on the ball of radius 5.

import numpy as np
rng = np.random.default_rng(1)
T, d, r = 5000, 20, 5.0                    # rounds, features, radius of the ball K
w_star = rng.normal(size=d); w_star *= 3 / np.linalg.norm(w_star)

def sample(n):                             # features z, label y = +1 (spam) or -1
    z = rng.normal(size=(n, d)) * 2 / np.sqrt(d)
    y = np.where(rng.random(n) < 1 / (1 + np.exp(-z @ w_star)), 1, -1)
    return z, y

def loss(w, z, y):  return np.logaddexp(0, -y * (z @ w))
def grad(w, z, y):  return -(y / (1 + np.exp(y * (z @ w))))[..., None] * z
def proj(w):        return w * min(1, r / np.linalg.norm(w))

Z, Y = sample(T)
G, D = np.linalg.norm(Z, axis=1).max(), 2 * r   # gradient bound, diameter of K
w, w_bar, total = np.zeros(d), np.zeros(d), 0.0
for t in range(T):
    total += loss(w, Z[t], Y[t])
    w_bar += (w - w_bar) / (t + 1)              # running average (online-to-batch)
    w = proj(w - D / (G * np.sqrt(t + 1)) * grad(w, Z[t], Y[t]))

u = np.zeros(d)                                 # best fixed vector in hindsight
for _ in range(2000):
    u = proj(u - 2.0 * grad(u, Z, Y).mean(axis=0))
regret = total - loss(u, Z, Y).sum()
print(f"regret {regret:.1f}  bound 1.5*D*G*sqrt(T) = {1.5 * D * G * np.sqrt(T):.0f}"
      f"  regret/T = {regret / T:.4f}")

Zt, Yt = sample(200_000)                        # fresh data: population risk
print(f"risk of averaged iterate {loss(w_bar, Zt, Yt).mean():.4f}, "
      f"of u {loss(u, Zt, Yt).mean():.4f}, of w* {loss(w_star, Zt, Yt).mean():.4f}")

The regret is 127.6, far below the worst-case bound 3498, that is 0.026 per email. On fresh data, the averaged iterate has logistic risk 0.5523, against 0.5518 for the best vector in hindsight and 0.5489 for the true parameter.

4. Adversarial bandits

In ad selection, the learner sees whether the displayed ad was clicked, and nothing about the others. This chapter shows how exponential weights survive this loss of information, and what it costs.

4.1 Estimating what was not observed

The protocol is that of ch. 2, with an oblivious environment: at round t the learner draws an arm I_t from p_t, suffers \ell_t(I_t) \in [0, 1] and observes only this number. The benchmark is the pseudo-regret \bar R_T = \mathbb{E}\Big[ \sum_{t=1}^T \ell_t(I_t) \Big] - \min_{i} \sum_{t=1}^T \ell_t(i) .

The estimator is unbiased, but its variance blows up when p_t(i) is small; the weighting by p_t in the regret bound exactly compensates.

4.2 EXP3

With N = 10 arms and T = 50{,}000 rounds, the bandit bound is about 1517, against 240 for full information. The price of seeing a single loss is a factor \frac{\sqrt{2 N T \ln N}}{\sqrt{(T/2) \ln N}} = \sqrt{4 N} \approx 6.3 .

4.3 The lower bound

The \sqrt{\ln N} gap between Theorems 4.4 and 4.5 is closed by FTRL with other regularizers (Audibert and Bubeck, 2009; Zimmert and Seldin, 2021). EXP3 controls the expected regret only; high-probability versions add implicit exploration (Neu, 2015).

import numpy as np
rng = np.random.default_rng(2)
T, N = 50_000, 10
# Oblivious adversary: loss levels drift with time, arm 0 is always 0.1 better
drift = 0.5 + 0.35 * np.sin(2 * np.pi * np.arange(T) / 7000)
means = np.clip(drift[:, None] + np.where(np.arange(N) == 0, -0.1, 0.0), 0, 1)
losses = (rng.random((T, N)) < means).astype(float)   # drawn once, before play

def exp3(losses, eta, rng):
    Lhat, total = np.zeros(losses.shape[1]), 0.0   # estimated cumulative losses
    for l, u in zip(losses, rng.random(len(losses))):
        w = np.exp(-eta * (Lhat - Lhat.min()))
        p = w / w.sum()
        i = min(np.searchsorted(np.cumsum(p), u), len(p) - 1)   # draw I_t ~ p_t
        total += l[i]                              # only l[i] is observed
        Lhat[i] += l[i] / p[i]                     # importance-weighted estimate
    return total

best = losses.sum(axis=0).min()
eta = np.sqrt(2 * np.log(N) / (N * T))
regrets = [exp3(losses, eta, np.random.default_rng(s)) - best for s in range(5)]
print("EXP3 regrets over 5 runs:", np.round(regrets).astype(int))
print(f"mean {np.mean(regrets):.0f} | bound sqrt(2NT ln N) = {np.sqrt(2*N*T*np.log(N)):.0f}"
      f" | uniform play: {losses.mean(axis=1).sum() - best:.0f}")

Over five runs the regret of EXP3 ranges from 913 to 1231, with mean 1034, below the bound 1517. Playing uniformly at random would cost 4552.

5. Stochastic bandits

When the rewards of each arm are i.i.d., the learner can estimate the best arm and stop exploring the others. This chapter shows that the regret then grows only logarithmically, at a rate fixed by the gaps between arms.

5.1 The model and the regret decomposition

Arm i gives i.i.d. rewards in [0, 1] with mean \mu_i.

Let \mu^\star be the largest mean, \Delta_i = \mu^\star - \mu_i the gap of arm i, and n_i(T) the number of pulls of arm i up to T.

A good algorithm pulls each suboptimal arm rarely. Exploring each arm a fixed number of times and then committing works only if the gaps are known (Exercise 6).

5.2 Optimism: UCB

The index is an upper confidence bound: the algorithm acts as if each arm were as good as plausible. A bad arm keeps a high index only while it has been pulled few times.

Splitting the arms by whether \Delta_i exceeds 2\sqrt{N \ln T / T} gives a bound free of the gaps, R_T \leq 4 \sqrt{N T \ln T} + 3 N .

5.3 The lower bound and optimal algorithms

By Pinsker’s inequality, the constant \Delta_i / \mathrm{kl}(\mu_i, \mu^\star) is at most 1/(2\Delta_i). In the other direction, the divergence is at most the chi-square distance, so the constant is at least \frac{\Delta_i}{\mathrm{kl}(\mu_i, \mu^\star)} \geq \frac{\mu^\star (1 - \mu^\star)}{\Delta_i} . When \mu^\star stays away from 0 and 1, the term 4 / \Delta_i of UCB is therefore optimal up to a constant factor. Two algorithms reach the exact constant.

• KL-UCB replaces the Hoeffding width by the largest mean q whose divergence \mathrm{kl}(\hat\mu_i, q) stays below a threshold of order \ln t / n_i (Garivier and Cappé, 2011).
• Thompson sampling (Thompson, 1933) draws each mean from its Beta posterior and plays the arm with the largest draw. Agrawal and Goyal (2012) gave its first logarithmic bound; its asymptotic optimality was proved by Kaufmann, Korda and Munos (2012) and by Agrawal and Goyal (2013).

The block compares explore-then-commit, UCB and Thompson sampling on four Bernoulli arms with means 0.6, 0.5, 0.45 and 0.4, averaged over 100 runs.

import numpy as np
rng = np.random.default_rng(3)
mu = np.array([0.6, 0.5, 0.45, 0.4])         # Bernoulli means, arm 0 is optimal
N, R = len(mu), 100                          # arms, independent runs
gaps = mu.max() - mu

def kl(x, y):                                # Bernoulli Kullback-Leibler divergence
    return x * np.log(x / y) + (1 - x) * np.log((1 - x) / (1 - y))

def run(policy, T):
    n, s = np.zeros((R, N)), np.zeros((R, N))   # pull counts and reward sums
    m = int(np.ceil((T / N) ** (2 / 3)))        # exploration length of ETC
    regret, rows = np.zeros(R), np.arange(R)
    for t in range(T):
        if t < N:
            a = np.full(R, t)                  # pull every arm once
        elif policy == "UCB":
            a = np.argmax(s / n + np.sqrt(np.log(T) / n), axis=1)
        elif policy == "TS":                   # Thompson sampling, Beta(1, 1) prior
            a = np.argmax(rng.beta(1 + s, 1 + n - s), axis=1)
        else:                                  # explore-then-commit
            a = np.full(R, t % N) if t < m * N else np.argmax(s / n, axis=1)
        n[rows, a] += 1
        s[rows, a] += rng.random(R) < mu[a]
        regret += gaps[a]
    return regret.mean()

lr = sum(gaps[i] / kl(mu[i], mu[0]) for i in range(1, N))
for T in [2_000, 20_000]:
    res = {p: run(p, T) for p in ["ETC", "UCB", "TS"]}
    print(f"T = {T:6d}: " + "  ".join(f"{p} {v:6.1f}" for p, v in res.items())
          + f"  | Lai-Robbins {lr:.1f} x ln T = {lr * np.log(T):5.1f}"
          + f"  | UCB bound {sum(g + 4 * np.log(T) / g for g in gaps[1:]) + 2 * N:4.0f}")

From T = 2000 to T = 20{,}000, the regret of explore-then-commit grows from 34.6 to 132.9, like its T^{2/3} exploration length. That of UCB grows from 71.5 to 152.1, and that of Thompson sampling from 30.5 to 52.3. The Lai–Robbins constant is 10.6, so the asymptotic lower bound at T = 20{,}000 is about 105. It is a limit statement: Thompson sampling is below it at this horizon. The UCB bound, 867, is pessimistic but of the right order in T.

6. Games and no-regret dynamics

When several learners play against each other, each one is the environment of the others. This chapter shows that no-regret learners reach equilibria, which gives a short proof of the minimax theorem, a view of boosting, and a route to correlated equilibria.

6.1 Zero-sum games and the minimax theorem

The block lets two Hedge players face each other on a random 6 \times 4 game and compares with the value computed by linear programming.

import numpy as np
from scipy.optimize import linprog
rng = np.random.default_rng(4)
N, M = 6, 4
A = rng.random((N, M))       # row player pays A[i, j] to the column player

# Value of the game by linear programming: min v s.t. (p^T A)_j <= v, p in simplex
res = linprog(c=np.r_[np.zeros(N), 1], A_ub=np.c_[A.T, -np.ones(M)], b_ub=np.zeros(M),
              A_eq=[np.r_[np.ones(N), 0]], b_eq=[1], bounds=[(0, None)] * N + [(None, None)])
print(f"value of the game (LP): {res.fun:.4f}")

def softmax(x):
    w = np.exp(x - x.max()); return w / w.sum()

for T in [100, 1_000, 10_000]:
    eta_r, eta_c = np.sqrt(8 * np.log(N) / T), np.sqrt(8 * np.log(M) / T)
    Lr, Gc = np.zeros(N), np.zeros(M)           # cumulative losses / gains
    p_bar, q_bar = np.zeros(N), np.zeros(M)
    for t in range(T):
        p, q = softmax(-eta_r * Lr), softmax(eta_c * Gc)   # both players run Hedge
        Lr += A @ q
        Gc += A.T @ p
        p_bar += p / T
        q_bar += q / T
    gap = (p_bar @ A).max() - (A @ q_bar).min()          # duality gap of the averages
    bound = np.sqrt(np.log(N) / (2 * T)) + np.sqrt(np.log(M) / (2 * T))
    print(f"T = {T:5d}: p_bar A q_bar = {p_bar @ A @ q_bar:.4f}, "
          f"duality gap {gap:.4f} <= {bound:.4f}")

The value of the game is 0.6655. The duality gap of the averaged strategies falls from 0.0618 at T = 100 to 0.0155 at T = 1000 and 0.0046 at T = 10{,}000, each time below the bound of Corollary 6.3.

6.2 Boosting as a game

Boosting combines weak classifiers, each barely better than chance, into an accurate one. Freund and Schapire (1997, 1999) read it as a zero-sum game between a distribution on the training examples and a weak learner.

Hard examples gain weight, easy ones lose it. AdaBoost adapts the learning rate to the accuracy of each h_t (Freund and Schapire, 1997).

6.3 General games, correlated equilibria and swap regret

A CE is what a mediator can recommend: each player hears only her own action, and obeying is a best response.

With Hedge copies, the swap regret is at most N \sqrt{(T/2) \ln N}; a finer analysis gives order \sqrt{N T \ln N} (Blum and Mansour, 2007).

7. Blackwell approachability and calibration

Some goals are not a single number to minimize but a set to reach, such as “all regrets non-positive” or “forecasts that match frequencies”. Blackwell’s approachability theorem handles such goals in games with vector payoffs, and calibration is its best-known application.

7.1 Games with vector payoffs

By the minimax theorem applied to the scalar game in the condition, Blackwell’s condition holds exactly when, for every mixed action q of nature, some p gives r(p, q) \in S. A convex set is therefore approachable if and only if every mixed action of nature can be answered inside S. With realized instead of expected payoffs, Theorem 0.4 adds a term of order \sqrt{\ln(1/\delta)/T}.

7.2 Regret matching

Take the regret vector r(p, \ell) \in \mathbb{R}^N, with components \langle p, \ell \rangle - \ell(k). No regret means that the average approaches the negative orthant. The projection of x onto the orthant leaves x - \pi = x_+, the positive part, so Blackwell’s condition asks that \langle x_+, r(p, \ell) \rangle \leq 0 for every \ell.

Regret matching needs no learning rate, at the price of \sqrt{N} instead of \sqrt{\ln N}. Its version on internal regrets leads to correlated equilibria (Theorem 6.7).

7.3 Calibration

A weather forecaster announces each evening a probability of rain for the next day. She is calibrated if, among the days announced with probability 30 %, it rained on about 30 % of them.

For large T the guarantee is about 0.35/\sqrt{N}: refining the grid improves calibration. The potential \Phi is Blackwell’s squared distance to the target \{0\}, which is approachable only up to the grid error.

import numpy as np
rng = np.random.default_rng(5)
N, T = 20, 100_000                    # grid {0, 1/N, ..., 1} and horizon

def calibrated_mix(B):
    """Forecast of Theorem 7.6 from the deficits B(k): two grid points and a weight."""
    if B[0] <= 0: return 0, 0, 1.0
    if B[N] >= 0: return N, N, 1.0
    k = np.flatnonzero((B[:-1] > 0) & (B[1:] <= 0))[0]     # sign change k -> k+1
    return k, k + 1, -B[k + 1] / (B[k] - B[k + 1])        # P(forecast k/N) = q

def score(B, t):                      # calibration score (1/t) sum_k |B(k)|
    return np.abs(B).sum() / t

for adversary in ["adaptive", "i.i.d. 0.3"]:
    B = np.zeros(N + 1)
    for t in range(T):
        k0, k1, q = calibrated_mix(B)
        if adversary == "adaptive":   # sees the mixed forecast, not the coin
            y = float((q * k0 + (1 - q) * k1) / N < 0.5)
        else:
            y = float(rng.random() < 0.3)
        k = k0 if rng.random() < q else k1        # the forecaster's private coin
        B[k] += y - k / N
    bound = np.sqrt((N + 1) / T) + np.sqrt(N + 1) / (2 * np.sqrt(2) * N)
    print(f"{adversary:10s}: calibration score {score(B, T):.4f} (bound {bound:.4f})")

# A deterministic forecaster (running frequency) against y_t = 1{p_t < 1/2}
B, ones = np.zeros(N + 1), 0
for t in range(T):
    k = int(round(N * ones / max(t, 1)))
    y = float(k / N < 0.5)
    ones += y
    B[k] += y - k / N
print(f"deterministic forecaster: calibration score {score(B, T):.4f}")

With N = 20 and T = 100{,}000, the randomized forecaster has score 0.0017 against the adaptive opponent and 0.0097 on i.i.d. outcomes of mean 0.3, both below the bound 0.0955. The deterministic forecaster scores 0.5238, as Proposition 7.5 predicts.

7.4 Calibration, regret and equilibria

If every player best-responds to calibrated forecasts of the others’ actions, the empirical distribution of play converges to the set of correlated equilibria (Foster and Vohra, 1997). Perchet (2014) surveys how approachability, internal regret and calibration can each be derived from the others.

8. Partial monitoring

Between full information and bandits lie games where the feedback is some other function of the action and the outcome. This chapter defines partial monitoring, proves a regret of order T^{2/3} for a game where information must be bought, and states the classification of finite games.

8.1 Loss and feedback matrices

The previous chapters are special cases, and the applications of the course description give new ones.

• Full information: the signal reveals the outcome, H(i, j) = j.
• Bandits: the signal is the loss itself, H = L.
• Revealing action: one costly action reveals the outcome, the others give no signal; it models label-efficient prediction, where the true label of an email must be paid for.
• Dynamic pricing: a seller posts a price and observes only whether the buyer bought, not the buyer’s value.
• Repeated auctions: a bidder who learns only whether she won does not see the price she would have paid with another bid.

8.2 Buying information: the rate T^{2/3}

Exploration is now separated from exploitation: the informative action is never a good one, so its use must be rationed. Cesa-Bianchi, Lugosi and Stoltz (2006) show that the order T^{2/3} cannot be improved in such games.

import numpy as np
rng = np.random.default_rng(6)
N, M = 8, 5                                   # ordinary actions, outcomes
L = rng.random((N, M))                        # loss matrix; the revealing action costs 1

def play(T, rng):
    gamma = (np.log(N) / (2 * T)) ** (1 / 3)  # exploration rate of Theorem 8.2
    eta = np.sqrt(2 * gamma * np.log(N) / T)
    J = rng.choice(M, size=T, p=[0.4, 0.1, 0.1, 0.1, 0.3])   # oblivious outcomes
    Lhat, total = np.zeros(N), 0.0
    for t in range(T):
        if rng.random() < gamma:              # reveal: pay 1, see the whole loss vector
            total += 1.0
            Lhat += L[:, J[t]] / gamma        # unbiased estimate of the loss vector
        else:                                 # exploit: exponential weights, no feedback
            w = np.exp(-eta * (Lhat - Lhat.min()))
            i = min(np.searchsorted(np.cumsum(w / w.sum()), rng.random()), N - 1)
            total += L[i, J[t]]
    return total - L[:, J].sum(axis=1).min()  # regret against the best ordinary action

for T in [1_000, 10_000, 100_000]:
    reg = np.mean([play(T, np.random.default_rng(s)) for s in range(3)])
    bound = 3 * 2 ** (-1 / 3) * T ** (2 / 3) * np.log(N) ** (1 / 3)
    print(f"T = {T:6d}: regret {reg:7.1f}, regret / T^(2/3) = {reg / T ** (2 / 3):.3f}"
          f", bound {bound:7.1f}")

From T = 1000 to T = 100{,}000 the regret grows from 111.1 to 2376.7, while the ratio to T^{2/3} stays near 1.1, below the bound constant of about 3.0 for N = 8.

8.3 The classification of finite games

Whether a game is learnable at rate \sqrt{T} depends on what the signals reveal about the differences of losses.

• A game is globally observable if, for any two actions, the difference of their loss rows is a linear function of the signals of all actions.
• It is locally observable if, for neighbouring actions, the signals of these two actions suffice. Two actions are neighbours when their sets of optimality, among the distributions of outcomes, meet along a face of dimension M - 2.

Bartók, Foster, Pál, Rakhlin and Szepesvári (2014) proved it against stochastic environments, and Lattimore and Szepesvári (2019) completed the adversarial case. Bandits are locally observable; the revealing-action game is globally but not locally observable.

9. Complements: lower bounds, adaptivity and structured bandits

This self-study chapter completes the course in four directions: the proof of the Lai–Robbins bound, regret bounds that adapt to easy data, bandits whose arms have features, and bandits whose goal is to identify the best arm rather than to earn rewards.

9.1 Change of measure and the Lai–Robbins bound

Lower bounds for bandits compare two instances that the algorithm cannot easily tell apart. Two lemmas make this precise.

Proof of Theorem 5.4. Fix a suboptimal arm i and \varepsilon > 0.

Let \nu' be \nu with arm i replaced by a Bernoulli arm of mean \mu^\star + \varepsilon, so that i is the only optimal arm of \nu'.

1. Two expectations. Take Z = n_i(T)/T. The algorithm is consistent on both instances, so \mathbb{E}_\nu[Z] \to 0, and 1 - \mathbb{E}_{\nu'}[Z] is o(T^{a - 1}) for every a > 0.
2. Lower bound on kl. For all x, y, \mathrm{kl}(x, y) \geq (1 - x) \ln \frac{1}{1 - y} - \ln 2. With step 1, the right-hand side is at least (1 - a) \ln T\, (1 - o(1)).
3. Upper bound. By the two lemmas, since only arm i differs, the left-hand side is at most \mathbb{E}_\nu[n_i(T)]\, \mathrm{kl}(\mu_i, \mu^\star + \varepsilon) .
4. Divide by \ln T, let T \to \infty, then a \to 0 and \varepsilon \to 0. ∎

The same two lemmas, with Pinsker’s inequality, give the \sqrt{N T} lower bound of Theorem 4.5 and the bounds of best-arm identification below.

9.2 Adapting to easy data

The bound \sqrt{(T/2) \ln N} is a worst case. When the best expert has a small cumulative loss L^\star, exponential weights do much better.

A tuning of \eta in terms of L^\star gives a regret of order \sqrt{L^\star \ln N} + \ln N (Cesa-Bianchi and Lugosi, 2006, ch. 2). Since L^\star is unknown, adaptive algorithms tune themselves online.

• Second-order bounds replace T by the cumulative variance of the losses under p_t (Cesa-Bianchi, Mansour and Stoltz, 2007).
• AdaHedge sets the learning rate from the observed mixability gaps, and behaves like follow-the-leader on easy data (de Rooij, van Erven, Grünwald and Koolen, 2014).
• Excess-loss bounds hold simultaneously for every expert and adapt to stochastic data (Gaillard, Stoltz and van Erven, 2014).
• Parameter-free algorithms, built on coin betting, adapt to the norm of the comparator in online convex optimization (Orabona and Pál, 2016).

9.3 Linear and contextual bandits

An ad server knows features of the user and of each ad. In a linear bandit, each round offers a set of feature vectors a \in \mathbb{R}^d, and the reward of a is \langle \theta^\star, a \rangle plus noise. The unknown parameter is shared by all arms, so information on one arm informs the others.

Abbasi-Yadkori, Pál and Szepesvári (2011) build this ellipsoid with a self-normalized martingale inequality and prove a regret of order d \sqrt{T} up to logarithmic factors, whatever the number of arms. Li, Chu, Langford and Schapire (2010) applied a version of LinUCB to news article recommendation.

import numpy as np
rng = np.random.default_rng(7)
d, K, T, lam, sigma = 5, 20, 5000, 1.0, 0.3     # dimension, ads per round, horizon
theta = rng.normal(size=d); theta /= np.linalg.norm(theta)

V, b = lam * np.eye(d), np.zeros(d)              # ridge statistics
reg_lin, reg_rand = 0.0, 0.0
for t in range(1, T + 1):
    A = rng.normal(size=(K, d)) / np.sqrt(d)     # features of the K ads shown to user t
    Vinv = np.linalg.inv(V)
    theta_hat = Vinv @ b
    beta = sigma * np.sqrt(d * np.log(1 + t / (lam * d)) + 2 * np.log(T)) + np.sqrt(lam)
    width = np.sqrt(np.einsum("kd,de,ke->k", A, Vinv, A))     # ||a|| in the V^{-1} norm
    a = A[np.argmax(A @ theta_hat + beta * width)]            # optimistic choice
    r = a @ theta + sigma * rng.normal()                      # noisy reward
    V += np.outer(a, a)
    b += r * a
    best = (A @ theta).max()
    reg_lin += best - a @ theta
    reg_rand += best - A[rng.integers(K)] @ theta
print(f"LinUCB regret {reg_lin:.1f}, random ads {reg_rand:.1f}, "
      f"estimation error {np.linalg.norm(theta_hat - theta):.3f}")

With 20 new ads per round in dimension 5, LinUCB has regret 30.6 over 5000 rounds, against 4149.7 for random ads, and its estimate of \theta^\star is within 0.015 of the truth.

9.4 Pure exploration: identifying the best arm

In an A/B test, the goal is to find the best arm with confidence 1 - \delta using as few samples as possible, not to earn rewards along the way. The Reinforcement Learning course devotes a lecture to such bandit methods for pure exploration.

The proof is Lemmas 9.1 and 9.2 again. The optimal proportions w solve a zero-sum game between the sampler and a nature that picks the most confusing alternative. Degenne, Koolen and Ménard (2019) exploit this game with the no-regret learners of ch. 6.

10. Research directions and open problems

This self-study chapter points to active questions in the topics of the course. The papers cited are entry points, not a complete survey.

10.1 Best of both worlds

Algorithms are usually designed either for stochastic or for adversarial bandits. Bubeck and Slivkins (2012) showed that a single algorithm can have polylogarithmic regret on stochastic instances and regret of order \sqrt{T}, up to logarithms, against adversaries. Zimmert and Seldin (2021) obtained optimal rates in both regimes with a plain FTRL algorithm and a Tsallis-entropy regularizer. Extending such guarantees to structured settings (linear bandits, partial monitoring, reinforcement learning) is an active direction.

10.2 Faster learning in games

In self-play, Hedge reaches an \varepsilon-equilibrium after about 1/\varepsilon^2 rounds. Optimistic variants, which use the last loss as a prediction of the next one, go faster: Rakhlin and Sridharan (2013) in zero-sum games, Syrgkanis, Agarwal, Luo and Schapire (2015) in general games. Daskalakis, Fishelson and Golowich (2021) proved that optimistic Hedge has regret polylogarithmic in T when all players use it.

Open questions concern the convergence of the last iterate rather than of averages, and the complexity of reaching correlated equilibria in games with many players or large action sets.

10.3 Calibration

The rate of the calibration error is not settled. When the forecasts may take any value in [0, 1], the unnormalized error T C_T of the forecaster of Foster and Vohra (1998) is of order at most T^{2/3}, and random outcomes force at least \sqrt{T}.

Qiao and Valiant (2021) raised the lower exponent strictly above 1/2. Dagan, Daskalakis, Fishelson, Golowich, Kleinberg and Okoroafor (2025) then brought the upper exponent strictly below 2/3. The optimal exponent remains open.

Calibration has also come back in machine learning: neural network classifiers are often miscalibrated (Guo, Pleiss, Sun and Weinberger, 2017), and multicalibration requires calibration on many subpopulations at once (Hébert-Johnson, Kim, Reingold and Rothblum, 2018).

10.4 Partial monitoring and information

The classification of ch. 8 holds up to logarithmic factors and to constants that depend on the game; how the regret scales with the numbers of actions and outcomes is much less understood. Information-directed sampling (Russo and Van Roy, 2018) chooses actions by trading off expected regret against information gain, and applies to feedback structures beyond bandits. Lattimore and Szepesvári (COLT 2019) used an information-theoretic analysis of this kind to bound the minimax regret of finite partial-monitoring games. Making such algorithms efficient for large games is an open direction.

10.5 Online aggregation in practice

Expert aggregation is used for operational forecasting. Devaine, Gaillard, Goude and Stoltz (2013) aggregate specialized forecasters of electricity consumption, and adaptive algorithms such as those of ch. 9.2 are designed for this use. Open questions include aggregation under distribution shift, with delayed feedback, and with probabilistic rather than point forecasts.

Exercises

Exercises are sorted by level: ★ applies the course, ★★ combines results or asks for a short proof, ★★★ is open-ended or research-flavoured. The session plan says which exercises follow which session.

1. ★ The size of a random walk. Let X_1, \dots, X_T be independent and uniform on \{-1, 1\}, with T = 2500. Use Theorem 0.4 to find a level \varepsilon such that the sum exceeds \varepsilon with probability at most 0.01, and compare with the normal approximation.

   Solution: the range of each X_t has length 2, so the bound is \exp(-2\varepsilon^2 / (4T)). Setting it to 0.01 gives \varepsilon = \sqrt{2 T \ln 100} = \sqrt{5000 \times 4.605} \approx 151.7 . The sum has standard deviation \sqrt{T} = 50, and the normal 1 % quantile gives 2.326 \times 50 \approx 116.3: the inequality is conservative by a factor of about 1.3, but has the right order.

2. ★ Cover’s adversary and the halving algorithm. (a) A deterministic learner predicts the majority of the past outcomes, and 1 on ties. Run Cover’s adversary for T = 6 rounds and compute the regret against the two constant experts. (b) With N = 64 experts, one of them perfect, how many mistakes can the halving algorithm make? Show that the bound can be attained.

   Solution: (a) The predictions are 1, 0, 1, 0, 1, 0, and the adversary answers 0, 1, 0, 1, 0, 1. The learner makes 6 mistakes, each constant expert 3: the regret is 3 = T/2.

   (b) At most \log_2 64 = 6. Let expert k predict at round t the t-th bit of k. At every round the surviving experts split evenly, the adversary contradicts the majority, and exactly one expert survives after 6 rounds.

3. ★ Follow the leader by hand. On the sequence of Example 1.5 with T = 9, ties broken toward action 1, list the actions of follow-the-leader, its total loss and the losses of the two actions. Count the leader changes and compare with the regret.

   Solution: FTL plays 1, 2, 1, 2, 1, 2, 1, 2, 1 and loses 0.5 + 8 = 8.5. Action 1 loses 4.5 and action 2 loses 4, so the regret is 4.5.

   The leader changes 8 times. In general the regret of FTL is at most the number of leader changes for losses in [0, 1]: this follows from step 1 of Theorem 3.5 with no regularizer.

4. ★ Tuning exponential weights. Take N = 16 experts and T = 1000 rounds. (a) Compute the learning rate and the bound of Theorem 2.2. (b) Compute the bound of the doubling trick. (c) Compute the bound of Theorem 2.9 for the square loss on [0, 1].

   Solution: (a) \ln 16 = 2.773, so \eta = \sqrt{8 \times 2.773 / 1000} \approx 0.149, and the bound is \sqrt{500 \times 2.773} \approx 37.2.

   (b) 3.414 \times 37.2 \approx 127.1. (c) The square loss is 1/2-exp-concave, so the regret is at most 2 \ln 16 \approx 5.5, whatever T.

5. ★ Online gradient descent by hand. On K = [-1, 1], the losses are f_t(x) = (x - y_t)^2/2 with y = (1, 1, -1, 1). Run OGD from x_1 = 0 with constant step \eta = 0.5, compute its total loss and its regret, and compare with Theorems 3.2 and 3.3.

   Solution: the gradients are x_t - y_t. The iterates are 0, 0.5, 0.75, -0.125, with losses 0.5, 0.125, 1.531 and 0.633: total 2.789.

   The best fixed point is the mean 0.5, with total loss 1.5, so the regret is 1.289. Theorem 3.2 with D = G = 2 gives 4 + 4 = 8. The losses are 1-strongly convex, and Theorem 3.3 gives 2(1 + \ln 4) \approx 4.77 with the steps 1/t.

6. ★ Explore-then-commit with a known gap. Two arms have rewards in [0, 1] and gap \Delta. Explore-then-commit pulls each arm m times, then commits to the best empirical mean. (a) Show that R_T \leq m \Delta + T \Delta\, e^{-m \Delta^2 / 2} . (b) Choose m for \Delta = 0.1 and T = 10^4, and compute the bound. (c) What is left of the guarantee if the true gap is 0.02?

   Solution: (a) Exploration costs m\Delta. The commitment is wrong only if the sum of the m differences of paired rewards, each in [-1, 1] with mean -\Delta, is non-negative; Hoeffding bounds this probability by e^{-m\Delta^2/2}.

   (b) Setting the derivative to zero gives m = (2/\Delta^2) \ln(T \Delta^2 / 2) = 200 \ln 50 \approx 783, and the bound is 78.3 + 2/\Delta = 98.3. (c) With m = 783 and \Delta = 0.02, the failure bound is e^{-0.157} \approx 0.86: no protection. The tuning needed the unknown gap, which UCB does not need.

7. ★ UCB indices. With T = 1000, after 30 rounds arm 1 has 20 pulls and mean 0.6, arm 2 has 6 pulls and mean 0.5, arm 3 has 4 pulls and mean 0.3. Compute the indices of Algorithm 5.2, the next arm, and the maximal number of pulls of an arm of gap 0.2 on the good event of Theorem 5.3.

   Solution: \ln T = 6.908. The indices are 0.6 + 0.588 = 1.188, 0.5 + 1.073 = 1.573 and 0.3 + 1.314 = 1.614: UCB pulls arm 3, the least explored.

   An arm of gap 0.2 is pulled at most 1 + 4 \times 6.908 / 0.04 \approx 692 times. The bound is pessimistic: with this width, UCB explores a lot at small horizons.

8. ★ A 2 × 2 zero-sum game. The row player pays A = \begin{pmatrix} 0.2 & 0.8 \\ 0.7 & 0.4 \end{pmatrix}. Find the value and the optimal strategies, and the bound on the duality gap of Hedge self-play after T = 10^4 rounds.

   Solution: with probability p on row 1, the two columns cost 0.7 - 0.5 p and 0.4 + 0.4 p; they are equal at p = 1/3.

   With probability q on column 1, the two rows cost 0.8 - 0.6 q and 0.4 + 0.3 q, equal at q = 4/9. The value is 8/15 \approx 0.533.

   By Corollary 6.3, the gap is at most 2 \sqrt{\ln 2 / (2T)} \approx 0.0118.

9. ★ A calibration score by hand. With the grid of step 1/4, a forecaster announces 0.25 four times (outcomes 0, 0, 1, 0), 0.75 four times (outcomes 1, 1, 0, 1) and 0.5 twice (outcomes 1, 0). Compute its calibration score and its mean squared error, and compare with the forecaster that always announces 0.5.

   Solution: each bin has the right frequency (1/4, 3/4 and 1/2), so C_{10} = 0. Its mean squared error is 2.0/10 = 0.20.

   The constant forecaster is also perfectly calibrated, since the overall frequency is 1/2, but its mean squared error is 0.25. Calibration is necessary for good probability forecasts, not sufficient: the first forecaster is also more refined.

10. ★★ Exp-concave losses. (a) Show that the square loss on [0, 1] is \eta-exp-concave if and only if \eta \leq 1/2. (b) Show that the logarithmic loss is 1-exp-concave, that exponential weights with \eta = 1 predict with the Bayesian posterior mixture, and deduce the regret bound \ln N directly.

    Solution: (a) For h(f) = e^{-\eta (f - y)^2}, the second derivative is (4\eta^2 (f - y)^2 - 2\eta)\, h(f). It is non-positive for all f, y \in [0, 1] if and only if 2\eta \leq 1, since |f - y| can reach 1.

    (b) e^{-\lambda} is the predicted probability of the outcome, which is linear in the forecast. The weights are proportional to the likelihoods, so they form the posterior of a uniform prior. The cumulative loss of the mixture is minus the log of the average likelihood, which is at most that of the best expert plus \ln N.

11. ★★ Anytime learning rates (Python). Rerun the block of ch. 2 with three versions of exponential weights: the tuned rate, the rate \eta_t = \sqrt{8 \ln N / t}, and the doubling trick. Compare the regrets with the bounds.

    Hints and expected result: on the unstable sequence the regrets are about 29.7 (tuned), 58.3 (anytime) and 69.2 (doubling). On the stochastic experts they are about 111.2, 89.9 and 189.9.

    The anytime rate costs at most a constant factor, and the restarts of the doubling trick waste information; both stay well below the bound 3.41 \sqrt{(T/2) \ln N} of Proposition 2.6.

12. ★★ Follow the leader on quadratic losses. Let f_t(x) = (x - y_t)^2 with y_t \in [0, 1] on K = [0, 1]. Show that follow-the-leader plays the running mean of the past outcomes and that its regret is at most 2(1 + \ln T).

    Solution: the minimizer of a sum of squares is the mean, so x_{t+1} - x_t = (y_t - x_t)/t. By the be-the-leader inequality (step 1 of Theorem 3.5 with \psi = 0), the regret is at most the sum of f_t(x_t) - f_t(x_{t+1}).

    Each term equals (x_t - x_{t+1})(x_t + x_{t+1} - 2 y_t), of absolute value at most (1/t) \times 2. Summing the harmonic series gives the claim. Strong convexity makes the leader stable.

13. ★★ UCB against an adversary (Python). With two arms and T = 20{,}000, build the reward sequence that gives reward 0 to the arm UCB pulls and 1 to the other. (a) Show that UCB has regret at least T/2 on it. (b) Run EXP3 on the same, now fixed, sequence.

    Hints and expected result: (a) UCB is deterministic, so the sequence is well defined in advance. UCB earns 0, and the two arms earn T in total, so the better one earns at least T/2.

    (b) In a run, each arm earns 10,000, so UCB’s regret is exactly 10,000. EXP3 has regrets between -42 and 66 over five seeds, below its bound \sqrt{2 N T \ln N} \approx 235. Randomization protects EXP3; optimism assumes stationarity.

14. ★★ Equilibria in the game of chicken. Two drivers choose Dare or Chicken, with gains (row, column): (D, D) = (0, 0), (D, C) = (7, 2), (C, D) = (2, 7), (C, C) = (6, 6). (a) Show that the uniform distribution on (C, C), (D, C), (C, D) is a correlated equilibrium. (b) Find the mixed Nash equilibrium and compare the gains. (c) Show Nash \subset CE \subset CCE in general.

    Solution: (a) Told C, a driver faces C or D with probability 1/2 each: obeying gives 4, daring gives 3.5. Told D, she faces C for sure: daring gives 7, against 6 for C.

    (b) Indifference gives the probability 1/3 of daring, for a gain of 14/3 ≈ 4.67 each, against 5 in the correlated equilibrium. (c) A product distribution satisfies the CE constraints exactly when each action in its support is a best response; constant maps are particular maps.

15. ★★ Regret matching from Blackwell’s theorem. (a) Show that the projection onto the negative orthant is the coordinatewise minimum with 0, so that x - \pi = x_+. (b) Show that p proportional to x_+ satisfies Blackwell’s condition with equality. (c) Apply Theorem 7.2 to losses in [0, 1] and compare with Proposition 7.3.

    Solution: (a) The orthant is a product of half-lines, so the projection acts coordinatewise. (b) The inner product \langle x_+, \pi \rangle vanishes, and \langle x_+, r(p, \ell) \rangle = 0 for this p, as in the proof of Proposition 7.3.

    (c) The regrets lie in [-1, 1] and the projections in [-1, 0], so K \leq 2 \sqrt{N} and the distance is at most 2\sqrt{N/T}. The direct analysis gains a factor 2: the positive regrets are at most \sqrt{N T}.

16. ★★ Rationing information. In Theorem 8.2, (a) show that for a fixed exploration rate the best learning rate gives regret at most \gamma T + \sqrt{2 T \ln N / \gamma} ; (b) minimize in \gamma and recover the constant 3 \cdot 2^{-1/3}; (c) compute \gamma, the expected number of revealing rounds and the bound for N = 8 and T = 10^5.

    Solution: (a) \ln N/\eta + \eta T/(2\gamma) is minimal at \eta = \sqrt{2 \gamma \ln N / T}, with value \sqrt{2 T \ln N / \gamma}.

    (b) The derivative vanishes at \gamma = (\ln N / (2T))^{1/3}; the two terms are then 2^{-1/3} and 2^{2/3} times T^{2/3} (\ln N)^{1/3}.

    (c) \gamma = (2.079 / 200{,}000)^{1/3} \approx 0.0218, so about 2180 revealing rounds, and the bound is about 6548. The block of ch. 8 measures a regret of about 2377.

17. ★★ Choosing the grid of a calibrated forecaster. Using Theorem 7.6, choose the grid size N as a function of a known horizon T to minimize the bound, and give the resulting rate. Compute it for T = 10^6.

    Solution: for large N the bound is about \sqrt{N/T} + 1/(2\sqrt{2N}). The two terms balance at N = \sqrt{T}/(2\sqrt{2}), and the bound becomes 2^{1/4}\, T^{-1/4} \approx 1.19\, T^{-1/4} . For T = 10^6, N \approx 354 and the bound is about 0.038. Sharper analyses reach the order T^{-1/3} (Foster and Vohra, 1998).

18. ★★★ A two-armed minimax lower bound. Let \nu have Bernoulli arms of means (1/2 + \Delta, 1/2) and \nu' means (1/2 + \Delta, 1/2 + 2\Delta), with \Delta \leq 1/8.

    Using Lemmas 9.1 and 9.2 and Pinsker’s inequality, show that every algorithm has regret at least \sqrt{T}/44 on one of them when \Delta = 1/\sqrt{T} and T \geq 64.

    Hints and expected result: let a and b be the expectations of n_2(T)/T under the two instances. The regrets satisfy R_\nu \geq T \Delta a, \qquad R_{\nu'} \geq T \Delta (1 - b) .

    Only arm 2 differs, and \mathrm{kl}(1/2, 1/2 + 2\Delta) \leq 22 \Delta^2, so Pinsker gives (b - a)^2 \leq 11 T a \Delta^2.

    If a \geq 1/(44 T \Delta^2), then R_\nu \geq 1/(44\Delta). Otherwise b - a \leq 1/2 and the larger regret is at least T\Delta/4. Conclude with \Delta = 1/\sqrt{T}.

19. ★★★ Optimistic self-play (Python, research-flavoured). In the block of ch. 6, let both players use optimistic Hedge, which counts the last loss vector twice in the exponent, with the constant rate \eta = 0.5. Compare the duality gap of the averages with tuned Hedge and with Hedge at \eta = 0.5, for T = 100, 1000 and 10,000, and relate to ch. 10.2.

    Hints and expected result: with the same matrix, tuned Hedge gives gaps of about 0.062, 0.016 and 0.0046, the rate 1/\sqrt{T} of the block. Hedge at \eta = 0.5 gives about 0.044, 0.011 and 0.0049, still decreasing like 1/\sqrt{T} (0.0016 at T = 10^5).

    Optimistic Hedge gives about 0.041, 0.0031 and 0.0003: a rate close to 1/T, as predicted by Rakhlin and Sridharan (2013). Try a general-sum game next, and measure the distance to the set of CCE with a linear program.

Projects and assessment

master-mva.com announces a homework (“Devoir Maison”) and a final exam (“Mode de validation”), and the Université Paris-Saclay course detail describes the assessment as “Evaluation Continue non Intégrale” (partial continuous assessment); no weights are displayed. The solo subjects below are sized like a substantial homework or a paper study, in the MVA tradition; the group subjects are larger. The written exam is a proposal in the spirit of a blackboard course. Each project is evaluated with the rubric at the end of the section.

Solo projects

1. [Solo · ≈ 20 h] EXP3 and implicit exploration (paper study: Auer, Cesa-Bianchi, Freund and Schapire, 2002; Neu, 2015). How heavy is the tail of the realized regret of EXP3, and how much does implicit exploration help?
   • Implement: EXP3 (Algorithm 4.3) and EXP3-IX, whose estimator adds a small constant to the denominator (ch. 2, 4).
   • Data: synthetic oblivious sequences, including drifting losses and the sequence of Exercise 13.
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: histograms of the realized regret over at least 200 seeds, with the 99 % quantile of EXP3-IX below the high-probability bound of Neu (2015), and a comparison with EXP3.
2. [Solo · ≈ 20 h] Calibrated forecasting (paper study: Foster and Vohra, 1998; Foster, 1999). How fast can a forecaster become calibrated against an adaptive opponent?
   • Implement: the forecaster of Theorem 7.6, a deterministic forecaster, and an opponent that maximizes the current calibration deficit (ch. 7).
   • Prove: the rate of Exercise 17, and the inequality of step 3 of Theorem 7.6 in full.
   • Deliverables: code, a 4–6 page report with the proofs, a 10-minute talk.
   • Success criterion: a log–log plot of the calibration score against T, with N proportional to \sqrt{T}, of slope at most -1/4, and the deterministic forecaster stuck above 1/2.
3. [Solo · ≈ 20 h] Towards the Lai–Robbins constant (paper study: Garivier and Cappé, 2011; Kaufmann, Korda and Munos, 2012). How fast do KL-UCB and Thompson sampling approach the asymptotic lower bound?
   • Implement: UCB (Algorithm 5.2), KL-UCB and Thompson sampling, vectorized over runs (ch. 5, 9.1).
   • Data: Bernoulli instances with small and large gaps, including means close to 0 where Pinsker’s inequality is loose.
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: curves of R_T / \ln T up to T = 10^6 with confidence bands over at least 100 runs, the Lai–Robbins constant drawn, and a supported conclusion on which algorithms approach it.

Group projects

1. [Group of 3 · ≈ 30 h each] Online aggregation of load forecasters (paper study: Devaine, Gaillard, Goude and Stoltz, 2013; Gaillard, Stoltz and van Erven, 2014). Can an online mixture of simple forecasters beat the best of them on a series with a regime change?
   • Data: a synthetic hourly load series with daily and weekly cycles, a temperature effect and a level shift after one year.
   • Split: member A builds the experts (seasonal naive, ridge regressions on different features); member B implements exponential weights for the square loss, OGD on the simplex and an adaptive algorithm (ch. 2, 3, 9.2); member C runs the evaluation.
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: an aggregated error below that of the best expert, regret curves against the best expert and the best convex combination, and behaviour across the shift.
2. [Group of 2–3 · ≈ 30 h each] No-regret dynamics in games and auctions (paper study: Hart and Mas-Colell, 2000; Blum and Mansour, 2007). Which equilibria do Hedge, regret matching and swap-regret learners reach?
   • Data: the game of chicken (Exercise 14), Shapley’s 3 \times 3 game, and a two-bidder first-price auction with values drawn uniformly on a grid of 10 values, one learner per value over a grid of bids (Example 6.9).
   • Split: member A writes linear programs that measure the violation of the CE and CCE constraints; member B implements the learners, including Theorem 6.8; member C runs the auction (ch. 6, 7).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: CE violations of swap-regret learners below R_T / T, a case where Hedge reaches a CCE that is not a CE, and auction bids compared with the equilibrium bid v/2.
3. [Group of 3 · ≈ 30 h each] Contextual bandits for ad selection (paper study: Li, Chu, Langford and Schapire, 2010; Abbasi-Yadkori, Pál and Szepesvári, 2011). How much do features help, and what happens when the click model is not linear?
   • Data: a synthetic click model with user and ad features, linear and logistic versions, and a log of random displays.
   • Split: member A implements LinUCB (Algorithm 9.4) and a linear Thompson sampling; member B the non-contextual baselines EXP3 and UCB; member C the offline replay evaluation on the random log (ch. 4, 5, 9.3).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: regret curves of all algorithms, a replay estimate within the confidence interval of the online click rate, and an analysis of the misspecified logistic case.

Written exam (proposal)

Format (proposal): 3 hours, one handwritten A4 sheet allowed, no electronic device, four exercises.

1. Question (4 points). Define the regret of a randomized learner, and the difference between oblivious and adaptive environments. Prove that every deterministic learner has regret at least T/2 in binary prediction with two constant experts, and explain the two remedies used in the course.

   Expected: Definitions 1.1–1.2; Proposition 1.3 with the adversary that contradicts the learner; randomization (linear expected loss) and convexity (averaging the advice).

2. Computation (6 points). (a) Compute the learning rate and the regret bound of EXP3 for N = 5 arms and T = 10^4, and compare with full information. (b) With T = 10^4, arm 1 has 40 pulls and mean 0.55, arm 2 has 10 pulls and mean 0.40: compute the UCB indices and the bound of Theorem 5.3 if the gap is 0.15. (c) Find the value and the optimal strategies of the game where the row player pays \begin{pmatrix} 0.1 & 0.6 \\ 0.5 & 0.2 \end{pmatrix}.

   Expected: (a) \eta \approx 0.0080 and a bound of about 401, against 89.7 with full information: a factor \sqrt{4N} \approx 4.5. (b) The indices are 1.030 and 1.360, so arm 2 is pulled; the bound is about 250. (c) p = 3/8 on row 1, q = 1/2 on column 1, value 0.35.

3. Short proof (5 points). Prove the regret bound of exponential weights for losses in [0, 1], admitting Hoeffding’s lemma, and deduce the bound for the aggregation of forecasters with a convex loss.

   Expected: the potential proof of Theorem 2.2 in its three steps, the tuning of \eta, and Corollary 2.3 by Jensen’s inequality.

4. Problem (5 points). (a) State Blackwell’s condition and prove the rate of Theorem 7.2. (b) Derive regret matching from it and prove its \sqrt{N T} bound. (c) Show that no deterministic forecaster is calibrated.

   Expected: (a) the decomposition and the induction of Theorem 7.2. (b) The positive part as the direction to the orthant, Proposition 7.3. (c) Proposition 7.5.

Grading rubric (proposal)

References

Official references (master-mva.com, “Références”)

• N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006 — ch. 1, 2, 6, 7, 8.
• S. Bubeck, N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems”, Foundations and Trends in Machine Learning 5(1), 1–122, 2012 — ch. 4, 5.
• V. Perchet, “Approachability, regret and calibration: implications and equivalences”, Journal of Dynamics and Games 1, 181–254, 2014 — ch. 6, 7.
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020 — ch. 4, 5, 8, 9.

Books and surveys

• E. Hazan, “Introduction to online convex optimization”, Foundations and Trends in Optimization 2(3–4), 2016 — ch. 3.
• S. Shalev-Shwartz, “Online learning and online convex optimization”, Foundations and Trends in Machine Learning 4(2), 2012 — ch. 3.
• F. Orabona, “A modern introduction to online learning”, arXiv:1912.13213, 2019 — ch. 3, 9.2.

Experts and exponential weights (ch. 1–2)

• V. Vovk, “Aggregating strategies”, Proceedings of the Third Annual Workshop on Computational Learning Theory (COLT), 1990.
• N. Littlestone, M. K. Warmuth, “The weighted majority algorithm”, Information and Computation 108(2), 1994.
• Y. Freund, R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting”, Journal of Computer and System Sciences 55(1), 1997.
• J. Kivinen, M. K. Warmuth, “Exponentiated gradient versus gradient descent for linear predictors”, Information and Computation 132(1), 1997.
• J. Hannan, “Approximation to Bayes risk in repeated play”, Contributions to the Theory of Games 3, Annals of Mathematics Studies 39, Princeton University Press, 1957.

Online convex optimization and stochastic optimization (ch. 3)

• M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent”, ICML, 2003.
• E. Hazan, A. Agarwal, S. Kale, “Logarithmic regret algorithms for online convex optimization”, Machine Learning 69(2–3), 2007.
• N. Cesa-Bianchi, A. Conconi, C. Gentile, “On the generalization ability of on-line learning algorithms”, IEEE Transactions on Information Theory 50(9), 2004.
• A. Rakhlin, O. Shamir, K. Sridharan, “Making gradient descent optimal for strongly convex stochastic optimization”, ICML, 2012.

Bandits (ch. 4, 5, 9)

• P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, “The nonstochastic multiarmed bandit problem”, SIAM Journal on Computing 32(1), 2002.
• P. Auer, N. Cesa-Bianchi, P. Fischer, “Finite-time analysis of the multiarmed bandit problem”, Machine Learning 47(2–3), 2002.
• T. L. Lai, H. Robbins, “Asymptotically efficient adaptive allocation rules”, Advances in Applied Mathematics 6(1), 1985.
• 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.
• A. Garivier, O. Cappé, “The KL-UCB algorithm for bounded stochastic bandits and beyond”, COLT, 2011.
• E. Kaufmann, N. Korda, R. Munos, “Thompson sampling: an asymptotically optimal finite-time analysis”, ALT, 2012.
• S. Agrawal, N. Goyal, “Analysis of Thompson sampling for the multi-armed bandit problem”, COLT, 2012.
• S. Agrawal, N. Goyal, “Further optimal regret bounds for Thompson sampling”, AISTATS, 2013.
• J.-Y. Audibert, S. Bubeck, “Minimax policies for adversarial and stochastic bandits”, COLT, 2009.
• G. Neu, “Explore no more: improved high-probability regret bounds for non-stochastic bandits”, NeurIPS, 2015.
• A. Garivier, P. Ménard, G. Stoltz, “Explore first, exploit next: the true shape of regret in bandit problems”, Mathematics of Operations Research 44(2), 2019.
• Y. Abbasi-Yadkori, D. Pál, C. Szepesvári, “Improved algorithms for linear stochastic bandits”, NeurIPS, 2011.
• L. Li, W. Chu, J. Langford, R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation”, WWW, 2010.
• A. Garivier, E. Kaufmann, “Optimal best arm identification with fixed confidence”, COLT, 2016.
• R. Degenne, W. M. Koolen, P. Ménard, “Non-asymptotic pure exploration by solving games”, NeurIPS, 2019.

Games, approachability and calibration (ch. 6–7)

• Y. Freund, R. E. Schapire, “Adaptive game playing using multiplicative weights”, Games and Economic Behavior 29(1–2), 1999.
• A. Blum, Y. Mansour, “From external to internal regret”, Journal of Machine Learning Research 8, 2007.
• S. Hart, A. Mas-Colell, “A simple adaptive procedure leading to correlated equilibrium”, Econometrica 68(5), 2000.
• T. Roughgarden, “Intrinsic robustness of the price of anarchy”, Journal of the ACM 62(5), 2015.
• D. Blackwell, “An analog of the minimax theorem for vector payoffs”, Pacific Journal of Mathematics 6(1), 1956.
• D. P. Foster, R. V. Vohra, “Calibrated learning and correlated equilibrium”, Games and Economic Behavior 21(1–2), 1997.
• D. P. Foster, R. V. Vohra, “Asymptotic calibration”, Biometrika 85(2), 1998.
• D. P. Foster, “A proof of calibration via Blackwell’s approachability theorem”, Games and Economic Behavior 29(1–2), 1999.
• D. Oakes, “Self-calibrating priors do not exist”, Journal of the American Statistical Association 80(390), 1985.

Partial monitoring (ch. 8)

• N. Cesa-Bianchi, G. Lugosi, G. Stoltz, “Regret minimization under partial monitoring”, Mathematics of Operations Research 31(3), 2006.
• G. Bartók, D. P. Foster, D. Pál, A. Rakhlin, C. Szepesvári, “Partial monitoring—classification, regret bounds, and algorithms”, Mathematics of Operations Research 39(4), 2014.
• T. Lattimore, C. Szepesvári, “Cleaning up the neighborhood: a full classification for adversarial partial monitoring”, ALT, 2019.
• T. Lattimore, C. Szepesvári, “An information-theoretic approach to minimax regret in partial monitoring”, COLT, 2019.

Adaptivity and research directions (ch. 9–10)

• N. Cesa-Bianchi, Y. Mansour, G. Stoltz, “Improved second-order bounds for prediction with expert advice”, Machine Learning 66(2–3), 2007.
• S. de Rooij, T. van Erven, P. D. Grünwald, W. M. Koolen, “Follow the leader if you can, hedge if you must”, Journal of Machine Learning Research 15, 2014.
• P. Gaillard, G. Stoltz, T. van Erven, “A second-order bound with excess losses”, COLT, 2014.
• F. Orabona, D. Pál, “Coin betting and parameter-free online learning”, NeurIPS, 2016.
• S. Bubeck, A. Slivkins, “The best of both worlds: stochastic and adversarial bandits”, COLT, 2012.
• J. Zimmert, Y. Seldin, “Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits”, Journal of Machine Learning Research 22, 2021.
• A. Rakhlin, K. Sridharan, “Optimization, learning, and games with predictable sequences”, NeurIPS, 2013.
• V. Syrgkanis, A. Agarwal, H. Luo, R. E. Schapire, “Fast convergence of regularized learning in games”, NeurIPS, 2015.
• C. Daskalakis, M. Fishelson, N. Golowich, “Near-optimal no-regret learning in general games”, NeurIPS, 2021.
• M. Qiao, G. Valiant, “Stronger calibration lower bounds via sidestepping”, STOC, 2021.
• Y. Dagan, C. Daskalakis, M. Fishelson, N. Golowich, R. Kleinberg, P. Okoroafor, “Breaking the T^{2/3} barrier for sequential calibration”, STOC, 2025.
• C. Guo, G. Pleiss, Y. Sun, K. Q. Weinberger, “On calibration of modern neural networks”, ICML, 2017.
• Ú. Hébert-Johnson, M. P. Kim, O. Reingold, G. N. Rothblum, “Multicalibration: calibration for the (computationally-identifiable) masses”, ICML, 2018.
• D. Russo, B. Van Roy, “Learning to optimize via information-directed sampling”, Operations Research 66(1), 2018.
• M. Devaine, P. Gaillard, Y. Goude, G. Stoltz, “Forecasting electricity consumption by aggregating specialized experts”, Machine Learning 90(2), 2013.