The Exp3 and Exp3-IX Algorithms

Corresponds to Lattimore & Szepesvári, Part III introduction and Chapters 11–12.

Motivation: all models are wrong

IntuitionWhat a bandit model is for

“All models are wrong, but some are useful” (Box). The stochastic model (each arm’s rewards drawn i.i.d. from a fixed distribution) is almost never literally true. The authors’ view: a bandit model exists to predict how algorithms will perform on the problems you will actually face. It can fail in two opposite ways:

Failure	Effect
Too specific	Assumptions detached from reality. Predicted and real performance can diverge catastrophically.
Too general	Algorithms become over-cautious and leave performance on the table.

This is the bias–variance trade-off at the level of modelling. A correct specialized model gives better algorithms; a wrong one can be disastrous.

ImportantWhich stochastic assumptions actually matter

The critical one is that each arm’s mean doesn’t drift over time. That arms have fixed, independent distributions matters much less. Bandits with drifting means are non-stationary (Chapter 31).

DefinitionThe adversarial bandit (informal)

Drop almost every assumption about how rewards are generated. The environment, now called the adversary, may even read the algorithm’s code before choosing rewards. The only thing kept is the objective: compete with the best fixed action in hindsight.

ExampleRandomization is the only defence

One round, two arms. You announce a strategy; your friend secretly picks $x_1, x_2\in\{0,1\}$ ; you play $A$ and suffer regret $\max\{x_1,x_2\} - x_A$ .

Deterministic ( $A = 1$ ): she sets $x_1 = 0$ , $x_2 = 1$ , and your regret is 1.
Randomized (fair coin): her best reply is $x_1\ne x_2$ , and your expected regret is $\frac12$ .

With one round you can’t do better. Over many rounds the adversary’s relative advantage shrinks, to $O(\sqrt{nk})$ out of $n$ .

Adversarial bandit environments

Definition $k$ -armed adversarial bandit

An arbitrary sequence of reward vectors $(x_t)_{t=1}^n$ with $x_t\in[0,1]^k$ , fixed in advance (an oblivious adversary).

flowchart LR
  A["Adversary secretly fixes x_1 ... x_n in [0,1]^k"] --> R["Round t"]
  R --> P["Learner picks a distribution P_t over arms"]
  P --> S["Sample A_t from P_t"]
  S --> O["Observe only X_t = x_t,A_t"]
  O --> R

DefinitionPolicy and regret

A policy is any map $\pi : ([k]\times[0,1])^*\to\mathcal P_{k-1}$ from histories to distributions over arms. No measurability is needed: actions are discrete and rewards are deterministic. The regret is

$R_n(\pi,x) = \max_{i\in[k]}\sum_{t=1}^nx_{ti} - \mathbb E\Big[\sum_{t=1}^nx_{tA_t}\Big] \tag{11.1}$

where the only randomness is the learner’s own. The worst-case regret is $R_n^*(\pi) = \sup_{x\in[0,1]^{n\times k}}R_n(\pi,x)$ , and the minimax regret is $R_n^* = \inf_\pi R_n^*(\pi)$ .

Component	Detail
Signature	$R_n : \Pi\times[0,1]^{n\times k}\to\mathbb R$
Benchmark	The best single arm over the whole game, chosen in hindsight.
Randomness	Only the learner’s sampling, since $x$ is fixed.
Not	The best arm in each round (see the tracking-regret warning below).

TheoremDeterministic policies have linear regret (Exercise 11.2)

For every deterministic policy there is an $x$ with $R_n(\pi,x)\ge n(1 - 1/k)$ .

ProofThe adversary simulates you and zeroes out your choice

A deterministic policy’s action at time $t$ is a function of past rewards, which the adversary can compute in advance. Set $x_{tA_t} = 0$ and $x_{ti} = 1$ for $i\ne A_t$ . The learner earns 0. Each round contributes $k - 1$ to $\sum_i\sum_tx_{ti} = n(k-1)$ , so some arm earns at least $n(k-1)/k$ , and that is the regret.

∎

RemarkUCB and ETC are deterministic

All the algorithms of explore-then-commit-and-ucb-algorithms are deterministic, so all of them suffer linear regret against some adversary. In game-theoretic terms, this is a zero-sum game in which the learner moves first, and moving first without randomizing means being exploited.

WarningCompeting with the best arm in each round is hopeless (Exercise 11.4)

The “tracking” regret $\mathbb E\big[\sum_t\max_ix_{ti} - \sum_tx_{tA_t}\big]$ is at least $n(1-1/k)$ for every policy, randomized or not. Make one uniformly random arm pay 1 each round, independently of the learner. The learner finds it with probability $1/k$ , while the per-round maximum is always 1. The benchmark must be a fixed arm.

Relation to stochastic bandits

TheoremAdversarial regret bounds stochastic regret

Let $\nu$ be a stochastic bandit with rewards in $[0,1]$ , and use the random-table model ( $X_{ti}\sim\nu_i$ , all independent). For any adversarial policy $\pi$ ,

