提出新型学习动态,实现多人博弈中次对数级交换遗憾。
Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
- 结合熵与对数障碍的混合正则化设计优化算法
- 交换遗憾降至 $O(nm^2 oot\log m\log T)$,为首次次对数结果
- 适用于无先验时间信息或对抗性收益场景
交换遗憾决定多人一般和博弈中解耦学习动态收敛到相关均衡的速率。在完全信息反馈下,此前所有玩家采用相同动态时的最优保证在时间跨度 $T$ 上呈对数增长。本文构造了一种解耦动态,使得每位玩家的交换遗憾仅为 $O(nm^2 oot\log m\log T)$,其中 $n$ 为玩家数,$m$ 为每名玩家动作数上限。据我们所知,这是该设定下的首个次对数个体保证,意味着策略的平均联合分布为 $O(nm^2 oot\log m\log T/T)$-近似相关均衡。核心算法是将 Blum-Mansour 约化与使用混合正则化的乐观跟随正则化领袖结合:负香农熵控制预测误差,对数障碍通过 Bregman 散度控制转移矩阵变动。新提出的马尔可夫链平稳分布敏感性定理,不依赖混合参数或最小转移概率,将此控制传递至实际策略,使分析更简洁,无需局部范数或自协调论证。该保证还可被抗对抗扰动变体保持,额外提供 $O(nm^2 oot\log m\log T + oot{mT\log m})$ 的交换遗憾;同时存在无需预知 $T$ 的时间无关变体。
原文摘要 · Abstract (English)
Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon $T$. We construct uncoupled dynamics under which every player incurs only $O(nm^2\sqrt{\log m\log T})$ swap regret, where $n$ is the number of players and $m$ bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an $O(nm^2\sqrt{\log m\log T}/T)$-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures $O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})$ swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of $T$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。