Concentration of Measure for Bandits

Corresponds to Lattimore & Szepesvári, Chapter 5.

Motivation: how long does it take to learn a mean?

The regret decomposition reduces every bandit analysis to one question: how many times must each arm be pulled before we can tell, with enough confidence, that it isn’t the best? That requires knowing how fast an empirical mean concentrates around its true mean, and not just on average but in the tails: how often the estimate is badly wrong.

IntuitionThe central question

After $n$ samples of an arm, how unlikely is it that the sample mean is off by more than $\varepsilon$ , and how does that probability fall with $n$ and $\varepsilon$ ? Bandit algorithms need answers that are finite-time (valid for this $n$ , not as $n\to\infty$ ) and exponentially small (so that confidence intervals can be made very reliable cheaply).

flowchart TD
  M["Markov: mean only, decays like 1 over epsilon"] --> C["Chebyshev: variance, decays like 1 over n epsilon squared"]
  M --> CC["Cramér-Chernoff: Markov applied to exp of lambda X"]
  CC --> SG["Subgaussian: exp of minus n epsilon squared over 2 sigma squared"]
  SG --> H["Hoeffding: bounded variables"]
  CC --> B["Bennett and Bernstein: variance plus a one-sided bound"]
  CC --> LD["Large deviations: exact exponential rate"]

Tail probabilities

Setup. $X, X_1, \ldots, X_n$ are i.i.d. with mean $\mu$ and variance $\sigma^2$ .

DefinitionSample (empirical) mean

$\hat\mu = \frac1n\sum_{i=1}^nX_i$

By linearity, $\mathbb E[\hat\mu] = \mu$ : the sample mean is an unbiased estimator.

TheoremVariance of the average (Exercise 5.1)

$\mathbb V[\hat\mu] = \mathbb E\big[(\hat\mu - \mu)^2\big] = \frac{\sigma^2}n \tag{5.1}$

ProofVariances of independent terms add

$\hat\mu - \mu = \frac1n\sum_i(X_i - \mu)$ . Expanding the square, the cross terms $\mathbb E[(X_i-\mu)(X_j-\mu)]$ vanish for $i\ne j$ by independence, leaving $\frac1{n^2}\cdot n\sigma^2$ .

∎

IntuitionThe squared error shrinks like $1/n$

The typical error is of order $\sigma/\sqrt n$ : halving it takes four times as many samples. But a mean squared error says little about how often the error is large, which is what decides whether a bandit algorithm discards a good arm.

DefinitionTail probabilities

As functions of $\varepsilon > 0$ :

upper tail: $\mathbb P(\hat\mu\ge\mu + \varepsilon)$ (overestimate);
lower tail: $\mathbb P(\hat\mu\le\mu - \varepsilon)$ (underestimate);
two-sided tail: $\mathbb P(|\hat\mu - \mu|\ge\varepsilon)$ .

Component	Detail
Signature	$\varepsilon\mapsto\mathbb P(\hat\mu - \mu\ge\varepsilon)$ , a function $[0,\infty)\to[0,1]$
Input	An error tolerance.
Output	The probability the estimate misses by at least that much, in that direction.
What we want	Explicit upper bounds valid for every finite $n$ .

Markov and Chebyshev

TheoremLemma 5.1

For any random variable $X$ and $\varepsilon > 0$ :

Markov: $\mathbb P(|X|\ge\varepsilon)\le\dfrac{\mathbb E|X|}\varepsilon$ ;
Chebyshev: $\mathbb P(|X - \mathbb EX|\ge\varepsilon)\le\dfrac{\mathbb V[X]}{\varepsilon^2}$ .

NoteAlready covered

Proofs, the tight balls-in-buckets example, and Chebyshev confidence intervals are in concentration-inequalities-and-limit-theorems and concentration-inequalities-and-limit-theorems. Markov is “one of the golden hammers of probability theory”, and everything below is Markov applied to a cleverly chosen function of $X$ .

FormulaChebyshev for the sample mean

Combining (5.1) with Chebyshev:

$\mathbb P(|\hat\mu - \mu|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2} \tag{5.2}$

It needs only a finite variance, which is its strength. Its weakness is the decay: only polynomial in $n$ , and very loose for well-behaved $X$ .

IntuitionHigher moments help, and the limit of that idea is the MGF

Applying Markov to $|\hat\mu - \mu|^k$ for larger $k$ gives faster decay, provided those moments exist, and one could optimize over $k$ . Doing this optimization over a continuous parameter is the Cramér–Chernoff method.

Calibrating with the central limit theorem

What should we hope for? Let $S_n = \sum_{t\le n}(X_t - \mu)$ . With nothing beyond a finite variance, the CLT says $S_n/\sqrt{n\sigma^2}$ converges in distribution to $Z\sim\mathcal N(0,1)$ .

