Lower Bounds for Finite-Armed Bandits

Corresponds to Lattimore & Szepesvári, Part IV introduction and Chapters 13–17. Chapter 14 (foundations of information theory) is condensed to what the lower bounds actually use. The coding view of entropy and relative entropy is in entropy-mutual-information, information-inequalities and data-compression.

Motivation: the real truth is in the lower bounds

ImportantWhy prove lower bounds

An upper bound doesn’t tell you what you’re missing. Only a matching lower bound shows an algorithm is (nearly) optimal.
Lower bounds are usually right first. Historically, upper bounds improve step by step until one finally meets a long-known lower bound.
They reveal what makes a problem hard. The authors’ advice: on a new problem, try the lower bound first. The right algorithm often falls out of it.

DefinitionThe two flavours of lower bound

Flavour	Form of the claim	Use
Worst-case (minimax)	“For any policy you give me, I’ll give you an instance $\nu$ with regret at least $L$ .”	Robustness: adversarial in spirit.
Instance-dependent	”For any reasonable policy, the regret on every instance $\nu$ is at least $L(\nu)$ .”	Refined: shows $O\big(\sum_i(\Delta_i + \frac{\log n}{\Delta_i})\big)$ is unimprovable.

“Reasonable” can’t be dropped. For any $\nu$ , the policy that always plays $\nu$ ‘s optimal arm has zero regret there and linear regret wherever another arm is optimal.

Chapter	Bound	Main tool
13	Heuristic $\Omega(\sqrt{kn})$	Two-point hypothesis testing
14	—	Relative entropy, Bretagnolle–Huber
15	Minimax $\frac1{27}\sqrt{(k-1)n}$	Divergence decomposition
16	Asymptotic $c^*(\nu)\log n$ ; finite-time versions	Consistency, $d_{\inf}$
17	High-probability, stochastic and adversarial	The same two-point argument on tail events

Basic ideas (Chapter 13)

DefinitionWorst-case regret, minimax regret, minimax optimality

For a class of stochastic bandits $\mathcal E$ and the set $\Pi$ of all policies:

$R_n(\pi,\mathcal E) = \sup_{\nu\in\mathcal E}R_n(\pi,\nu), \qquad R_n^*(\mathcal E) = \inf_{\pi\in\Pi}\sup_{\nu\in\mathcal E}R_n(\pi,\nu)$

$\pi$ is minimax optimal for $\mathcal E$ if $R_n(\pi,\mathcal E) = R_n^*(\mathcal E)$ .

Component	Detail
Signature	$R_n^* : \{\text{classes of bandits}\}\times\mathbb N\to[0,\infty]$
Meaning	The best worst-case guarantee any policy can have.
*Small $R_n^$**	The class is easy in the worst case.
Depends on	The class and the horizon. Minimax optimality is a property of (policy, class, horizon), not of a policy alone.

RemarkPractical caveats

Computing a minimax policy is usually infeasible. We settle for “minimax optimal up to constant (or logarithmic) factors”: $R_n(\pi,\mathcal E^k)/R_n^*(\mathcal E^k)\le C$ for all $k, n$ (or $\le C(n,k)$ , logarithmic in $n$ and $k$ ).
Exactly minimax policies may not even be desirable. In classical statistics, minimizing the worst case often gives a flat risk profile: the same regret on easy instances as on hard ones. In practice we want low regret on easy bandits (gaps large or tiny) and higher regret only on hard ones (Chapter 16).

DefinitionGame-theoretic view and Pareto optimality

The minimax regret is the value of a sequential zero-sum game: the protagonist proposes $\pi$ , the antagonist inspects it and picks $\nu\in\mathcal E$ , and the antagonist’s payoff is the regret. Its value for the antagonist is $R_n^*(\mathcal E)$ .
Regret over a class is a multi-objective criterion. $\pi$ is Pareto optimal if no $\pi'$ has $R_n(\pi',\nu)\le R_n(\pi,\nu)$ for all $\nu$ with strict inequality somewhere.

ExamplePareto optimality is weak (Exercise 13.2)

On Gaussian bandits, “always play arm 1” is Pareto optimal. Any $\pi'$ at least as good would need zero regret whenever arm 1 is uniquely optimal, so it must play arm 1 almost surely on those instances. Gaussian outcome laws on different instances are mutually absolutely continuous, so it must do the same everywhere, which makes $\pi' = \pi$ . A terrible policy can still be Pareto optimal. (Argument worked here.)

TheoremTheorem 13.1 — Minimax lower bound (proved in Chapter 15)

Let $\mathcal E^k$ be the $k$ -armed unit-variance Gaussian bandits with means in $[0,1]^k$ . There is a universal $c > 0$ such that $R_n^*(\mathcal E^k)\ge c\sqrt{kn}$ for all $k > 1$ and $n\ge k$ . Together with Theorem 9.1, this makes MOSS minimax optimal up to constants.

Hypothesis testing: how many samples to tell two means apart?

ExampleTwo Gaussian means

$X_1, \ldots, X_n$ i.i.d. $\mathcal N(\mu,1)$ with $\mu\in\{0,\Delta\}$ . The natural test guesses whichever value $\hat\mu$ is closer to. Under $\mu = 0$ it errs iff $\hat\mu\ge\Delta/2$ , and $\hat\mu\sim\mathcal N(0,1/n)$ , so

$\frac{\sqrt{8/\pi}\,e^{-n\Delta^2/8}}{\sqrt{n\Delta^2} + \sqrt{n\Delta^2 + 16}}\le\mathbb P\Big(\hat\mu\ge\frac\Delta2\Big)\le\frac{\sqrt{8/\pi}\,e^{-n\Delta^2/8}}{\sqrt{n\Delta^2} + \sqrt{n\Delta^2 + 32/\pi}} \tag{13.1}$

using Abramowitz–Stegun’s tail bounds $\frac{e^{-x^2}}{x + \sqrt{x^2+2}}\le\int_x^\infty e^{-t^2}dt\le\frac{e^{-x^2}}{x + \sqrt{x^2 + 4/\pi}}$ (13.4).

