# Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Raymond Zhang, Hédi Hadiji, Richard Combes

<figure><img src="image_1.png" /></figure>

## To cite this version:

Raymond Zhang, Hédi Hadiji, Richard Combes. Linear Bandits on Ellipsoids: Minimax Optimal Algorithms. 38th Annual Conference on Learning Theory (COLT 2025), Jun 2025, Lyon, France. pp.6016-6040. hal-05369727

HAL Id: hal-05369727

https://hal.science/hal-05369727v1

Submitted on 17 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Raymond Zhang*

Hédi Hadiji*

Richard Combes

RAYMOND.ZHANG@CENTRALESUPELEC.FR

HEDI.HADIJI@CENTRALESUPELEC.FR

RICHARD.COMBES@CENTRALESUPELEC

Laboratoire des signaux et systèmes, Université Paris-Saclay, CNRS, CentraleSupélec, France

**Editors:** Nika Haightalab and Ankur Moitra

## Abstract

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least $\Omega(\min(d\sigma\sqrt{T} + d\|\theta\|_A, \|\theta\|_A T))$ where $d$ is the dimension, $T$ the time horizon, $\sigma^2$ the noise variance, $A$ a matrix defining the set of actions and $\theta$ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate $\|\theta\|$, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings. The code to reproduce the experiments is available at https://github.com/RaymZhang/LinearBanditsEllipsoidsMinimaxCOLT.

# 1. Introduction

## 1.1. Model

We consider the problem of stochastic linear bandits over ellipsoids with independent subgaussian rewards. Time is discrete with a horizon $T$, and at time $t \in [T] = \{1, \dots, T\}$ a learner selects an action $x_t \in \mathcal{X}$ where action set $\mathcal{X}$ is a subset of $\mathbb{R}^d$ initially known to the learner. The action set $\mathcal{X}$ is an ellipsoid described by

$$ \mathcal{X} := \{x \in \mathbb{R}^d : \|x - c\|_{A^{-1}} \le 1\} $$

with vector $c \in \mathbb{R}^d$, positive definite matrix $A \in \mathbb{R}^{d \times d}$ and $\|u\|_M := \sqrt{u^\top M u}$ for $u \in \mathbb{R}^d$ is the norm associated to positive definite matrix $M$. After choosing action $x_t$ the learner observes a scalar reward $y_t = x_t^\top \theta + z_t$ where the vector $\theta \in \mathbb{R}^d$ is initially unknown to the learner, and $z_t \in \mathbb{R}$ is additive noise. Random variables $(z_t)_{t \in \mathbb{N}}$ are assumed independent, centered and subgaussian with variance proxy $\sigma^2$ so that conditionally on past observations

$$ \mathbb{E}(\exp(\lambda z_t)) \le \exp\left(\frac{\lambda^2 \sigma^2}{2}\right) \quad \text{for all } t \in \mathbb{N} \text{ and } \lambda \in \mathbb{R}. $$

<footnote>* The first two authors contributed equally to this work.</footnote>
The learner selects action $x_t$ solely based on the observed rewards up to time $t$, that is, $y_1, ..., y_{t-1}$. The goal of the learner is to minimize the (expected) regret

$$R_T(\theta) := \mathbb{E} \left[ \sum_{t=1}^{T} x^*(\theta)^\top \theta - x_t^\top \theta \right] \quad \text{where } x^*(\theta) \in \arg \max_{x \in \mathcal{X}} x^\top \theta$$

which is the expectation of the difference between the rewards obtained by the learner and the reward obtained by an oracle who knows $\theta$ and hence always select the decision with the largest expected reward. From the Karush-Kush-Tucker conditions, $A^{-1}(x^*(\theta) - c)$ should be proportional to $\theta$, so that the decision chosen by the oracle is $x^*(\theta) = c + A\theta/\|\theta\|_A$.

For two functions $f, g$ of $\phi = (T, \theta, \mathcal{X}, d, \sigma)$, we write $f(\phi) = O(g(\phi))$ and $f(\phi) = \Omega(g(\phi))$ if there exists $c_1, c_2$ strictly positive universal constants (not allowed to depend on any parameter such as $\phi$) such that $f(\phi) \le c_1 g(\phi)$ and $f(\phi) \ge c_2 g(\phi)$ respectively, for all $\phi$. We do not use the $\tilde{O}$ notation in which logarithmic terms are hidden, to avoid confusion.

## 1.2. Our contribution

We make two main contributions to this problem. First we derive a novel information-theoretic lower bound on the regret of any algorithm, stating that for any algorithm and any $B \ge 0$

$$\max_{\theta \in \mathcal{E}_A(B)} R_T(\theta) = \Omega \left( \min(BT, d\sigma\sqrt{T}) \right) \quad \text{with } \mathcal{E}_A(B) := \{ \theta \in \mathbb{R}^d : \|\theta\|_A = B \}.$$

In fact we prove an even stronger result showing that the same hold true when $\mathcal{E}_A(B)$ is replaced by a neighborhood of $\theta$ whose size vanishes with $T$. Second, we propose a novel algorithm called E2TC (Explore-Explore-Then-Commit) matching this upper bound so that under E2TC

$$\max_{\theta \in \mathcal{E}_A(B)} R_T(\theta) = O \left( \min(BT, d\sigma\sqrt{T} + dB) \right).$$

Algorithm E2TC has low computational complexity (time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$) so it can be applied to high dimensions, and is not based on optimism or sampling. Rather, it combines a non-trivial, adaptive initialization procedure to estimate the norm of $\theta$ followed by an Explore-Then-Commit (ETC) strategy. We emphasize that initially the learner has no information about the norm of $\theta$. In fact not only do our results show that E2TC is minimax optimal with low computational complexity, but they also show that E2TC is locally asymptotically minimax optimal, a much stronger notion of optimality than minimax optimality, further discussed next section.

## 1.3. Locally asymptotic minimax optimality

We use a refined notion of optimality called "locally asymptotic minimax optimality" proposed by Hájek (1972) for estimation. Denote by $R_T^A(\theta)$ the regret of algorithm A under parameter $\theta \in \mathbb{R}^d$ and let $\mathcal{P} \subset \mathbb{R}^d$ the set of allowed $\theta$. Algorithm A is minimax optimal if for any algorithm $A'$ there exists $\theta \in \mathcal{P}$ such that with $R_T^{A'}(\theta) = \Omega(\max_{\theta \in \mathcal{P}} R_T^A(\theta))$. Algorithm A is locally asymptotically minimax optimal if for any algorithm $A'$ there exists $\theta'_T$ such that $R_T^{A'}(\theta'_T) = \Omega(R_T^A(\theta))$ and $\lim_{T \to \infty} \theta'_T = \theta$. Local asymptotic minimax optimality, as illustrated in Figure 1, is stronger than minimax optimality.
<figure><img src="image_3.png" /><figcaption>Figure 1: Schematic illustration of the differences between minimax and locally asymptotically minimax lower bounds. Minimax lower bounds require that the regret curve of any algorithm goes above the bound at least once, whereas locally minimax lower bounds require that the curve of any algorithm goes above the bound in any region of size $\delta_T = o(1)$. In both figures, Algorithms 1 and 2 match the lower bound, and Algorithm 3 does not.</figcaption></figure>

Locally optimal algorithms perform well in the worst case, but also adapt to the information-theoretic "local difficulty" of the problem.

For instance when $\mathcal{X}$ is the unit ball, and the set of allowed $\theta$ is $\mathcal{P} = \{\theta \in \mathbb{R}^d : \|\theta\|_2 \le 1\}$ Lattimore and Szepesvári (2020) prove the minimax lower bound $\max_{\theta \in \mathcal{P}} R_T(\theta) = \Omega(d\sqrt{T})$, but their analysis only involves values of $\theta$ very close to 0. Our analysis paints a more complex picture, where the difficulty depends on $\|\theta\|_A$; locally minimax optimal algorithms like E2TC adapt to this.

## 1.4. Related Work

We now summarize the current state of the art on the problem of stochastic linear bandits with i.i.d. subgaussian rewards. For fair comparison, we first highlight the difference in assumptions made by authors, and whenever those assumptions differ from ours, we specialize their results to our setting.

**Different settings** Dani et al. (2008) consider an arbitrary action set $\mathcal{X}$ and assume that $\max_{x \in \mathcal{X}} |\theta^\top x| \le 1$, which in our setting is equivalent to $|c^\top \theta + \|\theta\|_A| \le 1$. Rusmevichientong and Tsitsiklis (2010) consider an arbitrary compact action set $\mathcal{X}$, but they assume intricate conditions on its curvature, see below. Abbasi-Yadkori et al. (2011) consider an arbitrary, possibly time-dependent, action set $\mathcal{X}_t$ and assume $\max_{x \in \mathcal{X}_t} |\theta^\top x| \le 1$, which in our setting is equivalent to $|c^\top \theta + \|\theta\|_A| \le 1$. They further assume that an upper bound for $\|\theta\|_2$ is known and provided as an input to the algorithm. Abeille and Lazaric (2017) consider an action set $\mathcal{X}$ which is an arbitrary closed subset of the unit ball, and also assume that an upper bound for $\|\theta\|_2$ is known and provided as an input to the algorithm.

**Regret upper bounds** The two versions of the CB (ConfidenceBall) algorithm of Dani et al. (2008) achieve regret upper bounds of $O(d\sqrt{T \log(T)^3})$ and $O(d^{3/2}\sqrt{T \log(T)^3})$ in our setting. The
**PEGE (Phased Exploration and Greedy Exploitation)** algorithm of Rusmevichientong and Tsitsiklis (2010) achieves a regret of $O((\|\theta\|_2 + 1/\|\theta\|_2)d\sqrt{T})$ when $\mathcal{X}$ is a unit ball. The **UE (Uncertainty Ellipsoid)** algorithm of Rusmevichientong and Tsitsiklis (2010) achieves a regret of $O(f(\mathcal{X})d\sqrt{T}\log(T)^3)$ when $\mathcal{X}$ is an ellipsoid where $f$ has an intricate dependency on the curvature of $\mathcal{X}$, and can only be bounded by a universal constant if the maximal ratio of eigenvalues of $A$, $|\lambda_{max}(A)/\sqrt{\lambda_{min}(A)}|$ is bounded by another universal constant, so that $\mathcal{X}$ is "close" to the unit ball. The **OFUL (Optimism in the Face of Uncertainty Linear bandit)** algorithm of Abbasi-Yadkori et al. (2011) achieves a regret $O((\|\theta\|_2 + \sigma\sqrt{d}\log(T))\sqrt{dT}\log(T))$ assuming that the algorithm is given an upper bound on $\|\theta\|_2$ as prior information in order to set the algorithm parameters correctly. The **TS (Thompson Sampling)** algorithm of Abeille and Lazaric (2017) achieves a regret of $O(\sigma d^{3/2}\sqrt{T}\log(dT)^3)$ assuming that the algorithm is given an upper bound on $\|\theta\|_2$ as prior information in order to set the algorithm parameters correctly. The **OLSOFUL (Ordinary Least Squares OFUL)** algorithm of Gales et al. (2022) achieves a regret of $O(\sigma d\sqrt{T}\log(T/d)^2 + \|\theta\|_2d\log(d))$ without prior information on $\theta$. Therefore, the two versions of CB, PEGE, UE, OFUL, OLSOFUL, TS are not provably minimax optimal, in contrast with E2TC.

**Regret lower bounds** Rusmevichientong and Tsitsiklis (2010) show that the minimax regret of any algorithm is at least $\Omega(d\sqrt{T})$ when the set of actions is the unit ball, using a Bayesian approach. Lattimore and Szepesvári (2020) show the same lower bound in a more general setting, using an Assouad-style construction. Our locally asymptotically minimax lower bound is a stronger result with the correct dependency on $d, \sigma, T$ and $\|\theta\|_A$.

