Explore-Then-Commit and the Upper Confidence Bound Algorithms

Corresponds to Lattimore & Szepesvári, Chapters 6–10.

Motivation: one problem, five increasingly sharp answers

Every algorithm here attacks the same problem: $k$ arms with unknown means, $n$ rounds, minimize regret. By the regret decomposition, $R_n = \sum_i\Delta_i\mathbb E[T_i(n)]$ , so the whole game is to pull each suboptimal arm as few times as possible while still being sure it is suboptimal. The algorithms differ in how they decide when they’ve seen enough.

Algorithm	Exploration rule	Needs to know	Gap-dependent regret	Worst case
ETC (Ch. 6)	fixed budget $m$ per arm, then commit	$n$ and $\Delta$ , for tuning	$\Delta + \frac4\Delta\big(1 + \log\frac{n\Delta^2}4\big)$ ( $k=2$ )	$O(\sqrt n)$ tuned; $O(n^{2/3})$ untuned
UCB( $\delta$ ) (Ch. 7)	optimism with $\delta = 1/n^2$	$n$	$\sum_i\big(3\Delta_i + \frac{16\log n}{\Delta_i}\big)$	$8\sqrt{nk\log n}$
Asymptotically optimal UCB (Ch. 8)	optimism with $\log f(t)$	nothing (anytime)	$\limsup\frac{R_n}{\log n}\le\sum_i\frac2{\Delta_i}$ , optimal	$O(\sqrt{nk\log n})$
MOSS (Ch. 9)	per-arm confidence $\log^+\frac n{kT_i}$	$n, k$	$O\big(\frac k{\Delta_{\min}}\log\frac{n\Delta_{\min}^2}k\big)$	$39\sqrt{kn}$ , optimal
KL-UCB (Ch. 10)	KL confidence intervals	nothing	$\limsup\frac{R_n}{\log n}\le\sum_i\frac{\Delta_i}{d(\mu_i,\mu^*)}$	(see notes)

ConventionStanding assumption for Chapters 6–9

Every bandit is in $\mathcal E^k_{SG}(1)$ : each arm’s reward noise is 1-subgaussian (definition). Other known constants $\sigma$ follow by scaling rewards (Lemma 5.4). Two points this hides:

every algorithm here relies on knowing $\sigma$ ;
arms may have different subgaussian constants: easy if they’re known (Exercise 7.2), harder if not (Exercise 7.7).

Chapter 10 replaces subgaussianity with Bernoulli or $[0,1]$ rewards.

ConventionNotation

$T_i(t) = \sum_{s\le t}\mathbb I\{A_s = i\}$ is the number of pulls of arm $i$ after round $t$ , and $\hat\mu_i(t) = \frac1{T_i(t)}\sum_{s\le t}\mathbb I\{A_s = i\}X_s$ is its empirical mean. $\hat\mu_{is}$ is the mean of arm $i$ ‘s first $s$ samples, in the reward-stack model where each arm has a pre-drawn stack. Arm 1 is optimal without loss of generality.

Explore-then-commit (Chapter 6)

AlgorithmExplore-then-commit, ETC( $m$ )

Input: the number of exploration pulls per arm, $m$ .

$A_t = \begin{cases}(t \bmod k) + 1 & t\le mk \quad\text{(round-robin exploration)}\\ \arg\max_i\hat\mu_i(mk) & t > mk\quad\text{(commit to the empirical best)}\end{cases}$

Ties in the argmax are broken arbitrarily.

TheoremTheorem 6.1 — Regret of ETC

On any 1-subgaussian bandit with $1\le m\le n/k$ ,

$R_n\le m\sum_{i=1}^k\Delta_i + (n - mk)\sum_{i=1}^k\Delta_i\exp\Big(-\frac{m\Delta_i^2}4\Big)$

ProofDecompose; exploration is deterministic; commitment errors are subgaussian tails

Step 1: Decomposition. $R_n = \sum_i\Delta_i\mathbb E[T_i(n)]$ .

Step 2: Count pulls. Exploration pulls each arm exactly $m$ times. After that, arm $i$ is played in every remaining round iff it was the empirical winner:

$\mathbb E[T_i(n)] = m + (n - mk)\,\mathbb P(A_{mk+1} = i)\le m + (n - mk)\,\mathbb P\big(\hat\mu_i(mk)\ge\max_{j\ne i}\hat\mu_j(mk)\big)$

Step 3: Being beaten by arm $i$ means a gap-sized deviation. The winner must at least beat arm 1:

$\mathbb P\big(\hat\mu_i(mk)\ge\hat\mu_1(mk)\big) = \mathbb P\big((\hat\mu_i - \mu_i) - (\hat\mu_1 - \mu_1)\ge\Delta_i\big)$

Step 4: Subgaussian calculus. Each of $\hat\mu_i - \mu_i$ and $\hat\mu_1 - \mu_1$ is an average of $m$ independent 1-subgaussian terms, so each is $1/\sqrt m$ -subgaussian, and their difference is $\sqrt{2/m}$ -subgaussian (rigorous version: Exercise 6.1). By Theorem 5.3 the probability is at most $\exp\big(-\frac{\Delta_i^2}{2\cdot2/m}\big) = e^{-m\Delta_i^2/4}$ .

∎

IntuitionThe exploration–exploitation trade-off, in one formula

The first term is the price of exploring (every arm pulled $m$ times, needed or not). The second is the price of committing wrongly (with probability about $e^{-m\Delta^2/4}$ , losing $\Delta$ per round for the rest of the game). A larger $m$ shrinks the second term and grows the first.

Tuning the commitment time ( $k = 2$ )

With $\Delta = \Delta_2$ , the bound becomes

$R_n\le m\Delta + (n - 2m)\Delta e^{-m\Delta^2/4}\le m\Delta + n\Delta e^{-m\Delta^2/4} \tag{6.4}$

FormulaOptimal $m$ and the resulting bound

$m = \max\Big\{1,\ \Big\lceil\frac4{\Delta^2}\log\frac{n\Delta^2}4\Big\rceil\Big\} \tag{6.5}$

$R_n\le\min\Big\{n\Delta,\ \Delta + \frac4\Delta\Big(1 + \max\Big\{0,\ \log\frac{n\Delta^2}4\Big\}\Big)\Big\} \tag{6.6}$

TheoremWorst-case bound (Exercise 6.2)

(6.6) implies $R_n\le\Delta + C\sqrt n$ for a universal constant $C$ , so $R_n\le1 + C\sqrt n$ when $\Delta\le1$ .

DerivationMaximize the gap-dependent term over

\Delta

If $\Delta\le2/\sqrt n$ , then $n\Delta\le2\sqrt n$ . Otherwise set $x = \Delta\sqrt n/2 > 1$ , so $\frac4\Delta = \frac{2\sqrt n}x$ and $\log\frac{n\Delta^2}4 = 2\log x$ :

$\frac4\Delta\Big(1 + \log\frac{n\Delta^2}4\Big) = 2\sqrt n\cdot\frac{1 + 2\log x}x$

The derivative vanishes where $2 - (1 + 2\log x) = 0$ , i.e. $x = \sqrt e$ , giving maximum value $2/\sqrt e\approx1.21$ . So the term is at most $2.5\sqrt n$ , and $C = 2.5$ works. (Constant worked here.)

DefinitionWorst-case versus gap-dependent bounds

Worst-case (problem-free, problem-independent, gap-free): depends only on $n$ and the environment class, as in (6.7).
Gap- (problem-, distribution-, instance-) dependent: depends on the specific instance through the gaps, as in (6.6).

WarningWorst-case bounds need bounded rewards

Without a bound such as $\Delta\le1$ , the worst-case regret of ETC, and of every reasonable algorithm that tries each arm at least once, is infinite: an adversary makes the bad arm arbitrarily bad. “Worst-case” always means “over a class with bounded reward range”.

WarningThe tuning cheats

