Efficient Contextual Bandits in Non-stationary Worlds

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 $\mathcal{O}(\sqrt{ST})$ if there are $T$ rounds with $S$ stationary periods, or more generally $\mathcal{O}({\Delta }^{1/3}{T}^{2/3})$ where $\Delta$ 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 $\Delta$, we also develop a parameter free algorithm achieving regret $\min \{S^{1/4}{T}^{3/4},{\Delta }^{1/5}{T}^{4/5}\}$. This improves and generalizes the best existing result ${\Delta }^{0.18}{T}^{0.82}$ by Karnin and Anava (2016) which only holds for the two-armed bandit problem.

Cited by in corpus (20)

• Learning Contextual Bandits in a Non-stationary Environment
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Model selection for contextual bandits
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Bandit Convex Optimization in Non-stationary Environments
• Learning and Optimization with Seasonal Patterns
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• A Linear Bandit for Seasonal Environments
• Non-Stationary Latent Bandits
• Learning User Preferences in Non-Stationary Environments
• Self-Tuning Bandits over Unknown Covariate-Shifts
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Non-Stationary Off-Policy Optimization