Stochastic Linear Bandits

Corresponds to Lattimore & Szepesvári, Chapters 19, 22 and 23. The statistical machinery (confidence ellipsoids from the method of mixtures, and optimal experimental design) is in confidence-bounds-and-optimal-design-for-least-squares.

Motivation: learning transfers across actions

IntuitionThe central idea

With $k$ unrelated arms, every arm must be learned separately, which costs $\sqrt{nk}$ . If every action is described by a feature vector $a\in\mathbb R^d$ and the mean reward is $\langle\theta^*,a\rangle$ , then every pull teaches something about every action, because each pull is a noisy measurement of $\theta^*$ . The difficulty of the problem becomes the dimension $d$ , not the number of actions, which can be enormous or infinite.

Chapter	Setting	Algorithm	Regret
19	Arbitrary bounded action sets, possibly changing	LinUCB / OFUL	$O(d\sqrt n\log n)$
22	Fixed finite action set, $\lvert\mathcal A\rvert = k$	Phased elimination + G-optimal design	$O(\sqrt{dn\log(nk)})$
23	Sparse $\theta^$ , $\lVert\theta^\rVert_0\le m_0$	SETC (hypercube); OLR-UCB (general)	$O(m_0\sqrt{n\log n})$ ; $O(\sqrt{dnm_0}\log n)$

Stochastic contextual bandits

DefinitionStochastic contextual bandit

In round $t$ the learner observes a context $C_t\in\mathcal C$ , chooses $A_t\in[k]$ , and receives

$X_t = r(C_t,A_t) + \eta_t$

where $r : \mathcal C\times[k]\to\mathbb R$ is the reward function and the noise is conditionally 1-subgaussian: $\mathbb E[e^{\lambda\eta_t}\mid\mathcal F_t]\le e^{\lambda^2/2}$ a.s., with $\mathcal F_t = \sigma(C_1,A_1,X_1,\ldots,C_t,A_t)$ the information just before $X_t$ is seen. Hence $\mathbb E[X_t\mid\mathcal F_t] = r(C_t,A_t)$ .

RemarkConditioning on more is harmless

If the noise is subgaussian given a larger σ-algebra $\mathcal G\supseteq\mathcal F_t$ , the tower rule gives subgaussianity given $\mathcal F_t$ . So the condition can be checked with respect to anything that contains the learner’s information.

DefinitionContextual regret

$R_n = \mathbb E\Big[\sum_{t=1}^n\max_{a\in[k]}r(C_t,a) - \sum_{t=1}^nX_t\Big]$

The benchmark action $A_t^* = \arg\max_ar(C_t,a)$ is random, through $C_t$ .

WarningMeaningful only if actions don’t steer future contexts

No restriction is placed on how contexts arise. If a “suboptimal” action now could lead to better contexts later, this regret undervalues it. The definition makes sense when the learner’s actions don’t (greatly) affect subsequent contexts.

WarningUnstructured contexts are hopeless

