论文标题
0/1-多域游戏的内核化倍增权重：在广泛形式和正常形式的游戏中弥合学习之间的差距
Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games
论文作者
论文摘要
虽然可以将广泛的游戏（EFG）转换为正常形式游戏（NFG），但这样做的代价是以策略空间的指数爆炸为代价。因此，NFG和EFGS的进步历史上一直遵循单独的曲目，EFG社区经常不得不赶上较大的NFG社区的进步（例如，最后介绍的融合和预测性遗憾界限）。在本文中，我们表明，可以使用kernel trick在游戏树大小中，可以模拟乐观的多重权重更新（OMWU）算法 - NFGS的主要学习算法。所得的算法，内核化的OMWU（KOMWU），只要可以有效地评估内核，其策略空间是具有0/1积分顶点的策略空间的所有凸面游戏。在特定的EFG情况下，KOMWU通过将直接的黑盒转移到迄今为止仅在NFG中才能实现的直接黑盒转移来缩小NFG和EFG学习之间的几个常规差距。具体来说，Komwu给出了第一种算法，该算法保证了最后卷接收的同时保证游戏树的大小比所有先前的算法都较低，并且在所有玩家都遵循所有玩家时，$ \ tilde {\ tilde {\ tillcal {o}}}（1）$遗憾。
While extensive-form games (EFGs) can be converted into normal-form games (NFGs), doing so comes at the cost of an exponential blowup of the strategy space. So, progress on NFGs and EFGs has historically followed separate tracks, with the EFG community often having to catch up with advances (e.g., last-iterate convergence and predictive regret bounds) from the larger NFG community. In this paper we show that the Optimistic Multiplicative Weights Update (OMWU) algorithm -- the premier learning algorithm for NFGs -- can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick. The resulting algorithm, Kernelized OMWU (KOMWU), applies more broadly to all convex games whose strategy space is a polytope with 0/1 integral vertices, as long as the kernel can be evaluated efficiently. In the particular case of EFGs, KOMWU closes several standing gaps between NFG and EFG learning, by enabling direct, black-box transfer to EFGs of desirable properties of learning dynamics that were so far known to be achievable only in NFGs. Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence, lower dependence on the size of the game tree than all prior algorithms, and $\tilde{\mathcal{O}}(1)$ regret when followed by all players.
