# Fairness in Learning: Classic and Contextual Bandits

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

## Key facts

- Cited by 168 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

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

- [Harms from Increasingly Agentic Algorithmic Systems](https://mlsanity.com/paper/2302.10329/) (2023)
- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Representation Bias in Data: A Survey on Identification and Resolution Techniques](https://mlsanity.com/paper/2203.11852/) (2022)
- [Leave-one-out Unfairness](https://mlsanity.com/paper/2107.10171/) (2021)
- [Gender Bias in Large Language Models across Multiple Languages](https://mlsanity.com/paper/2403.00277/) (2024)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Long-Term Fairness with Unknown Dynamics](https://mlsanity.com/paper/2304.09362/) (2023)
- [Bayes-Optimal Classifiers under Group Fairness](https://mlsanity.com/paper/2202.09724/) (2022)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- ["There Is Not Enough Information": On the Effects of Explanations on Perceptions of Informational Fairness and Trustworthiness in Automated Decision-Making](https://mlsanity.com/paper/2205.05758/) (2022)
- [Unintended Selection: Persistent Qualification Rate Disparities and Interventions](https://mlsanity.com/paper/2111.01201/) (2021)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Algorithmic Fairness in Business Analytics: Directions for Research and Practice](https://mlsanity.com/paper/2207.10991/) (2022)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Adaptive Fairness Improvement Based on Causality Analysis](https://mlsanity.com/paper/2209.07190/) (2022)
- [Fair Sequential Selection Using Supervised Learning Models](https://mlsanity.com/paper/2110.13986/) (2021)
- [Fair Bayes-Optimal Classifiers Under Predictive Parity](https://mlsanity.com/paper/2205.07182/) (2022)
- [FaiR-IoT: Fairness-aware Human-in-the-Loop Reinforcement Learning for Harnessing Human Variability in Personalized IoT](https://mlsanity.com/paper/2103.16033/) (2021)
- [Achieving Counterfactual Fairness for Causal Bandit](https://mlsanity.com/paper/2109.10458/) (2021)
- [Out of Context: Investigating the Bias and Fairness Concerns of "Artificial Intelligence as a Service"](https://mlsanity.com/paper/2302.01448/) (2023)
- [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)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)

## Abstract (arXiv)

We introduce the study of fairness in multi-armed bandit problems. Our fairness definition can be interpreted as demanding that given a pool of applicants (say, for college admission or mortgages), a worse applicant is never favored over a better one, despite a learning algorithm's uncertainty over the true payoffs. We prove results of two types. First, in the important special case of the classic stochastic bandits problem (i.e., in which there are no contexts), we provide a provably fair algorithm based on "chained" confidence intervals, and provide a cumulative regret bound with a cubic dependence on the number of arms. We further show that any fair algorithm must have such a dependence. When combined with regret bounds for standard non-fair algorithms such as UCB, this proves a strong separation between fair and unfair learning, which extends to the general contextual case. In the general contextual case, we prove a tight connection between fairness and the KWIK (Knows What It Knows) learning model: a KWIK algorithm for a class of functions can be transformed into a provably fair contextual bandit algorithm, and conversely any fair contextual bandit algorithm can be transformed into a KWIK learning algorithm. This tight connection allows us to provide a provably fair algorithm for the linear contextual bandit problem with a polynomial dependence on the dimension, and to show (for a different class of functions) a worst-case exponential gap in regret between fair and non-fair learning algorithms