mlsanityData to 7 Oct 2026

A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem

arXiv 1711.03539 ↗First posted 8 Nov 2017cs.LG cs.AI stat.MLcited by 48

Not on the map. Why?

Abstract (arXiv)

The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems under the piecewise-stationary setting, and study a class of change-detection based UCB (Upper Confidence Bound) policies, CD-UCB, that actively detects change points and restarts the UCB indices. We then develop CUSUM-UCB and PHT-UCB, that belong to the CD-UCB class and use cumulative sum (CUSUM) and Page-Hinkley Test (PHT) to detect changes. We show that CUSUM-UCB obtains the best known regret upper bound under mild assumptions. We also demonstrate the regret reduction of the CD-UCB policies over arbitrary Bernoulli rewards and Yahoo! datasets of webpage click-through rates.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 9; 2024: 9; 2025: 8; 2026: 7.

48 papers.

Sort:

By area:

  1. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  2. 2024Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Banditscited by 26
  3. 2022Stochastic Rising Banditscited by 18
  4. 2024Sliding-Window Thompson Sampling for Non-Stationary Settingscited by 15
  5. 2021An empirical evaluation of active inference in multi-armed banditscited by 12
  6. 2022Non-Stationary Bandits with Auto-Regressive Temporal Dependencycited by 10
  7. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  8. 2023A Definition of Non-Stationary Banditscited by 9
  9. 2021Generalized non-stationary banditscited by 8
  10. 2021On Limited-Memory Subsampling Strategies for Banditscited by 8
  11. 2021Bandit Quickest Changepoint Detectioncited by 7
  12. 2021Finite-time Analysis of Globally Nonstationary Multi-Armed Banditscited by 7
36 more
  1. 2022Non-Stationary Dueling Banditscited by 7
  2. 2021Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regretcited by 6
  3. 2022Decentralized Competing Bandits in Non-Stationary Matching Marketscited by 4
  4. 2023Discounted Thompson Sampling for Non-Stationary Bandit Problemscited by 4
  5. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  6. 2026Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Modelscited by 4
  7. 2022Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical Systemcited by 3
  8. 2023Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application to Joint Communications and Sensingcited by 3
  9. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  10. 2022Safety Aware Changepoint Detection for Piecewise i.i.d. Banditscited by 2
  11. 2023Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Banditcited by 2
  12. 2026A single algorithm for both restless and rested rotting banditscited by 2
  13. 2023MNL-Bandit in non-stationary environmentscited by 1
  14. 2023Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  15. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
  16. 2024Exploiting Adjacent Similarity in Multi-Armed Bandit Tasks via Transfer of Reward Samplescited by 1
  17. 2024Competing Bandits in Decentralized Contextual Matching Marketscited by 1
  18. 2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
  19. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  20. 2025Non-stationary Bandit Convex Optimization: A Comprehensive Studycited by 1
  21. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  22. 2021Adapting Bandit Algorithms for Settings with Sequentially Available Armscited by 0
  23. 2023Forced Exploration in Bandit Problemscited by 0
  24. 2024State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewardscited by 0
  25. 2024Partially-Observable Sequential Change-Point Detection for Autocorrelated Data via Upper Confidence Regioncited by 0
  26. 2024Improving Portfolio Optimization Results with Bandit Networkscited by 0
  27. 2024Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Banditscited by 0
  28. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  29. 2025Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Banditscited by 0
  30. 2025Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communicationscited by 0
  31. 2025BALLAST: Bandit-Assisted Learning for Latency-Aware Stable Timeouts in Raftcited by 0
  32. 2026The Cost of Learning Under Multiple Change Pointscited by 0
  33. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  34. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Banditscited by 0
  35. 2026On Non-Stationary Dynamic Pricing: Adaptivity and Optimalitycited by 0
  36. 2026You Cannot Pick a Provider From the Price List: Market-Aware Routing for Open-Weight LLM Inferencecited by 0