FormulaGaussian tail bound

For $u > 0$ :

$\mathbb P(Z\ge u) = \int_u^\infty\frac1{\sqrt{2\pi}}e^{-x^2/2}dx\le\frac1{u\sqrt{2\pi}}\int_u^\infty xe^{-x^2/2}dx = \sqrt{\frac1{2\pi u^2}}\,e^{-u^2/2} \tag{5.3}$

DerivationMultiply by

x/u\ge1

On $[u,\infty)$ , $\frac xu\ge1$ , so inserting it can only increase the integral. Then $xe^{-x^2/2}$ has antiderivative $-e^{-x^2/2}$ , which evaluates to $e^{-u^2/2}$ . (The $\Phi$ table gives exact values.)

FormulaThe CLT heuristic for the sample mean

$\mathbb P(\hat\mu\ge\mu + \varepsilon) = \mathbb P\Big(\frac{S_n}{\sqrt{\sigma^2n}}\ge\varepsilon\sqrt{\frac n{\sigma^2}}\Big)\approx\mathbb P\Big(Z\ge\varepsilon\sqrt{\frac n{\sigma^2}}\Big)\le\sqrt{\frac{\sigma^2}{2\pi n\varepsilon^2}}\exp\Big(-\frac{n\varepsilon^2}{2\sigma^2}\Big) \tag{5.4}$

It decays slightly faster than $e^{-n\varepsilon^2/2\sigma^2}$ : the sample mean concentrates exponentially fast. This is the benchmark.

ExampleGaussian tail versus Chebyshev (Exercise 5.3)

Let $u = \varepsilon\sqrt{n/\sigma^2}$ . Chebyshev’s one-sided bound is $1/u^2$ , and the Gaussian is $\frac{1}{u\sqrt{2\pi}}e^{-u^2/2}$ . Their ratio is $\frac{u}{\sqrt{2\pi}}e^{-u^2/2}$ , which is at most $\frac{e^{-1/2}}{\sqrt{2\pi}}\approx0.24$ (maximized at $u = 1$ ). So the Gaussian bound is always smaller.

The improvement is dramatic for large $u$ , i.e. many samples or a coarse tolerance. At $u = 5$ : Chebyshev $0.04$ , Gaussian about $1.5\times10^{-7}$ .
Both bounds are trivial (at least 1) for small $u$ : Chebyshev for $u\le1$ , the Gaussian bound for $u\le1/\sqrt{2\pi}\approx0.4$ .

(Worked here; the book poses it as an exercise.)

WarningWhy the CLT can’t be used to design algorithms

It’s asymptotic. It says nothing for any particular $n$ , and a bandit algorithm must act at every $n$ .
" $n\ge30$ " is folklore. Take $X_t$ Bernoulli $(1/n)$ . As $n\to\infty$ , $\sum X_t\to$ Poisson $(1)$ (Poisson limit), which looks nothing like a Gaussian. (Exercise 5.6 explores this; there is no contradiction with the CLT because the distribution changes with $n$ .)
The error rate is too coarse for small tails. Berry–Esseen: if $\rho = \mathbb E|X - \mu|^3 < \infty$ , then $\sup_x\Big|\mathbb P\Big(\frac{S_n}{\sigma\sqrt n}\le x\Big) - \Phi(x)\Big|\le\frac{C\rho}{\sigma^3\sqrt n},\qquad C < \tfrac12$ (in the book’s normalization, which takes $\sigma = 1$ ). The $1/\sqrt n$ rate is tight for that class, but it is vacuous when the tail probabilities themselves are smaller than $1/\sqrt n$ , which is exactly the regime confidence bounds live in.

Finite-time exponential bounds need extra assumptions on the distribution.

The Cramér–Chernoff method and subgaussian random variables

DefinitionMoment- and cumulant-generating functions

$M_X(\lambda) = \mathbb E[e^{\lambda X}], \qquad \psi_X(\lambda) = \log M_X(\lambda)$

Component	Detail
Signature	$M_X : \mathrm{dom}(M_X)\subseteq\mathbb R\to(0,\infty]$
Domain	The $\lambda$ where the expectation is finite: an interval containing 0 (Exercise 5.9).
Name	$M_X^{(k)}(0) = \mathbb E[X^k]$ when 0 is interior, hence “moment-generating”.
Shape	$M_X$ is convex, and $\psi_X$ is convex ( $M_X$ is log-convex). $M_X(\lambda)\ge e^{\lambda\mathbb EX}$ by Jensen.

DefinitionLight and heavy tails

$X$ is heavy tailed if $M_X(\lambda) = \infty$ for all $\lambda > 0$ , and light tailed otherwise.