(6.5) uses $\Delta$ , which is never known. The horizon is sometimes known; the gap almost never is.

Horizon-only tuning: $m\approx n^{2/3}$ gives $R_n\le(\Delta + C)n^{2/3}$ for all instances, but no constant gives $\Delta + Cn^{2/3}$ (Exercise 6.5a).
Data-dependent commitment: alternate arms until a confidence-interval test separates them, which achieves $\Delta + \frac{C\log n}\Delta$ and hence $\Delta + C\sqrt{n\log n}$ . A sharper stopping test achieves $\Delta + \frac C\Delta\log\max\{e, n\Delta^2\}$ and hence $\Delta + C\sqrt n$ (Exercise 6.5b–e).

ExampleExperiment 6.1 — Theory versus practice

Gaussian arms with means $0$ and $-\Delta$ , $n = 1000$ , ETC tuned by (6.5), averaged over $10^5$ runs. The bound (6.6) tracks the true expected regret closely as $\Delta$ ranges over $[0,1]$ . The regret peaks at intermediate $\Delta$ : small gaps cost little per mistake, and large gaps are found quickly. ETC’s immediate expected regret is also monotonically non-increasing in $t$ , though not smoothly.

WarningExpected regret hides a bimodal distribution (Exercise 6.9)

With $\Delta = \frac1{10}$ and $n = 2000$ , both the expected regret and the standard deviation of the pseudo-regret depend sharply on $m$ . ETC’s regret is nearly two-valued: about $m\Delta$ if it commits correctly, and about $n\Delta$ if it commits wrongly. A standard deviation is a poor summary of such a distribution.

Variants and notes

DefinitionAnytime algorithm and the doubling trick

An algorithm is anytime if it needs no advance knowledge of $n$ . ETC isn’t. The doubling trick restarts a horizon- $n_\ell$ algorithm on epochs of lengths $n_1 < n_2 < \cdots$ (without resetting the global clock). If the base algorithm has regret at most $f_{n}(\nu)$ up to horizon $n$ , the restarted algorithm has $R_n\le\sum_{\ell\le\ell_{\max}}f_{n_\ell}(\nu)$ (Exercise 6.6).

$f_n = \sqrt n$ with $n_\ell = 2^{\ell-1}$ : $R_n\le C\sqrt n$ . The geometric sum is dominated by its last term.
$f_n = g\log n$ with $n_\ell = 2^{\ell-1}$ : $R_n = O(g\log^2n)$ , because every epoch pays a log. Faster-growing epochs such as $n_\ell = 2^{2^\ell}$ recover $O(g\log n)$ .
Cons: restarts throw away data, the transient behaviour is poor, and it is wasteful in practice. Natively anytime algorithms are preferable. (Nothing here uses stochasticity, so it also applies to adversarial and contextual settings.)

Algorithmε-greedy (Exercise 6.7)

Play each arm once. Then in round $t$ , play the empirical best with probability $1 - \varepsilon_t$ , and otherwise a uniformly random arm.

A constant $\varepsilon$ gives linear regret: $R_n/n\to\frac\varepsilon k\sum_i\Delta_i$ .
$\varepsilon_t = \min\{1, \frac{Ck}{t\Delta_{\min}^2}\}$ gives $R_n\le C'\sum_i\big(\Delta_i + \frac{\Delta_i}{\Delta_{\min}^2}\log\max\{e, \frac{n\Delta_{\min}^2}k\}\big)$ , but that requires knowing $\Delta_{\min}$ .

AlgorithmPhased elimination (Exercise 6.8; Auer–Ortner)

Keep an active set $\mathcal A_\ell$ , starting from all arms. In phase $\ell$ , pull every active arm $m_\ell$ times, using only that phase’s samples for the means $\hat\mu_{i,\ell}$ , and keep

$\mathcal A_{\ell+1} = \{i : \hat\mu_{i,\ell} + 2^{-\ell}\ge\max_{j\in\mathcal A_\ell}\hat\mu_{j,\ell}\}$

Phase $\ell$ aims to eliminate every arm with $\Delta_i\ge2^{-\ell}$ . With suitable $m_\ell\approx2^{2\ell}\log(\cdot)$ :

the optimal arm is wrongly eliminated in a phase with probability at most $k\,e^{-m_\ell2^{-2\ell}/4}$ ;
$R_n\le C\sum_{i:\Delta_i>0}\big(\Delta_i + \frac{\log\max\{e, n\Delta_i^2\}}{\Delta_i}\big)$ ;
the worst case is $\sum_i\Delta_i + C'\sqrt{nk\log k}$ .

RemarkHistory

Robbins (1952) used “certainty equivalence with forcing”: play the empirical best, except on prescribed exploration times. Anscombe (1963) largely solved the Gaussian clinical-trial version. Later relatives include epoch-greedy (contextual bandits) and forced exploration / PEGE (linear bandits). Garivier et al. (2016) showed that all explore-then-commit and elimination policies are asymptotically suboptimal (Chapter 16).

The upper confidence bound algorithm (Chapter 7)

The optimism principle

IntuitionOptimism in the face of uncertainty

Act as if the environment is as nice as plausibly possible. In a new country, choosing between the unknown local cuisine and a familiar chain, optimism says: the local food might be amazing, so try it. After a few visits the statistics settle the question. Pessimism never tries it and may miss something wonderful forever.

ImportantWhy optimism gives sublinear regret

Give each arm an upper confidence bound that overestimates its mean with high probability. Then:

the optimal arm’s index is at least $\mu^*$ (with high probability);
a suboptimal arm is played only if its index beats the optimal arm’s, hence only if its index is at least $\mu^*$ ;
every play of that arm shrinks its confidence width, so its index soon falls below $\mu^*$ .

Optimism is self-correcting: overestimates attract plays, and plays remove overestimates.

DefinitionUCB index (7.2)

From (5.6), $\mathbb P\big(\mu\ge\hat\mu + \sqrt{2\log(1/\delta)/n}\big)\le\delta$ . So

$\mathrm{UCB}_i(t-1,\delta) = \begin{cases}\infty & T_i(t-1) = 0,\\[2pt] \hat\mu_i(t-1) + \sqrt{\dfrac{2\log(1/\delta)}{T_i(t-1)}} & \text{otherwise.}\end{cases}$

The added term is the exploration bonus (confidence width). An algorithm that plays the arm maximizing such a per-arm score is an index algorithm.

Component	Detail
Inputs	Arm $i$ ‘s empirical mean and pull count; the confidence level $\delta$ .
Output	A plausible optimistic value for $\mu_i$ .
Large when	The arm looks good ( $\hat\mu_i$ large) or is under-explored ( $T_i$ small).

AlgorithmUCB( $\delta$ ) — Algorithm 3

For $t = 1, \ldots, n$ : play $A_t = \arg\max_i\mathrm{UCB}_i(t-1,\delta)$ , observe $X_t$ , and update.

IntuitionWhy this particular form

If arm 1 has been played far more often, then $\hat\mu_1\approx\mu_1$ , and to keep playing it the algorithm should be confident that every other arm is worse:

$\hat\mu_i(t-1) + \sqrt{\frac{2\log(1/\delta)}{T_i(t-1)}}\le\mu_1\approx\hat\mu_1(t-1) + \sqrt{\frac{2\log(1/\delta)}{T_1(t-1)}} \tag{7.3}$

Two questions remain: whether the width can be made much narrower (the lower bounds say not for subgaussian noise), and how to choose $\delta$ . If $\delta$ is too large, the optimal arm’s index may drop below $\mu^*$ and it gets abandoned, at a cost of linear regret. If $\delta$ is too small, suboptimal arms get over-explored. A first guess is $\delta\approx1/n$ ; the analysis below needs $\delta = 1/n^2$ .

WarningThe sample size inside the index is random (Exercise 7.1)

(5.6) holds for a fixed number of samples, but $T_i(t-1)$ depends on the data.

