mlsanityData to 14 Oct 2026

BanditQ: Fair Bandits with Guaranteed Rewards

arXiv 2304.05219 ↗First posted 11 Apr 2023cs.LG cs.PFcited by 6

Not on the map. Why?

Abstract (arXiv)

Classic no-regret multi-armed bandit algorithms, including the Upper Confidence Bound (UCB), Hedge, and EXP3, are inherently unfair by design. Their unfairness stems from their objective of playing the most rewarding arm as frequently as possible while ignoring the rest. In this paper, we consider a fair prediction problem in the stochastic setting with a guaranteed minimum rate of accrual of rewards for each arm. We study the problem in both full-information and bandit feedback settings. Combining queueing-theoretic techniques with adversarial bandits, we propose a new online policy, called BanditQ, that achieves the target reward rates while conceding a regret and target rate violation penalty of at most O(T^frac34). The regret bound in the full-information setting can be further improved to O(√T) under either a monotonicity assumption or when considering time-averaged regret. The proposed policy is efficient and admits a black-box reduction from the fair prediction problem to the standard adversarial MAB problem. The analysis of the BanditQ policy involves a new self-bounding inequality, which might be of independent interest.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 23 of its 43 references that are in the map. First posted on arXiv 11 Apr 2023.

Builds on

23 of 43 references.

References · 23

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2016Fairness in Learning: Classic and Contextual Banditscited by 168
  3. 2013Bandits with Knapsackscited by 164
  4. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  5. 2013Discrimination in Online Ad Deliverycited by 93
  6. 2019Achieving Fairness in the Stochastic Multi-armed Bandit Problemcited by 78
  7. 2019Combinatorial Sleeping Bandits with Fairness Constraintscited by 68
  8. 2013Projection onto the probability simplex: An efficient algorithm with a simple proof, and an applicationcited by 67
  9. 2018Online Learning with an Unknown Fairness Metriccited by 62
  10. 2017Online Convex Optimization with Time-Varying Constraintscited by 56
  11. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 49
  12. 2018Online convex optimization for cumulative constraintscited by 47
11 more
  1. 2019Fair Contextual Multi-Armed Bandits: Theory and Experimentscited by 42
  2. 2020Fair Algorithms for Multi-Agent Multi-Armed Banditscited by 41
  3. 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
  4. 2020Metric-Free Individual Fairness in Online Learningcited by 30
  5. 2015Thompson Sampling for Budgeted Multi-armed Banditscited by 24
  6. 2021Achieving Counterfactual Fairness for Causal Banditcited by 15
  7. 2020Adaptation to the Range in K-Armed Banditscited by 13
  8. 2021Scale Free Adversarial Multi Armed Banditscited by 12
  9. 2023No-regret Algorithms for Fair Resource Allocationcited by 9
  10. 2019Stochastic One-Sided Full-Information Banditcited by 5
  11. 2023Queue Scheduling with Adversarial Bandit Learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

6 papers.

  1. 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 34
  2. 2025Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimizationcited by 4
  3. 2024Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedbackcited by 0
  4. 2025Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairnesscited by 0
  5. 2026A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regressioncited by 0
  6. 2026Constrained Online Learning with Noisy Constraint Valuescited by 0