提出最优公平性算法，解决线性博弈中纳什福利的维度瓶颈问题。
Improved Algorithms for Nash Welfare in Linear Bandits
- 设计新分析工具，实现线性带宽中纳什后悔率的理论最优。
- 提出统一框架FairLinBandit，对所有参数p实现亚线性p-均值后悔。
- 实验证明优于现有方法，适合追求公平与效率平衡的研究者。
纳什后悔近年来作为公平感知的性能度量被引入随机多臂赌博机，源于纳什社会福利目标。尽管该概念已扩展至线性带宽，但现有结果在环境维度$d$上存在次优性，源于依赖限制性集中不等式的证明技术。本文通过引入新的分析工具，解决了这一开放问题，实现了线性带宽中阶最优的纳什后悔界。此外，我们首次研究了线性带宽中的$p$-均值后悔，该框架在公平性与效用目标间插值，严格推广了纳什后悔。我们提出通用算法框架FairLinBandit，可作为元算法作用于任意线性带宽策略。通过实例化相位消除和上置信界算法，证明二者在全部$p$范围内均实现亚线性$p$-均值后悔。在真实数据集生成的线性带宽实例上进行大量实验，表明我们的方法始终优于现有最先进基线。
原文摘要 · Abstract (English)
Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension $d$, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of $p$-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear $p$-means regret for the entire range of $p$. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。