# Fair Contextual Multi-Armed Bandits: Theory and Experiments

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2019.

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

- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [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)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [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)
- [Designing Long-term Group Fair Policies in Dynamical Systems](https://mlsanity.com/paper/2311.12447/) (2023)
- [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)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Adapting Static Fairness to Sequential Decision-Making: Bias Mitigation Strategies towards Equal Long-term Benefit Rate](https://mlsanity.com/paper/2309.03426/) (2023)
- [Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability](https://mlsanity.com/paper/2104.12037/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [Holistic Survey of Privacy and Fairness in Machine Learning](https://mlsanity.com/paper/2307.15838/) (2023)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Improved Regret Bounds for Online Fair Division with Bandit Learning](https://mlsanity.com/paper/2501.07022/) (2025)
- [Contextual bandits with concave rewards, and an application to fair ranking](https://mlsanity.com/paper/2210.09957/) (2022)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)

## Abstract (arXiv)

When an AI system interacts with multiple users, it frequently needs to make allocation decisions. For instance, a virtual agent decides whom to pay attention to in a group setting, or a factory robot selects a worker to deliver a part. Demonstrating fairness in decision making is essential for such systems to be broadly accepted. We introduce a Multi-Armed Bandit algorithm with fairness constraints, where fairness is defined as a minimum rate that a task or a resource is assigned to a user. The proposed algorithm uses contextual information about the users and the task and makes no assumptions on how the losses capturing the performance of different users are generated. We provide theoretical guarantees of performance and empirical results from simulation and an online user study. The results highlight the benefit of accounting for contexts in fair decision making, especially when users perform better at some contexts and worse at others.