Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
arXiv:2107.11419
Abstract
We consider nonstationary multi-armed bandit problems where the model parameters of the arms change over time. We introduce the adaptive resetting bandit (ADR-bandit), a bandit algorithm class that leverages adaptive windowing techniques from literature on data streams. We first provide new guarantees on the quality of estimators resulting from adaptive windowing techniques, which are of independent interest. Furthermore, we conduct a finite-time analysis of ADR-bandit in two typical environments: an abrupt environment where changes occur instantaneously and a gradual environment where changes occur progressively. We demonstrate that ADR-bandit has nearly optimal performance when abrupt or gradual changes occur in a coordinated manner that we call global changes. We demonstrate that forced exploration is unnecessary when we assume such global changes. Unlike the existing nonstationary bandit algorithms, ADR-bandit has optimal performance in stationary environments as well as nonstationary environments with global changes. Our experiments show that the proposed algorithms outperform the existing approaches in synthetic and real-world environments.
arXiv commentRevision: Regret bound for ADR-Bandit + TS
References in corpus (16)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
- Exponentially Weighted Moving Average Charts for Detecting Concept Drift
- The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
- Further Optimal Regret Bounds for Thompson Sampling
- Combinatorial Multi-Armed Bandit with General Reward Functions
- Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays
- Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
- A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
- Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection
- Tracking the Best Expert in Non-stationary Stochastic Environments
- Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
- KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints
- On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems
- A single algorithm for both restless and rested rotting bandits
- Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits