Adversarial Linear Bandits · Vaibhav on HTTPS

Corresponds to Lattimore & Szepesvári, Chapters 27–29.

Motivation: an adversary chooses the parameter

DefinitionAdversarial linear bandit

The learner has an action set $\mathcal A\subset\mathbb R^d$ and horizon $n$ . An adversary fixes loss vectors $y_1, \ldots, y_n\in\mathbb R^d$ . In round $t$ the learner plays a (possibly random) $A_t\in\mathcal A$ and observes only the scalar loss $Y_t = \langle A_t,y_t\rangle$ , never $y_t$ itself.

$R_n = \mathbb E\Big[\sum_{t=1}^nY_t\Big] - \min_{a\in\mathcal A}\sum_{t=1}^n\langle a,y_t\rangle$

With $\mathcal A = \{e_1, \ldots, e_d\}$ this is the $k$ -armed adversarial bandit.

ConventionStanding assumptions (Chapter 27)

Bounded losses: $y_t\in\mathcal L = \{x : \sup_{a\in\mathcal A}\lvert\langle a,x\rangle\rvert\le1\}$ , the polar of the action set. The adversary’s power is defined by the geometry of $\mathcal A$ .
$\mathcal A$ spans $\mathbb R^d$ . This is only for convenience (Exercises 27.7, 27.10).

IntuitionWhat carries over and what doesn’t

The algorithms combine exponential weights with optimal design, and later with convex analysis. But stochastic intuitions mislead here: the unit-ball rates differ by a factor of $\sqrt d$ between the two models, and Chapter 29 explains why. The setting is also computationally demanding, since the number of actions is often exponential or infinite.

Algorithm	Action set	Regret	Computation
Exp3 + Kiefer–Wolfowitz exploration	finite, $\lvert\mathcal A\rvert = k$	$2\sqrt{3dn\log k}$	$O(kd + d^3)$ per round
Exp3 on an $\frac1n$ -cover	any bounded set	$O(d\sqrt{n\log(nd)})$	exponential in $d$
Continuous exponential weights	convex, positive volume	$2d\sqrt{3n(1 + \log^+(2n/d))}$	polynomial, but impractical
FTRL, barrier potential	unit ball	$2\sqrt{3nd\log n}$	cheap
FTRL/INF (Tsallis)	simplex ( $k$ arms)	$\sqrt{8kn}$	cheap

Exp3 for linear bandits (Chapter 27)

DefinitionLeast-squares importance-weighted estimator

Let $P_t$ be the sampling distribution, $Q_t = \sum_aP_t(a)aa^\top$ and $\mathbb E_t[\cdot] = \mathbb E[\cdot\mid P_t]$ . Estimate the whole loss vector:

$\hat Y_t = Q_t^{-1}A_tY_t, \qquad\hat Y_t(a) = \langle a,\hat Y_t\rangle$

Then $\mathbb E_t[\hat Y_t] = Q_t^{-1}\mathbb E_t[A_tA_t^\top]y_t = Q_t^{-1}Q_ty_t = y_t$ : it is unbiased, provided $Q_t$ is invertible.

IntuitionOne scalar observation informs every action

With $\mathcal A = \{e_i\}$ , $Q_t = \mathrm{diag}(P_t)$ , and $\hat Y_t$ is the usual importance-weighted estimator. In general, the observed loss is “back-projected” through the second-moment matrix of the sampling distribution, so it updates the estimate of every action that shares a direction with $A_t$ . This is the adversarial counterpart of least squares.

AlgorithmExp3 for linear bandits (Algorithm 15)

Input: finite $\mathcal A$ , learning rate $\eta$ , exploration distribution $\pi$ with $Q(\pi) = \sum_a\pi(a)aa^\top\succ0$ , and mixing weight $\gamma$ . For $t = 1, \ldots, n$ :

$P_t(a) = \gamma\pi(a) + (1-\gamma)\dfrac{\exp(-\eta\sum_{s<t}\hat Y_s(a))}{\sum_{a'}\exp(-\eta\sum_{s<t}\hat Y_s(a'))}$ ;
sample $A_t\sim P_t$ and observe $Y_t = \langle A_t,y_t\rangle$ ;
set $\hat Y_t = Q_t^{-1}A_tY_t$ and $\hat Y_t(a) = \langle a,\hat Y_t\rangle$ .

TheoremTheorem 27.1 — Regret of linear Exp3

For any exploration distribution $\pi$ , with $g(\pi) = \max_a\lVert a\rVert^2_{Q(\pi)^{-1}}$ , $k = \lvert\mathcal A\rvert$ , and suitably tuned $\eta, \gamma$ ,

$R_n\le2\sqrt{(2g(\pi) + d)\,n\log k} \tag{27.1}$

By Kiefer–Wolfowitz (Exercise 21.6 handles non-spanning sets), some $\pi$ has $g(\pi)\le d$ , so $R_n\le2\sqrt{3dn\log k}$ . The general form (27.1) is useful when the optimal design is expensive: trade computation for a larger $g$ .

ProofExp3’s potential argument, a variance of exactly

d

, and boundedness from exploration

Step 1: The Exp3 template. If $\eta\hat Y_t(a)\ge-1$ for all $a$ (27.2), the proof of Theorem 11.1, with the mixture costing at most $2\gamma n$ (Exercise 27.1), gives

$R_n\le\frac{\log k}\eta + 2\gamma n + \eta\sum_t\mathbb E\Big[\sum_aP_t(a)\hat Y_t(a)^2\Big] \tag{27.3}$

The sharper $\eta/2$ form isn’t used. It would need estimates bounded by 1 in a way that costs too much elsewhere.

Step 2: The variance is at most $d$ . $\sum_aP_t(a)\hat Y_t(a)^2 = Y_t^2A_t^\top Q_t^{-1}\big(\sum_aP_t(a)aa^\top\big)Q_t^{-1}A_t = Y_t^2A_t^\top Q_t^{-1}A_t\le\mathrm{tr}(A_tA_t^\top Q_t^{-1})$ . In conditional expectation this is $\mathrm{tr}(Q_tQ_t^{-1}) = d$ , the same trace identity as in (21.5).