If $T$ is independent of the samples, the bound still holds.
If $T$ is a stopping time, it can fail with probability 1: by the law of the iterated logarithm, $\limsup\frac{\sum_{t\le n}X_t}{\sqrt{2n\log\log n}} = 1$ , so the running mean eventually exceeds any fixed-level bound. Stop then.
Fix: pay a union-bound penalty, $\mathbb P\big(\hat\mu - \mu\ge\sqrt{2\log(T(T+1)/\delta)/T}\big)\le\delta$ . $\log\log T$ almost suffices (Garivier 2013; Chapter 20).

The proofs below avoid this by union-bounding over all possible sample counts $s\in[n]$ .

Regret analysis

TheoremTheorem 7.1 — Gap-dependent regret of UCB

With $\delta = 1/n^2$ , on any $k$ -armed 1-subgaussian bandit,

$R_n\le3\sum_{i=1}^k\Delta_i + \sum_{i:\Delta_i>0}\frac{16\log n}{\Delta_i}$

ProofThe good-event argument

Fix a suboptimal arm $i$ and a constant $u_i\in[n]$ (chosen later).

Step 1: The good event.

$G_i = \Big\{\mu_1 < \min_{t\in[n]}\mathrm{UCB}_1(t,\delta)\Big\}\cap\Big\{\hat\mu_{iu_i} + \sqrt{\frac{2\log(1/\delta)}{u_i}} < \mu_1\Big\}$

The optimal arm is never under-estimated, and after $u_i$ samples, arm $i$ ‘s index is already below $\mu_1$ .

Step 2: On $G_i$ , arm $i$ is pulled at most $u_i$ times. Suppose not. Then some round $t$ has $T_i(t-1) = u_i$ and $A_t = i$ . But

$\mathrm{UCB}_i(t-1,\delta) = \hat\mu_{iu_i} + \sqrt{\frac{2\log(1/\delta)}{u_i}} < \mu_1 < \mathrm{UCB}_1(t-1,\delta)$

so arm $i$ isn’t the argmax, which is a contradiction. Since $T_i(n)\le n$ always,

$\mathbb E[T_i(n)]\le u_i + n\,\mathbb P(G_i^c) \tag{7.5}$

Step 3: The optimal arm fails rarely. Union bound over its possible sample counts:

$\mathbb P\Big(\mu_1\ge\min_t\mathrm{UCB}_1(t,\delta)\Big)\le\sum_{s=1}^n\mathbb P\Big(\mu_1\ge\hat\mu_{1s} + \sqrt{\frac{2\log(1/\delta)}s}\Big)\le n\delta \tag{7.7}$

Step 4: Arm $i$ ‘s index falls by $u_i$ samples. Choose $u_i$ so that $\Delta_i - \sqrt{2\log(1/\delta)/u_i}\ge c\Delta_i$ for some $c\in(0,1)$ . Then

$\mathbb P\Big(\hat\mu_{iu_i} + \sqrt{\frac{2\log(1/\delta)}{u_i}}\ge\mu_1\Big) = \mathbb P\Big(\hat\mu_{iu_i} - \mu_i\ge\Delta_i - \sqrt{\cdot}\Big)\le\mathbb P(\hat\mu_{iu_i} - \mu_i\ge c\Delta_i)\le e^{-u_ic^2\Delta_i^2/2}$

Step 5: Combine and tune. With the smallest valid $u_i = \big\lceil\frac{2\log(1/\delta)}{(1-c)^2\Delta_i^2}\big\rceil$ and $\delta = 1/n^2$ ,

$\mathbb E[T_i(n)]\le\Big\lceil\frac{2\log n^2}{(1-c)^2\Delta_i^2}\Big\rceil + 1 + n^{1 - 2c^2/(1-c)^2}$

The last term is polynomial in $n$ unless $2c^2/(1-c)^2\ge1$ . Taking $c = \frac12$ makes it at most 1, and gives $\mathbb E[T_i(n)]\le3 + \frac{16\log n}{\Delta_i^2}$ . Multiply by $\Delta_i$ and sum.

∎

IntuitionThe template for every optimistic analysis

Split “arm $i$ was played” into (a) the optimal arm’s index failed (rare by concentration and a union bound) or (b) arm $i$ ‘s index is still high (can only last about $\log(1/\delta)/\Delta_i^2$ pulls). Every UCB-style proof in the book is a refinement of this split.

TheoremTheorem 7.2 — Worst-case regret of UCB

With $\delta = 1/n^2$ , on any $\nu\in\mathcal E^k_{SG}(1)$ ,

$R_n\le8\sqrt{nk\log n} + 3\sum_{i=1}^k\Delta_i$

ProofSplit arms at a threshold gap

\Delta

$R_n = \sum_{\Delta_i<\Delta}\Delta_i\mathbb E[T_i(n)] + \sum_{\Delta_i\ge\Delta}\Delta_i\mathbb E[T_i(n)]\le n\Delta + \sum_{\Delta_i\ge\Delta}\Big(3\Delta_i + \frac{16\log n}{\Delta_i}\Big)\le n\Delta + \frac{16k\log n}\Delta + 3\sum_i\Delta_i$

The small-gap arms together get at most $n$ pulls. Then choose $\Delta = \sqrt{16k\log n/n}$ .

∎

IntuitionSmall gaps are cheap, large gaps are found fast

Arms with tiny gaps cost little per pull even if pulled often. Arms with big gaps are pulled rarely. The worst case sits in between, at $\Delta\approx\sqrt{k\log n/n}$ . The same balancing argument converts any $\sum_i\frac{\log n}{\Delta_i}$ bound into $\sqrt{nk\log n}$ .

RemarkHow good is this?

The additive $\sum_i\Delta_i$ is unavoidable: every reasonable algorithm must try every arm once.
No algorithm beats $O(\sqrt{nk})$ in the worst case (lower-bounds-for-finite-armed-bandits, Chapter 15). MOSS removes the $\sqrt{\log n}$ .

ExampleExperiment 7.1 — UCB versus ETC

$k = 2$ , Gaussian arms, $n = 1000$ . ETC with the gap-optimal $m$ (which requires knowing $\Delta$ ) beats parameter-free UCB, but only slightly. ETC with any fixed $m$ (25, 50, 75 or 100) loses badly for some range of $\Delta$ : a bump, a dip, then linear growth as committing wrongly becomes costly. A variant of UCB from Chapter 8 even beats optimally tuned ETC.

Notes and extensions

RemarkTwo problems with $\delta = 1/n^2$

A slightly smaller $\delta$ improves both regret and empirical performance, and depending on $n$ means the algorithm isn’t anytime. Chapter 8 fixes both by making the confidence level depend on $t$ .

RemarkIndependence can be relaxed

All results hold if, with $\mathcal H_{t-1}$ the history,

$\mathbb E[X_t\mid\mathcal H_{t-1},A_t] = \mu_{A_t}, \qquad \mathbb E\big[e^{\lambda(X_t - \mu_{A_t})}\mid\mathcal H_{t-1},A_t\big]\le e^{\lambda^2/2} \tag{7.11–7.12}$

i.e. conditionally centred, conditionally subgaussian noise. The proofs then use martingale concentration (Chapter 20).

WarningOptimism isn’t universal

It works well when (i) playing an action reveals that action’s quality and (ii) actions reveal nothing about other actions. If (i) fails, even sublinear regret can be lost. If (ii) fails, optimism may skip a low-reward, high-information action whose information would pay off. An example comes with linear bandits (Chapter 25).

RemarkOptimism bias

Psychologists document an “optimism bias” in humans and animals, among the most robust biases known. The authors note that its mathematical justification as a driver of exploration seems to have escaped notice in those fields.

TheoremKnown per-arm scales (Exercise 7.2)