Example: for $X\sim$ Exponential(1), $\mathbb E[e^{\lambda X}] = \int_0^\infty e^{-x}e^{\lambda x}dx = \infty$ for $\lambda\ge1$ . The MGF exists only on $(-\infty, 1)$ , which is light tailed but not globally finite.

AlgorithmThe Cramér–Chernoff method

For any $\lambda > 0$ , exponentiating preserves the event, and Markov does the rest:

$\mathbb P(X\ge\varepsilon) = \mathbb P(e^{\lambda X}\ge e^{\lambda\varepsilon})\le M_X(\lambda)e^{-\lambda\varepsilon}$

Then optimize $\lambda$ : $\mathbb P(X\ge\varepsilon)\le\exp\big(-\sup_{\lambda\ge0}(\lambda\varepsilon - \psi_X(\lambda))\big)$ .

IntuitionMarkov on the right function

Markov is weak because $\varepsilon\mapsto1/\varepsilon$ decays slowly. Applying it to $e^{\lambda X}$ turns a polynomial bound into an exponential one. The free parameter $\lambda$ trades how much the exponential amplifies the tail against how large the MGF is.

DefinitionSubgaussian random variable (Def. 5.2)

$X$ is $\sigma$ -subgaussian if for all $\lambda\in\mathbb R$ ,

$\mathbb E[e^{\lambda X}]\le\exp\Big(\frac{\lambda^2\sigma^2}2\Big),\qquad\text{equivalently}\qquad\psi_X(\lambda)\le\frac{\lambda^2\sigma^2}2$

Component	Detail
Parameter	$\sigma\ge0$ , the “variance proxy” scale.
Benchmark	$\mathcal N(0,\sigma^2)$ has $M_X(\lambda) = e^{\lambda^2\sigma^2/2}$ exactly, so it is $\sigma$ -subgaussian with equality.
Meaning	The MGF is dominated everywhere by a centred Gaussian’s.
Not centred?	Convention: say $X$ is $\sigma$ -subgaussian when the noise $X - \mathbb EX$ is. Subgaussianity is a property of a variable and its law, so the terminology is doubly abused.

TheoremTheorem 5.3 — Subgaussian tails

If $X$ is $\sigma$ -subgaussian, then for all $\varepsilon\ge0$ ,

$\mathbb P(X\ge\varepsilon)\le\exp\Big(-\frac{\varepsilon^2}{2\sigma^2}\Big) \tag{5.5}$

ProofCramér–Chernoff with the subgaussian bound

For $\lambda > 0$ :

$\mathbb P(X\ge\varepsilon)\le\mathbb E[e^{\lambda X}]e^{-\lambda\varepsilon}\le\exp\Big(\frac{\lambda^2\sigma^2}2 - \lambda\varepsilon\Big)$

The exponent is a parabola in $\lambda$ , minimized at $\lambda = \varepsilon/\sigma^2$ , where it equals $-\frac{\varepsilon^2}{2\sigma^2}$ .

∎

FormulaTwo-sided and deviation forms

$-X$ is also $\sigma$ -subgaussian, so the lower tail obeys the same bound, and by the union bound $\mathbb P(|X|\ge\varepsilon)\le2e^{-\varepsilon^2/2\sigma^2}$ . Solving for $\varepsilon$ :

$\mathbb P\Big(X\ge\sqrt{2\sigma^2\log(1/\delta)}\Big)\le\delta, \qquad \mathbb P\Big(|X|\ge\sqrt{2\sigma^2\log(2/\delta)}\Big)\le\delta$

With overwhelming probability, $X$ lies in $\big[-\sqrt{2\sigma^2\log(2/\delta)},\ \sqrt{2\sigma^2\log(2/\delta)}\big]$ .

LemmaLemma 5.4 — Calculus of subgaussians

If $X$ is $\sigma$ -subgaussian, and $X_1, X_2$ are independent and $\sigma_1$ -, $\sigma_2$ -subgaussian:

$\mathbb E[X] = 0$ and $\mathbb V[X]\le\sigma^2$ ;
$cX$ is $|c|\sigma$ -subgaussian;
$X_1 + X_2$ is $\sqrt{\sigma_1^2 + \sigma_2^2}$ -subgaussian.

ProofTaylor expansion, substitution, and factorized MGFs

1. Expand both sides for small $\lambda$ : $1 + \lambda\mathbb E[X] + \frac{\lambda^2}2\mathbb E[X^2] + o(\lambda^2)\le1 + \frac{\lambda^2\sigma^2}2 + o(\lambda^2)$ . Dividing by $\lambda$ and letting $\lambda\to0^\pm$ gives $\mathbb EX\le0$ and $\mathbb EX\ge0$ , so $\mathbb EX = 0$ . Then dividing by $\lambda^2$ gives $\mathbb E[X^2]\le\sigma^2$ .

