Faster No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
Authors: Ioannis Anagnostides
Gabriele Farina
Christian Kroer
Tuomas Sandholm
Venue: ICLR 2022 Submitted (2022)

Abstract: A recent emerging trend in the literature on learning in games has been concerned with providing accelerated learning dynamics for correlated and coarse correlated equilibria in normal-form games. Much less is known about the significantly more challenging setting of extensive-form games, which can capture sequential and simultaneous moves, as well as imperfect information. In this paper, we develop faster no-regret learning dynamics for \textit{extensive-form correlated equilibrium (EFCE)} in multiplayer general-sum imperfect-information extensive-form games. When all agents play $T$ repetitions of the game according to the accelerated dynamics, the correlated distribution of play is an $O(T^{-3/4})$-approximate EFCE. This significantly improves over the best prior rate of $O(T^{-1/2})$. One of our conceptual contributions is to connect predictive (that is, optimistic) regret minimization with the framework of $\Phi$-regret. One of our main technical contributions is to characterize the stability of certain fixed point strategies through a refined perturbation analysis of a structured Markov chain, which may be of independent interest. 
Finally, experiments on standard benchmarks corroborate our findings.

Under review as a conference paper at ICLR 2022
FASTER NO-REGRET LEARNING DYNAMICS FOR EXTENSIVE-FORM CORRELATED EQUILIBRIUM
Anonymous authors Paper under double-blind review
ABSTRACT
A recent emerging trend in the literature on learning in games has been concerned with providing accelerated learning dynamics for correlated and coarse correlated equilibria in normal-form games. Much less is known about the significantly more challenging setting of extensive- and simultaneous moves, as well as imperfect information. In this paper, we de- velop faster no-regret learning dynamics for extensive form correlated equilibrium (EFCE) in multiplayer general-sum When all agents play T repetitions of the game according to the accelerated dy- namics, the correlated distribution of play is an O (/4) -app--xiiioo EFCE. This significantly improves over the best prior rate of O 1/3). One of our conceptual contributions is to connect predictive (that is, optimistic) regret mini- mization with the framework of @-regret. One of our main technical contributions is characterize the stability of certain fixed point strategies through a refined perturbation analysis of a structured Markov chain, which may be of independent interest. Finally, experiments on standard benchmarks corroborate our findings.
games, which can capture sequential
extensive-form games.
INTRODUCTION
Game-theoretic solution concepts describe how agents should rationally act in games. Over the last two decades there has been tremendous progress in imperfect-information game solving and algorithms based on game-theoretic solution concepts have become the state of the art. Prominent milestones of this were an optimal strategy for Rhode Island hold' em poker (Gilpin & Sandholm, 2007), near-optimal strategy for limit Texas hold' em (Bowling et al., 2015), and a superhuman strategy for no-limit Texas hold' em (Brown & Sandholm, 2017). In particular, these advances rely on algorithms that approximate Nash equilibria (NE) of two-player zero-sum extensive-fore games (EFGs). EFGs are a broad class of games that capture sequential and simultaneous interaction, and imperfect information. For two-player zero-sum EFGs, it is by now rell-understood how to compute a Nash equilibrium at scale: in theory this can be achieved using accelerated uncoupled no- regret learning dynamics, for example by having each player use an optimistic regret minimizer and leveraging suitable distance distance-generatiin generating functions (Hoda et al., 2010; Kroer et al., 2020; Farina et al., 2021c) for the EFG decision space. Such a setup converges to an equilibrium at a rate of OTT-1). In practice, modern variants of the counterfactual regrel minimization (CFR) framework typically lead to better performance, although the worst-case convergence rate is 1(2-1/2) (Zinkevich et al., 2007). CFR is also an uncoupled no-regret learning dynamic.
However, many real-world applications are not two-player zero-sum games, but instead have general-sum utilities and often more than two players. In such settings, Nash equilibrium suffers from several drawbacks when used as prescriptive tool. First, there can be multiple equilibria, and an equilibrium strategy may perform very poorly when played against the "wrong" equilibrium strategies of the other player(s). Thus, the players effectively would need to communicate in order to find an equilibrium, or hope to converge to via some sort of learning dynamics. Second, find- ing Nash equilibrium is computationally hard both in theory (Daskalakis al., 2006; Etessami & Yannakakis, 2007) and in practice (Berg & Sandholm, 2017). This effectively squashes any hope of developing efficient learning dynamics that converge general-sum Nash equilibria.
A competing notion of rationality proposed by Aumann (1974) is that of correlated equilibrium (CE), typically modeled via trusted mediator who privately recommends actions to the players.

---

