# Improved Analysis of UCRL2 with Empirical Bernstein Inequality

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2020.

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

- [Understanding Domain Randomization for Sim-to-real Transfer](https://mlsanity.com/paper/2110.03239/) (2021)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Optimism and Delays in Episodic Reinforcement Learning](https://mlsanity.com/paper/2111.07615/) (2021)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)
- [Optimistic World Models: Efficient Exploration in Model-Based Deep Reinforcement Learning](https://mlsanity.com/paper/2602.10044/) (2026)
- [Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span](https://mlsanity.com/paper/2410.14992/) (2024)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Provably Efficient Exploration in Reward Machines with Low Regret](https://mlsanity.com/paper/2412.19194/) (2024)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Tail Distribution of Regret in Optimistic Reinforcement Learning](https://mlsanity.com/paper/2511.18247/) (2025)
- [Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model](https://mlsanity.com/paper/2604.16111/) (2026)
- [A Cover Time Study of a non-Markovian Algorithm](https://mlsanity.com/paper/2306.04902/) (2023)
- [On Reward Structures of Markov Decision Processes](https://mlsanity.com/paper/2308.14919/) (2023)
- [Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding](https://mlsanity.com/paper/2602.00781/) (2026)
- [Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2608.07725/) (2026)

## Abstract (arXiv)

We consider the problem of exploration-exploitation in communicating Markov Decision Processes. We provide an analysis of UCRL2 with Empirical Bernstein inequalities (UCRL2B). For any MDP with S states, A actions, Gamma ≤ S next states and diameter D, the regret of UCRL2B is bounded as widetildeO(√DGamma S A T).