2. $\mathbb E[e^{\lambda cX}]\le e^{(\lambda c)^2\sigma^2/2} = e^{\lambda^2(|c|\sigma)^2/2}$ .

3. By independence, $\mathbb E[e^{\lambda(X_1+X_2)}] = \mathbb E[e^{\lambda X_1}]\,\mathbb E[e^{\lambda X_2}]\le e^{\lambda^2(\sigma_1^2+\sigma_2^2)/2}$ .

(Exercise 5.7.)

∎

RemarkWithout independence (Exercise 5.8)

For dependent $X_1, X_2$ , the sum is still $(\sigma_1+\sigma_2)$ -subgaussian (via Hölder’s inequality), so the scales add linearly instead of in quadrature.

The sample mean

CorollaryCorollary 5.5 — Subgaussian concentration of the sample mean

If the $X_i - \mu$ are independent and $\sigma$ -subgaussian, then for all $\varepsilon\ge0$ ,

$\mathbb P(\hat\mu\ge\mu + \varepsilon)\le\exp\Big(-\frac{n\varepsilon^2}{2\sigma^2}\Big),\qquad\mathbb P(\hat\mu\le\mu - \varepsilon)\le\exp\Big(-\frac{n\varepsilon^2}{2\sigma^2}\Big)$

ProofAverage, then apply Theorem 5.3

By Lemma 5.4 parts 2 and 3, $\hat\mu - \mu = \sum_i(X_i - \mu)/n$ is $\sqrt{n\sigma^2/n^2} = \sigma/\sqrt n$ -subgaussian. Apply (5.5) with $\sigma^2/n$ in place of $\sigma^2$ .

∎

FormulaConfidence bounds (deviation form)

For any $\delta\in(0,1]$ , each of the following holds with probability at least $1 - \delta$ :

$\mu\le\hat\mu + \sqrt{\frac{2\sigma^2\log(1/\delta)}n} \tag{5.6}$ $\mu\ge\hat\mu - \sqrt{\frac{2\sigma^2\log(1/\delta)}n} \tag{5.7}$

A union bound gives a two-sided interval with $\log(2/\delta)$ .

ImportantThis is the formula behind UCB

(5.6) is an upper confidence bound on an arm’s mean from $n$ pulls. Its width shrinks like $1/\sqrt n$ and grows only like $\sqrt{\log(1/\delta)}$ as the required reliability increases. Algorithms built on it are in explore-then-commit-and-ucb-algorithms.

ExampleWhy $\log(1/\delta)$ instead of $1/\delta$ matters

Two-sided confidence-interval half-widths, in units of $\sigma/\sqrt n$ :

$\delta$	Chebyshev, $\sqrt{1/\delta}$	Subgaussian, $\sqrt{2\log(2/\delta)}$
$10^{-1}$	3.2	2.4
$10^{-3}$	31.6	3.9
$10^{-6}$	1000	5.4

Bandit algorithms take union bounds over many arms and rounds, so they need tiny $\delta$ . Chebyshev intervals would explode. (Numbers computed here.)

RemarkChebyshev versus Chernoff once more

Since $e^{-x}\le\frac1{ex}$ for $x > 0$ , the subgaussian bound beats Chebyshev except when $\varepsilon$ is very small, and is exponentially smaller once $n\varepsilon^2\gg\sigma^2$ .

Which variables are subgaussian

ExampleExample 5.6

Random variable	Subgaussian?
$\mathcal N(0,\sigma^2)$	$\sigma$ -subgaussian
mean zero, $\lvert X\rvert\le B$ a.s.	$B$ -subgaussian
mean zero, $X\in[a,b]$ a.s.	$\frac{b-a}2$ -subgaussian (Hoeffding’s lemma)
Bernoulli $(p)$ (centred)	$\frac12$ -subgaussian for every $p$
Exponential (any rate)	not subgaussian for any $\sigma$
$\chi^2$	not subgaussian (but Chernoff still works)

WarningSubgaussian is a real restriction

Exponential, $\chi^2$ , Poisson-type and heavier tails are not subgaussian. The broader classes subexponential and subgamma cover such tails with weaker MGF conditions. Standard bandit analyses assume subgaussian rewards (Bernoulli, bounded, or Gaussian noise).

Converse: Gaussian tails imply subgaussianity, with slack

TheoremTails to MGF

If $\mathbb EX = 0$ and $\mathbb P(|X|\ge\varepsilon)\le2e^{-\varepsilon^2/2}$ for all $\varepsilon$ , then $X$ is $\sqrt5$ -subgaussian.

ProofExpand the MGF, bound each moment by a tail integral

$\mathbb E[e^{\lambda X}]\le1 + \sum_{i\ge2}\frac{\lambda^i\mathbb E|X|^i}{i!} = 1 + \sum_{i\ge2}\int_0^\infty\mathbb P\Big(|X|\ge\frac{(i!)^{1/i}}\lambda x^{1/i}\Big)dx\le\cdots\le e^{5\lambda^2/2}$

The linear term vanishes because $\mathbb EX = 0$ . Each moment is written as a tail integral, the assumed tail bound is plugged in, and the sum is evaluated (the book uses Mathematica, getting an error-function expression).

∎

ExampleSome slack is unavoidable (Exercise 5.4)

The density $p(x) = \frac12|x|e^{-x^2/2}$ has exactly Gaussian tails, $\mathbb P(|X|\ge\varepsilon) = e^{-\varepsilon^2/2}$ , yet $X$ is not $\sqrt{2-\epsilon}$ -subgaussian for any $\epsilon > 0$ , so the best constant is $\sqrt2$ , not 1. Tail behaviour and MGF behaviour match only up to constants.

RemarkBeating the subgaussian bound

For Gaussians, (5.4) is slightly sharper than $e^{-n\varepsilon^2/2\sigma^2}$ by the polynomial prefactor. Talagrand (1995) showed similar refinements hold for bounded random variables.

Hoeffding

TheoremHoeffding’s lemma

If $\mathbb EX = 0$ and $X\in[a,b]$ a.s., then $M_X(\lambda)\le\exp\big(\lambda^2(b-a)^2/8\big)$ , i.e. $X$ is $\frac{b-a}2$ -subgaussian.

ProofTaylor with remainder, plus a tilted distribution (Exercise 5.11 hint)

Step 1: by Taylor, $\psi_X(\lambda) = \psi_X(0) + \psi_X'(0)\lambda + \psi_X''(\lambda')\frac{\lambda^2}2$ for some $\lambda'$ between 0 and $\lambda$ . Here $\psi_X(0) = 0$ and $\psi_X'(0) = \mathbb EX = 0$ .

Step 2: Tilt. Define $P_{\lambda}(dz) = e^{-\psi_X(\lambda)}e^{\lambda z}P(dz)$ . Then $\psi_X''(\lambda)$ is the variance of $Z\sim P_\lambda$ .

Step 3: $Z\in[a,b]$ , and any variable supported on an interval of length $b-a$ has variance at most $\frac{(b-a)^2}4$ . So $\psi_X(\lambda)\le\frac{\lambda^2(b-a)^2}8$ .

∎

TheoremHoeffding’s inequality

If $X_1, \ldots, X_n$ are independent with $X_t\in[a_t,b_t]$ a.s., then

$\mathbb P\Big(\frac1n\sum_{t=1}^n(X_t - \mathbb EX_t)\ge\varepsilon\Big)\le\exp\Big(-\frac{2n^2\varepsilon^2}{\sum_t(b_t - a_t)^2}\Big) \tag{5.8}$

For $[0,1]$ -valued rewards this is $e^{-2n\varepsilon^2}$ , i.e. $\sigma = \frac12$ in Corollary 5.5.

ProofLemma, then subgaussian calculus

Each centred $X_t$ is $\frac{b_t-a_t}2$ -subgaussian. The average is subgaussian with $\sigma^2 = \frac{\sum_t(b_t-a_t)^2}{4n^2}$ , and $e^{-\varepsilon^2/2\sigma^2}$ is the claim.

∎

Bennett and Bernstein: use the variance

IntuitionHoeffding ignores the variance

A $[0,1]$ -valued arm with mean $0.01$ has variance about $0.01$ , far below Hoeffding’s worst case of $\frac14$ . Bounds that use the actual variance can be much tighter for such low-variance arms.

TheoremBennett and Bernstein (Exercise 5.14)

Let $X_t$ be independent with $X_t - \mathbb EX_t\le b$ a.s., $S = \sum_t(X_t - \mathbb EX_t)$ , $v = \sum_t\mathbb V[X_t]$ , and $\alpha = b\varepsilon/v$ . Then

$\mathbb P(S\ge\varepsilon)\le\exp\Big(-\frac v{b^2}\big((1+\alpha)\log(1+\alpha) - \alpha\big)\Big)\le\exp\Big(-\frac{\varepsilon^2}{2v\big(1 + \frac{b\varepsilon}{3v}\big)}\Big) \tag{5.10–5.11}$

The first form is Bennett, the second Bernstein. In deviation form, with probability at least $1-\delta$ ,

