Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent
Authors: Yu Bai
Chi Jin
Song Mei
Ziang Song
Tiancheng Yu
Venue: NeurIPS 2022 Accept (2022)
Keywords: extensive-form games
regret minimization
correlated equilibria
multi-agent reinforcement learning
reinforcement learning theory

Abstract: A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them to Normal-Form Games (NFGs). This approach enables us to directly translate state-of-the-art techniques and analyses in NFGs to learning EFGs, but typically suffers from computational intractability due to the exponential blow-up of the game size introduced by the conversion. In this paper, we address this problem in natural and important setups for the \emph{$\Phi$-Hedge} algorithm---A generic algorithm capable of learning a large class of equilibria for NFGs. We show that $\Phi$-Hedge can be directly used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse Correlated Equilibria (NFCCE), and Extensive-Form Correlated Equilibria (EFCE) in EFGs. We prove that, in those settings, the \emph{$\Phi$-Hedge} algorithms are equivalent to standard Online Mirror Descent (OMD) algorithms for EFGs with suitable dilated regularizers, and run in polynomial time. This new connection further allows us to design and analyze a new class of OMD algorithms based on modifying its log-partition function. In particular, we design an improved algorithm with balancing techniques that achieves a sharp $\widetilde{\mathcal{O}}(\sqrt{XAT})$ EFCE-regret under bandit-feedback in an EFG with $X$ information sets, $A$ actions, and $T$ episodes. To our best knowledge, this is the first such rate and matches the information-theoretic lower bound.

Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent
Yu Bai
Chi Jin Princeton University chij@princetonn. edu
Salesforce Research
yu. bai www.aessorreeccom
Song Mei
Ziang Song Stanford University zi ziangs@atanf ord. edu
Tiancheng Yu MIT yutc edu
UC Berkeley Lungmei@berkeeey...
Abstract
A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them Normal-Form Games (NFGs). This approach enables us to directly translate state-of-the-ar techniques and analyses in NFGs to learning EFGs, but typically suffers from computational intractability due to the exponential blow-up of the game size introduced by the conversion. In this paper. ad- dress this problem natural and important setups for the 4-Hedge algorithm- AA generic algorithm capable of learning large class of equilibria for NFGs. We show that He-Hedge can be directly used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse Correlated Equilibria (NFCCE), and Extensive-Form Corre- lated Equilibria (EFCE) EFGs. We prove that, in those settings, the H-Hedge algorithms are equivalent standard Online Mirror Descent (OMD) algorithms for EFGs with suitable dilated regularizers, and run in polynomial time. This new connection further allows rithms based on modifying its ieg-paritionn function. In particular, we design an improved algorithm with balancing techniques that achieves sharp O(vX AT) EFCE-regret under bandit-feedback an EFG with X information sets, actions, and T' episodes. To our best knowledge, this is the first such rate and matches the information-theoretic lower bound.
design and analyze
class of OMD algo-
Introduction
Extensive form games (EFGs) is a natural formulation for multi-player games with imperfect informa- tion and sequential play. which models real-world games such as Poker [9, 10]. Bridge [45], Scotland Yard [41]. Diplomacy [7] and has many other important applications such as cy cybersecurity [32], auction [39], marketing [29]. In multi-player general-sum EFGs, computing
approximate Nash equilibrium (NE) [40] is PPAD-hard [15] and thus likely intractable. A reasonable and computa- tionally tractable solution concept in general-sum EFGs is the extensive-form correlated equilibria (EFCE) [46, 27, 13, 23].
known that, as long as each player runs an uncoupled dynamics minimizing suitable EFCE-regret, their average joint policy will converge an EFCE [28].
Existing algorithms of minimizing the EFCE-regret are mostly built upon the regret decomposition techniques [51], which utilize the structure of the game and the set of policy modifications [13, 38, 23, 42]. For example, Morrill et al. [38] decomposes the EFCE-regret to local regrets at each information set (infoset) with each of them handled by local regret minimizer; Farina al. [23] utilizes the trigger structure of the policy modification set to decompose the regret to external- regrets.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

