A Perturbation Approach to Unconstrained Linear Bandits

2026/03/30 by Andrew Jacobsen, Dorian Baudry, Shinji Ito +1
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Optimization and Search Problems #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2603.28201

50 pages; v2: ICML 2026; v3: fixed document outine + typos

openalex publication_date 2026/03/30 · openalex created_date 2026/04/02 · openalex updated_date 2026/07/28 · arxiv created 2026/08/02 · arxiv updated 2026/08/04

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 √(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 Ω(√(dT)) rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.

Citations

• Dynamic Regret Reduces to Kernelized Static Regret
• An Equivalence Between Static and Dynamic Regret Minimization
• Dealing with unbounded gradients in stochastic saddle-point optimization
• Bandit Convex Optimisation
• Unconstrained Online Learning with Unbounded Losses
• Unconstrained Dynamic Regret via Sparse Coding
• Parameter-free Regret in High Probability with Heavy Tails
• Parameter-free Mirror Descent
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits
• PDE-Based Optimal Strategy for Unconstrained Online Learning
• The Pareto Frontier of model selection for general Contextual Bandits
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Comparator-adaptive Convex Bandits
• Bandit Algorithms
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Lipschitz and Comparator-Norm Adaptivity in Online Learning
• Online Learning: A Modern Introduction Using Convex Optimization
• Combining Online Learning Guarantees
• Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
• Corralling a Band of Bandit Algorithms
• Introduction to Online Convex Optimization
• Coin Betting and Parameter-Free Online Learning
• Strongly Adaptive Online Learning
• On the Complexity of Bandit Linear Optimization
• Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
• Towards minimax policies for online linear optimization with bandit feedback
• Online convex optimization in the bandit setting: gradient descent without a gradient