# Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2018.

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

- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer](https://mlsanity.com/paper/2509.18648/) (2025)
- [Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents](https://mlsanity.com/paper/2410.22908/) (2024)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Best Policy Learning from Trajectory Preference Feedback](https://mlsanity.com/paper/2501.18873/) (2025)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)

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