Step 3: Exploration bounds the estimates. $Q_t\succeq\gamma Q(\pi)$ , so $Q_t^{-1}\preceq Q(\pi)^{-1}/\gamma$ (Exercise 27.4: inversion reverses the Loewner order). Then $\lvert Y_t\rvert\le1$ and Cauchy–Schwarz give

$\lvert\eta\hat Y_t(a)\rvert\le\eta\lvert a^\top Q_t^{-1}A_t\rvert\le\eta\lVert a\rVert_{Q_t^{-1}}\lVert A_t\rVert_{Q_t^{-1}}\le\frac\eta\gamma g(\pi) \tag{27.4}$

Step 4: Tune. $\gamma = \eta g(\pi)$ makes $\lvert\eta\hat Y_t(a)\rvert\le1$ . Then $R_n\le\frac{\log k}\eta + \eta n(2g(\pi) + d)$ , and the best $\eta$ gives (27.1).

∎

WarningExploration can’t be dropped here

In the $k$ -armed case, Exp3 needs no extra exploration (Chapter 11). For general linear action sets, without $\gamma\pi$ the matrix $Q_t$ can become nearly singular in directions the weights neglect. Then the estimates $Q_t^{-1}A_tY_t$ explode and regret is very poor even with an optimal $\eta$ (Exercise 27.8). Only a bound on (27.4) is needed, not the exactly optimal design: Kiefer–Wolfowitz makes it $d$ .

RemarkVariants

Loss ranges: if $\sup_a\lvert\langle a,y\rangle\rvert\le b$ , rescale and the regret scales by $b$ . If $\langle a,y\rangle\in[a_-,b_+]$ , shift as well (Exercises 27.2–27.3).
Changing action sets with identities (Note 4, Exercise 27.5): with $\mathcal A_t = \{a_1(t), \ldots, a_k(t)\}$ and a fresh exploration design each round, $\max_i\mathbb E\sum_t\langle A_t - a_i(t),y_t\rangle\le2\sqrt{3dn\log k}$ . This compares against the best fixed index $i$ , a weaker benchmark than the per-round optimum in stochastic linear bandits (see Contextual linear bandits).
Computation: $O(kd + d^3)$ per round plus a one-off design, hopeless for combinatorial sets such as the hypercube’s corners ( $k = 2^d$ ). This motivates FTRL and mirror descent, and Chapter 30.
Optimality: the $\sqrt n$ dependence is unimprovable. The linear dependence on $d$ is optimal for some action sets and not others: the unit ball does better.
History: Bubeck et al. (2012) used John’s ellipsoid for exploration, which is right only when it is centred. Kiefer–Wolfowitz is the centred version.

Continuous exponential weights

Warning $\log k$ is objectionable for huge or infinite action sets

One fix is to run Exp3 on a finite $C\subseteq\mathcal A$ with $\sup_a\min_{b\in C}\sup_{y\in\mathcal L}\lvert\langle a - b,y\rangle\rvert\le1/n$ . Such a $C$ exists with $\log\lvert C\rvert\le d\log(6dn)$ (Exercise 27.6), giving $O(d\sqrt{n\log(nd)})$ . But $\lvert C\rvert$ is exponential in $d$ .

AlgorithmContinuous exponential weights

For convex $\mathcal A$ with positive volume and an exploration measure $\pi$ on $\mathcal A$ , sample $A_t\sim P_t = (1-\gamma)\tilde P_t + \gamma\pi$ , where

$\tilde P_t(B) = \frac{\int_B\exp\big(-\eta\sum_{s<t}\hat Y_s(a)\big)da}{\int_{\mathcal A}\exp\big(-\eta\sum_{s<t}\hat Y_s(a)\big)da} \tag{27.5}$

The density is $\propto\exp(-\text{linear})$ on a convex set: log-concave. The idea goes back to Cover’s universal portfolios (a wealth-weighted average over a continuum of strategies). It was applied to linear bandits by Hazan et al. (2016).

TheoremTheorem 27.2 — Sampling log-concave densities (Bubeck et al. 2015)

If $p(a)\propto\mathbb I_{\mathcal A}(a)e^{-f(a)}$ with $f$ convex, there is a polynomial-time sampler given efficient access to (1) gradients $\nabla f(a)$ and (2) Euclidean projections onto $\mathcal A$ . (27.5) supplies the gradients. Projections are efficient given a separation oracle, which either confirms $x\in\mathcal A$ or returns a $u$ with $\langle y,u\rangle > \langle x,u\rangle$ for all $y\in\mathcal A$ . The authors warn that these samplers are not practical, especially with theoretically justified parameters (Lovász–Vempala survey).

TheoremTheorem 27.3 — Regret of continuous exponential weights

For compact convex $\mathcal A$ with $\mathrm{vol}(\mathcal A) > 0$ , and Kiefer–Wolfowitz exploration,

$R_n\le2d\sqrt{3n\big(1 + \log^+(2n/d)\big)}$

LemmaProposition 27.4 — Log-Laplace transform of a convex body

For compact convex $K$ with positive volume, $u\in\mathbb R^d$ and $x^* = \arg\min_{x\in K}\langle x,u\rangle$ ,

$\log\frac{\mathrm{vol}(K)}{\int_K\exp(-\langle x - x^*,u\rangle)\,dx}\le d\Big(1 + \log^+\frac{\sup_{x,y\in K}\langle x - y,u\rangle}d\Big)$

This plays the role of $\log k$ : the continuum “prior” puts enough mass near the best action (Exercise 27.11).

ProofProof of Theorem 27.3

Choosing $\gamma = d\eta$ keeps $\eta\lvert\langle a,\hat Y_t\rangle\rvert\le1$ as before. The exponential-weights argument with integrals in place of sums (Exercise 27.9) gives