$R_n(\pi,\nu) = \max_i\mathbb E\Big[\sum_t(X_{ti} - X_{tA_t})\Big]\le\mathbb E\Big[\max_i\sum_t(X_{ti} - X_{tA_t})\Big] = \mathbb E[R_n(\pi,X)]\le R_n^*(\pi) \tag{11.2}$

The middle step is Jensen’s inequality, since the maximum is convex (Exercise 11.3).

ImportantConsequences, in both directions

Adversarial ⇒ stochastic: a policy with small worst-case adversarial regret has small worst-case stochastic regret on $[0,1]$ -bounded bandits. It may still be far from the best instance-dependent stochastic performance.
Stochastic lower bounds ⇒ adversarial lower bounds: stochastic Bernoulli bandits force regret at least $c\sqrt{nk}$ (lower-bounds-for-finite-armed-bandits, Exercise 15.4), so $R_n^*\ge c\sqrt{nk}$ .

The adversarial problem is not much harder than the stochastic one in the worst case.

WarningReductions need their assumptions checked

The argument relies on bounded support. “Adversarial algorithms work on stochastic problems” is not a general law; the linear case (Chapter 29) has real subtleties.

NoteMeasurability

Stochastic regret needs policies that are probability kernels (canonical model). The lower-bound transfer is safe because Bernoulli instances have finitely many reward sequences. For infinite action sets, the policy must be measurable in the past actions.

Importance-weighted estimators

The problem. Only the chosen arm’s reward is observed. To rank arms we need estimates of every arm’s reward each round.

DefinitionImportance-weighted estimator (reward-based)

With $P_{ti} = \mathbb P(A_t = i\mid A_1,X_1,\ldots,A_{t-1},X_{t-1}) > 0$ ,

$\hat X_{ti} = \frac{\mathbb I\{A_t = i\}X_t}{P_{ti}} \tag{11.3}$

TheoremUnbiased, with variance proportional to $1/P$

With $\mathbb E_{t-1}$ the conditional expectation given the first $t-1$ rounds,

$\mathbb E_{t-1}[\hat X_{ti}] = x_{ti}, \qquad \mathbb V_{t-1}[\hat X_{ti}] = \frac{x_{ti}^2(1 - P_{ti})}{P_{ti}} \tag{11.4–11.5}$

ProofThe indicator has conditional mean

P_{ti}

, and

P_{ti}

is known

Write $A_{ti} = \mathbb I\{A_t = i\}$ , so $\hat X_{ti} = \frac{A_{ti}}{P_{ti}}x_{ti}$ . Since $P_{ti}$ is determined by the past and $\mathbb E_{t-1}[A_{ti}] = P_{ti}$ ,

$\mathbb E_{t-1}[\hat X_{ti}] = \frac{x_{ti}}{P_{ti}}P_{ti} = x_{ti}, \qquad \mathbb E_{t-1}[\hat X_{ti}^2] = \frac{x_{ti}^2}{P_{ti}^2}P_{ti} = \frac{x_{ti}^2}{P_{ti}}$

Subtract $x_{ti}^2$ .

∎

IntuitionUnbiased by rare jackpots

Most rounds arm $i$ isn’t played, and its estimate is 0. When it is played, its reward is inflated by $1/P_{ti}$ . On average it comes out right, but an arm played with probability $10^{-3}$ produces estimates of size up to $10^3$ . Variance about $1/P$ is the central difficulty of adversarial bandits.

DefinitionLoss-based importance-weighted estimator

$\hat X_{ti} = 1 - \frac{\mathbb I\{A_t = i\}}{P_{ti}}(1 - X_t) \tag{11.6}$

In terms of losses $y = 1 - x$ , $Y_t = 1 - X_t$ and $\hat Y_{ti} = 1 - \hat X_{ti}$ , this is just $\hat Y_{ti} = \frac{\mathbb I\{A_t = i\}Y_t}{P_{ti}}$ : the same formula applied to losses. It is also unbiased, with $\mathbb V_{t-1}[\hat X_{ti}] = y_{ti}^2\frac{1-P_{ti}}{P_{ti}}$ .

	Reward-based (11.3)	Loss-based (11.6)
Values	$[0,\infty)$	$(-\infty, 1]$
Variance	$\propto x_{ti}^2/P_{ti}$	$\propto y_{ti}^2/P_{ti}$
Better when	rewards are small	rewards are large (losses small)
Dangerous surprise	positive (small $P$ , large $X$ ): pushes all other arms’ probabilities toward 0	negative (small $P$ , small $X$ ): pushes the played arm toward 0

ImportantThe one-sided range is what Exp3 needs

The loss-based estimate is bounded above by 1. The Exp3 proof uses $e^x\le1 + x + x^2$ , which only holds for $x\le1$ . That one-sided bound is why Exp3 uses (11.6), and it is also why dangerously small probabilities are more frequent with the reward-based estimator.

RemarkCentring and uniqueness

