Confidence Bounds and Optimal Design for Least Squares Estimators

Corresponds to Lattimore & Szepesvári, Chapters 20–21. Used throughout stochastic-linear-bandits.

Motivation: two questions about least squares

IntuitionWhat a linear bandit algorithm needs from statistics

Confidence (Chapter 20): after actions $A_1, \ldots, A_t$ and rewards $X_s = \langle\theta^*,A_s\rangle + \eta_s$ , how far can the least-squares estimate be from $\theta^*$ ? The difficulty: the actions were chosen by the algorithm, based on earlier rewards, so they are neither fixed nor independent of the noise.
Design (Chapter 21): if we may choose the actions freely, which ones make the estimate accurate in every direction we care about, with as few samples as possible?

Notation. $\hat\theta_t = V_t(\lambda)^{-1}\sum_{s\le t}X_sA_s$ with $V_t(\lambda) = \lambda I + \sum_{s\le t}A_sA_s^\top$ ; $V_t = V_t(0)$ ; $\lVert x\rVert_V^2 = x^\top Vx$ ; $S_t = \sum_{s\le t}\eta_sA_s$ .

Warm-up: fixed design

Simplifying assumptions (dropped later): $\lambda = 0$ with $V_t$ invertible (so $t\ge d$ ); independent 1-subgaussian noise; actions fixed in advance.

TheoremPer-direction confidence bound

For any fixed $x\in\mathbb R^d$ ,

$\mathbb P\Big(\langle\hat\theta_t - \theta^*,x\rangle\ge\sqrt{2\lVert x\rVert^2_{V_t^{-1}}\log\frac1\delta}\Big)\le\delta \tag{20.2}$

ProofThe error is a fixed linear combination of the noise

$\hat\theta_t - \theta^* = V_t^{-1}\sum_sA_s(A_s^\top\theta^* + \eta_s) - \theta^* = V_t^{-1}\sum_sA_s\eta_s$ , so $\langle\hat\theta_t - \theta^*,x\rangle = \sum_s\langle x,V_t^{-1}A_s\rangle\eta_s$ . With deterministic coefficients, this is subgaussian with variance proxy $\sum_s\langle x,V_t^{-1}A_s\rangle^2 = x^\top V_t^{-1}\big(\sum_sA_sA_s^\top\big)V_t^{-1}x = \lVert x\rVert^2_{V_t^{-1}}$ . Apply Theorem 5.3.

∎

Intuition $\lVert x\rVert_{V^{-1}}$ is the uncertainty in direction $x$

Directions sampled often (large $V$ along $x$ ) have small $\lVert x\rVert_{V^{-1}}$ . If $A_s = e_i$ for $T_i$ rounds, then $\lVert e_i\rVert^2_{V^{-1}} = 1/T_i$ , the usual $1/\sqrt{\text{count}}$ width.

From one direction to all directions: covering

LemmaLemma 20.1 — Covering the sphere

There is a set $C_\varepsilon\subset\mathbb R^d$ with $\lvert C_\varepsilon\rvert\le(3/\varepsilon)^d$ such that every $x\in S^{d-1}$ has some $y\in C_\varepsilon$ with $\lVert x - y\rVert_2\le\varepsilon$ .

DerivationUniform bound by covering

Step 1: $\lVert\hat\theta - \theta^*\rVert_{V_t} = \max_{x\in S^{d-1}}\langle V_t^{1/2}x,\hat\theta - \theta^*\rangle$ , but the maximizing $x$ is random, so (20.2) doesn’t apply to it directly.

Step 2: apply (20.2) to each $V_t^{1/2}y$ with $y\in C_\varepsilon$ (note $\lVert V_t^{1/2}y\rVert_{V_t^{-1}} = \lVert y\rVert = 1$ ) plus a union bound. With probability $1-\delta$ all are below $\sqrt{2\log(\lvert C_\varepsilon\rvert/\delta)}$ .

