mlsanityData to 7 Oct 2026

Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach

arXiv 2102.05406 ↗First posted 10 Feb 2021cs.LG cs.AI stat.MLcited by 98

Not on the map. Why?

Abstract (arXiv)

We propose a black-box reduction that turns a certain reinforcement learning algorithm with optimal regret in a (near-)stationary environment into another algorithm with optimal dynamic regret in a non-stationary environment, importantly without any prior knowledge on the degree of non-stationarity. By plugging different algorithms into our black-box, we provide a list of examples showing that our approach not only recovers recent results for (contextual) multi-armed bandits achieved by very specialized algorithms, but also significantly improves the state of the art for (generalized) linear bandits, episodic MDPs, and infinite-horizon MDPs in various ways. Specifically, in most cases our algorithm achieves the optimal dynamic regret widetildeO(min√LT, Delta1/3T2/3) where T is the number of rounds and L and Delta are the number and amount of changes of the world respectively, while previous works only obtain suboptimal bounds and/or require the knowledge of L and Delta.

Key facts. Cited by 98 papers in the map (data through 7 Oct 2026). Builds on 36 of its 64 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

36 of 64 references.

References · 36

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  5. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  6. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  7. 2015Strongly Adaptive Online Learningcited by 102
  8. 2018Learning to Optimize under Non-Stationaritycited by 85
  9. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  10. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  11. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  12. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
24 more
  1. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
  2. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  3. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  4. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  5. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  6. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 48
  7. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  8. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  9. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
  10. 2017Tracking the Best Expert in Non-stationary Stochastic Environmentscited by 35
  11. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  12. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  13. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  14. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  15. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  16. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 29
  17. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  18. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  19. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  20. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 23
  21. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  22. 2020Regret Balancing for Bandit and RL Model Selectioncited by 20
  23. 2019Randomized Exploration for Non-Stationary Stochastic Linear Banditscited by 18
  24. 2020Combinatorial Semi-Bandit in the Non-Stationary Environmentcited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 20; 2023: 21; 2024: 16; 2025: 16; 2026: 15.

98 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2022Open-environment Machine Learningcited by 48
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  5. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  6. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  7. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  8. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  9. 2022Performative Reinforcement Learningcited by 25
  10. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  11. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  12. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
38 more
  1. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  2. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  3. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  4. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  5. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  6. 2021Bandit Algorithms for Precision Medicinecited by 12
  7. 2022Testing Stationarity and Change Point Detection in Reinforcement Learningcited by 12
  8. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11
  9. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  10. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  11. 2024Model Assessment and Selection under Temporal Distribution Shiftcited by 10
  12. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  13. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  14. 2022Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Driftcited by 9
  15. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  16. 2023A Definition of Non-Stationary Banditscited by 9
  17. 2023A Stability Principle for Learning under Non-Stationaritycited by 9
  18. 2022Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Armscited by 8
  19. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  20. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  21. 2024Performative Reinforcement Learning with Linear Markov Decision Processcited by 8
  22. 2021Model Selection for Generic Contextual Banditscited by 7
  23. 2022Event-Triggered Time-Varying Bayesian Optimizationcited by 7
  24. 2023The complexity of non-stationary reinforcement learningcited by 7
  25. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  26. 2023Online Reinforcement Learning in Non-Stationary Context-Driven Environmentscited by 6
  27. 2025Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixabilitycited by 6
  28. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  29. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  30. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  31. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  32. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  33. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  34. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  35. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  36. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  37. 2024OMPO: A Unified Framework for RL under Policy and Dynamics Shiftscited by 4
  38. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4

50 most cited of 98 All 98 (JSON)