在强盗问题中，标准的后悔最小化算法将探索视为摊销成本，这在临床试验等环境中可能导致早期参与者面临不公平的预期损失。近期研究通过广义 $p$-均值评估每轮预期奖励的序列，介于功利福利（$p=1$）、纳什福利（$p o0$）和罗尔斯公平（$p o- ext{∞}$）之间。虽然对于 $p ext{≥}0$ 已知有严格保证，但严格公平的 $q=-p ext{<}0$ 情形仍未解决，因为负幂均值被最小的每轮奖励所主导。对于具有非负均值的 $ ext{σ}$-次高斯奖励，先前最佳算法依赖于均匀早期探索，后悔为 $O(k^{(q+1)/2}/ ext{√}T)$，而唯一的一般下界是经典的 $ ext{Ω(σ√(k/T))}$。因此，尚不清楚额外的 $k$ 依赖性是严格公平的内在特征还是均匀探索的伪影。我们通过识别严格公平的确切多项式代价来填补这一空白。使用针在干草堆中的构造，我们证明了一个与算法无关的下界 $ ext{Ω(σ√(k^{ ext{max}(1,q)}/T))}$；对于 $q ext{≥}1$，这表明惩罚 $k^{q/2}$ 是信息论上不可避免的。随后我们引入 extsf{UCB-HARE}（和谐锚定排名探索），其用反向加权的和谐排名调度取代均匀探索，并由认证的正均值锚点保护。其后悔为 $ ilde{O}(σ√(k^{ ext{max}(1,q)}/T))$，与下界相匹配，最多只差对数因子。对合成实例的实验确认了 extsf{UCB-HARE} 在均匀探索基准之上的改进，且随着 $q$ 的增加，收益也在增加。
博主点评： 本文通过精确的多项式界定了严格公平性的代价，突破了传统探索方法的局限。特别是引入的 extsf{UCB-HARE} 算法，不仅在理论上达到了下界，还在实际应用中展现了优越性。这为公平算法的设计提供了重要的理论基础和实践指导。