mlsanityData to 14 Oct 2026

A Simple Approach for Non-stationary Linear Bandits

arXiv 2103.05324 ↗First posted 9 Mar 2021cs.LGcited by 54

Not on the map. Why?

Abstract (arXiv)

This paper investigates the problem of non-stationary linear bandits, where the unknown regression parameter is evolving over time. Existing studies develop various algorithms and show that they enjoy an widetildeO(T2/3PT1/3) dynamic regret, where T is the time horizon and PT is the path-length that measures the fluctuation of the evolving unknown parameter. In this paper, we discover that a serious technical flaw makes their results ungrounded, and then present a fix, which gives an widetildeO(T3/4PT1/4) dynamic regret without modifying original algorithms. Furthermore, we demonstrate that instead of using sophisticated mechanisms, such as sliding window or weighted penalty, a simple restarted strategy is sufficient to attain the same regret guarantee. Specifically, we design an UCB-type algorithm to balance exploitation and exploration, and restart it periodically to handle the drift of unknown parameters. Our approach enjoys an widetildeO(T3/4PT1/4) dynamic regret. Note that to achieve this bound, the algorithm requires an oracle knowledge of the path-length PT. Combining the bandits-over-bandits mechanism by treating our algorithm as the base learner, we can further achieve the same regret bound in a parameter-free way. Empirical studies also validate the effectiveness of our approach.

Key facts. Cited by 54 papers in the map (data through 14 Oct 2026). Builds on 20 of its 43 references that are in the map. First posted on arXiv 9 Mar 2021.

Builds on

20 of 43 references.

References · 20

  1. 2013Non-stationary Stochastic Optimizationcited by 175
  2. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2015Strongly Adaptive Online Learningcited by 107
  5. 2016Corralling a Band of Bandit Algorithmscited by 100
  6. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  7. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  8. 2018Learning to Optimize under Non-Stationaritycited by 85
  9. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  10. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  11. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  12. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 50
8 more
  1. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  2. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 42
  3. 2019Bandit Convex Optimization in Non-stationary Environmentscited by 41
  4. 2020Minimizing Dynamic Regret and Adaptive Regret Simultaneouslycited by 31
  5. 2015Online Stochastic Linear Optimization under One-bit Feedbackcited by 26
  6. 2019Randomized Exploration for Non-Stationary Stochastic Linear Banditscited by 18
  7. 2017Distribution-Free One-Pass Learningcited by 10
  8. 2019Equipping Experts/Bandits with Long-term Memorycited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 11; 2023: 13; 2024: 6; 2025: 12; 2026: 6.

54 papers.

Sort:

By area:

  1. 2022Recent Advances in Bayesian Optimizationcited by 76
  2. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  3. 2022Open-environment Machine Learningcited by 48
  4. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  5. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  6. 2021Distribution-free Contextual Dynamic Pricingcited by 22
  7. 2024Adaptive Memory Replay for Continual Learningcited by 22
  8. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  9. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  10. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  11. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  12. 2022Dynamic Regret of Online Markov Decision Processescited by 13
38 more
  1. 2024Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Driftcited by 13
  2. 2022Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learningcited by 9
  3. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  4. 2023A Definition of Non-Stationary Banditscited by 9
  5. 2023Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender Systemcited by 7
  6. 2023Linear Bandits with Memory: from Rotting to Risingcited by 6
  7. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6
  8. 2024Causally Abstracted Multi-armed Banditscited by 6
  9. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  10. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  11. 2025Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customizationcited by 5
  12. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  13. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  14. 2022Rotting Infinitely Many-armed Banditscited by 4
  15. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  16. 2022Competing Bandits in Time Varying Matching Marketscited by 3
  17. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  18. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  19. 2025Overcoming Non-stationary Dynamics with Evidential Proximal Policy Optimizationcited by 2
  20. 2023Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Banditscited by 1
  21. 2023MNL-Bandit in non-stationary environmentscited by 1
  22. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
  23. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  24. 2025Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticitycited by 1
  25. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  26. 2026Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendationscited by 1
  27. 2021When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solutioncited by 0
  28. 2022Bayesian Non-stationary Linear Bandits for Large-Scale Recommender Systemscited by 0
  29. 2023Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oraclecited by 0
  30. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0
  31. 2023Learning to Seek: Multi-Agent Online Source Seeking Against Non-Stochastic Disturbancescited by 0
  32. 2023Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Banditscited by 0
  33. 2024Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Banditscited by 0
  34. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  35. 2025An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical Systemcited by 0
  36. 2025Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Armscited by 0
  37. 2025Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewardscited by 0
  38. 2025Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communicationscited by 0

50 most cited of 54 All 54 (JSON)