Price of Fairness in Bandits: A Tight Minimax Characterization

arXiv:2607.13402v1 Announce Type: cross Abstract: 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 (po0), and Rawlsian fairness (po-infty). Although tight guarantees are known for pge0, the strictly fair regime q=-p>0 remains unresolved because negative-power means are dominated by the smallest per-round rewards. For sigma-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret O(k^{(q+1)/2}/sqrt{T}), while the only general lower bound was the classical Omega(sigmasqrt{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(sigmasqrt{k^{max(1,q)}/T}); for q>1, this shows that the penalty k^{q/2} is information-theoretically unavoidable. We then introduce extsf{UCB-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 widetilde{O}(sigmasqrt{k^{max(1,q)}/T}), matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that extsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as q grows.

Source: arXiv cs.AI | 2026-07-16