Step 3: Approximate the maximizer. For any $x$ and its nearest $y$ , $\langle V^{1/2}(x - y),\hat\theta - \theta^*\rangle\le\varepsilon\lVert\hat\theta - \theta^*\rVert_V$ . So $\lVert\hat\theta - \theta^*\rVert_V < \varepsilon\lVert\hat\theta - \theta^*\rVert_V + \sqrt{2\log(\lvert C_\varepsilon\rvert/\delta)}$ . Rearrange and take $\varepsilon = \frac12$ :

$\mathbb P\Big(\lVert\hat\theta_t - \theta^*\rVert_{V_t}\ge2\sqrt{2\big(d\log6 + \log\tfrac1\delta\big)}\Big)\le\delta \tag{20.3}$

ImportantA uniform bound costs $\sqrt d$

One direction: width $\sqrt{2\log(1/\delta)}$ . All directions at once: width $\approx\sqrt{d + \log(1/\delta)}$ . The $(3/\varepsilon)^d$ covering is where the dimension enters. This is essentially optimal, but the argument relies on $V_t$ being deterministic.

Martingales and the method of mixtures

Assumptions now: $X_t = \langle\theta^*,A_t\rangle + \eta_t$ ; the noise is conditionally 1-subgaussian, $\mathbb E[e^{\alpha\eta_t}\mid\mathcal F_{t-1}]\le e^{\alpha^2/2}$ , where $\mathcal F_{t-1}$ contains $A_1,X_1,\ldots,A_{t-1},X_{t-1},A_t$ (so the noise may depend on the current action, as with Bernoulli rewards); $\lambda > 0$ . Actions are chosen adaptively, and the horizon may be infinite.

WarningPlain Cramér–Chernoff fails

We’d want to bound $\mathbb E\exp\big(\alpha\lVert\hat\theta_t - \theta^*\rVert^2_{V_t(\lambda)}\big)$ , but with an adaptive $V_t$ nobody knows how.

FormulaLinearize with a maximum (Fenchel duality)

With $\lambda = 0$ for intuition: $\hat\theta_t - \theta^* = V_t^{-1}S_t$ and

$\frac12\lVert\hat\theta_t - \theta^*\rVert^2_{V_t} = \frac12\lVert S_t\rVert^2_{V_t^{-1}} = \max_{x\in\mathbb R^d}\Big(\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t}\Big)$

The maximum is attained at $x = V_t^{-1}S_t$ . This separates the martingale $S_t$ (appearing linearly) from $V_t$ , at the price of a max. It is a case of $f(x) = \sup_u\langle u,x\rangle - f^*(u)$ (Chapter 26).

LemmaLemma 20.2 — Exponential supermartingale

For every fixed $x\in\mathbb R^d$ ,

$M_t(x) = \exp\Big(\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t}\Big)$

is a nonnegative $\mathbb F$ -supermartingale with $M_0(x)\le1$ (it also holds with $V_t(\lambda)$ ).

ProofOne-step subgaussianity in direction

x

Conditional subgaussianity with $\alpha = \langle x,A_t\rangle$ (which is $\mathcal F_{t-1}$ -measurable) gives $\mathbb E[e^{\eta_t\langle x,A_t\rangle}\mid\mathcal F_{t-1}]\le e^{\langle x,A_t\rangle^2/2} = e^{\lVert x\rVert^2_{A_tA_t^\top}/2}$ . So $\mathbb E[M_t(x)\mid\mathcal F_{t-1}] = M_{t-1}(x)\,\mathbb E\big[e^{\eta_t\langle x,A_t\rangle - \frac12\lVert x\rVert^2_{A_tA_t^\top}}\mid\mathcal F_{t-1}\big]\le M_{t-1}(x)$ .

∎

WarningThe max is on the wrong side

Cramér–Chernoff gives $\mathbb P\big(\frac12\lVert\hat\theta - \theta^*\rVert^2_{V_t}\ge\log\frac1\delta\big)\le\delta\,\mathbb E[\max_xM_t(x)]$ (20.5). But Lemma 20.2 controls $\max_x\mathbb E[M_t(x)]$ , and $\mathbb E\max\ge\max\mathbb E$ . Two fixes: cover the near-maximizers (works, but loosely), or replace the max with an integral.

