# Fair Best Arm Identification with Fixed Confidence

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 30 Aug 2024.

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

- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [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)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Fairness in Learning-Based Sequential Decision Algorithms: A Survey](https://mlsanity.com/paper/2001.04861/) (2020)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Enabling Long-term Fairness in Dynamic Resource Allocation](https://mlsanity.com/paper/2208.05898/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Achieving User-Side Fairness in Contextual Bandits](https://mlsanity.com/paper/2010.12102/) (2020)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Best Arm Identification with Fairness Constraints on Subpopulations](https://mlsanity.com/paper/2304.04091/) (2023)
- [On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure](https://mlsanity.com/paper/2211.15129/) (2022)
- [Regret in Online Recommendation Systems](https://mlsanity.com/paper/2010.12363/) (2020)

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

- [Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima](https://mlsanity.com/paper/2505.15643/) (2025)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)
- [Active Context Selection Improves Simple Regret in Contextual Bandits](https://mlsanity.com/paper/2605.20040/) (2026)

## Abstract (arXiv)

In this work, we present a novel framework for Best Arm Identification (BAI) under fairness constraints, a setting that we refer to as textitF-BAI (fair BAI). Unlike traditional BAI, which solely focuses on identifying the optimal arm with minimal sample complexity, F-BAI also includes a set of fairness constraints. These constraints impose a lower limit on the selection rate of each arm and can be either model-agnostic or model-dependent. For this setting, we establish an instance-specific sample complexity lower bound and analyze the textitprice of fairness, quantifying how fairness impacts sample complexity. Based on the sample complexity lower bound, we propose F-TaS, an algorithm provably matching the sample complexity lower bound, while ensuring that the fairness constraints are satisfied. Numerical results, conducted using both a synthetic model and a practical wireless scheduling application, show the efficiency of F-TaS in minimizing the sample complexity while achieving low fairness violations.