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

arXiv:2605.05102v1 Announce Type: new Abstract: 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 elta in (0,1], thereby characterizing the regret distribution across the full range of elta. We present a simple UCBVI-style algorithm with exploration bonus min{c_{1,k}/N, c_{2,k}/sqrt{N}}, where N denotes the visit count and (c_{1,k},c_{2,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(sqrt{AT}log(1/elta)), confirming the conjecture of Lattimore & Szepesvari (2020, Section 17.1) for the first time.

Source: arXiv cs.LG | 2026-05-07