IntuitionLaplace’s method: an integral of an exponential is about its max

If $f$ has a sharp maximum at $x_0$ with $f''(x_0) = -q < 0$ , then

$\int e^{sf(x)}dx\sim e^{sf(x_0)}\sqrt{\frac{2\pi}{sq}}\qquad(s\to\infty)$

by a second-order Taylor expansion and a Gaussian integral. The integrating measure barely matters as long as it charges a neighbourhood of the maximizer. So $\max_xM_t(x)\approx\int M_t(x)\,dh(x)$ (20.6), and integrals commute with expectations.

LemmaLemma 20.3 — Mixtures preserve the supermartingale property

For any probability measure $h$ on $\mathbb R^d$ , $\bar M_t = \int M_t(x)\,dh(x)$ is a nonnegative supermartingale with $\bar M_0 = 1$ (Fubini for the conditional expectation; measurability via the sections lemma, Exercise 20.5).

TheoremTheorem 20.4 — Self-normalised bound, uniform in time

For all $\lambda > 0$ and $\delta\in(0,1)$ ,

$\mathbb P\Big(\exists t\in\mathbb N : \lVert S_t\rVert^2_{V_t(\lambda)^{-1}}\ge2\log\frac1\delta + \log\frac{\det V_t(\lambda)}{\lambda^d}\Big)\le\delta$

ProofGaussian prior, complete the square, maximal inequality

Step 1: Mix with a Gaussian. Let $H = \lambda I$ and $h = \mathcal N(0,H^{-1})$ :

$\bar M_t = \frac1{\sqrt{(2\pi)^d\det H^{-1}}}\int\exp\Big(\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t} - \frac12\lVert x\rVert^2_H\Big)dx$

Step 2: Complete the square.

$\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t + H} = \frac12\lVert S_t\rVert^2_{(H+V_t)^{-1}} - \frac12\big\lVert x - (H+V_t)^{-1}S_t\big\rVert^2_{H+V_t}$

The remaining Gaussian integral is exact:

$\bar M_t = \Big(\frac{\det H}{\det(H + V_t)}\Big)^{1/2}\exp\Big(\frac12\lVert S_t\rVert^2_{(H+V_t)^{-1}}\Big) \tag{20.8}$

and $H + V_t = V_t(\lambda)$ .

Step 3: Maximal inequality. $\bar M_t$ is a nonnegative supermartingale starting at 1, so Theorem 3.9 gives $\mathbb P(\sup_t\bar M_t\ge1/\delta)\le\delta$ (20.7). Take logs and rearrange.

∎

ImportantWhat the mixture buys

Uniform in time (anytime-valid): one union-free bound for all $t$ , from the maximal inequality, not a union bound.
Valid under adaptive designs: only conditional subgaussianity was used.
The dimension enters only through $\log\det V_t(\lambda)/\lambda^d$ : the Gaussian prior “pays” for not knowing the maximizing direction, exactly what the covering paid for, but data-dependently and with better constants. In practice the improvement over covering is large.
Bounds of this type are called self-normalised (de la Peña et al.); the method of mixtures goes back to Robbins–Siegmund (1970).

TheoremTheorem 20.5 — Confidence ellipsoid for ridge regression

With probability at least $1-\delta$ , for all $t\in\mathbb N$ ,

$\lVert\hat\theta_t - \theta^*\rVert_{V_t(\lambda)} < \sqrt\lambda\lVert\theta^*\rVert_2 + \sqrt{2\log\frac1\delta + \log\frac{\det V_t(\lambda)}{\lambda^d}}$

If $\lVert\theta^*\rVert_2\le m_2$ , then

$\mathcal C_t = \Big\{\theta : \lVert\hat\theta_{t-1} - \theta\rVert_{V_{t-1}(\lambda)} < m_2\sqrt\lambda + \sqrt{2\log\frac1\delta + \log\frac{\det V_{t-1}(\lambda)}{\lambda^d}}\Big\}$

contains $\theta^*$ for every $t$ with probability $1-\delta$ . This is exactly the set LinUCB needs (Theorem 19.2).

