# Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities

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

## Key facts

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

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

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Tactical Optimism and Pessimism for Deep Reinforcement Learning](https://mlsanity.com/paper/2102.03765/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.11489/) (2022)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Communication Efficient Parallel Reinforcement Learning](https://mlsanity.com/paper/2102.10740/) (2021)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning](https://mlsanity.com/paper/2302.08617/) (2023)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling](https://mlsanity.com/paper/2502.05434/) (2025)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)
- [Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2405.18793/) (2024)
- [Learning Optimal Admission Control in Partially Observable Queueing Networks](https://mlsanity.com/paper/2308.02391/) (2023)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)

## Abstract (arXiv)

We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret tildeO(√DSAT) up to logarithmic factors, and so our work closes a gap with the lower bound without additional assumptions on the MDP. We perform experiments in a variety of environments that validates the theoretical bounds as well as prove UCRL-V to be better than the state-of-the-art algorithms.