If arm $i$ is $\sigma_i$ -subgaussian with known $\sigma_i$ , scale its bonus to $\sigma_i\sqrt{2\log(1/\delta)/T_i}$ . The regret becomes $O\big(\sum_{i:\Delta_i>0}(\Delta_i + \frac{\sigma_i^2\log n}{\Delta_i})\big)$ , independent of the optimal arms’ $\sigma$ : an optimal arm’s noise only matters through its lower deviations, which the union bound handles cheaply.

TheoremAdapting to the variance: UCB-V (Exercise 7.6)

For rewards in $[0,b]$ , the empirical Bernstein inequality gives

$\mathbb P\Big(|\hat\mu - \mu|\ge\sqrt{\frac{2\hat\sigma^2}n\log\frac3\delta} + \frac{3b}n\log\frac3\delta\Big)\le\delta$

with $\hat\sigma^2$ the empirical variance. An index built on it achieves

$R_n\le C\sum_{i:\Delta_i>0}\Big(\Delta_i + \big(b + \frac{\sigma_i^2}{\Delta_i}\big)\log n\Big) \tag{7.14}$

This replaces UCB’s $\frac b{\Delta_i}$ with $b + \frac{\sigma_i^2}{\Delta_i}$ , a big gain for low-variance arms, and essentially unimprovable (Exercise 16.7). See Bernstein.

TheoremHeavy tails: median of means (Exercise 7.7)

Split $n$ samples into $m\approx8\log(e^{1/8}/\delta)$ blocks and take the median of the block means. With only a finite variance,

$\mathbb P\Big(\hat\mu_M + \sqrt{\frac{192\sigma^2}n\log\frac{e^{1/8}}\delta}\le\mu\Big)\le\delta$

A UCB built on it gets $R_n\le C\sum_i\big(\Delta_i + \frac{\sigma^2\log n}{\Delta_i}\big)$ on $\mathcal E^k_V(\sigma^2)$ . Subgaussianity is relaxed to a finite variance at the cost of constants. Alternatives include truncation with empirical Bernstein (which needs to know roughly where the mean is), Catoni’s estimator, and Huber loss. Bubeck et al. (2013) handle even infinite variance, with worse regret.

RemarkLazy updates (Exercises 7.4–7.5)

Phased UCB recomputes the argmax only at phase boundaries (lengths $1, 2, 4, \ldots$ ), or keeps playing the chosen arm until its count grows by a factor $\alpha$ . The regret degrades only mildly. This matters with delayed or batched feedback, communication costs, or expensive index computations.

Asymptotically optimal UCB (Chapter 8)

AlgorithmAlgorithm 6

Play each arm once, then

$A_t = \arg\max_i\ \hat\mu_i(t-1) + \sqrt{\frac{2\log f(t)}{T_i(t-1)}},\qquad f(t) = 1 + t\log^2t$

It is anytime: the confidence level depends on $t$ , not $n$ .

TheoremTheorem 8.1 — Finite-time and asymptotic regret

On any 1-subgaussian bandit,

$R_n\le\sum_{i:\Delta_i>0}\inf_{\varepsilon\in(0,\Delta_i)}\Delta_i\Big(1 + \frac5{\varepsilon^2} + \frac{2\big(\log f(n) + \sqrt{\pi\log f(n)} + 1\big)}{(\Delta_i - \varepsilon)^2}\Big) \tag{8.1}$

$\limsup_{n\to\infty}\frac{R_n}{\log n}\le\sum_{i:\Delta_i>0}\frac2{\Delta_i} \tag{8.2}$

With $\varepsilon = \Delta_i/2$ , $R_n\le\sum_i\big(\Delta_i + \frac1{\Delta_i}(8\log f(n) + 8\sqrt{\pi\log f(n)} + 28)\big)$ , so $R_n\le C\sum_i(\Delta_i + \frac{\log n}{\Delta_i})$ , and the usual argument gives the worst case $C\sum_i\Delta_i + 2\sqrt{Cnk\log n}$ .

ImportantWhy the messier bound

(8.3) has the right order but the wrong constant: dividing by $\log n$ gives $8/\Delta_i$ . Only the $\varepsilon\to0$ version (8.2) achieves $2/\Delta_i$ , which Lai and Robbins showed no reasonable policy can beat on any instance (lower-bounds-for-finite-armed-bandits, Chapters 15–16).

LemmaLemma 8.2 — How long an index stays high

Let $X_t$ be independent and 1-subgaussian with mean 0, $\hat\mu_t = \frac1t\sum_{s\le t}X_s$ , $\varepsilon, a > 0$ , and $u = 2a/\varepsilon^2$ . Then

$\mathbb E\Big[\sum_{t=1}^n\mathbb I\Big\{\hat\mu_t + \sqrt{\frac{2a}t}\ge\varepsilon\Big\}\Big]\le1 + \frac2{\varepsilon^2}\big(a + \sqrt{\pi a} + 1\big)$

ProofCount the first

u

rounds for free, then integrate the subgaussian tail

$\mathbb E[\kappa]\le u + \sum_{t\ge\lceil u\rceil}\mathbb P\Big(\hat\mu_t\ge\varepsilon - \sqrt{\frac{2a}t}\Big)\le u + \sum_{t\ge\lceil u\rceil}\exp\Big(-\frac t2\Big(\varepsilon - \sqrt{\frac{2a}t}\Big)^2\Big)\le1 + u + \int_u^\infty(\cdot)\,dt$

Substituting $s = \varepsilon\sqrt t - \sqrt{2a}$ evaluates the integral to $\frac2{\varepsilon^2}(\sqrt{\pi a} + 1)$ , and $u = \frac{2a}{\varepsilon^2}$ supplies the remaining term.

∎

IntuitionThe right order

The index $\hat\mu_t + \sqrt{2a/t}$ can’t drop below $\varepsilon$ before $t\approx2a/\varepsilon^2$ , because the bonus alone exceeds $\varepsilon$ until then. The lemma says it doesn’t stay up much longer.

ProofProof of Theorem 8.1: allow the optimal index to dip by ε

Step 1: Split.

$T_i(n)\le\sum_t\mathbb I\Big\{\hat\mu_1(t-1) + \sqrt{\frac{2\log f(t)}{T_1(t-1)}}\le\mu_1 - \varepsilon\Big\} + \sum_t\mathbb I\Big\{\hat\mu_i(t-1) + \sqrt{\frac{2\log f(t)}{T_i(t-1)}}\ge\mu_1 - \varepsilon,\ A_t = i\Big\}$

Step 2: The optimal arm dips rarely. Union bound over its sample count $s$ :

$\mathbb E[\text{first sum}]\le\sum_t\sum_s\exp\Big(-\frac s2\Big(\sqrt{\frac{2\log f(t)}s} + \varepsilon\Big)^2\Big)\le\sum_t\frac1{f(t)}\sum_se^{-s\varepsilon^2/2}\le\frac5{\varepsilon^2}$

using $(a+b)^2\ge a^2 + b^2$ . The function $f$ was chosen so that $\sum_t1/f(t)$ converges (Exercise 8.1: the geometric sum is at most $2/\varepsilon^2$ , and $\sum_t\frac1{1 + t\log^2t}$ is at most about $2.5$ ).

Step 3: Arm $i$ ‘s index. Replace $f(t)$ by $f(n)$ (which only makes the event larger), index by arm $i$ ‘s own sample count (each count occurs in at most one round with $A_t = i$ ), and apply Lemma 8.2 with $a = \log f(n)$ and gap $\Delta_i - \varepsilon$ .

Step 4: Asymptotics. Choose $\varepsilon = \log^{-1/4}n$ and let $n\to\infty$ .

∎

ImportantThe trick

Chapter 7 needed the optimal arm’s index to stay above $\mu_1$ , which forced $\delta\approx1/n^2$ and a doubled $\log$ . Here it only needs to stay above $\mu_1 - \varepsilon$ , and occasional dips are allowed as long as their total expected number is bounded ( $5/\varepsilon^2$ ). That permits a narrower confidence width, $\log f(t)\approx\log t$ , and recovers the optimal constant 2.

