Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.32149 · 0 citations · 14 references
Computer Science Mathematics

TL;DR

The 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.

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 $\gtrsim \sqrt{t}$ with time $t$, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability $\mathcal{O}(\sqrt{T}\log 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.

View source

Similar papers

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayes...

T. Goo, Kihyuk Hong · 0 citations
#machine learning Preprint Oct 2026

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits...

Jing-Yuan Liu, Hui-Wen Jia · 0 citations
#machine learning Preprint Oct 2026

Optimal Online Regret for Context-Lumpable Bandits

We study stochastic contextual bandits with an unknown context-lumpable structure. The $S$ contexts are partitioned into $r$ blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected re...

Chen-Yu Lu, Zi-Han Zhang · 0 citations
#machine learning Preprint Oct 2026

Reliable Scale-Free Bandits via Empirical Likelihood

The exact exponent of linear regret deviations on two-armed Gaussian instances with common variance is determined and a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance is established.

Pratham Gupta, Alhad Sethi, Shubhada Agrawal · 1 citation

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t...

Yu-Heng Zhang · 1 citation
#machine learning Preprint Oct 2026

Expected Sample Complexity in Multi-Armed Bandits

It is shown that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and stochastic algorithms in two settings are analyzed, showing that the algorithms are tight in $\epsilon$ and proving a performance separation between the two regimes.

Nadav Sukenik, Nadav Merlis · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.