On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits

2019/03/19 by Roman Pogodin, Tor Lattimore, Pogodin, Roman +1
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1903.07890

14 pages

openalex publication_date 2019/03/19 · arxiv created 2019/07/24 · arxiv updated 2019/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We make three contributions to the theory of k-armed adversarial bandits. First, we prove a first-order bound for a modified variant of the INF strategy by Audibert and Bubeck [2009], without sacrificing worst case optimality or modifying the loss estimators. Second, we provide a variance analysis for algorithms based on follow the regularised leader, showing that without adaptation the variance of the regret is typically Ω(n²) where n is the horizon. Finally, we study bounds that depend on the degree of separation of the arms, generalising the results by Cowan and Katehakis [2015] from the stochastic setting to the adversarial and improving the result of Seldin and Slivkins [2014] by a factor of log(n)/log(log(n)).

Citations

• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits

Related

• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds
• Stochastic Bandits Robust to Adversarial Attacks
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits
• Beyond the Hazard Rate: More Perturbation Algorithms for Adversarial Multi-armed Bandits
• Adaptation to the Range in K-Armed Bandits