# Variational Regret Bounds for Reinforcement Learning

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2019.

## Built on by (most cited first, 30 of 32)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2006.16785/) (2020)
- [Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualization](https://mlsanity.com/paper/2209.00347/) (2022)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Dealing with Non-Stationarity in MARL via Trust-Region Decomposition](https://mlsanity.com/paper/2102.10616/) (2021)
- [Lifelong Hyper-Policy Optimization with Multiple Importance Sampling Regularization](https://mlsanity.com/paper/2112.06625/) (2021)
- [Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2411.03107/) (2024)
- [AdaPool: A Diurnal-Adaptive Fleet Management Framework using Model-Free Deep Reinforcement Learning and Change Point Detection](https://mlsanity.com/paper/2104.00203/) (2021)
- [Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems](https://mlsanity.com/paper/2111.03772/) (2021)
- [Decision Making in Non-Stationary Environments with Policy-Augmented Search](https://mlsanity.com/paper/2401.03197/) (2024)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Markov Decision Processes with Long-Term Average Constraints](https://mlsanity.com/paper/2106.06680/) (2021)
- [Action Pick-up in Dynamic Action Space Reinforcement Learning](https://mlsanity.com/paper/2304.00873/) (2023)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2304.00232/) (2023)
- [Decision Making in Non-Stationary Environments with Policy-Augmented Monte Carlo Tree Search](https://mlsanity.com/paper/2202.13003/) (2022)
- [Online Reinforcement Learning in Periodic MDP](https://mlsanity.com/paper/2303.09629/) (2023)
- [Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehicles](https://mlsanity.com/paper/2312.13910/) (2023)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Model-Based Reinforcement Learning for Control under Time-Varying Dynamics](https://mlsanity.com/paper/2604.02260/) (2026)
- [Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty](https://mlsanity.com/paper/2106.08477/) (2021)
- [Online Reinforcement Learning for Periodic MDP](https://mlsanity.com/paper/2207.12045/) (2022)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)

## Abstract (arXiv)

We consider undiscounted reinforcement learning in Markov decision processes (MDPs) where both the reward functions and the state-transition probabilities may vary (gradually or abruptly) over time. For this problem setting, we propose an algorithm and provide performance guarantees for the regret evaluated against the optimal non-stationary policy. The upper bound on the regret is given in terms of the total variation in the MDP. This is the first variational regret bound for the general reinforcement learning setting.