Bandit Algorithms

How quickly does the empirical mean of independent random variables concentrate around the true mean? This question is the analytic engine of the entire theory of stochastic bandits: every optimistic algorithm (Explore-Then-Commit, UCB and its relatives) is calibrated by a tail bound on the sample mean. This mission formalizes the subgaussian framework of Chapter 5 of Lattimore–Szepesvári's Bandit Algorithms: a random variable $X$ is $\sigma$-subgaussian when $\mathbb{E}[e^{\lambda X}] \le e^{\lambda^2\sigma^2/2}$ for all $\lambda$, and the Cramér–Chernoff method converts this moment-generating-function control into the exponential tail $\mathbb{P}(X \ge \varepsilon) \le e^{-\varepsilon^2/(2\sigma^2)}$. The goal theorem is the Hoeffding-type bound: the sample mean of $n$ independent $\sigma$-subgaussian deviations exceeds the true mean by $\varepsilon$ with probability at most $\exp(-n\varepsilon^2/(2\sigma^2))$, together with its confidence form $\mathbb{P}\big(\hat\mu + \sqrt{2\sigma^2\log(1/\delta)/n} \le \mu\big) \le \delta$ — the exact bound every UCB index is built from. These few lines of analysis are cited by every regret bound in the series.

Motivation

In best arm identification with fixed confidence, a learner samples $K$ unknown distributions ("arms") sequentially and must name the arm with the largest mean, with error probability at most a prescribed $\delta$, using as few samples as possible. Garivier and Kaufmann (arXiv:1602.04589, COLT 2016) showed that every $\delta$-PAC strategy needs, in expectation, at least $T^*(\boldsymbol\mu)\,\mathrm{kl}(\delta,1-\delta)$ samples, where the characteristic time $T^*(\boldsymbol\mu)$ is the value of a max–min optimization problem over the proportions of draws allocated to the arms. The maximizer of that problem, $w^*(\boldsymbol\mu)$, is the allocation any asymptotically optimal strategy must follow; the Track-and-Stop algorithm of the same paper computes $w^*(\hat{\boldsymbol\mu})$ at plug-in estimates and tracks it.

A strategy can only track $w^*$ if $w^*$ can be computed. This mission formalizes the part of the paper (Section 2.2 and Appendix A) that turns the abstract max–min problem into an explicit recipe: a closed form for the inner infimum, and a characterization of $w^*$ through the root of one increasing scalar function. The problem had been solved in closed form before only for special cases, such as Poisson rewards with all suboptimal arms equal (Vaidhyan and Sundaresan, 2015); the paper's result covers every one-parameter exponential family.

Setting

A canonical one-parameter exponential family is a family of laws $\nu_\theta$, $\theta\in\Theta$, on $\mathbb R$ with density $\exp(\theta x-b(\theta))$ with respect to a reference measure $\xi$. The law $\nu_\theta$ has mean $\dot b(\theta)$; the set of attainable means is the mean space $\dot b(\Theta)$. For means $\mu=\dot b(\theta)$ and $\mu'=\dot b(\theta')$ the Kullback–Leibler divergence is

Bernoulli laws and Gaussian laws with known variance are the standard examples.

A bandit model is identified with its vector of means $\boldsymbol\mu=(\mu_1,\dots,\mu_K)\in\dot b(\Theta)^K$. $\mathcal S$ is the set of models with a unique optimal arm $a^*(\boldsymbol\mu)$, and $\mathrm{Alt}(\boldsymbol\mu)=\{\boldsymbol\lambda\in\mathcal S:a^*(\boldsymbol\lambda)\ne a^*(\boldsymbol\mu)\}$ is the set of alternatives. $\Sigma_K$ is the probability simplex. The transportation cost of proportions $w\in\Sigma_K$ and the objects of the paper are

The arms are sorted so that $\mu_1>\mu_2\ge\dots\ge\mu_K$. The parameterized Jensen–Shannon divergence is, for $\alpha\in[0,1]$,

For $a\in\{2,\dots,K\}$ let $g_a(x)=(1+x)I_{1/(1+x)}(\mu_1,\mu_a)$ for $x\ge0$, let $x_a=g_a^{-1}$, and let $x_1\equiv1$. Finally

Formalization targets

Goal: Theorem 5 (p. 5)

With $D=d(\mu_1,\mu_2)$: $F_{\boldsymbol\mu}$ is continuous and strictly increasing on $[0,D[$, $F_{\boldsymbol\mu}(0)=0$, $F_{\boldsymbol\mu}(y)\to\infty$ as $y\to D$, the equation $F_{\boldsymbol\mu}(y)=1$ has a unique solution $y^*\in[0,D[$, and

The equivalence says at once that the argmax exists, that it is a single point, and that it is given by eq. (5).

Milestones

1. Lemma 3 (p. 5): for every $w\in\Sigma_K$,

2. Claim after eq. (4) (p. 5): $g_a$ is a strictly increasing one-to-one mapping from $[0,+\infty[$ onto $[0,d(\mu_1,\mu_a)[$.
3. Lemma 4 (p. 5): for every maximizer $w^*$ and all $a,b\in\{2,\dots,K\}$,

Significance

The result. Theorem 5 reduces a $(K-1)$-dimensional non-smooth max–min problem to finding the root of one continuous increasing function on a bounded interval, each evaluation of which requires $K-1$ scalar inversions. It gives existence and uniqueness of $w^*(\boldsymbol\mu)$, which the paper's lower bound only presupposes, and it is the computational core of Track-and-Stop: without an explicit, well-posed $w^*$ the tracking strategy is not defined. Lemma 3 alone gives the closed form of the inner infimum used again in the analysis of the stopping rule.

Formalizing it. The results are proved in the paper; nothing here is open. To the best of our knowledge none of them has a machine-checked proof: the platform's existing best-arm-identification rows concern Gaussian arms and state the characteristic time at the level of measures, without this characterization. The mission produces a checked reduction for general one-parameter exponential families, including the edge cases the text passes over (ties among suboptimal arms, zero weights, the behaviour of $x_a$ near the end of its domain).

Difficulty

The infimum in Lemma 3 ranges over $\mathrm{Alt}(\boldsymbol\mu)$, a set of models with a unique best arm, so it is an open condition: the minimizing configuration, in which $\lambda_1$ and $\lambda_a$ coincide, lies outside $\mathrm{Alt}(\boldsymbol\mu)$ and is only approached. Other arms may also compete for the best position. A statement in which the infimum is taken over the closed relaxation $\{\lambda_a\ge\lambda_1\}$ is a lemma of the proof, not Lemma 3.

For Theorem 5, the equalization in Lemma 4 needs an argument that holds for every maximizer, not only for one found by a first-order condition, because the objective is a minimum of functions and is not differentiable. The monotonicity of $F_{\boldsymbol\mu}$ needs the monotonicity of each $x_a$ and of each ratio in the moving point $m_a$, and the limit at $D$ rests on the second-best arm(s) only, which is where the ordering $\mu_1>\mu_2\ge\dots$ enters. Finally the analytic facts about $d$ (continuity, positivity off the diagonal, monotonicity in each argument) must be derived from the exponential family itself.

Formalization scope

Lean represents a model by μ : Fin K → ℝ with 2 ≤ K and every μ a in the mean space deriv F.b '' F.Θ. The paper's arm $1$ is index 0, arm $2$ is index 1. The exponential family is a structure ExpFamily whose parameter set is a nonempty open interval and whose b is twice continuously differentiable with $\ddot b>0$ on $\Theta$. These two conditions are added to the paper's "convex, twice differentiable" and are disclosed: strict convexity is what makes the mean parameterization unique, and openness is what lets alternatives approach the boundary of $\mathrm{Alt}(\boldsymbol\mu)$. The reference measure and normalization are part of the structure but unused here.

The transportation cost is an infimum in EReal, so it is the true infimum of the set of values rather than a default 0. $w^*(\boldsymbol\mu)$ is never defined by choice: "$w$ is optimal" is a predicate, and Theorem 5 characterizes the set of such $w$. The functions $x_a$ are the inverse of $g_a$ on $[0,+\infty[$ and are evaluated only on $[0,d(\mu_1,\mu_2)[$. "Increasing" in Theorem 5 is stated as strictly increasing, as proved in Appendix A.2. Lemmas 3 and 4 and the claim on $g_a$ assume only that arm $1$ is the unique best arm, which is weaker than the paper's standing ordering.

A formalization that replaces $\mathrm{Alt}(\boldsymbol\mu)$ by $\{\lambda_a\ge\lambda_1\}$, assumes the maximizer exists and is unique, or asserts only existence of some $y^*$ without the formula for $w^*$, does not state these results and is ruled out.

A complete development needs: basic calculus of exponential families (the Bregman form of $d$, its continuity and strict positivity off the diagonal, its monotonicity in the second argument), the inverse function of a continuous strictly monotone map on an interval, and compactness of the simplex. The divergence facts are reusable in every bandit mission built on exponential families. Proofs of the milestones, of auxiliary facts about $d$ and $I_\alpha$, and a sorry-free instance of ExpFamily (Bernoulli or unit-variance Gaussian) are welcome.

Selected references

• A. Garivier, E. Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016 (JMLR W&CP 49), arXiv:1602.04589v2. https://arxiv.org/abs/1602.04589
• E. Kaufmann, O. Cappé, A. Garivier, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, JMLR 17, 2016. https://arxiv.org/abs/1407.4443
• N. K. Vaidhyan, R. Sundaresan, Learning to detect an oddball target, arXiv:1508.05572, 2015. https://arxiv.org/abs/1508.05572
• O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, G. Stoltz, Kullback–Leibler upper confidence bounds for optimal sequential allocation, Annals of Statistics 41(3), 2013. https://arxiv.org/abs/1210.1136

Motivation

In the contextual bandit problem a learner repeatedly observes a context, picks one of $K$ actions, and sees the reward of that action only. Against a finite class $\Pi$ of policies, statistically optimal regret of order $\sqrt{KT\ln|\Pi|}$ has been known since EXP4 (Auer et al., 2002), but EXP4 maintains a weight per policy and costs $\Omega(|\Pi|)$ time per round. For the large policy classes used in practice (linear classifiers, trees), that is prohibitive.

The oracle-efficient line of work accesses $\Pi$ only through a cost-sensitive classification oracle (an arg max oracle, AMO). The RandomizedUCB algorithm of Dudík et al. (2011) obtains optimal regret with polynomially many oracle calls by solving a convex program in each round, but the number of calls is large. Agarwal, Hsu, Kale, Langford, Li and Schapire (2014) replace that solver by a coordinate descent method whose number of iterations, and hence of oracle calls, is bounded independently of $|\Pi|$. Their algorithm, ILOVETOCONBANDITS, and its practical variant are now standard references for oracle-based exploration.

This mission formalizes the optimization half of that paper: Algorithm 2 solves the per-epoch problem (OP) after at most $4\ln(1/(K\mu))/\mu$ coordinate steps.

Setting

Let $A=\{0,\dots,K-1\}$ be the actions, $X$ any set of contexts, and $\Pi\subseteq A^X$ a finite nonempty set of policies. A history $H_t$ is a sequence of $t\ge1$ records $(x_i,a_i,r_i(a_i),p_i(a_i))$ with $r_i(a_i)\in[0,1]$ the observed reward and $p_i(a_i)\in(0,1]$ the probability with which $a_i$ was chosen. Write $\widehat{\mathbb E}_{x\sim H_t}[f(x)]=\frac1t\sum_i f(x_i)$.

The inverse propensity scoring estimate (Eq. (1)) is

the estimated regret is $\widehat{\mathrm{Reg}}_t(\pi)=\max_{\pi'\in\Pi}\widehat{\mathcal R}_t(\pi')-\widehat{\mathcal R}_t(\pi)$, and for a minimum probability $\mu$ one sets $b_\pi=\widehat{\mathrm{Reg}}_t(\pi)/(\psi\mu)$ with $\psi=100$.

Weights are vectors $Q\in\mathbb R^\Pi$; $\Delta^\Pi$ is the set of nonnegative $Q$ with $\sum_\pi Q(\pi)\le1$. The smoothed projection of $Q$ is

The optimization problem (OP) asks for $Q\in\Delta^\Pi$ with

Algorithm 2 starts from $Q_{\mathrm{init}}$ and loops. With $V_\pi(Q)=\widehat{\mathbb E}[1/Q^\mu(\pi(x)\mid x)]$, $S_\pi(Q)=\widehat{\mathbb E}[1/Q^\mu(\pi(x)\mid x)^2]$ and $D_\pi(Q)=V_\pi(Q)-(2K+b_\pi)$: if $\sum_\pi Q(\pi)(2K+b_\pi)>2K$ it rescales $Q$ by $c=2K/\sum_\pi Q(\pi)(2K+b_\pi)$ (Eq. (4)); then, if some $\pi$ has $D_\pi(Q)>0$, it adds

to $Q(\pi)$ (Step 8) and repeats; otherwise it halts and outputs $Q$.

The analysis uses the potential (Eq. (6)), with $\tau=t$ and $\mathcal U_A$ uniform on $A$,

Formalization targets

Goal: Theorem 3 (p. 6)

For $0<\mu\le1/(2K)$, Algorithm 2 with $Q_{\mathrm{init}}=\mathbf 0$ satisfies: every run executes Step 8 at most

times, whatever policy each Step 8 chooses among those with $D_\pi>0$; and when it halts, its output solves (OP). The bound depends on $K\mu$ only, not on $|\Pi|$ or $t$.

Milestones

1. Lemma 5 (p. 10). If Algorithm 2 halts and outputs $Q$, then $Q$ satisfies (2), (3) and $\sum_\pi Q(\pi)\le1$.
2. Lemma 6 (p. 10). If $\sum_\pi Q(\pi)(2K+b_\pi)>2K$ and $c$ is as in Eq. (4), then $\Phi_m(cQ)\le\Phi_m(Q)$.
3. Lemma 7 (p. 10). If $D_\pi(Q)>0$ and $Q'$ adds $\alpha_\pi(Q)$ to $Q(\pi)$, then

Significance

The result. Theorem 3 is what makes ILOVETOCONBANDITS computationally efficient: each call of Algorithm 2 is implemented with one AMO call per iteration (Lemma 1 of the paper), so the oracle complexity of an epoch is $O(\ln(1/(K\mu))/\mu)$. Combined with the epoch schedule and warm start, this gives the paper's total of $\tilde O(\sqrt{KT/\ln(|\Pi|/\delta)})$ oracle calls over $T$ rounds. Theorem 3 also gives a constructive proof that (OP) is feasible for every history, which the regret analysis (a separate mission in this series) assumes.

Formalizing it. The result is proved in the paper, with complete proofs of Lemmas 5–7 in Appendix D. No machine-checked version is known. The formalization would give a checked termination bound for a coordinate descent method on a non-smooth feasibility problem, with a fully explicit constant, and a verified definition of the unnormalized relative entropy potential that is reusable for other smoothed-projection analyses (e.g. RandomizedUCB-type convex programs).

Difficulty

Termination cannot be read off the constraints. Step 8 raises one weight and can push the total weight above 1, after which Step 5 shrinks every coordinate, so no constraint and no single weight moves monotonically along a run. The number of policies that violate (3) can also go up after a step. Bounding the number of iterations therefore needs a global quantity that tracks progress through both kinds of step. The rescaling step is the harder of the two: it lowers every $Q^\mu(a\mid x)$ at once, which pushes the relative-entropy term the wrong way, and it must be offset by the drop in the regret term. Knowing that (OP) is feasible, or that some convex function has a minimizer, bounds nothing about how many steps a particular method takes; that is the obvious approach, and it gives no count.

Formalization scope

• Actions are Fin K with $K\ge1$; contexts form an arbitrary type (no measure is needed: Theorem 3 is deterministic). $\Pi$ is a nonempty Finset (X → Fin K); weights are real functions on its subtype.
• Histories are indexed by Fin t with $t\ge1$ (0-based indices). The paper allows $p_i(a_i)\in[0,1]$; the formalization requires $p_i(a_i)\in(0,1]$, since Eq. (1) divides by it.
• $\widehat{\mathrm{Reg}}_t(\pi)$ is written as $\max_{\pi'}\widehat{\mathcal R}_t(\pi')-\widehat{\mathcal R}_t(\pi)$, which equals $\widehat{\mathcal R}_t(\pi_t)-\widehat{\mathcal R}_t(\pi)$ for any maximizer $\pi_t$; $\psi=100$ is hard-wired in $b_\pi$.
• $Q^\mu$, $V_\pi$, $S_\pi$, (OP) and $\Phi_m$ all use the smoothed projection of the unnormalized weights; there is no default policy in this mission.
• $\mu$ ranges over $(0,1/(2K)]$, the range of $\mu_m$ in Algorithm 1 that the printed theorem refers to. $\tau$ in $\Phi_m$ is the history length $t$.
• Algorithm 2 is encoded relationally. A run of length $n$ from $Q_{\mathrm{init}}$ is a sequence $Q^{(0)}=Q_{\mathrm{init}},\dots,Q^{(n)}$ in which each $Q^{(k+1)}$ is Step 8, for some policy with $D_\pi>0$, applied to the rescaled $Q^{(k)}$. It halts at $Q^{(n)}$ when no policy has $D_\pi>0$ after rescaling, and it then outputs the rescaled $Q^{(n)}$. "Iterations" means executions of Step 8. The last pass, which halts at Step 10, is not counted: the paper's proof bounds "the number of times Step 8 is executed". The bound is compared in $\mathbb R$, without rounding.
• Lemmas 5–7 are stated for nonnegative weight vectors without a bound on their sum, because Algorithm 2 rescales vectors whose sum may exceed 1. Lemma 7's "$\alpha=\alpha_\pi(Q)>0$" is part of its conclusion.
• A trivializing formalization is ruled out: the goal quantifies over every run from $\mathbf 0$ and every choice in Step 8, not over some run, and the potential, $b_\pi$ and $D_\pi$ are computed from the history rather than taken as free parameters.
• The auxiliary facts $\Phi_m\ge0$ and $\Phi_m(\mathbf 0)\le\tau\mu\ln(1/(K\mu))/(1-K\mu)$ are inline claims in the paper and are not stated separately; contributions stating and proving them are welcome, as are general lemmas on the unnormalized relative entropy.
• Out of scope: the regret bound (Theorem 2) and the probabilistic model (mission I of this series), the AMO implementation (Lemma 1), warm start and epoch-level oracle counts (Lemmas 2, 3, 8), and the support lower bound (Theorem 4).

Selected references

• A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, R. E. Schapire, Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits, ICML 2014; arXiv:1402.0555v2. https://arxiv.org/abs/1402.0555
• M. Dudík, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, T. Zhang, Efficient Optimal Learning for Contextual Bandits, UAI 2011. https://arxiv.org/abs/1106.2369
• P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM J. Comput. 32(1), 2002. https://doi.org/10.1137/S0097539701398375

Motivation

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a point $x_t$ from a compact decision set $D\subset\mathbb R^n$ and observes only the random cost $\ell_t$ of that point, whose mean is $\mu\cdot x_t$ for an unknown vector $\mu$. The problem models online routing, ad placement and other sequential decisions with linearly structured costs. The quality of a learner is measured by its regret against the best fixed decision.

For the $K$-armed bandit the achievable regret for a fixed instance is logarithmic in the horizon $T$ (Lai and Robbins 1985; Auer, Cesa-Bianchi and Fischer 2002). Dani, Hayes and Kakade (COLT 2008) showed that for linear costs the picture depends on the geometry of $D$. Their Theorem 1 gives polylogarithmic regret when the decision set has a positive gap between the best and second-best extreme point (a polytope, for instance), and their Theorem 2 gives $O^*(n\sqrt T)$ regret for every decision set. Their Theorem 3 shows that the second rate cannot be improved in general: on a decision set with zero gap, every algorithm pays $\Omega(\sqrt T)$ in expectation.

Timeline:

• 2002: Auer, Using confidence bounds for exploitation–exploration trade-offs (JMLR 3), introduces confidence-bound algorithms for linear bandits on finite decision sets.
• 2008: Dani, Hayes and Kakade prove the $O^*(n\sqrt T)$ upper bound for ConfidenceBall₂ and the $\Omega(\sqrt T)$ lower bound on a product of circles, the subject of this mission. A hypercube lower bound for the adversarial setting appears in their NIPS 2007 paper.
• 2010: Rusmevichientong and Tsitsiklis, Linearly parameterized bandits (Math. OR 35), give $\Omega(n\sqrt T)$ lower bounds on the unit sphere.
• 2020: Lattimore and Szepesvári, Bandit Algorithms, Theorems 24.1 and 24.2, give minimax lower bounds on the hypercube and the unit ball with Gaussian noise.

Setting

The decision set is the unit circle $D_2=S^1=\{x\in\mathbb R^2: x_1^2+x_2^2=1\}$. An unknown mean vector $\mu\in\mathbb R^2$ is drawn once, uniformly from the circle $D_2/2$ of radius $1/2$; concretely $\mu=\mu(\theta)=\tfrac12(\cos\theta,\sin\theta)$ with $\theta$ uniform on $[0,2\pi)$.

On each round $t=1,\dots,T$ the algorithm plays $x_t\in D_2$ and observes a cost $\ell_t\in\{-1,+1\}$ with $\Pr(\ell_t=+1)=(1+\mu\cdot x_t)/2$, so that $\mathbb E[\ell_t]=\mu\cdot x_t$. Given the decision, the cost is independent of the past.

An algorithm may be randomised. It draws a seed $s$ once from a probability measure $\rho$ on a measurable space $S$, and chooses $x_t$ as a function of $s$ and the costs $\ell_1,\dots,\ell_{t-1}$ observed so far, measurably in $s$.

The regret over $T$ rounds is

so each round costs $r_t=\mu\cdot x_t+\tfrac12\ge0$ when $\|\mu\|=1/2$. The expected regret $\mathbb E R=\mathbb E_\mu\,\mathbb E(R\mid\mu)$ averages over the seed, the prior and the costs.

In the Lean development these objects are unitCircle, meanVec, optCost, RandomizedPolicy and expectedRegret in the namespace StochLinOpt.LowerBound.

Formalization targets

Goal: Theorem 3 for $n=2$

There is a universal constant $c>0$ such that for every randomised algorithm and every $T\ge1$,

The constant is left existential, which is the form that survives any later improvement of the constant; it is chosen before the algorithm and before $T$.

Milestones

1. Section 6.1, Eq. (3). For $\|\mu_1\|=\|\mu_2\|=1/2$, $x\in S^1$, a posterior probability $p\in[0,1]$ of $\mu=\mu_1$ and a cost $\ell\in\{\pm1\}$, the Bayes-updated bias $b_{t+1}$ satisfies $|b_{t+1}-b_t|\le|(\mu_1-\mu_2)\cdot x|$, where $b_t=2p-1$.
2. Lemma 15. With $\varepsilon=\|\mu_1-\mu_2\|>0$ and the same data,

3. Theorem 4 (Freedman). For a martingale difference sequence $X_1,\dots,X_T$ bounded above by $b$, with conditional variance sum $V$, and all $a,v>0$,

Significance

The lower bound shows that the $\sqrt T$ dependence of the problem-independent upper bound (Theorem 2 of the same paper) is necessary. It also shows that the gap-dependent polylogarithmic rate of Theorem 1 cannot extend to decision sets without a gap, such as the sphere. Together with the upper bound it characterises the minimax regret of stochastic linear bandits in $T$ up to logarithmic factors, and in the paper's general-$n$ form it also underlies the claim that the price of bandit information is $\Theta^*(\sqrt n)$.

The result is proved in the paper for $n=2$ and has not been machine-checked. The mission produces a checked Bayesian lower bound over all randomised algorithms, with an explicit probability model for the protocol. Two related platform results are different theorems: BanditAlgorithm.linear_bandit_unit_ball_minimax_lower_bound (Lattimore–Szepesvári Theorem 24.2: unit ball, Gaussian noise, a worst-case $\mu$) and BanditAlgorithm.linear_bandit_hypercube_minimax_lower_bound (Theorem 24.1: hypercube). The $\{-1,+1\}$ costs, the circle and the uniform prior used here are not covered by either.

Difficulty

The obvious attempt is a two-point change-of-measure argument with a fixed pair of means at distance $\varepsilon$. It fails as stated because the decision set has no gap: an algorithm that plays close to the optimum of both candidates learns slowly but also pays little. The per-round trade-off between regret and information (Lemma 15) is exact only while the posterior is undecided, $|b_t|\le1/2$. Turning it into a bound on the whole horizon requires controlling how long the posterior stays undecided, which is a statement about a martingale whose step sizes are chosen by the algorithm; a concentration bound that ignores the accumulated conditional variance (Azuma–Hoeffding with worst-case steps) is too weak for this. The averaging step from a two-point prior to the uniform prior on the circle is also part of the formal work.

Formalization scope

Vectors are Fin 2 → ℝ with the dot product ⬝ᵥ; Euclidean norms are written through dot products, never with Lean's sup norm. Rounds are 0-indexed internally: the Lean index $t$ is the paper's round $t+1$. The expected regret is the exact finite expectation

so no infinite product of measures is needed. A randomised algorithm is a seeded policy, which covers every randomised algorithm. The optimal cost is the infimum of $\mu\cdot x$ over the compact circle and is attained. Every junk value in the model (a non-integrable integrand) could only make the lower bound harder to prove, never easier.

A statement over deterministic algorithms only, over a worst-case $\mu$ instead of the uniform prior, or with the constant allowed to depend on the algorithm or on $T$ would be a weaker theorem. The goal quantifies $\exists c>0$ before the algorithm and $T$, and fixes the prior.

Corrections relative to the printed paper:

• General $n$ is not stated. Theorem 3 as printed claims $\mathbb E R\ge\frac1{10}n\sqrt T$ for every even $n$. It is false for $n>10$: on $D_n$ with $\mu\in D_n/n$ each round has regret at most $1$, so at $T=1$ the claim would need $\mathbb E R\ge n/10>1$. The general case rests on Lemma 16, which has no proof. The goal is the $n=2$ case, which Section 6.1 proves.
• The constant. For $n=2$ the paper prints $\frac15\sqrt T$; its proof gives $c=\frac1{16}\min(\frac12-\frac1e,\frac1{64})=\frac1{1024}$. The proof's Freedman step prints $2\exp(-\frac{1/4}{1/8+\varepsilon/3})\le 2/e^2$; with $v=1/32$ the denominator is $1/16+\varepsilon/3$, and the bound $2/e^2$ then needs $\varepsilon=T^{-1/4}\le3/16$. Small $T$ is covered by the first round, whose expected regret is $1/2$. The goal leaves $c$ existential.
• Theorem 4. The printed variance sum runs to $n$; it runs to $T$. The conditioning is on a general filtration, and square-integrability of the steps is assumed so that the conditional variance is defined.
• Lemma 15. Its right side depends on the round-$t$ cost $\ell_t$, which is not part of $\mathcal H_t$; the Lean statement holds for either value of $\ell_t$.

Welcome contributions: a Lean proof of Freedman's inequality (reusable across the bandit and concentration missions on the platform); the averaging argument from two-point priors to the uniform prior; and the stopped-martingale bookkeeping for the bias sequence.

Selected references

• Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Stochastic Linear Optimization under Bandit Feedback, Proceedings of the 21st Annual Conference on Learning Theory (COLT), 2008.
• David A. Freedman, On tail probabilities for martingales, The Annals of Probability 3(1):100–118, 1975. https://doi.org/10.1214/aop/1176996452
• Colin McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics, Springer, 1998. https://doi.org/10.1007/978-3-662-12788-9_6
• Peter Auer, Using confidence bounds for exploitation–exploration trade-offs, JMLR 3:397–422, 2002. https://www.jmlr.org/papers/v3/auer02a.html
• Paat Rusmevichientong, John N. Tsitsiklis, Linearly parameterized bandits, Mathematics of Operations Research 35(2):395–411, 2010. https://doi.org/10.1287/moor.1100.0446
• Tor Lattimore, Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 24. https://doi.org/10.1017/9781108571401

Motivation

Decision-making problems rarely present the same fixed choice twice. A doctor prescribing a treatment sees each patient's medical history and symptoms before deciding; a website choosing which article to show sees the visitor's profile first. The multi-armed bandit model — where the learner repeatedly picks from a fixed set of arms with no side information — cannot express this: it is blind to the covariates that any real decision-maker actually observes. The contextual bandit model closes this gap by letting the learner see a context before acting, and asks for a decision rule that generalizes across contexts rather than memorizing a policy per context. Foster and Rakhlin's Foundations of Reinforcement Learning and Interactive Decision Making (arXiv:2312.16730v1, Section 3, pp. 38–53) develops this model and its algorithms as the bridge between supervised learning and sequential decision making, en route to general reinforcement learning. Contextual bandits with a learned reward-function class underlie production systems for content recommendation, online advertising, and adaptive clinical trial design (Li et al., A Contextual-Bandit Approach to Personalized News Article Recommendation, 2010, https://arxiv.org/abs/1003.0146; Agarwal et al., Making Contextual Decisions with Low Technical Debt, 2016, https://arxiv.org/abs/1606.03966).

The algorithmic history in this chapter runs through two distinct principles. The optimism principle (LinUCB, Section 3.2) generalizes the UCB algorithm to contexts under a linear reward model, but the chapter's own Example 3.1 (Section 3.3) shows optimism fails outside such structured classes, incurring regret linear in the size of the context space or the class. Foster and Rakhlin then present two "black-box" alternatives that use any function class $F$ through an abstract regression subroutine: the naive $\varepsilon$-Greedy method (Section 3.4), and the Inverse Gap Weighting (IGW) strategy underlying the SquareCB algorithm (Bietti, Agarwal & Langford, A Contextual Bandit Bake-off, 2018, https://arxiv.org/abs/1802.04064; Foster & Rakhlin, Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles, 2020, https://arxiv.org/abs/2002.04926). SquareCB attains a regret rate that both generalizes across contexts (no dependence on the size of the context space) and matches the optimal $\sqrt{T}$ rate — improving on $\varepsilon$-Greedy's $T^{2/3}$ rate — while remaining agnostic to the internal structure of $F$.

Setting

Over $T$ rounds, a decision-maker faces the contextual bandit protocol: at each round $t$, it observes a context $x_t \in X$, selects a decision $\pi_t$ from a finite action set $\Pi = \{1,\dots,A\}$, and observes a reward $r_t \in \mathbb{R}$. Rewards are generated independently as $r_t \sim M^\star(\cdot \mid x_t, \pi_t)$ for a fixed, unknown conditional model $M^\star$; write $f^\star(x,\pi) := \mathbb{E}[r \mid x, \pi]$ for the mean reward function and $\pi^\star(x) := \arg\max_\pi f^\star(x,\pi)$ for the optimal, context-dependent policy. The context sequence $x_1,\dots,x_T$ is arbitrary — fixed in advance or adversarially chosen — while rewards remain stochastic. Performance is measured by regret against $\pi^\star$:

where $p_t$ is the learner's (possibly randomized) action distribution at round $t$.

To generalize across contexts, the learner is given a class $F \subseteq \{f : X\times\Pi \to \mathbb{R}\}$ with $f^\star \in F$, and aims for regret scaling with the statistical complexity $\log|F|$ rather than with $|X|$. Both algorithms in this mission access $F$ only through an online regression oracle (Definition 3, p. 47): given the history $(x_1,\pi_1,r_1),\dots,(x_{t-1},\pi_{t-1},r_{t-1})$, it returns an estimate $\hat f_t : X\times\Pi\to\mathbb{R}$ satisfying, with probability at least $1-\delta$, $\sum_{t=1}^T \mathbb{E}_{\pi_t\sim p_t}[(\hat f_t(x_t,\pi_t)-f^\star(x_t,\pi_t))^2] \le \mathrm{EstSq}(F,T,\delta)$ — for instance, exponential weights on a finite class $F$ achieves $\mathrm{EstSq}(F,T,\delta) = \log(|F|/\delta)$. SquareCB (p. 50–51) then samples its action from the Inverse Gap Weighting distribution (Definition 4, p. 50): given a vector of estimated values $\hat f \in \mathbb{R}^A$ with greedy action $\bar\pi = \arg\max_\pi \hat f(\pi)$, and an exploration parameter $\gamma \ge 0$, $p = \mathrm{IGW}_\gamma(\hat f)$ is $p(\pi) = 1/(\lambda + 2\gamma(\hat f(\bar\pi)-\hat f(\pi)))$ for the unique $\lambda \in [1,A]$ making $p$ a probability distribution.

Formalization targets

Milestone — Proposition 9 (IGW estimation-to-regret inequality)

This holds for any $\hat f, f^\star \in \mathbb{R}^A$ and any $\gamma>0$, with no reference to $F$ or to how $\hat f$ was produced — it is the purely algebraic core the goal theorem invokes at every round.

Goal — Proposition 10 (SquareCB regret bound)

with probability at least $1-\delta$, for SquareCB run with $\gamma = \sqrt{TA/\mathrm{EstSq}(F,T,\delta)}$, for any context sequence $x_1,\dots,x_T$. This is the weakest stable target level in the chapter's oracle-based development: it is stated for an arbitrary class $F$ and oracle, so it survives any future improvement to the oracle's own $\mathrm{EstSq}$ bound, unlike a version hard-coded to a specific class or oracle.

Significance

Proposition 10 shows that Inverse Gap Weighting converts any estimation-error guarantee into a regret guarantee with the same statistical rate, with no algorithm-side dependence on the structure of $F$ or the size of $X$: the same SquareCB template, driven by a plug-in regression oracle, is minimax optimal whenever the oracle itself is. When $F$ is finite, this yields $\mathrm{Reg} \lesssim \sqrt{AT\log(|F|/\delta)}$, matching the optimal rate for stochastic multi-armed bandits (Section 2) while generalizing across contexts — a guarantee that optimism (Proposition 7) provably cannot deliver outside linear classes (Example 3.1), and that the simpler $\varepsilon$-Greedy baseline (Proposition 8) only delivers at a slower $T^{2/3}$ rate. Foster and Rakhlin describe Proposition 9 itself as being "at the core of the development for the rest of the course": the same IGW mechanism reappears, generalized, in the book's treatment of general decision-making and the Decision-Estimation Coefficient.

Both propositions are proved results, not open questions; this mission's contribution is a machine-checked formalization of their exact statements and hypotheses — the precise OracleGuarantee hypothesis Proposition 10 requires, the exact constant ($2$, not a bare $\lesssim$) its proof yields at the stated optimal $\gamma$, and the universally-quantified form of the IGW inequality (Proposition 9) that makes it reusable independently of any particular oracle or class.

Difficulty

The obvious first idea for exploiting an estimator $\hat f_t$ is a UCB-style optimism approach: build a confidence set around $\hat f_t$ and act greedily on its upper envelope, as in LinUCB (Proposition 7). Example 3.1 shows this fails in general: a class $F$ can force the confidence set to remain wide on a fresh action at every new context, driving regret linear in $\min\{|F|,|X|\}$ — the confidence width in the regret bound does not shrink merely because the oracle's cumulative estimation error is small, since that error is not localized to the specific action the confidence-set approach tries next. Uniform exploration ($\varepsilon$-Greedy) sidesteps this but wastes exploration budget on actions already known to be far from optimal, which is what caps its rate at $T^{2/3}$ (Proposition 8). Inverse Gap Weighting instead ties the sampling probability itself to the estimated gap from the greedy action, so cheap-to-rule-out actions are down-weighted continuously rather than either fully explored (ε-Greedy) or trusted outright (optimism); the technical content of Proposition 9 is showing this specific reciprocal-gap form gives a bound with no hidden dependence on $F$ or $X$, for every pair $(\hat f, f^\star)$ simultaneously — a guarantee optimism cannot match because its confidence sets are class-dependent by construction.

Formalization scope

Contexts form an arbitrary type X; actions are Fin A for A : ℕ. A finite probability distribution over Fin A is represented directly as p : Fin A → ℝ with ∀ π, 0 ≤ p π and ∑ π, p π = 1, and $\mathbb{E}_{\pi\sim p}[g]$ as the finite sum ∑ π, p π * g π, rather than via Mathlib's PMF (which is ℝ≥0∞-valued) — an equivalent and lighter-weight representation of a distribution on a finite type. The normalizing constant $\lambda$ of Definition 4 and the optimal actions $\pi^\star$, $\bar\pi$ are each specified by their defining property (existence of $\lambda \in [1,A]$ realizing the IGW formula; $\forall\pi, f(\pi)\le f(\text{argmax})$) rather than constructed explicitly via an intermediate-value or Finset.argmax argument, avoiding committing to one choice function for a value the book itself leaves implicit. The class $F$ enters neither proposition's statement directly: it appears in the source only through the abstract bound $\mathrm{EstSq}(F,T,\delta)$, which is carried as an explicit real-valued parameter and hypothesis (OracleGuarantee) rather than as a literal subset of a function space, since no property of $F$ beyond producing this bound is ever used. The probability-$(1-\delta)$ qualifier attached to the online regression oracle's guarantee is likewise the explicit hypothesis OracleGuarantee ... EstSq on a fixed realized run, rather than a statement quantified over an underlying probability space of histories — every subsequent step in both propositions' proofs is deterministic given that this event holds, so this does not weaken either conclusion. A trivializing formalization would fix $A=1$ (a single ever-optimal action, making both Reg and the IGW inequality vacuous) or take EstSq as an unconstrained free variable with no positivity hypothesis (making $\gamma$ in Proposition 10 undefined); this mission's statements require 0 < EstSq and leave $A$, $T$, $X$, $F$-via-EstSq fully general.

This mission omits Proposition 7 (LinUCB): its proof rests on an entirely disjoint apparatus (finite linear parameter sets, least-squares confidence sets, the elliptic potential lemma) that neither Proposition 9 nor 10 requires, and Example 3.1 (the failure of optimism) is a worked example rather than a numbered, formalizable claim. It also omits Proposition 8 ($\varepsilon$-Greedy): the source leaves the optimal $\varepsilon$ unspecified ("choosing $\varepsilon$ appropriately"), and deriving its own optimal value and matching constant independently — rather than reusing the book's own explicit constant, as Rule 7 of this formalization effort requires — was judged too likely to introduce an unfaithful, invented constant within this mission's time budget; both are natural extensions for a follow-up mission or contribution. Reusable infrastructure: the Fin A-indexed finite-distribution convention and the OracleGuarantee/optimal-action-by-property pattern extend directly to any later chapter built on the same online-regression-oracle abstraction.

Selected references

• Foster, D. J. and Rakhlin, A. Foundations of Reinforcement Learning and Interactive Decision Making. 2023. https://arxiv.org/abs/2312.16730
• Foster, D. J. and Rakhlin, A. Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles. ICML 2020. https://arxiv.org/abs/2002.04926
• Bietti, A., Agarwal, A., and Langford, J. A Contextual Bandit Bake-off. JMLR 2021 (arXiv 2018). https://arxiv.org/abs/1802.04064
• Li, L., Chu, W., Langford, J., and Schapire, R. E. A Contextual-Bandit Approach to Personalized News Article Recommendation. WWW 2010. https://arxiv.org/abs/1003.0146
• Agarwal, A. et al. Making Contextual Decisions with Low Technical Debt. 2016. https://arxiv.org/abs/1606.03966

Motivation

The multi-armed bandit is the simplest model of sequential decision-making under partial feedback: a learner repeatedly picks one of finitely many options and observes a reward only for the option chosen, never for the alternatives. It formalizes problems ranging from clinical trial design (which treatment to offer a patient) to online advertising (which ad to show) and A/B testing more generally. The framework dates to Robbins' 1952 paper on sequential design, and the algorithm this mission's goal theorem concerns — the Upper Confidence Bound (UCB) algorithm of Lai and Robbins [1985] and Auer, Cesa-Bianchi and Fischer [2002] — is the canonical answer to how to explore efficiently: instead of exploring uniformly at random, act optimistically with respect to the current uncertainty about each option's value. This mission draws its formalization from Chapter 2 of Foster and Rakhlin's 2023 lecture notes, Foundations of Reinforcement Learning and Interactive Decision Making, which develops the bandit problem as the first rung of a ladder of increasingly general interactive decision-making settings (contextual bandits, structured bandits, reinforcement learning) that the book's later chapters build.

Setting

Fix a finite decision (action) space $\Pi = \{1,\dots,A\}$. In the multi-armed bandit protocol, for each round $t = 1,\dots,T$ the learner selects a decision $\pi_t \in \Pi$, possibly at random according to a distribution $p_t$ depending on the history $H_{t-1} = ((\pi_1,r_1),\dots,(\pi_{t-1},r_{t-1}))$ observed so far, and then observes a reward $r_t \in \mathbb{R}$ drawn independently from a fixed conditional distribution $M^\star(\cdot \mid \pi_t)$ (the stochastic rewards assumption). Writing $f^\star(\pi) := \mathbb{E}[r \mid \pi]$ for the mean reward function and $\pi^\star := \arg\max_\pi f^\star(\pi)$ for an optimal decision, the learner's performance is measured by the regret

Because the learner observes a reward only for the action played (bandit feedback), a purely greedy strategy that always plays the current empirical maximizer can commit to a suboptimal action forever, incurring linear regret; some form of deliberate exploration is necessary. The chapter's central construction is the confidence interval: a pair of functions $\underline{f}_t, \bar f_t : \Pi \to \mathbb{R}$ such that, with probability at least $1-\delta$, $f^\star(\pi) \in [\underline{f}_t(\pi), \bar f_t(\pi)]$ for every round $t$ and decision $\pi$ simultaneously. The UCB algorithm plays the optimistic action $\pi_t = \arg\max_\pi \bar f_t(\pi)$ at every round, using the confidence interval built from Hoeffding's inequality around the empirical mean $\hat f_t(\pi)$.

Formalization targets

Goal — Proposition 5 (UCB regret)

holding with probability at least $1-\delta$, for the UCB algorithm using the confidence radius $\sqrt{2\log(2T^2A/\delta)/n_t(\pi)}$ of Eq. (2.19). This is the weakest stable statement the chapter proves: it is optimal up to the log factor, and strengthening it (e.g. to the sharper instance-dependent bound of Remark 10) is explicitly left to later work by the book itself.

Milestones

• Proposition 4 (ε-Greedy regret): $\mathrm{Reg} \lesssim A^{1/3}T^{2/3}\log^{1/3}(AT/\delta)$ — the book's preceding, weaker result, establishing that naive forced exploration already gives sublinear regret, and motivating why an adaptive strategy (UCB) does better.
• Lemma 7 (Optimism): the per-round regret of the optimistic action is bounded by the confidence width at that action.
• Lemma 8 (Confidence width potential lemma): $\sum_{t=1}^T (1/\sqrt{n_t(\pi_t)} \wedge 1) \lesssim \sqrt{AT}$, a pigeonhole bound on how often any one action's confidence interval can still be wide.

Significance

UCB is the prototype of the "optimism in the face of uncertainty" principle that recurs, in increasingly abstract form, throughout the rest of the book: the same two-step argument (Lemma 7 + Lemma 8) reappears for linear bandits, structured bandits via the Decision-Estimation Coefficient, and UCB-VI for tabular reinforcement learning. Formalizing Chapter 2 in full therefore front-loads the proof pattern every later chapter in this series specializes. The result itself is also of standalone interest: the $\sqrt{AT}$ minimax rate is the benchmark every subsequent bandit algorithm in the literature is compared against, and the $A^{1/3}T^{2/3}$-vs-$\sqrt{AT}$ contrast between ε-Greedy and UCB is the standard illustration, in any course on the subject, of why adaptive exploration matters.

No formalization of this exact statement — realizability with respect to a function class $f^\star \in \mathcal{F} = \mathbb{R}^\Pi$ and a generic confidence interval, rather than a per-arm sub-Gaussian empirical mean — currently exists on the platform (see Formalization scope below); the mission both proves this specific regret bound and seeds the generic optimism/potential lemma pair (Lemma 7, Lemma 8) that the book's later, more structured settings specialize.

Difficulty

The natural first attempt — bound the regret of the empirical-mean-greedy algorithm directly — fails outright: on a two-armed instance where one arm is deterministic and the other only slightly better in expectation, the greedy algorithm can commit to the worse arm forever with constant probability, giving linear, not sublinear, regret (§2.1). The obvious fix, ε-Greedy, forces exploration uniformly across all actions regardless of how much is already known about each, so the exploration cost scales with $\varepsilon T$ even for actions whose value is already well determined — this is exactly what caps ε-Greedy at the $T^{2/3}$ rate. UCB's optimism principle resolves this by exploring an action only in proportion to how uncertain it still is; the technical core, isolated in Lemma 7 and Lemma 8, is disentangling "the algorithm made a mistake" from "the algorithm is still uncertain," which are conflated in the naive per-round regret decomposition used for ε-Greedy.

Formalization scope

Both the goal and the milestones fix a finite decision space Fin A, a mean reward function fStar : Fin A → ℝ with fStar π ∈ [0,1], and an optimal decision piStar. Regret is defined generically (Eq. (2.3)) via per-round decision weights p : ℕ → Fin A → ℝ, so it applies uniformly to a randomized algorithm (ε-Greedy) and a deterministic one (UCB, via the point mass at the played action). The book's "with probability at least $1-\delta$" qualifier on both Proposition 4 and Proposition 5 is formalized as the deterministic consequence of the underlying concentration event (Eq. (2.9) and Eq. (2.18) respectively) holding — exactly the move the book's own proofs make ("Let us condition on the event in (2.18) ... "). The concentration events themselves rest on Hoeffding's inequality for adaptive stopping times (Lemma 33) and Bernstein's inequality (Lemma 5), both stated in the book's technical appendix outside this chapter, and are not drafted here; a solver may either take them as a hypothesis (as this mission's statements do) or import/prove them separately. A trivializing formalization is ruled out explicitly: taking δ outside $(0,1)$, or dropping the fStar π ∈ [0,1] hypothesis, would make the stated constants vacuous or false, so both are retained as explicit hypotheses in every theorem. In every ≲ statement (Prop. 4, Lemma 8, Prop. 5) the witnessed constant C is quantified before the instance parameters (A, T, δ, and the realized sequences): ∃ C, 0 < C ∧ ∀ A T δ ..., Reg ≤ C * (rate), not the other order. This is deliberate, not stylistic: quantifying C after the instance lets it depend on A, T, δ, making the bound satisfiable by an arbitrarily large C chosen per instance and hence content-free, which is not what the book's ≲ means (a single constant working uniformly over all instances). Proposition 5's UCB decision rule is stated in the book's own two clauses, not collapsed into a single "maximize the upper confidence bound" rule: the confidence radius of Eq. (2.19) is $+\infty$ at $n_t(\pi)=0$ (an action never yet sampled), so the book's UCB always plays an unsampled action before ever comparing indices, and only compares finite upper confidence bounds once every action has been sampled at least once; the confidence event of Eq. (2.18) is correspondingly assumed only at sampled actions, since the book's own bound is vacuous otherwise. An earlier draft instead capped the radius at $1$ when $n_t(\pi)=0$, which is a true statement about a different algorithm (a sampled action can have index above the capped unsampled index), and was corrected to the book's own rule after moderation. Reuse from the platform's existing bandit library (BanditAlgorithm, Lattimore & Szepesvári) is deliberately avoided: that library's UCB (bandit_ucb_regret_bound, bandit_ucb_minimax_regret_bound) is stated for per-arm 1-sub-Gaussian rewards with $\delta = 1/n^2$ fixed by the horizon, whereas this chapter's UCB is stated for a free failure probability $\delta$ and a generic confidence-interval abstraction (the multi-armed case being $\mathcal{F} = \mathbb{R}^\Pi$ of the book's general realizability framework) — the two are related but not the same statement. Contributions extending the mission with the generic confidence-interval form of Lemma 7/8 applied to other chapters in this series (contextual and structured bandits) are welcome.

Selected references

• T. Lai and H. Robbins, Asymptotically Efficient Adaptive Allocation Rules, Advances in Applied Mathematics, 1985.
• P. Auer, N. Cesa-Bianchi, and P. Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, 2002.
• D. Foster and A. Rakhlin, Foundations of Reinforcement Learning and Interactive Decision Making, arXiv:2312.16730, 2023. https://arxiv.org/abs/2312.16730
• T. Lattimore and C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.

Beneath Exp3, Exp4 and their relatives lies one algorithm: minimize past losses plus a convex regularizer. Chapters 26–28 of Lattimore–Szepesvári develop this unifying view. For a Legendre potential $F$ with Bregman divergence $D_F$, both mirror descent and follow-the-regularised-leader satisfy the master bound $R_n(a) \le \frac{F(a) - F(a_1)}{\eta} + \frac{1}{\eta}\sum_t D_F(a_t, \tilde a_{t+1})$; the negentropy potential on the simplex recovers Exp3 exactly. The goal theorem is the payoff for adversarial linear bandits: FTRL on the unit ball with the self-concordant-flavoured potential $F(a) = -\log(1-\|a\|) - \|a\|$ achieves $R_n \le 2\sqrt{3nd\log n}$ — improving the $\sqrt{d}$ factor over the Exp3-style approach of Chapter 27 and matching the $\Omega(d\sqrt{n})$ lower bound of Mission XI up to logarithms.

Real decisions come with context: a news site chooses an article for a particular user. Competing with the single best arm is then meaningless; the right benchmark is the best mapping from contexts to arms, or more generally the best of $M$ expert policies. Chapter 18 of Lattimore–Szepesvári formalizes this via Exp4 — exponential weighting over experts, fed by the importance-weighted estimator of Mission V. The goal theorem: with learning rate $\eta = \sqrt{2\log(M)/(nk)}$, Exp4 satisfies $R_n \le \sqrt{2nk\log M}$ against the best of $M$ experts. Since $M$ enters only logarithmically, the learner can compete with exponentially large policy classes — the conceptual gateway from bandits to reinforcement learning with function approximation.