**Computational complexity** To the best of our knowledge, even when $\mathcal{X}$ is a unit ball, none of the optimistic algorithms such as CB, UE, OFUL and OLSOFUL cannot be implemented in polynomial time, because they must repeatedly maximize the bilinear function $x^\top\theta$ over the couple $(x, \theta) \in \mathcal{X} \times C_t$ where $C_t$ is the confidence ellipsoid computed at time $t$. To the best of our knowledge, no efficient algorithm is known to solve this bilinear optimization problem when $\mathcal{X}$ is an ellipsoid. The only case in which this is feasible in polynomial time is when $\mathcal{X}$ is finite with polynomial size in $d$. This is corroborated by our numerical experiments. Both PEGE, TS can be implemented in polynomial time, as they require to minimize a linear function over $\mathcal{X}$, and/or to compute the least-squares estimate of $\theta$. Our results show that there is no regret/complexity trade-off in linear bandits, in the sense that E2TC achieves both minimax regret, and low computational complexity.

**Related problems** Other authors have considered different but related problems in linear bandits, for instance: Zhu and Nowak (2022) consider the case where $\theta$ is sparse, Banerjee et al. (2022) lower bound asymptotically the eigenvalues of the expected design matrix, Jun and Kim (2024) consider the case where the variance of the reward from the optimal decision is small, and Lattimore and Szepesvári (2020) consider the adversarial case (we refer the reader to their discussion of the major differences between stochastic and adversarial linear bandits).

## 2. Regret lower bound

Our first main result is an information-theoretic lower bound on the regret of any algorithm on ellipsoids, presented in Theorem 1. Our result is a locally asymptotically minimax lower bound (stronger than a minimax lower bound) indeed, since given any $\theta$, there must exist a $\theta'$ in the vicinity of $\theta$ on which regret is larger than the lower bound, with $\|\theta - \theta'\| \to 0$ when $T$ is large. The lower bound is a minimum of two terms, the first proportional to $d\sigma\sqrt{T}$, and the second to $T\|\theta\|_A$, which
depends on the norm of $\theta$. Those two terms identify two "regimes" depending on $\|\theta\|_A$, suggesting that the correct measure of problem complexity is $\|\theta\|_A$ which captures both the magnitude and the orientation of $\theta$, as well as the curvature of the action set $\mathcal{X}$.

Similarly to the minimax lower bound for the ball (Thm 24.2 in Lattimore and Szepesvári (2020)), our proof is built around an Assouad-like construction where we define $2^d$ alternative mean-reward vectors $\theta(\xi)$, with $\xi \in \{-1, +1\}^d$, and argue that no algorithm can have low regret on all such parameters. We show our stronger result by enforcing that the alternative vectors be in the vicinity of the given $\theta$, and of the same norm. This comes with technical difficulty, as we need to lower bound the regret of playing actions that are close to optimal. We also took extra care to exhibit clearly the different regimes involving $T$, $\sigma$, $B$ and $d$.

**Theorem 1** For any algorithm, any $B > 0$, any $T \ge 1$ and any $\theta \in \mathcal{E}_A(B) = \{\theta \in \mathbb{R}^{d+2}, \|\theta\|_A = B\}$ there exists a bandit problem with mean-rewards vector $\theta' \in \mathcal{E}_A(B)$ in a neighbourhood of $\theta$ such that $\|\theta - \theta'\|_A^2 \le \min(\sigma dB/\sqrt{T}, 4B^2)$ and :

$$R_T(\theta') \ge \min \left( \frac{\sigma d \sqrt{T}}{16}, \frac{BT}{4} \right).$$

**Proof** Let us set $B > 0$ and $\theta \in \mathbb{R}^{d+2}$ such that $\|\theta\|_A = B$, and fix any algorithm. We shall consider problems with gaussian rewards of variance $\sigma^2$ which are in particular subgaussian with proxy variance $\sigma^2$. For all $t$, define $w_t := A^{-1/2}(x_t - c)$, so that $x_t = A^{1/2}w_t + c$ and $w_t^\top w_t \le 1$. The expected reward of action $x_t$ is then $\theta^\top x_t = (A^{1/2}\theta)^\top w_t + \theta^\top c$ and the reward of the optimal action is $B + \theta^\top c$ with $B = \sqrt{\theta^\top A \theta}$. The difference between the two equals $B - (A^{1/2}\theta)^\top w_t$. We work with $(e_i)_{1 \le i \le d+2}$ an orthonormal basis of $\mathbb{R}^{d+2}$ such that $e_{d+1} \propto A^{-1/2}\theta$ and $\text{Span}(e_{d+1}, e_{d+2}) = \text{Span}(A^{-1/2}\theta, A^{-1/2}c)$. We also set $C := \min(1/2\sqrt{2}, B\sqrt{2T}/\sigma d)$ and $\varepsilon^2 := \min(1, d\sigma C/B\sqrt{2T})$. Given $\xi \in \{-1, +1\}^d$ consider the family of problems defined by the mean-reward vectors

$$\theta(\xi) := A^{-\frac{1}{2}}\phi(\xi) \text{ and } \phi(\xi) := B \left[ e_{d+1}\sqrt{1-\varepsilon^2} + \frac{\varepsilon}{\sqrt{d}} \sum_{i=1}^{d} \xi_i e_i \right].$$

Moreover, $\theta(\xi)^\top A \theta(\xi) = \phi(\xi)^\top \phi(\xi) = B^2$. By inspection, the regret at time step $t$ satisfies

$$B - (A^{\frac{1}{2}}\theta(\xi))^\top w_t = B - \phi(\xi)^\top w_t \stackrel{(1)}{=} \frac{B}{2} \left[ 1 - w_t^\top w_t + \left\| \frac{\phi(\xi)}{B} - w_t \right\|_2^2 \right] \\ \ge \frac{B}{2} \left\| \frac{\phi(\xi)}{B} - w_t \right\|_2^2 = \frac{B}{2} \left( (w_{t,d+1} - \sqrt{1-\varepsilon^2})^2 + \sum_{i=1}^d \left( w_{t,i} - \xi_i \frac{\varepsilon}{\sqrt{d}} \right)^2 + w_{t,d+2}^2 \right),$$

using the facts that (1) $-a^\top b = \frac{1}{2}(\|a - b\|^2 - a^\top a - b^\top b)$ and (2) $w_t^\top w_t \le 1$. Summing over $t$ we get a lower bound for the regret:

$$R_T(\theta) = \sum_{t=1}^{T} \left[ B - \phi(\xi)^\top w_t \right] \ge \frac{B}{2} \sum_{t=1}^{T} \left[ \left( w_{t,d+1} - \sqrt{1-\varepsilon^2} \right)^2 + \sum_{i=1}^{d} \left( w_{t,i} - \xi_i \frac{\varepsilon}{\sqrt{d}} \right)^2 + w_{t,d+2}^2 \right] \\ \ge \frac{B}{2} \sum_{i=1}^{d} \sum_{t=1}^{T} \left( w_{t,i} - \xi_i \frac{\varepsilon}{\sqrt{d}} \right)^2 \ge \frac{B}{2} \sum_{i=1}^{d} U_i(\xi_i) \quad \text{where}$$

$$\tau_i(T) := \min \left( \min \left\{ t : \sum_{s=1}^{t} w_{s,i}^2 \ge \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} \right\}, T \right) \text{ and } U_i(\xi) := \sum_{t=1}^{\tau_i(T)} \left( w_{t,i} - \xi_i \frac{\varepsilon}{\sqrt{d}} \right)^2.$$
This is upper bounded with probability 1 by:

$$U_i(\xi) \le 2 \sum_{t=1}^{\tau_i(T)} w_{ti}^2 + \frac{\varepsilon^2}{d} \le 2 \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right],$$

using the Cauchy-Schwarz inequality, $(a-b)^2 \le 2(a^2+b^2)$ and the definition of $\tau_i(T)$. For all $i \in [d]$ define $\xi^{(-i)}$ with coordinates $\xi_j^{(-i)} := (-1)^{1(i=j)}\xi_j$ and define $P_{\theta(\xi),i}$ the probability distribution of $(w_t)_{t \le \tau_i(T)}$ under parameter $\theta(\xi)$. From the choice of $\theta(\xi)$ we have

$$\begin{aligned} \theta(\xi)^{\top} x_t - \theta(\xi^{(-i)})^{\top} x_t &= (\phi(\xi) - \phi(\xi^{(-i)}))^{\top} w_t + (\theta(\xi) - \theta(\xi^{(-i)}))^{\top} c \\ &= (\phi(\xi) - \phi(\xi^{(-i)}))^{\top} w_t + 2 \frac{\varepsilon}{\sqrt{d}} e_i^{\top} A^{-\frac{1}{2}} c = (\phi(\xi) - \phi(\xi^{(-i)}))^{\top} w_t = \frac{2\varepsilon B}{\sqrt{d}} w_{t,i}, \end{aligned}$$

as $e_i^{\top} A^{-1/2} c = 0$ for all $i \le d$. By Lattimore and Szepesvári (2020)[Exercises 14.7 and 15.8], the relative entropy between the distributions of the observations in both problems bounded by

$$\begin{aligned} D(P_{\theta(\xi),i} | P_{\theta(\xi^{(-i)}),i}) &= \frac{1}{2\sigma^2} \mathbb{E} \left( \sum_{s=1}^{\tau_i(T)} \left( \theta(\xi)^{\top} x_t - \theta(\xi^{(-i)})^{\top} x_t \right)^2 \right) \\ &= \frac{1}{2\sigma^2} \mathbb{E} \left( \sum_{s=1}^{\tau_i(T)} \left( \phi(\xi)^{\top} w_t - \phi(\xi^{(-i)})^{\top} w_t \right)^2 \right) = \mathbb{E} \left( \sum_{s=1}^{\tau_i(T)} w_{si}^2 \right) \frac{2\varepsilon^2 B^2}{d\sigma^2} \le C^2. \end{aligned}$$

Then because $U_i(\xi)$ is a function of $(w_t)_{t \le \tau_i(T)}$ and is bounded by $2(\frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d})$, we can use a total variation and Pinsker's inequalities to get that:

$$\begin{aligned} \mathbb{E}_{\theta(\xi)}(U_i(\xi)) &\ge \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi)) - 2 \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right] \sqrt{\frac{1}{2} D(P_{\theta(\xi),i} | P_{\theta(\xi^{(-i)}),i})} \\ &\ge \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi)) - \sqrt{2} \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right] C. \end{aligned}$$

Adding on both sides and using the definition of $U$:

$$\begin{aligned} \mathbb{E}_{\theta(\xi)}(U_i(\xi)) + \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi^{(-i)})) &\ge \mathbb{E}_{\theta(\xi)}(U_i(\xi) + U_i(\xi^{(-i)})) - \sqrt{2} \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right] C \\ &= 2\mathbb{E}_{\theta(\xi)} \left( \sum_{t=1}^{\tau_i(T)} \frac{\varepsilon^2}{d} + w_{ti}^2 \right) - \sqrt{2} \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right] C. \end{aligned}$$

Either $\tau_i(T) = T$ so $\sum_{t=1}^{\tau_i(T)} \frac{\varepsilon^2}{d} = \frac{T\varepsilon^2}{d}$, or $\tau_i(T) < T$ and then $\sum_{t=1}^{\tau_i(T)} w_{ti}^2 \ge \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2}$. Therefore

