UCB-HARE algorithm closes fairness gap in bandits with provably optimal bounds

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, potentially exposing early participants to unfair losses in applications like clinical trials. Recent work evaluates fairness via the generalized p-mean, interpolating from utilitarian (p=1) to Rawlsian fairness (p→−∞). While tight bounds existed for p≥0, the strictly fair regime (q=−p>0) remained unresolved because negative-power means are dominated by the smallest per-round rewards.

Sarkar, Dutta, and Chowdhury close this gap with a tight minimax characterization. They prove an algorithm-independent lower bound Ω(σ√(k^{max(1,q)}/T)), showing that for q>1 the penalty k^{q/2} is information-theoretically unavoidable. They then introduce 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 matches the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that UCB-HARE improves over uniform-exploration baselines, with gains increasing as q grows.