Reading: once $n\gg8/\Delta^2$ , the error probability falls exponentially. But if $n\lesssim1/\Delta^2$ , the test fails with constant probability. Nearest-mean is in fact the minimax test (Exercise 13.1; ML rule).

ImportantThe recipe: competition versus similarity

Pick two bandit instances that are

competing: what is good in one is bad in the other (different optimal arms), and
similar: close enough that the policy can’t reliably tell which one it faces.

These pull in opposite directions (separated means versus close means), and the lower bound comes from optimizing the trade-off.

DerivationThe heuristic

\sqrt{kn}

argument

Instance 1: $\mu = (\Delta, 0, \ldots, 0)$ , with regret $R_n(\pi,\nu) = \Delta(n - \mathbb E[T_1(n)])$ (13.2).

Find the neglected arm: let $i = \arg\min_{j>1}\mathbb E[T_j(n)]$ . Since $n\ge(k-1)\mathbb E[T_i(n)]$ , we have $\mathbb E[T_i(n)]\le\frac n{k-1}$ .

Instance 2: the same, except $\mu_i' = 2\Delta$ , so arm $i$ is now optimal by $\Delta$ . Then $R_n(\pi,\nu')\ge\Delta\mathbb E'[T_1(n)]$ (13.3).

Tune $\Delta$ to the information available: the instances differ only on arm $i$ , sampled about $\frac n{k-1}$ times. Choose $\Delta = \sqrt{1/\mathbb E[T_i(n)]}\ge\sqrt{(k-1)/n}$ , which is exactly the undetectable scale. Then $\mathbb E[T_1(n)]\approx\mathbb E'[T_1(n)]$ :