$$\mathbb{E}_{\theta(\xi)}(U_i(\xi)) + \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi^{(-i)})) \ge \min \left( 2T \frac{\varepsilon^2}{d}, \frac{2d\sigma^2 C^2}{2\varepsilon^2 B^2} \right) - \sqrt{2} \left[ \frac{d\sigma^2 C^2}{2\varepsilon^2 B^2} + \frac{T\varepsilon^2}{d} \right] C.$$

If $d < 4B\sqrt{T}/\sigma$, then $C = 2\sqrt{2}/2$ and $\varepsilon^2 = d\sigma/(4B\sqrt{T}) < 1$ so

$$\mathbb{E}_{\theta(\xi)}(U_i(\xi)) + \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi^{(-i)})) \ge \frac{\sigma\sqrt{T}}{4B}.$$
If $d \ge 4B\sqrt{T}/\sigma$, then $C = \sqrt{2TB}/(\sigma d)$ and $\varepsilon^2 = 1$. So $2T/d \le d\sigma^2C^2/B^2$ and

$$ \mathbb{E}_{\theta(\xi)}(U_i(\xi)) + \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi^{(-i)})) \ge \frac{2T}{d} - \sqrt{2\frac{d\sigma^2C^3}{2B^2}} \ge \frac{2T}{d} - \sqrt{2\frac{(2T)^{3/2}B}{2\sigma d^2}} \ge \frac{T}{d}. $$

Putting both cases together and summing the regret over $\xi$:

$$ \sum_{\xi \in \{-1, +1\}^d} \mathbb{E}_{\theta(\xi)}(R_T(\theta)) \ge \frac{B}{2} \sum_{\xi \in \{-1, +1\}^d} \sum_{i=1}^d \mathbb{E}_{\theta(\xi)}(U_i(\xi)) \\ \ge \frac{B}{4} \sum_{i=1}^d \sum_{\xi \in \{-1, +1\}^d} \mathbb{E}_{\theta(\xi)}(U_i(\xi)) + \mathbb{E}_{\theta(\xi^{(-i)})}(U_i(\xi^{(-i)})) \ge 2^d \min \left( \frac{\sigma d \sqrt{T}}{16}, \frac{TB}{4} \right). $$

We conclude the proof by saying that there must exist at least a $\xi$ such that

$$ \mathbb{E}_{\theta(\xi)}(R_T(\theta)) \ge \min \left( \frac{\sigma d \sqrt{T}}{16}, \frac{TB}{4} \right) \quad \blacksquare $$

To complete the picture, we also show that there is a minimal regret of $\Omega(d\|\theta\|_A)$ as soon as $T \ge d$. While this seems intuitively straightforward, as the learner should have no choice but to explore all dimensions at least once, the proof (in Appendix C) requires some technical work.

**Proposition 2** For any algorithm, for any $B > 0$, if $T \ge d$, there exists a noiseless bandit problem, with mean-rewards parameter $\theta \in \mathbb{R}^d$, such that $\|\theta\|_A \le 4B$ and

$$ R_T(\theta) \ge 0.017 d \|\theta\|_A. $$

### 3. The E2TC algorithm

We now describe the E2TC algorithm and prove its optimality. We first describe the algorithm and bound its regret when $\mathcal{X}$ is a centered ellipsoid i.e., $c = 0$, and then extend our results to $c \ne 0$ using a reduction. To ease notation, we define $\log(x) := 1 + \log(\max(x, 1))$, $(a)^- := \min(a, 0)$, and given a set of instants $T \subset \mathbb{N}$, we define vectors $Y_T := (y_t)_{t \in T} \in \mathbb{R}^{|T|}$ and $Z_T := (z_t)_{t \in T} \in \mathbb{R}^{|T|}$ and matrix $X_T := (x_t)_{t \in T} \in \mathbb{R}^{|T| \times d}$ so that $Y_T = X_T\theta + Z_T$. When $X_T$ has full rank we define $LS(X_T, Y_T) = (X_T^\top X_T)^{-1} X_T Y_T$ the (unregularized) ordinary least-squares estimate of $\theta$ when using only observations at times $t \in T$. For $i \in \mathbb{N}$ we define $n_i = d2^{i-1}$, $T_i = d(2^i - 1)$ and $\delta_i = \min(dn_i/T, 1)$.

#### 3.1. Algorithm description

Consider the centered case $c = 0$. The pseudocode of E2TC is presented as Algorithm 1 and is composed of three phases, whose names are inspired by the "explore-then-commit" strategy of Garivier et al. (2016). The main addition is the first phase that allows to determine how many exploration rounds are necessary, as those must depend on $\|\theta\|_A$, as shown by our analysis.

**Phase 1:** ("warmup phase", lines 1-5): We sample actions in $(A^{1/2}e_j)_{j \in [d]}$ in a round-robin fashion. At times $t \in (T_i)_{i \in \mathbb{N}}$ with we compute $\hat{\theta}_i := \text{LS}(X_i, Y_i)$ the least-squares estimate of $\theta$
using the observations during time interval $[T_i, T_{i+1} - 1]$ and if $\|\hat{\theta}_i\|_A$ exceeds a threshold equal to $\alpha U(\delta_i, n_i)$ where $\alpha \in \mathbb{R}^+$ is a positive parameter of the algorithm and with

$$U(\delta_i, n_i)^2 = \frac{\sigma^2 d^2}{n_i} \left( 1 + 2\sqrt{\frac{1}{d} \log \frac{1}{\delta_i} + \frac{2}{d} \log \frac{1}{\delta_i}} \right). \quad (1)$$

We exit this phase that we number $\hat{i}$, otherwise we keep going. When exiting, we compute $\hat{B} := \|\hat{\theta}_i\|_A$ the norm estimate. The threshold $U$ is designed to estimate the magnitude of $\theta$ correctly, so that with high probability $c_1 \|\theta\|_A \le \hat{B} \le c_2 \|\theta\|_A$, with $c_1, c_2$ well-chosen universal constants.

**Phase 2:** ("exploration phase", lines 6-9): We sample actions in $(A^{1/2}e_j)_{j \in [d]}$ in a round-robin fashion during an amount of time $N_e := d\sigma[\sqrt{T}/\hat{B}]$. The goal of this phase is simply to gather enough samples to estimate $\theta$ accurately, to be able to find a good action by the end of the phase with high probability. The analysis shows that the number of samples needs to depend on $\|\theta\|_A$, which is why we use the estimate $\hat{B}$ from the previous phase.

**Phase 3:** ("commit phase", lines 10-12): We compute $\hat{\theta} := \text{LS}(X, Y)$ the least-squares estimate of $\theta$ using the past observations gathered during phase 2, and play greedily by selecting decision arg $\max_{x \in \mathcal{X}} x^\top \hat{\theta}$ until the time horizon runs out. The goal of this phase is simply to maximize reward, as we are certain that enough samples have been gathered and this decision should be close to the optimal one $x^*(\theta)$ with high probability.

**Algorithm 1:** E2TC (Explore-Explore-Then-Commit)

**Input:** Ellipsoid matrix $A$, noise level $\sigma$, time horizon $T$, parameter $\alpha \ge 0$.

**Init:** $i = 0$.

1. **while** warm-up **do**

2. **for** $t = T_i$ to $T_{i+1} - 1$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;**Play** $x_t = A^{1/2}e_{(t \bmod d)+1}$. Receive $y_t$.

4. &nbsp;&nbsp;&nbsp;&nbsp;Set $X_i = x_{[T_i, T_{i+1}-1]}$ and $Y_i = y_{[T_i, T_{i+1}-1]}$. Set $\hat{\theta}_i = \text{LS}(X_i, Y_i)$. Update $i \leftarrow i + 1$.

5. &nbsp;&nbsp;&nbsp;&nbsp;Exit warm-up if $\|\hat{\theta}_i\|_A > \alpha U(\delta_i, n_i)$, defined in (1).

6. Set $\hat{B} = \|\hat{\theta}_i\|_A$ and $N_e = d\sigma[\sqrt{T}/\hat{B}]$.

7. **for** $t = T_i$ to $T_i + N_e - 1$ **do**

8. &nbsp;&nbsp;&nbsp;&nbsp;**Play** $x_t = A^{1/2}e_{(t \bmod d)+1}$. Receive $y_t$.

9. Set $X = x_{[T_i, T_i + N_e - 1]}$ and $Y = y_{[T_i, T_i + N_e - 1]}$.

10. Set $\hat{\theta} = \text{LS}(X, Y)$.

11. **for** $t = T_i + N_e(\hat{B})$ **to** $T$ **do**

12. &nbsp;&nbsp;&nbsp;&nbsp;**Play** $x_t = x^*(\hat{\theta})$. Receive $y_t$.

**Remark 3 (Computational complexity)** A run of E2TC takes time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, since it involves at most $\log_2(T/d) + 1$ least-squares estimates of $\theta$, and all those estimations require inverting $d \times d$ matrices which are all proportional to $A$, so it suffices to invert $A$ once.
## 3.2. Regret upper bound

We now upper bound the regret of E2TC, in the centered case $c = 0$. We present the main elements of analysis here, and present complete proofs in appendix.

**Regret of phases 2 and 3** Assume that phase 1 was successful. Denote by $\mathbb{E}_{\text{expl}}$ the expectation conditionally on all rounds before phase 3. The regret caused by a round of phase 2 is at most $2\|\theta\|_A$ by the Cauchy-Schwarz inequality. The regret caused by a round of phase 3 is $\theta(x^*(\theta) - x^*(\hat{\theta}))$ we always select the same action. The regret caused by phases 2 and 3 is hence upper bounded by

$$2N_e\|\theta\|_A + T \mathbb{E}_{\text{expl}}[\theta^\top(x^*(\theta) - x^*(\hat{\theta}))].$$

We note that, during phases 1 and 2, we play uniformly along the axes of the ellipsoid, which ensures that the design matrix $X^\top X$ stays proportional to $A$ (after a number of exploration rounds multiple of $d$, which is always the case at the end of exploration in our algorithm).

As observed by Rusmevichientong and Tsitsiklis (2010), when the action set has positive curvature, the commit error scales quadratically with the mean-squared error of estimation (see Lemma 10 in Appendix A), which itself scales with $1/N_e$; this is crucial to ensure that the regret grows proportionally to $\sqrt{T}$.

**Lemma 4** Let $\hat{\theta}$ the least-squares estimator after $N_e$ rounds of exploration, then conditionally on the exploration rounds,

$$\mathbb{E}_{\text{expl}}[\theta^\top(x^*(\theta) - x^*(\hat{\theta}))] \le \frac{d^2\sigma^2}{\|\theta\|_A N_e} + 2\|\theta\|_A e^{(2d/3 - N_e\|\theta\|^2/(3\sigma^2d))^{-}}.$$

See Appendix A.1 for a proof. The regret incurred by phases 2 and 3 is hence upper bounded as

$$2N_e\|\theta\|_A + T \frac{d^2\sigma^2}{\|\theta\|_A N_e} + T \left( \frac{d^2\sigma^2}{\|\theta\|_A N_e} + 2\|\theta\|_A e^{(2d/3 - N_e\|\theta\|^2/(3\sigma^2d))^{-}} \right).$$

Our analysis therefore suggests selecting $N_e \approx \sigma d \sqrt{T}/\|\theta\|_A$ to balance the first two terms in the right-hand side. Doing this would yield a regret upper bound of $O(d\sqrt{T})$ which is the correct minimax rate. Of course, since $\|\theta\|_A$ is initially unknown, we must estimate it during phase 1.

