mlsanityData to 7 Oct 2026

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

arXiv 1802.03692 ↗First posted 11 Feb 2018stat.ML cs.LGcited by 49

Not on the map. Why?

Abstract (arXiv)

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(√MKTlog 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.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

49 papers.

Sort:

By area:

  1. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  2. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  3. 2024Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Banditscited by 26
  4. 2022Stochastic Rising Banditscited by 18
  5. 2025BanditSpec: Adaptive Speculative Decoding via Bandit Algorithmscited by 18
  6. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  7. 2021Bandit Algorithms for Precision Medicinecited by 12
  8. 2022Testing Stationarity and Change Point Detection in Reinforcement Learningcited by 12
  9. 2022Non-Stationary Bandits with Auto-Regressive Temporal Dependencycited by 10
  10. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  11. 2022Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learningcited by 9
  12. 2023A Definition of Non-Stationary Banditscited by 9
37 more
  1. 2021Generalized non-stationary banditscited by 8
  2. 2021On Limited-Memory Subsampling Strategies for Banditscited by 8
  3. 2021Finite-time Analysis of Globally Nonstationary Multi-Armed Banditscited by 7
  4. 2022Non-Stationary Dueling Banditscited by 7
  5. 2021Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regretcited by 6
  6. 2022Collaborative Algorithms for Online Personalized Mean Estimationcited by 5
  7. 2021Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Banditscited by 4
  8. 2023Discounted Thompson Sampling for Non-Stationary Bandit Problemscited by 4
  9. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  10. 2022Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical Systemcited by 3
  11. 2021Dynamic Pricing and Learning under the Bass Modelcited by 2
  12. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  13. 2022Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networkscited by 2
  14. 2026A single algorithm for both restless and rested rotting banditscited by 2
  15. 2023Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  16. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
  17. 2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
  18. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  19. 2025Non-stationary Bandit Convex Optimization: A Comprehensive Studycited by 1
  20. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  21. 2021Adaptively Optimize Content Recommendation Using Multi Armed Bandit Algorithms in E-commercecited by 0
  22. 2022Learning to Price Supply Chain Contracts against a Learning Retailercited by 0
  23. 2023Forced Exploration in Bandit Problemscited by 0
  24. 2024Partially-Observable Sequential Change-Point Detection for Autocorrelated Data via Upper Confidence Regioncited by 0
  25. 2024Improving Portfolio Optimization Results with Bandit Networkscited by 0
  26. 2024Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Banditscited by 0
  27. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  28. 2025Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Banditscited by 0
  29. 2025Fooling Algorithms in Non-Stationary Bandits using Belief Inertiacited by 0
  30. 2026Adaptive Exploration for Latent-State Banditscited by 0
  31. 2026The Cost of Learning Under Multiple Change Pointscited by 0
  32. 2026A Modularized Framework for Piecewise-Stationary Restless Banditscited by 0
  33. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  34. 2026The Sample Complexity of Multiple Change Point Identification under Bandit Feedbackcited by 0
  35. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Banditscited by 0
  36. 2026From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensingcited by 0
  37. 2026You Cannot Pick a Provider From the Price List: Market-Aware Routing for Open-Weight LLM Inferencecited by 0