统一建模强化学习中后悔分布，实现对风险与性能的精细权衡。
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
- 提出带探索奖励的统一算法，通过参数控制风险与收益平衡。
- 在多臂赌博机中首次证明了√(AT log(1/δ))的分布后悔界。
- 适用于关注尾部风险或需稳健策略的研究者与工程师。
我们通过统一框架研究随机多臂赌博机与周期性强化学习中的后悔分布。将分布后悔界形式化为对所有置信水平 δ∈(0,1] 均成立的概率保证，从而刻画后悔分布的全范围行为。提出一种类似UCBVI的简单算法，探索奖励为 min{c₁ₖ/N, c₂ₖ/√N}，其中 N 为访问次数，(c₁ₖ,c₂ₖ) 为用户指定参数。针对任意参数序列，推导出一般性的无间隙与有间隙分布后悔界，揭示参数如何控制期望性能、尾部风险与实例相关行为之间的权衡。特别地，所获界在极小化与实例相关两种情形下均达到最优。作为特例，在含 A 个臂、时长为 T 的多臂赌博机中，首次获得分布后悔界为 O(√(AT log(1/δ))），证实了 Lattimore & Szepesvári (2020, Section 17.1) 的猜想。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。