ProofSeparate noise from regularisation bias

$\hat\theta_t - \theta^* = V_t(\lambda)^{-1}S_t + (V_t(\lambda)^{-1}V_t - I)\theta^*$ . By the triangle inequality in $\lVert\cdot\rVert_{V_t(\lambda)}$ , the first term gives $\lVert S_t\rVert_{V_t(\lambda)^{-1}}$ . For the second, using $I - V_t(\lambda)^{-1}V_t = \lambda V_t(\lambda)^{-1}$ , its squared norm is $\lambda\,\theta^{*\top}(I - V_t(\lambda)^{-1}V_t)\theta^*\le\lambda\lVert\theta^*\rVert^2$ . Then apply Theorem 20.4.

∎

FormulaA concrete radius

If $\lVert A_t\rVert_2\le L$ : by AM–GM on the eigenvalues, $\frac{\det V_t(\lambda)}{\lambda^d}\le\big(1 + \frac{nL^2}{\lambda d}\big)^d$ (20.9). With $\lambda = 1$ ,

$\mathcal C_t = \Big\{\theta : \lVert\hat\theta_{t-1} - \theta\rVert_{V_{t-1}(1)} < m_2 + \sqrt{2\log\frac1\delta + d\log\Big(1 + \frac{nL^2}d\Big)}\Big\}$

Prefer the $\log\det$ form inside algorithms (it is data-dependent and smaller); use this form for stating regret bounds.

How tight is this?

NoteVariance plus bias, and the unavoidable $\sqrt d$

Up to constants and a $\sqrt{\log n}$ , the adaptive radius matches the fixed-design (20.3). Playing each $e_i$ $m$ times with Gaussian noise gives $\lVert\hat\theta - \theta^*\rVert^2_{V}\sim\chi^2_d$ , so $\mathbb E\lVert\hat\theta_n - \theta^*\rVert^2_{V_n} = d$ (Exercise 20.1). The $2\log\frac1\delta$ term is the fluctuation (variance) of this $\chi^2$ ; the $d\log(\cdot)$ term is its mean (bias). So the $\sqrt d$ in a self-normalised bound can’t be avoided, even with fixed designs.

WarningFixed directions: going through the ellipsoid costs $\sqrt d$

Bounding $\langle\hat\theta - \theta^*,x\rangle$ via the whole ellipsoid gives width about $\sqrt d\lVert x\rVert_{V^{-1}}$ , while the fixed-design bound (20.2) has no $\sqrt d$ . So under fixed design, avoid the ellipsoid for single-direction questions. Under sequential design the $\sqrt d$ is genuinely needed: an adaptive choice of basis vectors (play each once, then repeatedly sample the coordinates that push $\langle\hat\theta,\mathbf 1\rangle$ away from zero) achieves $\mathbb E\big[\langle\hat\theta_n,\mathbf 1\rangle^2/\lVert\mathbf 1\rVert^2_{V_n^{-1}}\big]\ge cd$ (Exercise 20.2). Designing per-direction bounds that adapt to how dependent the design actually is remains open.

RemarkSupermartingales are behind every Chernoff argument

Most Cramér–Chernoff proofs for sums can be rewritten as “this exponential is a supermartingale, apply Markov or the maximal inequality”, for example the Exp3-IX concentration lemma (Lemma 12.2). Lai (2009) surveys martingale methods in sequential analysis.

Further results from the exercises

DefinitionCovering and packing numbers (Def. 20.6)

An $\varepsilon$ -cover $C\subseteq A$ has $A\subseteq\bigcup_{x\in C}B(x,\varepsilon)$ ; an $\varepsilon$ -packing $P\subseteq A$ has pairwise distances $> \varepsilon$ . $N(A,\varepsilon)$ is the minimum cover size and $M(A,\varepsilon)$ the maximum packing size; their logs are the metric entropy. The definitions extend to pseudo-metrics.

TheoremCovering facts (Exercises 20.3–20.4)

