stat.MLFeb 24, 2025

Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Authors: Raymond Zhang, Hedi Hadiji, Richard Combes

Organizations: Laboratoire des signaux et systèmes, Univ. Paris-Saclay, CNRS, CentraleSupélec

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 Ω(min⁡(dσT+d∥θ∥A,∥θ∥AT))Ω(\min(d σ\sqrt{T} + d \|θ\|_{A}, \|θ\|_{A} T)) where dd is the dimension, TT the time horizon, σ2σ^2 the noise variance, AA a matrix defining the set of actions and θθ 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 ∥θ∥\|θ\|, 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+d2log⁡(T/d)+d3)O(dT + d^2 \log(T/d) + d^3) and memory O(d2)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.

Figures & tables

Explore similar work

Sep 26, 2026

A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets

Linear bandits model sequential decision-making problems with noisy rewards that are linear in the decision variable, where an agent must simultaneously learn about an unknown parameter that governs the mean rewards, while maximizing (expected) rewards over time. Two prominent algorithmic families--upper confidence bound (UCB) and Thompson sampling (TS)--achieve a balance of exploration (to estimate said parameter) and exploitation (utilization of knowledge about it) across time. The quality of estimation of that parameter depends on the eigenvalues of a design matrix. In this paper, we begin by showing that if the inference quality obtained from exploration, encoded in the minimum eigenvalue of the design matrix, grows ≳t\gtrsim \sqrt{t} with time tt, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability O(Tlog⁡T)\mathcal{O}(\sqrt{T}\log T)-regret rate over a time-horizon TT for spherical action sets. This analysis is algorithm-agnostic and follows an alternative route to the classical optimism-based elliptical-potential argument for regret analysis. Then, we illustrate that variants of UCB and TS satisfy the inference and concentration properties and in turn, enjoy optimal regret rate. In effect, our results provide a modular framework that can be used to analyze linear bandit algorithms and explicitly connect quality of parameter estimation to optimal regret accumulation.
May 29, 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size BB, and during each batch the learner sends BB requested arm pulls to an agent, who then observes the corresponding BB rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that Ω(Bmin⁡{d,log⁡∣A∣})Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\}) regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of Ω~(Bmin⁡{d,log⁡∣A∣}+dTmin⁡{d,log⁡∣A∣})\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}}). We develop two phased-elimination algorithms based on GG-optimal designs and 1-bit mean estimation. The first achieves O~(dB+dT)\widetilde{O}(dB + d\sqrt{T}) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp⁡(Ω(d))\lvert \mathcal{A} \rvert = \exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O~(Blog⁡∣A∣+d3/2B+dTlog⁡∣A∣)\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert}) regret, which is near-optimal in broad scaling regimes of (∣A∣,B,d,T)(\lvert \mathcal{A} \rvert, B, d, T). Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as Θ(T)Θ(\sqrt{T}).
May 11, 2026

Learning to Sparsify Stochastic Linear Bandits

This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a O~(dT)\tilde{\mathcal{O}}(d\sqrt{T}) regret, where dd is the dimension of the action vector and TT is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a O~(dT)\tilde{\mathcal{O}}(d \sqrt{T}) αα-regret; for general compact sets lacking strong convexity, we establish a O~(dT2/3)\tilde{\mathcal{O}}(d T^{2/3}) αα-regret, where αα pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.