**Regret of phase 1** Lemma 5 shows that the regret caused by phase 1 is small enough to ensure minimax optimality, and that the value of $\hat{B}$ output at the end of phase 1 is a good enough estimate of $\|\theta\|_A$ with high probability. This lemma also justifies the choice of the stopping criterion for phase 1.

**Lemma 5 (Regret of Phase 1)** Set $\alpha = 3$ and let $\hat{B}$ be the output of phase 1. We have

$$\mathbb{P}[\hat{B} \notin [(1/2)\|\theta\|_A, (3/2)\|\theta\|_A]] \le \frac{164 \sigma^2 d^2}{T \|\theta\|_A^2} \log \left( \frac{T \|\theta\|_A^2}{d^2 \sigma^2} \right) + 48 \frac{d}{T},$$

and the expected length of phase 1 is at most

$$\mathbb{E}[N_{\text{warm-up}}] \le \frac{164 \sigma^2 d^2}{\|\theta\|_A^2} \log \left( \frac{T \|\theta\|_A^2}{\sigma^2 d^2} \right) + 48d.$$
**On the design of phase 1** The threshold $U(\delta_i, n_i)$ is chosen such that the probability of stopping too early at time $T_i$ is less than $\delta_i$. So $U(\delta_i, n_i)$ and $\delta_i$ can be interpreted as an upper confidence bound, and a failure probability respectively. The exploration design is chosen so that $X_i^\top X_i = (n_i/d)A$ after a phase of length $n_i$, which guarantees at the end of subphase $i$ of the warm-up, the probability of failure is less than $\delta_i$:

$$ \mathbb{P}[\|\hat{\theta}_i - \theta\|_A^2 \ge U(n_i, \delta_i)] \le \delta_i. $$

Interestingly, our analysis shows that $\delta_i$ must (counterintuitively) be an increasing function of $i$ to yield a minimax optimal algorithm. The cornerstone of both the design of phase 1 and its analysis is a concentration inequality for least-squares regression, by Hsu et al. (2011), which is an extension of the tail bounds for chi-squared variables by Laurent and Massart (2000) to sub-gaussian noise.

**Lemma 6 (Concentration of error in linear regression)** In linear regression with $Y = X\theta + Z$ and $\hat{\theta} = LS(X, Y)$, assume that all entries of $Z$ are $\sigma^2$-subgaussian and independent, and that $X$ is full rank. Then for all $x \ge 0$

$$ \mathbb{P}[\|\hat{\theta} - \theta\|_{X^\top X}^2 \ge \sigma^2(d + 2\sqrt{dx} + 2x)] \le e^{-x}. $$

Putting the three phases together, we can now state the regret upper bound of E2TC in Theorem 7, and the detailed proof is presented in appendix. Corollary 8 shows that the regret upper bound matches our regret lower bound of Theorem 1 up to a universal multiplicative constant, so that E2TC is locally asymptotically minimax optimal as announced.

**Theorem 7** Consider $\mathcal{X} = \{x \in \mathbb{R}^d : \|x\|_{A^{-1}} \le 1\}$ a centered ellipsoid. The regret of E2TC tuned with $\alpha = 3$ admits the upper bound for any $\theta \in \mathbb{R}^d$ and any $T \ge 0$:

$$ R_T(\theta) \le 6d\sigma\sqrt{T} + \frac{984\sigma^2 d^2}{\|\theta\|_A} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) + 290 d\|\theta\|_A + 2T\|\theta\|_A e^{(2d/3 - (2/9)\sqrt{T}\|\theta\|_A/\sigma)^{-1}}. $$

**Corollary 8** E2TC is locally asymptotically minimax optimal: for any $\theta \in \mathbb{R}^d$,

$$ R_T(\theta) = \mathcal{O}\left(\min\left(\sigma d\sqrt{T} + d\|\theta\|_A, T\|\theta\|_A\right)\right). $$

**Proof of Corollary 8** We proceed by considering multiple cases, depending on the value of $T$. If $T \le 36d^2\sigma^2/\|\theta\|_A^2$, then $2T\|\theta\|_A \le 12\sigma d\sqrt{T}$. So by the Cauchy-Schwarz bound, the regret is less than $R_T(\theta) \le \min(2T\|\theta\|_A, 12\sigma d\sqrt{T})$. Otherwise,

$$ 2d/3 - (2/9)\sqrt{T}\|\theta\|_A/\sigma \le -(1/9)\sqrt{T}\|\theta\|_A/\sigma, $$

and the final term in the regret bound is upper bounded by

$$ \begin{aligned} T\|\theta\|_A e^{(2d/3 - (2/9)\sqrt{T}\|\theta\|_A/\sigma)^{-1}} &\le T\|\theta\|_A e^{-(1/9)\sqrt{T}\|\theta\|_A/\sigma} = \sigma\sqrt{T} \left(\frac{\sqrt{T}\|\theta\|_A}{\sigma} e^{-(1/9)\sqrt{T}\|\theta\|_A/\sigma}\right) \\ &\le 9\sigma\sqrt{T} \sup_{X \ge 2d/3} (Xe^{-X}) \le 6e^{-2d/3} \sigma d\sqrt{T}. \end{aligned} $$

Similarly, for the first logarithmic term,

$$ \frac{\sigma^2 d^2}{\|\theta\|_A} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) \le \sigma d\sqrt{T} \frac{\sigma d}{\|\theta\|_A \sqrt{T}} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) \le \sigma d\sqrt{T} \sup_{X \ge 1/6} \frac{1}{X} \log(X^2) = 6\sigma d\sqrt{T}. $$

Therefore, the total bound is at most $O(d\sigma\sqrt{T} + d\|\theta\|)$ as announced. ■
### 3.3. Non-centered Action Sets

Now consider the general, non-centered case $c \neq 0$. In Appendix B, we describe a general procedure to extend E2TC (and any other algorithm with similar structure) designed for the centered case to the non-centered case. Theorem 9 shows that E2TC is also locally asymptotically minimax optimal in the non-centered case; it is a direct consequence of Theorem 13 in Appendix B

**Theorem 9** Consider $\mathcal{X} = \{x \in \mathbb{R}^d : \|x - c\|_{A^{-1}} \le 1\}$ an arbitrary ellipsoid. Set $\alpha = 3$. The regret of E2TC with Reduction 2 admits the upper bound for any $\theta \in \mathbb{R}^d$ and any $T \ge 0$:

$$R_T(\theta) \le 7d\sigma\sqrt{T} + \frac{2622 \sigma^2 d^2}{\|\theta\|_A} \log\left(\frac{T\|\theta\|_A^2}{4\sigma^2 d^2}\right) + 2T\|\theta\|_A e^{(2d/3 - (1/9)\sqrt{T}\|\theta\|_A/\sigma)^{-1}} + 392 d\|\theta\|_A.$$

### 4. Numerical Experiments

We now compare E2TC to state-of-the-art algorithms OFUL and OLSOFUL using numerical experiments. Regret of algorithms is averaged over 20 independent runs, and both averages and confidence intervals are presented. The source code for those numerical experiments will be released publicly after review. We denote by E2TC($\alpha$) the E2TC algorithm with parameter $\alpha$, and we consider both E2TC(1) and E2TC(3). We consider action set $\mathcal{X}$ as the unit ball and a time horizon of $T = 10^4$. The confidence ellipsoids in OFUL and OLSOFUL require a confidence parameter $\delta$, which can be interpreted as a probability of failure, and we set it to $\delta = 1/T$, to ensure that the regret caused by failure does not scale linearly in $T$.

We use a commercially available optimization solver Gurobi Optimization, LLC (2024) to handle the bilinear maximization problem $\max_{(x, \theta)} x^\top \theta$ subject to $(x, \theta) \in \mathcal{X} \times C_t$ with $C_t$ the confidence ellipsoid at time $t$, which must be solved at each step to implement OFUL and OLSOFUL. We limit Gurobi's available time to 1 second per time step, which already amounts to 2.7 hours per run, that is 2.5 days to average the regret over 20 independent runs. Gurobi is allowed to use all 20 cores of an i9-129000H processor, and outputs the best solution found within the allotted time, with an early stop if the estimated relative gap to optimality is less than 1%.

**Regret $R_T(\theta)$ vs norm of $\theta$** We compare in Figure 2 the final regret of the algorithms for different values of $\|\theta\|_2$ chosen as $\|\theta\|_2 \in \{d/\sqrt{T}, 0.1, 1, 10, 25, 50\}$. OFUL requires an input parameter $S$ which should be an upper bound for $\|\theta\|$. We set $S$ as half the range norms so that $S = 25$. Due to the enormous computation complexity of optimistic algorithms, we limit ourselves to a small dimension $d = 3$: a larger dimension would already require over a week of computation to generate meaningful results.

**Regret $R_T(\theta)$ vs dimension $d$** We compare in Figure 3 the final regret of the algorithms for different values of $d$, and we choose $\theta$ with a fixed norm $\|\theta\|_2 = 10$. We consider dimensions $2 \le d \le 90$. We could not make the optimistic algorithms work in reasonable time for $d > 4$, so for high dimensions, solely E2TC is presented. As suggested by our theoretical results, the regret of E2TC seems to scale linearly with the dimension.

**Runtime** We compare the runtime (CPU time) of E2TC and OFUL for different norms $\|\theta\|$, where dimension is $d = 3$ in Fig.4(a) and for different dimensions $d$ and fixed norm 10 in Fig.4(b). Runtime includes the time to compute the action to be played, the time used to solve the bilinear optimization problem, and the time to update the estimated parameters $\hat{\theta}_t$ using the Sherman Morrison algorithm for the inversion of the design matrix. We present the ratio between the runtime of OFUL and that of E2TC, and observe that OFUL is slower by about 5 orders of magnitude, an enormous
<figure><img src="image_4.png" /><figcaption>Figure 2: Comparison of the final regret of E2TC, OFUL and OLSOFUL for different norms.</figcaption></figure>

difference. This clearly illustrates the lower computational complexity of E2TC with respect to optimistic algorithms. Also, for small norms in dimension 3 and for dimension greater than 4, it is harder for Gurobi to find a good solution, and it maxes out its allotted time.

<figure><img src="image_5.png" /><figcaption>Figure 3: Final regret of E2TC, OFUL and OLSOFUL as a function of the dimension *d*.</figcaption></figure>

<table><tr><td>||θ||</td><td>0.1</td><td>1</td><td>10</td><td>50</td></tr><tr><td>Runtime Ratio</td><td>6.1 × 10<sup>4</sup></td><td>1.0 × 10<sup>5</sup></td><td>1.7 × 10<sup>5</sup></td><td>8.7 × 10<sup>4</sup></td></tr></table>

(a) Norm runtime comparison

<table><tr><td>d</td><td>2</td><td>3</td><td>4</td></tr><tr><td>Runtime Ratio</td><td>1.2 × 10<sup>4</sup></td><td>1.7 × 10<sup>5</sup></td><td>6.7 × 10<sup>5</sup></td></tr></table>

(b) Dimension runtime comparison

<caption>Figure 4: Runtime comparison of E2TC and OFUL for different norms and dimensions.</caption>

## 5. Conclusion

We have proposed the first known provably minimax optimal algorithm for linear stochastic bandits over ellipsoids called E2TC. We derived a new information-theoretic lower bound on the regret of
any algorithm equal to $\Omega(\min(d\sigma\sqrt{T}, \|\theta\|_A T))$, and showed that the regret of E2TC matches this bound so that it is minimax optimal. The E2TC algorithm is locally asymptotically minimax optimal, a stronger optimality notion than classical minimax optimality. Also E2TC is highly computationally efficient, requiring time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, unlike optimistic algorithms for which, to the best of our knowledge, no polynomial time implementation exists, even when the action set is a unit ball. Numerical experiments confirm our theoretical findings both in terms of regret as well as running time. An interesting direction for future research is whether or not the general structure of E2TC can be adapted to solve other structured bandit problems.