Subtracting any constant $v$ before importance weighting and adding it back keeps the estimator unbiased and gives the lowest variance for rewards near $v$ , but the best $v$ depends on what is being estimated. Every unbiased estimator of $x_{t1}$ from a single sample has the form $\hat X(i,z) = a_i + \frac{\mathbb I\{i = 1\}z}{P_1}$ with $\langle a,P\rangle = 0$ (Exercise 11.5). There is no unbiased alternative to importance weighting.

The Exp3 algorithm

DefinitionExponential weighting

With $\hat S_{ti} = \sum_{s\le t}\hat X_{si}$ the estimated cumulative reward and learning rate $\eta > 0$ ,

$P_{ti} = \frac{\exp(\eta\hat S_{t-1,i})}{\sum_{j=1}^k\exp(\eta\hat S_{t-1,j})} \tag{11.7}$

This is a softmax of estimated cumulative rewards.

Learning rate	Behaviour
Large $\eta$	$P_t$ concentrates on the estimated leader: aggressive exploitation, but poor arms get tiny probabilities and their estimates explode in variance.
Small $\eta$	$P_t$ stays near uniform: steady exploration, slow to exploit.

AlgorithmExp3 — “exponential-weight algorithm for exploration and exploitation” (Algorithm 9)

Input $n, k, \eta$ . Set $\hat S_{0i} = 0$ . For $t = 1, \ldots, n$ :

compute $P_t$ by (11.7);
sample $A_t\sim P_t$ and observe $X_t$ ;
update $\hat S_{ti} = \hat S_{t-1,i} + 1 - \frac{\mathbb I\{A_t = i\}(1 - X_t)}{P_{ti}}$ for every arm.

NoteSampling in practice (Exercise 11.1)

With one uniform $U$ , return the smallest $i$ with $U\le\sum_{j\le i}P_{tj}$ . This is the inverse CDF on cumulative sums. Floating-point non-uniformity can matter in practice.

Regret analysis

TheoremTheorem 11.1 — Exp3’s regret

For any $x\in[0,1]^{n\times k}$ , Exp3 with $\eta = \sqrt{\log(k)/(nk)}$ has

$R_n\le2\sqrt{nk\log k}$

ProofA telescoping potential, two exponential inequalities, and a variance bound

Fix an arm $i$ and let $R_{ni} = \sum_tx_{ti} - \mathbb E\sum_tX_t$ . It is enough to bound $R_{ni}$ for every $i$ .

Step 1: Express the regret through estimates. Unbiasedness gives $\mathbb E[\hat S_{ni}] = \sum_tx_{ti}$ and $\mathbb E_{t-1}[X_t] = \sum_jP_{tj}x_{tj} = \sum_jP_{tj}\mathbb E_{t-1}[\hat X_{tj}]$ . By the tower rule,

$R_{ni} = \mathbb E\big[\hat S_{ni} - \hat S_n\big], \qquad \hat S_n = \sum_t\sum_jP_{tj}\hat X_{tj} \tag{11.9}$

Step 2: The potential. Let $W_t = \sum_j\exp(\eta\hat S_{tj})$ , with $W_0 = k$ . Then

$e^{\eta\hat S_{ni}}\le W_n = k\prod_{t=1}^n\frac{W_t}{W_{t-1}}, \qquad \frac{W_t}{W_{t-1}} = \sum_jP_{tj}e^{\eta\hat X_{tj}} \tag{11.10–11.11}$

Step 3: Bound each ratio. Since $\eta\hat X_{tj}\le1$ (the loss-based estimate is at most 1), use $e^x\le1 + x + x^2$ for $x\le1$ and then $1 + x\le e^x$ :

$\frac{W_t}{W_{t-1}}\le1 + \eta\sum_jP_{tj}\hat X_{tj} + \eta^2\sum_jP_{tj}\hat X_{tj}^2\le\exp\Big(\eta\sum_jP_{tj}\hat X_{tj} + \eta^2\sum_jP_{tj}\hat X_{tj}^2\Big)$

Step 4: Telescope and take logs.

$\hat S_{ni} - \hat S_n\le\frac{\log k}\eta + \eta\sum_{t=1}^n\sum_{j=1}^kP_{tj}\hat X_{tj}^2 \tag{11.13}$

Step 5: The variance term. With $\hat X_{tj} = 1 - \mathbb I\{A_t = j\}y_{tj}/P_{tj}$ ,

$\mathbb E\Big[\sum_jP_{tj}\hat X_{tj}^2\Big] = \mathbb E\Big[1 - 2Y_t + \sum_jy_{tj}^2\Big] = \mathbb E\Big[(1 - Y_t)^2 + \sum_{j\ne A_t}y_{tj}^2\Big]\le k$

Step 6: Tune. $R_{ni}\le\frac{\log k}\eta + \eta nk = 2\sqrt{nk\log k}$ at $\eta = \sqrt{\log k/(nk)}$ .

∎

IntuitionTwo error sources balanced by $\eta$

$\frac{\log k}\eta$ is the cost of starting uncommitted (uniform over $k$ arms). $\eta\sum P\hat X^2$ is the cost of reacting to noisy estimates, where importance weighting makes each round contribute variance of order $k$ . Optimizing $\eta$ balances them at $\sqrt{nk\log k}$ .

