提出新算法实现博弈中个体后悔恒定，无需随时间增长
Constant Individual Regret in General Games
- 用指数移动平均级联设计高阶乐观机制
- 任意玩家后悔上界为O(多项式(N, log m_max))
- 适合研究分布式博弈均衡与在线学习
无耦合的无后悔动态为均衡提供了去中心化路径，但以往对个体后悔的保证仍存在关于时间跨度的多对数依赖。本文在完全信息反馈下，针对任意有限N人正则形式博弈，消除了这种依赖。提出ECHO-OFTRL：一种配备指数移动平均级联以实现高阶乐观的乐观跟随正则化领导者算法。该算法为确定性且完全无耦合。若m_max表示最大动作集大小，则对任意T≥1，每个玩家的后悔均被上界控制在O(多项式(N, log m_max))内。算法基于现代滤波设计启发的新类型乐观机制。
原文摘要 · Abstract (English)
Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite $N$-player normal-form game under full-information feedback. We introduce \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If $m_{\max}$ denotes the largest action-set size, then, simultaneously for every horizon $T\geq1$, it guarantees that each of the $N$ players in the game incurs regret upper bounded by $O(\textrm{poly}(N, \log m_{\max}))$. Our algorithm leverages a new form of optimism inspired by modern filter design.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。