RemarkNotes

Any $f(t) = t\log^\alpha t$ with $\alpha > 0$ works, with messier algebra. For Gaussian rewards, $f(t) = t$ or even slightly less suffices.
Asymptotics can mislead: lower-order terms can dominate in every practical regime.
History: Lai–Robbins (1985) proved (8.2) is optimal and achievable; Lai (1987), Katehakis–Robbins (1995) and Agrawal (1995) gave UCB-type asymptotic analyses; finite-time versions came later.

ExampleOne-armed bandits (Exercises 8.2–8.3)

Arm 2 pays a known mean 0, and arm 1 is $\mathcal N(\mu_1,1)$ . Standard UCB wastes optimism on arm 2. Use the index $\hat\mu_1 + \sqrt{2\log f(t)/T_1}$ against the fixed value 0. Then $\limsup R_n/\log n$ is 0 if $\mu_1\ge0$ and $-2/\mu_1 = 2/\Delta$ if $\mu_1 < 0$ . Optimism is for uncertainty; don’t spend it on what you know.

MOSS: minimax optimality (Chapter 9)

The problem. UCB’s worst case is $O(\sqrt{nk\log n})$ , and phased elimination gets $O(\sqrt{nk\log k})$ . The lower bound is $\Omega(\sqrt{nk})$ . Removing the log requires a confidence level that depends on each arm’s own count.

AlgorithmMOSS — Algorithm 7

Input $n, k$ . Play each arm once, then

$A_t = \arg\max_i\ \hat\mu_i(t-1) + \sqrt{\frac4{T_i(t-1)}\log^+\Big(\frac n{kT_i(t-1)}\Big)},\qquad\log^+(x) = \log\max\{1,x\}$

(“Minimax Optimal Strategy in the Stochastic case”, Audibert–Bubeck 2009.)

IntuitionStop being optimistic about well-explored arms

Once $T_i\ge n/k$ , the bonus is zero: an arm that has received its “fair share” of the budget gets no exploration help. Arms pulled rarely get a bonus of order $\sqrt{\log(n/(kT_i))/T_i}$ , which is smaller than UCB’s $\sqrt{\log n/T_i}$ . MOSS explores less and saves the $\sqrt{\log n}$ factor.

TheoremTheorem 9.1 — Minimax regret of MOSS

$R_n\le39\sqrt{kn} + \sum_{i=1}^k\Delta_i$

TheoremTheorem 9.2 — Maximal Hoeffding inequality

If $X_1, \ldots, X_n$ are independent and $\sigma$ -subgaussian and $S_t = \sum_{s\le t}X_s$ , then

$\mathbb P(\exists t\le n : S_t\ge\varepsilon)\le\exp\Big(-\frac{\varepsilon^2}{2n\sigma^2}\Big) \tag{9.1}$

This is the same bound as for $S_n$ alone, but now uniform over all $t\le n$ .

ProofDoob’s submartingale inequality applied to

e^{\lambda S_t}

$e^{\lambda S_t}$ is a nonnegative submartingale (Exercise 9.1, by Jensen). Doob’s maximal inequality for submartingales gives

$\mathbb P\Big(\max_{t\le n}e^{\lambda S_t}\ge e^{\lambda\varepsilon}\Big)\le\frac{\mathbb E[e^{\lambda S_n}]}{e^{\lambda\varepsilon}}\le\exp\Big(\frac{n\sigma^2\lambda^2}2 - \lambda\varepsilon\Big)$

Then take $\lambda = \varepsilon/(n\sigma^2)$ .

∎

LemmaLemma 9.3 — The peeling device

For independent 1-subgaussian $X_s$ with mean 0, $\delta\in(0,1)$ and $\Delta > 0$ ,

$\mathbb P\Big(\exists s\ge1 : \hat\mu_s + \sqrt{\frac4s\log^+\Big(\frac1{s\delta}\Big)} + \Delta\le0\Big)\le\frac{15\delta}{\Delta^2}$

ProofUnion bound over a geometric grid of times

Step 1: Peel. Split $s\ge1$ into blocks $[2^j, 2^{j+1}]$ . Within block $j$ , make the event larger by replacing $s$ with the block’s endpoints, then apply the maximal inequality (9.1) on $[0, 2^{j+1}]$ :

$\mathbb P(\cdot)\le\sum_{j\ge0}\exp\Big(-\frac{\big(\sqrt{2^{j+2}\log^+\frac1{2^{j+1}\delta}} + 2^j\Delta\big)^2}{2^{j+2}}\Big)$

Step 2: Algebra. Using $(a+b)^2\ge a^2 + b^2$ , each term is at most $\delta2^{j+1}\exp(-\Delta^22^{j-2})$ . The terms are unimodal in $j$ , so the sum is at most the largest term ( $8\delta/(e\Delta^2)$ ) plus an integral. Both are $O(\delta/\Delta^2)$ , and the total is at most $15\delta/\Delta^2$ .

∎

IntuitionPeeling

A union bound over every time $s$ would cost a factor $n$ . A union bound over geometrically growing blocks costs only the number of blocks, about $\log n$ , and the maximal inequality handles each block at the price of its endpoint. This device also proves the law of the iterated logarithm.

ProofProof of Theorem 9.1: control the expected optimism deficit

Step 1: The deficit. Define

$\Delta = \Big(\mu_1 - \min_{s\le n}\Big(\hat\mu_{1s} + \sqrt{\frac4s\log^+\frac n{ks}}\Big)\Big)^+$

This is how far the optimal arm’s index ever drops below its mean. Arms with gaps above $2\Delta$ are rarely played. Arms with gaps below $2\Delta$ may be played often, but $\Delta$ is small on average.

Step 2: Split the regret. $R_n\le\mathbb E\big[2n\Delta + 8\sqrt{kn} + \sum_{i:\Delta_i>\max\{2\Delta, 8\sqrt{k/n}\}}\Delta_iT_i(n)\big]$ .

Step 3: The deficit is small on average. By the tail-integral formula and Lemma 9.3 (with $\delta = k/n$ ), $\mathbb E[2n\Delta]\le2n\int_0^\infty\min\{1, \frac{15k}{nx^2}\}dx\le16\sqrt{kn}$ .

Step 4: Large-gap arms. For $\Delta_i > 2\Delta$ , the optimal index stays above $\mu_i + \Delta_i/2$ , so $T_i(n)\le\kappa_i$ , the number of samples at which arm $i$ ‘s index exceeds $\mu_i + \Delta_i/2$ . Lemma 8.2 gives $\Delta_i\mathbb E[\kappa_i]\le\Delta_i + 15\sqrt{n/k}$ when $\Delta_i\ge8\sqrt{k/n}$ . Summing over at most $k$ arms gives $15\sqrt{nk} + \sum\Delta_i$ .

Total: $(16 + 8 + 15)\sqrt{kn} + \sum\Delta_i = 39\sqrt{kn} + \sum\Delta_i$ .

∎

ImportantOptimism in expectation, not with high probability

UCB’s analysis needed the optimal arm to be optimistic with high probability. MOSS’s bonus is too small for that. Instead the proof bounds the expected amount of pessimism, and lets the arms it harms (those with gaps below $2\Delta$ ) be ones that cost little anyway.

Two problems with MOSS

WarningMOSS can be much worse than UCB

Take Gaussian arms with $n = k^3$ , $\mu_1 = 0$ , $\mu_2 = -\sqrt{k/n}$ , and $\mu_i = -1$ for $i > 2$ . Then

$R_n^{\mathrm{UCB}} = O(k\log k), \qquad R_n^{\mathrm{MOSS}} = \Omega(\sqrt{kn}) = \Omega(k^2)$

Minimax and asymptotic optimality both hide this. Only fully finite-time, instance-dependent bounds reveal it.

WarningPushing expected regret down makes the regret unstable

With two arms and a well-tuned algorithm, the pseudo-regret is roughly bimodal:

