On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

Abstract

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.

24 pages

References in corpus (1)

• Cognitive Medium Access: Exploration, Exploitation and Competition

Cited by in corpus (42)

• Agent57: Outperforming the Atari Human Benchmark
• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Learning Contextual Bandits in a Non-stationary Environment
• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection
• Joint estimation of intersecting context tree models
• Semi-globally Exponential Trajectory Tracking for a Class of Spherical Robots
• A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem
• Non-Stationary Bandits with Habituation and Recovery Dynamics
• Online Stochastic Optimization with Wasserstein Based Non-stationarity
• Latent Bandits Revisited
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Online learning with Corrupted context: Corrupted Contextual Bandits
• Learning Adaptive Exploration Strategies in Dynamic Environments Through Informed Policy Regularization
• Multi-Armed Bandit Strategies for Non-Stationary Reward Distributions and Delayed Feedback Processes
• Recommendation System-based Upper Confidence Bound for Online Advertising
• Optimizing for the Future in Non-Stationary MDPs
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Diversity-Driven Selection of Exploration Strategies in Multi-Armed Bandits
• Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
• Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates
• Constrained Thompson Sampling for Wireless Link Optimization
• Hot Swapping for Online Adaptation of Optimization Hyperparameters
• Adaptively Optimize Content Recommendation Using Multi Armed Bandit Algorithms in E-commerce
• Non-Stationary Latent Bandits
• Learning User Preferences in Non-Stationary Environments
• Finite-time Analysis for the Knowledge-Gradient Policy
• Accelerated learning from recommender systems using multi-armed bandit
• On Limited-Memory Subsampling Strategies for Bandits
• Non-Stationary Off-Policy Optimization
• Generalized non-stationary bandits
• When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution
• Reactive Video Caching via long-short-term fusion approach
• MOLTE: a Modular Optimal Learning Testing Environment
• Smooth Sequential Optimisation with Delayed Feedback
• Bandits with Temporal Stochastic Constraints
• Multi-armed Bandit Problem with Known Trend
• Multiscale Non-stationary Stochastic Bandits
• On Distributed Multi-player Multiarmed Bandit Problems in Abruptly Changing Environment
• Scenario Approach for Robust Blackbox Optimization in the Bandit Setting