$N(\varepsilon)$ increases as $\varepsilon\downarrow0$ ; $M(2\varepsilon)\le N(\varepsilon)\le M(\varepsilon)$ ; and for convex $A$ with $\varepsilon B\subseteq A$ ,

$\Big(\frac1\varepsilon\Big)^d\frac{\mathrm{vol}(A)}{\mathrm{vol}(B)}\le N(\varepsilon)\le M(\varepsilon)\le\frac{\mathrm{vol}(A + \frac\varepsilon2B)}{\mathrm{vol}(\frac\varepsilon2B)}\le\Big(\frac3\varepsilon\Big)^d\frac{\mathrm{vol}(A)}{\mathrm{vol}(B)}$

(volume comparison: disjoint $\frac\varepsilon2$ -balls around a packing fit inside $A + \frac\varepsilon2B$ ). The covers are finite iff $A$ is bounded. Lemma 20.1 follows for the sphere.

TheoremHoeffding–Azuma (Exercises 20.6–20.7)

For adapted $X_t\in[a_t,b_t]$ a.s., $\mathbb P\big(\sum_t(X_t - \mathbb E[X_t\mid\mathcal F_{t-1}])\ge\varepsilon\big)\le\exp\big(-\frac{2\varepsilon^2}{\sum_t(b_t - a_t)^2}\big)$ : Hoeffding for martingale differences. With predictable random ranges $[A_t,B_t]$ and $R^2 = \sum(B_t - A_t)^2$ : $\mathbb P\big(\{R\le r\}\cap\{\sum\cdots\ge\varepsilon\}\big)\le e^{-2\varepsilon^2/r^2}$ .

TheoremAnytime one-dimensional bound (Exercise 20.8)

If $\mathbb E[e^{\lambda X_t}\mid\mathcal F_{t-1}]\le e^{\lambda^2\sigma^2/2}$ and $S_t = \sum_{s\le t}X_s$ , then for any $\rho > 0$ ,

$\mathbb P\Big(\exists t : \lvert S_t\rvert\ge\sqrt{2(t\sigma^2 + \rho^2)\log\frac{\sqrt{t\sigma^2 + \rho^2}}{\rho^2\delta}}\Big)\le\delta$

This is the method of mixtures in one dimension with a Gaussian prior of precision $\rho^2$ . SETC’s intervals in the sparse hypercube algorithm use it.

TheoremLaw of the iterated logarithm via mixtures (Exercise 20.9)

Mixing $\exp(\lambda S_n - \lambda^2n/2)$ over a density $f$ on $[0,\infty)$ with $\log\frac1{\lambda f(\lambda)} = (1 + o(1))\log\log\frac1\lambda$ as $\lambda\to0$ gives $\mathbb P\big(\limsup_n\frac{S_n}{\sqrt{2n\log\log n}}\le1\big) = 1$ , half of the LIL. The largest fluctuations of a random walk are about $\sqrt{2n\log\log n}$ , which is why anytime confidence widths need at least $\log\log t$ inside the square root.

TheoremSequential likelihood-ratio confidence sets (Exercise 20.11)

For a parametric family $p_\theta$ and any predictable estimates $\hat\theta_{s-1}$ , let $L_t(\theta) = \sum_{s\le t}\log\frac{p_{\hat\theta_{s-1}}(X_s)}{p_\theta(X_s)}$ . Then $e^{L_t(\theta^*)}$ is a nonnegative martingale with mean 1 (a product of likelihood ratios), so $\mathbb P(\sup_tL_t(\theta^*)\ge\log\frac1\delta)\le\delta$ , and $\Theta_t = \{\theta : L_t(\theta) < \log\frac1\delta\}$ is an anytime confidence sequence (Lai–Robbins 1985; Robbins–Siegmund 1972). Compare the wealth-ratio supermartingale: the same idea with a predictable “bettor”.

NoteTernary martingales (Exercise 20.10)

For $X_t\in\{-1,0,1\}$ with $N_t = \sum_s\lvert X_s\rvert$ nonzero observations, $\lvert S_t\rvert\le\sqrt{2N_t\log(c\sqrt{N_t}/\delta)}$ for all $t$ with probability $1-\delta$ , with $c\approx3.43$ (Lattimore et al. 2018). The width scales with the number of informative rounds only.

