# Dynamic Regret of Online Markov Decision Processes

arXiv: https://arxiv.org/abs/2208.12483 · HTML: https://mlsanity.com/paper/2208.12483/

## 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 (most cited first, 30 of 39)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning to Drive in a Day](https://mlsanity.com/paper/1807.00412/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Virtual-Taobao: Virtualizing Real-world Online Retail Environment for Reinforcement Learning](https://mlsanity.com/paper/1805.10000/) (2018)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Open-environment Machine Learning](https://mlsanity.com/paper/2206.00423/) (2022)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Dynamic Regret of Policy Optimization in Non-stationary Environments](https://mlsanity.com/paper/2007.00148/) (2020)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions](https://mlsanity.com/paper/1805.10066/) (2018)

## Built on by (most cited first, 13 of 13)

- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/2403.04568/) (2024)
- [Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2411.03107/) (2024)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes](https://mlsanity.com/paper/2405.02188/) (2024)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [On the Relation Between Interval Regret and Dynamic Regret](https://mlsanity.com/paper/2609.34423/) (2026)
- [Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs](https://mlsanity.com/paper/2606.29092/) (2026)

## 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.