🤖 machine learning

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

本文通过引入纳什社会福利（Nash Social Welfare）目标以防止少数群体边缘化，为异质偏好建立了全新的 $O(T^{2/3})$ 遗憾下界，并提出了实现匹配上界的算法，从而探讨了多用户对决老虎机（multi-user dueling bandits）中的公平性问题。

原作者： Maheed H. Ahmed, Mahsa Ghasemi

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Maheed H. Ahmed, Mahsa Ghasemi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正在为数百名宾客举办大型派对的 DJ。你的任务是挑选出下一首完美的歌曲。但这里有一个挑战：你不能询问每个人，“你想听什么？”相反，你必须通过连续播放两首歌并观察人群更偏好哪一首，来做出判断。这就是**对决强盗（Dueling Bandit）**问题的基本概念：通过比较选项而非询问评分，来学习人们的喜好。

现在，想象一下这个派对被分成了不同的群体。有些喜欢重金属，有些喜欢爵士，还有一些人喜欢流行乐。如果你只是试图取悦“平均”每一个人，你最终可能会播放一种让没人真正享受的乏味混音，或者更糟的是，你可能会因为金属乐迷的声音更大声，而完全忽略了热爱爵士乐的小众群体。

这篇论文提出了一种新的 DJ 方式，旨在确保每个人都有公平的机会听到自己喜欢的音乐，而不只是让大多数人获益。

核心问题：“平均值”陷阱

在大多数计算机系统中，目标是实现“总幸福感最大化”（即所有人的享受之和）。如果 90 个人喜欢摇滚，10 个人喜欢爵士，系统将只播放摇滚。那 10 个爵士乐迷的幸福感就是零。这被认为是公平的吗？论文认为这是不公平的。它想要一个即使是“爵士乐迷”这种少数群体也不会被抛弃的系统。

解决方案：“群体幸福感”公式

为了解决这个问题，作者使用了名为**纳什社会福利（Nash Social Welfare, NSW）**的概念。

你可以这样理解：

旧方法（功利主义）： 你把每个人的幸福感相加。 $90 + 10 = 100$ 。如果你播放摇滚乐，90 个乐迷很开心，但 10 个乐迷却很痛苦。总分很高，但不公平。
新方法（纳什社会福利）： 与其相加，不如将每个人的幸福感相乘。
- 如果 10 个爵士乐迷的幸福感为 0，那么总分就会变成 0（ $90 \times 0 = 0$ ）。
- 要获得高分，每个人都必须至少拥有一点点幸福感。

这个数学技巧迫使算法去关注最小的群体。如果它忽略了爵士乐迷，那么“得分”就会崩塌。这就像一条链条：链条的强度取决于它最薄弱的一环。

算法是如何工作的

论文介绍了两种主要的策略（算法），用以寻找满足这一公平规则的最佳音乐组合（在数学领域中称为“臂/arms”）。

“先学习，后演奏”策略（Fair-Explore-Then-Commit）：
- 第一阶段（口味测试）： DJ 花大量时间播放不同的歌曲对，仅仅是为了弄清楚每个群体到底喜欢什么。他们正在寻找每个群体的“孔多塞胜者（Condorcet Winner）”——基本上就是那个能击败其他所有歌曲的特定群体的最爱。
- 第二阶段（歌单）： 一旦他们确信自己了解每个人的喜好，他们就会停止猜测，并在余下的派对时间里播放能够平衡所有人幸福感的完美混音。
“混搭”策略（Fair- $\epsilon$ -Greedy）：
- 这个策略更加灵活。它主要播放它目前已知的最佳组合，但每隔一段时间，它会故意播放一对随机的歌曲，以再次核实它的假设。如果它意识到自己对爵士乐迷的理解错了，它可以立即改变主意。这就像一位 DJ 在后备口袋里留了几首惊喜曲目，以防观众的情绪发生变化。

重大发现：公平是有代价的

作者证明了一件非常重要的事：追求公平比追求效率更难。

在旧有的“平均”系统中，DJ 可以很快地学会最好的歌曲。但在这种“公平”系统中，DJ 必须花费额外的时间去搞清楚那些安静的、少数群体的喜好，即使这会减慢找到适合大多数人的“最佳”歌曲的过程。

