Sample-efficient Learning Of Correlated Equilibria In Extensive-form Games

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keysong2022sample

Related papers

• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34
• Score-based Equilibrium Learning In Multi-player Finite Games With Imperfect Information (2023)0.00
• Generalized Bandit Regret Minimizer Framework In Imperfect Information Extensive-form Game (2022)0.00
• Sample-efficient Learning Of Stackelberg Equilibria In General-sum Games (2021)0.00
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Model-free Learning For Two-player Zero-sum Partially Observable Markov Games With Perfect Recall (2021)0.00
• Explore Reinforced: Equilibrium Approximation With Reinforcement Learning (2024)0.00
• Achieving Correlated Equilibrium By Studying Opponent's Behavior Through Policy-based Deep Reinforcement Learning (2020)0.00