Hedging the Drift: Learning to Optimize under Non-Stationarity

Abstract

We introduce data-driven decision-making algorithms that achieve state-of-the-art \emph{dynamic regret} bounds for non-stationary bandit settings. These settings capture applications such as advertisement allocation, dynamic pricing, and traffic network routing in changing environments. We show how the difficulty posed by the (unknown \emph{a priori} and possibly adversarial) non-stationarity can be overcome by an unconventional marriage between stochastic and adversarial bandit learning algorithms. Our main contribution is a general algorithmic recipe for a wide variety of non-stationary bandit problems. Specifically, we design and analyze the sliding window-upper confidence bound algorithm that achieves the optimal dynamic regret bound for each of the settings when we know the respective underlying \emph{variation budget}, which quantifies the total amount of temporal variation of the latent environments. Boosted by the novel bandit-over-bandit framework that adapts to the latent changes, we can further enjoy the (nearly) optimal dynamic regret bounds in a (surprisingly) parameter-free manner. In addition to the classical exploration-exploitation trade-off, our algorithms leverage the power of the "forgetting principle" in the learning processes, which is vital in changing environments. Our extensive numerical experiments on both synthetic and real world online auto-loan datasets show that our proposed algorithms achieve superior empirical performance compared to existing algorithms.

arXiv commentJournal version of the AISTATS 2019 version (available at arXiv:1810.03024). This version fixed an error in the proof of Theorem 2 with Assumption 4 of arXiv:2103.05750

References in corpus (16)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Efficient Contextual Bandits in Non-stationary Worlds
• Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
• Taming Non-stationary Bandits: A Bayesian Approach
• Model selection for contextual bandits
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Tracking the Best Expert in Non-stationary Stochastic Environments
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
• Learning and Optimization with Seasonal Patterns
• On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems
• Stochastic bandits robust to adversarial corruptions
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization

Cited by in corpus (18)

• An empirical evaluation of active inference in multi-armed bandits
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Algorithms for Non-Stationary Generalized Linear Bandits
• Learning and Optimization with Seasonal Patterns
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Generalized Linear Bandits with Local Differential Privacy
• A Linear Bandit for Seasonal Environments
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Self-Tuning Bandits over Unknown Covariate-Shifts
• Lifelong Learning in Multi-Armed Bandits
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits
• Regret Bounds for Generalized Linear Bandits under Parameter Drift
• Distribution-free Contextual Dynamic Pricing
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Multiscale Non-stationary Stochastic Bandits