他们精确计算了这种速度差异。他们发现，“遗憾值（regret）”（即由于 DJ 还不了解完美歌曲而损失的幸福感）增长的速度，大约与时间的平方以及群体数量的立方根成正比。

简单翻译： 群体越多，且可选方案越多，找到一个让所有人都开心的解决方案所花费的时间，比起仅仅让大多数人开心的方案，就会长得多。

结果：它奏效了吗？

作者通过模拟和真实数据（使用了一个关于人们对寿司偏好的数据集）测试了他们的想法。

结果： 他们的“公平”算法成功地保持了较低的“基尼系数”（衡量不平等的指标）。
权衡： “不公平”的算法（那些仅仅追求总幸福最大化的算法）让大多数人非常开心，但让少数群体几乎一无所获。而“公平”算法虽然让大多数人的幸福感比不公平算法略低，但它确保了少数群体也能得到满足。
胜出者： “公平”算法实现了最高的纳什社会福利得分，这意味着它找到了最佳的平衡点，使得没有任何一个群体被完全忽视。

总结

这篇论文告诉我们，如果你想建立一个公平对待每个人的系统，你不能仅仅看平均值。你必须使用一种特殊的数学视角（纳什社会福利），这种视角会迫使系统去关心那些最小的群体。这需要花费更多的精力和时间去学习每个人的需求，但其结果是一个没有人会被冷落在外面的系统。

技术摘要：多用户对决老虎机：一种基于纳什社会福利的公平方法

问题定义

本文研究了**公平多用户对决老虎机（Fair Multi-User Dueling Bandit）**问题。在该设定下，智能体在时间跨度为 $T$ 、臂数为 $K$ 的环境下，通过来自 $D$ 个不同用户的成对偏好数据进行学习。与假设单一偏好模型或将偏好聚合为单一矩阵的标准对决老虎机不同，这项工作考虑的是每个用户 $d$ 可能拥有不同偏好矩阵 $P_d$ 的场景。

核心挑战在于如何学习一个能够平衡异质用户利益且不忽视少数群体利益的策略。标准的优化平均（功利主义）福利的方法往往倾向于统计上的多数派，从而导致对偏好迥异的用户产生不公平的结果。为了解决这个问题，作者使用**纳什社会福利（Nash Social Welfare, NSW）**来定义目标函数，该函数通过最大化用户效用的乘积来应对这一问题。这种目标函数本质上会对不平等进行惩罚，确保没有任何一个用户的效用被降至零。

一个关键的技术障碍是在这种相对设定中缺乏绝对奖励；反馈纯粹是相对的（表示两个臂中哪一个更受偏好的二元结果）。为了在相对设定中定义效用，作者假设每个用户都存在一个孔多塞获胜者（Condorcet winner）（即击败所有其他臂概率 $>0.5$ 的臂）。用户的效用则被定义为一个得分，该得分源自某个臂击败该用户特定孔多塞获胜者的概率。

方法论

理论框架

作者通过定义评分函数 $s_d(i) = 2P_{d, i, a^*_d}$ （其中 $a^*_d$ 是用户 $d$ 的孔多塞获胜者）来形式化该问题。策略 $\pi$ 对用户 $d$ 的效用为期望得分 $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$ 。全局目标是纳什社会福利：
$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$
目标是最小化相对于最大化该乘积的最优策略 $\pi^*$ 的期望累积遗憾（expected cumulative regret）。

硬度分析

论文建立了一个基本的遗憾下界 $\Omega(T^{2/3} \min(K, D)^{1/3})$ 。这一结果表明，在需要处理具有冲突孔多塞获胜者的用户时，最大化 NSW 会引入显著的硬度，这与标准对决老虎机（通常实现 $O(\log T)$ 遗憾）相比具有显著差异。这种难度源于算法必须通过“表现较差”的孔多塞获胜者（对一个用户是最优的，但对其他用户而言效用接近于零）来区分它们与“表现良好”的获胜者，从而在探索成本与瞬时遗憾之间产生权衡。

算法

提出了两种算法来实现这一目标，两者都包含了孔多塞获胜者识别阶段：

