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 in two-player zero-sum games the Nash equilibrium is a well-establishedprescriptive notion of optimal play, its applicability as a prescriptive toolbeyond that setting is limited. Consequently, the study of decentralizedlearning dynamics that guarantee convergence to correlated solution concepts inmultiplayer, general-sum extensive-form (i.e., tree-form) games has become animportant topic of active research. The per-iteration complexity of thecurrently known learning dynamics depends on the specific correlated solutionconcept considered. For example, in the case of extensive-form correlatedequilibrium (EFCE), all known dynamics require, as an intermediate step at eachiteration, to compute the stationary distribution of multiple Markov chains, anexpensive operation in practice. Oppositely, in the case of normal-form coarsecorrelated equilibrium (NFCCE), simple no-external-regret learning dynamicsthat amount to a linear-time traversal of the tree-form decision space of eachagent suffice to guarantee convergence. This paper focuses on extensive-formcoarse correlated equilibrium (EFCCE), an intermediate solution concept that isa subset of NFCCE and a superset of EFCE. Being a superset of EFCE, anylearning dynamics for EFCE automatically guarantees convergence to EFCCE.However, since EFCCE is a simpler solution concept, this begs the question: dolearning dynamics for EFCCE that avoid the expensive computation of stationarydistributions exist? This paper answers the previous question in the positive.Our learning dynamics only require the orchestration of no-external-regretminimizers, thus showing that EFCCE is more akin to NFCCE than to EFCE from alearning perspective. Our dynamics guarantees that the empirical frequency ofplay after $T$ iteration is a $O(1/\sqrt{T})$-approximate EFCCE with highprobability, and an EFCCE almost surely in the limit.

Efficient Decentralized Learning Dynamics for Extensive-Form Coarse  Correlated Equilibrium: No Expensive Computation of Stationary Distributions  Required