$S < \sqrt{2v\log(1/\delta)} + \frac{2b}3\log(1/\delta)$

IntuitionTwo regimes

For small deviations the variance term $\sqrt{2v\log(1/\delta)}$ dominates, which is Gaussian-like with the true variance. For large deviations the range term $\frac{2b}3\log(1/\delta)$ dominates, which is Poisson-like.

RemarkMartingale versions

Bennett’s bound holds for adapted sequences with conditional means, with the variance replaced by the predictable variation $V = \sum_t\mathbb E_{t-1}[(X_t - \mu_t)^2]$ , on the event $\{V\le v\}$ . Exercise 5.15 gives a related version with a free parameter $\eta$ :

$\mathbb P\Big(\sum_t(X_t - \mu_t)\ge\eta\sum_t\mathbb E_{t-1}[(X_t - \mu_t)^2] + \frac1\eta\log\frac1\delta\Big)\le\delta\quad\text{if }\eta(X_t - \mu_t)\le1$

$\eta$ must be fixed in advance (choosing it from the data would make it random). Fixing that takes union bounds or the method of mixtures (Chapter 20). Empirical-variance versions also exist (Audibert et al.; Maurer–Pontil).

Large deviations: the exact exponential rate

TheoremChernoff bound with the rate function (Exercise 5.10)

For i.i.d. zero-mean $X_t$ whose MGF is finite everywhere,

$\frac1n\log\mathbb P(\hat\mu_n\ge\varepsilon)\le-\psi_X^*(\varepsilon) = -\sup_\lambda\big(\lambda\varepsilon - \log M_X(\lambda)\big) \tag{5.9}$

and this becomes an equality as $n\to\infty$ (Cramér’s theorem). Here $\psi^*$ is the Legendre transform (convex conjugate, Fenchel dual, Cramér transform, rate function) of $\psi_X$ .

Distribution (centred)	Rate function $\psi^*(\varepsilon)$
$\mathcal N(0,\sigma^2)$	$\varepsilon^2/(2\sigma^2)$
Rademacher, $\pm1$	$\frac{1+\varepsilon}2\log(1+\varepsilon) + \frac{1-\varepsilon}2\log(1-\varepsilon)$ for $\lvert\varepsilon\rvert < 1$ ; $\infty$ otherwise
Bernoulli $(p)$ , centred	$d(p+\varepsilon, p)$ for $p+\varepsilon\le1$ ; $\infty$ otherwise

where $d(p,q) = p\log\frac pq + (1-p)\log\frac{1-p}{1-q}$ is the relative entropy between Bernoulli $(p)$ and Bernoulli $(q)$ .

IntuitionThe rate of a Bernoulli deviation is a KL divergence

The chance that a $p$ -coin looks like a $(p+\varepsilon)$ -coin over $n$ flips is about $e^{-n\,d(p+\varepsilon,p)}$ . The cost of being fooled is exactly how distinguishable the two coins are. KL divergence reappears later in bandit lower bounds and in KL-UCB.

WarningThe CLT gets large deviations wrong

Scales. The CLT describes $S_n$ deviating at scale $\sqrt n$ . Large deviation theory describes deviations at scale $n$ ( $\mathbb P(\hat\mu_n\ge\varepsilon) = \mathbb P(S_n\ge n\varepsilon)$ ). Pretending the CLT applies there predicts rate $\varepsilon^2/2\sigma^2$ , which is generally wrong: the true rate is $\psi^*(\varepsilon)$ .
Moderate deviations, at scale $n^\alpha$ with $\frac12<\alpha<1$ , are where “ruthless” use of the Gaussian formula happens to give correct answers.

ExampleHow wrong for a Bernoulli arm (Exercise 5.13)

Take $p = 0.1$ , $\Delta = 0.1$ , and ask for the smallest $n$ with $\mathbb P(\hat p_n\ge p + \Delta)\le\delta$ as $\delta\to0$ . The required $n$ is about $\log(1/\delta)/\text{rate}$ , so the ratio of sample sizes is the inverse ratio of rates:

$\frac{n_{\text{Ber}}}{n_{\text{Gauss}}}\to\frac{\Delta^2/(2p(1-p))}{d(p+\Delta,p)} = \frac{0.0556}{0.0444}\approx1.25$

The Gaussian approximation underestimates the samples needed by about 25%. The upper tail of a low-mean Bernoulli is heavier than the matching Gaussian’s, even though the CLT holds. (Worked here.)

Smaller constants for Bernoulli

TheoremBernoulli subgaussianity constant (Exercise 5.12; Kearns–Saul)

Bernoulli $(p)$ is $\frac12$ -subgaussian for every $p$ , and its best constant is

$Q(p) = \sqrt{\frac{1 - 2p}{2\ln\big((1-p)/p\big)}}$