$R_n\le\frac1\eta\mathbb E\Big[\log\frac{\mathrm{vol}(\mathcal A)}{\int_{\mathcal A}\exp\big(-\eta\sum_t(\hat Y_t(a) - \hat Y_t(a^*))\big)da}\Big] + 3\eta dn \tag{27.6}$

With $u = \eta\sum_t\hat Y_t$ , each round changes $\langle x - y,u\rangle$ by at most 2, so $\sup\langle x - y,u\rangle\le2n$ . Proposition 27.4 bounds the log term by $d(1 + \log^+(2n/d))$ . Then optimize $\eta$ .

∎

Online linear optimisation, mirror descent and FTRL (Chapter 28)

DefinitionOnline linear optimisation (full information)

$\mathcal A\subseteq\mathbb R^d$ is convex and $\mathcal L$ is the loss space. In round $t$ the learner picks $a_t\in\mathcal A$ , then observes the entire $y_t\in\mathcal L$ . The regret against a comparator $a$ is $R_n(a) = \sum_t\langle a_t - a,y_t\rangle$ , and $R_n = \max_aR_n(a)$ . Actions are deterministic.

AlgorithmMirror descent (MD) and follow-the-regularised-leader (FTRL)

Both use a learning rate $\eta > 0$ and a convex (usually Legendre) potential/regulariser $F$ , and start at $a_1 = \arg\min_{a\in\mathcal A}F(a)$ .

$\text{MD:}\quad a_{t+1} = \arg\min_{a\in\mathcal A}\big(\eta\langle a,y_t\rangle + D_F(a,a_t)\big) \tag{28.2}$ $\text{FTRL:}\quad a_{t+1} = \arg\min_{a\in\mathcal A}\Big(\eta\sum_{s\le t}\langle a,y_s\rangle + F(a)\Big) \tag{28.3}$

MD makes a small step that trades the new loss against moving far (in $D_F$ ) from the current point.
FTRL plays the best action in hindsight for the regularised cumulative loss.

Well-definedness isn’t automatic (Exercise 28.2). It holds when $\mathcal A$ is compact and $F$ is Legendre.

WarningFollow-the-leader is unstable

Without regularisation, $a_{t+1} = \arg\min_a\sum_{s\le t}\langle a,y_s\rangle$ . On $\mathcal A = [-1,1]$ with $y_1 = \frac12$ and then alternating $y_s = \pm1$ , the leader flips between the endpoints every round and is always wrong: linear regret (Exercise 28.4). FTL fails because the environment is adversarial and the action set has sharp corners. If either is missing it can be fine (Huang et al. 2017). With bandit feedback it also fails for lack of exploration (Exercises 4.12–4.13). Regularisation is stabilisation.

TheoremWhen MD and FTRL coincide

If $F$ is Legendre with domain $D\subseteq\mathcal A$ , the minimisers are interior and the first-order conditions give $\nabla F(a_{t+1}) = \nabla F(a_t) - \eta y_t$ for MD and $\nabla F(a_{t+1}) = -\eta\sum_{s\le t}y_s$ for FTRL. With $\nabla F(a_1) = 0$ these agree, and $\nabla F$ is invertible, so the two algorithms are identical.

The equivalence fails when $F$ ‘s domain exceeds $\mathcal A$ (so projections act), or when learning rates or potentials vary over time. With $\eta_t$ , MD has $\nabla F(a_{t+1}) = -\sum_s\eta_sy_s$ while FTRL has $-\eta_t\sum_sy_s$ .

ExampleFamiliar special cases

Setting	MD	FTRL
$\mathcal A = \mathbb R^d$ , $F = \frac12\lVert a\rVert^2$	online gradient descent $a_{t+1} = a_t - \eta y_t$	same
compact $\mathcal A$ , $F = \frac12\lVert a\rVert^2$	projected OGD $a_{t+1} = \Pi(a_t - \eta y_t)$	lazy projection $a_{t+1} = \Pi(-\eta\sum_{s\le t}y_s)$
simplex, $F$ = unnormalised negentropy	exponential weights	same: $a_{t+1,i} = \dfrac{e^{-\eta\sum_sy_{si}}}{\sum_je^{-\eta\sum_sy_{sj}}}$ (28.5)

Exponential weights, Hedge and Exp3 are all mirror descent with negentropy.

AlgorithmTwo-step implementation: mirror map, then projection

If $F$ is Legendre and $\nabla F(a) - \eta y\in\mathrm{int}(\mathrm{dom}F^*)$ (28.6):

$\tilde a_{t+1} = (\nabla F)^{-1}\big(\nabla F(a_t) - \eta y_t\big)\quad\text{(28.7, 28.9)}, \qquad a_{t+1} = \arg\min_{a\in\mathcal A}D_F(a,\tilde a_{t+1})\quad\text{(28.8)}$

Map to the dual with $\nabla F$ (the mirror map), take a gradient step, map back with $\nabla F^{-1} = \nabla F^*$ , then Bregman-project onto $\mathcal A$ . The first step is usually closed-form; the projection may be expensive. FTRL is $a_{t+1} = \Pi_{\mathcal A,F}\big(\nabla F^{-1}(-\eta\sum_{s\le t}y_s)\big)$ : FTRL accumulates losses in the dual space; MD re-anchors at each projected iterate. They agree until the first projection, then diverge.

Regret analysis

TheoremTheorem 28.4 — Mirror descent regret

Let $F$ be Legendre with domain $D$ , $\mathcal A$ nonempty convex with $\mathrm{int}(D)\cap\mathcal A\ne\emptyset$ , and the iterates well defined. For every $a\in\mathcal A$ ,

$R_n(a)\le\frac{F(a) - F(a_1)}\eta + \sum_{t=1}^n\langle a_t - a_{t+1},y_t\rangle - \frac1\eta\sum_{t=1}^nD(a_{t+1},a_t)$

and, if (28.6) holds,

$R_n(a)\le\frac1\eta\Big(F(a) - F(a_1) + \sum_{t=1}^nD(a_t,\tilde a_{t+1})\Big)$

