We study an interesting variant of the stochastic multi-armed bandit problem,
called the Fair-SMAB problem, where each arm is required to be pulled for at
least a given fraction of the total available rounds. We investigate the
interplay between learning and fairness in terms of a pre-specified vector
denoting the fractions of guaranteed pulls. We define a fairness-aware regret,
called r-Regret, that takes into account the above fairness constraints and
naturally extends the conventional notion of regret. Our primary contribution
is characterizing a class of Fair-SMAB algorithms by two parameters: the
unfairness tolerance and learning algorithm used as a black-box. We provide a
fairness guarantee for this class that holds uniformly over time irrespective
of the choice of the learning algorithm. In particular, when the learning
algorithm is UCB1, we show that our algorithm achieves O(log(T)) r-Regret.
Finally, we evaluate the cost of fairness in terms of the conventional notion
of regret.

研究公平多臂老虎机问题中学习与公平之间的相互作用，通过特定向量表示公平性约束，定义一个公平感知的后悔，通过两个参数刻画一个 Fair-SMAB 算法类，并提供一个公平保证，无论学习算法的选择是什么，都可以持续地适用。