$\hat R_n\approx\begin{cases}n\Delta & \text{with probability }\delta\ (\text{optimal arm misidentified}),\\ \frac1\Delta\log\frac1\delta & \text{otherwise,}\end{cases}\qquad R_n = O\Big(n\Delta\delta + \frac1\Delta\log\frac1\delta\Big)$

Minimizing the mean ( $\delta\approx1/(n\Delta^2)$ ) gives $R_n = O(\frac1\Delta(1 + \log n\Delta^2))$ , but on the failure event $F$ the second moment $\mathbb E[\mathbb I_F\hat R_n^2] = \Omega(n)$ .
A slightly smaller $\delta$ ( $= (n\Delta)^{-2}$ ) barely raises the mean, to $O(\frac1\Delta(\frac1n + \log n^2\Delta^2))$ , while $\mathbb E[\mathbb I_F\hat R_n^2] = O(1)$ .

The last log factor of expected regret is bought with heavy tails.

Notes

RemarkFixes and refinements

Asymptotics: MOSS has $\limsup\frac{R_n}{\log n}\le\sum_i\frac4{\Delta_i}$ . Replacing the 4 with 2 and peeling on finer grids $[\xi^j,\xi^{j+1}]$ (Garivier 2013) recovers the optimal constant. For Gaussian noise, Brownian-motion boundary-crossing bounds avoid peeling altogether (Exercise 9.4: the Bachelier–Lévy formula via the method of images, and tangent bounds for concave boundaries).
UCB*: the index $\hat\mu_i + \sqrt{\frac4{T_i}\log^+\frac n{T_i}}$ (no $k$ ) is never worse than UCB, and has worst case $O(\sqrt{nk\log k})$ (Exercise 9.3). “Improved UCB” (phased elimination) is the same idea in disguise.
Best of both: optimally confident UCB, $\hat\mu_i + \sqrt{\frac{2(1+\varepsilon)}{T_i}\log\frac nt}$ , and AdaUCB, with confidence level $\log\frac n{\sum_j\min\{T_i, \sqrt{T_iT_j}\}}$ , are minimax optimal and never worse than UCB. AdaUCB is also asymptotically optimal.
Anytime MOSS: Degenne–Perchet (2016).

Bernoulli rewards and KL-UCB (Chapter 10)

The problem. Bernoulli rewards (clicks, conversions) are $\frac12$ -subgaussian for every mean, so UCB already applies. But a Bernoulli arm’s variance $\mu(1-\mu)$ depends on its mean, and near 0 or 1 the empirical mean concentrates much faster than the worst case. Confidence intervals should shrink accordingly.

Concentration for sums of Bernoulli random variables

DefinitionRelative entropy between Bernoullis (Def. 10.1)

$d(p,q) = p\log\frac pq + (1-p)\log\frac{1-p}{1-q}$

with limits at the boundary: $d(0,q) = \log\frac1{1-q}$ , $d(1,q) = \log\frac1q$ , and $d(p,0)$ , $d(p,1)$ equal 0 if $p = q$ and $\infty$ otherwise. This is the relative entropy $D(\mathcal B(p)\Vert\mathcal B(q))$ , and it is the large-deviation rate of a Bernoulli average.

Component	Detail
Signature	$d : [0,1]\times[0,1]\to[0,\infty]$
First argument	The observed (or hypothesized) frequency.
Second argument	The true (or reference) mean.
Asymmetric	$d(p,q)\ne d(q,p)$ in general.

LemmaLemma 10.2 — Properties of $d$

For $p, q, \varepsilon\in[0,1]$ :

$d(\cdot,q)$ and $d(p,\cdot)$ are convex, with unique minimizers at $q$ and $p$ respectively.
Pinsker: $d(p,q)\ge2(p-q)^2$ .
If $p\le q - \varepsilon\le q$ , then $d(p, q-\varepsilon)\le d(p,q) - d(q-\varepsilon, q)\le d(p,q) - 2\varepsilon^2$ .

ProofConvexity from the binary entropy; Pinsker by calculus; (3) by linearity in

p

(1) $d(\cdot,q)$ is the negative binary entropy $h(p) = p\log p + (1-p)\log(1-p)$ , with $h'' = \frac1p + \frac1{1-p} > 0$ , plus a linear function of $p$ . $d(p,\cdot)$ is $h(p)$ plus the convex functions $p\log\frac1q$ and $(1-p)\log\frac1{1-q}$ . And $d(p,q) > 0$ unless $p = q$ .

(2) $g(x) = d(p, p+x) - 2x^2$ has $g(0) = 0$ ; show by differentiation that it is minimized there on $[-p, 1-p]$ (Exercise 10.1).

(3) $p\mapsto d(p, q-\varepsilon) - d(p, q)$ is linear and increasing in $p$ , so for $p\le q-\varepsilon$ it is at most its value at $q - \varepsilon$ , namely $-d(q-\varepsilon, q)$ . Then apply Pinsker.

∎

LemmaLemma 10.3 — Chernoff’s bound

For i.i.d. Bernoulli( $\mu$ ) with sample mean $\hat\mu$ :

$\mathbb P(\hat\mu\ge\mu + \varepsilon)\le e^{-n\,d(\mu+\varepsilon,\mu)}\ \ (\varepsilon\in[0,1-\mu]), \qquad \mathbb P(\hat\mu\le\mu - \varepsilon)\le e^{-n\,d(\mu-\varepsilon,\mu)}\ \ (\varepsilon\in[0,\mu]) \tag{10.1–10.2}$

ProofCramér–Chernoff with the exact Bernoulli MGF

For $\lambda > 0$ ,

$\mathbb P(\hat\mu\ge\mu + \varepsilon)\le\frac{\mathbb E e^{\lambda\sum_t(X_t - \mu)}}{e^{\lambda n\varepsilon}} = \Big(\mu e^{\lambda(1-\mu-\varepsilon)} + (1-\mu)e^{-\lambda(\mu+\varepsilon)}\Big)^n$

The minimizing $\lambda = \log\frac{(\mu+\varepsilon)(1-\mu)}{\mu(1-\mu-\varepsilon)}$ makes the bracket equal $e^{-d(\mu+\varepsilon,\mu)}$ . The lower tail is symmetric.

∎

RemarkCredit

Chernoff attributed the bound to his friend Herman Rubin, but the name stuck.

IntuitionChernoff versus Hoeffding

By Pinsker, $e^{-nd}\le e^{-2n\varepsilon^2}$ , which recovers Hoeffding. The two agree near $\mu = \frac12$ . Near 0 or 1, Chernoff is far stronger, because the true deviation rate $d(\mu\pm\varepsilon,\mu)$ is much larger than $2\varepsilon^2$ there.

CorollaryCorollary 10.4 — KL confidence intervals

For $a\ge0$ , $\mathbb P(d(\hat\mu,\mu)\ge a,\ \hat\mu\le\mu)\le e^{-na}$ , and likewise for $\hat\mu\ge\mu$ . Define

$U(a) = \max\{u\in[0,1] : d(\hat\mu,u)\le a\}, \qquad L(a) = \min\{u\in[0,1] : d(\hat\mu,u)\le a\}$

Then $\mathbb P(\mu\ge U(a))\le e^{-na}$ and $\mathbb P(\mu\le L(a))\le e^{-na}$ . With $a = \log(1/\delta)/n$ , these are $1-\delta$ upper and lower confidence bounds.

ProofMonotonicity of

d

on each side of

\hat\mu

Lower deviations: $d(\cdot,\mu)$ is decreasing on $[0,\mu]$ , so $\{d(\hat\mu,\mu)\ge a,\ \hat\mu\le\mu\} = \{\hat\mu\le\mu - x\}$ , where $x$ solves $d(\mu - x,\mu) = a$ . Apply (10.2).