For a general start, replace $F(a) - F(a_1)$ by $D(a,a_1)$ (28.11). This is useful for non-stationary bandits (Chapter 31).

ProofFirst-order optimality, a three-point identity, telescoping

Step 1: Split. $\langle a_t - a,y_t\rangle = \langle a_t - a_{t+1},y_t\rangle + \langle a_{t+1} - a,y_t\rangle$ .

Step 2: Optimality of $a_{t+1}$ (Proposition 26.14): $\langle a - a_{t+1},\eta y_t + \nabla F(a_{t+1}) - \nabla F(a_t)\rangle\ge0$ . The three-point identity for Bregman divergences turns this into

$\langle a_{t+1} - a,y_t\rangle\le\frac1\eta\big(D(a,a_t) - D(a,a_{t+1}) - D(a_{t+1},a_t)\big)$

Step 3: Telescope. Sum over $t$ , drop $-D(a,a_{n+1})\le0$ , and use $D(a,a_1)\le F(a) - F(a_1)$ (optimality of $a_1$ ). This gives the first bound.

Step 4: Second bound. With $\eta y_t = \nabla F(a_t) - \nabla F(\tilde a_{t+1})$ , the three-point identity gives $\langle a_t - a_{t+1},y_t\rangle = \frac1\eta\big(D(a_{t+1},a_t) + D(a_t,\tilde a_{t+1}) - D(a_{t+1},\tilde a_{t+1})\big)$ . Drop the last term and substitute.

∎

TheoremTheorem 28.5 — FTRL regret

For convex $F$ (Legendre isn’t needed) and well-defined iterates, FTRL satisfies the first bound of Theorem 28.4 (Exercise 28.5).

IntuitionBias plus stability

$\frac{F(a) - F(a_1)}\eta$ is the price of starting uncommitted: regularisation biases the iterates toward the regulariser’s minimiser. $\sum\langle a_t - a_{t+1},y_t\rangle - \frac1\eta\sum D(a_{t+1},a_t)$ is the price of instability: how much the iterates jump, net of what the regulariser charges for moving. Larger $\eta$ means less bias and more instability.

CorollaryCorollary 28.8 — Local-norm form

If $D_F(a_{t+1},a_t)\ge\frac12\lVert a_{t+1} - a_t\rVert_t^2$ for norms $\lVert\cdot\rVert_t$ , then, with $\mathrm{diam}_F(\mathcal A) = \max_{a,b}F(a) - F(b)$ ,

$R_n\le\frac{\mathrm{diam}_F(\mathcal A)}\eta + \frac\eta2\sum_{t=1}^n\lVert y_t\rVert^2_{t*}$

by “optimise to bound”: $\max_x(ax - bx^2/2) = a^2/2b$ . Theorem 26.13 often supplies the norm (the Hessian at an intermediate point, key inequality). Exercise 28.6.

ExampleMatching the regulariser to the geometry

Unit ball (Proposition 28.6): $F = \frac12\lVert a\rVert^2$ , $\lVert y_t\rVert_2\le1$ , $\eta = 1/\sqrt n$ . Here $\tilde a_{t+1} = a_t - \eta y_t$ and $D(a_t,\tilde a_{t+1}) = \frac{\eta^2}2\lVert y_t\rVert^2$ , with $\mathrm{diam} = \frac12$ , so $R_n\le\frac1{2\eta} + \frac{\eta n}2 = \sqrt n$ .
Simplex (Proposition 28.7): negentropy, $y_t\in[0,1]^d$ , $\eta = \sqrt{2\log(d)/n}$ . Here $\mathrm{diam} = \log d$ , and Pinsker gives $D(a_{t+1},a_t)\ge\frac12\lVert a_{t+1} - a_t\rVert_1^2$ , so the dual norm is $\lVert y\rVert_\infty\le1$ and $R_n\le\sqrt{2n\log d}$ .
Wrong regulariser (Example 28.9): $F = \frac12\lVert a\rVert^2$ on the simplex uses $\lVert y\rVert_2^2\le d$ and gives $O(\sqrt{nd})$ instead of $O(\sqrt{n\log d})$ . The potential should match the geometry of the action set and the loss space.

RemarkNon-oblivious losses

Theorems 28.4–28.5 never used obliviousness. They hold when $y_t$ depends on $a_1,y_1,\ldots,a_t$ , which is essential, since bandit loss estimates depend on past actions. (But see the warning on bandit regret below.)

From full information to bandits

AlgorithmOnline stochastic mirror descent / FTRL (Algorithm 16)

Keep a “mean action” $\bar A_t$ , starting at $\bar A_1 = \arg\min_{a\in\mathcal A\cap\mathrm{dom}F}F(a)$ . In each round:

choose a distribution $P_t$ on $\mathcal A$ with mean $\bar A_t$ and sample $A_t\sim P_t$ (randomised rounding, also necessary when $\mathcal A$ isn’t convex);
observe $\langle A_t,y_t\rangle$ and build an unbiased estimate $\hat Y_t$ with $\mathbb E[\hat Y_t\mid\bar A_t] = y_t$ ;
update $\bar A_{t+1}$ by MD or FTRL using $\hat Y_t$ .

TheoremTheorem 28.10 — Bandit regret of MD/FTRL

With Legendre $F$ , convex $\mathcal A$ and unbiased estimates,

$R_n(a)\le\mathbb E\Big[\frac{F(a) - F(\bar A_1)}\eta + \sum_t\langle\bar A_t - \bar A_{t+1},\hat Y_t\rangle - \frac1\eta\sum_tD(\bar A_{t+1},\bar A_t)\Big]$

and for MD (with the analogue of (28.6) a.s.) $R_n\le\frac{\mathrm{diam}_F(\mathcal A)}\eta + \frac1\eta\sum_t\mathbb E[D(\bar A_t,\tilde A_{t+1})]$ . Proof: linearity gives $\mathbb E\langle A_t,y_t\rangle = \mathbb E\langle\bar A_t,y_t\rangle = \mathbb E\langle\bar A_t,\hat Y_t\rangle$ , so the bandit regret is the expected full-information regret on the estimated losses, and the bounds hold for adaptively chosen losses.

