A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
Abstract
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 with time t, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability 𝒪(√Tlog T)-regret rate over a time-horizon T 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.
Related
- Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
- A Unified Space-Time Variational Framework for Wave Equations on Differential Forms
- Centered Weak Discrete Riemannian Gradients: A Unified Framework for Riemannian Optimization
- A unified variational framework for augmented Lagrangian preconditioning of saddle point systems: applications to mixed-dimensional and fictitious domain methods
- A unified framework for existing and new constructions of Neumaier graphs
BibTeX
@misc{guclu2026unified,
title = {{A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets}},
author = {Arda Güçlü and Subhonmesh Bose and John R. Birge},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32149},
eprint = {2609.32149},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32149},
}
RIS
TY - UNPB
TI - A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
AU - Arda Güçlü
AU - Subhonmesh Bose
AU - John R. Birge
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32149
UR - https://arxiv.org/abs/2609.32149
AB - 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 with time t, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability 𝒪(√Tlog T)-regret rate over a time-horizon T 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.
ER -