There are at least two alternative approaches to designing regret minimization algorithms for EFGs. The first is to convert EFG to a normal-form game (NFG) and use NFG-based algorithms such as b-Hedge [28]. This approach typically admits simple algorithm designs and sharp regret bounds by directly translating existing results in NFGs [44]. However, the conversion introduces an exponential blow-up in the game size, and makes such algorithms computationally intractable in general. The computational efficiency of these NFG-based algorithms is recently investigated by Farina et al. [25] in the external regret minimization problem, who provided an efficient implementation of an NFG- based algorithm using "kernel tricks". The second is to use Online Mirror Descent (OMD) algorithms via suitably designed regularizers over the parameter space. This approach has been successfully implemented in minimizing the external regret [35] but not yet generalized to the EFCE-regret, as it remains unclear how to design suitable regularizers for the policy modification space.
In this paper, we develop the first line of EFCE-regret minimization algorithms along both lines of approaches above, and identify an equivalence between them. We consider EFCF-regret minimization in EFGs with X infosets, A actions, and maximum -o-morm of sequence-fore policies bounded by |Il (cf. Section 2.2 for the formal definition). Our contributions can be summarized follows:
We present an efficient implementation of the d-Hedge algorithm for minimizing the extensive- form trigger regret, by recursively evaluating the gradient of a log pag-ptttttion function (Section 3.1). The implementation further reveals that this algorithm (via reparametrization) equivalent to an OMD algorithm with dilated regularizers, which we term as EFCE-OMD (Section C.1).
We show that EFCE-OMD achieves trigger regret bound O(VII0)) T) under full feedback and Ö(vX [|] AT) under bandit feedback (Section 3.3). Notably, the proofs are done using the corresponding NFG analysis straightforwardly, and is independent of the actual implementation.
We design improved algorithm Balanced EFCE-OMD, and show that it achieves sharp (VXAAT) trigger regret under bandit feedback (Section 4). This improves over EFCE-OMD by a factor of [[[T]] and is the first to match the information--heorrtii lower bound. The algorithm works by modifying the above log-partition function using a variety of balancing techniques, and is equivalent to another OMD algorithm (but no longer an NFG algorithm).
As another example our framework, we show that the H-Hedge algorithm for vanilla (external) regret minimization in EFGs, along with its efficient implementation via "kereeiizatio" devel- oped recently in [25], is actually equivalent to standard OMD with dilated entropy (Section 5).
1.1 Related work
Ø-regret minimization and correlated equilibrium The Ø-regret minimization framework was introduced in Greenwald and Jafari [28] and Stoltz and Lugosi [44]. In particular, Greenwald and Jafari [28] showed that uncoupled no P-regret dynamics leads to P-correlated equilibria, generalized notion of correlated equilibria introduced by Aumann [5]. Stoltz and Lugosi [44] then developed a family of d-regret minimization algorithms using the fixed-poing method (including the 4- HeHeege algorithm considered in this paper), and derived explicit regret bounds. Two important special cases of Φ- rerretttt are the internal regret and swap regret in normal-fome games [43, 8]. A recent line of work developed algorithms with (pooyyogT)) swap regret bound in normal-form games [2, 3].
Regret minimization in EFG from full feedback A line of work considers external regret min- imization in EFGs from full feedback [51, 12, 11, 21, 50]. In particular, Zhou et al. [50] achieves ((XXT) external regret. The recent work of Farina et al. [25] develops the first algorithm to achieve T[ polylog?)) external regret in EFGs by converting it to an NFG and invoking the fast rate of Optimistic Hedge [16], along with an efficient implementation via the "kernel trick". Our d-regret framework covers their algorithm as a special case, and we further show that their algorithm (along with its efficient implementation) is equivalent to the standard OMD with dilated entropy.
The notion of Extensive-Food Form Correlated Equilibria (EFCE) in EFGs was introduced in Von Stengel and Forges [46]. Optimization-basee algorithms for computing computing EFCEs in multi-player EFGs from full feedback have been proposed in Huang and von Stengel [31], Farina et al. [20].
Gordon et al. [27] first proposed to use uncoupled EFCE-regret minimization dynamics to compute EFCE; however, they do not explain how to efficiently implement each iteration of the dynamics. Recent works [13, 23, 38, 42] developed uncoupled EFCE regret minimization learning dynamics

---