IntuitionThe recipe

Choose (1) a potential matched to the geometry, (2) a sampling scheme with mean $\bar A_t$ and enough spread, (3) an unbiased estimator. The regret becomes $\frac{\mathrm{diam}_F}\eta + \frac\eta2\sum\mathbb E\lVert\hat Y_t\rVert^2_{(\nabla^2F)^{-1}}$ : the estimator’s variance measured in the regulariser’s local geometry. A good potential makes the curvature large exactly where the estimates are large.

Linear bandits on the unit ball

AlgorithmFTRL on the ball (Algorithm 17)

With $\mathcal A = B_2^d$ , losses $\lVert y_t\rVert_2\le1$ and $\hat L_{t-1} = \sum_{s<t}\hat Y_s$ :

Potential: $F(a) = -\log(1 - \lVert a\rVert) - \lVert a\rVert$ (a barrier at the sphere), on the shrunken ball $\tilde{\mathcal A} = \{\lVert x\rVert\le r\}$ .
Mean action: $\bar A_t = \Pi\Big(\dfrac{-\eta\hat L_{t-1}}{1 + \eta\lVert\hat L_{t-1}\rVert}\Big)$ (Euclidean projection onto $\tilde{\mathcal A}$ ; Exercise 28.7).
Sampling: with probability $1 - \lVert\bar A_t\rVert$ explore ( $E_t = 1$ ): play $U_t$ uniform on $\{\pm e_1, \ldots, \pm e_d\}$ . Otherwise play the unit vector $\bar A_t/\lVert\bar A_t\rVert$ . The mean is $\bar A_t$ .
Estimator: $\hat Y_t = \dfrac{dE_tA_t\langle A_t,y_t\rangle}{1 - \lVert\bar A_t\rVert}$ , unbiased because $\mathbb E[U_tU_t^\top] = I/d$ .

TheoremTheorem 28.11 — Regret on the unit ball

With $r = 1 - 2\eta d$ and $\eta = \sqrt{\log(n)/(3dn)}$ ,

$R_n\le2\sqrt{3nd\log n}$

This is a factor $\sqrt d$ better than continuous exponential weights, and below the stochastic lower bound $\Omega(d\sqrt n)$ (Theorem 24.2). There is no contradiction: see Stochastic linear bandits with parameter noise.

ProofShrink, apply the local-norm bound, use the barrier’s curvature

Step 1: Shrinking costs $(1-r)n$ . $R_n\le R_n(ra^*) + \sum_t\langle ra^* - a^*,y_t\rangle\le R_n(ra^*) + (1-r)n$ .

Step 2: Local-norm bound. By Theorems 26.13 and 28.10, for some $Z_t$ on $[\bar A_t,\bar A_{t+1}]$ , $R_n(ra^*)\le\frac{\mathrm{diam}_F(\tilde{\mathcal A})}\eta + \frac\eta2\mathbb E\sum_t\lVert\hat Y_t\rVert^2_{(\nabla^2F(Z_t))^{-1}}$ (28.14).

Step 3: Stability. $\eta\lVert\hat Y_t\rVert\le\frac{\eta d}{1-r} = \frac12$ , and from the closed form for $\bar A_t$ , $\frac{1 - \lVert Z_t\rVert}{1 - \lVert\bar A_t\rVert}\le\max\big\{1,\frac{1 + \eta\lVert\hat L_{t-1}\rVert}{1/2 + \eta\lVert\hat L_{t-1}\rVert}\big\}\le2$ : the iterate can’t jump much closer to the boundary in one step.

Step 4: Curvature beats variance. $\nabla^2F(a) = \frac I{1 - \lVert a\rVert} + \frac{aa^\top}{\lVert a\rVert(1 - \lVert a\rVert)^2}\succeq\frac I{1 - \lVert a\rVert}$ , so $(\nabla^2F)^{-1}\preceq(1 - \lVert a\rVert)I$ . Then

$\mathbb E_t\lVert\hat Y_t\rVert^2_{(\nabla^2F(Z_t))^{-1}}\le d^2\,\mathbb E_t\Big[(1 - \lVert Z_t\rVert)\frac{E_t\langle U_t,y_t\rangle^2}{(1 - \lVert\bar A_t\rVert)^2}\Big] = d\frac{1 - \lVert Z_t\rVert}{1 - \lVert\bar A_t\rVert}\lVert y_t\rVert^2\le2d$

using $\mathbb E\langle U,y\rangle^2 = \lVert y\rVert^2/d$ and $\mathbb P(E_t = 1) = 1 - \lVert\bar A_t\rVert$ .

Step 5: Total. With $\mathrm{diam}_F(\tilde{\mathcal A})\le\log\frac1{1-r}$ : $R_n\le(1-r)n + \frac1\eta\log\frac1{1-r} + \eta nd = 3\eta nd + \frac1\eta\log\frac1{2\eta d}\le2\sqrt{3nd\log n}$ .

∎

ImportantWhy the barrier potential works

Exploration happens with probability $1 - \lVert\bar A_t\rVert$ , so the estimator’s magnitude is about $d/(1 - \lVert\bar A_t\rVert)$ , which blows up near the sphere. The barrier’s Hessian blows up at the same rate, so the local norm $\lVert\hat Y\rVert^2_{(\nabla^2F)^{-1}}$ stays about $d$ . That is the “magician’s hat” choice of potential. The price of bandit information on the ball is about $\sqrt{d\log n}$ (compare Proposition 28.6).

Notes and exercises on FTRL/MD

TheoremExp3 is mirror descent (Exercises 28.9–28.10)

On the simplex with negentropy and $\hat Y_{ti} = \mathbb I\{A_t = i\}y_{ti}/P_{ti}$ , mirror descent is Exp3, and so is FTRL, since the KL projection is renormalisation. Even the bound matches: with $\tilde P_{t+1} = \arg\min_{p\ge0}\eta\langle p,\hat Y_t\rangle + D_F(p,P_t)$ ,