## Acknowledgements

This paper is supported by the CHIST-ERA Wireless AI 2022 call MLDR project (ANR-23-CHR4-0005), partially funded by AEI and NCN under projects PCI2023-145958-2 and 2023/05/Y/ST7/00004, respectively.

## References

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. *Advances in neural information processing systems*, 24, 2011.

Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In *Proceedings of the 20th International Conference on Artificial Intelligence and Statistics*, volume 54 of *Proceedings of Machine Learning Research*, pages 176–184. PMLR, 20–22 Apr 2017.

Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. *arXiv preprint arXiv:2207.11597*, 2022.

Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic Linear Optimization under Bandit Feedback. In *Conference on Learning Theory*, 2008.

Spencer B Gales, Sunder Sethuraman, and Kwang-Sung Jun. Norm-agnostic linear bandits. In *International Conference on Artificial Intelligence and Statistics*, pages 73–91. PMLR, 2022.

Aurelien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commit strategies. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 29. Curran Associates, Inc., 2016.

Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www.gurobi.com.

Jaroslav Hájek. Local asymptotic minimax and admissibility in estimation. In *Proceedings of the sixth Berkeley symposium on mathematical statistics and probability*, volume 1, pages 175–194, 1972.

Peter D Hoff. *A first course in Bayesian statistical methods*, volume 580. Springer, 2009.

Daniel Hsu, Sham M. Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors, October 2011. arXiv:1110.2842.
Kwang-Sung Jun and Jungtaek Kim. Noise-adaptive confidence sets for linear bandits and application to bayesian optimization. *arXiv preprint arXiv:2402.07341*, 2024.

Tor Lattimore and Csaba Szepesvári. *Bandit Algorithms*. Cambridge University Press, 1 edition, July 2020. ISBN 978-1-108-57140-1 978-1-108-48682-8. doi: 10.1017/9781108571401.

B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. *The Annals of Statistics*, 28(5):1302–1338, 2000. doi: 10.1214/aos/1015957395.

Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. *Mathematics of Operations Research*, 35(2):395–411, 2010. ISSN 0364765X, 15265471.

Yinglun Zhu and Robert Nowak. Pareto optimal model selection in linear bandits. In *International Conference on Artificial Intelligence and Statistics*, pages 6793–6813. PMLR, 2022.
# Appendix A. Proofs for Section 3

## A.1. Proof of Theorem 7

**Proof** We use the natural template for the analysis of Explore-Then-Commit (ETC) algorithms. The first step is to use the Cauchy-Schwarz inequality to bound the instantaneous regret $\theta^\top(x^*(\theta) - x_t) \le 2\|\theta\|_A$ on all the exploration rounds:

$$R_T(\theta) \le 2\|\theta\|_A \mathbb{E}[N_{\text{warm-up}} + N_e(\hat{B})] + T \mathbb{E}[\theta^\top(x^*(\theta) - x^*(\hat{\theta}))].$$

We shall then control separately the expected total number of exploration rounds,

$$\mathbb{E}[N_{\text{warm-up}} + N_e(\hat{B})] \le \frac{2d\sigma\sqrt{T}}{\|\theta\|_A} + \frac{328 \sigma^2 d^2}{\|\theta\|_A^2} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) + 97d, \quad (2)$$

and the expected cost of the commit rounds,

$$\mathbb{E}[\theta^\top(x^*(\theta) - x^*(\hat{\theta}))] \le \frac{3d\sigma}{2\sqrt{T}} + 2\|\theta\|_A e^{(2d/3 - (2/9)\sqrt{T}\|\theta\|_A/\sigma)^{-}} + \frac{328 \sigma^2 d^2}{T\|\theta\|_A} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) + 96 \frac{d\|\theta\|_A}{T}. \quad (3)$$

The three bounds combined yield the claimed result. The first step in the proof of both of these bounds is to control the warm-up behavior. This is done via Lemma 5 stated above and proved below. It then suffices to analyze the algorithm on the event that the warm-up was successful. We thus define the corresponding good event $\mathcal{G}$ as

$$\mathcal{G} = \left\{ \frac{\|\theta\|_A}{2} \le \hat{B} \le \frac{3\|\theta\|_A}{2} \right\}.$$

**Exploration rounds** On the good event $\mathcal{G}$, the estimate $\hat{B}$ is at least $\|\theta\|/2$, so

$$N_e(\hat{B}) \mathbb{1}\{\mathcal{G}\} = d\left[\frac{\sigma\sqrt{T}}{\hat{B}}\right] \mathbb{1}\{\mathcal{G}\} \le d\left[\frac{2\sigma\sqrt{T}}{\|\theta\|_A}\right] \le d\frac{2\sigma\sqrt{T}}{\|\theta\|_A} + d.$$

And therefore, by Lemma 5, in expectation, bounding $N_e(\hat{B})$ by the worst-case $T$ on $\bar{\mathcal{G}}$,

$$\mathbb{E}[N_e(\hat{B})] \le d \frac{2\sigma\sqrt{T}}{\|\theta\|_A} + d + T \mathbb{P}[\bar{\mathcal{G}}] \le d \frac{2\sigma\sqrt{T}}{\|\theta\|_A} + d + \frac{164 \sigma^2 d^2}{\|\theta\|_A^2} \log\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right) + 48d.$$

**Commit error** We isolate the guarantees for the least-squares estimator in Lemma 4, which we restate and prove below. Given this lemma, by the tower rule, and since $\mathcal{G}$ only depends on the exploration rounds (thus is measurable with respect to the $\sigma$-algebra generated by actions and observations in the exploration rounds),

$$\mathbb{E}[\theta^\top(x^*(\theta) - x^*(u)) \mathbb{1}\{\mathcal{G}\}] = \mathbb{E}[\mathbb{E}_{\text{expl}}[\theta^\top(x^*(\theta) - x^*(u)) \mathbb{1}\{\mathcal{G}\}]] \\ \le \mathbb{E}\left[\left(\frac{d^2\sigma^2}{\|\theta\|_A N_e} + 2\|\theta\|_A e^{(2d/3 - N_e \|\theta\|^2/(3\sigma^2 d))}\right) \mathbb{1}\{\mathcal{G}\}\right] \le \frac{3d\sigma}{2\sqrt{T}} + 2\|\theta\|_A e^{(2d/3 - (2/9)\sqrt{T}\|\theta\|_A/\sigma)^{-}}.$$

where we used the fact that $\hat{B} \le 3\|\theta\|_A/2$ on the event $\mathcal{G}$, and thus that $N_e \ge d\sigma\sqrt{T}/(3\|\theta\|_A/2)$

$$\mathbb{E}[\theta^\top(x^*(\theta) - x^*(u))] \le \mathbb{E}[\theta^\top(x^*(\theta) - x^*(u)) \mathbb{1}\{\mathcal{G}\}] + 2\|\theta\|_A \mathbb{P}[\bar{\mathcal{G}}].$$

The claimed bound follows by applying the previously shown inequalities. ■
**Lemma 4** If $\hat{\theta}$ is the least-squares estimator after $N_e$ rounds of exploration, then conditionally on the exploration rounds,

$$ \mathbb{E}_{\text{expl}}[\theta^{\top}(x^{*}(\theta) - x^{*}(\hat{\theta}))] \le \frac{d^2\sigma^2}{\|\theta\|_A N_e} + 2\|\theta\|_A e^{(2d/3 - N_e\|\theta\|^2/(3\sigma^2d))^{-}}. $$

**Proof** To ease notation, we remove the subscript on $\mathbb{E}_{\text{expl}}$ inside this proof; all expectations and probability are taken conditionally on the randomness of the exploration rounds. At the end of the exploration phase, consider the matrices $Y \in \mathbb{R}^{N_e}$, and $X \in \mathbb{R}^{N_e \times d}$, defined by stacking the exploratory actions and responses so that

$$ Y = X\theta + Z \quad \text{and} \quad \hat{\theta} = (X^{\top}X)^{-1}X^{\top}Y. $$

Let us start by evacuating very bad cases, in which the estimator is completely off. Depending on whether $\theta^{\top}A\hat{\theta} \le 0$, we upper bound the instantaneous regret by either $2\|\theta\|_A$, or using Lemma 10,

$$ \begin{aligned} \mathbb{E}[\theta^{\top}(x^{*}(\theta) - x^{*}(\hat{\theta}))] &\le 2\|\theta\|_A \mathbb{P}[\theta^{\top}A\hat{\theta} \le 0] + \frac{1}{\|\theta\|_A} \mathbb{E}[\|\theta - \hat{\theta}\|_A^2] \\ &\le 2\|\theta\|_A \mathbb{P}[\|\hat{\theta} - \theta\|_A \ge \|\theta\|_A] + \frac{1}{\|\theta\|_A} \mathbb{E}[\|\theta - \hat{\theta}\|_A^2]. \end{aligned} \quad (4) $$

The second term is essentially the mean-squared error of the least-squares estimator

$$ \mathbb{E}[\|\theta - \hat{\theta}\|_A^2] = \mathbb{E}[\|(X^{\top}X)^{-1}X^{\top}Z\|_A^2] = \mathbb{E}[\|A^{1/2}(X^{\top}X)^{-1}X^{\top}Z\|^2] $$

Now note that for any matrix $M \in \mathbb{R}^{N_e \times d}$, since the covariance matrix of $Z$ is diagonal with entries in $[0, \sigma^2]$, we have

$$ \mathbb{E}[\|MZ\|^2] = \mathbb{E}[\text{Tr}(ZZ^{\top}M^{\top}M)] = \sum_{t \in \mathcal{T}_{\text{expl}}} \mathbb{E}[z_t^2](M^{\top}M)_{t,t} \le \sigma^2 \text{Tr}(M^{\top}M). $$

In particular, taking $M = A^{1/2}(X^{\top}X)^{-1}X^{\top}$,

$$ \mathbb{E}[\|A(X^{\top}X)^{-1}X^{\top}Z\|^2] \le \sigma^2 \text{Tr}(A(X^{\top}X)^{-1}) = \frac{d^2\sigma^2}{N_e}, $$

where we used the fact that $X^{\top}X = (N_e/d)A$ to obtain the final equality.

To treat the first term in (4), we use again the sub-gaussian concentration, Lemma 6, to obtain

$$ \mathbb{P}[\|\hat{\theta} - \theta\|_A \ge \|\theta\|_A] \le e^{2d/3 - N_e \|\theta\|^2/(3\sigma^2d)}. \quad (5) $$

To see this, note that for any $x \ge 0$, applying the inequality $2\sqrt{xd} \le x + d$, we have

$$ \frac{\sigma^2 d}{N_e} (d + 2\sqrt{xd} + 2x) \le \frac{\sigma^2 d}{N_e} (2d + 3x). $$

Then consider $x = N_e\|\theta\|_A^2/(3d\sigma^2) - 2d/3$, so that $\frac{\sigma^2 d}{N_e}(2d + 3x) = \|\theta\|_A^2$. If $x \le 0$, then the claim (5) holds trivially as a probability is less than 1. Otherwise, we apply subgaussian concentration (Lemma 6) to get

$$ \begin{aligned} \mathbb{P}[\|\hat{\theta} - \theta\|_A^2 \ge \|\theta\|_A^2] &= \mathbb{P}[\|\hat{\theta} - \theta\|_{X^{\top}X}^2 \ge (\sigma^2 d/N_e)(2d + 3x)] \\ &\le \mathbb{P}[\|\hat{\theta} - \theta\|_{X^{\top}X}^2 \ge (\sigma^2 d^2/N_e)(d + 2\sqrt{dx} + 2x)] \\ &\le e^{-x} = e^{2d/3 - N_e \|\theta\|^2/(3\sigma^2d)}. \end{aligned} \quad \blacksquare $$
**Lemma 5** Let $\hat{B}$ be the output of the warm-up, then,

