Efficient Contextual Bandits in Non-stationary Worlds

2017/08/05 by Haipeng Luo, Luo, Haipeng, Chen-Yu Wei +5 · 5 citations
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.1708.01799

openalex publication_date 2017/08/05 · arxiv created 2019/04/03 · arxiv updated 2019/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. problems with sophisticated statistical tests so as to dynamically adapt to a change in distribution. We analyze various standard notions of regret suited to non-stationary environments for these algorithms, including interval regret, switching regret, and dynamic regret. When competing with the best policy at each time, one of our algorithms achieves regret O(√(ST)) if there are T rounds with S stationary periods, or more generally O(Δ^1/3T^2/3) where Δ is some non-stationarity measure. These results almost match the optimal guarantees achieved by an inefficient baseline that is a variant of the classic Exp4 algorithm. The dynamic regret result is also the first one for efficient and fully adversarial contextual bandit. Furthermore, while the results above require tuning a parameter based on the unknown quantity S or Δ, we also develop a parameter free algorithm achieving regret min\S^1/4T^3/4, Δ^1/5T^4/5\. This improves and generalizes the best existing result Δ^0.18T^0.82 by Karnin and Anava (2016) which only holds for the two-armed bandit problem.

Citations

• The Nonstochastic Multiarmed Bandit Problem
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• The best of both worlds: stochastic and adversarial bandits
• More Adaptive Algorithms for Adversarial Bandits

Cited by

• Nightjar: Dynamic Adaptive Speculative Decoding for Large Language Models Serving
• Power Constrained Nonstationary Bandits with Habituation and Recovery Dynamics
• Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
• Non-stationary Bandit Convex Optimization: A Comprehensive Study
• BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms

Related

• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces