New Minimax Bound Settles the True Cost of Fairness in Multi-Armed Bandits

A regret bound of Ω(σ√(k^max(1,q)/T)) now marks the point past which no fair bandit algorithm can improve, according to "Price of Fairness in Bandits: A Tight Minimax Characterization," submitted to arXiv on July 15, 2026. The paper closes a long-standing gap between theory and practice for algorithms that must balance reward maximization against equitable treatment across arms.

Multi-armed bandit problems are the standard testbed for sequential decision-making under uncertainty: an algorithm repeatedly chooses among k options ("arms") to maximize cumulative reward while learning which arms perform best. Classic bandit theory optimizes purely for total reward, but that objective can systematically starve some arms of exploration, a real concern when arms represent people, groups, or resources competing for allocation.

To formalize fairness, the authors evaluate rewards using generalized p-means, a single mathematical family that interpolates between three familiar notions of welfare depending on the parameter p. Setting p=1 recovers standard utilitarian welfare (maximize the sum of rewards), letting p approach 0 yields Nash welfare (a balance between efficiency and equality), and pushing p toward negative infinity produces Rawlsian fairness, which optimizes for the worst-off arm. This lets the paper study fairness not as a binary constraint but as a tunable spectrum, parameterized through a related quantity q.

Quantifying the Price of Fairness

The paper's central contribution is a matching pair of bounds. On the lower-bound side, it proves that any algorithm respecting fairness constraints must incur regret of at least Ω(σ√(k^max(1,q)/T)), where σ captures the sub-Gaussian noise of the reward distributions, k is the number of arms, and T is the time horizon. Critically, for q>1 this shows the extra k^(q/2) penalty compared to the unconstrained case is not an artifact of weak algorithms. It is information-theoretically unavoidable, meaning no clever algorithm design can escape it.

On the upper-bound side, the authors introduce UCB-HARE (Harmonic Anchored Rank Exploration), an algorithm that achieves regret of Õ(σ√(k^max(1,q)/T)), matching the lower bound up to logarithmic factors. That closes the theoretical gap left by prior approaches, which relied on uniform early exploration phases and only managed regret of O(k^((q+1)/2)/√T) for σ-sub-Gaussian rewards, a strictly weaker guarantee as q grows.

Synthetic experiments back up the theory: UCB-HARE consistently outperforms uniform-exploration baselines, and the margin widens as q increases, meaning the benefit of smarter exploration becomes more pronounced the stricter the fairness requirement gets.

Why the Bound Matters

For practitioners building bandit-based systems in domains like resource allocation, recommendation, or clinical trial design, this result offers something rare in fairness-aware machine learning: a hard, provable limit on how much fairness costs in terms of performance. Rather than guessing whether a better algorithm might close the gap further, engineers now have a benchmark to test against. UCB-HARE gives them an algorithm that reaches that benchmark up to log factors, turning an open theoretical question into a solved one, at least within this p-mean fairness framework.