$D_F(P_t,\tilde P_{t+1}) = \sum_iP_{ti}\big(e^{-\eta\hat Y_{ti}} - 1 + \eta\hat Y_{ti}\big)\le\frac{\eta^2}2\sum_iP_{ti}\hat Y_{ti}^2$

(using $e^{-x}\le1 - x + x^2/2$ for $x\ge0$ , valid since $\hat Y\ge0$ ), whose expectation is at most $\eta^2k/2$ . With $\mathrm{diam}_F = \log k$ , this gives $R_n\le\sqrt{2nk\log k}$ , recovering Theorem 11.2.

TheoremTime-varying learning rates (Exercises 28.11–28.13)

MD with $\eta_t$ : $R_n(a)\le\sum_t\frac{D_F(a_t,\tilde a_{t+1})}{\eta_t} + \sum_tD_F(a,a_t)\big(\frac1{\eta_t} - \frac1{\eta_{t-1}}\big)$ . The second sum needs $D_F(a,a_t)$ bounded, which fails for negentropy near the boundary.
FTRL with $F_t = F/\eta_t$ , $\eta_t$ decreasing: $R_n(a)\le\frac{F(a) - \min F}{\eta_n} + \sum_t\big(\langle a_t - a_{t+1},y_t\rangle - \frac{D_F(a_{t+1},a_t)}{\eta_t}\big)$ . This is the natural anytime tool, and here FTRL is preferable to MD.
Anytime Exp3: $R_n\le\frac{\log k}{\eta_n} + \frac k2\sum_t\eta_t$ . With $\eta_t = \sqrt{\log k/(kt)}$ both terms are at most $\sqrt{nk\log k}$ , so $R_n\le2\sqrt{nk\log k}$ for every $n$ . (Tuning worked here.) This is the anytime Exp3 needed for one-Exp3-per-context.

TheoremRemoving $\sqrt{\log k}$ : INF / Tsallis potential (Exercise 28.15)

FTRL on the simplex with $F(a) = -2\sum_i\sqrt{a_i}$ and IW estimates:

$P_{ti} = \big(\lambda + \eta\hat L_{t-1,i}\big)^{-2}$ , with $\lambda$ the normaliser (the implicitly normalised forecaster, Audibert–Bubeck 2009);
$\nabla^2F(x) = \frac12\mathrm{diag}(x^{-3/2})$ and $\mathrm{diam}_F\le2\sqrt k$ ;
$R_n\le\sqrt{8kn}$ , matching the $\Omega(\sqrt{kn})$ lower bound up to constants;
with $\eta_t = 1/\sqrt t$ , $R_n = O(\sqrt{kn})$ adversarially and $O(\sum_i\log n/\Delta_i)$ stochastically: best of both worlds (Zimmert–Seldin 2019; very hard).

See Example 26.10 for this potential’s dual.

TheoremFirst-order bounds via the log barrier (Exercise 28.14)

FTRL with $F(a) = -\sum_i\log a_i$ and an adaptive learning rate gives $R_n\le k + 2\sqrt{k\big(1 + \mathbb E\sum_ty_{tA_t}^2\big)\log\frac{n\vee k}k}$ , hence $R_n = O\big(\sqrt{k(1 + \min_a\sum_ty_{ta})\log\frac nk}\big)$ . When the best arm has small total loss, regret is much smaller than $\sqrt{nk}$ (Wei–Luo 2018).

WarningBandit regret with non-oblivious losses

The full-information bounds hold for adaptive losses, but bandit regret $\mathbb E[\max_a\hat R_n(a)]$ is not $\max_a\mathbb E[\hat R_n(a)]$ when losses react, since $\min_a\sum\langle a,y_t\rangle$ is then random. Bounding the gap needs empirical-process tools and gives $O(\sqrt n)$ only if $\mathbb V[\hat R_n(a)] = O(n)$ , which can fail badly (Exp3’s instability). And non-oblivious regret doesn’t capture reactivity anyway.

RemarkMore notes

$\ell_p$ balls: the $\ell_2$ ball gets $\tilde O(\sqrt{dn})$ , while the hypercube ( $\ell_\infty$ ) needs $\Theta(d\sqrt n)$ . As $n\to\infty$ , the optimal dimension dependence on $B_p^d$ is either $d$ or $\sqrt d$ , fully classified by Bubeck et al. (2018).
Price of bandit information: about $\sqrt d$ on the ball and the simplex (up to logs), but it can be as large as $\Theta(d)$ . Dimension dependence in general is not well understood.
Choosing potentials: there is no characterisation. In full information, any achievable regret is nearly achieved by MD with some potential (Srebro et al. 2011), which doesn’t help construct potentials. “Universal” potentials exist but it is unclear what matters, especially for bandits.
Naming: “mirror descent” is often used in bandit papers for what is really FTRL. Keep both in mind; one is sometimes easier to analyse.
Online convex optimisation: with convex losses $f_t$ , linearise with $y_t = \nabla f_t(a_t)$ , so that $R_n(a)\le\sum\langle a_t - a,y_t\rangle$ . Quadratic MD is then gradient descent (Zinkevich 2003; Shalev-Shwartz; Hazan).
History: MD is from Nemirovsky–Yudin (1983); FTRL is regularised risk minimisation (Gordon 1999; Shalev-Shwartz 2007); FTPL is from Hannan (1957) and Kalai–Vempala (2002); MD was first used for bandits by Abernethy et al. (2008).

TheoremMinimax theorems from no-regret learning (Notes 13–14, Exercise 28.16)

Always $\inf_x\sup_yf\ge\sup_y\inf_xf$ . Sion: equality holds if $X, Y$ are convex subsets of linear topological spaces (one compact), $f(\cdot,y)$ is lower semicontinuous and quasi-convex, and $f(x,\cdot)$ is upper semicontinuous and quasi-concave. With simplices and bilinear $f$ this is von Neumann’s minimax theorem.