Upper confidence bound: $U\ge\hat\mu$ and $d(\hat\mu,\cdot)$ is strictly increasing on $[\hat\mu,1]$ with $d(\hat\mu,U) = a$ , so $\{\mu\ge U\} = \{d(\hat\mu,\mu)\ge a,\ \mu\ge\hat\mu\}$ . Use the first part.

∎

RemarkComputing the bounds

$U$ and $L$ have no closed form, but $d$ is convex in its second argument, so Newton’s method solves $d(\hat\mu,u) = a$ quickly.

ExampleExample 10.5 — An asymmetric interval

$\hat\mu = \frac34$ , $n = 10$ , 90% confidence: $a = \log(10)/10\approx0.23$ . The interval $\{x : d(\frac34, x)\le0.23\}$ is highly asymmetric: it extends further below $\frac34$ than above. Hoeffding’s half-width, $\sqrt{\log(1/\delta)/2n}\approx0.34$ , gives a similar lower bound but a vacuous upper bound ( $0.75 + 0.34 > 1$ ). KL intervals automatically respect $[0,1]$ and tighten as $\hat\mu\to0$ or 1.

The KL-UCB algorithm

AlgorithmKL-UCB — Algorithm 8

Play each arm once, then

$A_t = \arg\max_i\ \max\Big\{\tilde\mu\in[0,1] : d\big(\hat\mu_i(t-1),\tilde\mu\big)\le\frac{\log f(t)}{T_i(t-1)}\Big\},\qquad f(t) = 1 + t\log^2t$

The index is the largest mean that is still statistically plausible in KL terms.

TheoremTheorem 10.6 — Regret of KL-UCB

If $X_t\sim\mathcal B(\mu_{A_t})$ , then

$R_n\le\sum_{i:\Delta_i>0}\ \inf_{\substack{\varepsilon_1,\varepsilon_2>0\\ \varepsilon_1+\varepsilon_2<\Delta_i}}\Delta_i\Big(\frac{\log f(n)}{d(\mu_i+\varepsilon_1,\ \mu^*-\varepsilon_2)} + \frac1{2\varepsilon_1^2} + \frac2{\varepsilon_2^2}\Big)$

$\limsup_{n\to\infty}\frac{R_n}{\log n}\le\sum_{i:\Delta_i>0}\frac{\Delta_i}{d(\mu_i,\mu^*)}$

ImportantNever worse than UCB, much better near the edges

UCB tuned for $\frac12$ -subgaussian rewards has asymptotic constant $\frac1{2\Delta_i}$ . By Pinsker, $d(\mu_i,\mu^*)\ge2\Delta_i^2$ , so $\frac{\Delta_i}{d}\le\frac1{2\Delta_i}$ : KL-UCB is never worse asymptotically. When $\mu_i\approx\mu^*$ , a Taylor expansion gives

$d(\mu_i,\mu^*) = \frac{\Delta_i^2}{2\mu_i(1-\mu_i)} + o(\Delta_i^2)\ \Longrightarrow\ \limsup\frac{R_n}{\log n}\approx\sum_{i:\Delta_i>0}\frac{2\mu_i(1-\mu_i)}{\Delta_i} \tag{10.5}$

The worst-case scale $\frac14$ is replaced by the arm’s actual variance $\mu_i(1-\mu_i)$ , which helps a lot when means are near 0 or 1 (rare clicks).

WarningThis is not a CLT effect

(10.5) looks like “Bernoulli behaves like a Gaussian with matched variance”, but that approximation’s quality doesn’t improve with $n$ . As $n\to\infty$ the confidence level must drive failure probabilities below $n^{-1/2}$ , where the CLT says nothing (why the CLT fails for tails). The KL rate is the true large-deviation rate.

LemmaLemma 10.7 — The optimal arm’s index rarely dips

With $\bar d(p,q) = d(p,q)\,\mathbb I\{p\le q\}$ , i.i.d. Bernoulli( $\mu$ ) samples, and

$\tau = \min\Big\{t : \max_{1\le s\le n}\Big(\bar d(\hat\mu_s, \mu - \varepsilon) - \frac{\log f(t)}s\Big)\le0\Big\},\qquad\mathbb E[\tau]\le\frac2{\varepsilon^2}$

After time $\tau$ , the KL index built from any sample count is at least $\mu - \varepsilon$ .

ProofShift the reference by ε, then Chernoff, then integrate the tail

$\mathbb P(\tau > t)\le\sum_{s=1}^n\mathbb P\Big(\bar d(\hat\mu_s,\mu-\varepsilon) > \frac{\log f(t)}s,\ \hat\mu_s < \mu - \varepsilon\Big)\le\sum_s\mathbb P\Big(d(\hat\mu_s,\mu) > \frac{\log f(t)}s + 2\varepsilon^2,\ \hat\mu_s < \mu\Big)$

using Lemma 10.2(3). By Corollary 10.4 this is at most $\sum_se^{-\log f(t) - 2s\varepsilon^2}\le\frac1{2f(t)\varepsilon^2}$ . Integrating, $\mathbb E[\tau]\le\frac1{2\varepsilon^2}\int_0^\infty\frac{dt}{f(t)}\le\frac2{\varepsilon^2}$ .

∎

LemmaLemma 10.8 — A suboptimal arm’s index stays high only briefly

For i.i.d. Bernoulli( $\mu$ ), $\Delta > 0$ , $a > 0$ and $\kappa = \sum_{s=1}^n\mathbb I\{d(\hat\mu_s,\mu+\Delta)\le a/s\}$ ,

$\mathbb E[\kappa]\le\inf_{\varepsilon\in(0,\Delta)}\Big(\frac a{d(\mu+\varepsilon,\mu+\Delta)} + \frac1{2\varepsilon^2}\Big)$

ProofEither the mean overshoots or

s

is still small

Since $d(\cdot,\mu+\Delta)$ is decreasing on $[0,\mu+\Delta]$ , $\{d(\hat\mu_s,\mu+\Delta)\le\frac as\}\subseteq\{\hat\mu_s\ge\mu+\varepsilon\}\cup\{s\le u\}$ with $u = a/d(\mu+\varepsilon,\mu+\Delta)$ . So $\mathbb E[\kappa]\le u + \sum_s e^{-s\,d(\mu+\varepsilon,\mu)}\le u + \frac1{d(\mu+\varepsilon,\mu)}\le u + \frac1{2\varepsilon^2}$ , by Chernoff and then Pinsker.

∎

ProofProof of Theorem 10.6

Fix a suboptimal arm $i$ and $\varepsilon_1,\varepsilon_2 > 0$ with $\varepsilon_1 + \varepsilon_2 < \Delta_i$ . Before $\tau$ (Lemma 10.7 applied to arm 1 with $\varepsilon_2$ ), count every round. After $\tau$ , arm 1’s index is at least $\mu^* - \varepsilon_2$ , so arm $i$ is played only when its own index reaches $\mu^* - \varepsilon_2$ , i.e. when $d(\hat\mu_{i,T_i}, \mu^* - \varepsilon_2)\le\log f(n)/T_i$ . That is the count $\kappa$ of Lemma 10.8 with $\mu + \Delta = \mu^* - \varepsilon_2$ and $a = \log f(n)$ :

$\mathbb E[T_i(n)]\le\mathbb E[\tau] + \mathbb E[\kappa]\le\frac2{\varepsilon_2^2} + \frac{\log f(n)}{d(\mu_i+\varepsilon_1,\mu^*-\varepsilon_2)} + \frac1{2\varepsilon_1^2}$

Multiply by $\Delta_i$ and sum. For the asymptotics, let $\varepsilon_1,\varepsilon_2\to0$ slowly with $n$ (Exercise 10.2).

∎

Notes and extensions

RemarkBernoulli is the worst case on $[0,1]$

