博弈论研究实现一般博弈中个体遗憾常数级界
原文：Constant Individual Regret in General Games
非耦合的无遗憾动力学为实现均衡提供了一条去中心化路径，但此前关于个体遗憾的保证仍与时间跨度存在多对数依赖。我们在全信息反馈下，针对每个有限的 N 人正规 form 博弈消除了这一依赖。我们提出 ECHO-OFTRL：即带有 EMA 级联以实现高阶乐观的乐观正则化领导者跟随算法（OFTRL），其中 ECHO 表示 EMA 级联高阶乐观（EMA Cascade for High-Order Optimism），EMA 表示指数移动平均。该算法是确定性的且完全非耦合的。若 m_max 表示最大的动作集大小，则对于每个时间跨度 T≥1，该算法同时保证博弈中的 N 个玩家各自的遗憾均以 O(poly(N, log m_max)) 为上界。我们的算法利用了一种受现代滤波器设计启发的全新乐观形式。作者：Mingyang Liu, Gabriele Farina, Asuman Ozdaglar 分类：cs.LG,cs.GT