$$ \mathbb{P}[\hat{B} \notin [(1/2)\|\theta\|_A, (3/2)\|\theta\|_A]] \le \frac{164 \sigma^2 d^2 \overline{\log}\left(\frac{T\|\theta\|_A^2}{d^2\sigma^2}\right)}{T\|\theta\|_A^2} + 48 \frac{d}{T}, $$

and the expected number of time-steps until the end the warm-up is

$$ \mathbb{E}[N_{\text{warm-up}}] \le \frac{164 \sigma^2 d^2 \overline{\log}\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right)}{\|\theta\|_A^2} + 48d. $$

**Proof** Define the threshold index

$$ i^* = \min\{i: U^2(\delta_i, n_i) \le \|\theta\|_A^2\}, $$

around which the warm-up should terminate. We first prove an upper bound on the length of the phase at that threshold index,

$$ 2^{i^*} \le \frac{(2 + \sqrt{2})\sigma^2 d \overline{\log}\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right)}{\|\theta\|_A^2} + 1. \quad (6) $$

**Proof of (6)** This essentially consists in inverting the formula of the definition of $U$. To this end define,

$$ \bar{n} = \frac{(1 + \sqrt{2}/2)\sigma^2 d^2 \overline{\log}\left(\frac{T\|\theta\|_A^2}{\sigma^2 d^2}\right)}{\|\theta\|_A^2}. $$

Define $\log_+(x) = \log(\max(x, 1))$. If $n_i \ge \bar{n}$, then, using the inequality $2\sqrt{u} \le \sqrt{2}/2 + (\sqrt{2})u$ for $u \ge 0$, we get

$$ \begin{aligned} U(\delta_i, n_i) &= \frac{\sigma^2 d^2}{n_i} \left( 1 + 2\sqrt{\frac{1}{d}\log_+\left(\frac{d}{Tn_i}\right)} + \frac{2}{d}\log_+\left(\frac{d}{Tn_i}\right) \right) \\ &\le \frac{\sigma^2 d^2}{\bar{n}} \left( 1 + 2\sqrt{\frac{1}{d}\log_+\left(\frac{d}{T\bar{n}}\right)} + \frac{2}{d}\log_+\left(\frac{d}{T\bar{n}}\right) \right) \\ &\le \frac{\sigma^2 d^2}{\bar{n}} \left( 2 + \frac{3}{d}\log_+\left(\frac{d}{T\bar{n}}\right) \right) = \|\theta\|^2 \frac{1 + \sqrt{2}/2 + \frac{2+\sqrt{2}}{d}\log_+\left(\frac{d}{T\bar{n}}\right)}{(1 + \sqrt{2}/2)\overline{\log}\left(\frac{T\|\theta\|^2}{\sigma^2 d^2}\right)} \\ &\le \|\theta\|^2 \frac{1 + \sqrt{2}/2 + \frac{2+\sqrt{2}}{d}\log_+\left(\frac{T\|\theta\|^2}{2\sigma^2 d}\right)}{(1 + \sqrt{2}/2)\overline{\log}\left(\frac{T\|\theta\|^2}{\sigma^2 d^2}\right)} \\ &\le \|\theta\|^2 \frac{1 + \sqrt{2}/2 + (1 + \sqrt{2}/2)\log_+\left(\frac{T\|\theta\|^2}{\sigma^2 d^2}\right)}{(1 + \sqrt{2}/2)\overline{\log}\left(\frac{T\|\theta\|^2}{\sigma^2 d^2}\right)} = \|\theta\|^2, \end{aligned} $$

where we also used the facts that $d \ge 2$ and $1/\bar{n} \le \|\theta\|^2/(\sigma^2 d^2)$. Therefore, we have shown that if $n_i \ge \bar{n}$, then $i \ge i^*$, hence

$$ 2^{i^*} \le \min\{2^i \mid n_i \ge \bar{n}\} \le \max\left(\frac{2\bar{n}}{d}, 1\right) \le \frac{2\bar{n}}{d} + 1, $$
which is the claimed inequality.

Now that (6) is proved, let us proceed with the next steps. Let $\hat{i}$ be the index of the warm-up round in which the algorithm terminates. Then by design, $\|\hat{\theta}_{\hat{i}}\| > 3U(\delta_{\hat{i}}, n_{\hat{i}})$. Therefore, by Lemma 11 and the triangle inequality,

$$ \begin{aligned} \mathbb{P}[\|\hat{\theta}_{\hat{i}}\| - \|\theta\| > \frac{1}{2}\|\theta\|] &\le \mathbb{P}[\|\hat{\theta}_{\hat{i}}\| - \|\theta\| > \frac{1}{3}\|\hat{\theta}_{\hat{i}}\|] \\ &\le \mathbb{P}[\|\hat{\theta}_{\hat{i}}\| - \|\theta\| > U(\delta, n_{\hat{i}})] \le \mathbb{P}[\|\hat{\theta}_{\hat{i}} - \theta\| > U(\delta, n_{\hat{i}})]. \end{aligned} $$

With a union bound on the possible values of $\hat{i}$, and applications of Lemma 6, the probability above is less than

$$ \begin{aligned} \sum_{i=1}^{i^*+4} \mathbb{P}[\|\hat{\theta}_i - \theta\| > U(\delta_i, n_i)] + \mathbb{P}[\hat{i} > i^* + 4] &\le \sum_{i=1}^{i^*+4} \delta_i + \mathbb{P}[\hat{i} > i^* + 4] \\ &\le \frac{d}{T} 2^{i^*+5} + \mathbb{P}[\hat{i} > i^* + 4]. \end{aligned} \quad (7) $$

The number of warm-up rounds can be written as

$$ N_{\text{warm-up}} = \min \left( T, \sum_{i=1}^{\hat{i}} n_i \right) $$

so that, doing a union bound over the value of $\hat{i}$ as above,

$$ \mathbb{E}[N_{\text{warm-up}}] \le \sum_{i=1}^{i^*+4} n_i + T \mathbb{P}[\hat{i} > i^* + 4] \le d 2^{i^*+5} + T \mathbb{P}[\hat{i} > i^* + 4]. \quad (8) $$

Now observe that on the event $\{\hat{i} > i^* + 4\}$, we have

$$ \|\hat{\theta}_{i^*+4}\| \le 3U(\delta_{i^*+4}, n_{i^*+4}) \quad \text{and} \quad U(\delta_{i^*+4}, n_{i^*+4}) < \frac{1}{4}U(\delta_{i^*}, n_{i^*}) \le \frac{1}{4}\|\theta\|. $$

Therefore, by combining both inequalities, on this event,

$$ \|\theta - \hat{\theta}_{i^*+4}\| \ge \|\theta\| - \|\hat{\theta}_{i^*+4}\| > 4U(\delta_{i^*+4}, n_{i^*+4}) - 3U(\delta_{i^*+4}, n_{i^*+4}) = U(\delta_{i^*+4}, n_{i^*+4}). $$

We have thus shown that

$$ \mathbb{P}[\hat{i} > i^* + 4] \le \mathbb{P}[\|\theta - \hat{\theta}_{i^*+4}\| > U(\delta_{i^*+4}, n_{i^*+4})] \le \delta_{i^*+4} = \frac{d}{T} 2^{i^*+4}. $$

Plug this in (7) and (8) to conclude.

$$ \mathbb{P}[\hat{B} \notin [(1/2)\|\theta\|_A, (3/2)\|\theta\|_A]] \le \frac{48d}{T} 2^{i^*} \quad \text{and} \quad \mathbb{E}[N_{\text{warm-up}}] \le 48d 2^{i^*}. \quad \blacksquare $$
## A.2. Technical lemmas

**Lemma 10** For any $\theta, u \in \mathbb{R}^d$, if $\theta^\top Au \ge 0$ then,

$$ \theta^\top(x^*(\theta) - x^*(u)) \le \frac{1}{\|\theta\|_A} \|\theta - u\|_A^2. $$

**Proof** Without loss of generality $A = I_d$, since $\|A^{1/2}\theta\| = \|\theta\|_A$ and

$$ \theta^\top(x_A^*(\theta) - x_A^*(u)) = A^{1/2}\theta^\top(x_I^*(A^{1/2}\theta) - x_I^*(A^{1/2}u)). $$

Then $x^*(\theta) = (1/\|\theta\|)\theta$ and $x^*(u) = (1/\|u\|)u$, so

$$ \theta^\top(x^*(\theta) - x^*(u)) = \frac{\|\theta\|}{2} \left\| \frac{1}{\|\theta\|} \theta - \frac{1}{\|u\|} u \right\|^2 = \frac{1}{2\|\theta\|} \left\| \theta - \frac{\|\theta\|}{\|u\|} u \right\|^2. $$

Furthermore, using the fact that $0 \le \theta^\top u \le \|\theta\|\|u\|$,

$$ \left\| \theta - \frac{\|\theta\|}{\|u\|} u \right\|^2 = 2 \|\theta\|^2 - 2 \frac{\|\theta\|}{\|u\|} \theta^\top u \le 2 \|\theta\|^2 - 2 \frac{1}{\|u\|^2} (\theta^\top u)^2. $$

Recognizing that the right-most term is twice the distance from $\theta$ to its projection on the line with direction $u$,

$$ \left\| \theta - \frac{\|\theta\|}{\|u\|} u \right\|^2 \le 2 \left( \|\theta\|^2 - \frac{1}{\|u\|^2} (\theta^\top u)^2 \right) = 2 \inf_{\lambda \in \mathbb{R}} \|\theta - \lambda u\|^2 \le 2 \|\theta - u\|^2. \quad \blacksquare $$

**Lemma 11** For any $a, b, \lambda \ge 0$ such that $|a - b| \ge \lambda a$, we have $|a - b| \ge \lambda/(1 + \lambda)b$.

**Proof** We consider two cases. If $a \ge b$, then $|a - b| \ge \lambda a \ge \lambda b \ge \lambda/(1 + \lambda)b$ proving the claim. Otherwise, if $a < b$, then $(1 + \lambda)|a - b| = |a - b| + \lambda(b - a) \ge \lambda a + \lambda(b - a) = \lambda b$. ■
# Appendix B. Action Sets That Do Not Contain Zero

## B.1. Non-centered Action Sets

We now describe how to modify our algorithm to handle non-centered ellipsoids, i.e., sets of the form

$$ \mathcal{X} = \{x \in \mathbb{R}^d : \|x - c\|_{A^{-1}} \le 1\} $$

for $c \neq 0$.

**ETC-type Algorithms** The modification applies more generally to any ETC-type algorithm, going from action sets $\mathcal{X}$ that contain 0 to the translated $c + \mathcal{X}$ for any $c \in \mathbb{R}^d$. Let us give some definitions.

**Definition 12** An algorithm is an ETC-type algorithm if there exists a stopping time $T_{\text{commit}}$ such that for any $t > T_{\text{commit}}$, the algorithm commits to the action $x_t = x_{T_{\text{commit}}+1}$.

In the case of Algorithm 1, the warm-up rounds should be counted as exploration rounds. We denote the commit action of an ETC-type algorithm by $x_{\text{commit}} := x_{T_{\text{commit}}+1}$. An ETC-type algorithm comes with a natural upper bound on its regret, as