Optimal design: the Kiefer–Wolfowitz theorem

Setting (Chapter 21). Fixed actions $a_1, \ldots, a_n$ spanning $\mathbb R^d$ ; independent 1-subgaussian noise; unregularised least squares $\hat\theta = V^{-1}\sum_ta_tX_t$ , $V = \sum_ta_ta_t^\top$ . By (20.2), for each $a\in\mathcal A$ : $\mathbb P\big(\langle\hat\theta - \theta^*,a\rangle\ge\sqrt{2\lVert a\rVert^2_{V^{-1}}\log\frac1\delta}\big)\le\delta$ (21.1). Goal: the shortest exploration sequence making this width at most $\varepsilon$ for all $a\in\mathcal A$ . Exactly, that’s an intractable integer program; approximately, it’s an efficient convex problem.

DefinitionDesign, G-optimality, D-optimality

A design is a distribution $\pi$ on $\mathcal A$ . Define

$V(\pi) = \sum_{a\in\mathcal A}\pi(a)aa^\top, \qquad g(\pi) = \max_{a\in\mathcal A}\lVert a\rVert^2_{V(\pi)^{-1}}, \qquad f(\pi) = \log\det V(\pi) \tag{21.2}$

G-optimal (“global”): minimizes $g$ , the worst-case predictive variance.
D-optimal (“determinant”): maximizes $f$ , i.e. minimizes the volume of the confidence ellipsoid.

$\mathrm{Supp}(\pi)$ is the core set.

FormulaFrom a design to an exploration schedule

Play each $a\in\mathrm{Supp}(\pi)$ exactly $n_a = \big\lceil\frac{2\pi(a)g(\pi)}{\varepsilon^2}\log\frac1\delta\big\rceil$ times (21.3). Then $V\succeq\frac{2g(\pi)}{\varepsilon^2}\log\frac1\delta\,V(\pi)$ , so every $a\in\mathcal A$ has width at most $\varepsilon$ with probability $1-\delta$ (each $a$ separately). The total is

$n\le\lvert\mathrm{Supp}(\pi)\rvert + \frac{2g(\pi)}{\varepsilon^2}\log\frac1\delta$

So we want small $g$ and a small support.

TheoremTheorem 21.1 — Kiefer–Wolfowitz

Let $\mathcal A\subset\mathbb R^d$ be compact with $\mathrm{span}(\mathcal A) = \mathbb R^d$ . The following are equivalent:

$\pi^*$ minimizes $g$ (G-optimal);
$\pi^*$ maximizes $f = \log\det V(\pi)$ (D-optimal);
$g(\pi^*) = d$ .

Moreover, some minimizer has $\lvert\mathrm{Supp}(\pi^*)\rvert\le d(d+1)/2$ .

ImportantEvery action can be learned at the price of $d$ dimensions

No matter how many actions (even infinitely many), a design with support at most $d(d+1)/2$ makes every action’s predictive variance at most $d/(\text{samples})$ . That is the same as estimating $d$ unrelated means, which is where the $\sqrt{dn}$ regret of phased elimination comes from.

ProofProof (finite

\mathcal A

): first-order optimality of a concave objective

Facts: $f$ is concave (Exercise 21.2: $t\mapsto\log\det(H + tZ)$ is concave), with gradient $(\nabla f(\pi))_a = \lVert a\rVert^2_{V(\pi)^{-1}}$ (21.4, Exercise 21.1, from $\frac{d}{dt}\log\det A(t) = \operatorname{trace}(A^{-1}\dot A)$ ). And for every $\pi$ ,

$\sum_a\pi(a)\lVert a\rVert^2_{V(\pi)^{-1}} = \operatorname{trace}\Big(\sum_a\pi(a)aa^\top V(\pi)^{-1}\Big) = \operatorname{trace}I = d \tag{21.5}$

so the average predictive variance is always $d$ , and hence $g(\pi)\ge d$ .