Proof idea: let both players run no-regret algorithms against each other on $f(x_t,y_t)$ . Sublinear regret for both implies the averaged iterates $\bar x_n, \bar y_n$ certify $\inf_x\sup_y f\le\sup_y\inf_x f + o(1)$ . Compactness can’t be dropped (Exercise 28.17). Minimax theorems bridge adversarial and Bayesian regret (Chapters 34, 36).

Definitions: quasi-convex means sublevel sets $f^{-1}((-\infty,a))$ are convex. Upper semicontinuous at $x$ means for every $\varepsilon$ some neighbourhood has $f\le f(x) + \varepsilon$ ; lower semicontinuous is the mirror condition.

Adversarial versus stochastic linear bandits (Chapter 29)

DefinitionUnified view (losses throughout)

$Y_t = \langle A_t,\theta\rangle + \eta_t\ \ (\text{stochastic}), \qquad Y_t = \langle A_t,\theta_t\rangle\ \ (\text{adversarial})$

with $\eta_t$ (conditionally) 1-subgaussian. The regrets are $\sum_t\mathbb E\langle A_t,\theta\rangle - n\inf_a\langle a,\theta\rangle$ and $\sum_t\mathbb E\langle A_t,\theta_t\rangle - n\inf_a\langle a,\bar\theta_n\rangle$ , with $\bar\theta_n$ the average loss vector.

WarningThree subtleties absent in the finite-armed case

Reducing stochastic to adversarial needs an augmented action set.
The models restrict the variance of the noise differently, which explains the unit-ball gap: adversarial $\tilde O(\sqrt{dn})$ versus stochastic $\Omega(d\sqrt n)$ .
With changing action sets, the right adversarial regret has no effective algorithms yet.

Reducing stochastic linear bandits to adversarial ones

AlgorithmAugmentation reduction

Assume $\lvert\langle a,\theta\rangle + \eta_t\rvert\le1$ a.s. Absorb the noise into an extra coordinate:

$\mathcal A_{\mathrm{aug}} = \{(a,1) : a\in\mathcal A\}\subset\mathbb R^{d+1}, \qquad\theta_t = (\theta,\eta_t)$

so that $\langle(a,1),\theta_t\rangle = \langle a,\theta\rangle + \eta_t$ matches the stochastic feedback exactly. Run any adversarial algorithm on $\mathcal A_{\mathrm{aug}}$ and play the first $d$ coordinates.

Regret transfers: for $a' = (a,1)$ , $\langle A_t,\theta\rangle - \langle a,\theta\rangle = \langle A_t',\theta_t\rangle - \langle a',\theta_t\rangle$ , so the stochastic regret is at most the adversarial regret bound $B_n$ .

ImportantThe reduction changes the geometry

If $\mathcal A$ is the unit ball, neither $\mathcal A_{\mathrm{aug}}$ nor its loss polar is a ball. The $\Omega(d\sqrt n)$ stochastic lower bound shows this change must empower the adversary: on the augmented set, adversarial regret is $\Omega(d\sqrt n)$ . Relatedly, $O(\sqrt{dn})$ is impossible on a shifted ball $\{(2,0,\ldots,0) + x : \lVert x\rVert\le1\}$ (Shamir 2015). So the recommendation is: for stochastic environments, run an adversarial algorithm on the augmented set. If unsure, running on the original set usually works but may need different tuning (Exercises 29.2–29.3).

RemarkUnbounded noise (Note 1)

For Gaussian noise, work on the event that $\lvert\langle A_t,\theta\rangle + \eta_t\rvert\le C = 1 + \sqrt{4\log n}$ for all $t$ , which fails with probability at most $1/n$ by a subgaussian tail and a union bound.

Stochastic linear bandits with parameter noise

DefinitionParameter noise

$\theta_t\sim\nu$ i.i.d. with mean $\theta$ , and $Y_t = \langle A_t,\theta_t\rangle$ : the noise enters before the inner product. If $\mathrm{Supp}(\nu)\subseteq\mathcal L$ it is directly an adversarial instance, with no augmentation (Exercise 29.1). Combined with Chapter 24’s techniques, this is the standard way to prove adversarial lower bounds.

FormulaThe noise variance depends on the action

Writing $Y_t = \langle A_t,\theta\rangle + \tilde\eta_t$ with $\tilde\eta_t = \langle A_t,\theta_t - \theta\rangle$ (conditionally mean zero),

$\mathbb V_t[\tilde\eta_t] = A_t^\top\Sigma A_t \tag{29.3}$

with $\Sigma$ the covariance of $\nu$ . For example $\Sigma = I$ gives $\lVert A_t\rVert^2$ : short actions are quiet. In the standard stochastic model, short actions carry full-size noise, which an adversary can exploit.

ImportantWhy the unit-ball rates differ

If $\nu$ lives on the unit sphere, $\mathrm{tr}\,\Sigma\le1$ . For $A_t$ uniform on the sphere, $\mathbb E[A^\top\Sigma A] = \mathrm{tr}(\Sigma)/d\le1/d$ : the effective noise variance is about $1/d$ , versus 1 under 1-subgaussian noise. Scaling the adversary’s vectors to the sphere of radius $\sqrt d$ restores variance about 1, and the regret becomes linear in $d$ , matching the stochastic case. The standard adversarial model generalises parameter-noise bandits, not additive-noise ones. Restricting the adversary to $\mathcal L$ limits its control over the learner’s signal-to-noise ratio.

RemarkAdversarial algorithms on stochastic problems (Notes 2–4)