$$ R_T(\mathcal{A}, \mathcal{X}, \theta) \le \left( \max_{x,y \in \mathcal{X}} \|x - y\| \right) \|\theta\|_{\star} \mathbb{E}[T_{\text{commit}}] + T \mathbb{E}[\theta^{\top}(x^{*}(\theta) - x_{\text{commit}})], \quad (9) $$

where $\| \cdot \|$ denotes any norm on $\mathbb{R}^d$ and $\| \cdot \|_{\star}$ denotes its dual norm.

Consider a parametric ETC-type algorithm Alg, that takes a variance proxy and time-horizon as inputs. Assume that for any linear bandit problem, the algorithm $\mathcal{A} = \text{Alg}(\sigma^2, T)$ tuned with $\sigma^2$ and $T$ satisfies

$$ \mathbb{E}[T_{\text{commit}}(\mathcal{A})] \le B(\theta, \sigma^2, T) \quad \text{and} \quad \mathbb{E}[\theta^{\top}(x_{\mathcal{X}}^{*}(\theta) - x_{\text{commit}}(\mathcal{A}))] \le C(\theta, \sigma^2, T), \quad (10) $$

for some $B$ and $C$, called the expected exploration time and expected commit error, respectively.

**A Reduction** We transform any ETC-type algorithm for action sets $\mathcal{X} \supseteq 0$ into an algorithm for the translated set $c + \mathcal{X}$ which retains essentially the same bound as above up to constant factors.

Consider a parametric algorithm Alg for $\mathcal{X}$ that takes the variance proxy and horizon as inputs, and let $\mathcal{A} = \text{Alg}(2\sigma^2, T/2)$. The recipe consists in replacing the plays $\tilde{x}_t \in \mathcal{X}$ in each round of exploration made by $\mathcal{A}$ by two rounds of exploration, playing first the reference point $c$ and then $c + \tilde{x}_t$, at times $2t - 1$ and $2t$. Now observe that

$$ y_{2t-1} - y_{2t} = \theta^{\top} \tilde{x}_t + (z_{2t-1} - z_{2t}). $$

Therefore, by providing $y_{2t-1} - y_{2t}$ as inputs to $\mathcal{A}$, the observations received by $\mathcal{A}$ are consistent with the linear bandit model with action set $\mathcal{X}$, except that the sub-gaussian variance proxy is doubled. Finally, since the optimal action is equivariant by translation of the action set, the commit error is the same in both cases.

## B.2. Analysis of the Reduction

The next theorem states that the algorithm obtained by applying the reduction enjoys essentially the same guarantees as the initial algorithm.
**Algorithm 2:** Reduction for non-centered action sets for ETC algorithms

**Input:** ETC-style algorithm $\mathcal{A}$ for action set $\mathcal{X}$ containing 0. Translation vector $c \in \mathbb{R}^d$.

**Init:** $t = 1$

1 **while** $t \le T_{\text{commit}}(\mathcal{A})$ **do**

2 Receive $\tilde{x}_t \in \mathcal{X}$ from $\mathcal{A}$

3 Play $x_{2t-1} = c$, receive $y_{2t-1}$. Play $x_{2t} = \tilde{x}_t$, receive $y_{2t}$.

4 Give $y_{2t-1} - y_{2t}$ as input to $\mathcal{A}$

5 Get $x_{\text{commit}}$ from $\mathcal{A}$

6 **while** $t \le T$ **do**

7 Play $c + x_{\text{commit}}$

**Theorem 13** Let $\mathcal{X}$ denote an action set containing $0 \in \mathbb{R}^d$. Let Alg be an ETC type algorithm with bounds $B$ and $C$ (see (10)). Denoting by $\mathcal{A}_c$ the algorithm obtained by applying the reduction Algorithm 2 to Alg$(2\sigma^2, T/2)$ for translation vector $c \in \mathbb{R}^d$, for any linear bandit problem with parameters $\theta$ and $\sigma^2$,

$$R_T(\mathcal{A}_c, c + \mathcal{X}, \theta) \le 2 \left( \max_{x,y \in \mathcal{X}} \|x - y\| \right) \|\theta\|_{\star} B(\theta, 2\sigma^2, T/2) + T C(\theta, 2\sigma^2, T/2).$$

This implies in particular that if there is a good ETC-type algorithm for an action set containing 0, then applying a translation to the action set can only make the linear bandit problem easier. Note also that the translation vector $c$ does not appear in the upper bound, perhaps surprisingly.

**Proof** Let $T_{\text{commit}}(\mathcal{A})$ denote the commit time, and $x_{\text{commit}}(\mathcal{A}) \in \mathcal{X}$ the commit action of $\mathcal{A}$ on its observations. The sequence of observations given to $\mathcal{A}$ fit exactly a linear bandit model with subvariance proxy $2\sigma^2$ and tuned for horizon $T/2$, so the guarantees on $\mathcal{A}$ hold:

$$\mathbb{E}[T_{\text{commit}}(\mathcal{A})] \le B(\theta, 2\sigma^2, T/2) \quad \text{and} \quad \mathbb{E}[\theta^\top(x_\mathcal{X}^*(\theta) - x_{\text{commit}}(\mathcal{A}))] \le C(\theta, 2\sigma^2, T/2).$$

By construction $\mathcal{A}_c$ is an ETC-type algorithm with $T_{\text{commit}}(\mathcal{A}_c) = 2T_{\text{commit}}(\mathcal{A})$, and the commit action is $x_{\text{commit}}(\mathcal{A}_c) = c + x_{\text{commit}}(\mathcal{A})$. So the regret decomposition (9) applies and

$$\begin{aligned} R_T(\theta) &\le \left( \max_{x,y \in \mathcal{X}} \|x - y\| \right) \|\theta\|_{\star} \mathbb{E}[T_{\text{commit}}(\mathcal{A}_c)] + T \mathbb{E}[\theta^\top (x_{c+\mathcal{X}}^*(\theta) - x_{\text{commit}}(\mathcal{A}_c))] \\ &\le 2 \left( \max_{x,y \in \mathcal{X}} \|x - y\| \right) \|\theta\|_{\star} \mathbb{E}[T_{\text{commit}}(\mathcal{A})] + T \mathbb{E}[\theta^\top (x_{\mathcal{X}}^*(\theta) - x_{\text{commit}}(\mathcal{A}))]. \quad \blacksquare \end{aligned}$$
## Appendix C. Proof details for Section 2

**Proof of Proposition 2** We consider a noiseless linear bandit problem with mean parameter $\theta$ sampled from a Gaussian distribution $N(0, (B^2/d)A^{-1})$. The idea of the proof is to lower bound the expected regret of any algorithm when averaged over this distribution.

After $t \le d$ rounds of playing, let $\mathcal{F}_t$ denote the $\sigma$-algebra generated by the observations $y_1, \dots, y_t$, and the chosen actions $x_1, \dots, x_{t+1}$ (we include $x_{t+1}$ to account for the possible internal randomization of the algorithm). At time $t+1$, if we integrate both over the initial randomization on $\theta$ and on the internal randomization, by the tower rule and since $x_{t+1}$ is $\mathcal{F}_t$-measurable,

$$ \mathbb{E}[(x_{t+1} - c)^{\top}\theta] = \mathbb{E}[(x_{t+1} - c)^{\top}\mathbb{E}[\theta|\mathcal{F}_t]] \le \mathbb{E}[\|\mathbb{E}[\theta|\mathcal{F}_t]\|_A]. $$

By standard results on Bayesian linear regression, (see, e.g., Chapter 9.2 in Hoff (2009)), the distribution of $A^{1/2}\theta$ conditional on $\mathcal{F}_t$ is $N(P_t\theta, (B^2/d)(I_d - P_t))$ where $P_t$ denotes the orthogonal projection on the span of $x_1, \dots, x_t$. Orthonormalizing the family $(x_t)$ yields orthonormal vectors $e_1, \dots, e_t$ such that $e_i$ is $\mathcal{F}_{i-1}$-measurable and

$$ \|A^{-1/2}P_t A^{1/2}\theta\|_A^2 = \|P_t A^{1/2}\theta\|^2 = \sum_{i=1}^{t} ((A^{1/2}\theta)^{\top} e_i)^2. $$

Then, since $e_i$ is $\mathcal{F}_{i-1}$-measurable, the vector $(A^{1/2}\theta)^{\top}e_i$ is normally distributed with distribution $N(0, (B^2/d)e_i^{\top}(I_d - P_{i-1})e_i) = N(0, B^2/d)$. So for all $i \le d$, we have the equality $\mathbb{E}[((A^{1/2}\theta)^{\top}e_i)^2|\mathcal{F}_{i-1}] = B^2/d$. Applying this repeatedly, we see that

$$ \mathbb{E}[\|A^{-1/2}P_t A^{1/2}\theta\|_A] \le \sqrt{\mathbb{E}[\|A^{-1/2}P_t A^{1/2}\theta\|_A^2]} = B\sqrt{\frac{t}{d}}. $$

This implies that the averaged regret up to time $d$ is at least

$$ \begin{aligned} \mathbb{E}[R_d(\theta)] = \sum_{t=1}^{d} \mathbb{E}[(x^*(\theta) - c)^{\top}\theta] - \mathbb{E}[(x_t - c)^{\top}\theta] \\ \ge \sum_{t=1}^{d} \mathbb{E}[\|\theta\|_A] - \mathbb{E}[\|A^{-1/2}P_{t-1}A^{1/2}\|_A] \ge \sum_{t=1}^{d} \mathbb{E}[\|\theta\|_A] - B\sqrt{\frac{t-1}{d}}. \end{aligned} $$

Note also that since $A^{1/2}$ is a standard gaussian vector,

$$ \mathbb{E}_{\theta}[\|A^{1/2}\theta\|] = \frac{B \sqrt{2\Gamma((d+1)/2)}}{\sqrt{d} \Gamma(d/2)} \ge B\sqrt{(d-1)/d}, $$

where we used Gautschi's inequality,

$$ x^{1-s} \le \frac{\Gamma(x+1)}{\Gamma(x+s)}, $$

with $x = (n-1)/2$ and $s = 1/2$. All in all, this implies that

$$ \mathbb{E}[R_T(\theta)] \ge B \sum_{t=1}^{d} \sqrt{\frac{d-1}{d}} - \sqrt{\frac{t-1}{d}} \ge \frac{1}{3}dB. $$
To complete the averaging argument, we also need to ensure that the norm of $\theta$ is large enough. Let $c$ be some numerical parameter, of which we will set the value later on. By a case disjunction,

$$ \mathbb{E}[R_d(\theta)1\{\|\theta\|_A \le cB\}] = \mathbb{E}[R_d(\theta)] - \mathbb{E}[R_d(\theta)1\{\|\theta\|_A > cB\}]. $$

We apply a version of the peeling trick decomposing over the values of $\|\theta\|_A$ in a grid to bound

$$ \begin{aligned} \mathbb{E}[R_d(\theta)1\{\|\theta\|_A > cB\}] &\le \sum_{i=1}^{+\infty} 2t\sqrt{i+1}cB\mathbb{P}[\|\theta\|_A > \sqrt{icB}] \\ &\le 2\sqrt{2}dB \sum_{i=1}^{+\infty} \sqrt{c^2i} \mathbb{P}[\|\theta\|_A > \sqrt{icB}] = \frac{2\sqrt{2}dB}{\sqrt{d}} \sum_{i=1}^{+\infty} \sqrt{ic^2} \mathbb{P}[\|\theta\|_A > \sqrt{icB}]. \end{aligned} $$

Use the concentration inequality Lemma 6, which applies in particular to the Gaussian vector $A^{1/2}\theta$,