RemarkWhere the potential argument comes from

It starts from the trivial soft-max inequality $\hat S_{ni}\le\frac1\eta\log\sum_je^{\eta\hat S_{nj}} = \frac1\eta\log W_n$ and telescopes $W_n$ . This is the same potential that drives Kelly-style and universal portfolio mixtures: exponential weights are a wealth-weighted mixture over experts.

TheoremTheorem 11.2 — A $\sqrt2$ improvement

With $\eta = \sqrt{2\log(k)/(nk)}$ , Exp3 has $R_n\le\sqrt{2nk\log k}$ .

ProofUse the second-order Taylor bound on its valid side

The key inequality: $e^x\le1 + x + \frac{x^2}2$ holds for $x\le0$ , but not for $x\le1$ . Since $\hat X_{tj}\le1$ , write $e^{\eta\hat X_{tj}} = e^\eta e^{\eta(\hat X_{tj} - 1)}$ , whose exponent is $\le0$ :

$e^{\eta\hat X_{tj}}\le e^\eta\Big(1 + \eta(\hat X_{tj} - 1) + \frac{\eta^2}2(\hat X_{tj} - 1)^2\Big)$

Summing with weights $P_{tj}$ and using $1 + x\le e^x$ : $\frac{W_t}{W_{t-1}}\le\exp\big(\eta\sum_jP_{tj}\hat X_{tj} + \frac{\eta^2}2\sum_jP_{tj}(\hat X_{tj} - 1)^2\big)$ .

The variance term: with $\hat Y_{tj} = 1 - \hat X_{tj}\ge0$ , $P_{tj}\hat Y_{tj}^2 = \mathbb I\{A_t = j\}y_{tj}\hat Y_{tj}\le\hat Y_{tj}$ . So

$\hat S_{ni} - \hat S_n\le\frac{\log k}\eta + \frac\eta2\sum_{t,j}\hat Y_{tj} \tag{11.15}$

and $\mathbb E\sum_{t,j}\hat Y_{tj} = \sum_{t,j}y_{tj}\le nk$ . Tune $\eta$ .

∎

NoteComparing the exponential bounds on $[-\frac12,\frac12]$

$1 + x$ is a lower bound everywhere. $1 + x + x^2$ is an upper bound for $x\le1$ , but loose. $1 + x + \frac{x^2}2$ is a much tighter upper bound, but only valid for $x\le0$ . Shifting by $e^\eta$ moves the estimates into the region where the tight bound applies.

Notes on Exp3

WarningSmall expected regret, terrible regret distribution (Exercise 11.6)

Define the random regret $\hat R_n = \max_i\sum_tx_{ti} - \sum_tX_t$ . For any reasonable learning rate and large $n$ , there is a two-armed bandit with $\mathbb P(\hat R_n\ge n/4) > \frac1{131}$ . Construction, in losses:

$y_{t1} = \begin{cases}0 & t\le n/2\\ 1 & t > n/2\end{cases}, \qquad y_{t2} = \begin{cases}\alpha & t\le n/2\\ 0 & t > n/2\end{cases}, \qquad \alpha\in[\tfrac14,\tfrac12]$

In the first half, arm 2’s probability can be driven to about $\frac1{8n}$ . When arm 2 becomes the good arm, Exp3 can’t recover in time.

Why Markov’s inequality doesn’t contradict this: the bound $\mathbb P(\hat R_n\ge n/4)\le4\mathbb E[\hat R_n]/n = O(n^{-1/2})$ needs $\hat R_n\ge0$ . But the random regret is often negative: Exp3 frequently beats the best fixed arm on this sequence, since it switches arms when the losses switch. Large positive and large negative outcomes average to a small mean. The book’s box plots show exactly this spread.

RemarkVariants and extensions

Full information (prediction with expert advice): the whole $x_t$ is observed, so true rewards replace estimates. That is Hedge (exponential weights), with regret $\sqrt{n\log(k)/2}$ via Hoeffding’s lemma, asymptotically optimal. Bandit feedback costs a factor of about $\sqrt k$ .
Reactive adversaries: if $x_t$ may depend on the learner’s past actions, the same bound holds with the same proof. Whether regret against a fixed arm is a meaningful goal then is another question.
Policy regret is impossible: if $x_t = f_t(A_1,\ldots,A_t)$ , even against constant action sequences, take $f_t = \mathbb I\{a_1 = 1\}$ versus $\mathbb I\{a_1 = 2\}$ . The first action decides everything, and one of the two environments forces linear regret. Limited adversary memory restores sublinear regret.
Not a model of non-stationarity: “best fixed arm in hindsight” has stationarity built in. When the best arm changes, compete with sequences of actions instead (Chapter 31).
Removing $\sqrt{\log k}$ : a mirror-descent variant (the Tsallis-INF family, Chapter 28) gets $O(\sqrt{nk})$ . With learning rate $1/\sqrt t$ it also gets $O(\log n)$ regret on stochastic bandits (Zimmert–Seldin 2019), “best of both worlds”, with subtleties for non-oblivious adversaries.
Non-uniform prior $P_1$ : favouring an arm lowers regret if it is optimal, at an unavoidable price if not.
Anytime: use the doubling trick, or more elegantly a decreasing $\eta_t$ (Exercise 28.13).
Unbounded rewards: only much weaker results are possible (Allenberg et al. 2006).
History: Auer et al. (1995) introduced Exp3 with explicit uniform exploration mixed in; Stoltz (2005) observed it isn’t needed.

