Achieving Fairness in the Stochastic Multi-armed Bandit Problem

Abstract

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 the 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(\ln T)$ $r$-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1905.11260

References in corpus (14)

• Equality of Opportunity in Supervised Learning
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Fairness of Exposure in Rankings
• FA*IR: A Fair Top-k Ranking Algorithm
• On Fairness and Calibration
• Bandits with Knapsacks
• A Convex Framework for Fair Regression
• A Reductions Approach to Fair Classification
• Online Learning with an Unknown Fairness Metric
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Policy Learning for Fairness in Ranking
• Thompson Sampling for Budgeted Multi-armed Bandits
• An Algorithmic Framework to Control Bias in Bandit-based Personalization
• Equal Opportunity in Online Classification with Partial Feedback

Cited by in corpus (7)

• Fairness in Machine Learning: A Survey
• What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective
• How Do Fair Decisions Fare in Long-term Qualification?
• Curse of "Low" Dimensionality in Recommender Systems
• Group Fairness in Bandit Arm Selection
• Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates
• Identifying Best Fair Intervention