with efficient implementation; All of these algorithms are based on counterfactual regret decomposi- tion [51] and minimizing each trigger regret (first considered by Dudik and Gordon [17], Gordon et al. [27]) using a different regret minimizer. Celli et al. [13] decomposed the regret to each laminar subtree, but they did not give an explicit regret bound, Farina et al. [23] decomposed the regret to each trigger sequence and used CFR type algorithm to minimize the regret on each trigger sequence and achieved an Õ(VX²T) EFCE-regret bound. Morrill al. [38]. Song al. [42] decomposed the regret to each information set and use regret minimization algorithms with time-selection func- tions [8, 33] to minimize the regret on each information set, giving (VVX²T) and (V) regret bounds respectively, In this paper, we show that the simple o-Hedge algorithm, which has an efficient implementation and an intuitive interpretation, can also achieve the state-of-art O(v ( regret bound in the full feedback setting.
Regret minimization in EFG from bandit feedback Minimizing the external regret in EFGs from bandit feedback is considered in a more recent line of work [36, 22, 19, 24, 49, 47, 34, 6J. Dudik and Gordon [18] consider sample-based learning of EFCE in succinct extensive-form games; however, their algorithm relies on an approximate Markov- Chhin Monte- sampling subroutine that does not lead to a sample complexity guarantee.
concurrent work by Song al. [42] also achieves ((X/=²) sample complexity for learning EFCE under bandit feedback (when only highlighting X) using the Balanced K-EFR algorithm. Our work achieves the same linear in X sample complexity. but using a very different algorithm (Balanced EFCE-OMD) We also remark that the algorithm of [42] cannot minimize the EFCE-regret against adversarial opponents from bandit feedback like our algorithm, as their algorithm requires playing multiple episodes against fixed opponent, which is infeasible when the opponent is adversarial.
2
Preliminaries
2.1 Ø-regret minimization and &-Hedge algorithm
Consider a generic linear regret minimization problem on a policy set II C RS with respect to a policy modification set & c. Rdddd Here 11 is convex compact subset of Rd and & is convex compact subset of [xdd where each ø E & is a policy modification function which is a linear transformation from Rdd to Rdd that maps II to itself (IIII) C II). For any algorithm that plays policies T ( within T rounds and receives loss functions { (()) C. RR2 the P-regret is defined as
Reg (T) := supaee Σt= (4t opp,e")
(1)
The P-regret subsumes the vanilla regret (i.e. external regret) as a special case by taking & to be the set of all constant modifications Øext == {Φn. : p,+ E II] where Øy- = n² for all μ II. Another widely studied example is the swap regret [8] (and the closely related internal regrel [26]) for normal-form games, where II Aa is the probability simplex over d actions, and & is the set of all stochastic matrices (i.c. those mapping Ad to itself). A primary motivation for minimizing the d--regret is for computing various types of Correlated Equilibria (CEs) in multi-player games using the online-to-bated conversion (see e.g. [14]), which has been established in many games and has been a cornerstone in the online learning and games literature.
Φ- Hedee algorithm A widely used strategy for minimizing the 0-regret is to use any (black-box) linear regret minimization algorithm the 4 set produce sequence of { (57)7 C Φ,, combined with the fixed point technique (e.g. [43])=Output policy n that satisfies the fixed-point equation o'y²² pt in each round t. In the common scenario where & is the convex hull of finite number of vertices, i.c. & = (o))(20) where 2 is a finite subset of 4, a standard regret minimization algorithm over & is Hedge (a.k.a. Exponential Weights) [4], leading to the &-Hedge algorithm (Algorithm 1).
is a standard result ([44], see also Lemma 1) that Algorithm I achieves Ø-regret bound Reg" (T)
log (Dol
+ y ΣT= Eseo, Po ,0))
(2)
7
By choosing 7) > 0, this result implies a quite desirable bound Reg a (T) < L 2 log Pol T in the full-feedback setting (assuming bounded loss ( e²) S T.), and can also be used to prove regret bounds in the bandit-feedback setting.
3

---

Algorithm o-Hedge
Require: Finite vertex set ty C Raxd such that conv(#o) = 4; Learning rate 17.
1: Initialize p' E As, with P/ = / Tol for Φ E Pu-
2: for iteration t = , . do
3: Compute o² = = P
4: Set policy μ² to be the fixed point of equation u² = =d'x'.
5: Receive loss function &e E 20 suffer loss (p",e)
6: Update p/ &s P/g expl (op', ,
2.2 Extensive-form games (EFGs) and extensive-form trigger regret
In this paper, we consider m-player amperfect-information extensive-form games (EFGs) with perfect- recall (see Appendix B.1 for detailed definitions). For the purpose of this work, we consider an alternative formulation of EFGs Tree-Form Adversarial Markov Decision Processes (TFAMDP). This model is equivalent to studying EFGs from the perspective of single player, while treating all other players as adversaries who can change both transitions and rewards each round.
Tree-form adversarial MDP followings (H, {Kh, helmn, A, T, (vf (10 {Rt heem),.21) Here H E N_ is the horizon length: Nr is the space of information sets (henceforth infosets) at step h with size |& = X and Σ X = X; A is the action space with size |A| A. Next, T {C(x,, (x.0) defines the tree structure over the infosets and actions, where C(an, C Xx+ denotes the set of immediate children of (z), an). Furthermore, {C(2), (on.). (axn.a))))xx forms a partition of X It directly follows from the tree structure of TFAMDP that the player has perfect recall, i.e., for any infoset Ta E Xr, there is a unique history (I1, a1..... 24-1, ag a2-1) that leads to øn. Furthermore, pb(()) Ax, is the initial distribution over 2 episode t; pl. (-Ian,, a.) is the transition probability from (x%, a&) to its immediate children C( a4) at episode t; R,, (-
We consider an episodic, tabular TFAMDP which consists of the
pa, as) is the distribution the stochastic reward E [0, 1] received at (Ir, an) at episode t, with expectation (2,, on).
At the beginning of episode f, an adversary will first choose the initial distribution pó- transition {ph, (H)[H)) and reward distribution (R, ME(M] Then in the bandit feedback setting, at each step h, the player observes the current infoset 24, takes an action On. receives a bandit feedback of the reward r
( (-122; (n), and the environment transitions the next state Th+1 Pj (-122,, a.).
denote policy, where each ua (aaa) E AA is the action distribution infoset Th. We say μ deterministic policy if μr (+|æx) takes some single action with probability 1 for any (h, ). Let II denote the set of all possible policies. We denote the sequence form representation of policy μ E by
Policies We use μ ((u(-1=a)
Mish (Th an.) I Mhe (ak
(3)
where (11, 01,-. -h 01 01-1) is the unique history of z4- We also identify μ vector in XXA whose (Ih, ath-th entry is equal its sequence form f1.t (Zn, an). Let ||II|, max || which admits bound ||T]]], < X but can in addition be smaller (cf. Appendix B.3).
Expected loss function Given any policy μ² at round f, the total expected loss received at round t (which equals to H minus the total rewards within round is given by
(1, e*) := En an Min (xh, e, (2t, on);
where the loss function for the /-th round given by le = {c, (2n, on) hn)ma E BAX
f (Zh az) (z 11 h-1 (TN4 an (w) [1
Ry, (2h,
(4)
where (x1, (d........ Th ap- ah-1) is the unique history that leads to F4. In the full feedback setting, the learner is further capable of observing the full loss vector El R.XAA at the end of each round t.

---

Subtree and subtree policies For any S h, 2g E Zg. Th E An. and any action ag. an E A. we say Iy or (Ih, aA) is in the subtree rooted at zg. written as 24, ž Fg or (In, an) - 2g. if x. is either equal to or is part of the unique preceding history (æ1, (21,01.... #h-1, 0h-1) which leads to Jh- Similarly, we say Th or (Ih, ah) is in the subtree of (xy. 0g), written as 2h > (T ag) or (Kh, an) ł=2 (T (g) if (Igz 0g) is either equal to (IA, an) (only in the latter case), or is part of the unique preceding history (I1, a1.... Th-1, ah-1) which leads to Zh.
For any 9 E [ and any infoset 2g E Eg we use μ²= [1 AA:TA t 5n to denote subtree policy rooted Zg. We use II and V to denote the set of all subtree policies and the set of all deterministic subtree policies rooted at 2g. We denote the sequence form representation of 1== II by:
Ih 2W (anelzne
if (2h, a1)) Zg. otherwise.
M g:h (Thy an)
Similarly, we can also identify any subtree policy p² E II as a vector in IRA whose (Ih, an 3-th entry is equal to its sequence form Wight (Ih, an) (which is non-zero only the subtree rooted at xg).:
Extensive-form trigger regret The notion of trigger regret is introduced in [27, 13, 23]. An (extensive-form) trigger modification 0r,0,-m²²
a policy modification that modifies any policy 11 as follows: When Ig is visited and 0g is about to be taken (by μ1) we say ag is triggered, in which case the subtree policy rooted at xy is then replaced by m E I One can verify that the trigger modification P2gay-m" can be written
linear transformation that maps from II to II:
Ongaz-ma == =1 Eza,a, + m m
T Egga E2ga, XXXXXX
Here, Ezza,a, is diagonal matrix with diagonal entry 1 all (Ih, an) satisfying (In; an) - (Igr ag). and zero otherwise, and Crgag E RR X is an indicator vector whose only non-zero entry is at (Ig. ag)- We say ạx is a deterministic trigger modification if th E y is a deterministic subtree policy. We denote the set of all deterministic trigger modifications and its convex hull D and Tr respectively, where
T
U 9. ="
U
{
Tr conv (
(5)
The (extensive-form) trigger regret is then defined as the difference in the total loss when comparing against the best extensive-fom form trigger modification in hindsight. We note that the trigger regret is special case of & 0-regret (1) with +- = Th
Definition (Extensive-Fone Form Trigger Regret). For any algorithm that plays policies μ² E II at round E [T) the extensive-form trigger regret (also the EFCE-regret) is defined
Reg Tr ((T) == ma Σl (n' - _6p",E"
(6)
Correlated Equilibrium (EFCE) The importance of extensive-form trigger regret is in its connection to computing EFCE: By standard online-to-batch conversion [13, 23], if all players have low trigger regret (with Reg." Tr (T) for the 7th player), then the average joint policy ग is E-EFCE, where
From trigger regret to Extensive-
maXie[m] Reg, Tr (T)/T (cf. Appendix B.2).
We remark in passing by taking & eext, low Ø-regret implies learning (Normal-Form) Coarse Correlated Equilibria in EFGs, as well as Nash Equilibria the two-player zero-sum setting [6].
Efficient H-Hedge for Fxtensive-Form Trigger Regret Minimization
In this section, we study the H-Hedge algorithm (Algorithm 1) for minimizing the trigger regret. Naively, Algorithm requires maintaining and updating p' E Ae. (cf. Line 6), whose computational cost is linear in T which can be exponential in X in the worst case'. We begin by deriving an efficient implementation of the iterate ø' E & (of Line 3) directly by exploiting the structure of D
| is at least the number of determinisicc policies of the game, which could be ((X) in the worst
5

---

3.1 Efficient implementation of T. -Hedge algorithm
We first use a standard trick to convert the computation of ø² (Line 6, Algorithm 1) P-Hedge to evaluating the gradient of a suitable log partition function. This is stated in the lemma below (for any generic Po), whose proof can be found in Appendix C.2.
Lemma 2 (Conversion to log-partition function). Define the log-partition function F Raxd R
p (M) == log Eseo, exp(- (Ø, M)}-
Then Line 3 of Q-Hedge (Algorithm 1) has a closed-form update for all 2
Φ' = (n (1E=i M³) Eocon exp -n ar)
M == (
(8)
Eoeoo exp (n {r
Eq. (8) suggests strategy for evaluating &' = VF (m Σ has some structure that allows efficient evaluation of the sum of exponentials the numerators and denominators (i.e. faster than naive sum), of may be computed directly sublinear in |Pll time, and there is no need to maintain the underlying distribution p¹ E A
== M So long as the vertex set Po
The following lemma enables such an efficient computation for the tog-partition function F pg" (and its gradient) associated with the trigger modification set Φ = o 'r_ This lemma (proof deferred to Appendix C.3) is consequence of the specific structure of do (cf. (5)), whose elements are indexed by a sequence og and a deterministic subtree policy v E V
Lemma 3 (Recursive expression of F and VF For any loss matrix M E RXAXXA, the EFCE log-partition function can be written us
F (MMM)= log Eg,ry,a exp { - (I (I-Eaa-aae Eragag M) + F F (M)
(9)
where for any In Zgg
Fz (M) log Ean exp
M Masenizge + +Enns Esge (M)
(10)
Furthermore, define X (x AxA and m (e ExXX with mzgag I (and also identified vector in TR XRX
A0gag X2,0, exp -1 -1- B : M) + F F (M)
(11)
Mayag (anl2x) caan exp {
Marannaja + EEnnIEC(enaa) F Fnga (M))
(12)
then we have
-VFT((M) = m(A,m) = Eg,e,, Anza (1- -raga + a ezgag).
(13)
Above, X = (Negoy E AXA is probability distribution over X' x A, and m is a collection of subtree policies Majay, where each
E M M= M= Tg,2 II
Mzyag E IT% is subtree policy that specifies an action distribution mz,0g.N (ap (xx) for every In ž Tgg and can be identified with vector in R X (c.f. Section 2.2).
The recursive structure in Lemma offers a roadmap for evaluating (A, m) and thus TF O(X²A3 A2) time (formal statement in Appendix C.4). Applying Lemma 3 with M E M gives efficient implementation of (8), i.c. the HeHedge algorithm with & Φ For clarity, summarize this in Algorithm 2. We remark that the parameters (X', mm*)) therein can also be expressed in terms of (X--1 m² and M which present in Algorithm 4 (the equivalent "OMD" form) in Appendix C. We also note that the fixed point equation o' fu in Line 5 can be solved in A2) time [23, Corollary 4.15).
(M) in
3.2 Equivalence to FTRL and OMD
We now show that Algorithm 2 equivalent FTRL and OMD with suitable dilated entropies and divergences (hence the name EFCE-OMD). We define the trigger dilated entropy function and trigger

---

Algorithm 2 EFCE-OMD (FTRL form; equivalent OMD form in Algorithm 4)
Require: Learning rate 7) > 0. 1: for t- 1,2...., do
2:
For each Fgg E A' A, from the reverse order of The compute m sgggg (an) and Ft. "aaaoth
mizag,h (anl<n)) Xan exp { Σ.= M
Pt
S2aaeens }. (14)
shonk 200g
F Ft agggginn = log Eas exp { E M Manas.oaa =Essnee((ss agggeenti (15)
1-1
3: Compute Noya
No,0, Kagaz exp { ( Ex M+)
F 12
(16)
4: Compute o' oa\,, m²) where is in Eq. (13).
5: Compute the policy n², which is a solution of the fixed point equation d'r²² = n²: IRXA
6: Receive loss & {6, (arn: on) (en
7: Compute matrix loss M (1²)) E ERR20 XAXXXX
dilated KI. divergence function over (A, A Mas
HT m) == H()) Egingga, Azgag Ha, (mzggg))) ml, m = DKL (AIIX) + Egitgie, t Dz, (Ma |
where H-) and D (:11.) are the (negative) Shannon entropy and KL divergence; and for any zg- Hu, (-) is the dilated entropy, and Dz, (-I1-) is the dilated KL divergence [30], both for the subtree rooted By (dctailed definitions Appendix C.5).
Lemma (Equivalent formulations of & Tr- hedge). For any sequence of loss functions {M') Jtz1, the iterates (X* m²) in Algorithm 2 (i.e. (14)-(16)) are equivalent to (i.e. satisfy) the following FTRL update H Tr and OMD update on Dhr
(X, (,m))) = arg minx
1 (0(,,)) E,, M²) + H TA, m)).
(x)
(17)
(X, m²) arg minx.m 17 m), M + D m |n m² 1mAA-1mm'-))
(18)
The proof of Lemma 4 follows directly by the concrete forms of (A m²) in (14)-(16), and can be found in Appendix C.6.
3.3 Regret bound under full feedback and bandit feedback
We now present the regret bounds of Algorithm 2. We emphasize that these regret bounds are simple consequence of the generic bound for H-Hedge in (2), and their proofs do not depend the actual implementation of Algorithm 2 developed the preceding two subsections. We first consider the full feedback setting, where the full expected loss vector &e E R.X is received after each episode.
Theorem 5 (Regret bound of EFCE-OMD under full feedback). Running Algorithm with n O(v 1 achieves the following trigger regret bound
Reg Tr (T) S <0(v H2 (T),
where L == Io)(XA) is a log factor.
The proof of Theorem 5 is simply by applying (2) and observing that log( S [[l]]| log A -
log(XA) (see Appendix D.1). This theorem shows that the Tedge algorithm gives Ó(vXT) trigger regret bound, which matches the informatiin--hherrticc lower bound Q XT) [48, Theorem 2] up to (poly((F)))))) (H)) factor, and is slightly better than the ((VXAT) upper bound of [42, Corollary F33] though their definition of EFCE-regret is slightly stricter (thus higher) than ours.
7

---

Algorithm 3 Balanced EFCE-OMD (FTRL form; equivalent OMD form in Algorithm 5)
Require: Learning rate 77, balanced exploration policy {u**) )eem)) 1: for = .., T do
2: For each Bg E X' x A, from the reverse order of Th, compute m magag & (0n and Fe, "gggyth
1-1
M Maggggh(aanaan Xan exp M
(igh and (nn
(-n)
M
M
Σ
Fr, Fig agageants ) }
==1
Ih+1 EC(ehaa)))))
Fxt
1
log Σ exp {
Moth (Dn, ax)
aAEA
M
Σ (((AOO(
Fdd
Eggg mm
By 2000
3: Compute X++1 as 2g4g
t-1
Mgg Xxya, exp
XA n Bra
Ma) + pes
ag9g110) )
(20)
4: Compute Ø' = o(\', (0)), where & is as defined in Eq. (13).
5: Find μ² to be solution of the fixed point equation x² p'pp²
6: Play policy μ², observe trajectory (I a ThEEE
7: Form vector loss estimator fT,2,0g " (Ih, an) an) for each (g, (gggg) as in Eq. (23).
8: Compute matrix loss estimator M E Lg 1e gl eagag"
In the bandit feedback setting, the learner only observes her own rewards and infosets. In this case we replace & in Algorithm 2 with the following loss estimator (with IX bonus 7) proposed in [34]:
(Tn, an) == [( a (2n, an)} (1 rft//// (Zn, an) + 7).
(19)
We show that EFCE-OMD achieves the following guarantee in the bandit feedback setting (proof in Appendix D.2). The proof follows by plugging the loss estimator ?" into (2) and additionally bounding concentrations (which we remark better strategy than using a naive bandit-based loss estimator in the corresponding NFG space).
Theorem 6 (Regret bound of EFCE-OMD under bandit feedback), Run Algorithm with loss AT),, and ? V|[l 1/(XAT). Then we have the following trigger regret bound with probability least ô:
estimator {e') [ (19), /[TlI] log A
Rog ((T s (| T),
where log(3X A/8) is log term
To our best knowledge, Theorem gives the first trigger regret bound against adversarial opponents and bandit feedback. This ((vX X [1], T') rate is VXA worse than Theorem (ignoring // and log factors), and is most Ö(v A2 using ||]]|| s.X. X.
4 Balanced EFCE-OMD for bandit feedback
We now build upon the EFCE-OME algorithm (Algorithm 2) to develop new algorithm, Balanced EFCE-OMD (Algorithm 3), and show that achieves near-optimal extensive-form trigger regret guarantee under bandit feedback. Here we discuss the two key modifications in the algorithm design.
Key modification I: "Rebalancing" the log-partition function Building on the balancing tech- nique of [6], we start from Eq. (9) and (10) of the log partition function, and rescale the inner functions F Fayayan using balanced exploration policies (4 (I on Jg. (see Definition E.

---

for the formal definition), and rescale the outer function F by XA. Concretely, for any matrix M& E R XAX, we define the balanced EFCE log- 1e8--patition funtttion.uunctin as
Flll == X E Enagioo exp
(T Pogagay M) + F 2g0g (M))
(21)
XA
where for any 24 ž Fg (using High = - High (Ins (xn, an) as shorthand, which depends on In but not an).
Fx aagggan (M) == h. H gch
log Σ exp {
x Manan.200
Σ
F Egg as (M)) (22)
(C(PAOR)
Key modification II: New loss estimator under bandit feedback We use an adaptive family of Sandit-based loss estimators (E Iz00,
C C250 X.A one for each (zg: 0g) E X' x A, defined as
20
2,0000 (Ih,, an) ==
(23)
Win (1p. (a (a) " "igggiith (F (m) bmy)"))
where Maja, == (xg (g) for shorthand. The main difference of (23) over (19) is in the adaptive IX bonus term on the denominator that scales with y but is different for each 0g We then place each urz ga into the Ty -th column of a matrix loss estimator M or in matrix form,
M = E Eg Haya, Tiiia e 2
With (21)-(23) at hand, our algorithm Balanced EFCE-OMD defined as the negative gradient of Fla evaluated at the cumulative loss estimators:
0¹ -- (1 M*). 14 221, ball
(24)
and n² E II solves the fixed point equation o' = n². Similar as EFCE-OMD, (24) also admits efficient implementations in both FTRL and OMD form (cf. Algorithm & 5). The corresponding m²) is also equivalent to rumning a FTRL/OMD algorithm with respect to a balanced dilated entropy/KL- over & E + Tr (cf. Lemma E.4 and Appendix E.3 for details).
Main result We now present the theoretical guarantee of Algorithm 3 (proof in Appendix F).
Theorem Balanced EFCE-OMD (Algorithm 3) with v = /X At/ HT and 7 = 2/ X A HºT achieves the following extensive-form trigger regret bound with probability at least 1 6:
Reg Ti (T) S (O(HHXATT))
where = log( A00X is a log term.
The (VXATT) trigger regret asserted in Theorem 7 improves over Theorem 6 by a factor of || and matches the information-theoreti lower bound up poly H) and log factors2. By the online-to- batch conversion (Appendix B.2), Theorem also implies an Ö( X A/e²) sample complexity for learning EFCE under bandit feedback (assuming same game sizes for all m players). This improves over the best known Hm X A2 /c²) sample complexity in the recent work of Song et al. [42]².
Overview of techniques The proof of Theorem 7 is significantly more challenging than that of Theorem 6, even though the algorithm itself is designed by appearingly simple modifications. This happens since Algorithm 3, unlike Algorithm 2, no longer necessarily corresponds to any normal-form algorithm. The technical crux of the proof losses), which we do by carefully controlling a series of second-order terms utilizing the balanced policies within F. and the new adaptive IX bonus within ("7=50% Jaga, (Lemma F.5-F88).
bound the nonlinear part of F.T (with respect to the
2 As the trigger regret is lower bounded the vanilla (extemnal) regret, [6. Theorem implies an {2 XATI lower bound for trigger regret as well under bandit feedback. We remark though that the 1-EFR algorithm of [42] actually finds an "1-EFCE" which is slightly stronger than our EFCE defined via trigger modifications.

---

Equivalence of OMD and Vertex MWU for external regret minimization
As another illustration of our framework, we now choose + ext conv { {$5**) } to be the set of external policy modifications, which modify any policy to some deterministic policy. In this case, the Φext -edge algorithm minimizes the external regret in EFGs. In this section, we show that -edge same as the vertex MWU algorithm considered in Farina et al. [25], is actually equívalent to the OMD with dilated entropy [30]. Let (221 C X be an arbitrary sequence of loss vectors. 20
Vertex MWU We use V denote all the deterministic sequence-form policies, which can also be viewed as the vertex set of the policy set II. A simple reformulation (cf. Appendix G) shows that next- (Algorithm 1) gives the vertex MWU algorithm considered by Farina et [25]
and Pd Di exp (.,
1. = E.
(25)
OMD with dilated entropy Another popular algorithm for external regret minimization is the OMD algorithm on the sequence-forn policy space with the dilated entropy [30, 35]:
k² arg min [ (1, E-1) + Do(ullul []
(26)
PEll
(1 an) log pn(an (a(an/sr)) Un (an|21)
De(n|lu)
Σ
Σ
(27)
h=1 2a
Theorem 8 (Equivalence of OMD and Vertex MWU), For any sequence of loss vectors {() h121.
OMD with dilated entropy equivalent Vertex MWU, that is, (26) and (25) give the same {n he2r
The proof of Theorem 8 can be found in Appendix G.I. Our proof also reveals that the efficient implementation of Vertex MWU developed by Farina et al. [25] using the "kernel trick" is actually equivalent to the standard linear-time efficient implementation of OMD with dilated entropy.
Conclusion
In this paper, we present efficient implementation of the D-Hedge algorithm for minimizing the extensive form trigger regret. The algorithm is equivalent to OMD with dilated regularizers, and achieves efficient regret bounds under both full feedback and bandit feedback. We also design improved algorithm Balanced EFCE-OMD, which achieves a sharp trigger regret bound under bandit feedback. We believe our work leads many open questions, such efficient implementations of He-Hege with more general & sets (e.g. the behavioral modifications considered in [38, 42)), or accelerated polylog(T)) (T) --regret bounds under full feedback by optimistic algorithms.
Acknowledgment
S.M. is supported by NSF grant DMSS2210827. C.J. is supported by Office of Naval Research N00014-22-1-2253. T.Y. is supported by NSF CCF-21 12665 (TILOS Al Research Institute).
References
[1] A. Agarwal, Hsu, S. Kale, J. Langford, I.. Li, and Schapire. Taming the monster: fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
[2] I. Anagnostides, C. Daskalakis, G. Farina, M. Fishelson, N. Golowich, and T. Sandholm. Near- optimal no-regret learning for correlated equilibria in multi-player general-sum games. arXiv preprint arXiv:21 2021.
[3] I. Anagnostides, G. Farina, C. Kroer, C.-W. Lee, H. Luo, and T. Sandholm. Uncoupled learning dynamies with oloogt) swap regret multiplayer games. arXiv preprint arXiv:2204. 1417, 2022.
10

---

[4] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta- aegta-agooritm and applications. Theory of computing. 8(1):121-64, 2012.
[5] R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67-96, 1974.
[6] Y. Bai, C. Jin, S. Mei, and T. Yu. Near-optimal learning of extensive-forn games with imperfect information. arXiv preprini arXiv:2202.01752, 2022.
[7] A. Bakhtin, D. Wu, A. Lerer, and N. Brown. No-press diplomacy from scratch. Advances in Neural Information Processing Systems, 34, 2021.
[8] A. Blum and Y. Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
[9] N. Brown and T. Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 3596677))418-424, 2018.
[10] N. Brown and T. Sandholm. Superhuman for multiplayer poker. Science, 365(64566:885-89)) 2019.
[11] N. Burch, M. Moravcik, and M. Schmid. Revisiting cfr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429 443, 2019.
[12] A. Celli, A. Marchesi, T. Bianchi, and N. Gatti. Learning to correlate in multi-player general-sum sequential games. Advances in Neural Information Processing Systems, 32, 2019.
[13] A. Celli, A. Marchesi, G. Farina, and N. Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. Advances in Neural Information Processing Systems, 33:7722-7732, 2020.
[14] N. Cesa-Bian Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[15] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
[16] C. Daskalakis, M. Fishelson, and N. Golowich. Near-optimal no-regret learning general games. Advances in Neural Information Processing Systems, 34, 2021.
[17] M. Dudik and G. Gordon. A sampling- based approach to computing equilibria in succinet extensive-form games, arXiv preprint arXiv: wo... 2012.
[18] M. Dudik and G. Gordon. sampling- based approach to computing equilibria succinet extensive-form games. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 151-160, 2009.
[19] G. Farina and T. Sandholm. Model-free online learning in unknown sequential decision making problems and games. arXiv preprint arXiv:2103.04539, 2021.
[20] G. Farina, C. K. Ling, F. Fang, and T. Sandholm. Correlation in extensive-form games: Saddle- point formulation and benchmarks. Advances in Neural Information Processing Systems, 32, 2019.
[21] G. Farina, C. Kroer, and T. Sandholm. Faster game solving via predictive blackwell approach- ability: Connecting regret matching and mirror descent. arXiv preprint arXiv:2007. 14358, 2020.
[22] G. Farina, C. Kroer, and T. Sandholm. Stochastic regret minimization in extensive- games. In International Conference Machine Learning, pages 3018-3028. PMLR, 2020.
[23] G. Farina, A. Celli, Marchesi, and N. Gatti. Simple uncoupled no-regret learning dynamics for extensive- formm correlated equilibrium. arXiv preprint arXiv:2104.0755 2021.
11

---

[24] G. Farina, R. Schmucker, and T. Sandholm. Bandit linear optimization for sequential decision making and extensive-form games, arXiv preprint arXiv:2103.04546, 2021.
[25] G. Farina, C.-W. Lee, H. Luo, and C. Kroer. Kemelized multiplicative weights for 0/1 polyyeeeaa games: Bridging the gap between learning in extensive-fome and normal-fome games. arXiv preprint arXiv:2202.00 002377 2022.
[26] D. Foster and R. V. Vohra. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
[27] G. J. Gordon, A. Greenwald, and C. Marks. No-regret learnnng in convex games. In Proceedings of the 25th international conference on Machine learning, pages 360-367, 2008.
[28] A. Greenwald and A. Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. In Learning theory and kernel machines, pages 2 12. Springer, 2003.
[29] A. Herbig. Game theory in marketing: Applications, uses and limits. Journal of Marketing Management, 7(3):285-298, 1991.
[30] S. Hoda, A. Gilpin, J. Pena, and T. Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494-55) 5124 2010.
[3]] W. Huang and von Stengel. Computing extensive-form correlated equilibrium in poly- nomial time. In International Workshop on Internet and Network Economics, pages 506-513. Springer, 2008
[32] V. Kakkad, H. Shah, R. Patel, and N. Doshi. A comparative study of applications of game theory in cyber security and cloud computing. Procedia Computer Science, 155:680-685, 2019.
[33] S. Khot and A. K. Ponnuswami. Minimizing wide range regret with time selection functions. In COLT, pages 81-86, 2008
[34] T. Kozuno, Ménard, Munos, and M. Valko. Model-free learning for two-player zero-sum partially observable markov games with perfect recall. arXiv preprint arXiv:2 106.06,,,,,,6,9,, 2021.
[35] C. Kroer, K. Waugh, Kilinç-Karzan and T. Sandholm. Faster first-order methods for extensive-form game solving. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 81 817-834, 2015.
[36] M. Lanctot, K. Waugh, M. Zinkevich, and M. H. Bowling. Monte carlo sampling for regret minimization in extensive games. In NIPS, pages 1078-1086, 2009.
[37] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[38] D. Morrill, R. D'Orazio, M. Lanctot, J. R. Wright, M. Bowling, and A. R. Greenwald. Efficient deviation types and learning for hindsight rationality in extensive- form games. In International Conference Machine Learning, pages
PMLR, 2021.
[39] R. B. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
[40] J. F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48-444 49, 1950.
[41] M. Schmid, M. Moravcik, N. Burch, R. Kadlec, J. Davidson, K. Waugh, N. Bard, F. Timbers, M. Lanctot, Z. Holland, et al. Player of games. arXiv preprint arXiv:2112.0311 2021.
[42] Z. Song, S. Mei, and Y. Bai. Samplc-efficient learning of correlated equilibria in extensive-form games. arXiv preprint arXiv:2205.077: 072233, 2022.
[43] G. Stoltz and G. Lugosi. Internal regret on-line portfolio selection. Machine Learning, 59(1): 125-159, 2005.
[44] G. Stoltz and G. Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1) 2007.
[45] Y. Tian, Q Gong, and T. Jiang. Joint policy search for multi-agent collaboration with imperfect information. arXiv preprint arXiv:2008.064995, 2020.
12

---

[46] B. Von Stengel and F. Forges. Extensive-form correlated equilibrium: Definition and computa- tional complexity. Mathematics of Operations Research, 33(4):1002-1022, 2008.
[47] B. H. Zhang and Sandholm. Finding and certifying (near-) optimal strategies in black- box extensive-form games. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 35, pages 5779-5788, 2021.
[48] Y. Zhou, T. Ren, J. Li, D. Yan, and Zhu. Lazy-cfr: fast and near optimal regret minimization for extensive games with imperfect information. arXiv preprint arXiv: (xXiv:8810004333 2018.
[49] Y. Zhou, J. Li, and J. Zhu. Posterior sampling for multi-agent reinforcement learning: solv- ing extensive games with imperfect information. In International Conference on Learning Representations, 2019.
[50] Y. Zhou, Ren, J. Li, D. Yan, and Zhu, Lazy-cfr: fast and near-optimal regret minimization for extensive games with imperfect information. In International Conference on Learning Representations, 2020. URL,
[51] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20:1729-1736 2007.
13


Reviews:
[{"review_id": "oDK3CHR6soz", "reviewer": "Reviewer_ZYdg", "summary": "The paper shows gives uncoupled no-regret dynamics for EFCE in extensive-form games with improved sample complexity both under full-information and (adversarial) bandit feedback. The regret bound in the full-information case matches concurrent work by Song et al.; the bandit case yields state-of-the-art results in that it applies even to adversarial opponents.\n\nThe proposed algorithm, from a conceptual standpoint, takes the extensive-form game and converts it into a normal-form game. Then, it applies the Phi-hedge algorithm for the choice of trigger deviation functions. The main hurdle is sidestepping the exponential blowup due to the normal-form conversion. In that sense, the paper provides a positive result that complements well the recent result by Farina et al. on kernelizability of OMWU (KOMWU) learning dynamics.\n\nAs an additional result, the authors point out that both KOMWU and their algorithm can be implemented in extensive-form games as specific instances of OMD with dilated entropy regularizers.", "questions": "In the past, certain results have focused on model-free learning within the bandit feedback. Effectively, what that means is that the structure of the decision space of each player (treeplex) needs to be discovered as part of the learning process. See for instance [1] and [2]. Because the structure of the decision problem is not known upfront, it is not immediately clear that one can instantiate a balanced exploration strategy. Do you think that your approach could be used to address that setting as well?\n\n\n[1] Farina and Sandholm. Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games.\n\n[2] Kozuno, Menard, Munos, and Valko. Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall.", "limitations": "No unaddressed concerns.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think the paper is interesting and well organized. The results are important and fit well within the current efforts on the topic and the existent literature. I also found the remark on KOMWU being equivalent on OMD+dilated entropy regularization very interesting. Overall, I have a very positive opinion of the paper.\n\nOriginality: The paper presents original research and is technically strong. None of the results can be classified as groundbreaking, but at least one of the result was unexpected to me (equivalence between KOMWU and OMD+dilated regularizer), and the other results represent new state-of-the-art bounds.\n\nSignificance: the results are natural and well-motivated. I am confident that the paper will be well-received within the learning-in-games community.\n\nQuality and clarity: the paper represents high-quality work. Both the body and the supplementary material are curated and easy to follow, at least for an expert in the field.", "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": "QT8FlHw4vdD", "reviewer": "Reviewer_4HYo", "summary": "The paper studies the problem of computing an EFCE in extensive-form games. First, it presents an efficient implementation of $\\Phi$-Hedge which minimizes a suitable notion of regret (i.e., trigger regret). Then, the authors show that such algorithm is equivalent to an OMD framework with dilated regularizers (EFCE-OMD). The authors provide regret upper bounds for EFCE-OMD in the full feedback and bandit feedback setting. Such bounds can be further improved via a modified version of the algorithm (Balanced EFCE-OMD) to match the information-theoretic lower bound. \n", "questions": "None.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and technically solid. The contributions span several interesting directions related to the problem of computing correlated equilibria in extensive-form games. \n\nA small typo: eq. (1) is probably missing a summation.", "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": "QMXrH1MOXZI", "reviewer": "Reviewer_mcQf", "summary": "This work addresses the task of developing an efficient algorithm for $\\Phi$-regret minimization in extensive-form games (EFGs). As a first step toward this goal, the authors consider the problem of regret minimization in the normal-form representation of the EFG that is known to have an exponential dimension with respect to the ATG size.  In such a scenario, they provide a computationally efficient version of the algorithm $\\Phi$-Hedge that, under a suitable definition of the set $\\Phi$ can be used to approximate equilibria like for instance the EFCE.\nIn the second part of the paper, the authors show that their version of $\\Phi$-Hedge is equivalent to FTRL and OMD with suitably defined dilated entropies and divergences. Based on this equivalence, they recover near-optimal regret bounds for both the full feedback case and the bandit feedback one (in the latter case regret bounds are in high probability).", "questions": "I do not have any question for the authors. ", "limitations": "This work is theoretical, hence it has no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe paper provides a solid contribution to the field of regret minimization in games. The writing is clear, overall resulting in a very good quality of presentation. As far as I'm concerned the theoretical claims are sound, novel, and non-trivial. The review of the related works seems accurate. For such reasons, I believe that this is a work that is ready to be published at a venue like NeurIPS.\n\nWeaknesses: \nSince the claims of the paper are those of an efficient algorithm, an experimental evaluation comparing their solution with previous state-of-the-art for computing EFCE (e.g., [1], [2]) could have been proposed. However, I understand that the contribution that this paper intends to propose is mainly theoretical, hence I would classify such weakness as a minor. \n\n[1] Farina et al. \"Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium\". \n[2] Celli et al. \"No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium\".", "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