(2)⇒(1),(3): at a maximizer $\pi^*$ of the concave $f$ , for every distribution $\pi$ , $0\ge\langle\nabla f(\pi^*),\pi - \pi^*\rangle = \sum_a\pi(a)\lVert a\rVert^2_{V(\pi^*)^{-1}} - d$ . Taking $\pi = \delta_a$ gives $\lVert a\rVert^2_{V(\pi^*)^{-1}}\le d$ for all $a$ , so $g(\pi^*)\le d$ . With $g\ge d$ always, $\pi^*$ minimizes $g$ and $\min g = d$ .

(3)⇒(2): if $g(\pi^*) = d$ , then $\langle\nabla f(\pi^*),\pi - \pi^*\rangle = \sum_a\pi(a)\lVert a\rVert^2_{V(\pi^*)^{-1}} - d\le g(\pi^*) - d = 0$ , which is first-order optimality for a concave function. (1)⇒(3) now follows.

Small support: at an optimum, every $a$ in the support has $\lVert a\rVert^2_{V(\pi^*)^{-1}} = d$ (Exercise 21.5). If $\lvert S\rvert > d(d+1)/2$ , the dimension of symmetric matrices, some nonzero $v$ on $S$ has $\sum_{a\in S}v(a)aa^\top = 0$ . Then $d\sum_av(a) = \sum_av(a)\lVert a\rVert^2_{V^{-1}} = 0$ , so moving along $\pi^* + tv$ keeps $V$ , hence $f$ , unchanged and stays a distribution until some weight hits zero. That gives a smaller optimal support; induct.

∎

IntuitionGeometry: the minimum-volume enclosing ellipsoid

With $V$ from a D-optimal design, the ellipsoid $\mathcal E = \{x : \lVert x\rVert^2_{V^{-1}}\le d\}$ contains all of $\mathcal A$ , with the core set on its boundary. It is the minimum-volume centred ellipsoid containing $\mathcal A$ , unique, and its computation is the convex dual of the log-det problem (Silvey–Sibson). Equivalently, it is the MVEE (John’s ellipsoid) of the symmetrised set $\mathcal A\cup(-\mathcal A)$ .

RemarkVariants

Non-spanning sets (Exercise 21.6): if $\dim\mathrm{span}(\mathcal A) = m$ , some $\pi^*$ with support at most $m(m+1)/2$ has $g(\pi^*) = m$ .
Approximate designs suffice: $g(\pi)\le(1+\varepsilon)g(\pi^*)$ inflates regret bounds only by a factor $(1+\varepsilon)^{1/2}$ .
Infinite action sets: approximate designs can sometimes be found efficiently, but the algorithms are much heavier (Hazan et al. 2016; Grötschel et al.).

AlgorithmFrank–Wolfe / Fedorov–Wynn for D-optimal design

Start from $\pi_0$ (for example uniform). Repeat:

$a_k = \arg\max_{a\in\mathcal A}\lVert a\rVert^2_{V(\pi_k)^{-1}}$ (the gradient coordinate, i.e. the worst-covered action);
move toward it: $\pi_{k+1} = (1 - \gamma_k)\pi_k + \gamma_k\delta_{a_k}$ (21.7), with exact line search $\gamma_k = \frac{\frac1d\lVert a_k\rVert^2_{V(\pi_k)^{-1}} - 1}{\lVert a_k\rVert^2_{V(\pi_k)^{-1}} - 1} \tag{21.8}$

From uniform, $g(\pi_k)\le(1+\varepsilon)d$ after $O(d\log\log\lvert\mathcal A\rvert + d/\varepsilon)$ iterations. A smarter initialisation removes the $\lvert\mathcal A\rvert$ dependence and gives $g\le2d$ with core set $O(d\log\log d)$ after $O(d\log\log d)$ iterations. Rank-one updates make each step cheap (Exercise 21.7). History: Fedorov (1972) and Wynn (1970), a specialisation of Frank–Wolfe (1956). See Todd (2016) for variants and convergence rates.

Quick reference

