A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free

Abstract

We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves dynamic regret $\mathcal{O}(\min \{\sqrt{ST},{\Delta }^{\frac{1}{3}}{T}^{\frac{2}{3}}\})$ for a contextual bandit problem with $T$ rounds, $S$ switches and $\Delta$ total variation in data distributions. Importantly, our algorithm is adaptive and does not need to know $S$ or $\Delta$ ahead of time, and can be implemented efficiently assuming access to an ERM oracle. Our results strictly improve the $\mathcal{O}(\min \{S^{\frac{1}{4}}{T}^{\frac{3}{4}},{\Delta }^{\frac{1}{5}}{T}^{\frac{4}{5}}\})$ bound of (Luo et al., 2018), and greatly generalize and improve the $\mathcal{O}(\sqrt{ST})$ result of (Auer et al, 2018) that holds only for the two-armed bandit problem without contextual information. The key novelty of our algorithm is to introduce replay phases, in which the algorithm acts according to its previous decisions for a certain amount of time in order to detect non-stationarity while maintaining a good balance between exploration and exploitation.

References in corpus (7)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Efficient Optimal Learning for Contextual Bandits
• Efficient Contextual Bandits in Non-stationary Worlds
• Efficient Algorithms for Adversarial Contextual Learning
• Dynamic Regret of Strongly Adaptive Methods
• Tracking the Best Expert in Non-stationary Stochastic Environments

Cited by in corpus (17)

• Model selection for contextual bandits
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Variational Regret Bounds for Reinforcement Learning
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Taking a hint: How to leverage loss predictors in contextual bandits?
• A Linear Bandit for Seasonal Environments
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• Self-Tuning Bandits over Unknown Covariate-Shifts
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• Unifying Clustered and Non-stationary Bandits
• Multiscale Non-stationary Stochastic Bandits