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.

深入研究了公平性，提出了一种基于两个层次的公平性方法，保证每个组的最小曝光，并确保组内每个单元根据其优越性被拉动；通过提出的算法 BF-UCB，实现了对遗憾的上界为 O (√T) 的平衡，同时提供更好的组和个体曝光保证，并且不会显著降低奖励。

随机赌博机中同时实现群体曝光公平和组内精英主义

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

We study fairness in linear bandit problems. Starting from the notion of
meritocratic fairness introduced in Joseph et al. [2016], we carry out a more
refined analysis of a more general problem, achieving better performance
guarantees with fewer modelling assumptions on the number and structure of
available choices as well as the number selected. We also analyze the
previously-unstudied question of fairness in infinite linear bandit problems,
obtaining instance-dependent regret upper bounds as well as lower bounds
demonstrating that this instance-dependence is necessary. The result is a
framework for meritocratic fairness in an online linear setting that is
substantially more powerful, general, and realistic than the current state of
the art.

本文研究线性 bandit 问题中的公平性，提出 meritocratic 公平的概念，并在更广泛的问题上进行分析，得出更好的性能保证。同时，探讨了无限线性 bandit 问题中的公平性问题，证明了实例相关性是必要的。结果是一个在线线性环境中 meritocratic 公平的框架，比现有技术的研究更强大、更普遍和更现实。