Object	Statement	Note
Fixed-design direction bound	$\langle\hat\theta - \theta^*,x\rangle < \sqrt{2\lVert x\rVert^2_{V^{-1}}\log\frac1\delta}$	no $d$
Covering	$\lvert C_\varepsilon\rvert\le(3/\varepsilon)^d$	$\lVert\hat\theta - \theta^*\rVert_V\le2\sqrt{2(d\log6 + \log\frac1\delta)}$
Linearisation	$\frac12\lVert S\rVert^2_{V^{-1}} = \max_x\langle x,S\rangle - \frac12\lVert x\rVert^2_V$	Fenchel duality
Supermartingale	$M_t(x) = e^{\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t}}$	conditional subgaussianity
Mixture	$\bar M_t = \sqrt{\det H/\det V_t(\lambda)}\,e^{\frac12\lVert S_t\rVert^2_{V_t(\lambda)^{-1}}}$	Gaussian prior $\mathcal N(0,H^{-1})$
Self-normalised bound	$\lVert S_t\rVert^2_{V_t(\lambda)^{-1}} < 2\log\frac1\delta + \log\frac{\det V_t(\lambda)}{\lambda^d}$ for all $t$	anytime, adaptive designs
Ellipsoid radius	$m_2\sqrt\lambda + \sqrt{2\log\frac1\delta + \log\frac{\det V_t(\lambda)}{\lambda^d}}$	$\le m_2 + \sqrt{2\log\frac1\delta + d\log(1 + \frac{nL^2}d)}$
Unavoidable $\sqrt d$	$\mathbb E\lVert\hat\theta - \theta^*\rVert^2_V = d$	$\chi^2_d$
Hoeffding–Azuma	$\exp(-2\varepsilon^2/\sum(b_t - a_t)^2)$	martingale Hoeffding
LIL	$\limsup S_n/\sqrt{2n\log\log n} = 1$	mixtures give the upper half
Average variance	$\sum_a\pi(a)\lVert a\rVert^2_{V(\pi)^{-1}} = d$	so $g\ge d$
Kiefer–Wolfowitz	G-optimal ⇔ D-optimal ⇔ $g = d$ ; support $\le d(d+1)/2$
Samples for width ε	$\le\lvert\mathrm{Supp}\rvert + \frac{2d}{\varepsilon^2}\log\frac1\delta$
MVEE	$\{x : \lVert x\rVert^2_{V^{-1}}\le d\}\supseteq\mathcal A$	John’s ellipsoid of $\mathcal A\cup(-\mathcal A)$
Frank–Wolfe	move toward $\arg\max\lVert a\rVert^2_{V^{-1}}$ , step (21.8)	$O(d\log\log\lvert\mathcal A\rvert + d/\varepsilon)$ iterations

Facts to keep to hand

Adaptive designs break naive least-squares confidence intervals. The coefficients multiplying the noise depend on the noise, so the fixed-design argument and its covering extension don’t apply.
The method of mixtures fixes this cleanly. Linearize the quadratic with a max, note that each $e^{\langle x,S_t\rangle - \frac12\lVert x\rVert^2_{V_t}}$ is a supermartingale, replace the max with a Gaussian-prior average (Laplace’s idea), compute it in closed form, and apply the maximal inequality. The result is anytime-valid and self-normalised.
Dimension enters as $\log\det$ . The prior pays for not knowing the worst direction. The $\sqrt d$ is real: it is the mean of a $\chi^2_d$ , and per-direction bounds need it under sequential design too.
Good designs make every action cheap to estimate. The average predictive variance under any design is exactly $d$ , and a D-optimal design achieves maximum $= d$ on a core set of at most $d(d+1)/2$ points: the minimum-volume enclosing ellipsoid.
Confidence and design are two halves of linear bandits. Optimistic algorithms use the ellipsoid; elimination algorithms use designs and fixed-design widths, buying back a $\sqrt d$ when the action set is fixed and finite.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapters 20–21
Todd, Minimum-Volume Ellipsoids (2016) — design and MVEE algorithms
de la Peña, Lai & Shao, Self-Normalized Processes (2008)

Related