# BanditQ: Fair Bandits with Guaranteed Rewards

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

## 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 (most cited first, 23 of 23)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Discrimination in Online Ad Delivery](https://mlsanity.com/paper/1301.6822/) (2013)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [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)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Achieving Counterfactual Fairness for Causal Bandit](https://mlsanity.com/paper/2109.10458/) (2021)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Stochastic One-Sided Full-Information Bandit](https://mlsanity.com/paper/1906.08656/) (2019)
- [Queue Scheduling with Adversarial Bandit Learning](https://mlsanity.com/paper/2303.01745/) (2023)

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

- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback](https://mlsanity.com/paper/2412.03983/) (2024)
- [Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness](https://mlsanity.com/paper/2502.15240/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## 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.