# Fair Algorithms for Infinite and Contextual Bandits

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

## Key facts

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

## Built on by (most cited first, 17 of 17)

- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [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)
- [What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective](https://mlsanity.com/paper/2206.04101/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [Consistent End-to-End Estimation for Counterfactual Fairness](https://mlsanity.com/paper/2310.17687/) (2023)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Rawlsian Fair Adaptation of Deep Learning Classifiers](https://mlsanity.com/paper/2105.14890/) (2021)
- [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)
- [Entropy Regularization for Population Estimation](https://mlsanity.com/paper/2208.11747/) (2022)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)
- [Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret](https://mlsanity.com/paper/2610.07737/) (2026)

## Abstract (arXiv)

We study fairness in linear bandit problems. Starting from the notion of meritocratic fairness introduced in Joseph et al. [2016], we carry out a more refined analysis of a more general problem, achieving better performance guarantees with fewer modelling assumptions on the number and structure of available choices as well as the number selected. We also analyze the previously-unstudied question of fairness in infinite linear bandit problems, obtaining instance-dependent regret upper bounds as well as lower bounds demonstrating that this instance-dependence is necessary. The result is a framework for meritocratic fairness in an online linear setting that is substantially more powerful, general, and realistic than the current state of the art.