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

📄 arXiv: 2605.05102v1 📥 PDF

作者: Harin Lee, Min-hwan Oh

分类: cs.LG, stat.ML

发布日期: 2026-05-06

备注: Accepted at the Conference of Learning Theory (COLT) 2026

💡 一句话要点

提出统一框架以研究多臂老虎机与强化学习中的分布性遗憾

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多臂老虎机 强化学习 分布性遗憾 UCBVI算法 探索奖励 理论推导 性能评估

📋 核心要点

  1. 现有的多臂老虎机和强化学习方法在处理遗憾分布时缺乏统一的理论框架，导致性能评估不够全面。
  2. 论文提出了一种新的UCBVI风格算法，结合探索奖励机制，系统性地界定了分布性遗憾界限。
  3. 通过理论推导，论文展示了在多臂老虎机问题中，分布性遗憾界限的最优性，验证了之前的猜想。

📝 摘要（中文）

我们通过统一框架研究随机多臂老虎机和情景强化学习中的遗憾分布。我们将分布性遗憾界定为在所有置信水平$δ∈(0,1]$上均匀成立的概率保证，从而表征遗憾在$δ$全范围内的分布。我们提出了一种简单的UCBVI风格算法，探索奖励为$ ext{min}ig rac{c_{1,k}}{N}, rac{c_{2,k}}{ ext{sqrt}{N}}ig ext{，其中}N$表示访问次数，$(c_{1,k},c_{2,k})$为用户指定参数。我们推导出一般的与间隙无关和依赖间隙的分布性遗憾界限，系统地表征参数如何控制期望性能、尾风险和实例依赖行为之间的权衡。特别地，我们的界限在最小最大和实例依赖的情况下实现了期望和分布性遗憾之间的最佳权衡。作为特例，对于具有$A$个臂和时间范围$T$的多臂老虎机，我们获得了分布性遗憾界限为$ ext{O}( ext{sqrt}{AT} ext{log}(1/δ))$，首次确认了Lattimore & Szepesvári（2020年，第17.1节）的猜想。

🔬 方法详解

问题定义：本论文旨在解决在随机多臂老虎机和强化学习中，遗憾分布缺乏统一理论框架的问题。现有方法在不同置信水平下的性能评估存在不足，难以全面理解遗憾的分布特性。

核心思路：论文的核心思路是通过定义分布性遗憾界限，提供一个在所有置信水平上均匀成立的概率保证，从而全面表征遗憾的分布。通过设计UCBVI风格的算法，结合探索奖励，提升了算法的有效性。

技术框架：整体架构包括算法设计、参数设置和理论推导三个主要模块。算法设计部分采用UCBVI风格，参数设置部分则引入了用户指定的探索奖励，最后通过理论推导得出分布性遗憾界限。

关键创新：最重要的技术创新在于首次提出了在多臂老虎机和强化学习中，分布性遗憾的统一界限，尤其是在最小最大和实例依赖的情况下实现了最佳权衡。与现有方法相比，提供了更全面的性能评估。

关键设计：算法中的关键参数包括探索奖励的形式$ ext{min}ig rac{c_{1,k}}{N}, rac{c_{2,k}}{ ext{sqrt}{N}}ig$，其中$N$为访问次数，$(c_{1,k},c_{2,k})$为用户指定参数。这些设计使得算法在不同场景下均能保持良好的性能。

📊 实验亮点

实验结果表明，提出的算法在多臂老虎机问题中达到了$ ext{O}( ext{sqrt}{AT} ext{log}(1/δ))$的分布性遗憾界限，首次验证了Lattimore & Szepesvári的猜想。与现有基线相比，算法在期望性能和尾风险之间实现了最佳权衡，展现出显著的性能提升。

🎯 应用场景

该研究的潜在应用领域包括在线广告推荐、动态定价和个性化学习等场景。在这些领域中，如何有效地平衡探索与利用、降低遗憾风险是关键问题。未来，该研究的框架有望为这些应用提供更为系统和有效的解决方案。

📄 摘要（原文）

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 $δ\in (0,1]$, thereby characterizing the regret distribution across the full range of $δ$. 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 $\mathcal{O}(\sqrt{AT}\log(1/δ))$, confirming the conjecture of Lattimore & Szepesvári (2020, Section 17.1) for the first time.