MD/FTRL analyses apply to stochastic linear bandits: $R_n = \mathbb E\sum\langle\bar A_t - a^*,\hat\theta_t\rangle$ for unbiased $\hat\theta_t$ . The estimator’s covariance differs from the adversarial case, so the bounds change.
Ball, additive noise: the Section 28.4 algorithm gets $O(d\sqrt{n\log n})$ . The variance computation grows by about $d$ (Exercise 29.2). For finite $\mathcal A$ , linear Exp3 with Kiefer–Wolfowitz gets $O(\sqrt{dn\log k})$ ; for convex $\mathcal A$ , use continuous exponential weights.
Misspecification on the ball: $Y_t = \langle A_t,\theta\rangle + \varepsilon(A_t) + \eta_t$ can’t be written as $\langle A_t,\theta_t\rangle$ with $\theta_t$ independent of $A_t$ . Even so, tuned FTRL gets $O(d\sqrt{n\log n} + \varepsilon n\sqrt d)$ (Exercise 29.4), improving on Chapter 22 by log factors and matching the misspecification lower bounds. For finite $\mathcal A$ , the Exp3 analysis breaks: the bias isn’t controlled by the exploration design.

Contextual linear bandits

WarningThe right adversarial benchmark is open

With changing action sets $\mathcal A_t$ , LinUCB controls $\mathbb E\sum_t\langle A_t - a_t^*,\theta\rangle = \tilde O(d\sqrt n)$ against the per-round optimum. The adversarial analogue is

$R_n(\Theta) = \max_{\theta\in\Theta}\mathbb E\Big[\sum_t\langle A_t - a_t(\theta),y_t\rangle\Big],\qquad a_t(\theta) = \arg\max_{a\in\mathcal A_t}\langle a,\theta\rangle \tag{29.4}$

which competes with the best policy induced by a parameter. For finite $\Theta$ , Chapter 27’s methods give $O(\sqrt{dn\log\lvert\Theta\rvert})$ , but this is (a) inefficient for large $\Theta$ , and (b) covering a continuous $\Theta$ doesn’t transfer, because $a_t(\theta)$ is discontinuous in $\theta$ . A meaningful bound for $\Theta = \{\lVert\theta\rVert_2\le1\}$ is a “fascinating challenge”. Exercise 27.5’s bound (actions with identities, best fixed index) is a different and weaker objective, like Exp4’s best-expert benchmark.

Quick reference

Object	Statement	Note
Loss space	$\mathcal L = \{x : \sup_a\lvert\langle a,x\rangle\rvert\le1\}$	polar of $\mathcal A$
LS-IW estimator	$\hat Y_t = Q_t^{-1}A_tY_t$ , $Q_t = \sum P_t(a)aa^\top$	unbiased
Variance	$\mathbb E\sum_aP_t(a)\hat Y_t(a)^2\le d$	trace identity
Linear Exp3	$2\sqrt{(2g(\pi) + d)n\log k}\le2\sqrt{3dn\log k}$	exploration $\gamma = \eta g(\pi)$ required
Cover	$\log\lvert C\rvert\le d\log(6dn)$	$O(d\sqrt{n\log(nd)})$ , inefficient
Continuous EW	$2d\sqrt{3n(1 + \log^+(2n/d))}$	log-concave sampling
MD	$a_{t+1} = \arg\min\eta\langle a,y_t\rangle + D_F(a,a_t)$	mirror step + Bregman projection
FTRL	$a_{t+1} = \arg\min\eta\sum_{s\le t}\langle a,y_s\rangle + F(a)$	dual accumulation
Equivalence	same if $F$ Legendre, $\mathrm{dom}F\subseteq\mathcal A$ , fixed $\eta$	differ with projections or $\eta_t$
Regret	$\frac{F(a) - F(a_1)}\eta + \sum\langle a_t - a_{t+1},y_t\rangle - \frac1\eta\sum D(a_{t+1},a_t)$	bias + stability
Local norms	$\frac{\mathrm{diam}_F}\eta + \frac\eta2\sum\lVert y_t\rVert^2_{t*}$	Hessian norms
Ball (full info)	$\sqrt n$	quadratic potential
Simplex (full info)	$\sqrt{2n\log d}$	negentropy
Bandit MD/FTRL	sample with mean $\bar A_t$ + unbiased $\hat Y_t$	linearity
Ball (bandit)	$2\sqrt{3nd\log n}$	barrier $-\log(1 - \lVert a\rVert) - \lVert a\rVert$
Anytime Exp3	$\frac{\log k}{\eta_n} + \frac k2\sum\eta_t\le2\sqrt{nk\log k}$	FTRL with $F/\eta_t$
INF/Tsallis	$\sqrt{8kn}$ ; best of both worlds with $\eta_t = 1/\sqrt t$	$F = -2\sum\sqrt a$
Log barrier	first-order $\sqrt{k L^*\log(n/k)}$
Augmentation	$(a,1)$ , $\theta_t = (\theta,\eta_t)$	stochastic ⇒ adversarial, geometry changes
Parameter noise	$\mathbb V[\tilde\eta_t] = A_t^\top\Sigma A_t$	about $1/d$ on the sphere
Contextual adversarial	(29.4)	open for continuous $\Theta$

Facts to keep to hand

Linear Exp3 = exponential weights + least-squares importance weighting + optimal-design exploration. The variance is always $d$ by the trace identity. Exploration is needed to keep the estimates bounded, and Kiefer–Wolfowitz makes its cost $g(\pi) = d$ .
MD and FTRL are one framework. Regularise to stabilise, run in the dual via the mirror map, project back. Regret = (regulariser range)/ $\eta$ + $\eta$ × (loss size in the local dual norm). Choosing the potential to match the geometry is everything: quadratic for the ball, negentropy for the simplex, Tsallis to remove $\sqrt{\log k}$ , barriers for bandit variance.
Bandits via MD/FTRL need only a sampling distribution with the right mean and an unbiased estimator. Good potentials put curvature exactly where the estimator is large (the barrier on the ball), which gives $\sqrt{dn\log n}$ .
Adversarial ≠ harder version of stochastic, geometrically. Stochastic reduces to adversarial only on an augmented set. The adversarial model really generalises parameter noise, where noise shrinks with the action and is about $1/d$ on the sphere. That is why the ball gets $\sqrt{dn}$ adversarially but $d\sqrt n$ stochastically.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 27–29
Shalev-Shwartz, Online Learning and Online Convex Optimization (2012); Hazan, Introduction to Online Convex Optimization (2016)
Bubeck & Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012)