# Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games

arXiv: https://arxiv.org/abs/2205.07223 · HTML: https://mlsanity.com/paper/2205.07223/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 15 May 2022.

## Builds on (most cited first, 14 of 14)

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Joint Policy Search for Multi-agent Collaboration with Imperfect Information](https://mlsanity.com/paper/2008.06495/) (2020)
- [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021)
- [Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria](https://mlsanity.com/paper/2202.05446/) (2022)
- [Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information](https://mlsanity.com/paper/1810.04433/) (2018)

## Built on by (most cited first, 7 of 7)

- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Learning Rationalizable Equilibria in Multiplayer Games](https://mlsanity.com/paper/2210.11402/) (2022)

## Abstract (arXiv)

Imperfect-Information Extensive-Form Games (IIEFGs) is a prevalent model for real-world games involving imperfect information and sequential plays. The Extensive-Form Correlated Equilibrium (EFCE) has been proposed as a natural solution concept for multi-player general-sum IIEFGs. However, existing algorithms for finding an EFCE require full feedback from the game, and it remains open how to efficiently learn the EFCE in the more challenging bandit feedback setting where the game can only be learned by observations from repeated playing. This paper presents the first sample-efficient algorithm for learning the EFCE from bandit feedback. We begin by proposing K-EFCE -- a more generalized definition that allows players to observe and deviate from the recommended actions for K times. The K-EFCE includes the EFCE as a special case at K=1, and is an increasingly stricter notion of equilibrium as K increases. We then design an uncoupled no-regret algorithm that finds an varepsilon-approximate K-EFCE within widetildeO(maxiXiAiK/varepsilon2) iterations in the full feedback setting, where Xi and Ai are the number of information sets and actions for the i-th player. Our algorithm works by minimizing a wide-range regret at each information set that takes into account all possible recommendation histories. Finally, we design a sample-based variant of our algorithm that learns an varepsilon-approximate K-EFCE within widetildeO(maxiXiAiK+1/varepsilon2) episodes of play in the bandit feedback setting. When specialized to K=1, this gives the first sample-efficient algorithm for learning EFCE from bandit feedback.