For any $X\in[0,1]$ with mean $\mu$ , convexity of $x\mapsto e^{\lambda x}$ gives $\mathbb E e^{\lambda X}\le\mu e^\lambda + 1 - \mu$ , the Bernoulli MGF (Garivier–Cappé). So Chernoff’s bound, and KL-UCB’s guarantee $\limsup\frac{R_n}{\log n}\le\sum\frac{\Delta_i}{d(\mu_i,\mu^*)}$ , hold for any $[0,1]$ -valued rewards. They even hold for adapted sequences with deterministic conditional means (Exercise 10.3), though the bound degrades toward Hoeffding when the means are spread between 0 and 1.

RemarkNot quite tight for general bounded rewards

The optimal asymptotic constant over $[0,1]$ -supported distributions uses $d_i = \inf\{D(P_i,P) : \mu(P) > \mu^*,\ \mathrm{Supp}(P)\subseteq[0,1]\}$ , a KL projection onto distributions with a better mean. This is never smaller than $d(\mu_i,\mu^*)$ , and is achieved by DMED and IMED (Honda–Takemura).

RemarkExponential families (Exercises 10.4–10.5)

For a one-parameter exponential family arm, replace $d$ by the family’s KL divergence to get $\limsup\frac{R_n}{\log n}\le\sum_i\frac{\Delta_i}{d_{i,\inf}}$ (Cappé et al. 2013). For non-canonical families, ties must be broken toward the most-played arm, and the lower-order term $1/d_{i,\min}$ may dominate in practice.

RemarkHistory

Lai (1987) gave the first asymptotic version. Finite-time KL-UCB was proved simultaneously by Garivier–Cappé (2011) and Maillard et al. (2011). KL-UCB-type asymptotic optimality is also known for Thompson sampling (Kaufmann et al.; Korda et al.) and BayesUCB. Ménard–Garivier (2017) combined MOSS and KL-UCB to be minimax and asymptotically optimal for exponential families.

ExampleKL-UCB versus UCB (Exercise 10.6)

With $n = 10{,}000$ and $k = 2$ , compare $\mu_1 = \frac12$ , $\mu_2 = \frac12 + \Delta$ (where the two should be similar, since the variance is near its maximum) with $\mu_1 = \frac1{10}$ or $\frac9{10}$ (where KL-UCB should win clearly, since its intervals shrink near the boundary).

Quick reference

Object	Statement	Note
ETC regret	$m\sum\Delta_i + (n-mk)\sum\Delta_ie^{-m\Delta_i^2/4}$	difference of means is $\sqrt{2/m}$ -subgaussian
ETC tuned ( $k=2$ )	$m\approx\frac4{\Delta^2}\log\frac{n\Delta^2}4$ ; $R_n\le\Delta + \frac4\Delta(1 + \log\frac{n\Delta^2}4)$	needs $\Delta$
ETC worst case	$\Delta + C\sqrt n$ tuned; $(\Delta + C)n^{2/3}$ untuned
Doubling trick	$R_n\le\sum_\ell f_{n_\ell}$	$\sqrt n$ preserved; $\log n$ needs faster growth
UCB index	$\hat\mu_i + \sqrt{2\log(1/\delta)/T_i}$	optimism
UCB, $\delta = 1/n^2$	$\mathbb E T_i(n)\le3 + \frac{16\log n}{\Delta_i^2}$	good-event proof
UCB worst case	$8\sqrt{nk\log n} + 3\sum\Delta_i$	split at $\Delta\approx\sqrt{k\log n/n}$
Asymptotically optimal UCB	$\log f(t)$ , $f = 1 + t\log^2t$ ; $\limsup\frac{R_n}{\log n}\le\sum\frac2{\Delta_i}$	Lai–Robbins optimal
Lemma 8.2	$\mathbb E\#\{\hat\mu_t + \sqrt{2a/t}\ge\varepsilon\}\le1 + \frac2{\varepsilon^2}(a + \sqrt{\pi a} + 1)$
Maximal Hoeffding	$\mathbb P(\exists t\le n : S_t\ge\varepsilon)\le e^{-\varepsilon^2/2n\sigma^2}$	Doob
Peeling	union bound over $[2^j, 2^{j+1}]$	Lemma 9.3: $15\delta/\Delta^2$
MOSS	bonus $\sqrt{\frac4{T_i}\log^+\frac n{kT_i}}$ ; $R_n\le39\sqrt{kn} + \sum\Delta_i$	minimax optimal
MOSS failure	$n = k^3$ instance: $\Omega(k^2)$ versus UCB’s $O(k\log k)$
Bernoulli KL	$d(p,q) = p\log\frac pq + (1-p)\log\frac{1-p}{1-q}$	Pinsker: $\ge2(p-q)^2$
Chernoff	$\mathbb P(\hat\mu\ge\mu+\varepsilon)\le e^{-nd(\mu+\varepsilon,\mu)}$	valid for any $[0,1]$ rewards
KL interval	$U(a) = \max\{u : d(\hat\mu,u)\le a\}$	asymmetric, respects $[0,1]$
KL-UCB	$\limsup\frac{R_n}{\log n}\le\sum\frac{\Delta_i}{d(\mu_i,\mu^*)}\approx\sum\frac{2\mu_i(1-\mu_i)}{\Delta_i}$	never worse than UCB
UCB-V	$C\sum(\Delta_i + (b + \sigma_i^2/\Delta_i)\log n)$	empirical Bernstein
Median of means	finite variance suffices	constants grow

Facts to keep to hand

Every analysis is “pulls of each bad arm”. Bound $\mathbb E[T_i(n)]$ by splitting into “the optimal arm’s index failed” (rare: concentration plus a union bound over sample counts) and “arm $i$ ‘s index is still high” (lasts about $\log(\cdot)/\Delta_i^2$ pulls). Then convert $\sum\frac{\log n}{\Delta_i}$ into a worst-case bound by splitting at a threshold gap.
ETC’s weakness is its fixed budget. It is nearly optimal when tuned with $\Delta$ and $n$ , but $\Delta$ is unknown. Adaptive stopping, elimination and optimism all fix this by letting the data decide when exploration is done.
The confidence level is the whole design. $1/n^2$ (simple proof) leads to $\log f(t)$ (anytime, optimal constant 2) and then to per-arm $\log^+\frac n{kT_i}$ (minimax, no log factor). Each refinement trades high-probability optimism for optimism in expectation, and pays in instance-dependent behaviour or regret tails.
Optimism must match the noise model. Subgaussian widths are worst-case. KL widths for Bernoulli or bounded rewards, variance-adaptive widths (UCB-V), and robust estimators (median of means) all win by modelling the noise more faithfully.
No single criterion tells the whole story. Minimax optimality (MOSS), asymptotic optimality (Lai–Robbins), finite-time instance behaviour (UCB beats MOSS on some instances), and regret tails (instability) can disagree.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 6–10

Related

Explore-Then-Commit and the Upper Confidence Bound Algorithms

Motivation: one problem, five increasingly sharp answers

Explore-then-commit (Chapter 6)

Tuning the commitment time ( $k = 2$ )

Variants and notes

The upper confidence bound algorithm (Chapter 7)

The optimism principle

Regret analysis

Notes and extensions

Asymptotically optimal UCB (Chapter 8)

MOSS: minimax optimality (Chapter 9)

Two problems with MOSS

Notes

Bernoulli rewards and KL-UCB (Chapter 10)

Concentration for sums of Bernoulli random variables

The KL-UCB algorithm

Notes and extensions

Quick reference

References

Mentioned in

Related

Motivation: one problem, five increasingly sharp answers

Explore-then-commit (Chapter 6)

Tuning the commitment time (k=2k = 2k=2)

Variants and notes

The upper confidence bound algorithm (Chapter 7)

The optimism principle

Regret analysis

Notes and extensions

Asymptotically optimal UCB (Chapter 8)

MOSS: minimax optimality (Chapter 9)

Two problems with MOSS

Notes

Bernoulli rewards and KL-UCB (Chapter 10)

Concentration for sums of Bernoulli random variables

The KL-UCB algorithm

Notes and extensions

Quick reference

References

Mentioned in

Tuning the commitment time ( $k = 2$ )