with $Q(\frac12) = \frac12$ by taking the limit. $Q(p)$ is larger than the standard deviation $\sqrt{p(1-p)}$ away from $p = \frac12$ ; for small $p$ it shrinks only like $1/\sqrt{\ln(1/p)}$ . For the one-sided upper tail with $p\ge\frac12$ , the variance itself suffices: $\mathbb E[e^{\lambda X}]\le\exp\big(p(1-p)\lambda^2/2\big)$ for $\lambda\ge0$ (MGF of the centred variable).

$\chi^2$ : Chernoff without a global MGF

ExampleTail of a $\chi^2_n$ variable

$Y = \sum_{i\le n}X_i^2$ with $X_i$ i.i.d. standard Gaussian has $M_Y(\lambda) = (1-2\lambda)^{-n/2}$ for $\lambda < \frac12$ only. Chernoff over $\lambda\in[0,\frac12)$ with the optimal $\lambda = \frac12 - \frac n{2(n+\varepsilon)}$ gives

$\mathbb P(Y\ge n + \varepsilon)\le\Big(1 + \frac\varepsilon n\Big)^{n/2}e^{-\varepsilon/2}$

which is essentially tight (Laurent–Massart). Cramér–Chernoff works whenever the MGF exists on some interval $[0,\lambda_0)$ .

Maxima and categorical distributions

TheoremExpected maximum of subgaussians (Exercise 5.18)

If $X_1, \ldots, X_n$ are $\sigma$ -subgaussian, possibly dependent, and $Z = \max_tX_t$ , then

$\mathbb E[Z]\le\sqrt{2\sigma^2\log n}, \qquad \mathbb P\Big(Z\ge\sqrt{2\sigma^2\log(n/\delta)}\Big)\le\delta$

ProofJensen, then bound the max by the sum

For $\lambda > 0$ : $e^{\lambda\mathbb E Z}\le\mathbb E e^{\lambda Z}\le\sum_t\mathbb E e^{\lambda X_t}\le ne^{\lambda^2\sigma^2/2}$ . So $\mathbb EZ\le\frac{\log n}\lambda + \frac{\lambda\sigma^2}2$ ; choose $\lambda = \sqrt{2\log n/\sigma^2}$ . The tail bound is a union bound over the $n$ applications of (5.5). (Proof filled in from the hint.)

∎

IntuitionMany draws, only $\sqrt{\log n}$ growth

The largest of $n$ subgaussian noise terms is of size $\sigma\sqrt{2\log n}$ . This is why union bounds over $k$ arms or $n$ rounds cost only a $\sqrt{\log}$ factor in confidence widths.

TheoremBretagnolle–Huber–Carol (Exercise 5.17)

For $X_t$ i.i.d. on $[m]$ , with true pmf $p$ and empirical pmf $\hat p$ ,

$\mathbb P\Big(\|p - \hat p\|_1\ge\sqrt{\frac{2(\log(1/\delta) + m\log2)}n}\Big)\le\delta \tag{5.12}$

Proof idea: $\|p-\hat p\|_1 = \max_{\lambda\in\{\pm1\}^m}\langle\lambda, p - \hat p\rangle$ . Each inner product is an average of bounded terms, and a union bound over the $2^m$ sign vectors produces the $m\log2$ .

NoteTwo more exercises

5.16: if $\mathbb P(X_t\le x)\le x$ on $[0,1]$ (stochastically at least uniform), then $\mathbb P\big(\sum_t\log(1/X_t)\ge\varepsilon\big)\le(\varepsilon/n)^ne^{n-\varepsilon}$ . This is a Chernoff bound for a sum of exponentials, used for p-values. 5.19: a tight bound on $\sum_t\mathbb E[X_t\mid\mathcal F_{t-1}]$ when $\sum_tX_t\le1$ a.s., with Bernoulli variables as the worst case.

Quick reference

