Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback
Authors: Canzhe Zhao
Yutian Cheng
Jing Dong
Baoxiang Wang
Shuai Li
Venue: ICML 2025 poster (2025)
Keywords: Extensive-form games; partially observable Markov games (POMGs); last-iterate convergence
Primary area: reinforcement_learning->online
TL;DR: The first last-iterate convergence learning of IIEFGs in the bandit-feedback setting.

Abstract: We investigate learning approximate Nash equilibrium (NE) policy profiles in two-player zero-sum imperfect information extensive-form games (IIEFGs) with last-iterate convergence guarantees. Existing algorithms either rely on full-information feedback or provide only asymptotic convergence rates. In contrast, we focus on the bandit feedback setting, where players receive feedback solely from the rewards associated with the experienced information set and action pairs in each episode. Our proposed algorithm employs a negentropy regularizer weighted by a "virtual transition" over the information set-action space to facilitate an efficient approximate policy update. Through a carefully designed virtual transition and leveraging the entropy regularization technique, we demonstrate finite-time last-iterate convergence to the NE with a rate of $\widetilde{\mathcal{O}}(k^{-\frac{1}{8}})$ under bandit feedback in each episode $k$. Empirical evaluations across various IIEFG instances show its competitive performance compared to baseline methods.

Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback
Canzhe Zhao' Yutian Cheng'
Jing Dong²
Baoxiang Wang? 2 Shuai Li'
Abstract
Yard (Schmid et al., 2021), and Mahjong (Li et al., 2020; Kurita & Hoki, 2021; Fu et al., 2022). Extensive research has been devoted to identifying the (approximate) Nash cquilibrium (NE) (Nash Jr. 1950) within IIFGGs. With the full knowledge of the game, various methodologies have been employed to tackle these games. These include lin- ear programming approaches (Koller & Megiddo, 1992; Von Stengel, 1996; Koller et al., 1996), first-order opti- mization techniques (Hoda et al., 2010; Kroer et al., 2015;
We investigate learning approximate Nash equi- librium (NE) policy profiles in two-player zero- sum imperfect information extensive-form games (IEFGG)) with last-iterate convergence guarantees. Existing algorithms either rely on full-information feedback or provide only asymptotic convergence rates. In contrast, we focus on the bandit feedback setting, where players receive feedhack solely from the rewards associated with the experienced information set and action pairs in each episode. Our proposed algorithm employs a negentropy regularizer weighted by a "'virtual transition" over the information set-action space to facilitate an ef- ficient upproximate policy update. Through a care- fully designed virtual transition and leveraging the entropy regularization technique, we demon- strate finite-time last-iterate convergence to the NE with a rate of OOk-' 1/=) under bandit feedback in each episode k. Empirical evaluations across various IEFG instances show its competitive per- formance compared to baseline methods.
2018; Munos et al., 2020; Lee et al., 2021; Liu et al., 2022), and counterfactual regret minimization (CFR) algorithms (Zinkevich et al., 2007; Lanctot et al., 2009; Johanson et al., 2012: Tammelin, 2014; Schmid et al., 2019; Burch et al., 2019; Liu al., 2022).
In practical scenarios, IIEGGs might involve unknown re- ward distributions over information set and action spaces, thwarting the application of the above approaches for com- puting the NE in IIEFGs. In this realm, the NE in IIEFGs is typically learned from random samples gathered through iterative playthroughs of the game, by Monte-Carks CFR methods (Lanctot al., 2009; Farina al., 2020; Farina & Sandholm, 2021), online mirror descent (OMD) follow- the-regularized-leadee (FTRL) frameworks (Farina et al., 2021; Kozuno et al., 2021; Bai et al., 2022; Fiegel et al., 2023). Notably, Bai et al. (2022) devise an OMD-based approach incorporating "balanced exploration policies" to learn an e-approximate NE with a sample complexity of Ô (H + /B)) where H is the horizon length, X, Y are the sizes of the information set space for the max- and min-player, and A, B are the sizes of the action space for the max- and min-player. This upper bound is information- theoretically optimal with respect to all parameters except H, up to logarithmic factors. Building upon Bai et al. (2022), Fiegel et al. (2023) make further strides, refining the upper bound to Ô (H (H)X++YB)/+²) by harnessing FTRL with "balanced transitions", achieving (nearly) optimal sample complexity in all parameters.
1. Introduction
In imperfect information games (IIGs), players operate with limited visibility of the game's true state, necessitating strategic decision-making based on incomplete information. Notably, the concept of imperfect-informatio extensive- form games (IEFGs), as introduced by Kuhn (1953), encap- sulates both the intricacies of imperfect information and the sequential nature of players' moves. This framework aptly represents broad spectrum of weal-world scenarios, such as Poker (Heinrich et al., 2015; Moravčík et al., 2017: Brown & Sandholm, 2018), Bridge (Tian et al., 2020), Scotland
'John Hopcroft Center for Computer Science Shanghai Jiao Tong University "School of Data Science, The Chinese Univer- sity of Hong Kong, Shenzhen. Correspondence to: Shuai Li <shuaili8 @ sjtu.cdu.cn>
Despite the (nearly) optimal leaning of the e-NE in IIEGGs by Bai et al. (2022) and Fiegel et al. (2023), the algorithms in these works require to average all the policies generated during the running of the algorithms, so as to obtain the final policy profile with s-NE guarantce. This is typically
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
termed as the average-iterate convergence. However, in cases when the policies in the games are approximated by nonlinear function approximation (e.g., neural networks), which has achieved great empirical success in recent years (Moravčík et al., 2017; Brown & Sandholm, 2018), com- puting the averaged policy might even be infeasible due to the nonlinearity of such function approximations. This motivates the studies of the learning algorithms with the last--teratt convergence guarantee of various games includ- ing HEFGs (Lin et al., 2020; Wei et al., 202 Lee et al., 2021; Cai et al., 2022; Abe et al., 2023; Feng et al., 2023; Cen et al., 2023; Liu et al., 2023). Specifically, Lee et al. (2021) and Liu et al. (2023) establish algorithms for learn- ing HEFGs with a last-iterate convergence rate of (1//k). However, the algorithms proposed by Lee et al. (2021) and Liu et al. (2023) rely on full-information feedback when learning IIEFGs, and therefore cannot be directly applied in practical scenarios where only bandit feedback is available. The above considerations naturally motivate the following question:
efficient bound for the stability term of OMD with the virtual transition-weighet
negentropy regularizer. To this end, we devise a virtual transition over the infor- mation set-action space that maximizes the minimum "visitation probability" across all information sets (see Section 4.2 for more details). With this virtual transition, we ultimately prove that our algorithm achieves a last- iterate convergence rate for learning IIEFGs in the bandit feedback setting of O((X + [) + YB) + (X + ")V*H]kVV/ with high probability for each episode k. When only obtaining an expected NE gap is of in- terest, we also show that our algorithm can generate a policy profile that converges to the NE with a rate of O((X= + {){(X² + B² + (X + Y) H//HH (see Section 5.1 for more details).
Additionally, we conduct empirical evaluations on a vari- ety of IIFFG instances, which demonstrate the advantages of our proposed algorithm over baseline methods (see Appendix for details).
Can we achieve last-iterate convergence for learning HEFGss with bandit feedback?
2. Related Works
In fact, this same question has also been posed by Fiegel et al. (2023). In this work, we answer this question affirmatively. The main contributions of our work are summarized as follows:
2.1. Partially Observable Markov Games (POMGs)
With perfect information, learning Markov games (MGs) can be traced back to the seminal work of Littman & Szepesvári (1996) and has since garnered extensive research attention (Littman, 2001; Greenwald & Hall, 2003; Hu & Wellman, 2003; Hansen et al., 2013; Sidford et al., 2018; Pérolat et al., 2015; Fan et al., 2020; Jia et al., 2019; Cui & Yang. 2021: Zhang et al., 2021; Bai & Jin, 2020; Liu et al., 2021; Zhou et al., 2021: Song et al., 2022; Li et al., 2022: Xiong et al., 2022; Wang et al., 2023; Cui al., 2023). In scenarios where only imperfect information is available yet the complete knowledge of the game (state transitions and rewards) is known, existing research can be catego- rized into three primary streams. The first stream leverages requence-form policies to recast the problem as a linear pro- gram (Koller & Megiddo, 1992; Von Stengel, 1996; Koller et al., 1996). The second stream translates the problem into minimax optimization problem and explores first-order algorithms, as exemplified in Hoda et al. (2010); Kroer et al. (2015; 2018), Munos et al. (2020); Lee et al. (2021); Liu et al. (2022). Lastly, the third stream addresses the prob- lem through CFR, minimizing counterfactual regrets locally within each information set (Zinkevich et al., 2007: Lanctot et al., 2009; Johanson et al., 2012; Tammelin, 2014; Schmid et al., 2019; Burch et al., 2019; Liu et al., 2022).
We introduce the first algorithm that learns the approx- imate NE of IEFGs with provable last-iterate conver- gence in the bandit feedback setting. Unlike previous approaches (Lee et al., 2021; Liu al., 2023) that use a dilated negentropy regularizer to achieve last-iterate con- vergence for IEEGGs under full-information feedback, our algorithm employs a negentropy regularizer weighted by a "virtual transition" over the information set-action space.
This design prevents our algorithm from encountering the issues of coupled information set-action pairs a problem that arises with the dilated negentropy regularizer and would otherwise result in an excessively large stability term when applying the entropy regularization technique over the objective function. On the other hand, from the computational perspective, we show that our algorithm still admits a closed-form solution for policy updates over the full policy space, similar to the dilated negentropy regularizer. This facilitates efficient approximate policy updates, in contrast to using the vanilla negentropy reg- ularizer (see Section 4.1 for details). Furthermore, our algorithm does not require any communication or coordi- nation between the two players and is model-free, without requiring the knowledge of the underlying state transition probabilities.
In the realm where the knowledge of the game is unknown, existing research focuses on integrating OMD and FTRL frameworks with importance-weighhee loss estimators (Fa- rina et al., 2021; Kozumo et al., 2021; Bai et al., 2022; Fiegel et al., 2023). Remarkably, Bai et al. (2022) achieve the sample complexity of Õ (X + Y B)²) for learn-
To achieve the last-iterate convergence rate with a sharp dependence on X (and Y), it is essential to establish an
2

---

Learning HEFGGs with Last-iterate Convergence under Bandit Feedback
ing an e-approximate NE by employing "balanced" di- lated KI.-divergence as the distance metric. Building upon this concept, Fiegel et al. (2023) utilize "balanced transi- tions" and attain a (nearly) optimal sample complexity of O (H(XA+ + YB) /ee"). However, we note that all the exist- ing algorithms studying POMGs with bandit feedback only have average-iterate convergence guarantees, while we aim to establish the algorithms with last-iterate convergence guarantees.
Partially Observable Markov Games We study episodic, finite-horizon, two-player zero-sum POMGs, denoted by P A, IP, r), in which
H the horizon length:
s Uneean Sr. is the finite state space, where Sn is the state space at step h and Sn Sn = 0 for any h * h'.
5 -h Sn is the size of S and [S, = Sr for all h;
X x== Unejaj Mr is the finite space of information sets (short for infosets in the following) for the max-player, where X, = {x(s) 8 E } is the set of the infosets at step h and x S + X' is the emission function.
2.2. Last-iterate Convergence Learning in Games
With full- iilliinformatin feedback, learning in games with last-iterate convergence guarantee has been investigated in strongly monotone games (Mokhtari et al., 2020; Jordan et al., 2024), monotone games (Golowich et al., 2020; Cai
Σ Xn, is the size of X' with [&g X₁, The finite space of infosets y Unetzn 3/h for the min-player and its size are defined analogously;
et al., 2022; Gorbunov et al., 2022; Cai & Zheng, 2023), Markov games (Cen et al., 2021; Zeng et al., 2022; Cen et al., 2023), and IEFGSs (Lee et al., 2021; Liu et al., 2023;
A with |AA| = A and B with [B] B are the finite action spaces for the max-player and min-player, respectively;
Bernasconi al.. 2024). Besides, there are some works studying achieving last-iterate convergence in games with noisy feedback. For instance, Abe et al. (2023; 2024; 2025) establish algorithms for solving two-player zero-sum matrix games or multi-playe monotone games with noisy gradient feedback, where the noisy feedback for all the actions is observable.
= (po()) E As } Uips (-1sh: an, bn)) E XeIH, are the state transition probabilities, where Po(-) is the probability distribution of initial states, (s 118, an bx) is the probability of transitioning to the next state sh+1 conditioned on (sh, an, bs) at step h. and As, denotes the probability simplex over Sn
Recently, motivated by the fact that it might be restrictive to require full knowledge of the (noisy) gradient as in the full-information feedback setting, a growing body of works has studied learning in games with last-iterate convergence guarantee in the bandit feedback setting, including strongly monotone games (Bravo et al., 2018; Hsich et al., 2019; Lin et al., 2021; Drusvyatskiy et al., 2022; Huang & Hu, 2023) and matrix games (Cai et al., 2023). Though the last- iterate convergence guarantees have also been established for Markov games (Wei et al., 2021b; Chen et al., 2022: 2023; Cai et al., 2023), existing algorithms are not fully de- coupled, with the exception of the algorithms of Chen et al. (2023) and Cai et al. (2023). In particular, the algorithm of Wei et al. (2021b) needs coordinated updates and prior knowledge of the game, and the algorithm of Chen et al. (2022) requires the players inform the opponent about the entropy of their own policies. Moreover, we note that all existing works study fully observable Markov games, while this work aims to establish uncoupled algorithms for learning IIEGGs in the formulation of partially observable Markov games, where only partial information of the under- lying states is revealed to the players.
r = (ra (5h. On, bn) E [0, 1] (sp. b,, x xAx are the (random) reward functions with Th (8h, an, bn) as mean for each Ty (sh, an, bn).
Learning Protocol We define the max-player's (stochas- tic) policy μ (ua where fhn : Xn - AA denotes the max-player's policy at step h. The set of all such policies for the max-player is denoted by Imax- Anal- ogously, the min-player's 's (stochastic) policy is denoted by he|m), ( with 14 : 3/, + Ag being the min- min-player's
v = {vr J he policy at step h, and the set of all min-player's policies is denoted by Mmin- The game proceeds in a finite number of episodes. At the commencement of episode k the max- player selects policy μ² E Imaxx while the min-player chooses n² E Immn Mcanwhile, an initial state st is sam- pled from po(-) by the environment. During each step h within episode k, the max-player and min-player observe their respective infosets 2 = x(s;) and ví = y(s))) but they do not observe the underlying state st. Given 2i the max-player takes action af 1 ( (-12%) while the min-player concurrently takes an action by ~ o (-lv)) Upon taking these actions, the max max-pllaer and min player receive rewards r = ra af bf) and -r respec- tively. Subsequently, the game transitions to the next state * ~ pn. (-1sf, at, 1).). The k-th episode will terminate af- ter actions at and b/ are taken conditioned on = and v and rewards r/ and -r are observed by the max- -layer and min-player, respectively.
3. Preliminaries
For ease of exposition, we consider IIFGGs in the formula- tion of POMGs (Kozuno et al., 2021; Bai et al., 2022) and introduce the preliminaries in this section.
3

---

Learning HEFGSs with Last-iterate Convergence under Bandit Feedback
Perfect Recall and Tree Structure Following prior works (Kozuno et al., 2021; Bai et al., 2022; Fiegel et al., 2023), we assume that the POMGs adhere to the free structure and the perfect recall condition (Kuhn, 1953). The tree structure signifies that for any step h = 2,..., H and state 8n E Sh. there exists a unique path ($1, 11,61111...... bi....,,,,............. 1..-1100..:00 .p-1:bb-1) culminating in 8h- The perfect recall condition, mean- while, is fulfilled for both players, implying that for any h 2....,P H and any infoset 24 E Xn, there exists unique history (I), (II, Sh-,, a)-1) leading to zh (analogously for the min-player). Furthermore, we de- note by (I an) C Ai. the set of descendants of the infoset-action pair (In, an) at step h' 2 h. Also, we de- fine Ch (1r)= = U Ca an) as the union of de- scendants across all actions at Ty.- For convenience, let C(a,, un) = 1 1 (IA, an) signify the immediate descen- dants at the subsequent step.
the policies {u) of the max-player generated by an algo- rithm with sublinear regret (similarly for the min-player) to obtain the average policy pair (ū,, p) (see, e.g., Theorem I of Kozuno et al. (2021)). This is the so-called average-iterate convergence of learning NE. By contrast, as explained in Section I, in this work, we are interested in finding the e- NE with the (finite-time) last-iterate convergence guarantee; that is, the algorithm is required to generate an approximate NE policy profile (μ* v²) such that NEGap(j" ,²)) I 6k: for each (finite-time) episode k.
Information Available to the Players In this work, learning POMGs in the bandit feedback setting is considered. Specifically, in each episode k, the max-player only observes her experienced trajectory (x at, rf. .y...., a of infosets, actions, and re- wards, but not the underlying states or the opponent's 's infos- and actions (similarly for the min-player). Additionally, the max-player has no knowledge of the min-player's poli- cies and cannot receive any information from the min-plan min-player, and vice versa. Besides, there is no shared randomness be- tween both players; that is, the algorithms of both players need to be fully uncoupled from each other.
Sequence-form Representations For any pair of product policies (14, v), the tree structure and the perfect recall condition facilitate a sequence-form representation of the reaching probability for the state-action tuple (sh, Ch.,ah bn):
(pr ap. bn) = where (s() I Ph (s ans, by) denotes the sequence-form ity, and (La( an) = Ih Me (aw))) and PLaa (yn, b)) == Ih== My (bw lyne) represent the sequence- form policies of the max-player and min-player, respectively. Under the sequence-form representation, we adopt a slight abuse of notation for l and v by interpreting them as u = ={MIn ( and v = {vish " Furthermore, it
(L:((8))))a (x()))) an (1 (s))s))))b) bn), (sn)
Additional Notations We slightly abuse the notation to view Ty as the set {s E S₁ : =<ss) mn), when writing E Th- Given sequence-form representations, for any μ E Imma and sequence of functions f (fi)ne(m with fn Xn X A + R, we define () = (ee(M) A Mist (Th, an [a( 0n). We denote by Fk the o-algebra generated by the random variables ((5), at, My, ri)))e ())))) For brevity, we abbreviate the conditional expectation E[. F²1 as E* Throughout this paper, the notation (()) suppresses all logarithmic factors.
transition probabil-
clear that mmxx constitutes convex compact subspace of X that adheres to the constraints (1 (p)) 2 0 and EANEAHH M1:h (Ih, an.) P1:h- 1 (Th-1, 1)- where (2h-1, 1h-1) is such that Iı E C( 11 1x-1) (with the convention that (1:0(20, an) = 1 as a base case).
4. Algorithm
This section presents the proposed algorithm, detailed in Algorithm 1. In Section 4.1, we introduce the algorithmic framework as well as the virtual transition transition-weighted negen- tropy regularizer. In Section 4.2, we present the algorithmic design to compute an effective virtual transition to incorpo- rate into the regularizer.
Learning Objective In this work, we consider the learn- ing objective of finding an approximate NE of the POMGs. Specifically, for any E 2 0, an e-approximate NE is a pair of product policy (e, v) satisfying NEGap( v) S E, where
NEGap(u, v) ==
sup wl Ptel
Vul Vuot
4.1. From Sequence-form Policies to Probability Measures over Infoset-Action Space
and Vir = ΣΣ Tn (sh, an bn) is the value func- tion of (I,)) with the expectation taken over the random- ness of the product policy pair (H,)) z/) and the environment (i.e., P and r). It is known that using regret to NE conver- sion, an approximate NE can be obtained by averaging all
With sequence-fom policies, we first reformulate the IIEFG into the following bilinear game:
5 v) = =TTGV, Gv,
(3)
'The set of sequence-form form policies is defined in top-down manner and is equivalent to the "treeplex" space of policies defined a bottom-up manner (see, e.g. Lee et al. (2021)).
where matrix with
G
E
RXAXYB is the loss (((In,an), (yn, bu))
En Exnnii Pish (8k) (1 - Th (sh, an, an, bn)).
In
4

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
Algorithm OMD with Virtual Transition-eeiheee Ne- gentropy Regularization (max-plae playerr
At high level, apply the entropy regularizing technique to perturb the bilinear form of the game in Eq. (3) into strongly convex strox-yttrngly concave structure, ensuring convergence to the NE of the perturbed game (and thus the NE of the original game). This approach builds upon previous research that has explored last-iterate convergence learning in Markov games with oull-information feedback (Cen et al., 2021; Chen al., 2022; Cen et al., 2023) and with bandit feedback (Cai et al., 2023), and IIEGGs with full- dall-informatio feedback (Liu et al., 2023). In detail, we consider the following perturbed game as surrogate:
1: Input: 7)k = ka Thk = k Ek k-
2: Initialize: Mr (an [mA) ) = ... V( an) X, A. Vh E
[ Set virtual transition p" computed by Algorithm
2.
3: for ===1, 1, do
4: for h = 1, 1.... H do
5:
Observes ,, executes o / (-11f)) and receives T
6: For all (oh, an) E An A. sets entropy regularized
loss estimator as Eq. (7).
7: end for
(1, . Gv + ( ELb(1),
(4)
8:
Update policy
where vb some strongly convex regularizer used in OMD and EK serves as the knob control the strength of the entropy regularization in episode k. By gradually decreas- ing Eμ to be moderately small, the approximate NE of the perturbed game in Eq. (4) will also serve as approximate NE of the original game in Eq. (3).
1 ++1
arg min T7 (1, ) + De(u, welltt
(2)
where IT = {u E mmax planloa)) > A(k+T) V(rn, an) E Nr A, [H]]
9: end for
The crucial aspect lies in selecting an appropriate regularizer b. A natural approach leveraging the dilated negentropy (Kroer al., 2015; Kozuno el al., 2021):
Algorithm 2 Computing Virtual Transition p" (max-player)
1: Input: Game tree structure of X' x A.
2: Initialize: Sequence
representation of virtual tran- sition q RXX Array of maximized number of descen- dant infosets E R d RX For all HH in NH. set c((H) = 1.
(p)
Σ h,
Pich (I an) log
Fish (Inh 0n) ) (5)
Pish (21)
which has been widely used in existing literature studying IIEGGs (Kozuno et al., 2021; Lee et al., 2021; Liu et al., 2023; Bernasconi et al., 2024). In particular, the dilated negentropy has been used to achieve the last-iterate con- vergence in IIFGGs with full-information feedback (Lee et al., 2021; Liu et al., 2023; Bernasconi al., 2024). However, the defect of dilated negentropy is that infoset- action pairs different steps are actually coupled with each other (recall Pish (xx) Een EA Mish (æn, 0%) in Eq. (5)). In IIFGGs with bandit feedback, leveraging OMD using dilated negentropy together with the entropy regular- ization technique will deduce a stability term scaling with Ez* [ex[exp(- En.es, 2 (2n, an) log (ax))))) where ak (2x, -) Cat (uy (-1ax)) is random vector indepen- dently sampled from the categorical distribution parame- terized by μ² (-lax)) and of (Ih, an) = = az) is the sequence-form representation of zk_ As log log (an contributed by entropy regularization might be potentially very negative, this renders this upper bound of the stability term vacuous and is not sufficient to obtain a meaningful last-iterate convergence rate.?
3: for h - H to do
4: for Iy in Xr, do
5: for ag in do Compute
6:
ak)
Eenr)E((es.o)) c( 7: end for
8: Compute c(xx)= max (enkeAd(Inn.. a(
9: end for
10: end for
11: for 21 in 21 do
12: Compute Q1.1 (x1) Exjex, c(21))
c(mi))
end for
14: for h= 1 to H do
15: for The ag in X', x A do
16:
for F4+1 in C(zh, an) do
17:
Compute Q1:h+ (I1+1) =
(1ah(an)
c(x++1)
Eg (00ei100 "'
18: end for
19: end for
20: end for
21: return g.
"It should be noted that this issue cannot be resolved by merely restricting the feasible set to a subset of 1mmax. In the case of OMD with dilated negentropy. even if the feasible set is constrained as Tm {1r E Amxxx : pa(p (2x). > ] approach used in our Algorithm 1-the stability term can still reach magnitudes large as exp(O(X)), which is prohibitively large.
this manner, the learning objective is equiva-
lent to finding (n,v) such that NEGap((,,)) v) =
5

---

Learning HEFGSs with Last-iterate Convergence under Bandit Feedback
To cope with this issue, we instead consider using the negen- tropy regularizer weighted by kind of "virtual transition" 5" over the infoset-action space X' x A:
Computation Since the update of OMD is now con- strained onto subset π max of max the computation of Eq. (2) generally does not have a closed-form solution. However, we note that the approximate update of our Algorithm I still admits an efficient closed-form solution. Specifically, notice that the operation of constraining the update of OMD onto the constrained set I1 max is only for the aim of preventing the entropy regularized loss from being prohibitively large. In practice, can still compute μr" over the whole mmxx. but clip the regularized loss when it becomes undesirably large. Importantly, in Appendix A, we prove that updating μ² over the whole Mma has a closed-form solution. As shown in the experiments, clipping the loss estimator and then operating OMD in the whole Imax using this closed- form update suffices obtain an appealing performance (please see Appendix for the experiment details).
Vy (1) = Σ
1o" (In, an) log lp" u) (Ih, an). (6)
where
[p* (on, an) E probability over (1n)
Pi:a (f.n()))u1 (2), an),
PR (-I2A,, ax)
Ac(as.o)) (n)) Xn x
transition Katt, and ph. (IN+1lzy,ay) aw) representation.
is
A
x
po (x1) II
is its sequence-form (<()))) on) is not necessarily the true pu w* (1n+1 Ee p($h++|sh, on, bn (bul)(ss)) perienced by the max-player in episode k. Also, notice that the constructed virtual transition p" is well-defined by the perfect recall condition and p" is a probability measure over the infoset-action space X, x A at step h. Therefore, by incorporating the virtual transition p², we actually regularize the probability measures over X' A instead of directly regularizing the sequence-form policy u, bypassing the issue arising when dealing with the coupled (and potentially very negative) loss estimates of infoset-action pairs of dilated negentropy. For notational convenience, we drop the dependence in the subscript of ()) on p". when the context is clear for brevity.
Note that
transition probability
4.2. Virtual Transition with Maximized Minimum Visitation Probability
As elaborated in Section 4.1, our Algorithm 1 leverages virtual transition transition-weightedd negentropy regularize the loss estimator and induce the Bregman divergence D& (:.) used in OMD. The upside of employing such virtual transition p" lies in that it implicitly helps to operate the update of OMD in the space probability measures over infoset-action pairs instead of the sequence- policies, to avoid the coupling between different infoset-action pairs. However, this is still not sufficient to obtain a well-controlled stability term if additional care is not taken. Specifically, upon applying the virtual transition to weight the negentropy, the stability term associated with OMD at each infoset vi. will be enlarged by (upproximately) a multiplicative factor of (xx). This enlargement arises intuitively from the fact that, (..).) induced by &b at each Tv undergoes a downscaling, propor- tional to pf,, (3)x), thereby resulting in relative increase in the stability term. Therefore, to ensure that the stability term is well-controlled, we design the following p" which maximizes the minimum "visitation probability" of all my in its sequence-fore representation:
With regularizer vb specified, the derivative of Su(u,, v) @fe(p..)
w.r.t. (( an) is (jLa(Zn.a))) = [Gv) (mn, ax) + Ek Pish (zx) (log [p" 14] (Ih, ax) + +1) Since |p" E I Ax,x for any μe, the constant in the above dis- play does not affect the optimization of OMD. Besides, with bandit feedback,
(optimistically biased) loss esti- (1) ) (1 rf)) of (Gv) (zn, az.) in episode k constructed (Kozuno et al., 2021), where 7k > is the im- plicit exploration parameter (Neu, 2015) and uf (z%, a I { [Ir,. ax) = at))- This specifies the final entropy regularized loss estimator as follows (Line l):
mate
T (Th, ard Hi (2h, an) + 7/k
pd = arg max min 9EPx he(M (In),
(8)
C (T), an) =
(1-r%) r
+ piun (IN) log [p* w*1 (In, an). (7)
where FP denotes the set of all the valid virtual transitions over infoset-action space. The solution to Eq. (8) can be computed efficiently via backward dynamic programming, as shown in Algorithm 2.
With the constructed loss estimator, Algorithm then uses OMD to update policy. Since now the entropy regularized loss estimator is considered, the variance of the loss estima- tor scales with log [p*14] /i] (IA, a4)) and will be prohibitively large if running OMD on the entire mmxx. eventually lead- ing to an unbounded stability term of OMD. Hence we constrain the feasible set of the OMD as a subset I of Imxxx where each μ E lht satisfies u(an (Tn) is lower bounded for all (Ia, 0n) E Xr x A and h E [H] (Line 1).
Note that similar ideas leveraging negentropy weighted by the transition over infoset-action space have also been ex- ploited by Bai et al. (2022); Fiegel et al. (2023). How- ever, we would like to underscore that the design of our virtual transition p" over infoset-action space is different from those of Bai et al. (2022); Fiegel et al. (2023). In detail, our virtual transition p" (I 1 (ah, an) is defined based on
6

---

Learning HEFGSs with Last-iterate Convergence under Bandit Feedback
some fixed action d1+1 E A that maximizes the number of reachable infosets |Ch (2h+11, 01+1)l Xn. This ap- proach contrasts with the "balanced transitions" introduced by Bai et al. (2022) and Fiegel et al. (2023), which either consider all reachable infosets in a specific layer Xr for some h/ 2/ h + I, the entire sub-tree, or compute transitions as the sum of reachable infosets across all possible actions ah+1 E AA at infoset Th+1- Further, we aim to establish the last-iterate convergence of IIEFGs while they can only guarantee the average-iterate convergence, necessitating dif- ferent theoretical analysis.
perimental results to Appendix I due to space limit.
5. Analysis
In Section 5.1, we first present the upper bound of the last- iterate convergence rate of our Algorithm 1. Then in Sec- tion 5.2, we provide the lower bound for learning IEFGss with bandit feedback and last-iterate convergence guarantee.
5.1. Upper Bound of Last-iterate Convergence
Theorem 5.1. If Algorithm I is adopted by both players, by setting On = 8/8, aty = 3/8 and 0g = 1/8, for any k 2 1, with probability at least 1 - O it holds that
On the Requirement of Knowing Game Tree Structure The construction of our virtual transition by Algorithm 2 requires the game tree structure to be known priori, which is also required by some algorithms learning IIFGGs with average-iterate convergence (Bai et al., 2022; Fiegel et al., 2023). While there are algorithms with average-iteree iterate con- vergence that do not need prior knowledge of the tree struc- ture (e.g., Kozuno et al. (2021)), we note the game tree structure can be extracted from one traversal on the game tree in ((XA) time. Therefore. this requirement is mild on game instances with moderately large X and A (Bai et al., 2022). Whereas, we also remark that there exist some game instances with exponentially large X (e.g., no-limit Texas hold' em (Johanson, 2013)), making one traversal on the game tree impractical. In such cases, the polynomial dependence on X of the convergence rate lower bound (see Section 5.2) indicates that it is also statistically intractable to learn such game instances if no function approximation assumptions are further imposed. Besides, in cases of un- known game tree structure, we show that using vanilla ne- gentropy is also able to achieve the last-iterate convergence in IIEFGs (see Remark 5.4 and Appendix for details). This approach no longer requires knowledge of the game tree structure. Nevertheless, the downside of using OMI) with vanilla negentropy is that it does not admit closed-form update (Hoda et al., 2010), even though the update of OMD is performed on the whole Immax. since it does not adapt to the game tree structure.
NEGap(u ,²)
=ō ( F + (XA+ HK-
+ +(X21+ Y²B) à k (x + Y) Hk $1 (X (x+r))
Remark
5.2. When max max (X*A-Y2B) /X///XXX (XA+Y "7 /XxX)) 1 /(++)))))/X+))))//)/)))))))))))+
k
we have NEGap(u* v²) (((X*+)](XX+XX) (X + -YYWH HV.). Besides, when only obtaining an expected last-iterate convergence rate is desired, our Algorithu 1 has an improved last-iterate convergence rate of Ō((X + Y)](X² + + + (X + +Y) in expectation (see Appendix E for details).
Remark 5.3. Though the last-iteran convergence rute of our Algorithmm 1 is inferior to the ((1/k) convergence rate by Lee et al. (2021); Liu et al. (2023), we note that both their algorithms can only work in the full-information setting. Further, we remark that the algorithm of Lee et al. (202 I) needs the assumption that the NE of the IIEFG considered is unique. Though such an assumption is not required by Liu et al. (2023), the algorithm of Liu et al. (2023) requires both players to be controlled by central controller, and thus their algorithm is not uncoupled. In contrast, our algorithm can work in the bandit feedback setting, is fully uncoupled between the two players, and can still guarantee a regret of order Ö(k/s) even when the opponent of the max-player is an adversary. Moreover, Section 5.2 shows that the lower bound of the convergence rate for learning IIEFGs with bandit feedback, last-iteran convergence guarantee, and uncoupled algorithms will be of order (2)) (for large enough k).
Experiments As aforementioned, our Algorithm I ad- mits an efficient approximate policy update. We conduct empirical evaluations on various IIFG game instances, in- cluding Lewis Signaling, Kuhn Poker (Kuhn, 1950), Ledue Poker (Southey et al., 2012), and Liars Dice. The empir- ical evaluations show that when Algorithm 1 is equipped with the virtual transition computed by Algorithm 2, it can perform relatively well across all game instances. Though there might be some baseline that performs similarly to our algorithm on some game instances, this baseline algorithm might not be able to converge fast on other game instances, as the last-iterate convergences of all the baseline algorithms are not theoretically guaranteed. We defer the detailed ex-
Remark 5.4. In Appendix F. we demonstrate that employing vanilla negentropy v((u) Enzn,a Mua(In, an) log p1st (1h,, an) also achieves last-iterate convergence rate of NEGap(u" ,1²) Ō((X A + B)) Compared with Theorem 5.1, when X and A are sufficiently large, this rate is superior by a factor of ((vX) but worse by Ö(H / A). When H is sufficiently large, it is superior by a factor of O(X)))
7

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
but worse by ((A). However, we emphasize again that in IEFGGs using OMD with vanilla negentropy does not permit efficient closed-form update, even though OMD operates on the entire Imax. as opposed to the virtual munsitiionweiightd negentropy.
Whlli 2
(x2A xx2A+V2 B)
wkws
(II)
Term 5
Term
where w/ = II ---- (1 - 7)8z) is the contraction coeffi- cient. Intuitively, Term 1 and Term 2 represent the underes- timation and overestimation errors of the loss estimator, re- spectively. Term 3 through Term 5 arise from bounding the stability term of OMD. Additionally, Term 6 is due to the variation of fR (and hence 5***) in each episode. Then we bound each of the above terms in by Lemma C.3 - Lemma C.8 in Appendix C.2.
Proof Sketch of Theorem 5.1 We postpone the complete proof of Theorem 5.1 to Appendix C. Here we provide proof sketch of it.
We denote by = (bit) the unique NE in the regularized game fs in Eq. (4) (there is only unique NE due to the strongly convex-strongly concave nature of fi). To begin with, one can see that the NE policy profile gli* of fi is also an approximate NE of the original game in Eq.
Finally, the proof can be concluded by substituting Eq. (11) and the upper bound of NEGap(g**)) into Eq. (9).
(3). This enables bound NEGap( ((*) using NEGap(e***))
together with the distance between &* and gki** weighted by the virtual transitions as bellow:
Remark 5.5. Our analysis scheme is inspired by Cai et al. (2023) to bound the last-iterate convergence of learning matrix games with bandit feedback. However, we also re- mark that a straightorwwar application of their analysis will not address our problem of learning IIEFGs with bandit feedback, since we leverage a different regularizer and a new virtual transition p" computed by Algorithm 2. This serves as core ingredient of the analysis when deriving the contraction in Eq. (10) and when bounding Term 6-nn of the leading term in the final bound of the convergence rute. Besides, compared with the analysis of Cai et al. (2023), the additional Term 5 in Eq. (1I) comes from the fact that we establish a refined analysis in the case of IIEFGs to farther sharpen the dependence of the final convergence rate.
NEGap(E") & NEGap(("'*)
+ +x|le I1pe
1l, + 1|0" (u+ - -I
where NEGap(5***) can be controlled by Lemma C.I. Due to the constructed virtual transition pz and p", the second and the third term in Eq. (9) are the -nnrrmm of the difference between the probability measures over infoset-action spaces, which thus turn out to be bounded by O( O(VKL "0""x"",,=""""> p²)(()) and O O(VKL KL (p"p""*, ))r=)) by Pinsker's inequality. Also, due to the constructed vir- tual transition- negentropy 1h one can deduce that KL. (p*) pp" v²* = D& (n ,1²²) (and similarly on the min-player side).
X and A (as well as Y and B)
To bound the Bregman divergence (u ,,²",, we show that in each episode k, the product policy 5* == (n² u²) generated by the algorithm will approach ek. close enough by proving that (gk ,5h) is an (approximate) contrac- tion mapping. In particular, we have
5.2. Lower Bound of Last-iterate Convergence
By leveraging existing regret lower bounds for learning in IIEFGs with bandit feedback (c.g., Theorem 6 of Bai et al. (2022) and Theorem 3.1 of Fiegel et al. (2023)), one can directly obtain lower bound for learning IIEFGs that guarantees last-iterate convergence under bandit feedback. For completeness, we formalize this result as the following theorem.
Do (gh+ ,*+,,++ 1 - (1 Then) D& (s*h*,5*) + Y) Tk + 2/2 A YY3B)
+ TkPk + Tk + क 2 2 (XA + YB) + wy-
(10)
Theorem 5.6. For any algorithm Alg that both players adopt generate policy profile (1tt vv²) and is uncoupled between both players, there exists an IIFFG instance such that the lower bound of the last-iterate convergence of learning this IEFG in the bendit-feedbuck setting satis- fies NEGap(μe 1²) = Q(VXA+A+++ Bk Bk-))), when k 2 max (X (XAYB))
Please see Appendix C.2 for the detailed definitions of Tk
Pk: as and Wk-
Expanding the above recursion, Du ((6ttli,ghh+ as
we can bound
k
k
De (ghttlinght sk+l)
w TiP: +
w w nio
Remark 5.7. Compared with the lower bound of the con- vergence rate above, the upper bound in Theorem 5.1 is loose by factor of Ō((X + Y))k//s) (for large enough X, Y, A and B). We believe one of the promising approaches to improve the upper bound of the convergence rate might be using the optimistic OMD/FTRL, which utilizes accel- erated techniques from the optimization perspective and
Term
Term
k
+ +(XA+YB) Σ wh (m (X
w whn m
Term 3
Term 4
8

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
typically used achieve the Ol1/k) convergence rate for learning IEFGGs with last-iterate convergence in the full- information setting. One of the main difficulties of using op- timistic OMD/FTRL in conjunction with the regularization technique to achieve a faster convergence rate in the bandit feedback setting is that the loss estimator constructed in the bandit feedback setting (either unbiased or optimistically biased) would have undesirably large variance, rendering the stability of optimistic OMD/FTRL hard to be controlled even in the special case of learning matrix games. We leave the possible improvement of our convergence upper bound as our future study.
Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, vol- ume 206 of Proceedings of Machine Learning Research, pp. 7999-998998 8028. PMLR, 2023.
Abe, K., Ariu, K., Sakamoto, M., and Iwasaki, A. Adap- tively perturbed mirror descent for learning in games. In Forty-first International Conference on Machine Learn- ing, ICML 2024, Vienna, Austria, July 21-27, 2024, 2024.
Abe, K., Sakamoto, M., Ariu, K., and Iwasaki, A. Boosting perturbed gradient ascent for last-iterate convergence in games. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
6. Conclustion
In this work, we take the first step toward developing an algo- rithm that learns an approximate NE of IEFGSs in the bandit feedback setting with fimite-tima last-iterate convergence. Our algorithm operates in an entirely uncoupled manner be- tween the two players involved, requiring no coordination, communication, or shared randomness. We prove that our algorithm achieves last-iterate convergence with a rate of Vlk with high probability, and rate of Okk-Vo) in expectation. Furthermore, empirical evaluations on various IIFGG instances show the comparative advantage of our algorithm over baseline methods. A noteworthy open prob- lem is closing the gap between the established upper and lower bounds for convergence, which remains unresolved even for the special case of learning matrix games with last-iterate convergence guarantee in the bandit feedback setting. We leave the investigation of this for our future research endeavors.
Bai, Y. and Jin, C. Provable self-play algorithms for compet- itive reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Pro- ceedings of Machine Learning Research, pp. 551-560. PMLR, 2020.
Bai, Y., Jin, C., and Yu, T. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-211 2020.
Bai, Y., Jin, C., Mei, S., and Yu, T. Near-optimal learning of extensive-form games with imperfect information. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, vol- ume 162 of Proceedings of Machine Learning Research, pp. 1337-1382. PMLR, 2022.
Bernasconi, M., Marchesi. A., and Trovò, F. Learning extensive-form perfect equilibria in two-player zero-sum sequential games. In International Conference on Artifi- cial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain, volume 238 of Proceedings of Machine Learning Research, pp. 2152-2160. PMLR, 2024.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Bravo, M., Leslie, D., and Mertikopoulos, P. Bandit learning in concave n-person games. Advances in Neural Informa- tion Processing Systems, 31, 2018.
Acknowledgements
The corresponding author Shuai Li partly supported by the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B121 1111112200000 (001). Baoxiang Wang is partially supported by the National Natu- ral Science Foundation of China (72394361, 62106213) and an extended support project from the Shenzhen Science and Technology Program.
Brown, N. and Sandholm, T. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(677))441-4444 2018.
Burch, N., Moraveik, M., and Schmid, M. Revisiting CFR+ and alternating updates. J. Artif. Intell. Res., 09:429-443, 2019.
Cai, Y. and Zheng, W. Doubly optimal no-regret learning in monotone games. In International Conference on Ma- chine Learning, ICML N0M3, 23-29 July 2023, Honolulu, Hawaii USA, volume 202 of Proceedings of Machine Learning Research, pp. 3507-3524. PMLR, 2023.
References
Abe, K., Ariu, K., Sakamoto, M., Toyoshima, K., and Iwasaki, A. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. In International

---

Learning IEFGSs with Last-iterate Convergence under Bandit Feedback
Cai, Y., Oikonomou, A., and Zheng, W. Finite-time last- iterate convergence for learning in multi-player games. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
games. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3403-3408. IEEE, 2022.
Fan, J., Wang, Z., Xie, Y., and Yang, Z. A theoretical analysis of deep q-learning. In Proceedings of the 2nd Annual Conference on Learning for Dynamics and Con- trol, L4DC 2020, Online Event, Berkeley, CA, USA, 11-12 June 2020, volume 120 of Proceedings of Machine Learn- ing Research, pp. 486-489 PMLR, 2020.
Cai, Y., Luo. H., Wei, C.,, and Zheng, W. Uncoupled and con- vergent learning in two- plopplyye zero-sum markov games with bandit feedback. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural In- formation Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10- 16, 2023, 2023.
Farina, G. and Sandholm, T. Model-free online learning in unknown sequential decision making problems and games. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on In- novative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Ar- tificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 5381-5390. AAAI Press, 2021.
Cen, S., Wei, Y., and Chi, Y. Fast policy extragradient meth- ods for competitive games with entropy regularization. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Process- ing Systems 2021, NeurlPS 2021, December 6- 2021, virtual, pp. 27952-27964, 2021.
Farina, G., Kroer, C., and Sandholm, T. Stochastic regret minimization in extensive-form games. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3018- 3028. PMLR, 2020.
Cen, S., Chi, Y., Du, S. S., and Xiao, L. Faster last-iterate convergence of policy optimization in zero-sum markov games. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Farina, G., Schmucker, R., and Sandholm, T. Bandit linear optimization for sequential decision making and extensive-fome games. In Thirty-Fifh AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Con- ference on Innovative Applications of Artificial Intelli- gence, IAAI 2021, The Eleventh Symposium on Educa- tional Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 5372-5380. AAAI Press, 2021.
Chen, Z., Ma, S., and Zhou, Sample efficient stochas- tic policy extragradient algorithm for zero-sum markov game. In International Conference on Learning Repre- sentation, 2022.
Chen, Z., Zhang, K., Mazumdar, E., Ozdaglar, A. E., and Wierman, A. finite-sample analysis of payoff- -aaeed independent learning in zero-sum stochastic games. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.
Feng, Y., Fu, H., Hu, Q., Li, P., Panageas, I., Peng, B., and Wang, X. On the last-iterate convergence in time- varying zero-sum games: Extra gradient succeeds where optimism fails. In Advances in Neural Information Pro- cessing Systems 36: Annual Conference on Neural In- formation Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16. 2023, 2023.
Cui, Q. and Yang, L. F. Minimax sample complexity for turn-based stochastic game. In Proceedings of the Thirty- Seventh Conference on Uncertainty in Artificial Intelli- gence, UAI 2021, Virtual Event, 27-30 July 2021, volume 161 of Proceedings of Machine Learning Research, pp. 1496-1504. AUAI Press, 2021.
Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Adapting to game trees in zero-sum imperfect information games. In International Confer- ence on Machine Learning, ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 10093-10135. PMLR, 2023.
Cui, Q., Zhang, K., and Du, S. S. Breaking the curse of mul- tiagents in large state space: RL in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pp. 2651- 2652. PMLR. 2023.
Fu, H. Liu, W., Wu, S., Wang, Y., Yang, T., Li, K., Xing, J., Li, B., Ma, B., Fu, Q., and Yang, W. Actor-critic policy optimization in a large-scale imperfect-infrmmatie information game. In The Tenth International Conference on Learning
Drusvyatskiy, D., Fazel, M., and Ratliff, L. J. Improved rates for derivative free gradient play in strongly monotone
10

---

Learning HEFGS with Last-iterate Convergence under Bandit Feedback
Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Johanson, M. Measuring the size of large no-limit poker games. CoRR, abs/1302.7008, 2013.
Golowich, N., Pattathil, S., and Daskalakis, C. Tight last- iterate convergence rates for no-regret learning in multi- player games. In Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Infor- mation Processing Systems 2020, NeurIPS 2020, Decem- ber 6-12, 2020, virtual, 2020.
Johanson, M., Bard, N., Lanctot, M., Gibson, R. G., and Bowling, M. Efficient nash equilibrium approximation through monte carlo counterfactual regret minimization. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 20/2, Valencia, Spain, June 4-8, 2012 (3 Volumes), pp. 837-846. IFAAMAS, 2012.
Gorbunov, E., Taylor, A. B., and Gidel, G. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Jordan, M., Lin, T., and Zhou, Z. Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback. Operations Research, 2024.
Koller, D. and Megiddo, N. The complexity of tro-ttoooo zero-sum games in extensive form. Games and economic behavior, 4(4):528-55) 552, 1992.
Greenwald, A. and Hall, K. Correlated q-learning. In Machine Learning. Proceedings of the Twentieth Inter- national Conference (ICMI. 2003), August 21-24, 2003, Washington, DC, USA, pp. 242-249. AAAI Press, 2003.
Koller, D., Megiddo, N., and Von Stengel, B. Efficient computation of equilibria for extensive two-person games. Games and economic behavior, 14(2)2247-299 1996.
Kozuno, T., Ménard, P., Munos, R., and Valko, M. Learn- ing in two-player zero-sum partially observable markov games with perfect recall. In Advances in Neural Infor- mation Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 11987-11998. 2021.
Hansen, T. D., Miltersen, P. B., and Zwick, U. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. J. ACM, 60(1):1:1-::16, 2013.
Heinrich, J., Lanetot, M., and Silver, D. Fictitious self -lly-pla in extensive-form games. In Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 805-813. JMLR.org, 2015.
Kroer, C., Waugh, K., Kiling-Karzan, F., and Sandholm, T. Faster first-order methods for extensive-form game solving. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, pp. 817-834. ACM, 2015.
Hoda, S., Gilpin, A., Peña, J., and Sandholm. T. Smoothing Techniques for Computing Nash Equilibria of Sequential Games. Mathematics of Operations Research, 2010.
Kroer, C., Farina, G., and Sandholm, T. Solving large sequential games with the excessive gap technique. In Ad- vances in Neural Information Processing Systems 31: An- nual Conference on Neural Information Processing Sys- lems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 872 882, 2018
Hsieh, Y., lutzeler, F., Malick, J., and Mertikopoulos, P. On the convergence of single-call stochastic extra-gradient methods. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 6936-6946 2019.
Kuhn, H. Extensive games and the problem of information. Contributions to the Theory of Games, (24):193, 1953.
Kuhn, H. W. Extensive games. Proceedings of the National Academy of Sciences, 36(10):570-576, 1950.
Hu, J. and Wellman, M. P. Nash q-learning for general-sum stochastic games. J. Mach. Learn. Res., 4: 1:109,-1069, 2003.
Kurita, M. and Hoki, K. Method for constructing artificial
intelligence player with abstractions to markov decision processes in multiplayer game of mahjong. IEEE Trans. Games, 13(1)999-110, 2021.
Huang, Y. and Hu, J. Zeroth-order learning in continu- ous games via residual pscudogradient estimates. arXiv preprint arXiv:2301.0223
2023.
Lanctot, M., Waugh, K., Zinkevich, M., and Bowling, M. H. Monte carlo sampling for regret minimization in exten- sive games. In Advances in Neural Information Pro- cessing Systems 22: 23rd Annual Conference on Neural
Jia, Z., Yang, L. F,, and Wang, M. Feature-based q-learning for two two-player stochastic games. CoRR, lbbs/1906000423, 2019.

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pp. 1078-1086. Curran Associates, Inc., 2009.
Liu, Q. Yu, T., Bai, Y., and Jin, C. A sharp analysis of model-based reinforcement learning with self-play. In Proceedings of the 38th International Conference Ma- chine Learning. ICML 2021. 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 7001-7010, PMLR, 2021.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F,, Tuyls, K., Omidshafiei, S., et al. Openspiel: A frame- work for reinforcement learning in games. arXiv preprint arXiv: 09453, 2019.
Liu, W., Jiang, H., Li, B., and Li, H. Equivalence analysis between counterfactual regret minimization and online mirror descent. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Mary- land, USA, volume 162 of Proceedings of Machine Learn- ing Research, pp. 13717-13745. PMLR, 2022.
Lee, C., Kroer, C., and Luo, Last-iterate convergence in extensive-form games. In Advances in Neural Infor- mation Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual. pp. 14293-14332 2021.
Mokhtari, A., Ozdaglar, A. E., and Pattathil, S. Convergence rate of o(1/k) for optimistic gradient and extragradient methods smooth convex-concave saddle point prob- lems. SIAM J. Optim., 30(4):3200-3555 2020.
Li, G., Chi, Y. Wei, Y., and Chen, Y. Minimax-optimal multi-agent RL in markov games with a generative model. In NewrlPS, 2022.
Moravčík, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowl- ing. M. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):008-55) 511-5,,, 2017.
Li, J., Koyamada, S., Ye, Q., Liu, G., Wang, C., Yang, R., Zhao, L., Qin, T., Liu, T., and Hon, H. Suphx: Master- ing mahjong with deep reinforcement learning. CoRR, abs/2003. 1at/2003..1590, 2020.
Munos, R., Pérolat, J., Lespiau, J., Rowland, M., Vylder, B. D., Lanctot, M., Timbers, F., Hennes, D., Omidshafici, S., Gruslys, A., Azar, M. G., Lockhart, E., and Tuyls, Fast computation of nash equilibria in imperfect infor- mation games. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 7119-7129. PMLR, 2020.
Lin, T. Zhou, Z., Mertikopoulos, P., and Jordan, M. I. Finite- time last-iterate convergence for multi-agent learning in games. In Proceedings of the 37th International Confer- ence on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp.
PMLR, 2020.
Lin, T., Zhou, Z., Ba, W., and Zhang, Doubly optimal no-regret online learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:2112.02856. 2021.
Nash Jr, J. F. Equilibrium points in n- n-person games. Pro- ceedings of the national academy of sciences, 36(1):48- 49, 1950.
Littman, M. L. Friend-or-foe q-learning in general-sum games. In Proceedings of the Eighteenth International Conference on Machine Learning (ICML ), Williams College, Williamstonn, MA, USA, June 28- July 1, 2001, pp. 322-328. Morgan Kaufmann, 2001.
Neu, G. Explore no more: Improved high-prohability re- gret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems 28: Annual Con- ference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 3168-3176, 2015.
Littman, M. L. and Szepesvári, C. A generalized ceinorreeent-leamming model: Convergence and appli- cations. In Machine Learning, Proceedings of the Thir- teenth International Conference (ICML '96), Bari, Italy, July 3-6, 1996, pp. 310-318. Morgan Kaufmann, 1996.
Pérolat, J., Scherrer, B., Piot, B., and Pietquin, O. Approx- imate dynamic programming for two-player zero-sum markov games. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1321-1329. JMLR.org, 2015.
Liu, M., Ozdaglar, A. E., Yu, T., and Zhang, K. The power of regularization in solving extensive-form games. In The Eleventh International Conference on Learning Repre- sentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Schmid, M., Burch, N., Lanctot, M., Moravcik, M., Kadlec, R., and Bowling, M. Variance reduction in monte carlo
12

---

Learning IIFGGs with Last-iterate Convergence under Bandit Feedback
counterfactual regret minimization (VR-MCCFR) for ex- tensive form games using baselines. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intel- ligence Conference, IAAI 2019, The Ninth AAAI Sympo- sium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- Febru- ary 1, 2019, pp. 2157-2164. AAAI Press, 2019.
2021, Boulder, Colorado, USA, volume 134 of Proceed- ings of Machine Learning Research, pp. PMLR, 2021a.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Last- iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on learning theory, pp. 4259-4299 PMLR, 2021b.
Schmid, M., Moraveik, M., Burch, N., Kadlec, R., David- son, J., Waugh, K., Bard, N., Timbers, F., Lanctot, M., Holland, Z.., Davoodi, E.,, Christianson, A., and Bowling, M. Player of games. CoRR, abs/21 12.03178, 2021.
Xiong, W., Zhong, H., Shi, C., Shen, C., and Zhang, T. A self-play posterior sampling algorithm for zero-sum markov games. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Mary- land, USA, volume 162 of Proceedings of Machine Learn- ing Research, pp. 24492-2444444 24523. PMLR, 2022.
Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. Near- optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp- 5192-5202, 2018.
Zeng, S., Doan, T. T., and Romberg, J. Regularized gradient zero-ssu
descent ascent for two-player zero-sum markov games. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Song. Z., Mei, S., and Bai, Y. When can we learn general- sum markov games with a large number of players sample-efficiently In The Tenth International Confer- ence Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.nect 2022.
Zhang, Z., Zhou, Y., and Ji, X. Model-free reinforcement learning: from clipped pseudo-regret to sample complex- ity. In Proceedings of the 38th International Confer- ence on Machine Learning, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12653-12661 PMLR, 2021.
2021, 18-24 July 2021,
Southey, F., Bowling, M. P., Larson, B., Piccione, C.,, Burch, N., Billings, D., and Rayner, C. Bayes' blufff: Opponent modelling in poker. arXiv preprint arXiv: 100.:1207.111 2012.
Zhou, D., Gu, Q., and Szepesvári, C. Nearly minimax op- timal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, COLT 1021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Re- search, pp. 4532-4576. PMLR, 2021.
Tammelin, O. Solving large imperfect information games using CFR+. CoRR, abs/1447.5544., 2014.
Tian, Y., Gong, Q.. and Jiang, Y. Joint policy search for multi-agent collaboration with imperfect information. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, vir- tual, 2020.
Zinkevich, M.. Johanson, M., Bowling, M. H., and Pic- cione, C. Regret minimization in games with incomplete information. In Advances in Neural Information Process- ing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pp. 1729-1736. Curran Associates, Inc., 2007.
Von Stengel, B. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-25 246, 1996.
Wang, Y. Liu, Q., Bai, Y., and Jin, C. Breaking the curse of agent RL with function approximation. In The Thirty Sixth An- nual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pp. 2793-2848. PMLR, 2023.
multiagency: Provably efficient decentralized
Wei, C., Lec, C., Zhang, M., and Luo, H. Last-iterate conver- gence of decentralized optimistic gradient descent/ascent in infinite- horizonn competitive markov games. In Con- ference on Learning Theory, COLT 2021, 15-19 August
13

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
A. Computation
As mentioned in Section 4.2, in practice, suffices to consider the following relaxed optimization problem of Eq. (2), which performs the update of OMD over mmx instead of II
arg min The M,, (*) D
(12)
wellmar
Then, to prevent the loss estimates contributed by the entropy regularization from being prohibitively large, it only remains clip the part of the entropy regularization:
rk+1 ( an3 (1 h + Ex+1 Pish (zx) log (max {[0" [p" (I an),
(an, (x),aR) Tk+1 h
t/ (2), an. + 11kk
(13)
1+1 M1th
where gx+1 0 is the clipping threshold.
To update the policy in Eq. (12), from the proof of Proposition F.2 of Fiegel et al. (2023), one can see that the virtual transition- weighted negentropy up (11) = aa [p"14 (2h, ax) log (Ip")) 14] (#r, an)) is equivalent to the following special dilated
negentropy:
Mish an) log
(iss (Irns an)
(k) = Σ
Σ
[p" (cih, an) log (xn))
(14)
Kik (x()
1iih (Irh)
R, an
where
Hy (x() = TT/(/HHHH-H - h ()p.).)))
(15)
Since the second term in Eg (14) is linear term in the virtual transition trnsition-wwigghed negentropy z and this special dilated negentropy /// will induce the same Bregman divergence. Hence, ++1 computed Eq. (12) is the same as computed by the following:
k+1 arg min Ti (n,, PT) Day (²,
(16)
peTTmax
We conclude the discussion here by demonstrating Algorithm 3, which provides a closed-fome update of Eq. (16). The correctness of Algorithm is guaranteed in Proposition A.
Algorithm 3 Closed-form Solution of Eq. (16)
1: Input: Tree-like structure of X' A, fixed learning rates v,, virtual transition pd and clipped loss estimator P
2: Initialization: For all HH in Xg, initialize z* (I#++) = 1. Set adaptive learning rates K& according to Eq. (15).
3: for = H do
4: for Ta in Xr do
5: Compute (ML, an) -KA
an) EEntrEClena (z(en) log 7 Zh+1 (2x+1). (alaa11)
6: Compute 7.( = Eased M1) (mn) exp (Jh: (1n, an)).
7: for ap. in A do
Je+1 k+1 (an (rA) = 14 (an (xn) exp (J,,, an) - log Z (zn)) 8: Compute f
9: end for
end for
11: end for
Proposition A.1. The solution to the update in Eq. (16) satisfies
(a(2))
11 (ap, (nn) (aal)))))
-K (xx(
an)+
Σ
log llog (2r))
(x(0)42)
14

---

Learning IEFGG with Last-iterate Convergence under Bandit Feedback
where
{ K4 (E ab+1 (C(aE
(g(an) log Zh+ Ziti(ontt) J. Kik (x(2)+11
(Ia)
E
u (a)) exp
E
(17)
and for notational convenience, define that ((HHaH)) Au A, has unique descendant TH+1 such that Z 11 (1 =1
Proof. First note that
(ur2t) De
Σ
Σ
1 log (an Mish (T and 2h (I and + (x( p (an (mh)
h= (an ann (ana,annedaa XEA
(watteand Ch. (In..)) KL (-1=))) (-h(((20)))
Σ
(18)
kx(
Am Jy EX,
We now prove the proposition via backward induction over h H H........
When h = H, for any XH. Eq. (18) shows that
1+1 (aHlжH) = p (a exp KA (In) (TH, (I - llog 2 (
HH
where Lff (xH) = Eoges (a (mH) exp (wn 2 (HH, aH)} is normalization factor.
Fix some h E [H). Now suppose the induction hypothesis holds from step + 1 to and consider the h-th step. Using the induction hypothesis,
that Eq. (18) can be rewritten
Σ
"1
Σ
Made (aw and
May Ma (an (ars)) uby (an (ar).) (pn (-aw)) The (aw):)) KL (par(-12w)) pui (-(a))))
( (wwr,aw) 16
log
1= (Tee aa .X
Pi: 11:
EXW
(an The (aw..)) +
KL (pw Ho (-1xw)) (oo(an))
ENN
H
(IN(()
Misk ( log (xW))
log (x -
Σ
xx(2N(42)
ni (x(ww))
W=i+1
Σ
Σ
M1:h 11:M-1(001) (20wr)
(mnc Prr (xw,))) +
KL (- uK (-1xw))
Kyy (xW))
W= WEE,
(1n(1)+11) (x(xnt1)
Σ
log 2hit1 (20+1)
Bht Extt
h-1
(mm((een))) Pbr (aw +
KL (aw uh (- (-1aw))) KK((NN)
Σ
Σ
(
W W=IZNEKY
log 2h (xn+1) 1ik (2(41)1)
KL (Hu (-1ax)) ) u (-122)) Ke (x(
Σ (15h
nn (a(()oo), (xn.
Σ
J4 E
#A41EO(#AN)
15

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
By minimizing (9), one can derive that
1h +++1 (an = 14 (an) exp { - (2 an)+ +
(a(wn) (x(+111)
Σ
log T (In+1) - -log 2%% (20k)
2N+1EC(EN,a))
where
{ (
k((In) Ri (x(+1)
log Zh+1 (wnnta) j.
(TN)
E
u (an) exp exp
E
aLEA
Eht1 on)
The proof is thus concluded.
B. More Discussions on Virtual Transition Probabilities
B.1. Illustration the Failure of Using Uniform Virtual Transition
In this section, demonstrate why uniform virtual transition is insufficient for achieving meaningful last-iterate convergence rates.
Consider an IIEGG instance where there is only one action and H = 4. Each infoset z in the game tree of this instance satisfies [C(rr, a)l = 2 except for infoset 22,1, which is such that [C(22,1, a) = n with some n 2 2. Now, suppose the uniform distribution p is used as a virtual transition over infosct-action spaces. Then for all the descendants { 12n on +. while there are only X = 9 3n infosets total.
step of infoset 1 . one can see that PI (#H)) = when n
Thus, will happen that P1.H' (z
Actually, one easily construct IIEGG instance such that min (xH) 0 (n and X O with as parameter that depends m but not n for uniform virtual transition p. Therefore, when using uniform distribution as virtual transition, , 1/P1.H (IH) might be prohibitively large and lead to convergence rate with much worse dependence on X than the virtual transition constructed in our Algorithm 2.
B.2. Balanced Effects of the Proposed Virtual Transition Probability
Lemma B.1. For any E [H] and In E Xh, the constructed virtual transition p" guarantees that 1/P4 (mn) S X.
Proof. Clearly, (-) is minimzed at h = H for some E Xz by the definition of virtual transition. By the construction of (.)...) in Algorithm 2, one can deduce that VaH E Xn, it holds that (understanding {(T,, (icn,,)))ve(H11 as the unique trajectory leading to dH below)
PI. (xH) q(zH]
c c(en]
-q (
Σ E0( [T'
c c[2H-1]
c [[H]]
=q
Σ En' (cH_,EC(en-22nmn-1)
C [HH-11
o/ cC(an-1,an--) [2'(1]
c c[xH-11]
[
-9(
Σn F E00__60(e
I' H-
[0 1,
(9)
c[zH-1]
c [ c[x=-1]
2 9 96
Ech_,,Clew-non--))
c[TH]
-
End 20m 2an 2) [4'r-1]
c c(xH]]
2
ExTex, ex, c|a1]
16

---

Learning IIEGGs with Last-iterate Convergence under Bandit Feedback
c [
X
[
X
X
where (f). and :[ :] are defined in our Algorithm 2; and (i) is due to c[ru-1] = max A d[ 2 d an 1
The property shown in this lemma of our constructed virtual transition pf serves as a key ingredient in the analysis (say, when bounding our Term 4 as well as Term 6 and when establishing the final convergence upper bound of the NE gap in the proof of Theorem 5.1) as we shall see.
C. Proof of Theorem 5.1
Proof of Theorem 5.1. Throughout the proof, since Theorem 5.1 holds for all k as fixed constants, we assume k 2 ko (i-an-o 1- (n4)) In what follows, we denote by mi minh, 1p²(x²) (x), an) and
24 In
12
I-a, aa
mg mi bn. [ (yn, bn).
First, notice that NEGap(Ex) can be translated into the summation of NEGap(5***) and the distance of gh to ghit as follows:
NEGap (5*)
f (pt v)) f f (1,
sup WEll
f (p/itt,)) f f (1iit,,) + f () - (1. + (p. - f (pr
sup rEllan
NEGap (Eh:²) + (1* - p/an) T Gv + H (
sup pellmae.eellmm
NEGap (5hht) + (10 (1* - - ,u//"") + (p" - (u*--wing G n//"))
sup "Ellm
NEGap (ch+*) + 1110 (n* - ( + 11t101(( -vtr) G n/
sup vellmax.eEll.
1 NEGap (cth*) + X 1122 (1²² - -nhit)) 11, + Y 110" (u* ( -
(
(AHH
+ YBH
sall (In(XA) + I)) 0
+ x v KK y Dr )b) + Y v KL ykit pe vb)
b
XAM
YBH
< SeaH (In(X) + In O
+
+ +(X Y) KF 17' w+) + KL (po wkin pp vb)
k
k.
(ir)
XAH
YBH
+(X Y) (pEEkit ( xEt))
S sill
+
k
k
2 H (In(XA) + I) +
XAH YBH k
+x +Xx+ Dey (Ekit (5tht,tt)
(19)
k
where in (i) Gv/D" E R-X is defined such that (E//""((xn an)] (Gv) an) / (Ir) and similarly for GT u/p" (1i) is by Lemma B.1; (iit) is by Lemma C and Pinsker's 's inequality; in (iv) we denote by p (p",, ,"): and (v) follows from the definition of the virtual wriiste negentropy regularizer in Eq. (6).
We proceed to bound D (gki* (c)) in the above display. To this end, putting Lemma C.2, C.3, C.4, C.5, C.6, C.7, and C.8 together leads
De (ghttin, ck+1)
17

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
S(XA+ YI
k + log (6216) + aayt,, log(k2/6)
+ (XA(log² m - (log m k an or + kay 201 (X + Y) (1/0) + (X2A+ Y2B) k tantor
+ (X + +Y) log² (1/ (m log(k)) (2in
h2
h²
00 (XA + +Y- In(k)k a, ta+ + k - + log
+ k ta log
+ XA log X + H log (Ak)²
+YB (log Y + H log (BK))2) i ay a
+ - 22 (X + +) log [
+ +X*A+ Y2 (X) anya.
+ (X + +Y) (H log (Ak) H log (Bk)) (log X + log (k) log H log (Bk))
-log(k) min (1. (1.
(2))
0o (1 | ( + (XA+ +
+ (X
k-
+(X+ H 1 (log² (XAk/5) + log² (10l/))))((((K))
(20)
where the second inequality is by the fact that log(1/m²) S (logY Y H log (Bk)).
(log X + H log (Ak)) and log(1/m²)
S
Substituting Eq. (20) into Eq. (19) shows that NEGap(u",, 1² -0 [|
(XA+ 3 h (X +YJAHK
(log (X Ak//0)) + log (Y Bk/6)) ()) + XAB YBH
k + k
-ō - r) -
(x (x
(XAH + +YBH)
- (x++))*
(
(XA+Y))* where the last equality holds when & > max(H* (X22)))))) ( /14x)))) The proof is thus concluded.
C.1. Bounding NEGap(5**** Lemma C.1. Wk > 1, it holds that
NEGap(E**t) -0 ( +I(
XAH
YBH k: k
(21)
Proof. Fix arbitrary (nl, v') Immax Immi-- Note that
f (114, ,2/) - (1l, =ʃ (4 bi ,/) (ntit, +)+ + (1ti,,)) (H, (hitt (n, (u', ((in),,
(22)
where v) E II x IIk is such that ب arg min 11 15-1ello
p'lloo and v arg minpent 10 l/loo. It is clear
that ff (1 v)) f (H, wht)) in the above display can be bounded as
f (uri .v) - f (H,
=f (ybir v) - Sh (ur++,,) + Sk (nritt ,)) - fs (HG + Su (1, unit) I (1,
18

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
2 (ERth (a Exc((1)) (Ex))(()) EE (z
(1)) - ENi (phitt) ExP (vtit)
SENH ( In(Y ())
(23)
where (1) is due to that (n*11 ,bht)) is the NE policy profile of fs: and (ti) follows from (p()) S for all E maxx (similarly for all v E m.mn).
Moreover, f (u(T,,1)) (u v) in Eq. (22) can be bounded as
f (1tt, v/) f (n v) = (Vof (H kit v) V' -v}
V of (uMi,,)) 11211e/ v
(1)
1 (1- B 1
XYB
Bk:
1 1
<YB 1-
k
YBH k:
(24)
where (i) is due to Lemma 2 of Kozuno et al. (2021) and the definition of I in Algorithm 1; and (ii) follows from
(1 - 111/)) = O (1 (1) /k + (1) /k,2 -... O(1 H/k)) Similarly, we have
f (p, - f w,)) so o XAH
(25)
The proof is concluded by substituting Eq. (23), Eq. (24) and Eq. (25) into Eq. (22) and noticing that the above holds for all
(nl, 1') maxx x mmin-
C.2. Bounding Contraction of Bregman Divergences
Lemma C.2 (Contraction of Bregman divergences). The Bregman divergences of the virtual transition-weighted negentropy regularizer satisfies
negenttr
Du (g (ghtl,,,
whmo + X Allog mx) Σ oh (nei)) + YBllog m Σ wh (me:))
Term
Term
Term
with (XI, +YF)
whth (x2 + wkws
(26)
where wt = I1 (1 ))
Proof. We start by deriving a descent inequality for D& (u&tii (ottt,,,,tt) pet1) using the difference between fe(u" v*) fe (h)::
(u*- folu", - fa(l"", = - pr:n) G +Ex (b(x²t (((tiit))
(27)
For the first term the RHS of the above display, we have
(1+ (1k)) T Gv
19

---

Learning IIEGGs with Last-iterate Convergence under Bandit Feedback
(u pha)² T G+ -P--P)
(4t - wn T @t + (ut))
T (Gul - - (uttin) (Gu - -
= (1* - phtttt T pa + E His (x0, (IGvA) (xn.an) - eo (xn,
h.znia
Σ Hith (Ins and (IGEV)) (Inss an) - 2o (In, an))
son
(1* p.hinn) Tx
+ Σ Hish an)
[GW']] (om (nn)
(1r ub an
(1 rh)) + supi. (an) log [D",*] [* (Inns and ]
pf.n (2h, and + 7/k
[Gr ( (2h, - ( Ii f (zh:ant and
M1Ln (1h and +ik (1 rh)) + ERPis log)log [p" n²) (Its (chs on))
Mith (Ih, an)
(28)
For the second term of the RHS of Eq. (27), we have
(p²)) (H(tit
[V" [t] (wi, and log [p" (arns an)
E (utttttt] (oh, and log [v" [h*t] an)
ha
Σ (I=* (In, an) - 10* m+ (oh, an)) log [p" (2h, as)
Σ (t*) (xx, and (log (p" pmrr] (In, an) log [p" 1h] (2h.
Σ (1=* (n) - 1p" pm:a]] (Ih, an)) log 1p","1 (In, and Du(
(29)
where the last equality again follows from the definition of the virtual transition negentropy regularizer in Eq. (6). Substituting Eq. (28) and Eq. (29) into Eq. (27) leads to
Su Su ,1²) Su (1t 1 To
pin an) [ (an)
Th {In, and (1 rh) u (I an) + +7
Σ
h..a .08
=Pp
Σ
Mi (#n, an)
an)
[GGn (n))
Ih (nnnann (1 (1-r%)
(E
whe (I and + -ik
N. A8
=0.
( 1 (Deluhin ,n²) Cur (uurr,,ttt))) Swo "1")",,H")) + the + In 11²)
1]k
(oinaann Σ mh (Pn Miin Coo,, and (Kn,, an)² + + log² 1pmx*) (on, an)
(66) (1 - Ex) Do (utin ,11t) - Das (setit s114t1)
+ Lu + ox + + log" m
1 { a and
Σ me Pr (2n) wi. (1x, ax) +7K
h.
(Hii) (1 ThE De (nt***, ,1t) - Do (1e"=,,4e ,1++1)
+ L.. ax
20

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
(an) (1r I/ {Ih, an Mfin (I an) + 7k
+ X-
-1
x=2 A me X Alog m
X
(1 ThEk) Do "a/",,,p) De (ntre, (1tre,pet)) + Pk + Is + NIX + nxx²A + m Aogg m
where (1) is by Lemma D.I; recall mi = minp, [ (²) (ons in (ii); and (iii) is due to Lemma B. Rearranging shows that
D& (1 ,1
$ (1 - TKEK) Do (nttin, ,1ah) + me (fr (atie sufi,, fix ,(),)())) + AE log² mi nh T + Th x2 A + nahe + nk@K + Do (1httii 1e(t1) - De (uttit, ,attm,uttt 1att1)
(30)
Analogously, for the min- min-playe sinn-plyerr we have
D (ut-l,,, )htt) (1 m)Ek)) D& (0tt,,,) mh (Je (1* (,=,,,))) Sx (1t (tirt)) + Y Be log² m² + Y + r2 2 + nmpP + 1R + Wk
(31)
where
m = min bs
[p"D*]] (yn, ba):
"fin (yns + 7k -1)
1 Lyn, bn}
Σ
Plan (vn)
Pb: = Σ
vi (yn,
[11 [GT NM (en, bn))
I Tyn bn } rh
2 (yhes bb) + nkk
h.yh..h bn
Th fyh. rt
0k = Σ
with (yn, bn))
- -11-1G GG (1)) (yn, bw))
ui (un bn) + Ykk
Ba by
Wg = D& (2+t2i+, whth)
D (utt+,
Combining Eq. (30) and Eq. (31), and noticing that fo (Hiie,, fx (1rh, shin) S O. we have
D& (iitt,ngghtt)
< (1 mk5k) Du (5*+,,5t) + n (X + YY) Th + v (X²A+Y2B) + MEPk TR + wk
+ nh X As log" m y B log² m
where I& + 7k. Ph
L. Pk. ax = a + ãR. and WE w + Wk.
Now expanding the recursion in the above display leads to
Dx (g (gh+t,, c
*
k we (nE)) + Y m Σ
w mpp +
wino, + XAlloop m Σ
we (nE)))
Term
2
Term
+
w n (X +YY
w + x
w wi
Term 4
Term
Term 6
where wi = II (1 - m), The proof is thus concluded.
21

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
C.2.1. BOUNDING CONTRACTION TERMS
Lemma C.3 (Bounding Term 1). When k 2 ko, Term in Eq. (26) satisfies
Term 1 $ (XA (XA+ +T)+ ( tot + k 2t + 2 log (k2/6)
Proof. Recall
k
Term Σ
mpp =
Σ
w
T.P +
wimpP:
1=1
1=1
To bound Ei=1 w. note that
w n.L.
1=1
Σ 1=1
u t/ ( (nt, - F)
XAY Σ
k
mi +
k
(witk) Th)
2
log
1
5
xm
27
k
d
12
k
h
AXAV
a
Ong
j
aa-aa
log
20
Il - a1- j=a=-as) j=++1
i=1
j=i+1
i=1
k
A22
k
SXA)
Onp
- (1-j-a aa))
+
log
i- 20
Il (1 j jaan-ae) j=i+1
j=it1
<XAln(A)k an to:
log (62/8) (k)} aa,ta
(XAln(k)* a,,)- log (k2 (62/6).
where (i) given by Lemma G.1 and the last inequality comes from Lemma G.4 and the condition of k: 2 ko- Analogously, we have
Σ whnk $ Bll)kk)k aa blae- log /8)
The proof is completed by combining the upper bounds of Σ w.P. and Σ w TpP.
Lemma C.4 (Bounding Term 2). When is 2 ka, with probability (8), Term 2 in Eq. (26) satisfies
Term < k tan log(k?
Proof. Applying Lemma G.3 shows that with probability 1 (63
Term
wima
winoo
+
Σ w
iml
22

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
7 k²
max S
log
7k
8
k22
Sk
dy a log
where the last inequality is due to Lemma G.5 and the condition of k 2 ko-
Lemma C.5 (Bounding Term 3), When k 2 ko Term in Eq. (26) satisfies
Term 3 S (XA(log* mî) + Y B(log* mx)) k kan
Proof.
Term 3 AXA mig)
wi (ne,) + Y B mx) Σ w (me,)
i=1
x (XA mx) + B(log m k- 2(0 taprta
= (Xo m + Y B(log" m))) a
where the inequality follows from Lemma G.4 and the condition of k ko-
Lemma C.6 (Bounding Term 4). With probability 1 5, Term 4 in Eq. (26) satisfies
Term 4 < -2 (X + Y) log (1/8).
Proof.
Term 4
w th (XI; + YT;)
I (rn -1 1)
ub {ul bn3 wf.h (Bn, bn) + 7K
1
Σ wi !i
X
Σ
Y
Σ h.ya bn.
(Zn)
Mith an)
an) + +7k
pl (un)
h,
w/ { (X Y)
max 15tck
(1/8)
7
<ka -ha-~2n 2a (X + Y) log (1/6),
where the first inequality follows from that 1/X S p.sA (xx) for all (Ih, ax) guaranteed by Lemma B.1 and Lemma G.3.
Lemma C.7 (Bounding Term 5). When k 2 kn Term Eq. (26) satisfies
Term 5 5 (x2A+ Y2 k a, tac
Proof.
k
Term 5
Σ
whth (x2 A + Y²B)
$ (x2A+Y2 -- ta,
(X²A+Y2B) 1: tar
where the inequality due to Lemma G.4 as well the condition of k: 2 kp-
23

---

Learning HEFGGs with Last-iterate Convergence under Bandit Feedback
Lemma C.8 (Bounding Term 6). When k 2 li. Term in Eq. (26) satisfies
Term 6 S(X + x) log? (1/ (m)m)))) log(k)) min(
Proof. By definition, we have
Term 6 wkWs
5(X + Y) log" (1/ (m
Σ w min((1((3_../2))
S(X + +Y log" (1/ (mfm))) log(k)} (20
where the first inequality is due to Lemma D.2 and the second inequality comes from Lemma G.4.
D. Omitted Details in the Proof of Theorem 5.1
D.1. One-step Analysis of OMD with Virtual Transition-Weighuee Negentropy Regularized Loss
Lemma D.1. Let
p' arg min KER
Σ
PIoh (Ih, an) (e (In, + Epi. (xx) log (p" [1] (an,, ax)) + Do (p.11)
XA
for some convex set S2 C 1mmax L E 20 and ε E
0, 1
Then Vu E Q.
(1 u. u Ep" log (4)
- (Dvlu, (u, +
1
Σ
(
Pl.A (xx) u (In (ndennaa)(((a (x)) nE² log" (v" 14] aw))))))
"
h.rn.am
where [p" log [p" (I), an) = PlA (xn) log [p" (zn, an).
Proof. The common one-step analysis of OMD shows that
4 u. ep ep" log (p" nl) - (Do(u, - Do(u, - D)(,(,))
Hence
11 u. ep= log μ1]
1 (D,(u, Du(u, p¹) Du ,4) + (p 1 Ep" log [p" nI)
(32)
Then, to upper bound (n- - n², l. + Ep log (p" nl) 1/1 Da (1', 11), notice that
(1 - ,l, + Ep" log [p) - DD Dr (n', ())
(w-vve Ep" log l0" nl) D& (v.1))
S sup VERXA
(v, + ep log (2= ep + - (v.
(u, l + op" log (2()((
inf vERXA
(33)
24

---

Learning HEFGS with Last-iterate Convergence under Bandit Feedback
Further, the first-order optimality condition, + epp log [p + (Vv((p)) Vv((1) = 0. implies that
log
P1sh (Ih, (ha)
" PIn (xx)
[e (1hh; an) + EPi.A (#t) log Ip" [4] (axa an)l
Mish (Zh, an.)
and thus
Vish (1n,
") PiAh (mn)
[e (2h, an) Epin (mn) log (p" n)] (Ih, (il)
-Pis (1h (..) exp
(34)
Substituting Eq. (34) into Eq. (33) leads to
(p - pl,e e + Ep" log [p"x() 1 D (p),
Σ
[HuLa (ohn an) Vish (2n, an)) (e (2h. + Epi. (2x) log (p" pl (In, an))
1
[p"u] (1n, an) log (2 an) (1="v) (ar an) - [y=1(] (2n, ((nnaa)))
Mish (2,, ax))
Σ
Pin (Zh, and (e (2), an) + =eT (2n) log (p" (2), an))
1pt u| (sh, (oxp))
exp (- "
(xn) [e(In, an) + epi. log lp" n) (In, an)) - -1)]
+
1)
[D* (I an)
(1n) (e (1(n, an) + εpΣ.A (Ix) log (0" us] (In an))
bann.as
17 (n)) (pf) (o (Ih, (zll, 1
+ exp
(xn)
Σ
17
M1sh (2r (
Pi (1n)
Mish (Ih, an)
"
EpiiA (Ix) log (p" nl (In,
PL. (x))
(-
+ Minl exp
[l(xn, an) + EPT. (xk) log lo" (Ins an))
Pish (1n)
(Tn()n)) E(In, an))
Mis an) exp
exp
Σ
17 Minh an)
Pl (2n)
1 1)
Σ
ins 1p" (Jin an) log wp")] (1h, mp)
Pl. (In) ((an)aa)) an) (ID" (I tn)-e - -Ip" (xh, an))
"1
+ exp
(48)
Σ
17
Mish )nd (mnh))))))
Pla (zx)
(xn)
+
Σ
1
Iee 1p" (In, an) log (v" p) (an, an) + [v"M] (In, an)" - -W (cnn an))
ha
(i1)
1
Mish (1h, an (x an)
Pl.
25

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
Σ
me Ip" no] (Ih, an) log (p" pl (In, an) ne lp" pl (Irn, an) 1 log lo" u1] (2 an)
Σ
7
M1sh (2 (xrh,
Pi. (2TA)
Σ
(ne (1n, (n)) - - -Ip" (anh, an)) log (p" (en,as))
(10)
7
M1sh (2h,
Pi,n
Σ
1
li
[yr (In, ( 1-ne log" lop (ar un)
"
Σ
7
1ith an) (on, +
Σ haanaa
ns² log" (v" nl (an, an),
(35)
Pi
where in (1) we use e S x²
for all x 2 and Pi.a (R.)) (In, an) 2 0; (ti) follows from
Pich (x an) 2 0 and
(pp")] (Zh, (x)))==P 1nn 1p="11 (oh, 0n)) 2 0; (ivi) and (iv) are by Lemma G.6.
Substituting Eq. (35) into Eq. (32) finishes the proof.
D.2. Bounding Divergence Differences
Recall the Bregman divergence difference wk = + Whe where We = Dos (nrtli ,(ttl) De (atiit, pttt)) and
@2 D& (u*tI,+, ,b+t) Dy (u+i*, ,btt).
Lemma D.2. The Bregman divergence wt. can be bounded
[wk| = ( (Xx+ log" (1/ (mfm²))
kmiin (1,3m(1,(300e))) (1,(3-a))/2)
Proof. By definition, we have
|al S Do (uttli,, 1utti,,,,tt 1x+11 De (attnn, (ahin,pttll ,(tt1)1 + D (wbtlin, xxt1)
Dos (uhia e4tt1)
$ 10 k+l+ p² 11 wit log mi + +1lp"yati* p log m
1
X +Y log² (1/ (mfm)))
where the second inequality is due to Lemma D.3 and the last inequality comes from Lemma D.4.
Lemma D.3 (Bounding divergence using e noomm)). For all μ. ,2² 11th it holds that
DD (p', p) Do (x² p)) i00 (Iw'' - -o' p² log
mi
Proof. By definition of virtual transition- negentropy v. can deduce that
D& (pt 11) Dxy (H²,11)
Σ pin (2on) (Nte (on, an) log Mian (In, an) pfin (on, and log Mi (wns an) Mith (xh, a+)
Mith (Ih, an)
ha
Piu (2x) (ptin (Ihh an) phi (xh, an)) log Mish (In, an) Mish (Ih, an)
Σ
26

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
(log
Mish (on, an) Mish (2h, as)
log Mi:h (Ih, an) Pich (Ih, an)
Pish (ar) ph (In, an)
00
log 11 10t - -5t 1111
D&s (os
mix
00 10'p²² -p" -0*1211 log
m
where the first inequality due to that vi (In) S all on E X and thus ming,a, (1.h( 2 m
Lemma D.4. Let p² = uhr pd p. The i--ormm of the virtual transition-weighted difference between gki and ch+ satisfies
(( log (1/(mgm))) (3
lpighti - 1² =0
Proof. Recall the entropy perturbed game fo (e(H,)) v) defined in Eq. (4). To begin with, note that for all k 2 1 and (p, v/) E IT max x I main it holds that
fo (,, - fu (1tii,))
= fi (1, - Su (u whitt) + fo (1tt (dittt fu (atit, ,))
Ss (1,, (h:) Sa ( -Vusk (ntie, (utte,,atin)) .chit)) (n -urir))
fo (1 ,v) (-fk (nliit, ,,,,)) - (- (-ufi (atinn (attin T (v (v- shin))
De (H. + +EEDi (U,
=c KL (p* MF, p²tttt.t) + t KL (p' pd plrt
(1) 1
Ek (II"" μ p² u 1 ||pd v pd 2u
2
4 ||p" - p
1
(36)
where (i) follows from the fact that w*** is the minimizer of fu given * and wh* is the maximizer of fs given μ together with the first-order optimality condition; and (fi) is by Pinsker's inequality.
Let Pk = min [1, 3) and j and i are the uniform policies for the max-player and the min-player, respectively. Define 1+I. = P + (1 1k+1) 4 ,,,, Then for all h and (Ih, an), is clear that
1 + (1 PA+11 A(K 1)2 AK
k+1 (anlan) > pk+1 A
which means that 1 + E II maxe Similarly, we define kll, which satisfies that y A+I E II min Thus, by Eq. (36), we have
fir (pttly (hi))) fx (phti bttl)) 4 Ek -
1
-p=
(37)
On the other hand, since (nrt uhir) E max x
1+++1 min we have
1 fx+1 (phin, vetlin) fati (p skitt
I = |pack.* p²
(38)
Therefore, one can see that
Jk (urtti (hi))))) - fa (niii, "itt,,ee (.
=fu (1etty, vhi+t) fa (uRii, 1.itt. + fv (1ettii,, :/ttt) Su (aittl,, (2dis) ) + fir (Nr** (2t1.)) (#***,,Att.)) fx (ari (t11,))
20 (1u+t1, (tin) Sie (uiin, uetting + Vulk (1ottl, sbin) luttin - 1ott
27

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
VDJN (u cltt.) - (htl
ck / -p² 112 Vust f (alitll (lrrr) oooo || (
Vutie (1 ,,,,,,1))) 11 || l w1t11=11 112
ck /pt 1² 5
Vusk (1,, Iluetii+ 1
sup uTTTmae
sup "
.)lloo Allolllttt/ -1tt/tl ,tt2,111,
(39)
where the first inequality is due to that f& is convex in j and is concave in v and the second inequality follows from Eq. (37)
and Höder's inequality. Further, by noticing that
Vink (n, (1r sup max [GA (In, + EKPl, (2x) log [p" u1| (rh, an)
sup pEll
well Oa
S sup max [G (Ir, (m)) + TEEPi (rx) log lo" u4] (2 an)l
wellaid A
1 O(),,
<1 k log
Mi+1
and
| 1t ++111111 11Pk-- (F 11)+1) 11 S 1 + -IPeeiIEHHll -
we proceed to lower bound Eq. (39) as
Sx (n +t,, whitt) - Sk (ntrit, -bt1in)
EN ||0 Ahachtlin - -p=tti111" e= - 11 -0 X X+Y
(xx
-
133
ck ||0 t == 111
2
(110" - p" 1=1 + I|p" - 1d * 112)
Ek
X Y
k3
1
Ek 1ppekth+ - p=
(xxx A-3
X (X+Y)
Ek (1pk+1 p² p²al ||pk+] - -p" M1
Ilp441 pu Ipp+2 - porhthi11??)
X + y
Ek ||= ppicktl+ - ph
1.3
p 112 Ektl -
0
X +
(40)
3-
where the first and the second incquality is by a² + 62 2 (a + 6)2 /2 for any a and b.
Combining Eq. (40) with Eq. (38) shows that
8 Sk+i 34+1lp= - 11
Sfa-1 (11*t,uat2,n) - fo (1t*it,, ,btt1,t) - Su+i (nrtlit, (art)) + Su (1eth>+, ,.itt + 0 (x+x)
+0(
i Th (ntit,, (ukit,uktt (ktiit) - Ju (1e² whitt +0
X X+Y
(x3
k3
=Te (ntii,, ,utl,tt) - Fro (1++2,++, ,b+)++) + F (1itti+ (bt2i+) - Fr (1+tti+, wkit)) + 0 (
X Y
3.3
28

---

Learning IIEGGs with Last-iterate Convergence under Bandit Feedback
(uuJi (ntti,, ( 1bht 1 ) + (Vulu (n ,hitt) wot (hit) + +0
X x
1.
X X
(v ja (ntti " /1/ os' (nyi - 1 )(+))))) + (V v. (nett whitt /D" pd (vetlie whitt) + 0
1.3
V fr (ut ( /p" bool 1" (1 ( ||| |||| V (n (/ett) / "aEl (uRti+ -
(ueti+- -(tit)l
X
13
-= - 0 (
X +Y
Vilte (1e, ckt2itt //01
VV Ik ,)/ 1d 1/
sup well
sup VEll
1.3
sup
max K(EK EX+1) 1pr ud] (2n: an) + sup a
max (EE Ek+1) 1) log [p"v] (yn, (9n> b,
NE
EEll
-
||pehttn peetiall + +0
(*
X
1:3
=0 2(Ex (Ex- (EK-11)11 Ek+1)
log 1
1
X+Y Y
log
pp
(41)
mi
m
13
where in (i) we let fu(H, futilu, fulu.v).
Solving the quadratic equation in Eq. (41) leads to
(Ex Ex41) log mm) + v (ER 5k+1) llg" (mfm²) + Ex+1 (X + Y) /k3
||pichtl, -p²5th*11 -
Ek+1
(Ex Ex41) log (1/(mmm())
X + Y Ek+1ka k.a
Ek+1
log (1/mmmm²))
X
(X+ log (1/(m)m)))
Ektik3 k3
1,13 1
where in the last inequality, we use the fact that
(5x Ex+1)
0
-1 (1+ (1++1//)) 1 10
- (tz
Sk+1
(k (k+1)-0x
by Taylor expansion.
E. Last-iterate Convergence Rate in Expectation
Theorem E.1. With the same condition as in Theorem 5.1, Algorithm 1 guarantees that
E [NEGap(ut = Ō =0(((x+))' V(X++) k- 6-
Proof. With the same arguments as in the proof of Theorem 5.1, we have
Dy 1, 1, , ck+1)
< TLEE) D& (ctt*,5)) + The (XTr + Y +x (X²A+ + n&Pk + Ma + wk
+ T/ X A (log X + log (A + Y B (log Y + log (Bk))²
Taking conditional expectation 1|:) on both sides and by noticing the fact that Eg-1 [Te] < 0, RE-1 [pt]
0. and
Et-1 [ox] = 0, we have
E1_1 [Dg. (ck+1, (0+t1x,g*+1)]
29

---

Learning IEFGGs with Last-iterate Convergenee under Bandit Feedback
< mhEk) D& (5 _ + n (X2A+ + Ex-1 [wx]] + AE (log X + H log (Ak))² + n BEi (log Y + H log (Bk))²
Expanding the recursion in the above display leads to
E D
(c*+11, , ck+1)]
&
E
Σ w
+ XA (log X + H log (AR))²
Σ
w (ne,) + +YB (log Y + H (Bk))²
Σ w (n:,;
1=1
Σ w (X2 A Y²
(XX + Y) (H log Logg(AA (Ak) + H log( (log X + H log(Ak) + log Y + H log( Bk))
log(k)) min min -
XA (log X + H log (Ak))² + YB (log Y + H log (B1)))) 1s aa + (X²A+ + B² k- aantt
- ((X+)) H 4 Ja, + (XA+ + kB) + (X2A+ (02A+Y²B). k kartar)
Hence,
NEGap(u,, (tt)
-0 EEHH+ + XAH YBH
+
+ (X+Y) (x+ + Y)
(XX++BB) Hk
+ V(X2A+ + +Y2B)k -anter
b XAH YBH
+ (X+ V(XA+YB)HK +
+ k
k
+ b
- (Xx+)) + v(X2A+Y2B) k-t)
F. Last-iterate Convergence of OMD with Vanilla Negentropy
Theorem F11 If Algorithm I is adopted by both players and the vanilla negentropy v Enan, (Th, an) log puraaan an) is used, by setting on = 5/8, an = 3/8 and 0z 1/8, for any k 3 1, with probability at least 1 Ö(6). it holds that
( ((XA+YB))))))
Proof. The proof is mostly similar to that of Theorem 5.1 and hence we only present the key steps that differ from those in the proof of Theorem 5.1.
To start with, since vanilla negentropy is 1-strongly-conver with respective to the 4n-norm (see, e.g., Lemma 11 of Lee et al. (2021)), following a similar analysis in the proof of Theorem 5.1, we have
NEGap (5*) <NEGap (Et:*)) + VXA 11 1 + VY
1 2iih l1
<NEGap (5*+*) (XA++ VYB) v Do g*))
30

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
When the vanilla negentropy is used, building on similar analysis in the proof of Lemma C.I, it holds that
XAH
YBH
NEGap(E**>) =
(42)
k h
To bound D& (chi*, ) by similar analysis of Lemma C.2, one can see that
Dv (ghtl,, 1
& Σ
ThP +
wano + Alogg m Σ wi (ne:)) + BBogg m
wot (nei))
Term
Term 2
Term
+
i Th
(I
+ 71)
with
(XA+YB)
w
(43)
Term 4
Term 5
Term
Note that Term 1 through Term 3 are the same as in the case of using virtual transition-weighted negentropy and can be bounded by Lemma C.3 Lemma C.5, respectively. For Term and Term 5, by similar analysis of Lemma C.6 and Lemma C.7, we have
Term 4 < k 2a,
-aa log (1/6),
and
Term 5 S (XA+YB) t.t
On the other hand, using again the fact that vanilla negentropy is 1-strongly-convex with respective to the f--norm and the analysis of Lemma C.8, we can show that
Term 6 S(XA + YB) (1/ (mzm))) log(k) (lb()
The proof is concluded by putting all the above together.
G. Auxiliary Lemmas
Lemma G.1. Let {ci)imn be fixed positive numbers. Then with probability at least 8, it holds that
Σ ( (
S XA Σ
47
H
c log
1
Proof. To begin with, notice that
Σ (ii -
(
+ Σ
( Ei-1
1=1
1=1
T=1
For the first part, we have
Σ
pr, (e -B,2 [2r00]
i=1
Hhn (ooss and piae (x and (1- wisn (Irn an)
Σ
G
Σ
Hi,n (on, an) + 76
31

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
Σ
pitz (Ih,
COXXA
where the last inequality comes from 8: (In, an) I 1 for all (Ih, an) E x A.
For the second part, taking d = exp (-s²/ (2 inequality, holds with probability at least that
- (t ). == V2Σt= 222 log (1/6) and using Azuma-Hoefiding
k
Σ cs (1
[
c 2 log 15)
The proof is concluded by combining the upper bounds of the two parts above.
Lemma G.2. Let 8 E (0,1) and frl +00+ Fix h E [H]. For any coefficient sequence {al s.t. E [0, 2% XA x is F,-1 measurable, with probability 1 have
Ei -G)
max log 1sisk 8
Proof. Define w = maxisisk wi Hence
3 (In, = wrllah foh, and (1 -1-r) r/)
Mish (0ths un) +r;
willi,h {rr, a (1 (1-r)) rh)
Mi,1 ax) + Tiws (1 - -rh) Li, {xn, an /ww
2yaw, (1- (1-r%) r1) Is, fxn, and / /wpp (I an)) 1 yells (1 - r/) Is fo and (wop (In, an))
w
2%
1 27wws (1 r1)) LLn føn, on
log
2%
wpii. (In, un)
Denote by S m² (cs, fx). S = wi (ci, p Then
c.onn an) log (1 1 2 (1- - r/) Is, far and
E.
exp
(5t)
-Ta-11
exp
Σ
27/
wpinh (Ir and
(EXxI))EXxA
Cilwte we; (1 rh) Wiin (an,an) (nd)
<E.-1
1+
wHinh (In an)
(sn,a))EXxd
(0h, wi (1 ri) Me (Ih, wpin (In, an)
E
1+
(AXXA))
+
S
exp (S))
Finally, one see that
l
E
St
5%
>
log
-E
Σ
S - 5h
>
8
im
32

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
<8B
exp
5h
5
i=
=6
E -1 1
exp Σ S% 5%
k- 1
Σ
( - -si
[EA-1 exp (5) st) s... 86. 56.
exp
i=1
Lemma G.3. Let {c:),21 be fixed positive numbers. Fix h E [H]. Then 4 sequence { E [0,1]xA s.t. q² is Fi-1-
measurable, with probability at least - 6,
k C3
Eh
2p) S
max isisk "k 8
Ci log
1
Proof. Noticing that {7:]-1 is decreasing and 11o0 10l00 S 1, applying Lemma G.2, we arrive at
Σ C4 d', Pr - (1)
C2
(270 Ph - -(%
Ci log
27
max 1sisk "k
8
Lemma G.4 (Lemma 1 of Cai et al. (2023)), Let 0 h 1,0 and lest
24 In
12 1-h
I
Then
k
(1 (1-5%))
< *9nn(())**) -4th R+h
f=++1
+
Lemma G.5 (Lemma 2 of Cai al. (2023)), Let < < 2, and lest >
(24, In
12 1-h
Then
II j=i+1
(1-3
S 4t
max
Lemma G.6 (Lemma 12 of Cai et al. (2023)). For all E (0, and y > 0, it holds that x'-9 - 5 -yz" 1 900-99nn In 1 1-6,
Lemma G.7 (Lemma 20 of Bai et al. (2020)). Let eı, ......, Cr be fixed positive numbers. Then with probability at least
C4
xi l, 2i) fi)=
= o
A B.G
In
Σ
H. Proof of Lower Bound of Last-iterate Convergence
Proof of Theorem 5.6. Let NEGap, == NEGap (1² 1²) with (u* p*) the policy profile generated by some algorithm Alg. Suppose that Alg leans the IIFGG with the last-iterate convergence rate of NEGap, θ A)k for some a E (0, 1), where A (X, A) denotes the polynomial dependence on X and A of NEGapt
Fix some > max(X A, B). Consider the regret defined as follows (Kozuno et al., 2021; Bai et al., 2022; Fiegel et al., 2023):
Regx (Alg) = sup E Gv
pellmax km
33

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
where {1" )NE[K] is potentially generated by adversary. Then, can deduce that
K
Regx (Alg) = sup
Σ
(us
,4, Gvv)
(44)
w
K
sup PETTmax
fus M, GvR)
k=
sup Suppellmar Mig Gvz p G
K
suPpellmase Melllmm,, VEllmm Pa Gv v GU
K
NEGap=
f(X, A) Σ k-a
θ (f(X, A)K--a)
(45)
On the other hand, by Theorem Bai et al. (2022) (see also Theorem 3.1 of Fiegel et al. (2023)), we have
Regx (Alg) > ((VAXK).
(46)
Combining Eq. (44) and Eq. (46), we have
Φ(AAK) < e (J(X,A)
We now further consider the following three cases:
If a 2, then VAX < f(X.A)K - However, this does not hold for any f, when K is large enough:
a 2- it must hold that VAX < f(X,A);
If a J. then VAX < S(X, A)K This holds for all S, including f(X, A) when K is large enough. In this case, the "minimal" is f(X,((,)))) A) = 1, implying that the minimal possible convergence rate of NEGap, in this case is NEGap; θ (k-a)
Taking the above three cases into account, the minimal possible convergence rate is
min to ( [VVXAk 3), (k-9) (a > 2
=9 (VXA
Analogously, we can prove that NEGap; > 9(VYBk-b) Therefore, we have
NEGap, 2 2 (VXA++VBB) k k-
The proof is concluded by noticing that the above holds for all algorithms.
34

---

Learning IEEGGs with Last-iterate Convergence under Bandit Feedback
I. Experiments
In this section, we present the empirical evaluations of our Algorithm I. Since we are not aware of any other algorithm that can also learn the (approximate) NE policy profile in IIEGGs with provable last-iterate convergence guarantees under bandit feedback, we compare our algorithm against previous algorithms that converge the (approximate) NE policy profile in IEFGGs with only average-iterate iterate convergence guarantees including IXOMD (Kozuno et al., 2021), BalancedOMD (Bai et al., 2022) and BalancedFTRL (Fiegel et al., 2023). Since these algorithms are only devised to obtain the average-iterate convergence for learning IIEGGs, the last-iterate convergence of these algorithms for learning IIEGGs is not theoretically guaranteed.
Environments We consider four standard IEFG instances including Lewis Signaling, Kuhn Poker (Kuhn, 1950), Leduc Poker (Southey et al., 2012) and Liars Dice. All the implementations of these games are from the OpenSpiel library (Lanctot al., 2019).
Implementation Details As mentioned in Section 4. for our Algorithm 1, instead of operating the update OMD in the constrained set 1h max. we clip the loss estimator and then perform the update of OMD in the whole max to compute an approximate update using the closed-form solution in Algorithm 3. The clipping estimator <+++1 in Eq. (13) is set as gk+1= 1 x 10-10 We adopt the implementation of all the baselines by Fiegel et al. (2023). Besides, we consider (logarithmic) grid search on the learning rates for all the algorithms, following Fiegel et al. (2023). All the experiments are conducted on a server with an Intel Xeon Gold CPU and G5B system memory. The running of all the algorithms including our algorithm costs approximately 10 hours, 12 hours, 13 hours, and 16 hours on Lewis Signaling, Kuhn Poker, Ledue Poker, and Liars Dice, respectively.
Results The experimental results are shown in Figure Our algorithm obtains the best or the competitive performance across all four IEFG instances. In partieular, our algorithm converges faster than all the baseline algorithms Kuhn Poker and Liars Dice and also converges fast the empirically best baseline algorithm Lewis Signaling and Leduc Poker. Though some baseline algorithms work relatively well on some game instances, we would like to note again that these algorithms are not theoretically guaranteed to converge to the NE policy profile with the last-iterate convergence. We speculate that this might also be the reason why some baseline algorithms perform relatively well in some instances but poorly in the remaining ones. For instance, the BalancedFTRL algorithm performs well on Ledue Poker while converging very slowly on Kuhn Poker. Analogously, BalancedOMD converges relatively well on Kuhn Poker and Ledue Poker but converges the most slowly on Liars Dice.
Moreover, in general, it appears that the advantage of our algorithm becomes more pronounced in IIEFG instances with larger infoset spaces X' (and action spaces A) over previous algorithms. This observation aligns with the intuition that in such instances, the baseline algorithms, which solely have average-iterate convergence theoretical guarantees, face greater difficulty in achieving last-iterate convergence to the NE. This challenge may arise because these algorithms are more susceptible to getting stuck in suboptimal policy profiles, due to lack of the last-iterate convergence theoretical guarantees.
'Codes of the experiments available https::////// http::/ggghhhht.cc///oooroeeeeee Last_ ctt.attttit___ooerreeeeec.c EFGs.
35

---

Learning IEFGGs with Last-iterate Convergence under Bandit Feedback
Signaling
Kuhn
IXOMD
10-1
BalancedOMD
10a4
NE Gap
Gap
10
10
Durs
10
BalancedOMD
BalancedFTRL
10¹
10a
10
107
10
10a
10
107
Episode
Episode
Leduc Poker
Liars Dice
6x-1-
10
4x10-1
NE Cap
NE Gap
3x 3.
2 xx101
Ours
Ours
IXOMD
BalancedOMD
BalancedOMD
BalancedFTRL
BalancedFTRL
10
10¹
10a
10²
10a
10
10a
10
10a
10a
10a
10'
Episode
Episode
Figure 1. We present experimental results of Algorithm I comparison with IXOMD (Kozuno al., 2021), BalancedOMD (Bai al., 2022), and BalancedFTRL (Fiegel et al., 2023). The curves depict the last-iterate convergence of the NE gap, as defined in Eg. (1). versus the number episodes.
36


Reviews:
[{"review_id": "fkAxwG5aEb", "reviewer": "Reviewer_SfND", "summary": "The paper studies two-player zero-sum POMGs, proposes an negentropy-regularization-based algorithm, and establishes the last-iterate convergence. Though the rate seems quite loose, it compares favorably to the rate in a very relevant work Cai et al. [2023] with bandit feedback and in terms of last-iterate guarantees. A worst-case lower bound is also established.\n\n## update after rebuttal\n\nAs I have communicated to the authors, I do not think I missed any important contributions/weaknesses in my original assessment and will therefore keep my score unchanged. I support the acceptance of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided below.\n\n**Q1. \"The paper mentions ... not include them in the main paper.\"**\n\nThanks for pointing this out. We will be sure to explicitly include more descriptions of the experiments in the main paper body.\n\n**Q2. Additional References.**\n\nThanks again for noting these additional references! We compare our work with these works as follows:\n\n* [1] establishes algorithms for solving two-player zero-sum MGs with $\\widetilde{{O}}(k^{-1 / 3})$ last-iterate convergence. However, they study fully observable MGs while we study partially observable MGs. Further, they require full-information gradient feedback while we only require the bandit feedback. Note that computing the full-information gradient feedback even requires the knowledge of the state transitions (please see Sec. 2.2 of [1]).\n* For the comparisons with [2,3,4], please see our response to Q1 of reviewer T2uG.\n\n* Our work and [5] both study MGs with bandit feedback. However, we remark that they study fully observable MGs while we study partially observable MGs. Further, they require the assumption that the Markov chain can be irreducible and aperiodic for some policy. Therefore, we believe their algorithm is not directly applicable to our problem and our results are not directly comparable to theirs. Besides, our algorithm is OMD-based and can still guarantee a sublinear regret of $\\widetilde{{O}}(k^{7 / 8})$ when the opponent is an adversary, while the policy in [5] is updated via constructing approximations of the best response to the opponent's policies and it is not clear whether their algorithm can guarantee a sublinear regret in the presence of a potentially adversarial opponent.\n\nWe will include all the above discussions in our revised paper for better clarity.\n\n**Q3. Experiment Results.**\n\nWe fully agree that on Lewis Signaling, the performance of our algorithm overlaps with that of the baseline algorithms. However, we believe the experiment results show that our algorithm performs relatively well across all game instances, and though there might be some baseline that performs similarly to our algorithm on some game instances, this baseline algorithm might not be able to converge fast on other game instances, as the last-iterate convergences of all the baseline algorithms are not theoretically guaranteed.\n\nSpecifically, as mentioned in Appendix I, on the remaining game instances that are harder to learn (note that $X=3$, $A=3$ on Lewis Signaling, while $X=6$, $A=2$ on Kuhn Poker, $X=468$, $A=3$ on Leduc Poker and $X=12288$, $A=13$ on Liars Dice), only baseline BalancedFTRL converges as fast as our algorithm on Leduc Poker. However, our algorithm converges faster than BalancedFTRL on Liars Dice, and there is clearly a large gap between our algorithm and it on Kuhn Poker during episode $10^5$ to $10^7$. The other baseline with notable performance is BalancedOMD. Nevertheless, we also would like to note that, though BalancedOMD tends to have a similar NE gap at the very end on Kuhn Poker and Leduc Poker, our algorithm converges relatively faster than BalancedOMD up to episode $10^5$ on Kuhn Poker and $10^7$ on Leduc Poker. More importantly, the performance of BalancedOMD is the worst among all the baselines on the hardest game instance Liars Dice, and our algorithm converges clearly faster than BalancedOMD on this instance.\n\n**Q4. \"The virtual transition is an important tool used in the paper ..., using fewer math expressions.\"**\n\nPlease see our response to Q2 of reviewer T2uG.\n\n**Q5. \"I do not agree with the discussion on ...\"**\n\nWe agree that if linear function approximation is leveraged, the average policy can be obtained by applying a moving average over the parameters online. Our original statement on the LHS of Line 55-57 might not be appropriate, as we now realize, and we will revise it accordingly. When using nonlinear function approximation, averaging the parameters of nonlinear function approximation is of course possible, but our original statement on the LHS of Line 61-63 intended to indicate that simply averaging the parameters of nonlinear function approximation might not be able to obtain the average policy. To see this, let $f(x)=x^2$, $x_1=1$ and $x_2=5$. Then $f(\\frac{x_1+x_2}{2})=9\\ne \\frac{f(x_1)+f(x_2)}{2}=13$. We will also revise this part for better clarity.\n\n[1] Zeng et al. Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games. NeurIPS, 20.\n\n[2] Abe et al. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. AISTATS, 23.\n\n[3] Abe et al. Adaptively Perturbed Mirror Descent for Learning in Games. ICML, 24.\n\n[4] Abe et al. Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games. ICLR, 25.\n\n[5] Chen et al. A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games. NeurIPS, 23.\n\n[6] Lattimore et al. Bandit Algorithms. 20.", "claims_and_evidence": "The claims are credible and well supported by the mathematical results.", "methods_and_evaluation_criteria": "Yes. The convergence is established on the NE gap, a standard measure of optimality.", "theoretical_claims": "I only checked the proof of the lower bound, but not the main theorem on the convergence rate of the proposed algorithm. However, I find the arguments reasonable, given the existing literature on the use of negentropy regularizer and Cai et al. [2023].", "experimental_designs_or_analyses": "The experiments do not look meaningful. I do not think any conclusion can be drawn. The curves are very close to each other and well within the confidence interval/one standard deviation.\n\nMinor: The paper mentions simulation results in the abstract but does not include them in the main paper.", "relation_to_broader_scientific_literature": "N/A.", "essential_references_not_discussed": "I do not find any essential reference missing. Some papers that are worth noting due to their connection to the work in some aspects include:\n\n1) Zeng et al. [2022] and Abe et al. [2024] seem to use regularization in a similar spirit. They add regularization to obtain last-iterate convergence, and decay the weight to ensure that eventually the original problem is solved.\n\n2) Chen et al. [2023] studies two-player zero-sum games, establishes last-iterate convergence, and allows for uncoupled learning.\n\n3) Abe et al. [2023], already referenced in the paper, needs more discussion, especially as Abe et al. [2023] also considers non-full-information feedback.\n\nAbe, K., Sakamoto, M., Ariu, K. and Iwasaki, A., 2024. Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games. arXiv preprint arXiv:2410.02388.\n\nChen, Z., Zhang, K., Mazumdar, E., Ozdaglar, A. and Wierman, A., 2023. A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games. Advances in Neural Information Processing Systems, 36, pp.75826-75883.\n\nZeng, S., Doan, T. and Romberg, J., 2022. Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35, pp.34546-34558.", "other_strengths_and_weaknesses": "Overall, I believe this work makes sufficient contributions to the literature to warrant acceptance. It is in general well-written (modulo the discussion on virtual transition, which I do not follow) and the technical results seem sound.\n\nOn the negative side, the sub-optimality of the convergence rate is a concern, and the simulations do not show a clear advantage of the algorithm over the existing ones.", "other_comments_or_suggestions": "1) The virtual transition is an important tool used in the paper. While the authors made an effort to explain this, the discussion is not clear enough for the audience to understand. The authors should consider explaining the virtual transition in a more intuitive manner, using fewer math expressions.\n\n2) I do not agree with the discussion on the advantage of average-iterate convergence on line 055 and below. I understand that last-iterate convergence is usually preferred in the community, but I do not find the reason compelling. Averaged parameters can be easily updated online and requires minimal extra storage. You do not have to maintain the history of all past iterates. I also do not follow the comment that averaging policies is infeasible with non-linear function approximation. What prevents you from averaging the weights of a neural network across iterations? In addition, most existing convergence results are established in the tabular case anyways.", "questions_for_authors": "No more questions. See above.", "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": "", "extra_scores": {}}, {"review_id": "hXICUMd19T", "reviewer": "Reviewer_T2uG", "summary": "The paper proposes an algorithm for two-player zero-sum extensive-form games (2p0g) with bandit feedback. Under the self-play setting, the last-iterate of a profile computed by the proposed algorithm converges to the Nash equilibrium in a rate of $k^{-1/8}$ (or $k^{-1/6}$ in expectation). The main innovation is the use of a negentropy regularization instead of dilated entropy regularization frequently used in other algorithms for 2p0g, combined with a novel technique called virtual transition.\n\n## update after rebuttal\n\nI thank the authors for the rebuttal responses. I am convinced by the authors' explanation and raised my score to \"Accept\".", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided below.\n\n**Q1. Additional References.**\n\nThank you for referring to this! We compare our work with some notable works studying achieving last-iterate convergence in games with noisy feedback [1,2,3]. Specifically, [1,2,3] establish algorithms for solving two-player zero-sum matrix games or multi-player monotone games with noisy gradient feedback, where the noisy feedback for all the actions is observable. In contrast, we study learning IIEFGs with bandit feedback. That is, only the rewards of the experienced infoset-action pairs are revealed to the players. For the infoset-action pairs that are not experienced in one episode, no information regarding them is revealed, not even the noisy rewards. Hence, their algorithms are not directly applicable to our problem, and our results might not be directly comparable to theirs. Actually, in Sec. 8 of [2], the authors say that bandit feedback is a scheme with more limited feedback, and in Sec. 8 of [3], it is also mentioned that extending their results from the noisy feedback setting to the bandit feedback is a challenging future direction.\n\nWe will explicitly incorporate the above discussions in the revision of our paper for completeness.\n\n**Q2. \"it would be nice to ... why virtual transition is necessary.\"**\n\nThanks for this comment! The primary effect of using a virtual transition-weighted negentropy regularizer is to ensure the algorithm can be approximately updated in a computationally efficient manner. Indeed, using a vanilla negentropy regularizer without the virtual transition can also lead to a finite-time last-iterate convergence for our problem, but in this way, the policy cannot be efficiently updated, as illustrated in Remark 5.4.\n\nParticularly, in matrix games, the policy space is simply the probability simplex over all the actions, and it is well known that using OMD/FTRL with vanilla negentropy regularizer admits a closed-form multiplicative update (see, e.g., Chap. 28 of [4]). However, in general IIEFGs, this is no longer the case since each sequence-form policy is not a probability measure over infoset-action space. Fortunately, the inner products between sequence-form virtual transitions and sequence-form policies are still probability measures over infoset-action space. Therefore, using a virtual transition-weighted negentropy regularizer permits efficient policy updates (please see Prop. A.1 in Appendix A). On the other hand, the downside of using a virtual transition-weighted negentropy regularizer is that it will enlarge the stability term (approximately) by a factor of $\\frac{1}{p_{1: h}^x(x_h)}$ (please see Lem. D.1 in Appendix D). Therefore, it necessitates choosing a good virtual transition with $p_{1: h}^x(x_h)$ well lower-bounded, which is guaranteed by our Algorithm 2 (please see Lem. B.1 for details).\n\nWe will incorporate the above explanations in our revised paper for clarity.\n\n**Q3. Lower Bound.**\n\nThe main difference is that our lower bound only applies to the class of algorithms with last-iterate convergence. Technically, as shown in Appendix H, the proof idea of our lower bound is that any algorithm with $\\Theta(k^{-\\alpha})$ ($\\alpha\\in(0,1)$) last-iterate convergence can also guarantee a $\\Theta(K^{1-\\alpha})$ regret. Thus, we can prove the lower bound for the last-iterate convergence by contradiction using the existing regret minimization lower bound of $\\Omega(\\sqrt{XAK})$ in learning IIEFGs with bandit feedback (say, Thm. 6 in [5];  Thm. 3.1 in [6]). Our reduction is specifically designed for the class of algorithms with last-iterate convergence and does not directly work for the class of algorithms only with average-iterate convergence. On the other hand, we note that the hard instance used in our lower bound of last-iterate convergence is the same as that in [6], as the hard instances in the proofs of lower bounds of regret minimization and sample complexity are the same [5,6].\n\nWe will further clarify this in the revision of our paper.\n\n**Q4. \"What does one traversal mean?\"**\n\nDue to the perfect recall condition, all the infoset-action pairs $\\mathcal{X}\\times\\mathcal{A}$ across different steps $h$ form a tree. This tree can be constructed by performing the search (e.g., DFS, BFS) over all the infoset-action pairs one time.\n\nWe will include the above explanations in the revision of our paper.\n\n[1] Abe et al. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. AISTATS, 23.\n\n[2] Abe et al. Adaptively Perturbed Mirror Descent for Learning in Games. ICML, 24.\n\n[3] Abe et al. Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games. ICLR, 25.\n\n[4] Lattimore et al. Bandit Algorithms. 20.\n\n[5] Bai et al. Near-optimal learning of extensive-form games with imperfect information. ICML, 22.\n\n[6] Fiegel et al. Adapting to game trees in zero-sum imperfect information game. ICML, 23.", "claims_and_evidence": "The following is a list of claims.\n1. The first algorithm for 2p0g under the bandit feedback setting with finite-time last-iterate convergence guarantee.\n2. Their algorithm still admits a closed form solution for policy updates over the full policy space.\n3. Their algorithm does not require any communication or coordination between the two players and is model-free\n4. A sample complexity lower bound for the last-iterate convergence rate.\n\nRegarding 1, I would like to mention that there exists an algorithm for 2p0g under the __noisy-feedback setting__ with finite-time last-iterate convergence guarantee. Indeed, [Abe et al. (2024)](https://proceedings.mlr.press/v235/abe24a.html) provides one. I recommend the authors to discuss it, especially why deriving a sample complexity bound like the one in the paper is difficult to derive.\n\nRegarding 2 and 3, they are supported by Appendix A and Algorithm 1, respectively.\n\nRegarding 4, the stated lower bound is correct and coincides with one obtained previously in Fiegel et al. (2023).", "methods_and_evaluation_criteria": "Experiments are conducted in standard games, as shown in Figure 1, which compares NE gap of different algorithms after different episodes.", "theoretical_claims": "No, but all theoretical results seem to be reasonable.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper contributes to scientific fields related to sequential decision making since the paper deepens the understanding of solving 2p0g with algorithms whose last iterate converges. It is currently an active research area.", "essential_references_not_discussed": "Maybe [Abe et al. (2024)](https://proceedings.mlr.press/v235/abe24a.html).", "other_strengths_and_weaknesses": "As I noted above, a similar result is obtained in [Abe et al. (2024)](https://proceedings.mlr.press/v235/abe24a.html), that is, an algorithm with finite-time last-iterate convergence guarantee under the noisy feedback setting. However, they do not specifically consider 2p0g and issues related to loss estimates. This paper picks up 2p0g and handles bias and variance trade-off resulting in a result closer to a practical setting. Furthermore, the paper improves the existing convergence rate result of [Abe et al. (2024)](https://proceedings.mlr.press/v235/abe24a.html) from $\\mathcal{O}(k^{-1/10})$ to $\\mathcal{O}(k^{-1/8})$ with a completely different idea.\n\nRegarding the lower bound, it seems it has been already shown in Fiegel et al. (2023).\n\nThe reason why I recommend weak acceptance is that the derived bound is not close to a lower bound, and it is not really clear why virtual transition is necessary.", "other_comments_or_suggestions": "As noted above, Abe et al. (2024) provides a similar result, and it is nice to cite and discuss it. In addition, it would be nice to have some illuminating example and discussion on why virtual transition is necessary.", "questions_for_authors": "Q1. Would you explain how the lower bound in this paper differs from the one in Fiegel et al. (2023)? Since the latter one does not assume algorithm to be used, its lower bound applies to the setting considered in this paper too. Also, while their theorems states only sample complexity, they actually derive rate lower bounds in their appendix and use them to derive sample complexity lower bounds. \n\nQ2. This paper states that \"extracting (tree structure) from one traversal on the game tree\" is easy, quoting Bai et al. (2022). However, I really did not understand what exactly this means (even when I read Bai et al. (2022) before). What does one traversal mean?", "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": "", "extra_scores": {}}, {"review_id": "U6ac8teBlT", "reviewer": "Reviewer_wkY8", "summary": "The authors propose an efficient algorithm (namely, with closed form solution update) which attains a last-iterate convergence rate of order $K^{-1/8}$ when run in self-play and when only bandit feedback is available. They also provide a lower-bound on the convergence which does not match the rate attained by the algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank the reviewer for the valuable comments. Our response to each question is provided below.\n\n**Q1. Specifically, the techniques seem to me ... when proper distance generating function are employed).**\n\nThank you for this comment. Indeed, our analysis scheme is inspired by [1], as we have mentioned in Remark 5.5 of our paper. However, we would also like to remark that a key distinction between our work and [1] is that [1] uses the *vanilla negentropy regularizer* while we use a *virtual transition-weighted negentropy regularizer*. Simply using the vanilla negentropy regularizer in our problem can still guarantee a finite-time last-iterate convergence result as mentioned in Remark 5.4 of our paper, but doing so will not be able to obtain computationally efficient approximate policy updates. In contrast, with the leverage of the virtual transition-weighted negentropy regularizer, our algorithm simultaneously permits efficient approximate policy updates (please see the end of Section 4.1 and Appendix A in our paper for details) and guarantees a meaningful last-iterate convergence.\n\nBesides, we fully agree that closed-form updates for OMD are common in IIEFGs. And it is precisely for this reason that we would like to make our algorithm computationally efficient as well. Nevertheless, we would like to note that, though dilated negentropy is common in existing literature studying IIEFGs (say, [2,3,4]), we did not use the dilated negentropy as the regularizer in our algorithm. Though it is well known that dilated negentropy admits efficient closed-form policy updates, using dilated negentropy in our problem can only lead to a vacuous convergence rate that is exponentially large in $X$, as illustrated in Section 4.1 of our paper. In contrast, as aforementioned, we leverage the negentropy weighted by the virtual transition over the infoset-action spaces. Importantly, this virtual transition is specifically designed to maximize the minimum sequence-form \"visitation probability\" of all the infoset-action pairs, so as to ensure a last-iterate convergence with meaningful dependence on $X$. Our virtual transition is directly computed by our Algorithm 2, and the construction of such a virtual transition is never exploited in existing literature for studying IIEFGs, let alone in [1]. Therefore, we believe our algorithmic design as well as the result is meaningful and valuable to the literature.\n\nWe hope the above explanations would be helpful to address the concerns of the reviewer about our technical contributions, and we will explicitly incorporate the above discussions into the revision of our paper for better clarity.\n\n**Q2. Which are the fundamental differences of this work with respect to (Cai et al. 2023)?**\n\nPlease see our response to the question above.\n\n\n\n[1] Cai et al. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. NeurIPS, 2023.\n\n[2] Hoda et al. Smoothing techniques for computing nash equilibria of sequential games. MOR, 2010.\n\n[3] Kroer et al. Faster First-Order Methods for Extensive-Form Game Solving. EC, 2015.\n\n[4] Kozuno et al. Learning in two-player zero-sum partially observable markov games with perfect recall. NeurIPS, 2021", "claims_and_evidence": "The result seems convincing and reasonable.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are standard.", "theoretical_claims": "I did not check the correctness of the proof, in details.", "experimental_designs_or_analyses": "I checked the experimental results in the Appendix.", "relation_to_broader_scientific_literature": "The only contribution of this works is to extend previous results in matrix games to extensive form games.", "essential_references_not_discussed": "The related references are cited in the work.", "other_strengths_and_weaknesses": "The main strength of the is work is that the authors show the first result on last-iterate convergence in EFGs with bandit feedback and uncoupled dynamic. Nonetheless, I have concerns regards the technical novelty of this work. Specifically, the techniques seem to me mainly adapted from (Cai et al. 2023), which established almost identical result for matrix games with bandit feedback. Indeed, the are some challenges in dealing with EFGs; nevertheless, the techniques employed to generalise (Cai et al. 2023) to EFGs are mainly adapted from (Kozuno et al. 2021) (e.g., notice that, closed form solution for OMD is not surprising in EFGs, when proper distance generating function are employed).\n\nOverall, I believe that the contribution of this paper is not enough to meet the acceptance bar of a conference such as ICML.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "Which are the fundamental differences of this work with respect to (Cai et al. 2023)? I am willing to increase my score if the answers are pretty positive.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm for two-player zero-sum extensive-form games (2p0g) under bandit feedback. In a self-play setting, the last iterate of the strategy generated by the algorithm converges to the Nash equilibrium at a rate of k^{-1/8}. The key innovation lies in replacing the commonly used dilated entropy regularization with negentropy regularization, combined with a novel technique called virtual transition. This is a nice theory result and I recommend for acceptance.
Decision: Accept (poster)