# Price of Fairness in Bandits: A Tight Minimax Characterization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 15 Jul 2026.

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

- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations](https://mlsanity.com/paper/2005.07370/) (2020)
- [On the Fairness of Normalized p-Means for Allocating Goods and Chores](https://mlsanity.com/paper/2402.14996/) (2024)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Convex Program Duality, Fisher Markets, and Nash Social Welfare](https://mlsanity.com/paper/1609.06654/) (2016)
- [Uniform Welfare Guarantees Under Identical Subadditive Valuations](https://mlsanity.com/paper/2005.00504/) (2020)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Improved Algorithms for Nash Welfare in Linear Bandits](https://mlsanity.com/paper/2601.22969/) (2026)
- [Nash Social Welfare, Matrix Permanent, and Stable Polynomials](https://mlsanity.com/paper/1609.07056/) (2016)

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

- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)

## Abstract (arXiv)

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized p-mean, interpolating between utilitarian welfare (p=1), Nash welfare (p→0), and Rawlsian fairness (p→-∞). Although tight guarantees are known for p≥0, the strictly fair regime q=-p>0 remains unresolved because negative-power means are dominated by the smallest per-round rewards. For σ-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret O(k(q+1)/2/√T), while the only general lower bound was the classical Omega(σ√k/T). Thus it was unclear whether the extra dependence on k was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound Omega(σ√kmax(1,q)/T); for q>1, this shows that the penalty kq/2 is information-theoretically unavoidable. We then introduce textsfUCB-HARE (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is widetildeO(σ√kmax(1,q)/T), matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that textsfUCB-HARE improves over uniform-exploration baselines, with gains increasing as q grows.