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/

Zendy Plus

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

Zendy Tools

Zendy Open

Learning and equilibrium computation in games are fundamental problems acrosscomputer science and economics, with applications ranging from politics tomachine learning. Much of the work in this area revolves around a simplealgorithm termed \emph{randomized weighted majority} (RWM), also known as"Hedge" or "Multiplicative Weights Update," which is well known to achievestatistically optimal rates in adversarial settings (Littlestone and Warmuth'94, Freund and Schapire '99). Unfortunately, RWM comes with an inherentcomputational barrier: it requires maintaining and sampling from a distributionover all possible actions. In typical settings of interest the action space isexponentially large, seemingly rendering RWM useless in practice.  In this work, we refute this notion for a broad variety of \emph{structured}games, showing it is possible to efficiently (approximately) sample the actionspace in RWM in \emph{polylogarithmic} time. This gives the first efficientno-regret algorithms for problems such as the \emph{(discrete) Colonel Blottogame}, \emph{matroid congestion}, \emph{matroid security}, and basic\emph{dueling games}. As an immediate corollary, we give a polylogarithmic timemeta-algorithm to compute approximate Nash Equilibria for these games that isexponentially faster than prior methods in several important settings. Further,our algorithm is the first to efficiently compute equilibria for more involvedvariants of these games with general sums, more than two players, and, forColonel Blotto, multiple resource types.

Sampling Equilibria: Fast No-Regret Learning in Structured Games