mlsanityData to 14 Oct 2026

Variational Regret Bounds for Reinforcement Learning

arXiv 1905.05857 ↗First posted 14 May 2019cs.LG stat.MLcited by 32

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 9; 2022: 7; 2023: 7; 2024: 3; 2025: 3; 2026: 2.

32 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  3. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  4. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  5. 2020Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learningcited by 15
  6. 2022Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualizationcited by 14
  7. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  8. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  9. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  10. 2023The complexity of non-stationary reinforcement learningcited by 7
  11. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  12. 2021Dealing with Non-Stationarity in MARL via Trust-Region Decompositioncited by 5
20 more
  1. 2021Lifelong Hyper-Policy Optimization with Multiple Importance Sampling Regularizationcited by 5
  2. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  3. 2021AdaPool: A Diurnal-Adaptive Fleet Management Framework using Model-Free Deep Reinforcement Learning and Change Point Detectioncited by 4
  4. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  5. 2024Decision Making in Non-Stationary Environments with Policy-Augmented Searchcited by 4
  6. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  7. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3
  8. 2023Action Pick-up in Dynamic Action Space Reinforcement Learningcited by 3
  9. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  10. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  11. 2022Decision Making in Non-Stationary Environments with Policy-Augmented Monte Carlo Tree Searchcited by 1
  12. 2023Online Reinforcement Learning in Periodic MDPcited by 1
  13. 2023Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehiclescited by 1
  14. 2025Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernelscited by 1
  15. 2026Model-Based Reinforcement Learning for Control under Time-Varying Dynamicscited by 1
  16. 2021Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertaintycited by 0
  17. 2022Online Reinforcement Learning for Periodic MDPcited by 0
  18. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  19. 2025Efficient Restarts in Non-Stationary Model-Free Reinforcement Learningcited by 0
  20. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0