mlsanityData to 14 Oct 2026

Dynamic Regret of Online Markov Decision Processes

arXiv 2208.12483 ↗First posted 26 Aug 2022cs.LG stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

We investigate online Markov Decision Processes (MDPs) with adversarially changing loss functions and known transitions. We choose dynamic regret as the performance measure, defined as the performance difference between the learner and any sequence of feasible changing policies. The measure is strictly stronger than the standard static regret that benchmarks the learner's performance with a fixed compared policy. We consider three foundational models of online MDPs, including episodic loop-free Stochastic Shortest Path (SSP), episodic SSP, and infinite-horizon MDPs. For these three models, we propose novel online ensemble algorithms and establish their dynamic regret guarantees respectively, in which the results for episodic (loop-free) SSP are provably minimax optimal in terms of time horizon and certain non-stationarity measure. Furthermore, when the online environments encountered by the learner are predictable, we design improved algorithms and achieve better dynamic regret bounds for the episodic (loop-free) SSP; and moreover, we demonstrate impossibility results for the infinite-horizon MDPs.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 39 of its 70 references that are in the map. First posted on arXiv 26 Aug 2022.

Builds on

39 of 70 references.

References · 39

  1. 2015Trust Region Policy Optimizationcited by 2,580
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2018Learning to Drive in a Daycited by 273
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2013Non-stationary Stochastic Optimizationcited by 175
  8. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  9. 2015Strongly Adaptive Online Learningcited by 107
  10. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  11. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  12. 2019Online Control with Adversarial Disturbancescited by 92
27 more
  1. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  3. 2018Virtual-Taobao: Virtualizing Real-world Online Retail Environment for Reinforcement Learningcited by 80
  4. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  5. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  6. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 66
  7. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  8. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  9. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  10. 2022Open-environment Machine Learningcited by 48
  11. 2019Bandit Convex Optimization in Non-stationary Environmentscited by 41
  12. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 40
  13. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  14. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
  15. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  16. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  17. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  18. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 31
  19. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
  20. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  21. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 28
  22. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  23. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  24. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  25. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  26. 2018Online learning over a finite action set with limited switchingcited by 21
  27. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 5; 2025: 1; 2026: 2.

13 papers.

Sort:

By area:

  1. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  2. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  3. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  4. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  5. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  6. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  7. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  8. 2024Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Informationcited by 2
  9. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  10. 2024Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processescited by 1
  11. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  12. 2026On the Relation Between Interval Regret and Dynamic Regretcited by 1
1 more
  1. 2026Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPscited by 0