A Perturbation Approach to Unconstrained Linear Bandits

Read full text Summarise with VIRAT
Authors: Andrew Jacobsen, Dorian Baudry, Shinji Ito, Nicolò Cesa‐Bianchi
Cited by: 0
References: 22

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the first guarantees with optimal $\sqrt{P_T}$ path-length dependencies without prior knowledge of $P_T$. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore $Ω(\sqrt{dT})$ rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.

Fields of Study & Subjects

Advanced Bandit Algorithms Research Optimization and Search Problems Machine Learning and Algorithms

Publication details

Journal / source
arXiv (Cornell University)
Volume
306
Publication date
30 March 2026
Language
EN
Document type
Preprint