mlsanityData to 7 Oct 2026

Learning to Optimize under Non-Stationarity

arXiv 1810.03024 ↗First posted 6 Oct 2018cs.LG stat.MLcited by 85

Not on the map. Why?

Abstract (arXiv)

We introduce algorithms that achieve state-of-the-art dynamic regret bounds for non-stationary linear stochastic bandit setting. It captures natural applications such as dynamic pricing and ads allocation in a changing environment. We show how the difficulty posed by the non-stationarity can be overcome by a novel marriage between stochastic and adversarial bandits learning algorithms. Defining d,BT, and T as the problem dimension, the variation budget, and the total time horizon, respectively, our main contributions are the tuned Sliding Window UCB (textttSW-UCB) algorithm with optimal widetildeO(d2/3(BT+1)1/3T2/3) dynamic regret, and the tuning free bandit-over-bandit (textttBOB) framework built on top of the textttSW-UCB algorithm with best widetildeO(d2/3(BT+1)1/4T3/4) dynamic regret.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 14; 2023: 19; 2024: 5; 2025: 8; 2026: 22.

85 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  3. 2023Continual Learning as Computationally Constrained Reinforcement Learningcited by 35
  4. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  5. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  6. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  7. 2022Non-stationary Bandits with Knapsackscited by 25
  8. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  9. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  10. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  11. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  12. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
38 more
  1. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  2. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  3. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  4. 2023Multi-channel Autobidding with Budget and ROI Constraintscited by 14
  5. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  6. 2023Smooth Non-Stationary Banditscited by 13
  7. 2024Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Driftcited by 12
  8. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  9. 2021Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithmscited by 10
  10. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  11. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  12. 2023A Definition of Non-Stationary Banditscited by 9
  13. 2021Generalized non-stationary banditscited by 8
  14. 2022Adaptive Experimentation in the Presence of Exogenous Nonstationary Variationcited by 7
  15. 2021An Online Learning Approach to Optimizing Time-Varying Costs of AoIcited by 5
  16. 2023Linear Bandits with Memory: from Rotting to Risingcited by 5
  17. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  18. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  19. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  20. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5
  21. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  22. 2022Rotting Infinitely Many-armed Banditscited by 4
  23. 2023Tailoring Machine Learning for Process Miningcited by 4
  24. 2025Online Decision-Focused Learningcited by 4
  25. 2022Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical Systemcited by 3
  26. 2023Tempo Adaptation in Non-stationary Reinforcement Learningcited by 3
  27. 2024Non-Stationary Latent Auto-Regressive Banditscited by 3
  28. 2025Non-Stationary Lipschitz Banditscited by 3
  29. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  30. 2022Bridging Adversarial and Nonstationary Multi-armed Banditcited by 2
  31. 2022Competing Bandits in Time Varying Matching Marketscited by 2
  32. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  33. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  34. 2024An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraintscited by 2
  35. 2026Parameter-Free Dynamic Regret for Unconstrained Linear Banditscited by 2
  36. 2026A single algorithm for both restless and rested rotting banditscited by 2
  37. 2022Adversarial Bandits against Arbitrary Strategiescited by 1
  38. 2023Online Resource Allocation: Bandits feedback and Advice on Time-varying Demandscited by 1

50 most cited of 85 All 85 (JSON)