TheoremExp3 is follow-the-perturbed-leader with Gumbel noise (Exercises 11.7–11.8)

Gumbel trick: if $G_i = -\log(-\log U_i)$ with $U_i$ i.i.d. uniform, then $\mathbb P\big(\log a_i + G_i = \max_j(\log a_j + G_j)\big) = \frac{a_i}{\sum_ja_j}$ . So

$A_t = \arg\max_i\Big(Z_{ti} - \eta\sum_{s<t}\hat Y_{si}\Big),\qquad Z_{ti}\ \text{i.i.d. standard Gumbel}$

samples exactly from Exp3’s distribution. Exponential weights = argmax of perturbed scores, which gives a sampling-free implementation and a bridge to other perturbation-based algorithms.

ExampleExp3 on a stochastic bandit (Exercise 11.9)

Bernoulli arms with $\mu = (0.5, 0.55)$ and $n = 10^5$ . Exp3’s regret depends strongly on $\eta$ and is generally far worse than UCB or KL-UCB, which exploit the stochastic structure. Worst-case adversarial guarantees cost instance-dependent performance.

The Exp3-IX algorithm

The problem. Exp3’s expected regret is near-optimal, but its regret can be linear with constant probability. The culprit is the importance-weighted estimate’s variance of order $1/P_{ti}$ . The goal is a high-probability bound: with probability at least $1 - \delta$ , $\hat R_n = O\big(\sqrt{nk\log(k/\delta)}\big)$ .

Setup (losses throughout). $Y_t = y_{tA_t}$ is the observed loss, $\tilde L_n = \sum_tY_t$ the learner’s total loss, $L_{ni} = \sum_ty_{ti}$ arm $i$ ‘s total loss, and with any estimates $\hat Y_{tj}$ , $\hat L_n = \sum_{t,j}P_{tj}\hat Y_{tj}$ and $\hat L_{ni} = \sum_t\hat Y_{ti}$ . The random regret against arm $i$ is $\hat R_{ni} = \tilde L_n - L_{ni}$ .

FormulaThe deterministic part of Exp3’s analysis

For any estimates with $0\le\hat Y_{ti}\le1/P_{ti}$ , (11.15) in loss form is

$\hat L_n - \hat L_{ni}\le\frac{\log k}\eta + \frac\eta2\sum_{j=1}^k\hat L_{nj} \tag{12.1}$

$\hat R_{ni}\le\frac{\log k}\eta + \underbrace{(\tilde L_n - \hat L_n)}_{\text{bias}} + \underbrace{(\hat L_{ni} - L_{ni})}_{\text{estimation error}} + \frac\eta2\sum_j\hat L_{nj} \tag{12.3}$

A high-probability bound needs each of these to be controlled with high probability.

DefinitionImplicit-exploration (IX) estimator

For a small $\gamma > 0$ ,

$\hat Y_{ti} = \frac{\mathbb I\{A_t = i\}Y_t}{P_{ti} + \gamma} \tag{12.4}$

It still satisfies $0\le\hat Y_{ti}\le1/P_{ti}$ , so (12.3) applies.

IntuitionBias buys variance, and the bias points the helpful way

$\mathbb E_{t-1}[\hat Y_{ti}] = \frac{P_{ti}y_{ti}}{P_{ti} + \gamma} = y_{ti} - \frac{\gamma y_{ti}}{P_{ti} + \gamma}\le y_{ti}$ . Losses are underestimated, i.e. the estimator is optimistic, and the optimism is largest for rarely played arms (small $P_{ti}$ ). So poorly performing arms keep getting occasional plays. Exp3-IX explores more than Exp3 without ever mixing in a uniform distribution. Hence “implicit exploration”: the exploration comes from modified estimates, not from altering $P_t$ directly.

AlgorithmExp3-IX — Algorithm 10

Input $n, k, \eta, \gamma$ . Set $\hat L_{0i} = 0$ . For $t = 1, \ldots, n$ :

$P_{ti} = \dfrac{\exp(-\eta\hat L_{t-1,i})}{\sum_j\exp(-\eta\hat L_{t-1,j})}$ ;
sample $A_t\sim P_t$ and observe $X_t$ ;
$\hat L_{ti} = \hat L_{t-1,i} + \dfrac{\mathbb I\{A_t = i\}(1 - X_t)}{P_{ti} + \gamma}$ .

Regret analysis

TheoremTheorem 12.1 — High-probability regret of Exp3-IX

Let $\delta\in(0,1)$ , $\gamma = \eta/2$ , and

