Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games
Authors: Ziang Song
Song Mei
Yu Bai
Venue: NeurIPS 2022 Accept (2022)
Keywords: extensive-form games
imperfect information
correlated equilibria
reinforcement learning theory
multi-agent reinforcement learning

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 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.

Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games
Ziang Song Stanford University zi ciangs@stanford. edu
Song Mei UC Berkeley songmei@berkeley.com edu
Yu Bai Salesforce Research yu ww..aa@@aleesorce.ccom com
Abstract
imperfect-Information Extensive-Fomn Games (IEFGSs is a prevalent model for real-world games involving imperfect information and sequential plays. The Extensive-Fore Correlated Equilibrium (EFCE) has been proposed as a natural solution concept for multi-player general-sum IIFGGs. However, existing algo- rithms for finding an EFCE require full feedback from the game, and remains open how to efficiently learn the EFCE in the more challenging bandit feedback setting where the game can only 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 generalized definition that allows players to observe and deviate from the recommended actions for K times. The K-EFCE includes the EFCE an increasingly stricter notion of equilibrium as K increases. We then design an uncoupled no-regret algorithm that finds an e-approximate K-EFCE within (max, X,A /s²) iterations the full feedback setting, where X, and A, are the number of information sets and actions for the i-th player. Our algorithm works by minimizing wide-range regret at each information set that takes into account all possible recommendation histories. Finally, design sample-based variant of algorithm that learns e-approximate K-EFCE within (mmx,; X,AK+1//e? 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.
special case at K and is
Introduction
This paper is concerned with the problem of learning equilibria in Imperfect-Infoon Information Extensive- Form Games (IEFGS) [29]. IIEGGs is general formulation for multi-player games with both imperfect information (such as private information) and sequential play, and has been used for modeling and solving real-world games such Poker [23, 32, 8), Bridge [39]. Scotland Yard [37], and so on. In a two-player zero-sum IEFG, the standard solution concept is the celebrated notion of Nash Equilibrium (NE) [35], that is, pair of independent policies for both players such that no player can gain by deviating. However, in multi-player general-sum IEFGS, computing an (approximate) NE PPAD-hard and unlikely admit efficient algorithms [12]. more amenable class of solution concepts is the notion of correlated equilibria [4], that is, a correlated policy for all players such that no player can gain by deviating from the correlated play using certain types of deviations.
The notion of Extensive-FFi Form Correlated Equilibria (EFCE) proposed by Von Stengel and Forges [40] is natural definition of correlated equilibria in multi-player general-sum IIEFGs. An EFCE is correlated policy that can be thought of as a "mediator" of the game who recommends actions to each player privately and sequentially (at visited information sets), in way that disincentivizes any player to deviate from the recommended actions. Polynomial-tin -ittmeil--ime algorithms for computing EFCEs have been established, by formulating as a linear program and using the ellipsoid method [24, 36, 26).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

min-max optimization [16], or uncoupled no-regret dynamics using variants of counterfactual regret minimization [11, 20, 34, 2].
However, all the above algorithms require that the full game is known (or full feedback). In the more challenging bandit feedback setting where the game can only be learned by observations from repeated playing, it remains open how to learn EFCEs samplc-efficiently. This is in contrast to other types of equilibria such as NE in two-player zero-sum IIEGGs, where sample-efficient learning algorithms under bandit feedback are known [30, 19, 28, 5J. A related question is about the structure of the EFCE definition: An EFCE only allows players to deviate once from the observed recommendations, upon which further recommendations are no longer revealed and the player needs to make decisions on her own instead. This may be too restrictive model situations where players can still observe the recommendations after deviating [34]. It is of interest how we can extend the EFCE definition in a structured fashion to disincentivize such stronger deviations while still allowing efficient algorithms.
This paper makes steps towards answering both questions above, by proposing stronger and more generalized definition of EFCEs, and designing efficient learning algorithms under both full-feedback and bandit-fcedback settings. We consider IEFGSs with m players, H steps, where each player i has X, information sets and A; actions. Our contributions can be summarized as follows.
We propose K-EFCE, a natural generalization of EFCE, at which players have no gains when allowed to observe and deviate from the recommended actions for K times (Section 3). At K = 1, the K-EFCE is equivalent the existing definition of EFCE based on trigger policies. For K 2 1, the K-FFCE are increasingly stricter notions of equilibria as K increases.
We design an algorithm K Extensive-Form Regret Minimization (K-EFR) which finds e- approximate K-EFCE within Ō(max, X,A4KH /E²) iterations under full feedback (Section 4). At K 1, our linear in max; X, dependence improves over the best known Ô (max, X?) depen- dence for computing e-approximate EFCE. At K > 1, this gives sharp result for efficiently computing (the stricter) K-EFCE, improving over the best known Ö Ommxx X² KM /E²) itera- tion complexity of Morrill et al. [34].
We further design Balanced K-EFR-a a sample- based variant of K-EFR-for the more challenging bandit-feedback setting (Section 5). Balanced K K-EFR learns an s-approximate K-EFCE within
O(max; X;A (K--+1// episodes of play. This is the first line of results for learning EFCE and K-EFCE from bandit feedback, and the linear in X, dependence matches information-theoretiee lower bounds. Technically, our bandit-feedback result builds on novel stochastic wide range regret minimization algorithm S SWRHEDGE, as well as sample-based estimators of counterfactual loss functions using newly designed sampling policies, which may be of independent interest.
1.1 Related work
Computing Correlated Equilibria from full feedback The notion of Extensive-Ford Correlated Equilibria (EFCE) in IIFGss is introduced in Von Stengel and Forges [40]. Huang and von Stengel [24] design the first polynomial time algorithm for computing EFCEs in multi-player IIEGGs from full feedback, using variation of the Ellipsoid against hope algorithm [36, 26). Farina et al. [16] later propose a min-max max optimization formulation of EFCEs which can be solved by first-order methods.
Celli et al. [11] and its extended version [20] design the first uncoupled no-regret algorithm for computing EFCEs. Their algorithms are based on minimizing the trigger regret (first considered in Dudik and Gordon [13], Gordon et al. [22]) via counterfactual regret decomposition [45]. Morrill al. [34] propose the stronger definition of "Behavioral Correlated Equilibria" (BCE) using general "behavioral deviations". and design the Extensive-Fond
Regret Minimization (EFR) algorithm to compute BCE by using a generalized version of counterfactual regret decomposition. They also propose intermediate notions such as a "Twice Informed Partial Sequence" (TIPS) (and its K-shot generalization) as an interpolation between the EFCE and BCE. Our definition of K K-EFCE offers a new interpolation between the EFCE and BCE that is different from theirs, as the deviating player in K-EFCE does not observe and does not follow recommended actions after K deviations has happened, whereas the deviator in Khohot Informed Partial Sequence resumes to following after K deviations has happened. The iteration complexity for computing an e-approximate correlated equilibrium in both [20, 34] scales quadratically in maxee(m] X4. Our K-EFR algorithm for the

---

full feedback setting builds upon the EFR algorithm, but specializes to the notion of K K-EFCE, and achieve an improved linear in ma X; iteration complexity.
Apart from the EFCE, there are other notions of (coarse) correlated equilibria in IIFGGs such as Normal-Form Corree-Cr Equilibria (NFCCE) [45, 10, 9, 18, 44], Extensive-Form Coarse- Correlated Equilibria (EFCCE) [17]. and Agent-Form
-oorre-Corree Equilibria (AF(C)CC) [38, 40]; see [33, 34] for a detailed comparison. All above notions are either weaker than or incomparable with the EFCE, and thus results there do not imply results for computing EFCE.
Learning Equilibria from bandit feedback A line of work considers learning Nash Equilibria (NE) in two-player zero-sum IIEGGs and NFCCE in multi-player general-sum IIEGGs from bandit feedback [30, 19, 15, 21, 43, 41, 28, 5]; Note that the NFCCE is weaker than (and does not imply results for learning) EFCE. Dudík and Gordon [14] consider sample-based learning of EFCE in succinct extensive-form games; however, their algorithm relies
approximate Markov-Chain Monte-Carlo (MCMC) sampling subroutine that does not lead to an end-to-end sample complexity guarantee. To our best knowledge, our results are the first for learning the EFCE (and K-FFCE) under bandit feedback.
Preliminaries
We formulate IIFGGs as
Markov games (POMGs) with tree structure and perfect
recall, following [28, 5]. For a positive integer we denote by [t] the set 21. .). For a finite set A, we let A (AA) denote the probability simplex over A. Let (*) denote the binomial coefficient (i.e. number of combinations) of choosing m elements from n different elements, with the convention
that (m) 0 if m n. We use m n to denote min {m, n2.
Partially observable Markov game partially observable Markov game
We consider an episodic, tabular, m-player, general-sum,
POMG S,
{& (
H. po: (Ph (reahe((m))e(n)
where S is the state space of size |S| S; X; is the space of information sets (henceforth infosets) for the nth player, which is a partition of S (i.e., Ty S S for all x2 E X, and S = L,,,,, where stands for disjoint union) with size [ player's emission (observation) function: AA, is the action space for the 7hh player with size [A, = A., and we let A A₁ ...Am denote the space of joint actions a (a1,.... 2m); H Eد is the time horizon: Po E A(S) is the distribution of the initial state $1: Ph. S x A + A(S) are transition probabilities where ph (sh+1 |sh, aq) the probability of transiting to the next state $/++1 from state-action (sh, a*)) E S x A: and ritk S x A - [0. 1] is the deterministic' reward function for the hh player at step h.
Xx,, and we also use I; : S + X₁ denote the 7t
Tree structure and perfect recall assumption We use a POMG with tree structure and perfect re- call to formulate imperfect information games??, following [28, 5]. We assume that the game has tree structure: for any state E S, there is a unique step h and history ($1, ai..... Sh-1. a Sh. = s) to reach s. Precisely, for any policy of the players, for any realization of the game (i.e., trajec- sf = s, it almost surely holds that We also assume perfect recall, which means that each player remembers its past informa- tion sets and actions. In particular, for each information set (infoset) x4 E X for the 7t player, there is a unique history past infosets and actions (z+,1, a1,1,............. -i,b- h-. Zy,4 2;) leading to T;, This requires that X, can be partitioned to H subsets (K,,)) such that Ti, E X., is reachable only at time step h. We define X == | Similarly, the state set S can be also partitioned into H subsets (-)) As we mostly focus on the thh player, we use F/ to also denote Ii,h and use them interchangeably.
tory) (5% (HT)) conditionally
and (s/......8) ..))..
8h)). (.1,...,
OOur results can be directly extended to the case of stochastic rewards.
We remark that POMGs with tree structure and perfect recall is specific subclass of POMGs; General
POMGs could possess different challenges and beyond the scope of this paper.
'Our definition of POMGs with tree structure and perfect recall can express any IIEFG satisfying an additional
mild condition called timeability [25]. Further, our algorithms and guarantees can be generalized directly to any general IIEFG that is necessarily timeable; see Appendix H.3 for discussions.
3

---

For s E S and 2, E Li we write notation, for S, we let (s) denote the ith player's infoset that belongs to. For any < h', Fith E K,,,, Tan X',' we write Liih x Lii if the information set Fi,h can be reached from information set Tiih by 1th player's actions; we write (Ta,h; 0i,h)) x ai,h if the infoset Ti,h can be reached from infoset Fi,h by 1th player's action ai,h- For any h < h' and Zi,h E Ri we let (ar,, (.,A. {ir K,N.' (Z..A. < z} and Cy (x,,) := {z R2 : Ii,h < r} = UaLAEA, (I as,a) denote the infosets within the h'-th step that are reachable from (i.e. children of) Fi, or (Ir dg,n), respectively. For shorthand, let Ca ag == C(Zi,,) C++1 (xiA,) denote the of immediate children.
if infoset æ; contains the state s. With an abuse of
asA)) and
Policies We use = (Ti, (e(f))))((FF...... (e(H))..... to denote policy of the 1th player, where each (+b,)))) E (AA)) the action distribution infoset 2i, We say my is pure policy M (-125,h) takes some single action deterministically for any (h, zi,h); in this case we let T; (=(.k,)) = TT (2).A) denote the action taken at infoset rish for shorthand. We use π {T; kejm) to denote a product policy for all players, and let T-; = {Ty i denote policies of all players other than the 7th player. We call и a pure product policy if is pure policy for all i E [m]] Let II; denote the set of all possible policies for the 1t player and IT = [[ee()] ПI, denote the of all possible product policies. Any probability measure हे on II induces a correlated policy, which executes as first sampling a product policy オ [e[m] E II from probability measure π and then playing the product policy т. We also use т to denote this policy. A correlated policy गे can be viewed as a mediator of the game which samples ı before the game starts, and privately recommends action sampled from T. (-1x;)) to the h player when infoset z; E X, is visited during the game.
Reaching probability With the tree structure assumption, for any state E S, and actions E A. there exists unique history ($1, a1...... ....... Sh. 8, a, a) ending with (s,, = 8, a = a). Given any product policy rT, the probability of reaching (#h, a4) at step h can be decomposed as
pi (sh; a) = PisA (sh) [Te[m)] Tr,1sh (8h, ai,h),
where we define the sequence-form transitions Pith and sequence-forn policies TT,1 as
(s.)(s)) == (s( II h-1 4al at²),
(2)
1i,1ch (8h, ai,x) = Ti ( (c,A) == I Te, (Ur, (Ti,
(3)
where (sw: ag) ant)ss-- is the unique history of states and actions that leads to 8h by the tree structure; Z4,4 2,)5)) is the 7t player's infoset at the h-th step, and (æi, a, ) is the unique history of infosets and actions that leads to Zi,h by perfect recall. We also define
Tadele (Fa,M,,
as,xr) (F
== T Te, (ai. (2,,ee) for any 1 S h h H.
Value functions and counterfactual loss functions Let Ve == Ex E re,n] denote the value function (i.e. expected cumulative reward) for the 7th player under policy π. By the product form of the reaching probability in (1), the value function V admits a multi-linear structure over the sequence-form policies. Concretely, fixing any sequence of product policies {x'}T_ where each n² = hem]. we have
H
Σ
PIeA (SN) II j=1
I (s)( a,,n),
h=1 (sh as
For any sequence of policies {Tr) we also define the counterfactual loss functions [45]
(Zi,, annlnnnaa))) as:
Σ
(s))(s)) II
(I,na( (s))
(4)
a E-
Li (1,h) = (i dith)
Σ
# (a an Dl (#w, aw).
M=h+1
zn Cereetrr E.E. EAi
(5)

---

Algorithm Executing modified policy Φ O n
Input: K-EFCE strategy modification E $ (0 K S oo), policy ni E [I for the 1th player.
1: Initialize recommendation history b = 0.
2: for h l.......4 !/ do
3: Receive infoset 2i,h E Xi
4: b 12!1. (#s,,)) then
Observe recommendation bn. R (-).,h))
6:
Take swapped action On = o(x,,, b, bn).
7:
Update recommendation history b 4- (b, ba) A
else
Must have b E 12 (I),,),, do not observe recommendation from w. 10: Take action = @(2,,h, b).
9:
Intuitively, L (Ti as,u) measures the 2th player's expected cumulative loss (one minus reward) conditioned on reaching (Ta.s, (s,A), weighted by the (environment) transitions and all other players' policies x_, at all time steps, and the 1th player's s own policy πद from step h + onward. We will omit the subscript and use L2 to denote the above when clear from the context.
Feedback protocol We consider two standard feedback protocols for our algorithms: full feedback, and bandit feedback. In the full feedback case, the algorithm can query a product policy n' [efmm]] in each iteration and observe the counterfactual loss functions i (Ti,ks ar,h) ) h.,.a,, exactly*. In the bandit feedback case, the players can only play repeated episodes with some policies and observe the trajectory of their own infosets and rewards from the environment.
K Extensive-Form Correlated Equilibria
We now introduce the definition of K Extensive-Foon Form Correlated Equilibria (K-EFCE) and establish its relationship with existing notions correlated equilibria IIFGGs.
3.1 Definition of K-EFCE
Intuitively, K-EFCE is correlated policy in which no player can gain if allowed deviate from the observed recommended actions K times, and forced to choose her own actions without observing further recommendations afterwards. To state its definition formally, letting A [(b..... [ow E A., 4h' < h), we categorize all possible recommendation histories (henceforth rechistories) at each infoset Zs,h X.,, (for the 7th player) into two types, based on whether the player has already deviated K times from past recommendations:
(1) A Type-I rechistory (S K-1 deviations happened) Righ is any action sequence bi:-11 E A such that Σ 1 {ax * ba) < K 1, where (a...... an-1) is the unique sequence actions leading T. Let (2(1).K (Ir,n) denote the of all Type-I rechistories Fi.h.
(2) A Type-Il rechistory (K deviations happened) at Ti,h is any action sequence bis E AW with length h' < h such that Σk'r -1 1 {ax * b = K - 1 and as + bw. where (a),... ah-1) is the unique sequence of actions leading to Ti,k- Let s2 ( (xi,1) denote the set of all Type-II rechistories Righ-
We now define a K-EFCE strategy modification (0 S S oc) for the 7th player.
Definition 1 (K-EFCE strategy modification). K-EFCE strategy modification (for the ith player) is mapping & of the following form: At any infoset Fi,h E Xi h. for any Type-I rechistory b
(.0)KK (I & swaps any recommended action by into @(zi,, 11 bn) Ai; for any Type-Il rechistory bra E ( (I,,n), & directly takes action of bis)) E A:.
'This is implementable (and slightly more general than) when the full game (transitions and rewards) is known.
5

---

Let o denote the set of all possible K K-EFCE X-EFCEEstrateg)) strategy modifications for any 0 S K S cc. Formally, for any & E & and any pure policy n, E ETT, we define the modified policy @ o n2 as in Algorithm 1.
We parse the modified policy o o πV (Algorithm 1) follows. Upon receiving the infoset 21,6 at each step h, the player has the rechistory b containing all past observed recommended actions. Then, b is Type-I, i.e. at most K 1 deviations have happened (Line 4), then the player observes the current recommended action ,₁ = i (.), takes potentially swapped action as = (( b, bn) (Line 6), and appends b, to the recommendation history (Line 7). Otherwise, (xi,n, b) is Type-II, i.e. K deviations have already happened. In this case, the player does not observe the recommended action, and instead takes an action dn = ((Ti,A, .. b), and does not update b (Line 10).
We now define K- K-EFCE as the equilibrium induced by the K-EFCE strategy modification set g.K With slight abuse of notation, we define & o for any correlated policy to be the policy (6OT.) X T-b where π ~ मे is the product policy sampled from म.
Definition 2 (K-EFCE). correlated policy π is an e-approximate K Extensive- Correlated Equilibrium (K-FFCE) if
K- K-EFCEGGp(TT max max (v. v,7) Se.
We say ग. is an (exact) K-EFCE if K- K-EFCEGGa(TT) =0.
3.2 Properties of K-EFCE
The K-EFCE is closely related to various existing definitions of correlated equilibria in IEFGSs We show that the special case of K = is equivalent to the existing definition of EFCE based on trigger policies (Proposition C.I); The K-EFCE are indeed stricter equilibria as K' increases (Proposition C.2); The two extreme cases K and oo are equivalent to (Normal-Form) Coarse Correlated Equilibrium and the "Behavioral Correlated Equilibria" of [34]s, respectively (Proposition C.3). Due to the space limit, the full statements and proofs are deferred to Appendix C.
4 Computing K-EFCE from full feedback
Algorithm description We first present our algorithm for computing K-EFCE in the full-feedback setting. Our algorithm K Extensive- Regret Minimization (K-FFR), described in Algorithm 2, an uncoupled no-regret algorithm aiming to minimize the following K-EFCE regret
Rº k == max ΣT (v. (y.dom xm'_ -v.dortxot V.T')
(6)
By standard that the average joint policy over all players is an approximate K-EFCE (Lemma E)
conversion, achieving sublinear K-EFCE regret for every player implies
At a high level, our Algorithm 2 builds upon the EFR algorithm of Morrill et al. [34] to minimize the K-EFCE regret R, K by maintaining regret minimizer Re,, (using algorithm REGALG) at each infoset Fi, E X; that is responsible for outputting the policy (-(a,,))) E A (Line 8) which combine to give the overall policy o. for the 1-th iteration.
Core to our algorithm is the requirement that Rz., REGALG should be able to minimize regrets with time selection functions and strategy modifications (also known as the wide range regret) [31, 6]. Specifically, R.,,, needs to control the regret
max EL Ih= 7/ (xn) (( (Fin(11a)) - y po
th. (aa.)) D
D ())
(7)
for all possible Type-I rechistories b E (, simultancously, where IL 1 T/ (bul2x)) =: St the time-selection function (i.e. a weight function) associated with this Piuh1 (cf. Line 5), and v = (v= A4 + AA, is the set of all swap modifications from the action set A,, onto itself. (An analogous regret for Type-II rechistories is also controlled by R Controlling these "local"
'Up to minor difference that our co- OF-EFCE only defines the equilibrium in terms of the overall game value, where the BCE additionally requries similar equilibrium properties to hold in certain subgames.

---

Algorithm 2 K-EER with full feedback (ith player's version)
Input: Algorithm REGALG for minimizing wide range regret; learning rates (Naza Ea
I: Initialize regret minimizers (Re,a JUA with REGALG and learning rate Thr for iteration/ = I....: ...
3: for h = 1,... H do
4: for 21,A E X.. do
Compute S IIk= h-1 vrixebblaag for all h E (2(T. (I.,)).
5:
6:
Compute St I mi, (belae) for all bl E S (2r,a).
7:
OBSERVE TIMESELECTION( tonn-een (aLa) U eo (ann))
8:
Set policy (-(.)) + R2,,, RECOMMEND()
9:
Observe counterfactual losses { (Lí (JrL,, an) horeiin (depending on nf and wi,; cf. (5)).
10: for all Fi,h X. do OBSERVE OBSERVE Loss( L (xLL, aaa.) Output: Policies { ME=1.
regrets at each Fi,h guarantees that the overall K-EFCE regret is bounded, by the K-EFCE regret decomposition (cf. Lemma E.2).
To control this wide range regret, we instantiate REGALG WRHEDGE (Algorithm 4; ef. Appendix A.2), which is similar as the wide regret minimization algorithm in [27], with a slight modification of the initial weights suitable for our purpose (ef. (11)). The learning rate is set
H (KAR) X, AKAH log (H2T)
for all Ti Xg With this algorithm in place, at each iteration, Re., observes all time selection functions (Line 7), computes the policy for the current iteration (Line 8), and then observes the loss vector L (Ti,k..) (Line 9) that is useful for updating the policy in the next iteration.
Theoretical guarantee We are now ready to present the theoretical guarantee for K-EFR.
Theorem 3 (Computing K-EFCE from full feedback). For any 0 S K S oo, E E (0, HJ, let all players run Algorithum 2 together in self-play fashion where REGALG is instantiated as Algorithm 4 with learning rates specified in (8). Let n² = (m]m) denote the joint policy of all players at the t 'tth iteration. Then the average policy π = Unif(( (TT))) satisfies K-EFCEGap(TT S E, as long as the number of iterations
T> = (KKM)) H (maxiemm) (:AKAH))//EE)
where
[m] Ad) is a log factor and O(.) hides poly (H) factors.
In the special case of K 1, Theorem 3 shows that K-EFR can compute an E-approximate 1-EFCE within (mmaxee xEA iterations. This improves over the existing O(maxee[m) X?22/=²) it- eration complexity of Celli al. [11], Farina et al. [20] by a factor of XçA,, Also, compared with the it- eration complexity of the optimistic algorithm of [3] which is at least Ö(maxsejm) X A4/3 / 4/3/6 we achieve lower X; dependence (though worse & dependence).
For < K < 20, Theorem 3 gives sharp Ō(( H (maxie(m) X,AKAH)/e iteration complex- ity for computing K-EFCE. This improves over the Ō((K (max;e X²AKAH) rate of EFR [34] instantiated to the K-EFCE problem. Also, note that although the term AKAH is exponential in K (for K H), this is sensible since it is roughly the same scale the number of possible recommendation histories, which also the "degree of freedom" within a K-EFCE strategy modification. Apart from learning equilibria, Algorithm 2 also achieves a low K-EFCE regret when controlling the jth player only and facing potentially ad adversarial opponents:
'More precisely. Anagnostides al. [3. Corollary 4.17] proves ((X, max., mla [|T.I///ee/) iteration complexity, which specializes to the above rate, for any 8 > game with max=;em1 || 2 X!!6 can be constructed.
7

---

Algorithm 3 Loss estimator for Type-II rechistories via Balanced Sampling (ith player's version)
Input: Policy ni. v'... Balanced exploration policies (x""")e((zr) ]ne[z]]-
I: for K & H < S H, W - [h]] with W| = K and ending in h do
2: Set policy my (.)
(Fi,) )= (kewugn(+1.....) (Mi,,)eepe) T1(++))).
3: Play n. T...l.ik w)) w) x T'= for one episode, observe trajectory
(2/,1 (0221 (.) C.(..'.. w) (.
1,8 14,8 (1. 1.
(. 6.066'.) (.l...))))
for all (2i, b14)) E 22, (2 do
4:
5:
Find (z.,1 01) 2... < (IiAA-1, an-1) 1) x aidh
6: Set W & {K E [W'] by o ax
7:
Construct loss estimator for all E
A.M. W) (.0...W)) 1)) (mrana)
H
Li (ann f-
Σ
(1
(1- s,1""
(9)
M.C. W)
(20,h,
Output: Loss estimators
[ ((
R S &6( ( (KAH)) (Corollary F.I). In particular, the OVVX,T) scaling is optimal up to log factors, due to the fact that RT,x 2 R.,o (i.e. the vanilla regret) and the known lower bound R 2 (VV,TT) in IIEFGs [42].
Proof overview Our Theorem follows from a sharp analysis on the K-EFCE regret of Algo- rithm 2, by incorporating (i) decomposition of the K- K-EFCEGap into local regrets at each infoset with tight leading coefficients (Lemma E.2), and (ii) loss-dependent upper bounds for the wide range regret of WRHEDGE (Lemma A.2), which when plugged into the aforementioned regret decomposition yields the improved dependence in (X,AK over the analysis of Morrill et al. [34] (Lemma F.1 & F.2), and also the X,A, factor improvement over the results of [11, 20] in the special case of K = 1. The full proof can be found in Appendix F.
5 Learning K-EFCE from bandit feedback
We now present Balanced K-EFR, a sample-based variant of K-EFR that achieves a sharp sample complexity in the more challenging bandit feedback setting. Our algorithm relies the following balanced exploration policy [19, 5]. Recall that [C, (Ti,Mr ((,x)) ) is the number of descendants of (Di,N; (D.,N: within the h-th layer of the 7th player's game tree (cf. Section 2).
Definition 4 (Balanced exploration policy). For any 1 S h S H, we define n, n,th the (ith player's) balanced exploration policy for layer h as
+h Ti,h (a (aw (ww) == (Ia, ar, 11/1)l///a (xa,e)) for all (e,,,,aik) E Xi Ai, M S
+ and -i (ar, (x,,) := 1/A. h
+h Note that there are H such policies, one for each layer h. We remark that the construction of T, requires knowledge about the descendant relationships among the :hh player's 's infosets, which is a mild requirement (e.g. can be efficiently obtained from one traversal of the 7th player's game tree; Appendix H.2 for a detailed discussion about this requirement).
Algorithm description (sampling part) Our Balanced K K-EFR (deferred Algorithm 7) builds upon the full feedback version of K-EFR (Algorithm 2). The main new ingredient within Algorithm 7 to use sample-based loss estimators obtained by two balanced sampling algorithms (Algorithm & 6), one for each type of rechistories. Here we present the sampling algorithm for Type-Il rechis- tories in Algorithm 3; The sampling algorithm for Type-T rechistories (Algorithm 6) designed similarly and deferred to Appendix G.1 due to space limit. Algorithm 3 performs two main steps:
8

---

Line 1-3 (Sampling): Construct policies { (r..(h.h''.) that interlaced concutenations of the current of and the balanced policy प. and play one episode using each policy against T'-g.
Line 7: Construct loss estimators (L aa, by (9), which for each Fi,h and byd E 2 (zi,n) is an unbiased estimator of counterfactual losses [L a)A. that will used by Algorithm be fed into the regret minimization algorithm REGALG.
We remark that the sampling policies { 1r2. " in Algorithm are interlaced concatenations of of and nz. along time steps h, where the policy take at each h is determined by W. These policies are generalizations of the sampling policies in the Balanced CFR algorithm of Bai et al. [5] (which can be thought of as simple con-interlaciig concatenation). They allow time-selection aware sampling: Each loss estimator Li achieves low variance relative the corresponding time selection function St Syo Further, there is an efficient sharing of sampling policies, as here roughly (KAH) X;AA A loss estimators (one for each (Ii,n, by are constructed using only (a much lower number of) H (xWM) policies.
Stochastic wide-range regret minimization Algorithm 7 requires the wide-range regret minimiza- tion algorithm REGALC to additionally handle the stochastic setting, i.e. minimize the wide-range regret (e.g. (7)) when fed with our sample-based loss estimators. Here, we instantiate REGALG be SWRHEDGE (Algorithm 5), a stochastic variant of WRHEDGE, with hyperparameters
(AAH) X, AKKKHHH
+AH+1 log(8 Eie(m) X:A:/p)/(H3T), I. H.
(10)
SWRHEDGE is a non-trivial extension WRHEDGE the stochastic setting, as in each round admits multiple sample- based loss estimators, one for each time selection function, with the same mean (cf. Line 8). This is needed since Algorithm 3 uses different sampling policies to construct the loss estimator I L'
(.) for each bia 2. (I),K (Is,a) (ef. (9)).
Theoretical guarantee We now present main result for the bandit feedback setting,
Theorem 5 (Learning K-EFCE from bandit feedback). For any 0 S K S co, & E (0, H and p E [0, 1), letting all players run Algorithm 7 together self-play fashion for T iterations, with REGALG instantiated as SWRHEDGE (Algorithm 5) with hyperparameters in (10). Let n'
{ (EEm)) denote the joint policy of all players the l'th iteration. Then, with probability at least p. the correlated policy π Unif((=*)TT)) satisfies K K-FFCEGGa((2) S e, as long as H 2 O(H (kx.)) (maxse|m) X,A, (.AAH+1))/// )/=="). The total number of episodes played
KAH ( (KAA) T = =0 KAH) ( (maxiElm) X,A KAHH! ((AA+)))/E2)))
where: i = log(8 Eie(m)] X,A:/p) is a log factor and O(-) hides poly (H) factors.
To our best knowledge, Theorem 5 provides the first result for learning K-EFCE under bandit feedback. The sample complexity Ö( ((())) maxxe[m] (X,A (KAAAM++)//+ (ignoring m, factors) has only an (KA)) A; additional factor over the iteration complexity in the full feedback setting (Theorem 3), which is natural The (x*,)) comes from the number of episodes sampled within each iteration (Lemma G. and the A, arises from estimating loss vectors from bandit feedback. In particular, the special case of K provides the first result for learning EFCEs from bandit feedback, with sample complexity ((max,e(mn) /E2) We remark that the linear in X; dependence at all K 2 0 is optimal, the sample complexity lower bound for the K = O case (learning NFCCEs) already { X, AeA, [5]". Also, the policies {m] ] maintained in Algorithm also achieves sublinear K-EFCE regret. However, strictly speaking, this is not a regret bound of our
1.(h.k' actually used are not nद.
algorithm, as the sampling policies π.
Proof overview The proof of Theorem 5 builds on the analysis in the full-feedback case, and further relies on several new techniques in order to achieve the sharp linear max;e[mi X, sample
'The sample complexity lower bound in [5] is stated for learning Nash Equilibria in two-player zum IEFGss but can be directly extended to learning NFCCEs in multi-player general-sum IIEFGs.

---

complexity: (1) A regret bound for the SWRHEDGE algorithm under the same mean condition (Lemma A.3). which may be of independent interest; (2) Crucial use of the balancing property of n; (Lemma B.4) to control the variance of the loss estimators a (+), which in turn produces sharp bounds on the regret terms and additional concentration terms (Lemma G.4-G.9). The full proof can be found in Appendix G.3.
6 Conclusion
This paper proposes K-EFCE, generalized definition of Extensive-Form Correlated Equilibria Imperfect- Inffrcct-Infommttionnnooo Games, and designs sharp algorithms for computing K K-EFCE under full feedback and learning a K-EFCE under bandit feedback. Our algorithms perform wide-range regret minimization over each infoset to minimize the overall K-EFCE regret, and introduce new efficient sampling policies to handle bandit feedback. We believe our work opens up many future directions, such as accelerated techniques for computing K-EFCE from full feedback, learning other notions of equilibria from bandit feedback, as well as empirical investigations of our algorithms.
Acknowledgment
The authors thank Brian Hu Zhang for discussions regarding the relationship between the co-EFCE and the BCE. S.M. is supported by NSF grant DMS-2210827.
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
[2] loannis Anagnostides, Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster no-regret learning dynamics for extensive-form correlated equilibrium. 2021.
[3] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, and Tuomas Sandholm. Faster no-regret learning dynamics for extensive-form correlated and coarse correlated equilibria. arXiv preprini urXiv:2202.00444 2022.
[4] Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of mathemati- cal Economics, 1(1):67-96, 1974.
[5] Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. arXiv preprint arXiv:2202.01752, 2022.
[6] Avrim Blum and Yishay Mansour. From external internal regret. Journal of Machine Learning Research, 8(6), 2007.
[7] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
[8] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365 (6456):885-890 2019.
[9] Neil Burch, Matej Moravcik, and Martin Schmid. Revisiting cfr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429 443, 2019.
[10] Andrea Celli, Alberto Marchesi, Tommaso Bianchi, and Nicola Gatti. Learning to correlate in multi-player general-sum sequential games. Advances in Neural Information Processing Systems, 32, 2019.
[11] Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for extensive-fomm correlated equilibrium. arXiv preprint arXiv:2004.0060) 2020.
[12] Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing nash equilibrium. SIAM Journal Computing, 3951), 2009.
10

---

[13] Miroslav Dudik and Geoftrey Gordon. A sampling- approach to computing equilibria in succinct extensive-form games. arXiv preprint arXiv: 2012.
[14] Miroslav Dudík and Geoffrey Gordon. sampling-basee approach to computing equilibria in succinct extensive- games. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 151-160, 2009.
[15] Gabriele Farina and Tuomas Sandholm. Model-free online learning in unknown sequential decision making problems and games. arXiv preprint arXiv:2103.045: 2021.
[16] Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive-form games: Saddle-point formulation and benchmarks. Advances in Neural Information Processing Systems, 32, 2019.
[17] Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm, Coarse correlation in extensive- form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1934-1941, 2020.
[18] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. arXiv preprint arXiv:2007. 14358, 2020.
[19] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Stochastic regret minimization in extensive-form games. International Conference on Machine Learning, pages 3018-3028. PMLR, 2020.
[20] Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. arXiv preprint arXiv:2104.01522 2021.
[21] Gabriele Farina, Robin Schmucker, and Tuomas Sandholm. Bandit linear optimization for sequential decision making and extensive- games. arXiv preprint urXiv:2200 00046, 2021.
[22] Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference Machine learning, pages 360-367, 2008.
[23] Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International conference on machine learning, pages 805-813. PMLR, 2015.
[24] Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics, pages 513. Springer, 2008
[25] Sune K Jakobsen, Troels Sørensen, and Vincent Conitzer. Timeability extensive-form games. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 191-199, 2016
[26] Albert Xin Jiang and Kevin Leyton-Brown. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior, 91:347-359, 2015.
[27] Subhash Khot and Ashok Kumar Ponnuswami. Minimizing wide range regret with time selection functions. In COLT, pages 81-86, 2008
[28] Tadashi Kozuno, Pierre Ménard, Rémi Munos, and Michal Valko. Model-free learning for two-player zero-sum partially observable markov games with perfect recall. arXiv preprint arXiv:2106.0627,, 2021.
[29] Harold W Kuhn. Extensive games and the problem of information. Contributions to the Theory of Games (AM-28), Volume II, pages 193-216. Princeton University Press, 1953.
[30] Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H Bowling. Monte carlo sampling for regret minimization extensive games. In NIPS, pages 1078-1086. 2009.
[31] Ehud Lehrer. A wide range no-regret theorem. Games and Economic Behavior, 42(1):101-115, 2003.
11

---

[32] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337:5588-13,, 2017.
[33] Dustin Morrill, Ryan D'Orazio, Reca Sarfati, Mare Lanctot, James R Wright, Amy Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. arXiv preprint arXiv:2012.05874 2020.
[34] Dustin Morrill, Ryan D'Orazio, Mare Lanctot, James R Wright, Michael Bowling, and Amy R Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. In International Conference on Machine Learning, pages 7818-7828. PMLR, 2021.
[35] John F Nash al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-44) 1950.
[36] Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi- player games. Journal of the ACM (JACM), 55(3):1-29, 2008
[37] Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Mare Lanctot, Zach Holland, al. Player of games. arXiv preprint arXiv:2112.03118, 2021.
[38] Reinhard Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4, 1975.
[39] Yuandong Tian, Qucheng Gong, and Tina Jiang. Joint policy search for multi-agent collaboration with imperfect information. arXiv preprint arXiv:2008. 06495, 26649,00,,006495
2020.
[40] Bernhard Von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4):1002-102) 2008.
[41] Brian Hu Zhang and Tuomas Sandholm. Finding and certifying (near-) optimal strategies in black-box extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5779-5788, 2021.
[42] Yichi Zhou, Tongzheng Ren, Jialian Li, Dong Yan, and Jun Zhu, Lazy-cfr: fast and near optimal regret minimization for extensive games with imperfect information. arXiv preprint arXiv:1810.0443: 2018.
[43] Yichi Zhou, Jialian Li, and Jun Zhu. Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information. In International Conference on Learning Representations, 2019.
[44] Yichi Zhou, Tongzheng Ren, Jialian Li, Dong Yan, and Jun Zhu. Lazy-cfr: fast and near- optimal regret minimization for extensive games with imperfect information. In International Conference on Learning Representations, 2020. URL //opereve/pee net/forum? id 1x4pJXYE
[45] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini- mization in games with incomplete information. Advances neural information processing systems, 20: 172--1736, 2007.
12


Reviews:
[{"review_id": "vkqYtKrba8J", "reviewer": "Reviewer_hT1T", "summary": "The paper has 3 main contributions. First, the authors propose a generalization of extensive-form correlated equilibrium (EFCE), known as K-EFCE. In this generalization, players continue to receive recommendations even after they have deviated from their recommendations (received at each infoset, just like regular EFCE) for up to K deviations. K-EFCE encompass a number of common equilibrium concepts. A 1-efce is just a regular EFCE, while a 0-EFCE is a normal-form CCE.  The second key contribution is a self-play algorithm to compute K-EFCE, which the authors call K-EFR. The third contribution is the a variant of K-EFR that can handle bandit feedback. The authors claim that this is the first algorithm for learning EFCE from bandit feedback.", "questions": "1. I would have liked a discussion on how K-EFCE could be implemented. In the original EFCE paper by von Stengel, EFCEs were implemented by means of sealed recommendations, even though the more popular formulation today is based on [13, 16], which use an equivalent formulation based on trigger sequences. How can a mediator (practically) achieve a K-EFCE where K > 1?\n\n2. The authors use POMG as their choice of framework, rather than extensive form games. Is there a difference between the 2, given that the POMG is restricted to be tree structured?\n\n", "limitations": "-", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Generally, I felt there was too much content to follow and feels more suitable for a journal. In particular, the part on bandit feedback feels rather cramped (though it is an important contribution in its own right). Given the authors’ claim that K-EFR outperforms [11], [20], I felt it would be good to give a more detailed sketch on the key differences between these methods—-this is currently done in lines 233-240, which (at least to me) was rather opaque. This should help to make the paper more accessible.\n\nOther than that, the paper seems good, except for the aforementioned points about it not being as accessible to readers not already familiar with EFR.\n\nSmall quips:\nIn the definition of Type-I rechistories, $\\mathcal{A}_i^{h-1}$ is not defined.\n\nNote: The paper is entirely theoretical with many pages of proof. I did not go through all the proofs, especially those in the appendix. I am not familiar with the state of the art EFCE solvers, and am unable to definitively comment on the authors’ claims with regard to comparison with other works.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V2MqL9_YCUX", "reviewer": "Reviewer_tyaC", "summary": "This paper studies the problem of learning extensive-form correlated equilibria (EFCE) in imperfect-information extensive-form games. In particular, the paper introduces a new notion of EFCE, called K-EFCE, in which a player does not stop receiving recommendation right after the first time they deviate, but they continue to receive them up to their K-th deviation. The paper studies the problem of learning K-EFCE, and it provides sample-efficient algorithms for both the full feedback and the bandit feedback settings.", "questions": "1) Can you please address my concern in the second point of the quality assessment?\n---------- AFTER AUTHORS' RESPONSE ----------\nThe authors clarified my concerns about the applicability of their algorithms to non-timeable perfect-recall games. As a result, I raised my score to 7 (from an original score of 6).", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "ORIGINALITY\n\n(+) To the best of my knowledge, this is the first paper that proposes sample-efficient no-regret learning dynamics that converge to EFCEs under the bandit feedback model.\n\nQUALITY\n\n(+) As far as I am concerned, the results in the paper are correct, though I did not check all the proofs in the details.\n\n(-) I only have one major concern about the formalization of imperfect-information extensive-form games with perfect recall. In particular, the authors claim that in order to have perfect recall it should be possible to partition the information sets of one player according to the tilmestep they belong to. However, the fact that the game is perfect recall does not necessarily imply that the states in the same infoset all refer to the same timestep of the game. Indeed, this is not the case whenever the game is not timeable. As far as I am concerned, the results in the paper rely on the assumption that the game is timeable, which is a more restrictive assumption than perfect recall only. If this is correct, this would somehow limit the impact of the results. See the following paper for a reference on timeability of extensive-form games:\n\n“Jakobsen, S. K., Sørensen, T. B., & Conitzer, V. (2016, January). Timeability of extensive-form games. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (pp. 191-199).”\n\nCLARITY\n\n(+) The paper is well written and all the concepts are well presented.\n\n(-) My only concern regarding the presentation is that too many results are in the appendix, which renders the main paper (perhaps too much) high level in terms of technical details.\n\nSIGNIFICANCE\n\n(+) The problem of learning EFCEs is receiving considerable attention over the last few years from the algorithmic game theory community and beyond. Thus, this paper could be of interest for a considerable portion of the NeurIPS community (as also testified by the Best Paper Award at NeurIPS 2020).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G38nDnnZD5o", "reviewer": "Reviewer_RRjP", "summary": "The paper's main contributions are threefold:\n\n1. The notion of K-EFCE is defined. It is a generalization of EFCE, whereby the mediator (correlation device) can condition their recommendation based on the number of deviations of each player, which can be any number between 0 and K. After K deviations have been reached, the mediator will stop issuing recommendations. K-EFCE is a natural generalization of EFCE: in fact, EFCE is simply a 1-EFCE.\n\n2. The paper shows that, within the *full-information* setting, an $\\epsilon$-approximated K-EFCE can be computed by means of uncoupled no-regret dynamics after running $\\tilde O(A^K / \\epsilon^2)$ iterations where $A$ is the maximum number of player actions (equivalently, each player is guaranteed to cumulate $\\tilde O(A^K \\sqrt T)$ regret after $T$ iterations).\n\n3. The paper shows that, withing the *trajectory-bandit setting*, an $\\epsilon$-approximated K-EFCE can be computed by means of uncoupled no-regret dynamics after running $\\tilde O(A^{K+1} / \\epsilon^2)$ iterations where $A$ is the maximum number of player actions (equivalently, each player is guaranteed to cumulate $\\tilde O(A^{K+1} \\sqrt T)$ regret after $T$ iterations).\n", "questions": "1. Can you please respond to my questions in the \"Clarity and quality\" assessment above?\n\n2. Currently, the main factor driving my (positive!) score is the originality of the work. While I also gave a good look in the appendix, it is possible---especially given the volume of a 60-page paper---that I might have missed some particularly innovative analysis tool that was used in this paper. If that's the case, please push back on my assessment above.\n\n3. Can you please confirm that your algorithm cannot be used in adversarial bandit-feedback settings (as it requires exploring the opponent for several episodes assuming the opponent's strategy does not change)?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I want to start by saying that I think the paper represents interesting, well-executed, high-quality work. Despite the very tight page limits, the body is well-organized and easy to follow. The appendix is also well-organized, and contains a trove of additional interesting results---I especially enjoyed browsing through appendix C.\n\nSignificance: I believe the paper contributes interesting results that fit well within the current research trend around extensive-form games. For example, learning EFCE with bandit feedback is a natural and interesting question.\n\nOriginality: The extension from EFCE to K-EFCE is interesting conceptually, and like I said I believe the paper is well executed and addresses relevant questions. In terms of significance, my impression is that the paper does not introduce any groundbreaking tool in the space. Rather, it fundamentally combines several expected existing techniques, such as balanced exploration policies and standard decompositions of Phi-regret for EFCE, obtaining results that were perhaps easy to guess for an expert in the field. I want to be clear that I am not saying that the paper is trivial---the authors put together and master several specialized tools, creating a paper that I expect will be very well received in the community. \n\nClarity and quality: the paper is very well executed and polished, both in the body and in the appendix. There is only one point that I found was slightly confusing: on lines 40-41, the bandit feedback setting is introduced as the opposite of the case in which \"the full game is known\". Just to be clear: your bandit algorithm still requires that at least the *decision space* (treeplex) of each player be known so that the balanced exploration strategy can be instantiated, correct? So, this bandit algorithm is not akin to, say, that of the cited works by Farina and Sandholm (\"Model-Free Online Learning...\") or Kozuno et al. (\"Model-free learning\"), which instead address both an unknown structure *and* bandit feedback on the utilities?\n\nMinor nits:\n- Abstract, line 9: I would avoid \"more generalized\" in favor of either \"generalized\" or \"more general\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "05G9T4HtyEb", "reviewer": "Reviewer_cdkB", "summary": "The authors first introduce a new equilibrium concept: K-EFCE in extensive-form games. Then the authors propose sample-efficient regret-minimization based algorithms to learn the equilibrium in both full-information and bandit feedback. When K=1 under the bandit feedback, this is the first sample-efficient algorithm to learn EFCE. ", "questions": "1. While this is not specific to this paper, I think POMGs are much more general than the authors introduce. Specifically, a POMG, like a POMDP, should have an observation model $O(\\cdot|s,a)$, which is a conditional probability given state s and action a. In the paper, the authors simplify this to a partition of the state space, which is sufficient for IIEFGs but I think POMGs are more than that and there is no need to bring up this term. \n\n2. Why is K-EFCE is an interesting extension to EFCE? Without this extension, can the reducing algorithms be further simplified? \n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To me it seems like the most important contribution of this paper is the first sample-efficient algorithm to learn EFCE under the bandit feedback. On the other hand, I don't really get why the authors introduce K-EFCE, a generalization of EFCE. Intuitively, we can definitely consider this generalization, but I don't know if the generalization induces interesting concepts or properties and the contribution I mentioned can completely hold without this generalization if I understand correctly.  \n\nIn terms of algorithms, it directly adapts WRHedge for the online learning literature, which is quite reasonable but I think this may limit the novelty of this paper. In the bandit setting, it looks like the balanced sampling idea also comes directly from another paper. Another weakness of this paper is probably the lack of experimental evaluations of the algorithms. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept