# Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

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

## 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 2 of its 36 references that are in the map.
- First posted on arXiv 6 May 2026.

## 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, 2 of 2)

- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Tail Distribution of Regret in Optimistic Reinforcement Learning](https://mlsanity.com/paper/2511.18247/) (2025)

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

- [Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy](https://mlsanity.com/paper/2606.23096/) (2026)

## Abstract (arXiv)

We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels δ ∈ (0,1], thereby characterizing the regret distribution across the full range of δ. We present a simple UCBVI-style algorithm with exploration bonus minc1,k/N, c2,k/√N, where N denotes the visit count and (c1,k,c2,k) are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with A arms and horizon T, we obtain a distributional regret bound of order O(√ATlog(1/δ)), confirming the conjecture of Lattimore & Szepesv'ari (2020, Section 17.1) for the first time.