# Fairness of Exposure in Stochastic Bandits

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 3 Mar 2021.

## Builds on (most cited first, 23 of 23)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets](https://mlsanity.com/paper/2010.01470/) (2020)
- [Fair Algorithms for Infinite and Contextual Bandits](https://mlsanity.com/paper/1610.09559/) (2016)
- [On preserving non-discrimination when combining expert advice](https://mlsanity.com/paper/1810.11829/) (2018)
- [An Algorithmic Framework to Control Bias in Bandit-based Personalization](https://mlsanity.com/paper/1802.08674/) (2018)

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

- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Correcting Exposure Bias for Link Recommendation](https://mlsanity.com/paper/2106.07041/) (2021)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking](https://mlsanity.com/paper/2206.07247/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings](https://mlsanity.com/paper/2202.03237/) (2022)
- [Uncertainty Quantification for Fairness in Two-Stage Recommender Systems](https://mlsanity.com/paper/2205.15436/) (2022)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Fast online ranking with fairness of exposure](https://mlsanity.com/paper/2209.13019/) (2022)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Long-Term Fairness Inquiries and Pursuits in Machine Learning: A Survey of Notions, Methods, and Challenges](https://mlsanity.com/paper/2406.06736/) (2024)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [The price of unfairness in linear bandits with biased feedback](https://mlsanity.com/paper/2203.09784/) (2022)
- [Ranked Prioritization of Groups in Combinatorial Bandit Allocation](https://mlsanity.com/paper/2205.05659/) (2022)
- [Interpolating Item and User Fairness in Multi-Sided Recommendations](https://mlsanity.com/paper/2306.10050/) (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)
- [Online Fair Revenue Maximizing Cake Division with Non-Contiguous Pieces in Adversarial Bandits](https://mlsanity.com/paper/2111.14387/) (2021)
- [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)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [IBCB: Efficient Inverse Batched Contextual Bandit for Behavioral Evolution History](https://mlsanity.com/paper/2403.16075/) (2024)
- [Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays](https://mlsanity.com/paper/2407.15439/) (2024)
- [First-See-Then-Design: A Multi-Stakeholder View for Optimal Performance-Fairness Trade-Offs](https://mlsanity.com/paper/2604.14035/) (2026)
- [On Penalization in Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.08311/) (2022)

## Abstract (arXiv)

Contextual bandit algorithms have become widely used for recommendation in online systems (e.g. marketplaces, music streaming, news), where they now wield substantial influence on which items get exposed to the users. This raises questions of fairness to the items -- and to the sellers, artists, and writers that benefit from this exposure. We argue that the conventional bandit formulation can lead to an undesirable and unfair winner-takes-all allocation of exposure. To remedy this problem, we propose a new bandit objective that guarantees merit-based fairness of exposure to the items while optimizing utility to the users. We formulate fairness regret and reward regret in this setting, and present algorithms for both stochastic multi-armed bandits and stochastic linear bandits. We prove that the algorithms achieve sub-linear fairness regret and reward regret. Beyond the theoretical analysis, we also provide empirical evidence that these algorithms can fairly allocate exposure to different arms effectively.