Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit

Abstract

Multi-armed bandit (MAB) is a class of online learning problems where a learning agent aims to maximize its expected cumulative reward while repeatedly selecting to pull arms with unknown reward distributions. We consider a scenario where the reward distributions may change in a piecewise-stationary fashion at unknown time steps. We show that by incorporating a simple change-detection component with classic UCB algorithms to detect and adapt to changes, our so-called M-UCB algorithm can achieve nearly optimal regret bound on the order of $O(\sqrt{MKT\log T})$, where $T$ is the number of time steps, $K$ is the number of arms, and $M$ is the number of stationary segments. Comparison with the best available lower bound shows that our M-UCB is nearly optimal in $T$ up to a logarithmic factor. We also compare M-UCB with the state-of-the-art algorithms in numerical experiments using a public Yahoo! dataset to demonstrate its superior performance.

Cited by in corpus (23)

• An empirical evaluation of active inference in multi-armed bandits
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Algorithms for Non-Stationary Generalized Linear Bandits
• Bandit Algorithms for Precision Medicine
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret
• A Linear Bandit for Seasonal Environments
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Non-Stationary Latent Bandits
• Adaptively Optimize Content Recommendation Using Multi Armed Bandit Algorithms in E-commerce
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Weighted Gaussian Process Bandits for Non-stationary Environments
• Accelerated learning from recommender systems using multi-armed bandit
• Generalized non-stationary bandits
• Non-Stationary Off-Policy Optimization
• Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits
• How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets
• Multiscale Non-stationary Stochastic Bandits
• Joint Link Rate Selection and Channel State Change Detection in Block-Fading Channels