# Tightening Exploration in Upper Confidence Reinforcement Learning

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2020.

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

- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)
- [Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms](https://mlsanity.com/paper/2206.08776/) (2022)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithms](https://mlsanity.com/paper/2105.02135/) (2021)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [Online Reinforcement Learning in Periodic MDP](https://mlsanity.com/paper/2303.09629/) (2023)
- [Safety through Permissibility: Shield Construction for Fast and Safe Reinforcement Learning](https://mlsanity.com/paper/2405.19414/) (2024)
- [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)
- [Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2510.03181/) (2025)
- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)
- [The Confusing Instance Principle for Online Linear Quadratic Control](https://mlsanity.com/paper/2510.19531/) (2025)
- [Tail Distribution of Regret in Optimistic Reinforcement Learning](https://mlsanity.com/paper/2511.18247/) (2025)
- [Online Reinforcement Learning for Periodic MDP](https://mlsanity.com/paper/2207.12045/) (2022)
- [Utilizing Maximum Mean Discrepancy Barycenter for Propagating the Uncertainty of Value Functions in Reinforcement Learning](https://mlsanity.com/paper/2404.00686/) (2024)
- [Reinforcement Learning and Regret Bounds for Admission Control](https://mlsanity.com/paper/2406.04766/) (2024)
- [How to Shrink Confidence Sets for Many Equivalent Discrete Distributions?](https://mlsanity.com/paper/2407.15662/) (2024)
- [Learning in Markovian bandits with non-observable states and constrained decision epochs](https://mlsanity.com/paper/2606.27448/) (2026)
- [Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2608.07725/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

The upper confidence reinforcement learning (UCRL2) algorithm introduced in (Jaksch et al., 2010) is a popular method to perform regret minimization in unknown discrete Markov Decision Processes under the average-reward criterion. Despite its nice and generic theoretical regret guarantees, this algorithm and its variants have remained until now mostly theoretical as numerical experiments in simple environments exhibit long burn-in phases before the learning takes place. In pursuit of practical efficiency, we present UCRL3, following the lines of UCRL2, but with two key modifications: First, it uses state-of-the-art time-uniform concentration inequalities to compute confidence sets on the reward and (component-wise) transition distributions for each state-action pair. Furthermore, to tighten exploration, it uses an adaptive computation of the support of each transition distribution, which in turn enables us to revisit the extended value iteration procedure of UCRL2 to optimize over distributions with reduced support by disregarding low probability transitions, while still ensuring near-optimism. We demonstrate, through numerical experiments in standard environments, that reducing exploration this way yields a substantial numerical improvement compared to UCRL2 and its variants. On the theoretical side, these key modifications enable us to derive a regret bound for UCRL3 improving on UCRL2, that for the first time makes appear notions of local diameter and local effective support, thanks to variance-aware concentration bounds.