Sample-Efficient Learning of Correlated Equilibria in Extensive-Form
  Games
  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
$\widetilde{\mathcal{O}}(\max_{i}X_iA_i^{K}/\varepsilon^2)$ iterations in the
full feedback setting, where $X_i$ and $A_i$ 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
$\widetilde{\mathcal{O}}(\max_{i}X_iA_i^{K+1}/\varepsilon^2)$ 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.
