# Achieving Fairness in the Stochastic Multi-armed Bandit Problem

arXiv: https://arxiv.org/abs/1907.10516 · HTML: https://mlsanity.com/paper/1907.10516/

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2019.

## Built on by (most cited first, 30 of 78)

- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Fairness-Aware Online Meta-learning](https://mlsanity.com/paper/2108.09435/) (2021)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making](https://mlsanity.com/paper/2109.08792/) (2021)
- [Modeling Attrition in Recommender Systems with Departing Bandits](https://mlsanity.com/paper/2203.13423/) (2022)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Towards Fair Disentangled Online Learning for Changing Environments](https://mlsanity.com/paper/2306.01007/) (2023)
- [Recommendation Fairness: From Static to Dynamic](https://mlsanity.com/paper/2109.03150/) (2021)
- [Uncertainty Quantification for Fairness in Two-Stage Recommender Systems](https://mlsanity.com/paper/2205.15436/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Fairness in Reinforcement Learning: A Survey](https://mlsanity.com/paper/2405.06909/) (2024)
- [Multi-disciplinary fairness considerations in machine learning for clinical trials](https://mlsanity.com/paper/2205.08875/) (2022)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning](https://mlsanity.com/paper/2306.00324/) (2023)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment](https://mlsanity.com/paper/2102.07120/) (2021)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)

## Abstract (arXiv)

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.