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

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

    Sep 26, 2026Arda Güçlü, Subhonmesh Bose, John R. BirgeMulti-Armed BanditsUCB Algorithms

  2. Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

    May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed BanditsBatched Bandits

  3. Learning to Sparsify Stochastic Linear Bandits

    May 11, 2026Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2Multi-Armed BanditsExploration-Exploitation Tradeoff