Estimating $r(c,a)$ separately for every pair costs $\Omega(\sqrt{nMk})$ in the worst case with $M$ contexts, since knowing $r(c,\cdot)$ need not reveal anything about $r(c',\cdot)$ . With $M$ like $2^{100}$ , that is useless. Real contexts are structured: $r$ varies smoothly with its arguments. Compare the expert-advice view.

DefinitionFeature map and linear reward

Given a known feature map $\psi : \mathcal C\times[k]\to\mathbb R^d$ and unknown $\theta^*\in\mathbb R^d$ ,

$r(c,a) = \langle\theta^*,\psi(c,a)\rangle \tag{19.1}$

The span of $\{\psi(c,a)\}$ is the feature space.

Component	Detail
Signature	$\psi : \mathcal C\times[k]\to\mathbb R^d$
Examples	indicators of (visitor category, book category) combinations; the last hidden layer of a neural network trained on historical data
Smoothness	Hölder: $\lvert r(c,a) - r(c',a')\rvert\le\lVert\theta^\rVert\,\lVert\psi(c,a) - \psi(c',a')\rVert_$ (dual norm)
Infinite $d$	Norm bounds on $\theta^*$ play the role of finite dimension, which makes linearity far less restrictive (kernels)

The stochastic linear bandit

DefinitionStochastic linear bandit

In round $t$ the learner receives a decision set $\mathcal A_t\subset\mathbb R^d$ , chooses $A_t\in\mathcal A_t$ , and observes

$X_t = \langle\theta^*,A_t\rangle + \eta_t$

with $\eta_t$ conditionally 1-subgaussian given the history, $\mathcal A_t$ and $A_t$ . Only the feature vector matters, not the identity of the action.

$\hat R_n = \sum_{t=1}^n\max_{a\in\mathcal A_t}\langle\theta^*, a - A_t\rangle\ \ (\text{pseudo-regret}), \qquad R_n = \mathbb E[\hat R_n]$

Choice of $\mathcal A_t$	Recovers
$\{e_1, \ldots, e_d\}$	The finite-armed bandit with $k = d$
$\{\psi(C_t,i) : i\in[k]\}$	The contextual linear bandit
$\subseteq\{0,1\}^d$ (incidence vectors)	Combinatorial bandits: matchings, shortest paths, spanning trees (Chapter 30)

LinUCB: optimism over a confidence set

DefinitionOptimistic index

Given a confidence set $\mathcal C_t\subseteq\mathbb R^d$ that probably contains $\theta^*$ ,

$\mathrm{UCB}_t(a) = \max_{\theta\in\mathcal C_t}\langle\theta,a\rangle, \qquad A_t = \arg\max_{a\in\mathcal A_t}\mathrm{UCB}_t(a) \tag{19.2–19.3}$

Known as LinRel, LinUCB or OFUL (“optimism in the face of uncertainty for linear bandits”). The book calls every such algorithm LinUCB.

IntuitionSame principle, harder confidence set

Exactly the optimism principle: act as if the world is as good as plausibly possible. But a reward now informs every action, so the confidence object is a set in $\mathbb R^d$ , not an interval per arm. It should (a) contain $\theta^*$ with high probability and (b) be as small as possible.

DefinitionRegularised least squares

With penalty factor $\lambda\ge0$ ,

$\hat\theta_t = \arg\min_\theta\Big(\sum_{s=1}^t(X_s - \langle\theta,A_s\rangle)^2 + \lambda\lVert\theta\rVert_2^2\Big) = V_t^{-1}\sum_{s=1}^tA_sX_s, \qquad V_t = \lambda I + \sum_{s=1}^tA_sA_s^\top \tag{19.4–19.6}$

$\lambda > 0$ guarantees a unique minimizer even if the actions don’t span $\mathbb R^d$ .

DerivationSetting the gradient to zero (Exercise 19.1)

The objective is a strictly convex quadratic (for $\lambda > 0$ ). Its gradient is $-2\sum_sA_s(X_s - A_s^\top\theta) + 2\lambda\theta$ ; setting it to zero gives $(\lambda I + \sum_sA_sA_s^\top)\theta = \sum_sA_sX_s$ . See linear-transformations-and-matrices for the matrix facts.

DefinitionEllipsoidal confidence set

$\mathcal C_t$ is closed and satisfies

$\mathcal C_t\subseteq\mathcal E_t = \big\{\theta\in\mathbb R^d : \lVert\theta - \hat\theta_{t-1}\rVert^2_{V_{t-1}}\le\beta_t\big\} \tag{19.7}$

with $(\beta_t)$ increasing and $\beta_1\ge1$ . Here $\lVert x\rVert_V^2 = x^\top Vx$ . The ellipsoid is centred at the estimate; its principal axes are $V$ ‘s eigenvectors, with lengths proportional to $\lambda_i^{-1/2}$ . As $V_t$ grows, the ellipsoid shrinks.

IntuitionWhy an ellipsoid

With Gaussian noise, a deterministic spanning design and $\lambda = 0$ , the vector $Z = V^{1/2}(\hat\theta - \theta^*)$ is standard normal in $\mathbb R^d$ , so $\lVert\hat\theta - \theta^*\rVert_V^2 = \lVert Z\rVert^2\sim\chi^2_d$ . The radius is a $\chi^2_d$ quantile. Directions probed often (large eigenvalues of $V$ ) are pinned down tightly. The adaptive-design version is Theorem 20.5 in the confidence-bounds note.

Regret analysis

DefinitionAssumption 19.1

$1\le\beta_1\le\cdots\le\beta_n$ ;
mean gaps bounded: $\sup_{a,b\in\mathcal A_t}\langle\theta^*, a - b\rangle\le1$ ;
actions bounded: $\lVert a\rVert_2\le L$ ;
with probability $1-\delta$ , $\theta^*\in\mathcal C_t$ for all $t$ , with $\mathcal C_t$ satisfying (19.7).

TheoremTheorem 19.2 — Regret of LinUCB

Under Assumption 19.1, with probability $1-\delta$ ,

$\hat R_n\le\sqrt{8n\beta_n\log\frac{\det V_n}{\det V_0}}\le\sqrt{8dn\beta_n\log\frac{d\lambda + nL^2}{d\lambda}}$

With $\lVert\theta^*\rVert_2\le m_2$ , the method of mixtures (Theorem 20.5) allows

$\sqrt{\beta_n} = \sqrt\lambda\,m_2 + \sqrt{2\log\frac1\delta + d\log\frac{d\lambda + nL^2}{d\lambda}} \tag{19.8}$

CorollaryCorollary 19.3 — Expected regret

With $\delta = 1/n$ : $R_n\le Cd\sqrt n\log(nL)$ .

LemmaLemma 19.4 — Elliptical potential lemma

Let $V_0\succ0$ , $\lVert a_t\rVert_2\le L$ and $V_t = V_0 + \sum_{s\le t}a_sa_s^\top$ . Then

$\sum_{t=1}^n\Big(1\wedge\lVert a_t\rVert^2_{V_{t-1}^{-1}}\Big)\le2\log\frac{\det V_n}{\det V_0}\le2d\log\frac{\operatorname{trace}V_0 + nL^2}{d\det(V_0)^{1/d}}$

ProofDeterminants grow by

1 + \lVert a\rVert^2_{V^{-1}}

per step

Step 1: $u\wedge1\le2\log(1+u)$ for $u\ge0$ .

Step 2: Matrix determinant lemma. $V_t = V_{t-1}^{1/2}\big(I + V_{t-1}^{-1/2}a_ta_t^\top V_{t-1}^{-1/2}\big)V_{t-1}^{1/2}$ , and $I + yy^\top$ has eigenvalues $1 + \lVert y\rVert^2$ and 1 (repeated), so

$\det V_t = \det V_{t-1}\big(1 + \lVert a_t\rVert^2_{V_{t-1}^{-1}}\big), \qquad \det V_n = \det V_0\prod_{t=1}^n\big(1 + \lVert a_t\rVert^2_{V_{t-1}^{-1}}\big) \tag{19.9}$

Step 3: AM–GM on the eigenvalues. $\det V_n = \prod_i\lambda_i\le\big(\frac1d\operatorname{trace}V_n\big)^d\le\big(\frac{\operatorname{trace}V_0 + nL^2}d\big)^d$ .

∎

IntuitionYou can’t keep being surprised

$\lVert a_t\rVert^2_{V_{t-1}^{-1}}$ measures how new direction $a_t$ is relative to what has been explored. Each novel action inflates the volume $\det V$ , but the volume can only grow polynomially in $n$ , so the total novelty is $O(d\log n)$ . At most $O(d\log(1 + L^2/\lambda))$ rounds can have novelty at least 1 (Exercise 19.3).

ProofProof of Theorem 19.2: optimism, Cauchy–Schwarz, potential

Work on the event $\theta^*\in\mathcal C_t$ for all $t$ . Let $A_t^*$ be optimal, $r_t = \langle\theta^*, A_t^* - A_t\rangle$ , and $\tilde\theta_t\in\mathcal C_t$ attain $\mathrm{UCB}_t(A_t)$ .

Step 1: Optimism. $\langle\theta^*,A_t^*\rangle\le\mathrm{UCB}_t(A_t^*)\le\mathrm{UCB}_t(A_t) = \langle\tilde\theta_t,A_t\rangle$ .

Step 2: Cauchy–Schwarz in the $V$ -geometry. Both $\tilde\theta_t$ and $\theta^*$ lie in $\mathcal E_t$ , so

$r_t\le\langle\tilde\theta_t - \theta^*,A_t\rangle\le\lVert A_t\rVert_{V_{t-1}^{-1}}\lVert\tilde\theta_t - \theta^*\rVert_{V_{t-1}}\le2\sqrt{\beta_t}\lVert A_t\rVert_{V_{t-1}^{-1}} \tag{19.10}$

Step 3: Truncate. Also $r_t\le2$ (gaps at most 1, so differences at most 2), hence $r_t\le2\sqrt{\beta_n}\big(1\wedge\lVert A_t\rVert_{V_{t-1}^{-1}}\big)$ .

Step 4: Cauchy–Schwarz over time, then Lemma 19.4.

$\hat R_n\le\sqrt{n\sum_tr_t^2}\le2\sqrt{n\beta_n\sum_t\big(1\wedge\lVert A_t\rVert^2_{V_{t-1}^{-1}}\big)} \tag{19.11}$

∎

RemarkLarger reward ranges (Exercise 19.3)

If gaps are only bounded by $B$ , the at most $O(d\log(1 + L^2/\lambda))$ rounds with $\lVert A_t\rVert_{V^{-1}}\ge1$ cost at most $B$ each, and the rest of the analysis is unchanged. $B$ enters only as an additive constant independent of $n$ .

Computation

FormulaThe ellipsoidal index (Exercise 19.2)

For $\mathcal C_t = \mathcal E_t$ ,

$\max_{\theta\in\mathcal E_t}\langle\theta,a\rangle = \langle\hat\theta_{t-1},a\rangle + \sqrt{\beta_t}\,\lVert a\rVert_{V_{t-1}^{-1}}, \qquad A_t = \arg\max_{a\in\mathcal A_t}\Big(\langle\hat\theta_{t-1},a\rangle + \sqrt{\beta_t}\lVert a\rVert_{V_{t-1}^{-1}}\Big) \tag{19.13}$

Write $\theta = \hat\theta + V^{-1/2}u$ with $\lVert u\rVert\le\sqrt\beta$ . Then $\langle V^{-1/2}u,a\rangle = \langle u,V^{-1/2}a\rangle$ is maximized by $u$ aligned with $V^{-1/2}a$ , giving $\sqrt\beta\lVert a\rVert_{V^{-1}}$ .

ImportantLinUCB is UCB, generalised

Estimated reward + exploration bonus. With $\lambda = 0$ and $\mathcal A_t = \{e_1, \ldots, e_d\}$ , $V_t$ is diagonal with pull counts on the diagonal, $\hat\theta_i$ is arm $i$ ‘s empirical mean, and the bonus is $\sqrt{\beta_t/T_i(t-1)}$ . Choosing $\beta_t = 2\log(\cdot)$ recovers UCB exactly. The generic analysis gives $O(\sqrt{dn\log(\cdot)})$ here, close to the specialized analyses of Chapters 7–9. That dimension-free $\beta_t$ doesn’t satisfy (19.7), but the proof doesn’t actually need it.

RemarkComputing the action in general

$A_t$ solves a bilinear problem $\max_{(a,\theta)\in\mathcal A_t\times\mathcal C_t}\langle\theta,a\rangle$ (19.12), which is hard in general. Two tractable cases:

$\mathcal C_t$ is the convex hull of finitely many points $\phi_1, \ldots, \phi_m$ and linear optimisation over $\mathcal A_t$ is easy: compute $a(\phi_j)$ for each $j$ and keep the best pair.
$\mathcal C_t = \mathcal E_t$ and $\mathcal A_t$ is small: evaluate (19.13) for each arm. Rank-one Sherman–Morrison updates of $V_t^{-1}$ give $O(kd^2)$ work per round (Exercise 19.8).

Rarely switching LinUCB (Exercise 19.4): for a fixed set of $k$ actions, recompute the action only when $\log\det V_t$ has grown by $\log(1+\varepsilon)$ since the phase began. Using $\sup_x\lVert x\rVert_A^2/\lVert x\rVert_B^2\le\det A/\det B$ for $0\prec B\preceq A$ , the regret bound holds with $\beta_n$ replaced by $(1+\varepsilon)\beta_n$ , while the cost falls from $O(kd^2n)$ to $O(k\log n + d^2n)$ .

Notes and extensions

RemarkRefinements and tightness

Data-dependent radius: $\beta_t^{1/2} = m_2\sqrt\lambda + \sqrt{2\log\frac1\delta + \log\frac{\det V_{t-1}}{\lambda^d}}$ (19.14) is never worse than (19.8) and sometimes modestly better.
Worst-case flavour: the bound barely depends on $\theta^*$ or the geometry of $\mathcal A$ . Instance-dependent theory is open, except for fixed finite action sets (Chapter 25).
Tightness: $d\sqrt n$ is tight up to logs (Chapter 24), but the hard instances have infinite or exponentially large action sets. The Cauchy–Schwarz step (19.11) often loses a log (for example when $r_t = \sqrt{1/t}$ ), yet Li et al. (2019) built contextual sequences where both it and Lemma 19.4 are tight.
Few actions per round ( $\lvert\mathcal A_t\rvert\le k$ ): algorithms with $R_n = O(\sqrt{dn\log^3(nk)})$ exist (next section).

RemarkBeyond plain linearity

Kernels: infinite-dimensional $\psi$ via a kernel $\kappa((c,a),(c',a')) = \langle\psi(c,a),\psi(c',a')\rangle$ . The dimension in Lemma 19.4 is replaced by a data-dependent effective dimension, and the confidence sets must be rebuilt (Srinivas et al.; Valko et al.).
Generalised linear models: $X_t = \mu(\langle\theta^*,A_t\rangle) + \eta_t$ , for example the logistic $\mu(x) = 1/(1 + e^{-x})$ (Filippi et al. 2010). With $c_1\le\mu'\le c_2$ on the relevant region, a confidence set from $g_t(\theta) = \lambda\theta + \sum_s\mu(\langle\theta,A_s\rangle)A_s$ gives $\hat R_n\le\frac{c_2}{c_1}\sqrt{8nd\beta_n\log(1 + nL^2/d)}$ (Exercise 19.6). The $c_2/c_1$ dependence is unpleasant and probably improvable.
Other design principles: Thompson sampling (Chapter 36); optimisation-based asymptotically optimal algorithms for fixed action sets (very asymptotic, not practical yet); information-directed sampling, which minimizes squared expected regret divided by information gain (Russo–Van Roy; Kirschner–Krause).

TheoremSpectral bandits (Exercise 19.7)

Regularise anisotropically with $V_0\succ0$ (eigenvalues $\lambda_1\le\cdots\le\lambda_d$ ). If $\lVert\theta^*\rVert_{V_0}\le m$ , then with

$d_{\mathrm{eff}} = \max\Big\{i : (i-1)\lambda_i\le\frac n{\log(1 + nL^2/\lambda_1)}\Big\}$

we get $\log\frac{\det V_t}{\det V_0}\le2d_{\mathrm{eff}}\log(1 + nL^2/\lambda_1)$ and $\mathbb E[\hat R_n] = O(d_{\mathrm{eff}}\sqrt n\log(nL^2))$ . Strong regularisation in “unlikely” directions shrinks the effective dimension, but if $\lVert\theta^*\rVert_{V_0}\le m$ fails, the confidence sets are wrong and the regret degrades with $\max(0,\lVert\theta^*\rVert_{V_0} - m)$ .

Graph application (Valko et al. 2014): arms are the vertices of a graph with Laplacian $\mathcal L = Q^\top\Lambda Q$ , and $\theta = Q^\top\mu$ . Then $\frac12\sum_{i,j}W_{ij}(\mu_i - \mu_j)^2 = \lVert\theta\rVert_\Lambda^2$ , so a small $\lVert\theta\rVert_\Lambda$ means rewards vary little across strong edges. Use $V_0 = \Lambda + \lambda I$ .

TheoremLipschitz contexts (Exercise 19.5)

With $\mathcal C = [0,1]$ and each $r(\cdot,i)$ $L$ -Lipschitz, discretize the contexts (or run Exp4 over piecewise-constant policies) to get $R_n = O((Lk\log k)^{1/3}n^{2/3})$ , and the minimax rate is $\Omega((Lk)^{1/3}n^{2/3})$ . In $[0,1]^d$ the exponent worsens with the dimension. Adaptive discretisation helps under margin conditions (Perchet–Rigollet).

ExampleLinUCB versus UCB (Exercise 19.8)

Two Gaussian arms as $\{e_1,e_2\}$ : LinUCB is close to, but slightly worse than, finite-armed UCB, which has sharper constants.
$k$ random unit vectors in $\mathbb R^5$ , $n = 5000$ : UCB’s regret grows with $k$ , while LinUCB’s stays roughly flat. Structure wins once $k\gg d$ .

RemarkHistory

Linear bandits: Abe–Long (1999). Optimism with finitely many actions: Auer (2002). Confidence ellipsoids: Dani et al. (2008), Rusmevichientong–Tsitsiklis (2010), Abbasi-Yadkori et al. (2011). An expected $\tilde O(d\sqrt n)$ holds for any action-set shape with bounded means. For the unit ball and smooth convex action sets, explore-then-commit (PEGE) is already near-optimal.

Fixed finite action sets (Chapter 22)

Setting. $\mathcal A_t = \mathcal A$ with $\lvert\mathcal A\rvert = k$ , fixed over time; conditionally 1-subgaussian noise; all gaps $\Delta_a = \max_b\langle\theta^*, b - a\rangle\le1$ . Goal: $R_n = O(\sqrt{dn\log(nk)})$ , better than LinUCB’s $d\sqrt n$ by up to $\sqrt d$ when $k$ is moderate.

IntuitionDecouple design from data, then use fixed-design confidence widths

Adaptive data forces LinUCB’s confidence sets to pay a $\sqrt d$ in every direction. If each phase’s actions are chosen only from earlier phases’ data, the in-phase design is fixed, and the sharper per-direction bound $\langle\hat\theta - \theta^*,a\rangle\lesssim\sqrt{2\lVert a\rVert^2_{V^{-1}}\log(1/\delta)}$ applies. A G-optimal design makes that width uniformly small over all surviving arms with only about $d/\varepsilon^2$ samples (Kiefer–Wolfowitz).

AlgorithmPhased elimination with G-optimal exploration (Algorithm 12)

Input $\mathcal A$ , $\delta$ . Set $\mathcal A_1 = \mathcal A$ . For phases $\ell = 1, 2, \ldots$ :

find a G-optimal design $\pi_\ell$ on $\mathcal A_\ell$ (maximize $\log\det V(\pi_\ell)$ ), with support at most $d(d+1)/2$ ;
set $\varepsilon_\ell = 2^{-\ell}$ and $T_\ell(a) = \big\lceil\frac{2d\pi_\ell(a)}{\varepsilon_\ell^2}\log\frac{k\ell(\ell+1)}\delta\big\rceil$ ;
play each $a\in\mathcal A_\ell$ exactly $T_\ell(a)$ times;
compute least squares from this phase only: $\hat\theta_\ell = V_\ell^{-1}\sum_tA_tX_t$ , with $V_\ell = \sum_aT_\ell(a)aa^\top$ ;
eliminate: $\mathcal A_{\ell+1} = \{a\in\mathcal A_\ell : \max_{b\in\mathcal A_\ell}\langle\hat\theta_\ell, b - a\rangle\le2\varepsilon_\ell\}$ .

TheoremTheorem 22.1 — Regret of phased elimination

With probability at least $1-\delta$ ,

$R_n\le C\sqrt{nd\log\frac{k\log n}\delta}$

and with $\delta = O(1/n)$ , $\mathbb E[R_n]\le C\sqrt{nd\log(kn)}$ .

ProofSketch (Exercise 22.1)

Phase length: by Kiefer–Wolfowitz ( $g(\pi_\ell) = d$ , support at most $d(d+1)/2$ ), $T_\ell\le\frac{2d}{\varepsilon_\ell^2}\log\frac{k\ell(\ell+1)}\delta + \frac{d(d+1)}2$ , and $V_\ell\succeq\frac{2d}{\varepsilon_\ell^2}\log(\cdot)V(\pi_\ell)$ , so every surviving arm’s estimate is within $\varepsilon_\ell$ with high probability.

The optimal arm survives: a union bound over arms and phases (the $k\ell(\ell+1)$ factor) gives $\mathbb P(\exists\ell : a^*\notin\mathcal A_\ell)\le\delta/k$ .

Bad arms die on schedule: let $\ell_a = \min\{\ell : 2\varepsilon_\ell < \Delta_a\}$ . Then $\mathbb P(a\in\mathcal A_{\ell_a+1})\le\delta/k$ . So in phase $\ell$ every surviving arm has gap $O(\varepsilon_\ell)$ .

Sum over phases: phase $\ell$ costs about $T_\ell\cdot4\varepsilon_{\ell-1}\approx\frac{d}{\varepsilon_\ell}\log(\cdot)$ . Stopping the phase sum when $\sum T_\ell$ reaches $n$ gives $\sqrt{dn\log(\cdot)}$ , by the same balancing as in Theorem 7.2.

∎

RemarkNotes

A fixed action set is essential. For changing sets with $\lvert\mathcal A_t\rvert\le k$ , SupLinRel (Auer 2002) and SupLinUCB (Chu et al. 2011) reach $O(\sqrt{nd\log^3(nk)})$ , but they need non-random action sets and a delicate decoupling device. Li et al. (2019) proved a matching lower bound $\Omega(\sqrt{dn\log(n/d)\log k})$ , up to iterated-log factors. These algorithms are less practical than LinUCB or Thompson sampling.
Infinite $k$ : with Chapter 20’s confidence sets instead, the regret is $O(d\sqrt{n\log n})$ .
Misspecification is handled gracefully: if $X_t = \langle\theta,A_t\rangle + \eta_t + f(A_t)$ with $\lVert f\rVert_\infty\le\varepsilon$ , then $R_n = O(\sqrt{dn\log(nk)} + n\varepsilon\sqrt d\log n)$ (Exercise 22.2). The $\sqrt d$ amplification of misspecification is often unavoidable (Lattimore–Szepesvári 2019). If linearity can be tested cheaply, switching between linear and finite-armed algorithms gets $(\sqrt k\wedge d)\sqrt n$ (Ghosh et al. 2017).
Novelty: using Kiefer–Wolfowitz here appears to be new, adapted from adversarial linear bandits’ use of John’s ellipsoid (Bubeck et al. 2012; Part VI). With symmetrization it is much cleaner.

Sparse linear bandits (Chapter 23)

The problem. Features are designed by people who don’t know which ones matter. Too many features means large $d$ and slow learning; omitting a useful one means a badly wrong model. Ideally, irrelevant features should be nearly free.

DefinitionSparsity

$\lVert\theta\rVert_0 = \sum_i\mathbb I\{\theta_i\ne0\}$ , the zero-”norm”. It fails absolute homogeneity, so it isn’t a norm (Exercise 23.1).

Assumption 23.1: known $m_0, m_2$ with $\lVert\theta^*\rVert_0\le m_0$ and $\lVert\theta^*\rVert_2\le m_2$ ; $\langle\theta^*,a\rangle\le1$ for all actions; noise conditionally 1-subgaussian given $\mathcal F_t = \sigma(A_1,X_1,\ldots,A_t,X_t,A_{t+1})$ .

WarningWhy passive sparse-regression theory doesn’t transfer

Sparse-recovery results (lasso and similar) assume a well-conditioned covariance of the actions (a small ratio of largest to smallest eigenvalue). A good bandit policy plays the optimal action most of the time, so its covariance has one dominant eigenvector pointing at $a^*$ . That is badly conditioned by design. A different approach is needed.

Elimination on the hypercube

Setting. $\mathcal A = [-1,1]^d$ . Coordinates can be chosen independently, so $a^* = \mathrm{sign}(\theta)$ : learn each sign separately. In the worst case that costs $\Omega(d\sqrt n)$ (Chapter 24), but exploring a coordinate with $\theta_i = 0$ costs nothing.

LemmaRademacher probing estimates one coordinate

If $(A_{ti})_i$ are conditionally independent given the past $\mathcal G_{t-1}$ , and $A_{ti}$ is Rademacher, then

$\mathbb E[A_{ti}X_t\mid\mathcal G_{t-1}] = \theta_i\mathbb E[A_{ti}^2] + \sum_{j\ne i}\theta_j\mathbb E[A_{tj}A_{ti}] + \mathbb E[A_{ti}\eta_t] = \theta_i, \qquad \mathbb V[A_{ti}X_t\mid\mathcal G_{t-1}]\le2 \tag{23.2}$

Other coordinates contribute zero-mean noise, and the variance is bounded using $\langle\theta,a\rangle\le1$ and unit noise.

AlgorithmSelective explore-then-commit, SETC (Algorithm 13)

Each coordinate $i$ runs its own explore-then-commit:

while the confidence interval $\mathcal C_{ti}$ contains 0: play $A_{ti}\sim$ Rademacher and keep estimating $\hat\theta_{ti} = \frac1{T_i(t)}\sum_sE_{si}A_{si}X_s$ ;
once $\mathcal C_{ti}\subset(0,\infty)$ (or $(-\infty,0)$ ): commit to $A_{ti} = +1$ (or $-1$ ) forever.

The intervals are $\mathcal C_{t+1,i} = [\hat\theta_{ti}\pm W_{ti}]$ with $W_{ti} = 2\sqrt{\big(\frac1{T_i(t)} + \frac1{T_i(t)^2}\big)\log\big(n\sqrt{2T_i(t) + 1}\big)}$ , an anytime bound from the 1-D method of mixtures (Exercise 20.8).

TheoremTheorem 23.2 — Regret of SETC

For universal constants $C, C'$ ,

$R_n\le3\lVert\theta\rVert_1 + C\sum_{i:\theta_i\ne0}\frac{\log n}{\lvert\theta_i\rvert}, \qquad R_n\le3\lVert\theta\rVert_1 + C'\lVert\theta\rVert_0\sqrt{n\log n}$

without knowing $\lVert\theta\rVert_0$ .

ProofPer-coordinate regret decomposition

Step 1: The regret splits by coordinate.

$R_n = \sum_{i=1}^d\Big(n\lvert\theta_i\rvert - \mathbb E\sum_tA_{ti}\theta_i\Big) = \sum_iR_{ni} \tag{23.3}$

and $R_{ni} = 0$ when $\theta_i = 0$ .

Step 2: For $\theta_i\ne0$ . Let $\tau_i$ be the commitment time and $F_i$ the event that $\theta_i\notin\mathcal C_{\tau_i+1,i}$ . Off $F_i$ , the algorithm commits to the right sign, so $R_{ni}\le2n\lvert\theta_i\rvert\mathbb P(F_i) + \lvert\theta_i\rvert\mathbb E[\mathbb I\{F_i^c\}\tau_i]$ .

Step 3: Exploration length. Just before committing, the interval contained both 0 and $\theta_i$ , so $2W\ge\lvert\theta_i\rvert$ , which gives $\tau_i - 1\le1 + C\log n/\theta_i^2$ .

Step 4: $\mathbb P(F_i)\le1/n$ (Lemma 23.3), so $R_{ni}\le3\lvert\theta_i\rvert + C\log n/\lvert\theta_i\rvert$ . The $\sqrt n$ form follows by the usual small/large-gap split, per coordinate (Exercise 23.2).

∎

LemmaLemma 23.3 — The intervals are valid

$\mathbb P(\theta_i\notin\mathcal C_{\tau_i+1,i})\le1/n$ .

ProofEach probe’s error is

\sqrt2

-subgaussian

With $S_{ti} = \sum_{j\ne i}A_{tj}\theta_j$ and $Z_{ti} = A_{ti}\eta_t + A_{ti}S_{ti}$ , while exploring $\hat\theta_{ti} - \theta_i = \frac1t\sum_sZ_{si}$ . Condition first on $\mathcal F_{t-1}$ (noise: factor $e^{\lambda^2/2}$ ), then on $S_{ti}$ (Rademacher $A_{ti}$ is 1-subgaussian by Hoeffding’s lemma: factor $e^{\lambda^2S_{ti}^2/2}$ ), and use $\lvert S_{ti}\rvert\le\lVert A_t\rVert_\infty\lVert\theta\rVert_1\le1$ . So $\mathbb E[e^{\lambda Z_{ti}}\mid\mathcal G_{t-1}]\le e^{\lambda^2}$ . Then apply the anytime bound of Exercise 20.8.

∎

Online-to-confidence-set conversion

The problem. On a general action set, coordinates can’t be probed separately. Plan: shrink LinUCB’s ellipsoid using a sparse online regression algorithm.

WarningAmbient dimension can’t be removed in general

With $\mathcal A_t = \{e_1, \ldots, e_d\}$ , a linear bandit is a $d$ -armed bandit, and Theorem 15.2’s hard instances are 2-sparse. So $R_n = \Omega(\sqrt{dn})$ even for very sparse $\theta^*$ . The target is $\sqrt{dpn}$ with $p = m_0$ , not $m_0\sqrt n$ .

DefinitionOnline linear regression

Each round: the environment picks $(A_t,X_t)$ arbitrarily and reveals $A_t$ ; the learner predicts $\hat X_t$ ; then $X_t$ is revealed and the loss is $(X_t - \hat X_t)^2$ . Regret against weights $\theta$ :

$\rho_n(\theta) = \sum_{t=1}^n(X_t - \hat X_t)^2 - \sum_{t=1}^n(X_t - \langle\theta,A_t\rangle)^2 \tag{23.5}$

The learner has guarantee $B_n$ relative to $\Theta$ if $\sup_{\theta\in\Theta}\rho_n(\theta)\le B_n$ against every environment (23.6).

DerivationFrom prediction regret to a confidence set

Step 1: Algebra. If $X_t = \langle\theta^*,A_t\rangle + \eta_t$ , expanding $(X_t - \hat X_t)^2 = (\eta_t - (\hat X_t - \langle\theta^*,A_t\rangle))^2$ gives

$Q_t = \sum_{s\le t}(\hat X_s - \langle\theta^*,A_s\rangle)^2 = \rho_t(\theta^*) + 2\sum_{s\le t}\eta_s(\hat X_s - \langle\theta^*,A_s\rangle)\le B_t + 2Z_t \tag{23.8}$

Step 2: The cross term is a martingale. $\hat X_s$ is predictable, so $Z_t$ ‘s increments are conditionally subgaussian with variance proxy $(\hat X_s - \langle\theta^*,A_s\rangle)^2$ , which sums to $Q_t$ . The self-normalised bound (Theorem 20.4, one dimension) gives, uniformly in $t$ with probability $1-\delta$ , $\lvert Z_t\rvert\le\sqrt{(1 + Q_t)\log\frac{1 + Q_t}{\delta^2}}$ .

Step 3: Solve the implicit inequality. $Q_t\le B_t + 2\sqrt{(1 + Q_t)\log\frac{1 + Q_t}{\delta^2}}$ (23.9). The left side grows linearly in $Q_t$ and the right side sublinearly, so

$Q_t\le\beta_t(\delta) = 1 + 2B_t + 32\log\frac{\sqrt8 + \sqrt{1 + B_t}}\delta \tag{23.10}$

TheoremTheorem 23.4 — Online-to-confidence-set conversion

If $\theta^*\in\Theta$ and $\sup_{\theta\in\Theta}\rho_t(\theta)\le B_t$ , then

$\mathcal C_{t+1} = \Big\{\theta : \lVert\theta\rVert_2^2 + \sum_{s=1}^t(\hat X_s - \langle\theta,A_s\rangle)^2\le m_2^2 + \beta_t(\delta)\Big\}$

contains $\theta^*$ for all $t$ with probability $1-\delta$ . (The $\lVert\theta\rVert_2^2$ term, from $\lVert\theta^*\rVert_2\le m_2$ , keeps the set bounded when the actions don’t span.)

FormulaThe same set as an ellipsoid (Exercise 23.5)

With $V_t = I + \sum_sA_sA_s^\top$ and $\hat\theta_t = V_t^{-1}\sum_sA_s\hat X_s$ (regression on the predictions, not the rewards),

$\lVert\theta\rVert_2^2 + \sum_s(\hat X_s - \langle\theta,A_s\rangle)^2 = \lVert\theta - \hat\theta_t\rVert^2_{V_t} + \sum_s(\hat X_s - \langle\hat\theta_t,A_s\rangle)^2 + \lVert\hat\theta_t\rVert_2^2 \tag{23.11}$

so $\mathcal C_{t+1}$ is an ellipsoid centred at $\hat\theta_t$ with squared radius $m_2^2 + \beta_t - \lVert\hat\theta_t\rVert^2 - \sum_s(\hat X_s - \langle\hat\theta_t,A_s\rangle)^2$ . It is nonempty with high probability, by Theorem 23.4.

AlgorithmOLR-UCB (Algorithm 14)

Each round: build $\mathcal C_t$ from Theorem 23.4 using the predictor’s past outputs; play the optimistic $A_t = \arg\max_{a}\max_{\theta\in\mathcal C_t}\langle\theta,a\rangle$ ; feed $A_t$ to the online predictor to get $\hat X_t$ ; observe $X_t$ and feed it back.

TheoremTheorem 23.5 — Regret of OLR-UCB

With probability $1-\delta$ ,

$\hat R_n\le\sqrt{8dn\big(m_2^2 + \beta_{n-1}(\delta)\big)\log\Big(1 + \frac nd\Big)}$

This is Theorem 19.2 with the radius $\beta$ now controlled by the predictor’s regret $B_n$ , not by $d\log n$ .

TheoremTheorem 23.6 — Sparse online regression (Gerchinovitz)

Some predictor achieves, against any environment with $\lVert A_t\rVert_2\le L$ and $\lvert X_t\rvert\le X$ ,

$\rho_n(\theta)\le cX^2\lVert\theta\rVert_0\Big(\log(e + n^{1/2}L) + C_n\log\Big(1 + \frac{\lVert\theta\rVert_1}{\lVert\theta\rVert_0}\Big)\Big) + (1 + X^2)C_n, \qquad C_n = 2 + \log_2\log(e + n^{1/2}L)$

so $\sup_{\lVert\theta\rVert_0\le m_0,\lVert\theta\rVert_2\le L}\rho_n(\theta) = O(m_0\log n)$ .

CorollarySparse linear bandit regret

Subgaussian noise is unbounded, but with probability $1 - 1/n$ every $\lvert X_t\rvert\le1 + \log(2n^2)$ . Plugging $B_n = O(m_0\log n\cdot\mathrm{polylog})$ into Theorem 23.5:

$R_n = O\big(\sqrt{dnm_0}\log^2n\big)$

compared with $d\sqrt n$ for LinUCB, an improvement of $\sqrt{d/m_0}$ .

WarningCaveats

Not computationally efficient: no polynomial-time online regressor with logarithmic sparse regret is known, so OLR-UCB has no efficient implementation.
$m_0$ must be known: no algorithm gets $O(\sqrt{\lVert\theta^*\rVert_0dn})$ for all sparsity levels simultaneously (Chapter 24).
The ambient $d$ remains, unavoidably (Theorem 24.3). Recent work instead assumes nice context distributions to import high-dimensional statistics (Kim–Paik 2019; Bastani–Bayati 2020).
Use the tightest data-dependent $B_n$ : online-learning bounds start data-dependent and are loosened for exposition. Here the tight version matters.

RemarkThe conversion is generic

Any online regression guarantee yields a confidence set, for any structural assumption on $\theta$ , including the non-sparse case. Rakhlin–Sridharan (2017) show the relationship goes both ways: tail inequalities imply regret bounds and vice versa. Similar constructions appear in Gentile and coauthors’ work. SETC is from Lattimore et al. (2015); the conversion from Abbasi-Yadkori et al. (2012).

Quick reference

Object	Statement	Note
Linear bandit	$X_t = \langle\theta^*,A_t\rangle + \eta_t$ , $A_t\in\mathcal A_t$	finite-armed, contextual, combinatorial as special cases
Ridge estimate	$\hat\theta_t = V_t^{-1}\sum A_sX_s$ , $V_t = \lambda I + \sum A_sA_s^\top$
Confidence ellipsoid	$\lVert\theta - \hat\theta_{t-1}\rVert^2_{V_{t-1}}\le\beta_t$	$\sqrt\beta\approx m_2\sqrt\lambda + \sqrt{2\log\frac1\delta + d\log(\cdot)}$
LinUCB index	$\langle\hat\theta,a\rangle + \sqrt{\beta_t}\lVert a\rVert_{V^{-1}}$	UCB when $\mathcal A = \{e_i\}$
Elliptical potential	$\sum(1\wedge\lVert a_t\rVert^2_{V^{-1}})\le2\log\frac{\det V_n}{\det V_0}\le2d\log(\cdot)$	$\det$ grows by $1 + \lVert a\rVert^2_{V^{-1}}$
LinUCB regret	$\sqrt{8dn\beta_n\log(\cdot)} = O(d\sqrt n\log n)$	tight up to logs in the worst case
Unstructured contexts	$\Omega(\sqrt{nMk})$	why features are needed
Spectral	$O(d_{\mathrm{eff}}\sqrt n\log n)$	anisotropic regularisation
GLM	$\frac{c_2}{c_1}\sqrt{8nd\beta\log(\cdot)}$	link-dependent factor
Fixed finite $\mathcal A$	$O(\sqrt{dn\log(nk)})$	phased elimination + G-optimal design
Changing, $\lvert\mathcal A_t\rvert\le k$	$O(\sqrt{dn\log^3(nk)})$	SupLinUCB
Misspecification	$+\,n\varepsilon\sqrt d\log n$	phased elimination
Hypercube (SETC)	$3\lVert\theta\rVert_1 + C\sum\frac{\log n}{\lvert\theta_i\rvert}$ ; $O(\lVert\theta\rVert_0\sqrt{n\log n})$	no knowledge of sparsity
Conversion	$Q_t\le1 + 2B_t + 32\log\frac{\sqrt8 + \sqrt{1 + B_t}}\delta$	regression regret → confidence set
OLR-UCB	$O(\sqrt{dnm_0}\log^2n)$	not efficient; needs $m_0$

Facts to keep to hand

Linearity turns arms into directions. Every observation constrains $\theta^*$ , so the cost scales with $d$ , not the number of actions. LinUCB is UCB with an ellipsoid in place of intervals.
The elliptical potential lemma is the engine. Novel directions inflate $\det V$ , which can only grow like $(1 + nL^2/d\lambda)^d$ , so total novelty is $O(d\log n)$ . Cauchy–Schwarz turns that into $\sqrt{dn\beta}$ regret.
Adaptive data costs a $\sqrt d$ ; decoupling buys it back. Phases whose designs depend only on past phases can use fixed-design widths, and Kiefer–Wolfowitz makes them uniformly small with about $d/\varepsilon^2$ samples.
Sparsity helps, but not completely. Separable action sets (the hypercube) allow $\lVert\theta\rVert_0\sqrt n$ . In general the ambient $d$ survives as $\sqrt{dm_0n}$ , and the best-known algorithm is not efficient.
Online regression and confidence sets are two views of one thing. A predictor’s squared-loss regret bound plus self-normalised concentration gives a valid ellipsoid for any structural class.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 19, 22, 23

Related