Under review as a conference paper at ICLR 2022
Unlike NE, it is known that the latter can be computed in polynomial time and, perhaps even more importantly, it can be attained through uncoupled learning dynamics, where the players only need to reason about their own observed utilities. This overeomes the often unreasonable presumption that players have knowledge about the other players' utilities. At the same time, uncoupled learning algorithms have proven to be a remarkably scalable approach for computing equilibria in large-scale games, described above. The basic CE notion is defined for normal-form games, and there it has long been known that uncoupled no-regret learning dynamics can converge to CE or the coarse correlated equilibrium (CCE) variant at rate of O(T-1/2) (Hart & Mas-Colell, 2000; Celli et al., 2019). More recently, it was shown that accelerated uncoupled no-regret learning dynamics can compute CCE and CE at rate of 33743 (Syrgkanis et al., 2015; Chen & Peng, 2020).
In the context of EFGs, the idea of correlation is much more intricate, and there are several no- tions of correlated equilibrium, based on when the mediator gives recommendations and how the mediator reacts to players who disregard the advice. One of the most compelling notions for EFGs is the extensive-form correlated equilibrium (henceforth EFCE) (von Stengel & Forges, 2008) for extensive-fore games with perfect recall. Because of the sequential nature, the presence of private information in the game, and the gradual revelation of recommendations, the constraints associated with EFCE are significantly more complex than for normal-form games. For these reasons, the question of whether uncoupled learning dynamics can converge to an EFCE was only very recently resolved by Celli et al. (2020). Moreover, in follow-up work they also established an explicit rate of convergence of 1/2) (Farina et al., 2021a). Our paper is concerned with the following fundamental question: Can one develop faster uncoupled no-regret learning dynamics for EFCE?
Contributions. Our primary contribution is to answer this question in the positive:
Theorem 1.1. On any finite perfect-recall general-sum multiplayer extensive-form game, the un- coupled no-regret learning dynamics described in this paper lead to a correlated distribution of play that is an -/rr-//))pppoiiinn EFCE, where the O()) notation suppresses game-specific parameters polynomial in the size of the game.
We achieve this result using the framework of predictive (also known as optimistic) regret mini- mization (Chiang et al., 2012; Rakhlin & Sridharan, 2013b). One of our conceptual contributions is to connect this line of work with the framework of 4-regret minimization of Greenwald & Jafari (2003); Gordon et al. (2008), by providing general template for stable-predictive Ø-regret min- imization. The importance of 0-rregret is that it leads to substantially more powerful notions of hindsight rationality, beyond the usual external regret (Gordon et al., 2008), including the powerful notion of swap regret (Blum& & Mansour, 2007). Moreover, one of the primary insights behind the re- sult of Farina al. (2021a) is cast convergence to an EFCE as a Ø-regret minimization problem. Given these prior connections, we believe that our stablc-predictive &b template is of independent interest, and could lead to further applications the future.
Theorem 1.1 extends and strengthens several prior papers in the literature, including the seminal work of Syrgkanis et al. (2015) that provides accelerated dynamies for coarse correlated equilib- rium in normal-fone -form games, as well as the more recent result of Chen & Peng (2020) which showed O 3/4) convergence to a correlated equilibrium in normal- games. For the more challeng- ing class of extensive-form games, accelerated rates were previously known only for finding Nash equilibrium in the special case of two-player zero-sum games, where an ((T43/4 rate was achieved via a stable-predictive CFR setup (Farina et al., 2019a) and an O(T-1) rate was achieved via opti- mistic regret minimizers coupled with good
functions (Farina al., 2019c).
From a technical standpoint, in order to apply our generic template for accelerated Ø-regret mini- mization, we establish two separate ingredients. First, we develop a stable-predictive external regret minimizer for the set of transformations & associated with EFCE. This differs from the construction by Farina al. (2021a) in that we have additionally guarantee and preserve the stability and sub- sequently the characterizing the stability of fixed points of trigger deviation functions. This turns out to be par- ticularly challenging, and direct extensions of prior techniques appear to only give bound that is exponential in the size of the game. In this context, one of our key technical contributions is to pro- vide refined perturbation analysis for Markov chain consisting of rank-one stochastic matrix, employing tools that have not been used before in this line of work, and substantially extending the techniques of Chen & Peng (2020). This leads rate of convergence that depends polynomially
-tttivvhtttttohhouuuu the construction. The second component consists of sharply
2

---

Under review as a conference paper at ICLR 2022
on the description of the game, which is crucial for the applicability of the accelerated dynamics. Finally, we support our theoretical findings with experiments on several general-sum benchmarks.
Further Related Work. The line of work on accelerated no-regret learning for Nash equilibrium was pioneered by Daskalakis al. (2015), showing that one can bypass the adversarial (((=1//2) barrier for the incurred average regret if both players in zero-sum game employ an uncoupled vari- ant of the excessive gap technique (Nesterov, 2005), leading to near-optimal rate of Olog T /T). Subsequently, Rakhlin& & Sridharan (2013a) showed that the optimal rate of (1/TT) can be obtained with a remarkably simple variant of Online Mirror Descent which incorporates a prediction term in the update step. While these results only hold for zero-sum games, Syrgkanis et al. (2015) showed that O(T-3/4) rate can be obtained for multiplayer general-sum normal-form games. In recent result, Chen & Peng (2020) strengthened the regret bounds of Syrgkanis et al. (2015) from external to swap regret using the celebrated construction of Blum & Mansour (2007). We also acknowledge a recent result of Daskalakis et al. (2021) which establishes a near-optimal rate of convergence of Ö(/T)) to a coarse correlated equilibrium when all players employ the Optimistic Multiplicative Weights Update (OMWU) algorithm in normal-form game. Extending their result to extensive- form games presents considerable technical challenges since their analysis crucially hinges on the closed-form softmax-type structure of OMWU on the simplex.
Correlated equilibrium in extensive-form games is much less understood than Nash equilibrium.A feasible EFCE can also be computed efficiently through variant of the Ellipsoid algorithm (Pa- padimitriou & Roughgarden, 2008; Jiang & Leyton-Bronn, 2015), and an alternative sampling- based approach was given by Dudík & Gordon (2009). However, those approaches perform poorly in large-scale problems, and do not allow the players to arrive at EFCE via distributed learning. Celli et al. (2019) devised variants of the CFR algorithm that provably convergence to normal-form coarse correlated equilibria, a solution concept much less appealing than EFCE in extensive-form games Gordon et al. (2008). Finally, Morrill et al. 2001a;b) characterize hindsight rationality no- tions and associate a set of solution concepts with suitable (T-11/2 no-regret learning dynamics.
2 PRELIMINARIES
Extensive-form Games. An extensive-form game is abstracted on a directed and rooted game tree T. The set of nodes of T is denoted with Hi non-terminal nodes are referred as decision nodes, and are associated with player who acts by selecting where h E H represents the decision node. By convention, the set of players [n] U {c} includes a fictitious agent who "selects" actions according to fixed probability distributions dictated by the nature of the game (e.g., the roll of a dice); this intends to model external stochastic phenomena occurring during the game. For a player E [n] U {c), we let 7(6 C 7 be the subset of decision nodes wherein a player i makes decision. The set of leaves 2 S H. or equivalently the terminal nodes, correspond to different outcomes; once the game transitions to a terminal node = E 2, payoffs are assigned to each player based on a set of normalized utility functions {u(") Z + [-1, 1e) It will also be convenient to represent with (2) the product of probabilities of "chance" moves encountered in the path from the root until the terminal node = E Z.
action from set of possible actions A(h),
Imperfect Information. To model imperfect information, the set of decision nodes H()) of player i are partitioned into collection of sets J(0, which called information sets. Each information set j E f groups nodes which cannot be distinguished by i. Thus, for any nodes h, h E j we have A(h)- = A(h'). As usual, we assume that the game satisfies perfect recall: players never forget information once acquired. We will also define a partial order < on J(t, so that j < j', for j.3' E J(A, if there exist nodes h E j and h' e such that the path from the root to h' passes through h. j j , we will say that is an ancestor of j', or equivalently, j is descendant of jr.
Sequence-form Strategies. a E A(j), we will denote with a (j, a) the sequence of i's actions encountered on the path from the root of the game until (and included) action a. For notational convenience, we will use the special symbol Ø to denote the empty sequence. Then, i's set of sequences is defined as ((6) = {(, a) j E J(0, A(i)) U (Ø]; we will also use the notation X(() = Σ() (Ø). For given information set j E J() we will use (j) E to represent the parent sequence; i.e. the last sequence
For a player i E [n], an information set j E J(),, and an action
3

---

Under review conference paper at ICLR 2022
encountered by player i before reaching any node in the information set j. assuming that exists. Otherwise, let g(0) (j) 2, and we say that is the root information set of player i. A strategy for a player specifies probability distribution for every possible information set encountered in the game tree. For perfect-recall EFGs, strategies can be equivalently represented sequence-form: Definition 2.1 (Sequence-form Polytope). The sequence-form strategy polytope for player i [n]] defined as the following (convex) polytope:
q
1 R
20 = =1,
0)00 E a)(i,))], REA()
Vj JGm
(I)
Analogously, one can define the sequence-form strategy polytope for the subiree of the partially ordered set (J(6, <) rooted at j J((,, which will be denoted as Q Moreover, the set of deterministic sequence-fomn form strategies for player [r|] the set II Q n {0, x0), and similarly for 115") The joint set of deterministic sequence-form strategies of the players will be represented with = Xie(n) IT(). As such, an element π is an n-tuple (T(").... ..... (")) specifying deterministic requence-form strategy for every player E [n]. Finally, the utility of player i [n]] under a profile E II can be expressed as
Σ (2)0 (2)1( (x) Ak [n]}.
We summarized in Table 1 the EFG notation that we will be using most often throughout the paper.
An Illustrative Example. To clarify some of the concepts we have introduced, we illustrate a simple two-player EFG in Figure 1. Black nodes belong to player 1, white round nodes to player 2, square nodes are terminal nodes (aka leaves), and the crossed node is a chance node. Player 2 has two information sets, T(2) = {C, D), each containing two nodes. This captures the lack of knowledge regarding the action played by player 1. In contrast, the outcome of the chance move is observed by both players. At the information set C, player has two possible actions, A(C) = {5, 6}. Thus, one possible sequence for player 2 is the pair o (C, 5) (2))
Description
Information sets of player i
B
A(j)
Actions information set
(
Set of sequences of player Sequence strategies rooted at E J()
Maximum depth of any j E g()
Figure 1: Example of two-player EFG.
Table 1: Summary of the basic notation.
Regret, &-Regret and Optimistic Regret Minimization. Consider convex and compact set X C R representing the space of strategies of some agent. In the online decision making framework, regret minimizer R can be thought of as black-box device which interacts with the external environment via the following two basic subroutines:
R. NENETSSTRATECY The regret minimizer returns the strategy of E X' time 4;
R. OBBSEREEUULLIT((() The regret minimizer receives as feedback linear utility function e 32:33 + (l', æ), and may alter its internal state accordingly.
The decision making is online in the sense that the regret minimizer can adapt to previously received information, but no information about future utilities is available. The error of regret minimizer is typically measured in terms of external regret, defined, for a time horizon T,, as follows:
T
T
Rf = max xx"
e-)
Σ
(3)
EX
t=1
t=1
4

---

Under review conference paper at ICLR 2022
That is, the performance of the online algorithm is compared with the best fixed strategy in hindsight.
P-Regret. A conceptual generalization of the concept of external regret is the so-called P-regret. Specifically, in this framework the performance the learning algorithm is measured based on set of transformations ④ X + X, leading to the notion of cumulative Φ r-regret:
R
max
Σ (o') E4
(a' E")
(4)
When the set of transformations & coincides with the set of constant functions, one recovers the notion of external regret given in Equation (3). However, Ø-regret is substantially more expressive and yields more appealing notion of hindsight rationality (Gordon et al., 2008), incorporating the notion of swap regret (Blum & Mansour, 2007).
We will employ the following definition, which a slight modification of the RVU property intro- duced by (Syrgkanis et al., 2015, Definition 3).
Definition 2.2 (Stable-predictiiitt).. Let R. be regert minimizer and let || 1|-
|| be a norm. R. is said to be k-stable with respect to || if for all 2, the strategies output by R satisfy
| x² I1
Ki
(5)
Moreover, it is said to be (a, p)-predictivee with respect to || for all 2 1 its regret R² satisfies
T re lx 11
Rd S a() +
(6)
1=
no matter the sequence of utility vectors el
LT
where
|| is the dual norm of ||
Optimistic Follow the Regularized Leader. some norm || |], and 1 > 0 the learning rate. OFTRL's update rule takes the following form:
Let d be I-strongly convex function with respect to
{(
d(x) "
x² == arg max MEN
xx,20* 28
(OFTRL)
where x = arg mi d(x). Syrgkanis et al. (2015) established the following property:
Lemma 2.3. (OFTRI) is stabbe and (Sa/1, (iinn,))ppu -reeddccee with respect to any norm || for which is I-strongly convex, where Qa the range of X, that is, Pa max x ex(((()) d(x')}
In this paper, we consider the entropic regularizer with respect to the simplex d(x)) = E æ; log wi which is 1-strongly convex with respect to the & norm. The pair of dual norms in the predictivity bound will therefore be (Il ||1, Iloo). We call this OFTRL setup Optimistic Multiplicative Weights Updates (OMWU).
Extensive-Fore Correlated Equilibrium. We will work with the definition of EFCE due to Farina et al. (2019e), which is equivalent that of von Stengel & Forges (2008). First, let us introduce the concept of trigger deviation function.
Definition 2.4. Consider some player E [n), a sequence = (i,a) E!") and joint sequence- form strategies π E I A trigger deviation function with respect to a trigger sequence â and continuation strategy स is any linear function f | R
| with the following properties.
Any strategy क E (T()) which does not prescribe the sequence remains invariant. That is, f(T) = न for any π E (t) such that π [0] = 0;
Otherwise, the preseribed sequence ô (j, a) is modified so that the behavior at j. well as all its descendants is replaced by the behavior specified by the continuation strategy:
π
i o j; i 2 j.
f(T)[a]
=
न [
(7)
for all
000 and π E (I() such that π T[ő] =
5

---

Under review conference paper at ICLR 2022
We will let v/() - 0 := ().) E. f ] be the of all possible linear mappings defining trigger deviation functions for player i. We are ready to introduce the concept of EFCE. Definition 2.5 (EFCE). For 2 0, probability distribution fa A is an 6-approximate EFCE for every player i [n] and every trigger deviation function Pa- E Tp((), it holds that
E Ex (2(*)
), )
( e;
(8)
where π (TTI.... n.) E probability distribution μ E A III is an EFCE is O-EFCE.
Theorem 2.6 (Farina et al. (2021a)). For every player i E [n]] let π ())11 ,...., (0)T E I1 be
....,.(().77
a sequence of deterministic sequence-form strategies whose cumulative -egrer R with respect to the sequence of linear utility functions
(+.t :I 3 π + (1) (()) 1 (-))))
(9)
Then, the empirical frequency of play E
! is e-EFCE, where : + maxie() R..TT.
3 ACCELERATING &EREGEET MINIMIZATION VIA OPTIMISM
In this section we develop a general template for accelerated (b-regret minimization for general sets, and then we instantiate the template for dynamics for EFCE. Our approach combines framework of Gordon et al. (2008) with the framework of stablc-predictive (aka. optimistic) regret minimization. As in Gordon al. (2008), in our template we combine transformation o² E & at every time t, and 2) fixed-point oracle for each d' E t. However, in our framework, we further require that 2) is stable (in the sense of Definition 2.2). To achieve this, we will focus regret minimizers that have the following property:
regret minimizer that outputs linear
Definition 3.1. Consider a set functions O such that ((x² S X for all Φ E d, and a no-regret algorithm R& for the of transformations & which returns sequence oe E Φ. We say that R4 is fixed point G-stable, for G 2 0, if the following conditions hold:
Every ø² admits fixed point. That is, there exists æ! X such that (x(()) x²
For any x' such that x² ('(x', there exists x²+1 with o ++1 = 8 (x such that || x'1l S G.
We will show how to construct accelerated --regret minimizer starting from the following:
1. RØ: k-stable (a. 3) preediccee fixed point G-stable regret minimizer for c;;
2. STABLEFPORACLE T, G, ): A stable fixed point oracle which returns point æ E X such that (i) |Ø(xx) æll S e, and (ii) ||æ- S G (the existence such a fixed point guaranteed by the fixed point G- G-stability assumption for the regret minimizer).
Given these two components, our next theorem builds a sueble-peddictiee P-regret minimizer.
Theorem 3.2 (Accelerated &eRegret Minimization), Consider k-stable (a,, preed-iieeictvvee regret minimizer R& for a set of linear transformations 4, with respect to the l norm || -11-- More- over, assume that R2 is fixed point G-stable with respect to 4. Then, if we have access to STABLEFPORACLE, we can construct a G-stable algorithm with 2-regret RD bounded as
T e'
T
R. S (a(T)++2DD)) 23D3 2T 23
Σ C' 1=2
+ +D
Σ a
(10)
where et is the error of STABLEFPORACLE at time t, and De is an upper bound the foo norm of Cs's. It is also assumed that ||0|||0 S for all a E X.
The proof is similar to that of Gordon et al. (2008). and included in Appendix
3.1 CONSTRUCTING A STABLE-PREDICTIO REGRET MINIMIZER FOR (v())
Here we develop regret minimizer for the set co (+), the convex hull of the of trigger deviation functions. Given that ())) 2 4((), this will immediately imply regret minimizer for the set

---

Under review conference paper at ICLR 2022
w/ -egrett Minimizer for (
R (Theorem 3.4)
(
(Proposition 3.3)
(
CFR
(OMWU)
L
R (6)
Fixed point
6),
R
(Proposition 3.3)
CFR (OMWU)
(4) 9
Pn
(
Figure 2: An overview of the overall construction. For notational convenience we have let y {1, 2,......,, m... The symbol & the figure denotes a multilinear transformation of the inputs. We also note that blue corresponds to the iterates, while red corresponds to the utilities.
(n()) An overview of the algorithm is given Figure Farina et al. (2021a) observed that the set co (t) can be evaluated in two stages. First, for fixed sequence ô = (j.a) x(" we define
the set ( à = co Φ + á E ( ): then, we take the convex hull of all (
à that is, co Tv(() =
cot (1) : E 1) }. Correspondingly, we first develop a stable-predictive regret minimizer for the set v (3) for any ā x(() and these individual regret minimizers then combined using regret circuit to conclude the construction in Theorem 3.4. All the omitted poofs and pseudocode for this section are included in Appendix B.1.
Stable-Predictive Regret Minimizer for the set (1)) Consider a sequence â E )!" Farina et al. (2021a) observed that the set transformations ( = co f : E 11))] is the image of under the affine mapping h() q Pa Hence, is well-known that a regret minimizer for can be constructed starting from regret minimizer for 0 We now show that the same can be said if one restricts to
regret minimizers. In particular, we have the following.
Proposition 3.3. Consider player [n] and any trigger sequence â (i,a) x!) There exists an algorithum which constructs deterministic regret minimizer R with access to a K-stable (Ar, B) B)-predictive deterministic regret minimizer R. for the set 2,0) such that R,O is K-stable and (Ar, B3 prrediciieee
In Appendix A we describe a sabbeepreedictiv variant of CFR for the set 0 for each J(,, following the construction of Farina et al. (2019a).
Stable-Predictive Regret Minimizer for co (()), The next step consists of combining the regret minimizers ( for all & E 2)()) to composite regret minimizer for the set (i)), To this end, we employ regret circuits (Farina et al., 2019d), leading to the main result of this section:
Theorem 3.4. Consider a k-stable (a, 9) -peediciee regret minimizer R for the the simplex A 1 and K-stable (A, B)-prdiictivve regret minimizers R for each â E y!!) all with re- spect to the pair of norms (ll |11, lloc). Then, there exists an algorithm which constructs a regret minimizer R( for the set co (i) such that (i) R(y O(K ||()) [1)--staaa -tt-sstale, and (ii) under any sequence of linear utility functions L "...,," LT the regret incurred can be bounded as
RTT (((a(T) + A(T) 3D + 12
L
L 1 100
(11)
1=
where |L Dr.

---

Under review as a conference paper at ICLR 2022
3.2 STABILITY OF THE FIXED POINTS
In this subsection we complete the construction of the -rrrret minimizer by establishing stable fixed point oracle for any é E co v)(0), All of the proofs of this section are included in Appendix B.2. Multiplicative Stability.
sequence (z'), with x' 2 is said to be k-mulliplicattvv-stahhe if (1 ([-x)) k)=; S # S (1 (1+ for any i E [d]. and for all 2 2. Importantl, this notion of multiplicative stability is guaranteed by OMWU (see Lemma B.2). Thus, if ( is the depth of i's actions and D an upper bound on the & norm in the treeplex, we can show the following:
Lemma 3.5. When each regret minimizer R is constructed using predictive CFR instantiated with OMWU with learning rate n (Theorem A.4) such that for all â E.! the output sequence is ( muliippiccatieelysstabaa Moreover, if the regret minimizer R is realized using OMWU with learning rate n, it will output an O(n)
(DJj)mmulppiicatvvly-ssllll sequence.
This characterization will be crucial for establishing the stability of the fixed points. In particular, following the approach of Farina et al. (2021a), let us introduce the following definitions:
Definition 3.6. Consider a player i E [n] and let J C ((t) be a subset of i's information sets. We say than J is trunk of ( if, for every E J, all predecessors of j are also in J.
Definition 3.7. Consider player E [m]. a trunk J S J and & E co V7(0) A vector E R | is J-partial fixed point of Φ if the following conditions hold:
20
x = 1 and x xzo0(1) [1)] = EncAt) x((] a)), for all j E J;
<0x)) [0] 22 [0] 1, and ((x))
a)), for all j J, and E A(j).
An important property is that a J-partial fixed point can be efficiently "promoted" to a J U {-*}- partial fixed point by computing the stationary distribution of a certain Markov chain. However, significant concern is whether this fixed point operation can potentially cause a substantial degrada- tion in terms of stability. One of our key results is that the associated Markov chain has particular structure, which enables us to substantially improve the stability bound and thereby obtain a poly- nomial degradation in stability. More precisely, this boils down to the following technical lemma.
Lemma 3.8. Let M and M' be transition matrices of m-state Markov chains such that M v1 C and M' v'1 +C', where C,C', u, v' have strictly positive entries. Moreover, let π and n' be the (unique) stationary distributions of M and M' respectively. Then, if (i) the entries of the matrices and C' are s-mulliplicatiivey-cloo --uutiplicatiivll-llss and (iii) the sum of the entries of and v' are x-multiplicatiiely-coos then æ and n' are (r + ((mm))-multiplicuut)
(ii) the entries of the vectors and v' are
for a sufficiently small k O(1/m)
Using a slightly more general result (Corollary B.10), we manage to obtain the following:
Proposition 3.9. Consider a player E [nl), and let EeErto \o be transformation for all à E x!! If x
in co (1() such that the sequence of X and d' 's is -mmultpplicttivll--ttaie is m-multiplicativelyy stable J J-partial fixed point sequence, there is algorithm which computes a (JU ( -partial fixed point (x'y of & such that the sequence of (x') 's is (7 O(k)A(j*)))) mudtiplicatively-stbbiei stable, for any sufficiently small O(1/lA(j*)))
Thus, using our technical lemma, we manage to bypass the substantial overhead of the term r[A(i*)], which would follow using techniques similar to Chen & Peng (2020). This turns out to be crucial for obtaining polynomial dependence on the size of the game. Finally, we can inductively employ this proposition to show the overall stability of the fixed points:
Theorem 3.10. Consider a player E [n), and let Φ o= E> No100 be a transformation in for all & = x+)) Then,
co ( such that the sequence of X 's and d 's is x-mulippiccativelysttab there exists an algorithm which computes a fixed point qº E Q(i) of such that the sequence of q A() ((()) ( muultipliiatively-sabbbi where [ = max AA(j), and for a sufficiently
small K= ((L((LA)))())
Finally, if we the stability values derived in Lemma 3.5, we arrive at the following conclusion:
8

---

Under review as a conference paper at ICLR 2022
Corollary 3.11. Kor = (2 |1 ( be [in]]]muliplliaailly--sst for any sufficiently small v = O(1kk).
De), De), the sequence of fixed points will
Putting Everything Together: Finally, having established these ingredients, we can use the template of Theorem 3.2 to obtain Theorem 1.1, as we formally show in Appendix B.3.
EXPERIMENTS
In this section we experimentally investigate the performance of our stable-predictive algorithm compared to two other popular approaches based on a CFR-style decomposition of regrets into lo- cal regret-minimizztion problems: the existing algorithm by Farina et al. (2021a) instantiated with (i) regret matching* + (RM*) (Tammelin, 2014) for each simplex (in place of regret matching), and (ii) using the vanilla MWU algorithm for each simplex. In accordance to the theoretical predic- tions, the stepsize for OMWU is set as 7 = T 1-1/1 (ef. Corollary 13), and for MWU it is set as 77 = 7 1-1/2 where the parameter is chosen by picking the best-performing value among {0.01, 0, 10, 100). In particular, we evaluate their performance based on the following popular benchmark games: (i) a three-player variant of Kuhn poker (Kuhn, 1950); (ii) two-player bargain- ing game known as Sheriff (Farina et al., 2019e) benchmark game introduced specifically for the study of correlated equilibria; and (iii) a three-playee version of Liar's 's dice (Lisý et al., 2015). A detailed description of each of the three game instances is available in Appendix D.
Kuhn poker
Sheriff
Liar's dice
OMWU (r - 10)
OMWU (r - 1)
CMWU (+ - 100)
cw
MWU
MWU 100)
BPCE gap
RM*
10-1
10-1
RM*
10-3
10-2
10-2
5000
10000
5000
10000
500
1000
Iteration
Iteration
Iteration
Figure The performance of MWU, OMWU, and RM+ + on three general-sum EFGs.
Figure shows the performance of each of the three learning dynamics for computing EFCE. On the r-axis we plot the number of iterations performed by each algorithm, and on the y-axis we plot the EFCE gap, defined as the maximum advantage that any player can gain by defecting optimally from the mediator's 's recommendations. It should be noted that one iteration costs the same for every algorithm, up to constant factors. We see that on every game, OMWU performs better than or on par with RM+ and MWU. On Sheriff, OMWU performs significantly better than both RM+ and MWU, by about an order of magnitude. One caveat to these results that we did not use two tricks that help CFR* + in two-player zero-sum EFG solving: alternation and linear averaging. These tricks are known to retain convergence guarantees in that context (Tammelin et al., 2015; Farina et al., 2019b; Burch et al., 2019), but it is unclear if they still guarantee convergence in the EFCE setting.
5 CONCLUSIONS
We described uncoupled no-regret learning dynamics so that if all agents play T repetitions of the game according to the dynamics, the correlated distribution of play an ( EFCE. This substantially improves over the prior best rate of (T22//)). One of our conceptual contributions is to connect the line of work optimistic regret minimization with the framework of r-regret. One of our main technical contributions is to characterize the stability of the fixed points associated with trigger deviation functions through refined perturbation analysis of certain structured Markov chain, which may be of independent interest. Finally, experiments conducted on standard benchmarks corroborated our theoretical findings.

---

Under review conference paper at ICLR 2022
REFERENCES
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
Kimmo Berg and Tuomas Sandholm. Exclusion method for finding nash equilibrium in multiplayer games. AAAI Conference on Artificial Intelligence (AAAI), 2017.
Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach. Learn. Res., 8:1307- 1324, 2007.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Hcads-up limit hold' em poker is solved. Science, 347(6218), January 2015.
Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaao1733, Dec. 2017.
Neil Burch, Matej Moraveik, and Martin Schmid. Revisiting CFR+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443 2019.
Andrea Celli, Alberto Marchesi, Tommaso Bianchi, and Nicola Gatti. Learning to correlate in multi-player general-sum sequential games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for sreesive-form correlated equilibrium. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Mlaria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, 2020.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Cha Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pp. 6-1, 2012.
Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing a Nash equilibrium. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2006.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Games and Economic Behavior, 92:327-348, 2015.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. CoRR, abs/2108.06922 2021.
Miroslav Dudík and Geoffrey Gordon. A sampling-bait based approach computing equilibria in suc- cinct extensive-form games. In Jeff A. Bilmes and Andrew Y. Ng (eds.), UAI 2009, P Proceedings of the Twenty-Fifth Conference on Uncertainty Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009, pp. 151-160. AUAI Press, 2009.
Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points (extended abstract). In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pp. 113-123, 2007.
Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International Conference on Machine Learning (ICML), 2019a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In AAAI Conference on Artificial Intelligence, 201 9b.
10

---

Under review conference paper at ICLR 2022
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated lerancc--eneratinn functions. In Advances in Neural Infor- mation Processing Systems, NeurIPS 2019, pp. 5222-5232, 2019c.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret circuits: Composability of regret minimizers. In International Conference on Machine Learning, pp. 1863-1872, 2019d.
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive-form games: Saddle-point formulation and benchmarks. In Conference on Neural Information Pro- cessing Systems (NeurIPS), 2019e.
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium, 2021a.
Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Efficient decentralized learning dynamics for extensive-form coarse correlated equilibrium: No expensive computation of stationary distri- butions required. ArXiv preprint, 2021b.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential deci- sion spaces: Fast convergence rates for Nash, correlated, and team equilibria. In ACM Conference Economics and Compulation, 2021c.
Andrew Gilpin and Tuomas Sandholm. Lossless abstraction of imperfect information games. Jour- nal of the ACM, 54(5), 2007.
Geoffrey Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference Machine learning, pp. 360-3670 ACM, 2008.
Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game- theoretic equilibria. Conference on Learning Theory (COLT), Washington, D.C., 2003.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 18:111271, 2000.
Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for com- puting Nash equilibria of sequential games. Mathematics of Operations Research, 35(2). 2010.
Albert Xin Jiang and Kevin Leyton-Brown. Polynomial-time computation of exact correlated equi- librium in compact games. Games Econ. Behav, 91:347-359, 2015.
Christian Kroer, Kevin Waugh, Fatma Kilmng-Kazznn and Tuomas Sandholm. Faster algorithms for extensive-fore game solving via improved smoothing functions. Mathematical Programming, 2020.
Alex Kruckman, Amy Greenwald, and John R. Wicks. An elementary proof of the Markov chain tree theorem. Technical Report 10-04, Brown University, 2010.
H. W. Kuhn. A simplified two two-person poker. In H. W. Kuhn and A. W. Tucker (eds.). Contributions to the Theory of Games, volume of Annals of Mathematics Studies, 24, pp. 97-103. Princeton University Press, Princeton, New Jersey, 1950.
Viliam Lisy, Mare Lanctot, and Michael Bowling. Online Monte Carlo counterfactual regret min- imization for search in imperfect information games. Autonomous Agents and Multi-Agent Systems, pp. 27-36, 2015.
Dustin Morrill, Ryan D'Orazio, Marc Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality extensive- form games. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICML 2021, volume 139 of Proceedings of Machine Learning Research, pp. 7818-7828. PMLR, 2021a.
11

---

Under review conference paper at ICLR 2022
Dustin Morrill, Ryan D' D'Orazio, Reca Sarfati, Mare Lanctot, James R. Wright, Amy R. Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, pp. 5584-5594. AAAI Press, 2021b.
Yurii Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal of Optimization, 16(1), 2005.
Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. J. ACM, 55(3):1::1114:29 2008.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Confer- ence on Learning Theory, pp. 993-1019, 2013a.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013b.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of reg- ularized learning in games. Advances Neural Information Processing Systems, pp. 2989- 2997, 2015.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint, 2014.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold' em. In Proceedings of the 24th International Joint Conference on Artificial Intelli- gence (IJCAI), 2015.
Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 1002-1000- 2008.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2007.
12


Reviews:
[{"review_id": "vJlhBTz9Jou", "reviewer": "Reviewer_zmM5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Computing game-theoretic solution concepts that capture the idea that the players may coordinate their strategies based on external signals has become an increasingly active field in recent years, whether in the form of correlated equilibrium, team correlated equilibrium, or other related concepts. Correlation has several attractive properties, with efficient computability among the most prominent ones and enough applications to justify further research in this direction. Designing uncoupled dynamics to approximate an extensive-form correlated equilibrium faster is hence definitely a problem worth studying. The authors' result is interesting, and I am convinced that the presented experimental results provide enough evidence to support their claims. I went through some of the proofs included in the appendix, and I could not find any obvious mistakes. The authors cite the relevant literature, and I also appreciate that they mention that alternation and linear averaging were left out from the experiments because of their lack of guarantees, which I find to be a valid argument. I have a few concerns as well, though.\n\nPerhaps the main one relates to the presentation of this work. Explaining the problem and techniques the authors study requires a lot of background. Already in the introduction, the authors mention different kinds of regrets and other fundamental notions without describing the main ideas behind these concepts or how they relate in general. This may make some readers confused. Several times I also found myself wondering how different claims relate together, e.g., why are \"certain Markov chains\" important, how are they used in the proofs, and what their stationary distributions relate to. This makes it difficult to follow the authors' thought processes, and the reader is forced to rely on the explanations in the appendix, which contradicts the idea of the main text being self-contained.\n\nThe work is also highly technical, which is an inherent problem of the framework of sequential decision-making. The problem is further aggravated by the plethora of notation, including upper and lower indexing. I believe a table of symbols similar to Table 1 in Farina et al. 2021a would be convenient. Moreover, the work is absolutely void of examples, despite containing many definitions and advanced concepts. The authors may consider providing some to help the readers familiarize themselves with the introduced notions.\n\nThe main result the authors present is indeed interesting. Still, after reading through the appendix, my impression is that many of the constructions and proofs (with the important exception of Lemma B.7) are directly inspired by previous works, especially the papers by Farina et al. May the authors elaborate what were the main difficulties they encountered when extending the results into the framework of optimistic regret minimizers?\n\nFarina et al. also define approximation of extensive-form correlated equilibrium using regret minimizers on the set of deterministic sequence-form strategies (Theorem 3.7 in Farina et al. 2021a), and moving to the set's convex hull (i.e., mixed strategies) will result in a guarantee with high probability only. According to Section 3.1, the sequence-specific regret minimizers are constructed from the regret minimizers for the mixed strategies (Q^i_j). Should not the approximation mentioned, e.g., already in the abstract, be hence also probabilistic?\n\nI understand that using the technique of Chen and Peng would result in a non-polynomial degradation in stability. May I ask how this would affect the overall rate of convergence to extensive-form correlated equilibrium and computational complexity of the algorithm computing fixed points? More specifically, would the convergence rate contain game-specific exponential constants and otherwise be similar, or would it change completely?\n\nLastly, I wonder how fast one iteration of the OMWU-based dynamic is, compared to the alternatives (regret-matching+ and vanilla MWU)?\n\nNits:\nThe proof of proposition 3.3 is missing a reference (it reads \"??\").\nEquation 45 is missing a comma.\nAt the beginning of Section 3, should not (2) be 2) instead?\nThe word \"coarse\" is missing in Corollary C.7.\n", "summary_of_the_paper": "This paper presents an uncoupled no-regret learning dynamic provably converging to the extensive-form correlated equilibrium in general-sum n-player extensive-form games. The central claim of the paper is that the introduced approach results in the convergence rate of O(T^{-3/4}) to the equilibrium and hence supersedes the recent algorithm of Farina et al. which converges with rate O(T^{-1/2}). To achieve this, the authors follow the construction presented by Farina et al., but employ stable and predictive regret-minimizers from the class of Optimistic Follow the Regularized Leader algorithms instead of CFR/regret-matching used by Farina et al. The main portion of the paper is then dedicated to the theoretical analysis of the dynamic to arrive at the desired convergence rate. To this end, the authors first study how to construct stable-predictive regret minimizers for the convex hull of the set of trigger deviation functions for a given sequence, and consequently also for the composite regret minimizer. This enables them to bound the overall incurred regret. The construction also requires that every trigger deviation function admits a fixed point that is efficiently computable by a stable oracle. The stability is hence of the authors' interest in the second part. The paper is concluded by an experimental evaluation of the algorithm that shows that it is superior or performs on par with the algorithm of Farina et al. instantiated with regret matching or vanilla multiplicative weights updates.", "summary_of_the_review": "Overall, I am slightly in favor of accepting this work. The problem is worth studying, the main result the authors present is exciting, and the empirical results support their claims. My main concerns relate to the presentation of this work. The text is extremely technical and notation-heavy, and I believe many concepts should be more adequately explained for a reader less familiar with no-regret learning to understand this work. The manuscript also completely lacks any examples. I remain unsure if a better exposition is possible given the ICLR's strict page limit and if this work would not be better suited for journals or conferences that allow longer narratives.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "guvHr6CBYfC", "reviewer": "Reviewer_mWDx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "On the positive side the improved convergence rate is a clear theoretical contribution and the experiments suggest that a practical implementation of these techniques is possible.  On the negative side, as discussed in detail below, the techniques used to achieve it essentially boil down to combining the approach of Farina et al. 2021a with a line of work on slowly-changing regret minimizers which have been shown to achieve accelerated rates in a number of settings, so the acceleration here is not terribly surprising.  While such a combination may require substantial novel insights, the exposition does not currently make it clear what those are.\n\nMore broadly, the positioning of the contribution of this paper relative to related work needs to be clearer.  I will discuss several particular relationships which do not appear to be sufficiently clearly explained, and for some of them this appears to expose weaknesses in the paper.\n\nFarina et al. 2021b [F21b].  This paper achieves a O(T^{-0.5|) rate to a weaker solution concept (EFCCE).  However, relative to EFCE it avoids an expensive computation at each step.  This paper is used as a baseline in the experiments Section 4, and thus has two differences (slower rate and different solution concept).  The discussion omits the second difference and appears to discuss it as converging to an EFCE.  So I am left wondering which factor is responsible for the worse performance in the experiments.  Furthermore, Appendix C of the supplemental materials (which does not appear to be referenced in the main text) discusses how the result of this paper can be combined with those of [F21b] to get accelerated convergence to EFCCE.  Give this, I am not sure why the experiments do not isolate the two factors (rate vs solution concept) and which version of the algorithm in the paper the experiments are actually testing (i.e. do they actually use the EFCCE version?).\n\nThe line of work on distance-generating functions (Hoda et al. 2010, Kroer et al. 2020, Farina et al. 2021c).  These techniques have achieved O(T^{-1}) in other settings but are mentioned only briefly.  Why not adopt these techniques rather than the ones that lead to O(T^{-0.75})?  I don’t a-priori see why they should be incompatible with the framework from Section 3 and if they can be achieved it makes the headline result of O(T^{-0.75}) less impressive unless there are other reasons to prefer this approach.\n\nFarina et al. 2021a [F21a].  While this work is referenced throughout the paper, the technical approaches share so much overlap that I have some difficulty disentangling where exactly the technical contributions in this paper are.  In particular, I am not precisely clear what constitutes the “stable predictive \\Phi template” referred to as being of independent interest.  [F21a] appear to use the same framework based on Gordon et al. 2008 which incorporates an arbitrary regret minimizing dynamics.  So it would be helpful to call out which specific results require new insights to apply it to a stable-predictive version (which have been explored in several previous works, although perhaps mostly for normal-form games).  The one result specifically mentioned is Lemma 3.9, and I could not find a proof of it in the supplementary material (there does seem to be a proof of the reference Corollary B.9 but it builds on different results, although they appear at least somewhat similar in spirit).  As a result I have a hard time evaluating the significance of the technical contribution of this paper.  Finally, as a minor note I am a bit confused about the status of [F21a].  This paper describes it simply as “very-recent follow-up work” to Celli et al. 2020, while [F21a] describes itself as an extended version of that paper in a note on the first page.\n", "summary_of_the_paper": "Previous work has identified uncoupled, regret-based dynamics that converge to extensive-form correlated equilibria in extensive-form games at a rate of O(T^{-0.5}) where T is the number of repetitions of the game.  This paper provides a new uncoupled, regret-based dynamics that achieves O(T^{-0.75}).  It does so by combining analysis techniques for regret-based dynamics that have shown such accelerated convergence in other settings with the framework used to achieve the  O(T^{-0.5}) rate.  Technical contributions in realizing this combination include a new analysis of a relevant Markov chain.  A limited set of experiments confirms faster convergence relative to prior approaches.", "summary_of_the_review": "While I appreciate the headline theoretical contribution, given my concerns I am not convinced that this version of the paper makes a sufficient novel technical contribution.  One possibility is that it does but the technical exposition needs to be improved to more clearly highlight the contribution.  Another path forward, since this paper is heavily based on the approach of [F21a], improves its results, and that paper appears to be still unpublished, would be to consider whether the authors of {F21a] would be amenable to merging the papers.  A third possibility to extend the results and demonstrate the power and flexibility of the approach would be to show that it can also be adapted to work with the line of work which uses dynamics based on carefully-designed distance-generating functions to achieve an O(T^{-1}) bound.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LIgfCwc9d_K", "reviewer": "Reviewer_NoAR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Strengths\nThe problem that the authors considered is an important problem for no-regret learning dynamics in games. Compared to existing literature on accelerated learning dynamics for correlated equilibria (CE) or coarse correlated equilibria in normal-form games, the convergence rate for extensive-form game is relatively less understood. \n\nThis paper shows an improved convergence rate to extensive-form correlated equilibrium (EFCE): when the game is played for T repetitions, the correlated distribution of play for all players is an $O(T^{-3/4})$-approximated EFCE, which improves upon the previous best rate $O(T^{-1/2})$. To me this is a good and important theoretical contribution to the existing literature.\n\nA main conceptual contribution is to establish a connection between the optimistic regret minimization to $\\phi$-regret minimization problem. A main technical contribution is a characterization of the stability of certain fixed point strategies through a refined\nperturbation analysis of the structured Markov chain. Other than that the proof utilized previous results in Farina et al.\n(2021a), which casts the convergence to an EFCE as a $\\phi$-regret minimization problem, and existing framework on optimistic regret minimization.\n\nNumerical simulations are provided in support of the theoretical results.\n\n## Weakness\n\nFirst I think the summary of related works on no-regret learning dynamics for normal-form games are missing some most recent results. For example in [Daskalakis, Fishelson, Golowich, Near-Optimal No-Regret Learning in General Games, 2021] it is shown that one can achieve a O(1/T) convergence rate to coarse correlated equilibrium in multi-player general-sum games. Secondly I don't see much discussion on the technical difficulty of why the paper's framework could not be applied to normal-game. Given the many other existing rates for normal-games, it would be good to add more details on this point.\n\nRegarding the technical contributions, the main concern is about novelty given that the main framework is built on previous results in Farina et al. (2021a) which casts the convergence to an EFCE as a $\\phi$-regret minimization problem, and existing framework on optimistic regret minimization as in Gordon et al. (2008).\n\n\n", "summary_of_the_paper": "This paper proves a faster no-regret learning dynamics for extensive-form correlated equilibrium (EFCE) in multiplayer general-sum imperfect-information extensive-form games. When the game is played for T repetitions according to the accelerated dynamics, the correlated distribution of play for all players is an $O(T^{-3/4})$-approximated EFCE. This improves upon the previous best rate which is $O(T^{-1/2})$ for extensive-form games.", "summary_of_the_review": "Overall I think this paper provides nice theoretical contribution with an improved rate for no-regret learning dynamics that converge to extensive-form correlated equilibrium. The paper is well-written. However currently the related work is missing some recent relevant results, and on the technical contribution side there should be some more details differentiating the new results and existing frameworks.\n\nPost rebuttal update: I have read the authors' response and will keep the original score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DApjgf5KD0k", "reviewer": "Reviewer_4e5F", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is well written (see specific comments and the concern below). The proofs seem correct (I did not check the appendices in detail). Providing an accelerated convergence rate for multiplayer extensive form games (and in particular proving the counterpart of what is known for normal-form game) is a valuable contribution. My main concern is that in the current form the paper is difficult to read. In particular, the proposed algorithm should be at least described in the main text (see main comments). Furthermore, some parts should be better introduced, e.g. the \\Phi-regret minimization framework (see specific comments).\n\nMain comments: \n\n-It is hard to find what is the final algorithm mentioned in Theorem 1.1 by reading the main text and even by looking at Appendix B. Thus without the big picture Section 3 looks a bit like a collection of unrelated technical results.\n\n-Could you state clearly the complexity of the proposed algorithm (it seems that it scales at least quadratically with the size of the game?) and polynomial dependence on the size of the game hidden in Theorem 1.1. This is important since usually the size of the game is very large.\n \nSpecific comments:\n-P1 Th 1.1: Is there any lower bound on the rate? For example, is there hope to improve the rate to O(1/T) as for two players? You should also clearly refer to the description of the algorithm in the paper.\n\n-P3 End of section 1: Why normal-form coarse correlated equilibria is solution concept much less appealing than EFCE?\n\n-P4, below (1): typo \\cJ^{(i)}\n\n-P5, Theorem 2.5: \\psi^(i)-regret is not defined at this point.\n\n-P6, Definition 3.1: does the point x_t necessarily coincide with the point played by the regret minimizer algorithm? Ok maybe you should describe the framework of Gordon et al. (x_t is the fixed point of a \\phi_t obtained by another regret minimizer on an auxiliary task?).\n\n-P6, Theorem 3.2: Maybe you should define clearly what you mean by a regret minimizer R_\\Phi\nfor the set of transformation \\Phi.  \n\n-P6, end of Section 2: could you detail what you mean by entropic regularizer on \\cX?\n\n-P9, end of Section 3: Could point out precisely where is the final algorithm in Appendix B. \n\n-P9, Section 4: At this point, it is not clear at all what the OMWU algorithm is. Did you also experiment on Leduc Poker? Because it is usually the setting where there is a gap between multiplicative weights type of algorithms and RM+ (ith alternating updates). \n\n-P13, top of the page: \\cJ is in the introduction the set of information set. Using the same notations for the sequential decision making setting is a bit confusing. Could you \n\n-P13, (13): is an observation node always followed by an action node?\n\n-P16, above (24): typo\n\n-P18, above (32): norm 1", "summary_of_the_paper": "The authors consider the problem of finding an approximate extensive-form correlated equilibrium (EFCE) of a finite general-sum multiplayer extensive-form game under the perfect recall assumption. They propose an accelerated version via optimism of the algorithm by Farina et al. (2019a). Precisely it combines the framework by Gordon et al. (2008) for \\Phi-regret minimization with the framework of optimistic regret minimization adapted to extensive form game. They prove that when all agents play T repetitions of the game according to the proposed algorithm the correlated distribution of play is an O(T ^−3/4 )-approximate EFCE where O hides quantities polynomial in the size of the game. The main technical point to obtain this result is to characterize the stability of certain fixed point strategies through a refined perturbation analysis of a structured Markov chain. They also provide preliminary experiments on simple two or three-players games.", "summary_of_the_review": "See Main Review", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper builds upon existing works to prove that learning (correlated) equilibrium can be fast, i.e., faster than \sqrt{n} even in extensive form games.

Three reviewers are rather lukewarm, and one reviewer is more positive (but seems less confident in his score). The two major criticisms is that this paper is very difficult to read and that the results might seem rather incremental with respect to the literature.

I tend to agree with both points but the paper still as merits: the reason is that extensive form games are intrinsically way harder than normal form games and they more or less all have a burden of notations. We agreed  that the authors actually did some efforts to make it fit within the page limit. but another a conference or a journal would have been better suited than ICLR.

Our final conclusion is that the result is interesting yet maybe not breathtaking for the ICLR community; we are fairly certain that another venue for this paper will be more appropriate and that it will be accepted in the near future (I can only suggest journals based on the large amount of content and notations, such as OR, MOR, or GEB - yet, conferences such as EC should be more scoped too) . It does not, unfortunately, reach the ICLR bar.
Decision: Reject