mlsanityData to 14 Oct 2026

Fair Best Arm Identification with Fixed Confidence

arXiv 2408.17313 ↗First posted 30 Aug 2024cs.LG cs.AIcited by 3

Not on the map. Why?

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.

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

24 of 45 references.

References · 24

  1. 2017Counterfactual Fairnesscited by 804
  2. 2020Fairness in Machine Learning: A Surveycited by 370
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  4. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  5. 2016Fairness in Learning: Classic and Contextual Banditscited by 168
  6. 2016Fairness in Reinforcement Learningcited by 95
  7. 2019Achieving Fairness in the Stochastic Multi-armed Bandit Problemcited by 78
  8. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  9. 2019Combinatorial Sleeping Bandits with Fairness Constraintscited by 68
  10. 2018Online Learning with an Unknown Fairness Metriccited by 62
  11. 2017Calibrated Fairness in Banditscited by 43
  12. 2021Fairness of Exposure in Stochastic Banditscited by 43
12 more
  1. 2019Fair Contextual Multi-Armed Bandits: Theory and Experimentscited by 42
  2. 2020Fair Algorithms for Multi-Agent Multi-Armed Banditscited by 41
  3. 2020Fairness in Learning-Based Sequential Decision Algorithms: A Surveycited by 35
  4. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  5. 2021Fair Exploration via Axiomatic Bargainingcited by 22
  6. 2022Enabling Long-term Fairness in Dynamic Resource Allocationcited by 15
  7. 2022Survey on Fair Reinforcement Learning: Theory and Practicecited by 14
  8. 2020Achieving User-Side Fairness in Contextual Banditscited by 11
  9. 2022Group Meritocratic Fairness in Linear Contextual Banditscited by 9
  10. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  11. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  12. 2020Regret in Online Recommendation Systemscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Optimal Best-Arm Identification under Fixed Confidence with Multiple Optimacited by 2
  2. 2026Envy-Free Allocation of Indivisible Goods via Noisy Queriescited by 0
  3. 2026Active Context Selection Improves Simple Regret in Contextual Banditscited by 0