Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the
  Gap Between Learning in Extensive-Form and Normal-Form Games
  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.