$$ \mathbb{P}[\|A^{1/2}\theta\|^2 \ge B^2\left(2+\frac{3x}{d}\right)] \le e^{-x} \quad \text{with} \quad x = \frac{d}{3}(c^2i-2). $$

If $c^2 \ge 8/7$, then $c^2i - 2 \ge 3c^2i/4$ as $7ci^2/4 \ge 2$ (remember $i \ge 1$) so

$$ \mathbb{P}[\|A^{1/2}\theta\|^2 \ge ic^2B^2] \le \exp\left(-\frac{idc^2}{4}\right) $$

Note furthermore that since the function $xe^{-x^2/8}$ is decreasing on $[4, +\infty)$, so for any $x \ge 4$, $xe^{-x^2/4} \le 4e^{-2}e^{-x^2/8}$. Consequently, if $c \ge 2\sqrt{2}$, then $\sqrt{idc^2} \ge 4$ since $d \ge 2$, and

$$ \sum_{i=1}^{+\infty} \sqrt{idc^2} e^{-idc^2/4} \le \sum_{i=1}^{+\infty} e^{-idc^2/8} = \frac{e^{-dc^2/8}}{1 - e^{-dc^2/8}}. $$

We have thus lower bounded the regret on the event that $\|\theta\|_A > cB$ as

$$ \begin{aligned} \mathbb{E}[R_t(\theta)1\{\|\theta\|_A > cB\}] &\ge \frac{dB}{2} - \frac{2\sqrt{2}dB}{\sqrt{d}} \frac{e^{-dc^2/8}}{1 - e^{-dc^2/8}} = \left(\frac{1}{2} - \frac{2\sqrt{2}}{\sqrt{d}} \frac{e^{-dc^2/8}}{1 - e^{-dc^2/8}}\right)dB \\ &\ge \left(\frac{1}{2} - \frac{2e^{-c^2/4}}{1 - e^{-c^2/4}}\right)dB \ge \left(\frac{1}{2} - \frac{2e^{-2}}{1 - e^{-2}}\right)dB \ge 0.18dB, \end{aligned} $$

we also used the facts that $d \ge 2$ and $c \ge 2\sqrt{2}$. Applying our result exactly with $c = 4$, we deduce the existence of some $\theta$ such that $\|\theta\|_A \le 4B$ and

$$ R_T(\theta) \ge R_d(\theta) \ge 0.07dB \ge \frac{0.07}{4} d \|\theta\|_A \ge 0.017d \|\theta\|_A. \quad \blacksquare $$
# Appendix D. Glossary

## Notation related to problem setting

<table><thead><tr><th>Notation</th><th>Description</th><th>Page List</th></tr></thead><tbody><tr><td>T</td><td>Time horizon</td><td>1</td></tr><tr><td>[T]</td><td>Set of time step until [T] = {1, 2, ..., T}</td><td>1</td></tr><tr><td>d</td><td>Dimension of the problem considered</td><td>1</td></tr><tr><td>A</td><td>Definite positive matrix defining a norm and an ellipsoid action set</td><td>1</td></tr><tr><td>λ<sub>max</sub></td><td>Maximal eigenvalue of the matrix</td><td>4</td></tr><tr><td>λ<sub>min</sub></td><td>Minimal eigenvalue of the matrix</td><td>4</td></tr><tr><td>||u||<sub>M</sub></td><td>Norm defined by the matrix M, ||u||<sub>M</sub> = √u<sup>T</sup>Mu</td><td>1</td></tr><tr><td>X</td><td>The action set X ⊂ ℝ<sup>d</sup></td><td>1</td></tr><tr><td>c</td><td>Center of the ellipsoid that define the action set</td><td>1</td></tr><tr><td>θ</td><td>Unknown parameter of the model θ ∈ ℝ<sup>d</sup></td><td>1</td></tr><tr><td>x<sup>*</sup>(θ)</td><td>Optimal action as a function θ and A</td><td>2</td></tr><tr><td>x<sub>t</sub></td><td>Action taken at time t</td><td>1</td></tr><tr><td>y<sub>t</sub></td><td>Reward received at time t</td><td>1</td></tr><tr><td>z<sub>t</sub></td><td>Noise at time t</td><td>1</td></tr><tr><td>σ</td><td>Subgaussian parameter of the noise</td><td>1</td></tr><tr><td>R<sub>T</sub>(θ)</td><td>Average regret at time T on the environment parametrized by θ</td><td>2</td></tr></tbody></table>

## Notation related to the algorithm and its analysis

<table><thead><tr><th>Notation</th><th>Description</th><th>Page List</th></tr></thead><tbody><tr><td>Ω</td><td>Lowerbound Notation, "f(φ) = Ω(g(φ))" iff ∃c > 0, ∀φ, f(φ) ≥ cg(φ)</td><td>2</td></tr><tr><td>O</td><td>Upperbound Notation, "f(φ) = O(g(φ))" iff ∃c > 0, ∀φ, f(φ) ≤ cg(φ)</td><td>2</td></tr><tr><td>~O</td><td>Upperbound Notation with hidden polylog terms</td><td>2</td></tr><tr><td>B</td><td>Norm A of the parameter θ</td><td>2</td></tr><tr><td>E<sub>A</sub>(B)</td><td>Elliptical ensemble of vectors for which the norm is B in ||·||<sub>A</sub> norm</td><td>2</td></tr><tr><td>A</td><td>Generic notation for an algorithm</td><td>2</td></tr><tr><td>w<sub>t</sub></td><td>Reparametrization of the action x<sub>t</sub> centered and in base A, x<sub>t</sub> = A<sup>1/2</sup>w<sub>t</sub> + c</td><td>5</td></tr><tr><td>ε<sup>2</sup></td><td>Parameter in the proof to set the distance between two confusing problems' parameter</td><td>5</td></tr><tr><td>φ</td><td>Function to create confusing parameters in the lowerbound</td><td>5</td></tr><tr><td>ξ</td><td>Vector in ξ ∈ {-1, 1}<sup>d</sup> to create confusing parameters in the lowerbound</td><td>5</td></tr><tr><td>θ(ξ)</td><td>Confusing parameters in the lowerbound</td><td>5</td></tr><tr><td>τ<sub>i</sub></td><td>Stopping time to control relative entropy in the i-th direction</td><td>5</td></tr><tr><td>U<sub>i</sub></td><td>Random variable representing directional regret in the i-th direction</td><td>5</td></tr><tr><td>ξ<sup>(-i)</sup></td><td>Flip the ith coordinate of the vector ξ. ∀j, ξ<sup>(-i)</sup><sub>j</sub> := (-1)<sup>1(i=j)</sup>ξ<sub>j</sub></td><td>6</td></tr><tr><td>P<sub>θ(ξ),i</sub></td><td>the probability distribution of (w<sub>t</sub>)<sub>t≤τ<sub>i</sub>(T)</sub> under parameter θ(ξ)</td><td>6</td></tr><tr><td>C</td><td>Parameter used to set a constant relative entropy between problems</td><td>5</td></tr><tr><td>D</td><td>Relative entropy between two distributions</td><td>6</td></tr></tbody></table>
<table><thead><tr><th>Notation</th><th>Description</th><th>Page List</th></tr></thead><tbody><tr><td>LS</td><td>Least-squares estimator with observed features X and rewards Y. LS(X, Y) = (X<sup>T</sup>X)<sup>-1</sup>X<sup>T</sup>Y</td><td>7</td></tr><tr><td>X<sup>T</sup>X</td><td>The design matrix with the observing features X ∈ ℝ<sup>n×d</sup></td><td>9</td></tr><tr><td>T</td><td>Set of instant T ⊂ N</td><td>7</td></tr><tr><td>X<sub>T</sub></td><td>Submatrix of the features of the reward X<sub>T</sub> := (x<sub>t</sub>)<sub>t∈T</sub> ∈ ℝ<sup>|T||×d</sup></td><td>7</td></tr><tr><td>Y<sub>T</sub></td><td>Subvector of the reward Y<sub>T</sub> := (y<sub>t</sub>)<sub>t∈T</sub> ∈ ℝ<sup>|T||</sup></td><td>7</td></tr><tr><td>Z<sub>T</sub></td><td>Subvector of the noise Z<sub>T</sub> := (z<sub>t</sub>)<sub>t∈T</sub> ∈ ℝ<sup>|T||</sup></td><td>7</td></tr><tr><td>θ̂<sub>i</sub></td><td>The Least square estimation of the parameter θ at the end of phase i</td><td>7</td></tr><tr><td>α</td><td>Parameter used in the warm-up phase</td><td>8</td></tr><tr><td>̂i</td><td>Phase when the warm-up phase ends</td><td>8</td></tr><tr><td>B̂</td><td>The estimation of ||θ||<sub>A</sub> at the end of the warm-up phase, B̂ = ||θ̂<sub>i</sub>||<sub>A</sub></td><td>8</td></tr><tr><td>δ<sub>i</sub></td><td>Probability of failure of the i-th phase of the warm-up procedure</td><td>7</td></tr><tr><td>n<sub>i</sub></td><td>Duration of the i-th phase of the warm-up procedure</td><td>7</td></tr><tr><td>T<sub>i</sub></td><td>Number of rounds after the i-th phase of the warm-up procedure</td><td>7</td></tr><tr><td>U(δ<sub>i</sub>, n<sub>i</sub>)</td><td>Confidence bound of the estimated norm distribution with probability 1 − δ<sub>i</sub> and n<sub>i</sub> samples. Related to the χ<sup>2</sup> law.</td><td>8</td></tr><tr><td>N<sub>e</sub></td><td>Number of exploration round during the exploration phase</td><td>8</td></tr><tr><td>θ̂</td><td>The least-squares estimation of the parameter θ at the beginning of the commit phase</td><td>8</td></tr><tr><td>E<sub>expl</sub></td><td>Expectation conditionally on all rounds before phase 3</td><td>9</td></tr><tr><td>C<sub>t</sub></td><td>Confidence ellipsoid at time t of the parameter θ in optimistic algorithms</td><td>4</td></tr><tr><td>log</td><td>log(x) = 1 + log(max(1, x))</td><td>7</td></tr><tr><td>−</td><td>a<sup>−</sup> := min(a, 0)</td><td>7</td></tr></tbody></table>

Abbreviation used in the paper

<table><thead><tr><th>Notation</th><th>Description</th><th>Page List</th></tr></thead><tbody><tr><td>ETC</td><td>Explore-Then-Commit, Type of algorithm that first explores the environment then commits to the best actions</td><td>2</td></tr><tr><td>E2TC</td><td>Explore-Explore-Then-Commit, The locally asymptotic minimax algorithm introduced in this paper</td><td>2</td></tr><tr><td>CB</td><td>ConfidenceBall, Optimistic based algorithm of Dani et al. (2008)</td><td>3</td></tr><tr><td>PEGE</td><td>Phased Exploration and Greedy Exploitation. Nearly ETC like algorithm of Rusmevichientong and Tsitsiklis (2010)</td><td>4</td></tr><tr><td>UE</td><td>Uncertainty Ellipsoid, Optimistic algorithm of Rusmevichientong and Tsitsiklis (2010)</td><td>4</td></tr><tr><td>OFUL</td><td>Optimism in the Face of Uncertainty Linear bandit, Optimistic algorithm of Abbasi-Yadkori et al. (2011)</td><td>4</td></tr><tr><td>OLSOFUL</td><td>Ordinary Least Squares OFUL, Optimistic algorithm of Gales et al. (2022)</td><td>4</td></tr><tr><td>TS</td><td>Thompson Sampling, Sampling based algorithm of Abeille and Lazaric (2017)</td><td>4</td></tr></tbody></table>