$\eta_1 = \sqrt{\frac{2\log(k+1)}{nk}}, \qquad \eta_2 = \sqrt{\frac{\log k + \log\frac{k+1}\delta}{nk}}$

With $\eta = \eta_1$ , which doesn’t depend on $\delta$ : $\mathbb P\Big(\hat R_n\ge\sqrt{8nk\log(k+1)} + \Big(\sqrt{\frac{nk}{2\log(k+1)}} + 1\Big)\log\frac{k+1}\delta\Big)\le\delta \tag{12.5}$
With $\eta = \eta_2$ , tuned to $\delta$ : $\mathbb P\Big(\hat R_n\ge2\sqrt{(2\log(k+1) + \log(1/\delta))nk} + \log\frac{k+1}\delta\Big)\le\delta \tag{12.6}$

ImportantOne algorithm for all $\delta$ , or a better bound for one $\delta$

$\eta_1$ gives a single algorithm that is good at every confidence level, with $\log(1/\delta)$ entering linearly times $\sqrt{nk}$ . $\eta_2$ gives the better $\sqrt{nk\log(1/\delta)}$ , but only for the $\delta$ chosen in advance. Chapter 17 shows this trade-off is unavoidable.

LemmaLemma 12.2 — Concentration for negatively correlated estimates

Let $(\tilde Y_{ti})_t$ be adapted for each $i\in[k]$ , with

$\mathbb E\big[\prod_{i\in S}\tilde Y_{ti}\mid\mathcal F_{t-1}\big]\le0$ for every $S\subseteq[k]$ with $|S| > 1$ (negative correlation), and
$\mathbb E[\tilde Y_{ti}\mid\mathcal F_{t-1}] = y_{ti}$ .

Let $\alpha_{ti}, \lambda_{ti}$ be predictable with $0\le\alpha_{ti}\tilde Y_{ti}\le2\lambda_{ti}$ . Then for all $\delta\in(0,1)$ ,

$\mathbb P\Big(\sum_{t=1}^n\sum_{i=1}^k\alpha_{ti}\Big(\frac{\tilde Y_{ti}}{1 + \lambda_{ti}} - y_{ti}\Big)\ge\log\frac1\delta\Big)\le\delta$

LemmaLemma 12.5 — A discounted exponential is linear-bounded

For $0\le x\le2\lambda$ : $\exp\big(\frac x{1+\lambda}\big)\le1 + x$ .

ProofMonotone in λ, then a log inequality

$\exp\big(\frac x{1+\lambda}\big)\le\exp\big(\frac x{1 + x/2}\big)\le1 + x$ . The first step holds because the expression decreases in $\lambda$ and $\lambda\ge x/2$ . The second is $\frac{2u}{1+u}\le\log(1+2u)$ for $u\ge0$ : equality at 0, and the left side’s derivative is smaller.

∎

ProofProof of Lemma 12.2: a supermartingale and Markov

Step 1: One round. By Lemma 12.5, $\exp\big(\frac{\alpha_{ti}\tilde Y_{ti}}{1+\lambda_{ti}}\big)\le1 + \alpha_{ti}\tilde Y_{ti}$ . Multiply over $i$ and expand the product:

$\mathbb E_{t-1}\Big[\exp\Big(\sum_i\frac{\alpha_{ti}\tilde Y_{ti}}{1+\lambda_{ti}}\Big)\Big]\le\mathbb E_{t-1}\Big[\prod_i(1 + \alpha_{ti}\tilde Y_{ti})\Big]\le1 + \sum_i\alpha_{ti}y_{ti}\le\exp\Big(\sum_i\alpha_{ti}y_{ti}\Big)$

The cross terms of the product have nonpositive conditional expectation by negative correlation, which saves a factor of $k$ . The last step is $1 + x\le e^x$ .

Step 2: A supermartingale. Let $Z_t = \exp\big(\sum_i\alpha_{ti}(\frac{\tilde Y_{ti}}{1+\lambda_{ti}} - y_{ti})\big)$ and $M_t = Z_1\cdots Z_t$ . Step 1 gives $\mathbb E_{t-1}[Z_t]\le1$ , so $\mathbb E[M_n]\le1$ .

Step 3: Markov. $\mathbb P(\log M_n\ge\log\frac1\delta) = \mathbb P(\delta M_n\ge1)\le\delta$ . This is the Cramér–Chernoff method in martingale form (cf. Exercise 5.15).

∎

LemmaLemma 12.3 — The loss estimates don’t overshoot by much

With probability at least $1 - \delta$ , simultaneously

$\max_i\big(\hat L_{ni} - L_{ni}\big)\le\frac{\log\frac{k+1}\delta}{2\gamma} \quad\text{and}\quad \sum_i\big(\hat L_{ni} - L_{ni}\big)\le\frac{\log\frac{k+1}\delta}{2\gamma} \tag{12.7}$

ProofFit the IX estimator into Lemma 12.2

Write

$\sum_i(\hat L_{ni} - L_{ni}) = \frac1{2\gamma}\sum_{t,i}2\gamma\Big(\frac1{1 + \gamma/P_{ti}}\cdot\frac{A_{ti}y_{ti}}{P_{ti}} - y_{ti}\Big)$

