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 o0$), and Rawlsian fairness ($p o- ext{∞}$). Although tight guarantees are known for $p ext{≥}0$, the strictly fair regime $q=-p ext{<}0$ remains unresolved because negative-power means are dominated by the smallest per-round rewards. For $ ext{σ}$-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret $O(k^{(q+1)/2}/ ext{√}T)$, while the only general lower bound was the classical $ ext{Ω(σ√(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 $ ext{Ω(σ√(k^{ ext{max}(1,q)}/T))}$; for $q ext{≥}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 $ ilde{O}(σ√(k^{ ext{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.
Blogger's Review: This paper precisely defines the polynomial cost of strict fairness, breaking through the limitations of traditional exploration methods. Notably, the introduced extsf{UCB-HARE} algorithm not only achieves theoretical lower bounds but also demonstrates superiority in practical applications. This provides crucial theoretical foundations and practical guidance for the design of fair algorithms.