if $\mathbb E[T_1(n)] < n/2$ : $R_n(\pi,\nu)\ge\frac n2\sqrt{\frac{k-1}n} = \frac12\sqrt{n(k-1)}$ ;
otherwise: $R_n(\pi,\nu')\ge\Delta\mathbb E'[T_1(n)]\approx\Delta\mathbb E[T_1(n)]\ge\frac12\sqrt{n(k-1)}$ .

Sloppy points: $T_i(n)$ is random, and “can’t tell apart” isn’t quantified. Chapters 14–15 fix both.

The information-theoretic toolkit (Chapter 14, condensed)

NoteCoding interpretation, briefly

Entropy $H(P) = \sum_ip_i\log\frac1{p_i}$ (in nats; $H_2$ in bits) is the optimal expected code length per symbol, with Huffman within one bit, $H_2\le L^*\le H_2 + 1$ . Relative entropy $D(P,Q)$ is the extra expected length from using the code built for $Q$ when the data come from $P$ . Details in data-compression and data-compression. Kraft’s inequality justifies restricting to prefix codes (Exercises 14.1, 14.3).

DefinitionRelative entropy for general measures

For probability measures on $(\Omega,\mathcal F)$ , discretize and take the worst case:

$D(P,Q) = \sup_{N\in\mathbb N^+}\ \sup_{X:\Omega\to[N]}D(P_X,Q_X) \tag{14.5}$

over measurable maps $X$ , with $P_X$ the push-forward. (Dobrushin: generating fields suffice.)

TheoremTheorem 14.1 — Density form

$D(P,Q) = \begin{cases}\displaystyle\int\log\Big(\frac{dP}{dQ}\Big)dP & P\ll Q,\\[4pt] \infty & \text{otherwise.}\end{cases}$

With a common dominating measure $\lambda$ (for example $P + Q$ ), $D(P,Q) = \int p\log\frac pq\,d\lambda$ (14.6).

Fact	Detail
Nonnegativity	$D(P,Q)\ge0$ , with equality iff $P = Q$ (Gibbs)
Not a metric	Asymmetric; no triangle inequality
Finite needs $P\ll Q$	but $P\ll Q$ doesn’t guarantee finiteness on infinite spaces (Exercise 14.2)
Gaussians, common variance	$D(\mathcal N(\mu_1,\sigma^2),\mathcal N(\mu_2,\sigma^2)) = \frac{(\mu_1-\mu_2)^2}{2\sigma^2}$
Gaussians, general (Ex. 14.7)	$\frac12\big(\log\frac{\sigma_2^2}{\sigma_1^2} + \frac{\sigma_1^2}{\sigma_2^2} - 1\big) + \frac{(\mu_1-\mu_2)^2}{2\sigma_2^2}$
Bernoulli	$d(p,q) = p\log\frac pq + (1-p)\log\frac{1-p}{1-q}$ (KL-UCB)

TheoremTheorem 14.2 — Bretagnolle–Huber inequality

For probability measures $P, Q$ on the same space and any event $A$ ,

$P(A) + Q(A^c)\ge\frac12\exp\big(-D(P,Q)\big) \tag{14.7}$

The roles of $P$ and $Q$ can be swapped, which helps since $D$ is asymmetric.

IntuitionClose distributions can’t be separated by any event

$P(A)$ is the error of “declare $Q$ on $A$ ” when the truth is $P$ , and $Q(A^c)$ is the error when the truth is $Q$ . If $D(P,Q)$ is small, every test has substantial total error. If $P = Q$ , the sum is exactly 1; the bound gives $\frac12$ .

ProofLe Cam’s inequality, then Jensen

Trivial if $D = \infty$ , so assume $P\ll Q$ . Let $\nu = P + Q$ , $p = \frac{dP}{d\nu}$ , $q = \frac{dQ}{d\nu}$ . It’s enough to show $\int p\wedge q\ge\frac12e^{-D(P,Q)}$ , because $\int p\wedge q\le\int_Ap + \int_{A^c}q = P(A) + Q(A^c)$ .

Step 1 (Le Cam): $\int p\wedge q\ge\frac12\big(\int\sqrt{pq}\big)^2$ . Since $pq = (p\wedge q)(p\vee q)$ , Cauchy–Schwarz gives $\big(\int\sqrt{pq}\big)^2\le\int p\wedge q\int p\vee q$ , and $\int p\vee q = 2 - \int p\wedge q\le2$ .

Step 2 (Jensen):

$\Big(\int\sqrt{pq}\Big)^2 = \exp\Big(2\log\int_{p>0}p\sqrt{\frac qp}\Big)\ge\exp\Big(2\int_{p>0}p\cdot\frac12\log\frac qp\Big) = e^{-D(P,Q)}$

Absolute continuity ensures $p > 0\Rightarrow q > 0$ .

∎

ExampleNo test of a weak signal is reliable

One observation from $\mathcal N(0,\sigma^2)$ (call it $P$ ) or $\mathcal N(\Delta,\sigma^2)$ (call it $Q$ ), with $\Delta^2/\sigma^2\le1$ . For any rejection region $A$ , $P(A) + Q(A^c)\ge\frac12e^{-\Delta^2/2\sigma^2}\ge\frac12e^{-1/2}\ge\frac3{10}$ , so $\max\{P(A),Q(A^c)\}\ge\frac3{20}$ , whatever the test.

RemarkRefinements and relatives

Equality case / Neyman–Pearson: $P(A) + Q(A^c)\ge\int p\wedge q$ is an equality for $A = \{p\le q\}$ , the likelihood-ratio test. More generally, likelihood-ratio tests are the most powerful at each significance level, and essentially the only ones (Exercises 14.14–14.15; LRTs).
Sharper versions: $P(A) + Q(A^c)\ge1 - \sqrt{1 - e^{-D}}$ (14.11), which dominates (14.7). For small $D$ , Pinsker is better.
Pinsker: $\delta(P,Q) = \sup_A|P(A) - Q(A)|\le\sqrt{D(P,Q)/2}$ , so $P(A) + Q(A^c)\ge1 - \sqrt{D/2}$ (14.12–14.13). That is vacuous for large $D$ , where Bretagnolle–Huber still works.
Other distances: total variation $\delta$ , Hellinger $h(P,Q)^2 = \int(\sqrt p - \sqrt q)^2 = 2(1 - \int\sqrt{pq})$ , and $\chi^2(P,Q) = \int\frac{p^2}q - 1$ : $\delta^2\le h^2\le D\le\chi^2 \tag{14.16}$ Each is tight for some pair. Bounded integrands obey $|\int X\,dP - \int X\,dQ|\le(b-a)\delta(P,Q)$ (Exercise 14.4).
Data processing: $D(P|_{\mathcal G},Q|_{\mathcal G})\le D(P,Q)$ for any sub-σ-algebra (Exercise 14.10; data processing).
Chain rule: $D(P,Q) = \sum_t\mathbb E_P\big[D(P_t(\cdot\mid X^{t-1}),Q_t(\cdot\mid X^{t-1}))\big]$ (Exercise 14.12), and it holds with a stopping time in place of $n$ (Exercise 14.13).

Minimax lower bounds (Chapter 15)

Relative entropy between bandits

LemmaLemma 15.1 — Divergence decomposition

Fix a policy $\pi$ and bandits $\nu = (P_i)$ , $\nu' = (P_i')$ , with outcome laws $\mathbb P_\nu$ , $\mathbb P_{\nu'}$ on the canonical model. Then

$D(\mathbb P_\nu,\mathbb P_{\nu'}) = \sum_{i=1}^k\mathbb E_\nu[T_i(n)]\,D(P_i,P_i') \tag{15.1}$

ProofThe policy terms cancel in the likelihood ratio

Step 1: Densities. With respect to $(\rho\times\lambda)^n$ , the outcome density is $\prod_t\pi_t(a_t\mid h_{t-1})p_{a_t}(x_t)$ , and the same for $\nu'$ with $p'$ . The policy is the same, so

$\log\frac{d\mathbb P_\nu}{d\mathbb P_{\nu'}} = \sum_{t=1}^n\log\frac{p_{A_t}(X_t)}{p_{A_t}'(X_t)} \tag{15.2}$

Step 2: Condition on the action. Given $A_t$ , $X_t\sim P_{A_t}$ under $\nu$ , so $\mathbb E_\nu\big[\log\frac{p_{A_t}(X_t)}{p'_{A_t}(X_t)}\big] = \mathbb E_\nu[D(P_{A_t},P'_{A_t})]$ .

Step 3: Regroup by arm. $\sum_t\mathbb E_\nu[D(P_{A_t},P'_{A_t})] = \sum_i\mathbb E_\nu\big[\sum_t\mathbb I\{A_t = i\}\big]D(P_i,P_i')$ . If some $D(P_i,P_i') = \infty$ with positive expected pulls, both sides are infinite.

∎

IntuitionInformation accrues only where you look

Distinguishing $\nu$ from $\nu'$ costs exactly the per-sample divergence of each arm times how often the policy samples it. An arm that is rarely pulled is an arm about which $\nu$ and $\nu'$ may disagree undetected. This is the regret decomposition’s information-theoretic twin.

RemarkGeneralizations

For general action spaces, $D(\mathbb P_\nu,\mathbb P_{\nu'}) = \int_{\mathcal A}D(P_a,P_a')\,dG_\nu(a) = \mathbb E\sum_tD(P_{A_t},P'_{A_t})$ (Exercise 15.8). With a stopping time, for any $\mathcal F_\tau$ -measurable $X$ , $D(\mathbb P_{\nu,X},\mathbb P_{\nu',X})\le\sum_i\mathbb E_\nu[T_i(\tau)]D(P_i,P_i')$ (Exercise 15.7).

The minimax lower bound

TheoremTheorem 15.2 — Minimax lower bound for Gaussian bandits

Let $k > 1$ and $n\ge k - 1$ . For every policy $\pi$ there is $\mu\in[0,1]^k$ with

$R_n(\pi,\nu_\mu)\ge\frac1{27}\sqrt{(k-1)n}$

where $\nu_\mu$ is the unit-variance Gaussian bandit with means $\mu$ . Hence $R_n^*(\mathcal E^k_N(1))\ge\frac1{27}\sqrt{(k-1)n}$ .

ProofTwo instances, Bretagnolle–Huber, divergence decomposition

Step 1: Instances. $\mu = (\Delta, 0, \ldots, 0)$ with $\Delta\in[0,\frac12]$ . Let $i = \arg\min_{j>1}\mathbb E_\mu[T_j(n)]$ , so $\mathbb E_\mu[T_i(n)]\le\frac n{k-1}$ . Set $\mu' = \mu$ except $\mu_i' = 2\Delta$ .

Step 2: Regret in terms of one event. By the regret decomposition,

$R_n(\pi,\nu_\mu)\ge\mathbb P_\mu\Big(T_1(n)\le\frac n2\Big)\frac{n\Delta}2, \qquad R_n(\pi,\nu_{\mu'}) > \mathbb P_{\mu'}\Big(T_1(n) > \frac n2\Big)\frac{n\Delta}2$

(in $\nu_{\mu'}$ , every pull of arm 1 costs $\Delta$ ).

Step 3: Bretagnolle–Huber with $A = \{T_1(n)\le n/2\}$ .

$R_n(\pi,\nu_\mu) + R_n(\pi,\nu_{\mu'}) > \frac{n\Delta}2\big(\mathbb P_\mu(A) + \mathbb P_{\mu'}(A^c)\big)\ge\frac{n\Delta}4e^{-D(\mathbb P_\mu,\mathbb P_{\mu'})} \tag{15.3}$

Step 4: Divergence decomposition. Only arm $i$ differs:

$D(\mathbb P_\mu,\mathbb P_{\mu'}) = \mathbb E_\mu[T_i(n)]\frac{(2\Delta)^2}2\le\frac{2n\Delta^2}{k-1}$

Step 5: Tune. $\Delta = \sqrt{(k-1)/(4n)}\le\frac12$ (using $n\ge k-1$ ) makes the exponent $-\frac12$ . So the sum of the two regrets is at least $\frac18\sqrt{(k-1)n}\,e^{-1/2}\approx0.076\sqrt{(k-1)n}$ , and the larger of the two is at least half that, $\ge\frac1{27}\sqrt{(k-1)n}$ .

∎

ImportantWhy the antagonist must look at the policy

The second instance perturbs the arm this policy neglects. A fixed pair of instances (classical Le Cam) can’t capture how a sequential policy distributes its samples. Choosing $\nu'$ after seeing $\pi$ is what produces the $\sqrt k$ .

RemarkWhy Gaussians are not special: Fisher information

All the proof used was $D(P_\mu,P_{\mu+\Delta}) = O(\Delta^2)$ for small gaps. For a smooth parametric family indexed by its mean, Taylor-expanding in $\Delta$ gives

$D(P_\mu,P_{\mu+\Delta})\approx\underbrace{-\frac{\partial}{\partial\Delta}\int dP_{\mu+\Delta}\Big|_{\Delta=0}}_{=0}\Delta + \frac12I(\mu)\Delta^2, \qquad I(\mu) = -\int\frac{\partial^2}{\partial\Delta^2}\log p_{\mu+\Delta}\Big|_{\Delta=0}p_\mu\,d\lambda$

The first-order term vanishes because total mass is constant; $I(\mu)$ is the Fisher information. So for any sufficiently rich, non-bizarre class, the KL is quadratic in the gap and the minimax regret is $\Omega(\sqrt{nk})$ .

Note $\Omega(\sqrt{nk})$ versus $O(\log n)$ : no contradiction

The logarithmic upper bounds carry factors $1/\Delta_i$ . The hard instances here have $\Delta\approx\sqrt{k/n}$ , where $\frac{\log n}\Delta$ is of order $\sqrt{nk}$ , up to logs.

RemarkLe Cam’s method and Assouad’s method

Le Cam: for estimating $\theta(P)$ from i.i.d. samples under a metric $d$ , any two $P_0, P_1$ give $\rho_n^*\ge\frac{d(\theta(P_0),\theta(P_1))}8e^{-nD(P_0,P_1)}$ (15.5). The bandit version differs in being sequential and in choosing $P_1$ after seeing the algorithm.
Assouad-style proof (Exercise 15.2): compare all $k$ instances $\mu^{(i)} = \Delta e_i$ against $\mu^{(0)} = 0$ . Pinsker and Exercise 14.4 give $\mathbb E_i[T_i]\le\mathbb E_0[T_i] + c\sqrt{nk\mathbb E_0[T_i]}$ ; summing with Jensen gives $\sum_i\mathbb E_i[T_i]\le n + ckn$ . So some instance has $R\ge\frac18\sqrt{kn}$ . This version is due to Auer et al.

TheoremFurther minimax facts (Exercises 15.3–15.6)

Small horizon ( $n < k$ ): some instance has regret at least $\frac{n(2k - n - 1)}{2k} > \frac n2$ .
Bernoulli bandits: $R_n^*(\mathcal E^k_B)\ge c\sqrt{nk}$ for $2\le k\le n$ . Bound KL by $\chi^2$ to handle Bernoulli divergences near the boundary.
The $\sum_i\Delta_i$ term in MOSS’s bound can’t be removed: pull counts are integers, and each arm must be tried.
ETC is not minimax optimal: for every exploration length $m$ , some instance has $R_n\ge c\min\{n, n^{2/3}k^{1/3}\}$ .

RemarkHistory

Vogel (1960) gave a precise minimax analysis of two-armed Bernoulli bandits. Bretagnolle–Huber entered bandits with Bubeck et al. (2013). The proof above follows Gerchinovitz–Lattimore (2016).

Instance-dependent lower bounds (Chapter 16)

IntuitionYou can’t be great everywhere

Order instances by difficulty. Minimax optimality says no policy can stay entirely below the flat $\sqrt n$ line. Instance optimality says something stronger: any policy that beats the instance-dependent line on some instances must pay above it on others. “Always play arm 1” has zero regret when arm 1 is optimal and linear regret otherwise, an extreme over-specialization. This trade-off is the nature of bandits.

Asymptotic bounds

DefinitionConsistent policy (Def. 16.1)

$\pi$ is consistent over $\mathcal E$ if for every $\nu\in\mathcal E$ and every $p > 0$ ,

$\lim_{n\to\infty}\frac{R_n(\pi,\nu)}{n^p} = 0 \tag{16.1}$

(subpolynomial regret everywhere). UCB is consistent on $\mathcal E^k_{SG}(1)$ . “Always play arm 1” is consistent only if arm 1 is always optimal.

WarningConsistency is purely asymptotic

A consistent policy could play arm 1 for the first $10^{100}$ rounds. Consistency supports only asymptotic lower bounds. Finite-time versions need a finite-time analogue (Section 16.2).

Definition $d_{\inf}$ : the cheapest way to make an arm look optimal

For a set of distributions $\mathcal M$ with means, $P\in\mathcal M$ with mean $\mu(P) < \mu^*$ :

$d_{\inf}(P,\mu^*,\mathcal M) = \inf_{P'\in\mathcal M}\{D(P,P') : \mu(P') > \mu^*\}$

The smallest divergence from $P$ to any distribution in the class whose mean beats the current best.

Component	Detail
Signature	$d_{\inf} : \mathcal M\times\mathbb R\times\{\text{classes}\}\to[0,\infty]$
Meaning	Information per pull needed to rule out “arm $i$ is secretly optimal”.
Small	The arm is hard to dismiss, so many pulls are needed.
$\infty$	One pull can rule it out (see the Rademacher example).

TheoremTheorem 16.2 — Asymptotic lower bound (Lai–Robbins; Burnetas–Katehakis)

Let $\mathcal E = \mathcal M_1\times\cdots\times\mathcal M_k$ be unstructured and $\pi$ consistent over $\mathcal E$ . For every $\nu = (P_i)\in\mathcal E$ ,

$\liminf_{n\to\infty}\frac{R_n}{\log n}\ge c^*(\nu,\mathcal E) = \sum_{i:\Delta_i>0}\frac{\Delta_i}{d_{\inf}(P_i,\mu^*,\mathcal M_i)} \tag{16.2}$

ProofPerturb the suboptimal arm until it becomes optimal; consistency forces enough pulls

It suffices to show $\liminf_n\frac{\mathbb E_\nu[T_i(n)]}{\log n}\ge\frac1{d_i}$ for each suboptimal arm $i$ , with $d_i = d_{\inf}(P_i,\mu^*,\mathcal M_i)$ .

Step 1: The alternative. Fix $\varepsilon > 0$ and let $\nu'$ equal $\nu$ except arm $i$ has $P_i'\in\mathcal M_i$ with $D(P_i,P_i')\le d_i + \varepsilon$ and mean $> \mu^*$ . It stays in $\mathcal E$ because the class is unstructured. By Lemma 15.1, $D(\mathbb P_\nu,\mathbb P_{\nu'})\le\mathbb E_\nu[T_i(n)](d_i + \varepsilon)$ .

Step 2: Two regrets, one event. With $A = \{T_i(n) > n/2\}$ (bad in $\nu$ , good in $\nu'$ ),

$R_n + R_n'\ge\frac n2\min\{\Delta_i,\mu_i' - \mu^*\}\big(\mathbb P_\nu(A) + \mathbb P_{\nu'}(A^c)\big)\ge\frac n4\min\{\cdot\}\,e^{-\mathbb E_\nu[T_i(n)](d_i+\varepsilon)}$

Step 3: Rearrange.

$\liminf_n\frac{\mathbb E_\nu[T_i(n)]}{\log n}\ge\frac1{d_i+\varepsilon}\Big(1 - \limsup_n\frac{\log(R_n + R_n')}{\log n}\Big)$

Step 4: Consistency kills the last term. For every $p > 0$ , $R_n + R_n'\le C_pn^p$ eventually, so the limsup is at most $p$ , hence 0. Then let $\varepsilon\to0$ .

∎

IntuitionWhy $\log n$ pulls, and why that constant

A consistent policy must stay alert to the possibility that arm $i$ is secretly the best, which is the alternative $\nu'$ , where neglecting arm $i$ would cost linear regret. To keep the chance of missing that alternative below $n^{-1+o(1)}$ , it needs $e^{-T_id_i}\lesssim1/n$ , i.e. $T_i\gtrsim\log n/d_i$ . Each such pull costs $\Delta_i$ .

Class $\mathcal M$	$P$ (mean $<\mu^*$ )	$d_{\inf}(P,\mu^*,\mathcal M)$
Gaussian, known variance	$\mathcal N(\mu,\sigma^2)$	$\frac{(\mu - \mu^*)^2}{2\sigma^2}$
Gaussian, unknown variance	$\mathcal N(\mu,\sigma^2)$	$\frac12\log\big(1 + \frac{(\mu - \mu^*)^2}{\sigma^2}\big)$
Bernoulli	$\mathcal B(\mu)$	$d(\mu,\mu^*)$
Uniform	$\mathcal U(a,b)$	$\log\big(1 + \frac{2(\mu^* - (a+b)/2)}{b-a}\big)$

DefinitionAsymptotic optimality

$\pi$ is asymptotically optimal on $\mathcal E$ if $\lim_n\frac{R_n(\pi,\nu)}{\log n} = c^*(\nu,\mathcal E)$ for all $\nu\in\mathcal E$ (16.3). For most classes such a policy exists (Burnetas–Katehakis). Examples: UCB with $\log f(t)$ on unit-variance Gaussians ( $c^* = \sum\frac2{\Delta_i}$ , Chapter 8), and KL-UCB on Bernoulli ( $c^* = \sum\frac{\Delta_i}{d(\mu_i,\mu^*)}$ ).

WarningETC and elimination are not asymptotically optimal

However they are tuned, they pay an extra multiplicative factor of 2 on Gaussian bandits (Garivier et al. 2016): committing in phases wastes information.

RemarkScope

Unstructured classes only. With structure, pulling one arm informs about others, and lower bounds must be derived case by case.
Nonparametric classes: solved exactly for bounded support (Honda–Takemura 2010), partly for semi-bounded support, and up to constants for bounded kurtosis.
Exponential families: the KL-UCB-type bound of Exercise 10.4 is tight (Exercise 16.3).

Finite-time bounds

LemmaLemma 16.3 — Finite-time pull lower bound

Let $\nu, \nu'$ differ only in arm $i$ , with $i$ suboptimal in $\nu$ and uniquely optimal in $\nu'$ , and let $\lambda = \mu_i(\nu') - \mu_i(\nu)$ . For any policy,

$\mathbb E_{\nu\pi}[T_i(n)]\ge\frac{\log\frac{\min\{\lambda - \Delta_i(\nu),\ \Delta_i(\nu)\}}4 + \log n - \log\big(R_n(\nu) + R_n(\nu')\big)}{D(P_i,P_i')} \tag{16.4}$

This is Bretagnolle–Huber plus divergence decomposition, without taking limits.

TheoremTheorem 16.4 — Nearly minimax-optimal policies can’t beat UCB by much

Let $\nu$ be a Gaussian bandit with means $\mu$ and gaps $\Delta$ , and $\mathcal E(\nu) = \{\nu' : \mu_i(\nu')\in[\mu_i,\mu_i + 2\Delta_i]\ \forall i\}$ . If $R_n(\pi,\nu')\le Cn^p$ for all $n$ in some set $\mathcal N$ and all $\nu'\in\mathcal E(\nu)$ (with $p\in(0,1)$ ), then for $\varepsilon\in(0,1]$ and $n\in\mathcal N$ ,

$R_n(\pi,\nu)\ge\frac2{(1+\varepsilon)^2}\sum_{i:\Delta_i>0}\Big(\frac{(1-p)\log n + \log\frac{\varepsilon\Delta_i}{8C}}{\Delta_i}\Big)^+ \tag{16.5}$

ProofApply Lemma 16.3 with the arm raised to just above optimal

For suboptimal $i$ , take $\nu'$ with $\mu_i(\nu') = \mu_i + \Delta_i(1+\varepsilon)$ , so $\lambda = \Delta_i(1+\varepsilon)$ , $\lambda - \Delta_i = \varepsilon\Delta_i$ , and $D = \frac{\Delta_i^2(1+\varepsilon)^2}2$ . With $R_n + R_n'\le2Cn^p$ ,

$\mathbb E[T_i(n)]\ge\frac2{\Delta_i^2(1+\varepsilon)^2}\Big((1-p)\log n + \log\frac{\varepsilon\Delta_i}{8C}\Big)$

Multiply by $\Delta_i$ and sum (regret decomposition).

∎

IntuitionRobustness costs at most a constant factor

Assuming only that the policy is not terrible on nearby instances (polynomial regret with exponent $p$ ), it must pay about $(1-p)\sum\frac{2\log n}{\Delta_i}$ . For $p = \frac12$ , any nearly minimax policy, that is about half the asymptotic constant. The gap may be real: this larger class of policies includes ones tuned to particular instances.

ExampleEdge cases (Exercises 16.2, 16.4, 16.6–16.8)

Infinite $d_{\inf}$ gives bounded regret. For shifted Rademacher rewards ( $\mu\pm1$ each with probability $\frac12$ ), distributions with different means have disjoint supports, so $d_{\inf} = \infty$ , and a policy with $R_n\le3\sum_i\Delta_i$ for all $n$ exists. The Fisher-information heuristic assumed a smooth, “not too bizarre” family, which this is not.
Unknown subgaussian constant gives $d_{\inf} = 0$ . On the class of all subgaussian distributions (any $\sigma$ ), every consistent policy has $\liminf R_n/\log n = \infty$ . Yet for any $f(n) = \omega(\log n)$ some policy achieves $R_n = o(f(n))$ : consistent, just not logarithmic.
Refining lower-order terms (two arms): if $R_n\le\frac{C\log n}{\Delta}$ on all instances with $\Delta\le1$ , then $R_n\ge\frac1{2\Delta}\log\frac{n\Delta^2}{8C\log n}$ . The $\log(n\Delta^2)$ form of MOSS-type bounds is essentially necessary.
UCB-V’s bound is sharp: no policy can have $\limsup R_n/\log n\le cb$ (no gap dependence) or $\le c\sum_i\sigma_i^2/\Delta_i$ (no range term) on all $[0,b]$ -bounded bandits. Both terms of $(b + \frac{\sigma_i^2}{\Delta_i})\log n$ are needed.
Optimality costs variance: if $\limsup R_n/\log n\le\sum\frac{2(1+p)}{\Delta_i}$ on Gaussian bandits, then some instance has pseudo-regret variance at least about $n^{1-p}$ . Being asymptotically optimal ( $p\to0$ ) forces the unstable regret seen in MOSS’s second problem.

High-probability lower bounds (Chapter 17)

Setting expectations. Exp3-IX gave two kinds of high-probability bound:

Algorithm	Guarantee with probability $1-\delta$	Can be integrated to bound $\mathbb E$ ?
One algorithm for all $\delta$	$O\big(\sqrt{kn\log k} + \sqrt{\frac{kn}{\log k}}\log\frac1\delta\big)$ (17.1)	Yes: $R_n\le\int_0^\infty\mathbb P(\hat R_n\ge u)du = O(\sqrt{kn\log k})$
Tuned to a given $\delta$	$O\big(\sqrt{kn\log\frac k\delta}\big)$ (17.2)	Only via $R_n\le n\delta + O(\sqrt{kn\log\frac k\delta})$ , giving $O(\sqrt{kn\log n})$

The question is whether the order of quantifiers really matters. It does: both bounds are tight up to constants.

Stochastic bandits

DefinitionRandom pseudo-regret

$\bar R_n = \sum_iT_i(n)\Delta_i$ , random through the pull counts. Here $\mathcal E^k$ denotes $k$ -armed unit-variance Gaussian bandits with gaps at most 1.

TheoremTheorem 17.1 — Low expected regret forces heavy tails

If $R_n(\pi,\nu)\le B\sqrt{(k-1)n}$ for all $\nu\in\mathcal E^k$ , then for every $\delta\in(0,1)$ there is $\nu\in\mathcal E^k$ with

$\mathbb P\Big(\bar R_n(\pi,\nu)\ge\frac14\min\Big\{n,\ \frac1B\sqrt{(k-1)n}\log\frac1{4\delta}\Big\}\Big)\ge\delta$

ProofThe same two-instance argument, on a tail event

Step 1: $\mu = (\Delta, 0, \ldots, 0)$ , with $i$ the least-pulled suboptimal arm. By the regret decomposition and the assumption, $\mathbb E[T_i(n)]\le\frac{R_n}{\Delta(k-1)}\le\frac B\Delta\sqrt{\frac n{k-1}}$ (17.5).

Step 2: $\mu' = \mu$ except $\mu_i' = 2\Delta$ . Then $D = \mathbb E[T_i(n)]\cdot2\Delta^2\le2B\Delta\sqrt{n/(k-1)}$ .

Step 3: $\{T_i(n)\ge n/2\}$ forces $\bar R_n\ge\Delta n/2$ in $\nu$ , and its complement forces $\bar R_n'\ge\Delta n/2$ in $\nu'$ . By Bretagnolle–Huber,

$\mathbb P\Big(\bar R_n\ge\frac{\Delta n}2\Big) + \mathbb P'\Big(\bar R_n'\ge\frac{\Delta n}2\Big)\ge\frac12\exp\Big(-2B\Delta\sqrt{\frac n{k-1}}\Big)\ge2\delta$

with $\Delta = \min\big\{\frac12, \frac1{2B}\sqrt{\frac{k-1}n}\log\frac1{4\delta}\big\}$ . One of the two probabilities is at least $\delta$ .

∎

CorollaryCorollary 17.2 — Tuning for one δ can’t do better than $\sqrt{nk\log(1/\delta)}$

For any $\pi$ and $\delta$ with $n\delta\le\sqrt{n(k-1)\log\frac1{4\delta}}$ , some $\nu\in\mathcal E^k$ has

$\mathbb P\Big(\bar R_n\ge\frac14\min\Big\{n,\ \sqrt{\frac{n(k-1)}2\log\frac1{4\delta}}\Big\}\Big)\ge\delta$

Proof by contradiction: otherwise $R_n\le n\delta + \sqrt{\cdot}\le\sqrt{2n(k-1)\log\frac1{4\delta}}$ , and Theorem 17.1 with $B = \sqrt{2\log\frac1{4\delta}}$ produces exactly such an instance.

CorollaryCorollary 17.3 — A single algorithm can’t have sub-exponential tails

For $p\in(0,1)$ and $B > 0$ , no policy satisfies $\mathbb P\big(\bar R_n\ge B\sqrt{(k-1)n}\log^p\frac1\delta\big) < \delta$ for all $n$ , $\delta$ and $\nu$ . Such tails would integrate to $R_n\le B'\sqrt{(k-1)n}$ , and then Theorem 17.1 gives a tail of order $\frac1{B'}\sqrt{(k-1)n}\log\frac1{4\delta}$ , which grows faster in $\log(1/\delta)$ than $\log^p$ . Small expected regret forces the tail to grow linearly in $\log\frac1\delta$ . The authors conjecture that $\mathbb P\big(\bar R_n\ge B\sqrt{kn}\log\frac1\delta\big)\le\delta$ is achievable.

ImportantKnowing δ in advance really helps

A single all- $\delta$ algorithm pays $\sqrt{nk}\log\frac1\delta$ ; a $\delta$ -tuned algorithm pays $\sqrt{nk\log\frac1\delta}$ . Both are tight. The price of the all- $\delta$ guarantee is $\sqrt{\log(1/\delta)/\log k}$ , small but real. It buys integrability, i.e. an expected-regret bound.

Adversarial bandits

TheoremTheorem 17.4 — High-probability lower bound against an adversary

For suitable universal constants $c, C$ , if $n\ge Ck\log\frac1{2\delta}$ , then for every policy there is a reward sequence $x\in[0,1]^{n\times k}$ with

$\mathbb P\Big(\hat R_n\ge c\sqrt{nk\log\frac1{2\delta}}\Big)\ge\delta$

No assumption on the algorithm is needed.

ProofSketch: random clipped-Gaussian adversaries

Two difficulties compared with the stochastic case: rewards must lie in $[0,1]$ , and the target is the adversarial regret $\hat R_n$ against the best arm in hindsight, not the pseudo-regret.

Claim 17.5 (averaging): if a random reward table $X\sim Q$ gives tail probability at least $\delta$ on average, some fixed table $x$ does too. So it suffices to randomize the adversary.

Construction: let $\eta_t\sim\mathcal N(\frac12,\sigma^2)$ be a common noise term for each round. Arm 1 pays $\mathrm{clip}_{[0,1]}(\eta_t + \Delta)$ , arm $i$ (in instance $Q_i$ ) pays $\mathrm{clip}(\eta_t + 2\Delta)$ , and the rest pay $\mathrm{clip}(\eta_t)$ . Arms are correlated within a round but i.i.d. across rounds.

Claim 17.6: with $\Delta = \sigma\sqrt{\frac{k-1}{2n}\log\frac1{8\delta}}$ , some $i$ has $\mathbb P_{Q_i}(T_i(n) < n/2)\ge2\delta$ . This is the stochastic argument with a new KL computation.

Relating to the regret: within a round, the shared noise makes the gaps exact unless clipping occurs:

$\hat R_n\ge\Delta\Big(n - T_i(n) - \sum_t\mathbb I\{\exists j : X_{tj}\in\{0,1\}\}\Big) \tag{17.8}$

Claim 17.7: with $\sigma = \frac1{10}$ , $\Delta < \frac18$ and $n\ge32\log\frac1\delta$ , clipping occurs in at least $n/4$ rounds with probability at most $\delta$ . Combining the claims gives $\mathbb P_{Q_i}(\hat R_n\ge n\Delta/4)\ge\delta$ . (Proofs: Exercise 17.1; details in Gerchinovitz–Lattimore 2016.)

∎

IntuitionThe best arm is best in every round, and it doesn’t help

Under $Q_i$ , arm $i$ has the highest reward in every round, not just on average. Yet with bandit feedback the learner sees one reward per round, and the shared noise $\eta_t$ hides which arm is best, so it can’t exploit this.

ImportantExp3-IX is nearly tight

If an algorithm has $R_n\le B\sqrt{kn}$ , then for small $\delta$ some adversary forces $\mathbb P\big(\hat R_n\ge\frac cB\sqrt{kn}\log\frac1{2\delta}\big)\ge\delta$ . That matches the $\log\frac1\delta$ term of Exp3-IX’s all- $\delta$ bound up to constants. Gerchinovitz–Lattimore also give lower bounds for structured loss matrices (low variance, similar arms).

Quick reference

Object	Statement	Note
Minimax regret	$R_n^*(\mathcal E) = \inf_\pi\sup_\nu R_n(\pi,\nu)$	depends on (class, horizon)
Pareto optimal	no policy weakly better everywhere, strictly somewhere	”always arm 1” qualifies
Testing two means	error $\approx e^{-n\Delta^2/8}$ ; constant if $n\lesssim1/\Delta^2$	(13.1)
Recipe	competing and similar instances	perturb the least-pulled arm
Relative entropy	$\int\log\frac{dP}{dQ}dP$ if $P\ll Q$ , else $\infty$	Gaussian: $\frac{(\mu_1-\mu_2)^2}{2\sigma^2}$
Bretagnolle–Huber	$P(A) + Q(A^c)\ge\frac12e^{-D(P,Q)}$	Le Cam + Jensen
Pinsker	$\delta(P,Q)\le\sqrt{D/2}$	better for small $D$
Distance chain	$\delta^2\le h^2\le D\le\chi^2$
Divergence decomposition	$D(\mathbb P_\nu,\mathbb P_{\nu'}) = \sum_i\mathbb E_\nu[T_i(n)]D(P_i,P_i')$	policy terms cancel
Minimax bound	$R_n^*\ge\frac1{27}\sqrt{(k-1)n}$	$\Delta = \sqrt{(k-1)/4n}$
Fisher information	$D(P_\mu,P_{\mu+\Delta})\approx\frac12I(\mu)\Delta^2$	so $\Omega(\sqrt{nk})$ is generic
ETC lower bound	$c\min\{n, n^{2/3}k^{1/3}\}$	not minimax optimal
Consistency	$R_n = o(n^p)$ for all $p > 0$ , on all instances	asymptotic notion
$d_{\inf}$	$\inf\{D(P,P') : \mu(P') > \mu^*\}$	per-pull information to rule an arm out
Lai–Robbins	$\liminf\frac{R_n}{\log n}\ge\sum\frac{\Delta_i}{d_{\inf}}$	unstructured classes
Gaussian	$c^* = \sum\frac{2\sigma^2}{\Delta_i}$	UCB is optimal
Bernoulli	$c^* = \sum\frac{\Delta_i}{d(\mu_i,\mu^*)}$	KL-UCB is optimal
Finite time	$R_n\gtrsim\frac{2}{(1+\varepsilon)^2}\sum\frac{(1-p)\log n}{\Delta_i}$ if $R_n\le Cn^p$ nearby	half the constant at $p = \frac12$
High probability, stochastic	$R_n\le B\sqrt{kn}$ ⇒ tail $\ge\frac1B\sqrt{kn}\log\frac1\delta$ w.p. $\delta$	no $\log^p$ tails
δ-tuned	at least $\sqrt{nk\log(1/\delta)}$	matches Exp3-IX (tuned)
Adversarial	$\mathbb P(\hat R_n\ge c\sqrt{nk\log\frac1{2\delta}})\ge\delta$	clipped common-noise construction

Facts to keep to hand

Every bound here is a two-point test. Pick a second instance that perturbs exactly the arm the policy samples least, bound the KL between the outcome laws by pulls times per-sample KL, and apply Bretagnolle–Huber to an event that is bad in one instance and good in the other.
Information accrues only where you sample. The divergence decomposition turns “the policy can’t tell” into “the policy didn’t pull that arm enough”. That is why the antagonist chooses its perturbation after seeing the policy.
KL is quadratic in the gap for smooth families. Detecting a gap $\Delta$ needs about $1/\Delta^2$ samples, which gives $\sqrt{nk}$ in the worst case and $\log n/\Delta$ per arm on instances. Non-smooth families (disjoint supports) or overly rich ones (unknown scale) break this, in opposite directions.
Instance optimality is a balance, not a free lunch. Consistency (or near-minimax robustness) forces $\log n/d_{\inf}$ pulls of each suboptimal arm. Doing better on some instances costs linear regret on others, and pushing to the exact constant costs regret variance.
Tails are part of the guarantee. Small expected regret forces tails that grow linearly in $\log\frac1\delta$ . Fixing $\delta$ in advance buys $\sqrt{\log(1/\delta)}$ instead, at the cost of integrability.

References

Lattimore & Szepesvári, Bandit Algorithms — Part IV introduction; Chapters 13–17
Tsybakov, Introduction to Nonparametric Estimation (2008) — information-theoretic lower bounds in statistics

Related