arXiv:2505.17277cs.LG2025-05NeurIPS被引 2

新算法更简单且性能更优,实现自适应专家学习的最优后悔界。

Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games

  • 设计先验分布,通过多副本学习提升算法简洁性。
  • 在一般和博弈中实现更快的自适应收敛到Φ-均衡。
  • 适用于外部、内部及交换后悔等经典场景,优于已有方法。

在经典专家问题中,Φ-后悔衡量学习者总损失与最佳动作变换ϕ∈Φ之间差距。近期工作Lu等[2025]提出一种自适应算法,其对比较器ϕ的后悔依赖于ϕ的稀疏性复杂度,几乎恢复并插值了外部、内部和交换后悔等标准后悔范式的最优界。本文提出一个通用思路,通过更简单的算法实现更优的比较器自适应Φ-后悔界。具体地,我们发现所有可能二值变换上的先验分布,并证明只需针对这些变换实现先验相关后悔即可。进而提出两个高效算法:第一个在Farina等[2022]的核化MWU算法基础上构建多个先验感知副本;第二个基于Blum和Mansour[2007]的BM归约构造类似结构。为进一步展示方法威力及相较于Lu等[2025]的优势(包括简洁性与更优后悔界),我们还证明第二类方法可拓展至博弈场景,实现一类广义和博弈中Φ-均衡的加速自适应收敛。当特化为相关均衡情形时,我们的界优于Anagnostides等[2022a,b]的现有结果。

原文摘要 · Abstract (English)

In the classic expert problem, $Φ$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $ϕ\in Φ$. A recent work by Lu et al., [2025] introduces an adaptive algorithm whose regret against a comparator $ϕ$ depends on a certain sparsity-based complexity measure of $ϕ$, (almost) recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $Φ$-regret bound via much simpler algorithms compared to Lu et al., [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one learns over multiple copies of a prior-aware variant of the Kernelized MWU algorithm of Farina et al., [2022], and the second one learns over multiple copies of a prior-aware variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al., [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $Φ$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al., [2022a,b]

在线学习后悔最小化博弈论算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。