arXiv:2604.05129cs.GTcs.LG2026-04

研究如何在零和博弈中最大化对恒定步长FTRL学习者的策略盈余。

No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics

论文配图:No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics
图 1 · 摘自论文原文
  • 基于非陡峭正则化,可实现瞬时最大盈余。
  • 随机博弈下盈余达Ω(ηT/poly(n,m)),高概率成立。
  • 揭示了正则化类型对盈余持久性的影响,适合博弈论与强化学习研究者。

我们研究在T轮n×m双人零和博弈中,面对恒定步长η的追随正则化领导者(FTRL)学习者时,能获取的最大策略盈余。不同于以往分析,我们证明这种盈余是FTRL族的固有特性。首先,针对固定最大最小优化器,建立阶为Ω(N_sub/η)的普适规律,表明盈余随学习者次优动作数N增加而增大,在无次优动作时消失。其次,对于交替优化器,在随机博弈中可保证Ω(ηT/poly(n,m))的盈余,高概率成立。分析揭示了尖锐的几何二分:非陡峭正则化允许通过有限时间消除次优动作实现最大瞬时盈余,而陡峭正则化引入衰减尾部修正,延迟盈余饱和。最后讨论双边收益不确定性下的持续性,并提出敏感度量以识别最易被学习者感知操控的正则化类型。

原文摘要 · Abstract (English)

We investigate the strategic surplus obtainable against a Follow-the-Regularized-Leader (FTRL) learner with constant step size $η$ in $n\times m$ two-player zero-sum games played over $T$ rounds against a clairvoyant optimizer. In contrast with prior analysis, we show that the extraction of such regret-scale surplus is an inherent feature of the FTRL family, rather than an artifact of specific instantiations. First, for a fixed max-min optimizer, we establish a sweeping law of order $Ω(N_{\mathrm{sub}}/η)$, proving that utility surplus scales with the number of the learner's suboptimal actions $N$ and vanishes in their absence. Second, for an alternating optimizer, a surplus of $Ω(ηT/\mathrm{poly}(n,m))$ can be guaranteed regardless of the equilibrium structure, with high probability, in random games. Our analysis uncovers a sharp geometric dichotomy: non-steep regularizers allow the optimizer to realize the maximal transient surplus via finite-time elimination of suboptimal actions, whereas steep regularizers introduce a vanishing tail correction that can delay surplus saturation. Finally, we discuss whether this leverage persists under bilateral payoff uncertainty and propose a susceptibility measure quantifying which regularizers are most vulnerable to learner-aware strategic steering.

博弈论学习算法正则化策略盈余

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