English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 strategyspace. 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 NFGcommunity. In this paper we show that the Optimistic Multiplicative WeightsUpdate (OMWU) algorithm -- the premier learning algorithm for NFGs -- can besimulated on the normal-form equivalent of an EFG in linear time per iterationin the game tree size using a kernel trick. The resulting algorithm, KernelizedOMWU (KOMWU), applies more broadly to all convex games whose strategy space isa polytope with 0/1 integral vertices, as long as the kernel can be evaluatedefficiently. In the particular case of EFGs, KOMWU closes several standing gapsbetween NFG and EFG learning, by enabling direct, black-box transfer to EFGs ofdesirable properties of learning dynamics that were so far known to beachievable only in NFGs. Specifically, KOMWU gives the first algorithm thatguarantees at the same time last-iterate convergence, lower dependence on thesize of the game tree than all prior algorithms, and $\tilde{\mathcal{O}}(1)$regret when followed by all players.

Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games