Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits

📄 arXiv: 2402.05575v1 📥 PDF

作者: Subham Pokhriyal, Shweta Jain, Ganesh Ghalme, Swapnil Dhamal, Sujit Gujar

分类: cs.LG, cs.AI, cs.CY, cs.MA

发布日期: 2024-02-08

备注: Accepted in AAMAS 2024

💡 一句话要点

提出双层公平性以解决随机多臂老虎机中的公平性问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 随机多臂老虎机 公平性 双层公平性 优点公平性 UCB算法 资源分配 在线广告

📋 核心要点

  1. 现有方法主要关注单个臂的曝光保证，未能有效处理臂的分组情况，导致公平性不足。
  2. 本文提出双层公平性，确保每个组的最低曝光量，并在组内实现基于优点的公平性。
  3. 实验结果表明，BF-UCB算法在后悔值上实现了次线性增长，且在曝光保证方面优于现有算法。

📝 摘要（中文）

现有的随机多臂老虎机（MAB）公平性方法主要关注单个臂的曝光保证。当臂根据某些属性自然分组时，本文提出了双层公平性（Bi-Level Fairness），考虑了两个层次的公平性。在第一个层次上，双层公平性保证每个组的最低曝光量。为了解决组内单个臂的拉取不平衡问题，第二个层次引入了基于优点的公平性，确保每个臂根据其在组内的优点被拉取。我们的工作表明，可以通过适应基于UCB的算法来实现双层公平性，提供随时的组曝光公平性保证，并确保组内的个体优点公平性。通过模拟实验，我们进一步展示了BF-UCB算法在后悔值上实现了次线性增长，并在组和个体曝光保证方面优于现有算法。

🔬 方法详解

问题定义：本文解决随机多臂老虎机中的公平性问题，现有方法未能有效处理臂的分组情况，导致曝光不均和优点不平衡的问题。

核心思路：提出双层公平性，第一层保证每个组的最低曝光量，第二层确保组内每个臂根据其优点被拉取，从而实现公平性与效益的平衡。

技术框架：算法BF-UCB基于UCB框架，分为两个主要模块：组曝光公平性模块和优点公平性模块，分别处理组间和组内的公平性问题。

关键创新：最重要的创新在于将公平性分为两个层次，首次在随机多臂老虎机中实现了组曝光和优点公平性的同时保证，显著提升了公平性效果。

关键设计：BF-UCB算法通过优化拉取策略，平衡组曝光公平性和优点公平性，确保后悔值的上限为O(√T)，并通过参数调节实现最佳性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，BF-UCB算法在后悔值上实现了次线性增长，优于现有算法，并且在组和个体曝光保证方面提供了更好的结果。具体而言，BF-UCB在不显著降低奖励的情况下，达到了O(√T)的后悔值上限，展现了其优越性。

🎯 应用场景

该研究的潜在应用领域包括在线广告投放、推荐系统和资源分配等场景，能够有效提升不同用户群体的公平性和满意度。未来，该方法有望在多种需要公平性考量的决策系统中得到广泛应用，推动相关领域的研究与实践。

📄 摘要（原文）

Existing approaches to fairness in stochastic multi-armed bandits (MAB) primarily focus on exposure guarantee to individual arms. When arms are naturally grouped by certain attribute(s), we propose Bi-Level Fairness, which considers two levels of fairness. At the first level, Bi-Level Fairness guarantees a certain minimum exposure to each group. To address the unbalanced allocation of pulls to individual arms within a group, we consider meritocratic fairness at the second level, which ensures that each arm is pulled according to its merit within the group. Our work shows that we can adapt a UCB-based algorithm to achieve a Bi-Level Fairness by providing (i) anytime Group Exposure Fairness guarantees and (ii) ensuring individual-level Meritocratic Fairness within each group. We first show that one can decompose regret bounds into two components: (a) regret due to anytime group exposure fairness and (b) regret due to meritocratic fairness within each group. Our proposed algorithm BF-UCB balances these two regrets optimally to achieve the upper bound of $O(\sqrt{T})$ on regret; $T$ being the stopping time. With the help of simulated experiments, we further show that BF-UCB achieves sub-linear regret; provides better group and individual exposure guarantees compared to existing algorithms; and does not result in a significant drop in reward with respect to UCB algorithm, which does not impose any fairness constraint.