公平-先探索后提交（Fair-Explore-Then-Commit, Fair-ETC）：
- 阶段 1（识别）： 使用改进的 Dvoretzky-Kiefer-Wolfowitz 锦标赛（DKWT）算法来识别所有 $D$ 个用户的孔多塞获胜者集合 $\hat{A}^*$ 。该阶段利用共享交互同时更新所有用户的经验边际。
- 阶段 2（探索）： 估计所有臂相对于识别出的孔多塞获胜者的得分。
- 阶段 3（提交）： 计算最大化经验 NSW 的策略 $\hat{\pi}$ ，并在剩余的时间跨度内提交该策略。
公平- $\epsilon$ -贪婪算法（Fair- $\epsilon$ -Greedy）：
- 该算法在整个时间跨度内交替进行探索与利用。
- 它从相同的孔多塞获胜者识别阶段开始。
- 在每一步 $t$ ，以概率 $\epsilon_t$ 进行探索，通过播放涉及估计的孔道塞获胜者的对（使用轮询调度）来精炼得分估计。
- 以概率 $1-\epsilon_t$ 进行利用，即播放当前最大化经验 NSW 的策略。
- 探索率 $\epsilon_t$ 随时间衰减以确保收敛。

两种算法都被证明可以达到 $\tilde{O}(T^{2/3})$ 的遗憾上界，在对数因子项上与下界的对 $T$ 的依赖关系相匹配。

核心贡献

问题形式化： 首次形式化了公平多用户对决老虎机问题，基于个体孔多塞获胜者对不同用户进行建模，并采用 NSW 作为公平性目标。
遗憾下界： 推导出了 $\Omega(T^{2/3} \min(K, D)^{1/3})$ 的遗憾下界，作者声称这是第一个量化具有异质偏好的对决老虎机中公平代价的结果。
算法解决方案： 提出了 Fair-ETC 和 Fair- $\epsilon$ -Greedy 算法，并附带了与下界在 $T$ 依赖关系上相匹配的理论遗憾上界。
实证验证： 通过广泛的模拟证明，所提出的算法在公平性指标（基尼系数、最小用户福利）方面优于功利主义基准，同时保持了具有竞争力的累积遗憾。

实验结果

作者在随机生成的偏好和真实世界数据（Sushi 数据集，已聚类为宏观用户）上评估了其算法。

随机偏好： 在各种用户数量 ( $D$ ) 和臂数 ( $K$ ) 的配置下，Fair-ETC 和 Fair- $\epsilon$ -Greedy 都展示了亚线性遗憾，始终优于功利主义基准和针对用户均匀分布的基准。
公平性指标： 所提出的算法实现了最高的纳什社会福利，并且基尼系数明显低于功利主义方法。它们还维持了更高的最小用户福利，表明能更好地保护少数群体的偏好。
聚类偏好： 在存在明显多数派和少数派集群（模拟极化偏好）的场景中，功利主义算法倾向于多数派，导致高不平等。所提出的公平算法成功平衡了利益，保持了较低的基尼系数和较高的最小福利。
Sushi 数据集： 在真实数据上，所提方法在 $D=5$ 和 $D=10$ 的集群设置下均实现了最低的累积遗憾。虽然在高度碎片化的 $D=10$ 情况中，均匀分布基准显示出略好的公平性，但其遗憾表现极差。

意义与主张

本文声称是第一个量化具有异质偏好的对决老虎机中公平代价的工作，确立了 $\Omega(T^{2/3})$ 的基本遗憾下界。作者认为，其工作是迈向以人为本的机器学习的重要一步，因为仅优化平均偏好是不够的，且可能对少数群体造成伤害。

通过将纳什社会福利目标整合到对决老虎机框架中，这项工作为学习平衡效率与公平的策略提供了理论和算法基础。作者指出，其方法与之前的多智能体老虎机工作（如 Hossain 等人，2021；Jones 等人，2023）不同，因为它是在相对偏好设定而非绝对奖励设定下运行，这需要从根本上不同的效用估计技术。

论文以谦逊的态度结束，承认未来的工作可以扩展此框架至上下文对决老虎机（contextual dueling bandits）、连续动作空间，以及孔多塞获胜者假设不成立的场景（可能使用 Copeland 或 Borda 得分）。