Object	Statement	Note
Sample mean variance	$\mathbb V[\hat\mu] = \sigma^2/n$	error of order $\sigma/\sqrt n$
Chebyshev	$\mathbb P(\lvert\hat\mu-\mu\rvert\ge\varepsilon)\le\sigma^2/(n\varepsilon^2)$	variance only, polynomial
Gaussian tail	$\mathbb P(Z\ge u)\le\frac{1}{u\sqrt{2\pi}}e^{-u^2/2}$	the CLT benchmark
Berry–Esseen	CDF error $\le C\rho/(\sigma^3\sqrt n)$	useless for tiny tails
Cramér–Chernoff	$\mathbb P(X\ge\varepsilon)\le\inf_{\lambda\ge0}M_X(\lambda)e^{-\lambda\varepsilon}$	Markov on $e^{\lambda X}$
Subgaussian	$\psi_X(\lambda)\le\lambda^2\sigma^2/2$	Gaussian-dominated MGF
Subgaussian tail	$\mathbb P(X\ge\varepsilon)\le e^{-\varepsilon^2/2\sigma^2}$	$\lambda = \varepsilon/\sigma^2$
Calculus	mean 0, $\mathbb V\le\sigma^2$ ; $cX$ : $\lvert c\rvert\sigma$ ; independent sum: $\sqrt{\sigma_1^2+\sigma_2^2}$	dependent sum: $\sigma_1+\sigma_2$
Sample mean	$\mathbb P(\hat\mu\ge\mu+\varepsilon)\le e^{-n\varepsilon^2/2\sigma^2}$	$\hat\mu - \mu$ is $\sigma/\sqrt n$ -subgaussian
Confidence bound	$\mu\le\hat\mu + \sqrt{2\sigma^2\log(1/\delta)/n}$ w.p. $\ge1-\delta$	the UCB width
Hoeffding	$[a,b]$ ⇒ $\frac{b-a}2$ -subgaussian; tail $e^{-2n^2\varepsilon^2/\sum(b_t-a_t)^2}$	$[0,1]$ : $e^{-2n\varepsilon^2}$
Bernstein	$S<\sqrt{2v\log\frac1\delta} + \frac{2b}3\log\frac1\delta$	uses the true variance
Rate function	$\frac1n\log\mathbb P(\hat\mu\ge\varepsilon)\to-\psi^*(\varepsilon)$	Bernoulli: KL $d(p+\varepsilon,p)$
$\chi^2_n$	$\mathbb P(Y\ge n+\varepsilon)\le(1+\varepsilon/n)^{n/2}e^{-\varepsilon/2}$	MGF only on $[0,\frac12)$
Expected maximum	$\mathbb E\max_tX_t\le\sqrt{2\sigma^2\log n}$	holds under dependence
Bretagnolle–Huber–Carol	$\lVert p-\hat p\rVert_1\lesssim\sqrt{2(\log\frac1\delta+m\log2)/n}$	categorical $\ell_1$

Facts to keep to hand

Every bound here is Markov’s inequality in disguise. Chebyshev applies it to $(X-\mu)^2$ ; Cramér–Chernoff applies it to $e^{\lambda X}$ and optimizes $\lambda$ . The more of the distribution the function captures, the faster the decay.
Subgaussian means Gaussian-quality tails without being Gaussian. It is preserved by scaling and independent sums, so sample means of subgaussian rewards concentrate like $e^{-n\varepsilon^2/2\sigma^2}$ at every finite $n$ . Bounded rewards are subgaussian (Hoeffding); exponential and $\chi^2$ are not.
The confidence width is $\sqrt{2\sigma^2\log(1/\delta)/n}$ . Reliability costs only $\sqrt{\log(1/\delta)}$ , which is what makes union bounds over arms and rounds affordable, and is the core of UCB.
The CLT is the wrong tool for algorithms. It is asymptotic, its error is $1/\sqrt n$ even when tails are far smaller, and at large-deviation scales its rate is wrong. The right rate is a Legendre transform, which for Bernoulli rewards is a KL divergence.
Use the variance when it’s small. Bennett and Bernstein add a range term but replace the worst-case scale with the true variance, which pays off for low-variance arms.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 5
Boucheron, Lugosi & Massart, Concentration Inequalities (2013) — recommended further reading and exercises

Related

Concentration of Measure for Bandits

Motivation: how long does it take to learn a mean?

Tail probabilities

Markov and Chebyshev

Calibrating with the central limit theorem

The Cramér–Chernoff method and subgaussian random variables

The sample mean

Which variables are subgaussian

Converse: Gaussian tails imply subgaussianity, with slack

Hoeffding

Bennett and Bernstein: use the variance

Large deviations: the exact exponential rate

Smaller constants for Bernoulli

$\chi^2$ : Chernoff without a global MGF

Maxima and categorical distributions

Quick reference

References

Mentioned in

Related

Motivation: how long does it take to learn a mean?

Tail probabilities

Markov and Chebyshev

Calibrating with the central limit theorem

The Cramér–Chernoff method and subgaussian random variables

The sample mean

Which variables are subgaussian

Refinements and companions (Notes and Exercises)

Converse: Gaussian tails imply subgaussianity, with slack

Hoeffding

Bennett and Bernstein: use the variance

Large deviations: the exact exponential rate

Smaller constants for Bernoulli

χ2\chi^2χ2: Chernoff without a global MGF

Maxima and categorical distributions

Quick reference

References

Mentioned in

$\chi^2$ : Chernoff without a global MGF