# Tail Distribution of Regret in Optimistic Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 25 references that are in the map.
- First posted on arXiv 23 Nov 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 17 of 17)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Optimizing the CVaR via Sampling](https://mlsanity.com/paper/1404.3862/) (2014)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents](https://mlsanity.com/paper/2301.12601/) (2023)
- [Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes](https://mlsanity.com/paper/2006.13405/) (2020)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)

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

- [Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning](https://mlsanity.com/paper/2605.05102/) (2026)

## Abstract (arXiv)

We derive instance-dependent tail bounds for the regret of optimism-based reinforcement learning in finite-horizon tabular Markov decision processes with unknown transition dynamics. We first study a UCBVI-type (model-based) algorithm and characterize the tail distribution of the cumulative regret RK over K episodes via explicit bounds on P(RK ≥ x), going beyond analyses limited to E[RK] or a single high-probability quantile. We analyze two natural exploration-bonus schedules for UCBVI: (i) a K-dependent scheme that explicitly incorporates the total number of episodes K, and (ii) a K-independent (anytime) scheme that depends only on the current episode index. We then complement the model-based results with an analysis of optimistic Q-learning (model-free) under a K-dependent bonus schedule. Across both the model-based and model-free settings, we obtain upper bounds on P(RK ≥ x) with a distinctive two-regime structure: a sub-Gaussian tail starting from an instance-dependent scale up to a transition threshold, followed by a sub-Weibull tail beyond that point. We further derive corresponding instance-dependent bounds on the expected regret E[RK]. The proposed algorithms depend on a tuning parameter α, which balances the expected regret and the range over which the regret exhibits sub-Gaussian decay.