mlsanityData to 7 Oct 2026

Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs

arXiv 1803.01626 ↗First posted 5 Mar 2018stat.ML cs.LG cs.SYcited by 41

Not on the map. Why?

Abstract (arXiv)

The problem of reinforcement learning in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion is considered, when the learner interacts with the system in a single stream of observations, starting from an initial state without any reset. We revisit the minimax lower bound for that problem by making appear the local variance of the bias function in place of the diameter of the MDP. Furthermore, we provide a novel analysis of the KL-UCRL algorithm establishing a high-probability regret bound scaling as widetilde mathcal OBigl(textstyle √Ssums,abf V^stars,aTBig) for this algorithm for ergodic MDPs, where S denotes the number of states and where bf V^stars,a is the variance of the bias function with respect to the next-state distribution following action a in state s. The resulting bound improves upon the best previously known regret bound widetilde mathcal O(DS√AT) for that algorithm, where A and D respectively denote the maximum number of actions (per state) and the diameter of MDP. We finally compare the leading terms of the two bounds in some benchmark MDPs indicating that the derived bound can provide an order of magnitude improvement in some cases. Our analysis leverages novel variations of the transportation lemma combined with Kullback-Leibler concentration inequalities, that we believe to be of independent interest.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 10; 2023: 5; 2024: 11; 2025: 5; 2026: 3.

41 papers.

Sort:

By area:

  1. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  2. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  3. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  5. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  6. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  7. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  8. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  9. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  10. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  11. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  12. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
29 more
  1. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  2. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  3. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  4. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  5. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  6. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  7. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  8. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  9. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  10. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  11. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  12. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  13. 2024Allocation Stability and Wald Inference under Variance-Aware UCBcited by 4
  14. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  15. 2025Best Policy Learning from Trajectory Preference Feedbackcited by 3
  16. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  17. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  18. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  19. 2023Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithmscited by 2
  20. 2024Scale-free Adversarial Reinforcement Learningcited by 2
  21. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  22. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  23. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  24. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  25. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  26. 2024Reinforcement Learning and Regret Bounds for Admission Controlcited by 0
  27. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
  28. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  29. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0