and take $\tilde Y_{ti} = A_{ti}y_{ti}/P_{ti}$ , $\lambda_{ti} = \gamma/P_{ti}$ , $\alpha_{ti} = 2\gamma$ . Only one arm is played per round, so $\prod_{i\in S}A_{ti} = 0$ for $|S| > 1$ (negatively correlated), and $\alpha\tilde Y\le2\gamma/P = 2\lambda$ . Lemma 12.2 gives the sum bound with probability $1 - \delta'$ . For a single arm, use $\alpha_{tj} = 2\gamma\,\mathbb I\{j = i\}$ . Then union bound the $k + 1$ events with $\delta' = \delta/(k+1)$ .

∎

LemmaLemma 12.4 — The bias is exactly γ times the total estimate

$\tilde L_n - \hat L_n = \gamma\sum_{j=1}^k\hat L_{nj}$

ProofOne line per round

$Y_t - \sum_jP_{tj}\hat Y_{tj} = \sum_j\big(1 - \frac{P_{tj}}{P_{tj}+\gamma}\big)A_{tj}y_{tj} = \gamma\sum_j\frac{A_{tj}y_{tj}}{P_{tj}+\gamma} = \gamma\sum_j\hat Y_{tj}$ . Sum over $t$ .

∎

ProofProof of Theorem 12.1

By (12.3) and Lemma 12.4,

$\hat R_n\le\frac{\log k}\eta + \max_i(\hat L_{ni} - L_{ni}) + \Big(\gamma + \frac\eta2\Big)\sum_j\hat L_{nj}$

On the event of Lemma 12.3, $\sum_j\hat L_{nj}\le\sum_jL_{nj} + \frac{\log((k+1)/\delta)}{2\gamma}\le nk + \frac{\log((k+1)/\delta)}{2\gamma}$ , so

$\hat R_n\le\frac{\log k}\eta + \Big(\gamma + \frac\eta2\Big)nk + \Big(\gamma + \frac\eta2 + 1\Big)\frac{\log\frac{k+1}\delta}{2\gamma}$

Substitute $\gamma = \eta/2$ and $\eta\in\{\eta_1,\eta_2\}$ .

∎

ImportantTwo lessons from the analysis

One-sided concentration is cheap because the estimator is biased downward. $\mathbb E[\hat L_{ni}] < L_{ni}$ by enough that the upward deviation $\hat L_{ni} - L_{ni}$ can be bounded with no dependence on $P_{ti}$ , at scale $\frac1\gamma$ (the largest possible summand). The price is $\log\frac1\delta$ rather than $\sqrt{\log\frac1\delta}$ .
Negative correlation replaces independence. For a fixed round, the indicators $(A_{ti})_i$ are negatively correlated, since exactly one is 1, so the sum over arms concentrates without a union bound over $k$ .

A Bernstein-type martingale inequality also works, losing only a factor of 2: $\hat L_{ni} - L_{ni} < \frac1\gamma\log\frac1\delta$ with probability $1 - \delta$ (Exercise 12.1). It is arguably more transparent.

Notes on Exp3-IX

RemarkExpected regret, anytime versions, and refined bounds

Expected regret: integrate the tail, $R_n\le\mathbb E[\hat R_n^+] = \int_0^\infty\mathbb P(\hat R_n^+\ge x)\,dx$ , which gives $R_n\le C\sqrt{kn\log k}$ (Exercise 12.7).
Anytime: $\eta_t = \sqrt{\log k/(kt)}$ , $\gamma_t = \eta_t/2$ give about the same regret (Kocák et al. 2014; Neu 2015).
First-order bounds: when the best arm has small total loss, $R_n = O\big(\sqrt{k\min_iL_{ni}\log k}\big)$ , which can be far below $\sqrt{nk}$ (Exercise 28.14).
Quadratic-variation bounds: with $Q_n = \sum_t\|x_t - \bar x\|^2$ , Hazan–Kale get $O(k^2\sqrt{Q_n})$ . Mirror descent removes the $k^2$ (Chapter 28).

AlgorithmExp3.P — explicit exploration plus biased estimates (Exercises 12.3–12.4)

Use $\hat Y_{ti} = \frac{A_{ti}y_{ti}}{P_{ti}} - \frac\beta{P_{ti}}$ (deliberately biased downward) and mix in uniform exploration:

$P_{ti} = (1-\gamma)\tilde P_{ti} + \frac\gamma k, \qquad \tilde P_{ti}\propto\exp(-\eta\hat L_{t-1,i})$

With $\gamma = k\eta$ and $\eta = \beta$ tuned, $\hat R_n\le C\sqrt{nk\log(k/\delta)}$ with probability $1 - \delta$ (Auer et al. 2002). This approach generalizes to settings where loss estimates can be negative, which arises in more complex feedback models. The generic analysis needs only $\eta|\hat Z|\le1$ , $\eta\beta\le1$ , $\eta\mathbb E_{t-1}[\hat Z^2]\le\beta$ and unbiasedness of $\hat Z$ .

