用标准UCB算法实现近优公平性,无需特殊设计
Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need
- 先均匀探索再用经典UCB,简单有效
- 在所有奖励分布下逼近最优公平性表现
- 适合关注群体公平的临床试验等场景
传统多臂赌博机中的遗憾度量以平均或最终奖励为基准,难以反映个体间公平性,尤其在患者分组的临床试验中。为此,近期研究引入了基于几何均值的纳什遗憾,与满足公平公理的纳什社会福利函数一致。然而现有方法需特殊算法设计和强假设(如乘法浓度不等式、非负有界奖励),无法处理高斯分布。本文证明:初始均匀探索后接标准上置信界(UCB)算法,仅依赖加法霍夫丁界即可实现近优纳什遗憾,并自然推广至亚高斯奖励。进一步将算法扩展至广义的p-均值遗憾,对所有p值统一达到近优遗憾界。相比以往工作,本方法假设更弱且性能更优。
原文摘要 · Abstract (English)
Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward. These conventional metrics often fail to address fairness among agents receiving rewards, particularly in settings where rewards are distributed across a population, such as patients in clinical trials. To address this, a recent body of work has introduced Nash regret, which evaluates performance via the geometric mean of accumulated rewards, aligning with the Nash social welfare function known for satisfying fairness axioms. To minimize Nash regret, existing approaches require specialized algorithm designs and strong assumptions, such as multiplicative concentration inequalities and bounded, non-negative rewards, making them unsuitable for even Gaussian reward distributions. We demonstrate that an initial uniform exploration phase followed by a standard Upper Confidence Bound (UCB) algorithm achieves near-optimal Nash regret, while relying only on additive Hoeffding bounds, and naturally extending to sub-Gaussian rewards. Furthermore, we generalize the algorithm to a broad class of fairness metrics called the $p$-mean regret, proving (nearly) optimal regret bounds uniformly across all $p$ values. This is in contrast to prior work, which made extremely restrictive assumptions on the bandit instances and even then achieved suboptimal regret bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。