ExampleExperiments (Exercises 12.5–12.6)

Stochastic Bernoulli arms ( $k = 5$ , $n = 10^4$ , one arm $\frac12$ , the rest $\frac12 - \Delta$ ): compare Exp3 and Exp3-IX expected regret across $\Delta$ .
Rerunning the instability example: Exp3-IX’s regret distribution no longer has the catastrophic positive tail. In the book’s figure, its regret on that switching sequence sits well below zero across the $\alpha$ range. Implicit exploration keeps the eventually-good arm alive.

RemarkHistory

Exp3-IX and the IX estimator are due to Kocák et al. (2014), originally for large action sets with side information. Its high-probability property is from Neu (2015). Earlier variance-reduction ideas truncated the weights, which makes estimators non-smooth. High-probability adversarial bounds go back to Auer et al. (2002b) and Abernethy–Rakhlin (2009).

Quick reference

Object	Statement	Note
Adversarial regret	$\max_i\sum_tx_{ti} - \mathbb E\sum_tx_{tA_t}$	best fixed arm in hindsight
Deterministic policies	$R_n^*\ge n(1 - 1/k)$	randomization is required
Tracking regret	$\ge n(1-1/k)$ for every policy	the benchmark is too strong
Reduction	stochastic regret $\le$ adversarial worst case	Jensen on the max
Minimax lower bound	$R_n^*\ge c\sqrt{nk}$	from Bernoulli bandits
IW estimator	$\hat X_{ti} = \mathbb I\{A_t = i\}X_t/P_{ti}$	unbiased; variance $\approx1/P_{ti}$
Loss-based IW	$\hat X_{ti} = 1 - \mathbb I\{A_t = i\}(1-X_t)/P_{ti}$	bounded above by 1
Exp3	$P_{ti}\propto\exp(\eta\hat S_{t-1,i})$	softmax of estimated cumulative reward
Exp3 regret	$2\sqrt{nk\log k}$ , or $\sqrt{2nk\log k}$ with $\eta = \sqrt{2\log k/(nk)}$	potential $W_t$ telescopes
Key inequalities	$1 + x\le e^x$ ; $e^x\le1 + x + x^2$ ( $x\le1$ ); $e^x\le1 + x + \frac{x^2}2$ ( $x\le0$ )
Exp3 instability	$\mathbb P(\hat R_n\ge n/4) > 1/131$ on some instance	random regret can be negative
Hedge (full information)	$\sqrt{n\log(k)/2}$	bandit feedback costs about $\sqrt k$
Gumbel trick	$\arg\max_i(\log a_i + G_i)\sim a/\sum a$	Exp3 = perturbed leader
IX estimator	$\mathbb I\{A_t = i\}Y_t/(P_{ti}+\gamma)$	optimistic bias, lower variance
IX bias	$\tilde L_n - \hat L_n = \gamma\sum_j\hat L_{nj}$	exact identity
Overshoot bound	$\max_i(\hat L_{ni} - L_{ni})\le\log\frac{k+1}\delta/(2\gamma)$	negative-correlation lemma
Exp3-IX	$\hat R_n = O\big(\sqrt{nk\log(k/\delta)}\big)$ w.p. $1-\delta$	$\eta_1$ : all $\delta$ ; $\eta_2$ : one $\delta$

Facts to keep to hand

Against an adversary, randomize. Any deterministic policy can be simulated and defeated. The fair-coin trick in the one-round game becomes exponential weights over $n$ rounds.
Adversarial is barely harder than stochastic in the worst case. Both minimax regrets are $\Theta(\sqrt{nk})$ up to logs. Adversarial algorithms give up the $O(\log n)$ instance-dependent behaviour that stochastic algorithms enjoy, unless best-of-both-worlds methods are used.
Importance weighting is the only unbiased option, and it costs variance about $1/P$ . Exp3 controls the variance in expectation via $\sum_jP_{tj}\hat X_{tj}^2\le k$ , but not in the tails.
Exp3’s analysis is a potential argument. Telescope $W_t = \sum_je^{\eta\hat S_{tj}}$ , bound each ratio with a quadratic upper bound on $e^x$ (which needs a one-sided bounded estimator), and tune $\eta$ to balance $\frac{\log k}\eta$ against $\eta\times$ variance.
Trade a little bias for a lot of concentration. Adding $\gamma$ to the denominator (IX) makes losses optimistic, keeps every arm explored, and makes the estimates concentrate one-sidedly at scale $1/\gamma$ . Negative correlation of the play indicators avoids paying for a union bound over arms.

References

Lattimore & Szepesvári, Bandit Algorithms — Part III introduction; Chapters 11–12

Related

The Exp3 and Exp3-IX Algorithms

Motivation: all models are wrong

Adversarial bandit environments

Relation to stochastic bandits

Importance-weighted estimators

The Exp3 algorithm

Regret analysis

Notes on Exp3

The Exp3-IX algorithm

Regret analysis

Notes on Exp3-IX

Quick reference

References

Mentioned in