Local and Adaptive Mirror Descents in Extensive-Form Games
Authors: Côme Fiegel
Pierre Menard
Tadashi Kozuno
Remi Munos
Vianney Perchet
Michal Valko
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
game theory
extensive-form games
mirror descent
Primary area: online_learning
TL;DR: We study how to reduce the variance of algorithms that learn to play a large imperfect information game.

Abstract: We study how to learn $\epsilon$-optimal strategies in zero-sum imperfect information games (IIG) with *trajectory feedback*. In this setting, players update their policies sequentially, based on their observations over a fixed number of episodes denoted by $T$. Most existing procedures suffer from high variance due to the use of importance sampling over sequences of actions. To reduce this variance, we consider a *fixed sampling* approach, where players still update their policies over time, but with observations obtained through a given fixed sampling policy. Our approach is based on an adaptive Online Mirror Descent (OMD) algorithm that applies OMD locally to each information set, using individually decreasing learning rates and a *regularized loss*. We show that this approach guarantees a convergence rate of $\tilde{\mathcal{O}}(T^{-1/2})$ with high probability and has a near-optimal dependence on the game parameters when applied with the best theoretical choices of learning rates and sampling policies. To achieve these results, we generalize the notion of OMD stabilization, allowing for time-varying regularization with convex increments.

Local and Adaptive Mirror Descents in Extensive-Form Games
Côme Fiegel
Pierre Ménard ENS Lyon Lyon, France
Tadashi Kozuno OMRON SINIC X Tokyo. Japan
Rémi Munos
CREST
FairPlay, ENSAE Paris
Google DeepMind
Palaiseau, France
Paris, France
come wwwgeeeoormmllesup...oomo org
Vianney Perchet
Michal Valko
CREST FairPlay, ENSAE Paris, Criteo Al Lab Paris, France
INRIA
Abstract
We study how learn e-optimal strategies in zero-sum imperfect information games (IIG) with trajectory feedback. In this setting, players update their policies sequentially, based their observations by T. As noted by Steinberger et al. (2020) and McAleer et al. (2022), most existing procedures suffer from high variance due the use of importance sampling over sequences of actions. To reduce this variance, we consider fixed sampling approach, where players still update their policies over time, but with observations obtained through given fixed sampling policy. Our approach is based on an adaptive Online Mirror Descent (OMD) algorithm that applies OMD locally each information set, using individually decreasing learning rates and a regularized
a fixed number of episodes denoted
loss. We show that this approach guarantees convergence rate of Ó(T-1/2) with high probability and has near-optimal dependence on the game parameters when applied with the best theoretical choices of learning rates and sampling policies. To achieve these results, we generalize the notion of OMD) stabilization, allowing for time-varying regularization with convex increments.
Introduction
The extensive-fome representation of game (Osborne & Rubinstein, 1994) be depicted tree whose nodes correspond to the game states. At each state, the players choose some available actions and, based these choices, the game transitions to the next state among the current state's children.
In imperfect information games (IIGs), players may only have access partial information about the current game state upon taking action. Therefore, the state space is partitioned for each player into multiple information sets, which consist of indistinguishable states from the player's perspective. With perfect recall (Kuhn, 1950), when players remember their previous moves, each space of information sets also has a tree structure.
We focus more specifically on zero-sum IIGs represented in an extensive form under the perfect recall assumption, where the gains of one player, conventionally called the max-player, are equal the losses of his opponent, the min-player. The primary goal is to design an algorithm learning e-optimal strategies (von Neumann, 1928). To achieve this, one can use the self-play framework, where an agent controls both players for 7 episodes. At the beginning of each episode, the agent prescribes strategy for each player. The agent then observes the play and updates the players' strategies for the next episode based on the outcome of the game. After I' episodes, this protocol returns a guess of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

strategies with small exploitability gap (Ponsen et al., 2011). In this learning framework, the agent has very limited feedback, only observing the rewards along each sampled trajectory, as opposed to richer feedback that would for example include all possible rewards and all transition probabilities, (Zinkevich et al., 2007; Hoda et al., 2010; Tammelin, 2014; Kroer et al., 2015; Burch et al., 2019) unrealistic in large games.
To deal with this learning framework, well-studied approach is unilaterally minimize the regret of each player during the interactions with the game, i.e. the difference between the cumulative gain the player would have obtained had he played the best fixed a posteriori policy and the cumulative gain obtained by following the sequence of policies. The key observation is that by minimizing the regret of both players, the average policies over the sequence of policies generated during the process converge toward optimal strategies at the rate of order O ((1/V /V) (Cesa-Biand Bianchi & Lugosi, 2006; Kozuno et al., 2021). Regret minimizers such as CFR-based algorithm or online mirror descent (OMD) (Hoda et al., 2010; Kroer et al., 2015) can be used, leading to optimal rates (with respect to the game size) with the latter option (Bai et al., 2022; Fiegel et al., 2023).
Since the agent only observes trajectories of the game, an importance sampling estimate (Auer et al., 2003) of gain (or loss) is fed to the regret minimizer. However, the estimate of this loss usually suffers from high variance due two reasons. First, the same sequence of policies is used to minimize the regret and to collect the trajectories, making the players strive to fulfill two competing goals: play a policy with small regret and play policy leading to a small variance gain estimate. Second, importance sampling is applied to sequences of actions, that have in large games a very small probability of being played, leading to empirically large importance sampling weights and ultimately inflating the variance of the gain estimates.
To mitigate this issue, regularization and biasing the estimates can help (Kozuno et al., 2021; Bai et al., 2020). However, the high variance of the gain estimates remains problematic with large games, for which the algorithms are generally coupled with function approximation (Steinberger et al., 2020; McAleer et al., 2022). For instance, neural networks are particularly susceptible to noise (Zhang al.. 2021). A natural question is thus whether it is possible to learn optimal strategies without relying on importance-sampling over the sequence of actions.
To this aim, consider a particular case of the self-play framework: the fixed policy sampling framework (Lanctot et al., 2009). In this setting, a fixed policy is used to collect the trajectories of the game. Precisely, at each round, one player, let's s say the min-player, follows the fixed sampling policy to play against the current policy of the max-player. The collected trajectory is then used to update the current policy of the min-player. In the next episode, the max-player will follow a sampling policy against the current policy of the min-player, and so on. The outcome sampling MCCFR algorithm adopts this framework to update the two players' policy by regret minimization, feeding the CFR algorithm with gain estimated via importance sampling (Lanctot et al., 2009; Bai et al., 2020; Farina et al., 2021b).
Recently, McAleer et al. (2022) proposed the ESCHER algorithm that removes the need for importance sampling in this framework. In particular, the CFR algorithm is invariant by re-scaling of the gains and the weights of the sampling policy are fixed, ESCHER can directly operate with the unweighted history cumulative gain (Bai al., 2020). Unfortunately, it still requires access to an oracle that provides this history of cumulative gains at an arbitrary information set.
Nonetheless, the insight of McAleer et al. (2022) cannot be used directly for OMD-based algorithms as they are not scale- invariant. Furthermore, the OMD-based algorithms generally work at the global game level whereas CFR-based algorithms work at the local level of the information set (Bai et al., 2020), making local adaptation to the problem easier.
Contributions
We make the following main contributions:
We propose the LocalOMD algorithm, in the fixed policy sampling framework, that allows adaptive learning rates and does not require importance-sampling over the sequence of actions but only for the current action. We explain how it can simply be seen as regret minimization procedure applied to local loss each information set, similarly to Farina et al. (2019b).

---

We prove that LocalOMD achieves, in this fixed sampling framework, Ô (1/E2) sample complex- ity with any choice of non-degenerate sampling policy, ignoring the game and policy-dependent parameters.
With an appropriate sampling policy and choice of learning rates, we prove that LocalOMD, recover the (Ax + By)/E²) near-optimal sample complexity for learning s-optimal strategies in a tabular setting, where H is the height of the tree, Ax the total number of available actions for the min-player and By the same quantity for the max- mlx-pr.yer. This sample complexity was also achieved in the fixed policy framework by BalancedCFR (Bai et al., 2022). but with less generalizable
procedure that updates the policy at one depth at a time.
We generalize the aaalstabilization technique introduced by Fang et al. (2020) to analyze OMI) with time-narying regularization as long as the increments of the regularization are convex.
Our tabular experiments reveal that our algorithm yields comparable results to existing baselines while demonstrating a reduced variance in loss estimation.
2 Settings and fixed sampling procedure
2.1 Extensive-form games and regret
Game definition We consider a finite zero-sum IIG game VY, p. p. E) with perfect recall. Given two behavioral policies μ = (p(+Iz))=Ex and v/ (v(-1)) wEy, one episode of such game proceeds as follows: An initial game state 81 ~ p(-1s0) is first sampled in the set of states S according to the transition function p. starting from the root 8o of the tree. At depth h, the min- and max- players respectively observe the information set Iy and yh. associated with the current state 8n, in the spaces of information sets X' and y (these spaces being two partitions of S), then simultaneously choose and execute actions an μa(|[za)) and by v(-18n) in the sets of legal actions A(rx) and B(ya). As result, the state transitions to new state 8h+1 p(: sh, Oh, bn) in S, with the min- and max- players getting respectively the losses la ~ ((-[s), ah. bj) in [0. 1] and - ln according to the loss distribution f. This is repeated until final state sh of fixed depth H is reached, after which the episode finishes.
Policies and actions We will denote by Imin and mmxx the set of behavioral policies of the min- and max- players. Because of the perfect recall assumption, such policies, with an independent stochastic choice of action for each information set, are enough describe the entire set of strategies (Laraki et al., 2019). We will also denote by Ax and By the total number of actions for respectively the min- and max- players, i.c. Ax == EeEx A(z)) and By Eyey [By))).
Regret and e-optimal strategies We are interested in learning s-optimal policies through self- play over multiple episodes. A useful notion for this objective is the regret as explained in the introduction. We first define the value Vur = E.. [> Ln] as the expected sum of losses (for the min-player) with respect to a pair of policies (J4, v) Immi X Immax- Given a sequence (μ², v²" (e(T)) in Imin x mmxx the regrets of the min- and max- players are then defined by
T
RAT = max elllnn
I(vuler
- -vill,o and
BT max
max Σ(vuret - vulee) VI ellaa t=1
Minimizing the regret of both players leads to the computation of an e-optimal profile (equivalent to an e-Nash equilibrium for two players zero-sum games) through the computation of an average of the policies. The following theorem quantifies this statement under the perfect recall assumption.
Theorem 2.1. (Cesa-Bianche Bianchi & Lugosi, 2006; Kozuno et al., 2021) From a sequence (μ', 1/" eee in 1mmin X 1max a certain tine-averaged profile (TI, D) is e-optimal with s (D + + /T.
It especially shows that both averaged strategies converge to the set of optimal strategies as long as the regret of both players is sub-linear.
We now focus the min-player point of view because of the symmetry of the game. Indeed, the following ideas will apply exactly the same way to the max-player, using the losses - l, instead.
For algorithms with a probability at least 1 å of a correct output, the symbol δ hides dependencies logarithmic in Ax, By and 6
3

---

Algorithm Learning procedures with fixed sampling policies for two players
1:
Input: Fixed sampling policies je and v²_ Initial policies y and v² and update procedure for each player
2: For t= 1 T
The min-player observes the full outcome of an episode with the policies (n*e, v²)
The max-player observes the full outcome of an episode with the policies (u' 1*) The min- and max-player respectively update μ and y based on their past observations
3:
Output: The time-averaged policies J. V of Theorem 2.1
Perfect recall and realization plan Under the perfect recall assumption, players do not forget their past observations and actions. We can then assume, for any information set X and action E A(x), the existence of unique depth & E [M] and history (I1, 41, ..., Ln, (p.) such that and db = a. Using this unique history, we define the realization plan P1: RAxx (von Stengel, 1996) associated to a policy I E mimn with, for any x X' and a E A(x) by [1:(2, a) == IT (((aala;)) It denotes the combined probability of choosing actions that lead to (zc, a). We will especially define Q max = {M 1 E miaa the treeplex, i.e. the set of all possible realization plans.
Loss and regret linearization For v max- max-player policy, the unique history also allows for the definition of adversarial transitions pf: E F and adversarial losses L" e AAx with:
p=)(x) = (s0)
II pl (2:1/01-11 a-11 and == 1=2
where p(a (so) is the probability that an initially observed by the min-player, and, assuming that the max-player policy is set to ("(((1;-1,4--11) denotes the probability of transitioning to s; when (xz-1: (;-1) is reached, and f% the average loss l, associated to a when x is reached. Similarly to the realization plan, the adversarial transitions denote the combined probability of both Nature and max-player actions that lead to x, assuming that the min-player plays the actions (a1, an-1).
Using chain-rule argument, we get the relation Vk. (e" p1.), given pair of policies V, E IImi X mmax. where (.--) is the standard inner product of IR Ax, defined by (21, := Exex EREA(s) 21 (z, 22) a). The regret can then be rewritten
Ele, -MI:
RT =
min
max A ATEllmin
where Ee := =="", which effectively reduces the problem to a linear regret problem over the convex polytope Qini of realization plans.
Several techniques exist to sequentially choose policies (e") minimizing R assuming that the losses Le are observed after each round l (Hoda et al., 2010). However, in the trajectory feedback setting, these losses are not observed, and can only be estimated from the observation of the trajectories (a1 a .... -/H a'y)) and partial losses (Li..., e of each round.
2.2 Fixed sampling policy
In the fixed sampling framework (Lanctot et al., 2009), both players always use the same policy for the observations of the trajectory. However, the two observations can not be done simultancously with such an approach, as the learning would then be quite naive. The solution, summarized in Algorithm 1, is for the two players to take turns between observation phase, in which they play their fixed sampling policy 1r" or v², and an interaction phase, which they play their updated policy u² or v². The underlying idea is that the observation phase lets each player observe how the game unfolds against the opponent in its interaction phase, playing its updated policy. Given upper-bounds of the regrets P. and R2 Mis associated the sequence (μ², v² )te(z] the previous Theorem 2.1 then characterizes the optimality of the outputted time-averaged profile (j, v).
While theoretically optimal algorithms already exist using simultaneous regret minimization pro- cedures (Bai et al., 2022; Fiegel et al., 2023), this framework allows for the removal of the global

---

importance sampling term of the loss, which reduces the variance to make algorithms more suitable beyond the tabular setting (McAleer et al., 2022). Indeed, the probability of choosing a sequence of action reaching a given information set is fixed, the average estimations of the losses do not need be re-weighted based on the inverse of changing probability. This re-weighting eventually leads to unstable function approximation, e.g. with neural networks, as this probability can be very small.
Furthermore, the fixed sampling framework also allows aggressive policies more focused on exploita- tion, as the observation side is handled by the sampling strategy. The downside is that this sampling policy must be fixed in advance, which requires defining good sampling policy beforehand.
From now on, we again focus on the min-player for the same symmetry reasons.
Estimated regret
Based on the min-player observations, we define 2. the estimated regret by
T (p. - -1.-)
9 min
max JA Ellmatn
where the e are the ipportance-sampling estimated loss vectors, defined for each information set x of depth h and action A(x) by
(x=st,a=01) (xx (i
e
with 2/ the visited information set, a the chosen action and f the loss at depth of episode
The following theorem states that the actual regret, up additional additive term. Its proof is given in Appendix B and relies Bernstein-type inequalities.
this estimated regret is enough to upper-bound
Theorem 2.2. Assume that the estimated losses obtained with fixed positive sampling policy μ as above. Then, for any sequence (y'))E(T) miin and any 8 E (0, 1), the following bound holds with probability least 1 5
RI I max AA 0) 4VHHK((
where: log (Axtl) and x(x²) maxpellmme ΣxEx ExEA,
(araa
P1. (z,a)
A similar proposition is proved by Farina et al. (2020). Our bound is specific to the importance- sampling loss estimator, but tighter by a factor / /x(μ*)/HI
Remark 2.3. The quantity x(n") can be efficiently computed recursively for each of the sub-trees induced by an information set x X. and we will denote by x(μ* (z) the associated quantities. The same recursion shows that the balanced policy μ², which plays proportionally to the total number of actions of each sub-tree, minimizes all these local quantities and satisfies x((²)) = Ax- The related computations provided in Appendix C.
3 Adaptive Mirror Descent
We shall now focus on the update procedure the min-player can use to minimize this estimated regret. Let us first define some important notions of convex optimization.
Definition 3.1. Let Ω C R be non-empty open convex, and Ω be its closure. A function + is said to be Legendre
is strictly convex, continuously differentiable on and vy E D 22, lim,-ryl V (z)] = +oo The Bregman divergence D Ω x Ω + of Legendre function V is defined as Dw y) :=
(xx) ()y) (VV()), y). The Fenchel conjugate
V* R U {+oo] of defined by V (E) = suprem e (E, x)) (xx).
3.1 Online Mirror Descent and dilated entropy
In an extensive-form game with perfect recall, algorithms based on the Online Mirror Descent (OMD) typically compute each time step the update
arg min (?r, D (Misshh)
(OMD)
plllain
5

---

where L. is the estimated loss and V Quin - R Legendre regularizer.
Dilated entropy A common choice of such regularizer is the dilated entropy (Hoda et al., 2010; Kroer et al., 2015). It requires for each x E X' a Legendre regularizer v over a convex domain Og [24(11 that contains the simplex A(x) == {M. ElEA(e) uuaa) = =1). For given list of positive weights a (a(x))xxx. the dilated entropy wilil satisfies for any l E min-
va (m)) Σ (t) (u(-lz))
where (1:(x) E Zae #1: (2, a). Using this dilated entropy as the regularizer, the OMD updates become
1 1=+1
arg min
(P.mi) + Dall (M1:11)
uellmio
where Ddd (11: (1.) ==):==eee Eaex (z) (1, (+()) and (Dæ)zex are the individual Bregman divergences of the (Lz))rxx The benefits of this regularization are that it efficiently suits the structure of the game and that the associated updates are easily computed recursively, starting from the final states.
3.2 Stabilized OMD algorithm
The regularizer V sometimes needs to change over time. For example, when T is unknown, regularizer of the form रे /ry is usually considered, with rf = 1-1 the learning rate. Fiegel et al. (2023) gives another example of time-varying regularization, adapting the regularization the game structure that is assumed to be initially unknown. The previous updates (OMD) do not however allow adaptive regularization in general. In fact, even the simple learning rate decrease r/- = t 1/2 can lead to a linear regret dependence with time (Orabona & Pál, 2018).
In this part, we shall consider more generally a sequence of Legendre regularizers (4²) ketr defined on convex domain Ω C R", and that the player chooses a sequence of primal iterates (e()) (respectively the updated realization plans (/1))E((T; of our settings) in closed convex set C (respectively the treeplex Qmin) included in Ω2 according sequence of dual increments (E")xE(z
in IR" (respectively the estimated losses ( ((E(T) observed sequentially.
Fang al. (2020) proposed in the presence of non-increasing learning rates, use a technique called dual-stabilization to recover the classical OMD bounds. We noticed that their updates can be interpreted
w ++1 arg min (5', w) + Dap (w. w²) + Dert+i (w, w²)
LDS-OMD)
EC
with v T incremental functions assumed to be convex, generalizing their special case 1 1 //n The following theorem, proven in Appendix D shows that classical OMD guarantees be recovered with these updates.
Theorem 3.2. Let (w* )eefr be a sequence of primal iterates generated by the updates (GDS-OMD), with convex incremental functions. Then for any w E Ω
Σ (g', wn -w") <D (w!, , wt
Dor. (VV'(w") - (w")
where the (11(+ (No(+)) )ierry are the respective Fenchel conjugates of the (4'))
Compared to the guarantees obtained with previous adaptive procedures, such as Ada-MD (Joulani et al., 2017), the first term of the bound is stated with respect to w instead of the sequence (w") )+ which is important for some (V'),, sequences (Orabona Pál, 2018).
Remark 3.3. AdaGrad for stochastic gradient descent (Duchi et al., 2011) is an interesting example of regularization with convex increments (and not only through a decreasing learning rate). It uses the adaptive regularization g = ||-11/ where G is positive semi-definite matrix defined
with the gradients da by either G Ek=1 Da9K or, more efficiently, by G Diag (Ek=1 9..1%)

---

Algorithm 2 Local0MD
1: Input:
Sampling policy μº mim and initial policy n² E min Bregman divergences D for each information set a E X Sequences of (possibly adaptive) learning rates (x)),, for each round and information
set z.
2: For to T
Observes the outcome of an episode using the fixed strategy n²
4H++1 0
For h = H to 1:
f {a=at] (Ch, + /n (ahla())
+ + arg minmin A (1(
di min (1)
where h2, (p) = (2,10) ( Dr (H, (-12f)) (prt(e "f" 1(x{] and t' is the last round in which 2t was visited For all non-visited (-(x) + (-1-1z)
Do (e, p (112h))
X::
3: Output: The time-averaged policy ІI
Adaptive dilatation In the extensive-form game setting based the dilated entropy Tilll this stabilization can be applied to have weights (x=)))xxxx that vary with times. The convexity assumption of qdiil a++1 qidil then rewrites to having locally non-decreasing weights for each E X. In this particular case, the updates are obtained with the formula
++ arg
argmin min
(2,Pu)) Dall (H, n²) + D a'ti - (N,1²).
(DDS-OMD)
pell
4 LoCalOMD algorithm
4.1
Algorithm
Let consider the fixed sampling framework introduced in Section 2.2. Given sequence (x)))))))) of locally non-increasing learning rates for each x E X, we introduce the LocalOMD algorithm described in Algorithm 2. that uses the updates (DDS-OMD) above with the adaptive weights a' a'(x) (z)) Dividing the loss by the importance sampling term (x) through the learning rates lets bypass the large variance that this rate can introduce.
Local loss This algorithm can be interpreted as one that locally applies the updates (GDS-OMD)
using the local loss f/ regularized version of the sum of subsequent losses. Even though this algorithm results from a global minimization procedure, the local loss only uses the probability u² (afæ) of choosing the last action a E A(x) in the important sampling, instead of the combined probability ui (æ, a) of the realization plan. A similar decomposition was observed by Farina et al. (2019a) for the nonsstcchastic settings, in which both players directly observe the gradient associated with their policies.
For this reason, the local loss will consistently be at most of order O(HA). Meanwhile, the loss used by Fiegel et al. (2023) can of order ((Ax) (approximately A the worst case), even with IX exploration attempting to alleviate the importance sampling issue. This presents a challenge for potential applications involving function approximation, where Ax becomes very large (McAleer et al., 2022). For instance, such high-variance estimates could lead to highly unstable training dynamics of a policy parametrized with a neural network.
Complexity At each iteration, the algorithm only needs to update the policy along the observed trajectory, so the time complexity per iteration only times the cost of a local update. D, the Kallback-Leible divergence, the local updates then simplify to some Exponential Weights updates
7

---

and the total time complexity of an iteration becomes OHH)), where A is an upper-bound on the local number of actions.
4.2 Theoretical analysis
The analysis of LocalOMD, detailed in Appendix E is derived from Theorem 3.2 that bounds the estimated regret. The results on the real regret are then obtained with Theorem 2.2. We now present two choices of regularization and their associated guarantees.
Adaptive rates As LocalOMD treats each information set z E A' as a separate problem through the local losses fg. an interesting choice is to consider the same adaptive rates that would be used in the K-armed bandit problems. The following theorem provides an upper bound in this case.
Theorem 4.1. (Informal, exact statement in Appendix E)
For large class of regularizers (Wa)zex and learning rates (1' (x))xxx))))) the regret has ((vT log(1/6)) upper bound (hiding the game cane-dependent terms) with a probability at least 1 Such learning rates include, for all x & X of depth h,
2
(²(x)) =
( or the adaptive version nf()) =
The adaptive learning rates mentioned for this theorem generally enjoy better performances in practice. Furthermore, they require no initial computation and are easily updated.
Optimal rates The following theorem uses a constant learning rate that locally depends on the k(u"(z) quantities of Remark 2.3, and on the A == max |Ax)) quantity that upper bounds the local number of available actions on the whole tree.
Theorem 4.2. Using LocalOMD with je as the uniform policy, with the learning rates rz(z))
n/<<(=12)) where 7) = Vlog(A) ())(()))((())))))) (/3H)) and with v the Shannon entropy V (z(x) ELEA(H) ula) log(u(a)), we have with probability at least 1 - and = 12g(2(Ax + 1)/8).
Ri S (4+2/3) 3112 /log (ogg(A)n((>)TT.
Note that these rates are not adaptive and thus do not require the stabilization introduced in Section 3.2. When using the balanced policy μ* as the sampling policy, for which x(μ*) AAx. we obtain with Theorem 1 the rate (H3/2 VAxT), near-optimal up to the H dependency (Bai et al., 2022).
5 Experiments
We implemented LoCalOMD, with the parameters of Theorem 4.1 and Theorem 4.2, then tested against the theoretically optimal BalancedCFR (Bai et al., 2022) using the balanced policy as the sample policy, and BalancedFTRL (Fiegel et al., 2023). The algorithms were compared on three standard benchmark games: Kuhn poker (Kuhn, 1950), Ledue poker (Southey et al., 2005) and liars dice, using the version 1,4 of the OpenSpiel library (Lanctot et al., 2019) under the Apache 2.0 license. The learning rates (and the IX parameters for the relevant algorithms) were optimized independently for each algorithm using grid search. The code is available at https: //github. com/ wwwaaannnnoccaaan00/0// www.oooD-Deeeeimeeeeee
experiments.
The results are given with respect to the total number of episodes used for learning, This technically disadvantages the fixed sampling algorithms, as these require more than one episode at each round while still performing single update on the policy of each player. The exploitability gap, along with the variance across the different instances the simulation, is plotted in Figure top. Note that this variance across the instances different from the variance of the estimated loss vector l our method tries to reduce, which is plotted in the Figure 1, down.
Focusing on the exploitability gap, we observe that the two versions LocalOMP 1MD behave similarly and constantly beat BalancedCFR, mainly because the latter needs to update each depth with independent

---

samples, thus needing H times more episodes overall. The results of BalancedFTRL are more comparable, exhibiting for example better performances on liars dice but worse on Ledue poker.
In the second figure, we observe that the algorithms based on a fixed sampling procedure indeed get smaller variance in their loss estimation as the sampling policy stays consistently balanced. BalancedCFR again gets worse results compared to LocalOMD as the losses of each depth are only estimated every H/ iteration, which increases its variance.
Average exp. in Ruhn paker
Average exp. in Leduc poker
Average exp. in liars dice
10
1
BebecrdCER
Belanced
BelsnoedCRR
16-
DebercedTRR
DnlancedTTRL
10
BelencedTTRL
LockiCMD Optimal
LocalHH Optimal
Loca DVD Optimal
LocalCMO Adapriee
10
LocalMD Adeettive
Ade stive
20'
15'
10
15
10
10
10
10'
10-
307
BalancodChh
Folancedf
6x 10
Sul ScudCPh
Dalenced
LocarCDD Opaimal
LocaioND IMD mat
LecalcHD Cpt mal
132
LocalCMD Aduptive
LocalcHt Adeptive
LecaloND Adaptive
3x
1:3
2x 201
165
1.0
30
10a
10
10'
1.0
125
30
10' 1.4 301
15
Epicods
Episude
Episdd
Figure 1: Performances over 5 simulations of various algorithms with respect to the total number of episodes. The vertical axis denotes the exploitability gap (ax().))lllmnn xIlmax V Vu. (top) and the empirical variance of the Zt vectors over time (bottom), with all rewards scaled between 0 and 1. The total numbers of actions are Ax = By = 12 for Kuhn poker, Ax = By = 1092 for Ledue poker, and Ax By 24570 for Liars dice.
6 Conclusion
We studied the use of fixed sampling OMD procedure for the computation of c-optimal strategies. This approach relies, for each player, on an uncoupling between the observation policy and the interaction policy described in Algorithm 1. This uncoupling is in direct contrast with the more restrictive semi-bandit setting usually considered for self-play, where these two policies must coincide by design. Notice that this is not the standard exploration/exploitation trade-off, as even in the expert setting (with full information), some kind of exploration is still required.
While the balanced observation policy gets the optimal rates in the worst case, it may not always be the best one for a given game, An alternate choice is to instead use for the observations the current average policy (Gibson et al., 2012). This choice can be adapted to the fixed sampling framework, by restarting the algorithm after a certain number of episodes and using the computed average as the new sampling policy.
The proposed algorithm LocalOMD also enjoys simultaneously two interpretations: one as a Mirror Descent type algorithm working at the global level, with single update performed at each iteration over the whole tree; and one as regret minimizers working locally at each information set, which makes it very similar to CFR algorithm despite fundamentally different approach.

---

We would like to conclude by providing the following interesting research directions.
Problem-dependent optimality For given game structure and fixed sampling policy n², is there policy-dependent lower bound O(vk(1> on the regret? We wonder if the k(a") quantity of Remark 2.3 denotes some sort of complexity related to the problem.
General game Using the same techniques Bai et al. (2022), in general sum game with potentially more than two players, LocalOMD can be shown to converge to an e-approximate normal- form coarse correlated equilibrium. Are convergences to other forms of correlated equilibrium possible using this fixed sampling policy framework?
On-policy algorithms Is it also possible to remove the anportance-sappling of the previous actions in the usual semi- bandit framework that observes with the current policy? The answer not obvious since the current approach heavily relies the fact that the sampling policy is fixed.
7 Acknowledgements
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23- 11----EE---0033 and through the grant DOOM ANR- 23-CE23-0002. It was also funded by the European Union (ERC, Ocean, 101071601) Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority be held responsible for them.
References
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal on Computing, 32(())48-77, January 2003. ISSN 0097-5397. doi:
10.117/5009333901988755
Bai, Y., Jin, C.,, and Yu, T. Near-optimal reinforcement learning with self-play. In Larochelle, H., Ran- zato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2159-2170. Curran Associates, Inc., 2020. URL httpptpss//pooceeeeaeaeeee neurips. EL http://///.///.....//a////aa/0t.
leaming Bai, Y., Jin, C., Mei, S., and Yu, T. Near-optimal learning of eetenssvve-frm games with imperfect information. In International Conference on Machine Learning. 2022.
Burch, N., Moravčík, M., and Schmid, M. Revisiting CFR+ and Alternating Updates. Journal of
Artificial Intelligence Research, 64:429-443, 2019.
Resa-BBanchh,, N. and Lugosi, G. Prediction, Learning. and Games. Cambridge University Press, Cambridge, 2006. ISBN 978-0-521-84108-5 doi: (0.1017/CB0997001154669
Daskalakis, C., Foster, D. J., and Golowich, N. Independent policy gradient methods for competitive reinforcement learning. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5527-5540. Cur- ran Associates, Inc., 2020. URL https: http://ppooeeee..eeeee/e/e pdf.
neurips www.eeee...nn.niii......eeee
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2111-2159 2011. URL http:
//jmlr. t/tmmll.ogg/apeeeeeeee www.oo/wg///.//.aaooooo 22t//cchiiiitc 1 html.
Fang, H., Harvey, N., Portella, V., and Friedlander, M. Online mirror descent and dual averaging: Keeping pace in the dynamic case. In Proceedings of the 37th International Conference on Machine Learning, pp.
PMLR, November 2020.
Farina, G., Kroer, C., and Sandholm, T. Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generatinn Functions. Advances Neural Information Processing Systems, 2019a.
10

---

Farina, G., Kroer, C., and Sandholm, T. Regret circuits: Composability of regret minimizers. In Chaudhuri, K. and Salakhutdinov, R. (eds.). Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pp. 1863-1872. PMLR, 2019b. URL http: //proceedings.ot mlr. press/v91 farina19b.... html..
Farina, G., Kroer, C., and Sandholm. T. Stochastic Regret Minimization in Extensive-Fore Games. In International Conference on Machine Learning, 2020.
Farina, G., Kroer, C., and Sandholm, T. Faster Game Solving via Predictive Blackwell Approach- ability: Connecting Regret Matching and Mirror Descent. In AAAI Conference on Artificial Intelligence, 2021a. URL https: //tpvvawvvvv///////////e///aaav. org/ ats//ab////////////////// 14358.
Farina, G., Kroer, C., and Sandholm, T. Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games. In AAAI Conference on Artificial Intelligence, 2021b.
Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Adapting to game trees in 7ero-sum imperfect information games, 2023.
Gibson, R., Burch, N., Lanetot, M., and Szafron, D. Efficient monte carlo counterfactual regret minimization in games with many player actions. volume 3, 12 2012.
Gordon, G. No-regret Algorithms for Online Convex Programs. In Advances in Neural Information Processing Systems, 2007.
Hart, S. and Mas-Colell, A. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 68(5): 127-1150, 2000.
Hoda, S., Gilpin, A., Peña, J., and Sandholm, T. Smoothing Techniques for Computing Nash Equilibria of Sequential Games. Mathematics of Operations Research, 2010. URL https: //kilthub. cmu www.eedudooooo www.nnoadeerffilee///////oo 12101699.
Johanson, M., Bard, N., Lanctot, M., Gibson, R., and Bowling, M. Efficient nash equilibrium approximation through monte carlo counterfactual regret minimization. In Proceedings of the I I1th International Conference on Autonomous Agents and Multiagent Systems Volume AAMAS '22 pp. 837-846, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 0981738125.
Joulani, P., György, A., and Szepesvari, C. A modular analysis of adaptive (non-)coovex optimiza- tion: Optimism, composite objectives, and variational bounds. In International Conference on Algorithmic Learning Theory, 2017. URL https://apt semanticscholar .org/ www.:oorpssoooorroee CorpusID: 28926102.
Koller, D., Megiddo, N., and Von Stengel, B. Efficient Computation of Equilibria for Extensive Two-Person Games. Games and Economic Behavior, 14(2):247-259, 1996.
Kozuno, T., Ménard, P., Munos, R., and Valko, M. Learning in two-player zero-sum partially observable Markoy games with perfect recall. In Neural Information Processing Systems, 2021.
Kroer, C., Waugh, K., Kiling-Karzan, F., and Sandholm, T. Faster first-order methods for extensive- form game solving. In Economics and Computation, 2015. ISBN 978-1-4503-3410-5 doi: 10.1145/2764468.27666 27644477...76....
Kroer, C., Farina, G., and Sandholm, T. Solving large sequential games with the excessive gap technique. In Neural Information Processing Systems, 2018.
Kroer, C., Waugh, K., Kilinç-Kas Karzan, F., and Sandholm, T. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179(1):385 2020.
Kuhn, H. W. Extensive games. Proceedings of the National Academy of Sciences, 36 36(10)570-576 1950.
Kuhn, H. W. Extensive Games and the Problem of Information, Annals of Mathematics Studies, 28: 193-216, 1953.

---

Lanctot, M.. Waugh, K., Zinkevich, M., and Bowling, M. Monte-Carlo sampling for regret minimiza- tion in extensive games. In Neural Information Processing Systems, 2009.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., Hennes, D., Morrill, D., Muller, P., Ewalds, T., Faulkner, R., Kramár, J., De Vylder, B., Saeta, B., Bradbury, J., Ding, D., Borgeaud, S., Lai, M., Schrittwieser, J., Anthony, T., Hughes, E., Danihelka, I., and Ryan-Davis, J. Openspiel: A framework for reinforcement learning in games, 2019. URL https: : //arii//aaiiia/iaaeeaeeeeeiaiaaa org/ 1908. 09453.
Laraki, R., Renault, J., and Sorin, S. Mathematical Foundations of Game Theory. Springer, October 2019. doi: 10.1007/978-3 0777/997833-300 3-030-266444 URL https: //tps:///hall http://aaaa.c.iccce...oeeessscee scwence/eaaaaiaeeeeeceoeoaaaaaae httph/aaal0000444
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/9781 0087//911111511144
Lee, C.-W., Kroer, C., and Luo, H. Last-iterate convergence in extensive-form games. In Neural Information Processing Systems, 2021. URL https: https://proceeddngg neurips httpppcrcc/p/////p/p/pp/p
.dfp.
Liu, Q., Yu, T., Bai, Y., and Jin, C. A sharp analysis of model-based reinforcement learning with self-play. In Meila, M. and Zhang. T. (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 7001-7010. PMLR, 18-24 Jul 2021. URL httph::t///pptt htttps://proceedings mlr
McAleer, S., Farina, G., Lanctot, M., and Sandholm, T. ESCHER: Eschewing importance sampling in games by computing history value function to estimate regret. CoRR, abs/2206.04122, 2022. doi: 10.4 00.48550/rrxi.2226..kk 0422 URL https: / //wii org/10. 100 48540/500/5 (0150//rrii /wroii/rivv..... 2206 .01122.
McMahan, H. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research, 18:1-50 08 2017.
Munos, R., Pérolat, J., Lespiau, J.-B., Rowland, M., De Vylder, B., Lanetot, M., Timbers, F., Hennes, D., Omidshafiei, S., Gruslys, A., Azar, M. G., Lockhart, E., and Tuyls, K. Fast computation of nash equilibria in imperfect information games. In International Conference on Machine Learning, 2020.
Nemirovski, A. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 15(1):229-25 251, 2004.
Nesterov, Y. Smooth minimization of non-smooth functions. Mathematical programming, 103(1): 127-152, 2005.
Orabona, F. and Pál, D. Scale-free online learning. Theor Comput. Sci., 716:50-69, 2018. doi: 10.1016/j.tcs.222 10.2.1 .011..11....2011....001.... URL. https::///// //doi. org/10. 1/111....1111111 tcc. 1017.11.00
Osbore, M. J. and Rubinstein, A. A Course in Game Theory. The MIT Press, 1994. ISBN 0-262-65040-1.
Ponsen, M., De Jong, S., and Lanctot, M. Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling. Journal of Artificial Intelligence Research, 42:575-605 2011.
Romanovsky, J. V. Reduction of game with complete memory a matricial game. Dokl. Akad. Nauk SSSR, 144:62-64, 1962.
Schmid, M., Burch, N., Lanctot, M.. Moravčík, M., Kadlec, R., and Bowling, M. Variance reduction in monte carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. CoRR, Abs//880.030053 2018. URL http: // http://aaivvvv//aa///a//eaeeaaaa org/ abs/ 1809. 03057.
Sidford, A., Wang, M., Yang, L., and Ye, Y. Solving discounted stochastic two-player games with near- optimal time and sample complexity. In Chiappa, S. and Calandra, R. (eds.), ), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Pulermo, Sicily, Itly], volume 108 of Proceedings of Machine Learning Research, pp. 2902-3002. PMLR. 2020. URL http: http::tttt/ooo httt:://proceeeings. mlr, wwwps//vssssveeee http///ddfooddddoo html.
12

---

Southey, F., Bowling, M., Larson, B., Piccione, C., Burch, N., Billings, D.. and Rayner, C. Bayes' bluff: Opponent modelling in poker. In Proceedings of the Twenty- First Conference on Uncertain- fyin Artificial Intelligence (UAI), pp. 550-558, 2005.
Steinberger, E., Lerer, A., and Brown, N. DREAM: deep regret minimization with advantage baselines and model-free learning. CoRR, abss20006.00410, 2020. URL https://arxiv. wwwxii..rrg/ab//0065. 10410.
Strens, M. A Bayesian Framework for Reinforcement Learning. In International Conference Machine Learning, 2000.
Tammelin, O. Solving large imperfect information games using CFR+. arXiv:1407.500 407,5042, 2014.
arXiv preprint
von Neumann, J. 7ur Theorie der Gesellschaftsspieee. Mathematische Annalen, 100:295-3200 1928. ISSN 0025-5831; 1432-1807/e.
von Stengel, B. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2): 220-246, 1996.
Waugh, K. and Bagnell, J. A. A unified view of large-scale zero-sum equilibrium computation. CoRR, Abs/1411.5007, 2014. URL http::/ttaaaee
arg/abs// 11///1111..111 1507.
Wei, C., Lee, C., Zhang, M., and Luo, H. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4259 4299. PMLR, 2021. URL http: http://proceeddngg mlr press/ cress/vv34/wse www.//ee21...a.....eeeee html.
Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. Online reinforcement learning in stochastic games. In Guyon, I. Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Cur- Associates, Inc., 2017. URL https: sstps://proceedingg www.eeeinnnnnnniin.ooomm www.eees.....pprr/.///e poppp///////p///////////// Paaea pdf.
Xie, Q. Chen, Y., Wang, Z., and Yang, Z. Learning zero-sum simultaneous--ooe markoy games using function approximation and correlated equilibrium. In Abernethy, J. and Agar- wal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3674-3682. PMLR, 09-12 Jul 2020. URL https: / patpss////occeding.... mlr. wwtssssvv2//xxieeee html.
Zhang, B. H. and Sandholm, T. Finding and Certifying (Near-) Optimal Strategies in Black-Box Extensive- Form Games. In AAAI Conference on Artificial Intelligence, 2021.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115, feb 2021. ISSN 0001-0782. doi: 10. 145/444434 URL https: //doi. ort.:/..........1 1145/3446776.
Zhang, K., Kakade, S., Basar, T., and Yang, L.. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. Advances in Neural Information Processing Systems, volume 33, pp. 1166-1178 Curran Associates, Inc., 2020. URL https: http:///poeeeenn...e/ees www.oceedinnnnneuripps... wwt..niis.....ppree///.......e pttpppppp//22//ilee 0e0eee00050221022200000000111111 e2d-7edddPPpps .dff.
Zhou, Y., Li, J., and Zhu, J. Posterior sampling for multi-agent reinforcement learning: solving exten-
sive games with imperfect information. In International Conference on Learning Representations, 2020. URL https://openrevieu nwt/pdffttdetett ?
ET4FPS.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. Neural Information Processing Systems, 2007.
13

---

Appendix and Checklist
A Related works
In this section, we review previous works on learning an e-optimal strategy in IIGs.
Full feedback When the game is known, that is the information set structure space, transitions probability, and reward function are provided, first line of work recasts the setting through the sequence-form representation of a game as linear program which can be solved efficiently (Ro- manovsky, 1962; von Stengel, 1996; Koller et al., 1996). A second line of work relies on first-order optimization methods for saddle point computation (Hoda et al., 2010; Kroer et al., 2015, 2018, 2020; Munos et al., 2020; Lee et al., 2021). In particular Hoda et al. (2010); Kroer et al. (2018) relies on the Nesterov smoothing technique Nesterov (2005) whereas Kroer et al. (2015, 2020) use the MirrorProx algorithm (Nemirovski, 2004). These methods have a rate of convergence of order (poly(H,, Ax, By)/E).
A third approach, counterfactual regret minimization (Zinkevich et al., 2007), leverages local regret minimization, i.e. minimizing type of regret at each information set. Popular algorithms are based on the Pegret-matching algorithm (Hart & Mas-Colell, 2000; Gordon, 2007) such CFR algorithm (Zinkevich et al., 2007) or based on a close variant of regret-matching e.g. CFR+ (Tammelin, 2014; Burch et al., 2019; Farina et al., 2021a). Note that other local regret minimizers could be used, see for example Waugh & Bagnell (2014); Farina et al. (2019b). These algorithms enjoy a guarantee of convergence of order (poly (H, Ax, By)/E²).
Nevertheless, all the methods described above need explore the whole information set tree (or the whole state space) in order to compute one update. The cost of one traversal is of order O(X + Y) if the transitions and the actions of the other player are sampled; see for example the external- -aaepll- MCCFR algorithm (Lanctot et al., 2009).
Trajectory feedback A way tackle the aforementioned issues is to consider the agnostic setting where the agent has no prior knowledge of the game and only observes trajectories of the game. Precisely, the rewards and the transition probabilities are unknown.
Model-based A first method to deal with this limited feedback is to build a model of the game and then run any full feedback algorithm in this model. For example, Zhou al. (2020) use posterior sampling (PS, Strens, 2000) to learn a model and then use the CFR algorithm in games sampled from the posterior. They obtain a convergence rate of order Oppoly(H. SH, A, B))s²) but only when the games are actually sampled according to the known prior. Instead, Zhang & &Sandholm (2021) relies on the principle of optimism in the presence of uncertainty incrementally build a model of the game. Then, the CFR algorithm is fed with optimistic estimates of the local regrets. They prove a high-probability sample complexity of order Opooy A, B)
Model-free Another line of work (Lanctot al., 2009; Johanson et al., 2012: Schmid et al., 2018; Farina et al., 2020) directly estimates the local regret via importance sampling that is then fed to the CFR algorithm. In particular, the outcome-sampling MCCFR (Lanctot et al., 2009; Farina al., 2020) builds an importance sampling estimate of the counterfactual regret by playing according to well-chosen balanced policy. Intuitively, this policy should ensure to explore all the information sets. Note that, depending on the structure of the information set space, playing uniformly over the actions each information set is not necessarily good choice. Instead, Farina al. (2020) propose as a balanced policy to play action with probability proportional to the number of leaves in the sub-tree of possible next information sets. In particular, the outcome-sampling MCCFR algorithm requires the knowledge of the information set space structure to build its balanced policy. Nonetheless, in order to obtain e-optimal strategies with high probability, MCCFR needs at most (( + By)/+?) realizations the game (Farina et al., 2020; Bai et al., 2022).
Later, Kozuno et al. (2021) proposed to combine Online Mirror Descent (OMD) with dilated Shannon entropy as regularizer and importance sampling estimate of the losses of player, see also Farina et al. (2021b). They prove sample complexity, for the proposed algorithm, IXOMD, of order
14

---

+ Interestingly, they do not need to know in advance the structure of the information set space obtain this bound. However, the sample complexity of IXOMD does not match the lower bound for this setting which is of order ( + By)/s* Recently, Bai et al. (2022) proposed the Balanced OMD algorithm that enjoys also relies on OMD but with a dilated entropy weighted by the realization plans of balanced policies as regularizers. For this algorithm, they prove sample complexity of order (HH3(Ax + By)/E?).
Perfect information Markov game Another line of work considers Markov game Kuhn (1953) with perfect information and limited feedback. However, it does not assume perfect recall. Sidford et al. (2020); Zhang et al. (2020); Daskalakis et al. (2020); Wei et al. (2021) consider the case where generative model is available whereas Wei et al. (2017); Bai et al. (2020); Xie al. (2020); Liu et al. (2021) deal with the trajectory feedback case. Although this setting related to ours there is no direct comparison between the
B Regret estimation
In this section, we aim to establish Theorem 2.2 of the main paper. We start by stating Bernstein-tyee inequality that we will use multiple times. It can be found e.g. in Exercise 5.15 by Lattimore & Szepesvári (2020), We provide a short proof below as we did not find any for this precise statement.
Lemma B.1. Let he(t) be a sequence of random variables with respect to a filtration F, and 7 > be fixed constant such that for all 1, -U S 1. Then with probability of at least - 8':
Σ -U--EU9---3 S
E [(
1 4
log( log(5)
1 8
Proof. For any & [T]. using the inequalities exp(x) < 1+ for all 1 and 1+x exp(x) for all x E IR, we have
E exp (~U*)
< [1 + 20 + ((
+ E [ + 2 (
- exp (
+ ( ((0))1=-11])
This implies that the random process (St) defined by
S. = exp Σ 7 (U* -E E Σ>eE 2 [(U)))](((-1)
is a super-martingale, with So = 1. Using the Markov inequality, we then get
P log log(Sr) 1 log
1 ) ST 8
1 s E'E())) S
which immediately yields the stated inequality with probability at least
This lemma is then used for Theorem 2.2. The filtration (F" (Pem will be used, such that J is the geema-algebra of variables of the self-play algorithm up to the exccution of episode t + 1.
Theorem B.2, Assume that the estimated losses are obtained with a fixed positive sampling policy ne as above. Then, for any sequence (j² (eeet) of miin and any 8 E (0, 1), the following bound holds with probability least 1 8
RT min < max RTiin 0} 4V1HHK(UO)T
where
Axx Mx+1) and x(x²)==
Σ Σ
log
NEX aEA, (i,(2,))
15

---

Proof. We want to show that, with probability at least - 8, that
Σ [ m1 = WiHHM(HOTT
holds for all j min- Then the property follows after re-organizing the inequality and maximizing over μs. In order to do so, we divide this term into two parts:
Σ
c - 2, mi - -mii -m:)-
Σ Ce 2 p,pi.
ui:
EST
EST II
We will furthermore assume that HT 2 uR(11), as otherwise, 4 WIHHn(10)T & 4HT and the property immediately follows from A S HT.
Upper bound of EST For all x E X' of depth h and A(x). we apply Lemma B. to the random process
U 2.a = -1 (==
with 8 5/x and fixed 7/ (0, 1] we will specify later. This yields, with a probability
least 1 - 8", that
T
T
E [ ( -== a=a
((-11
71
(ch)
{==a)_a=a)
Hq-1| + n
t=1
12
E
e
(2=x
Ft-1] -. 71
1=1
By definition of the estimated loss, e (-=)), / (z, = az) We thus divide by 46. a) both sides of the inequality, and the unbiasedness of the loss estimator yields
(x,a)) ((x S m Σ (x,
7/4 (z, a)
This inequality holds for all (xx, a) with probability of least 1 - 6Ax/(Ax + 1). Taking the scalar product with any μ E Tmin then gives
T Σ
(1, a) (x, a)
2
M1:
S m1
(e,,mi mn)
t=1
xE (EA(()
L =x(x²). $ MH +
Using 71 Vux(u)) < 1 (by assumption), finally yields
EST < 2/1HK(p*'T.
Upper bound of EST For this upper bound, we apply Lemma B.1 directly the sequence U (-,, We now choose "2 R4 (no further assumption is needed on 72 the sequence is negative) and apply the lemma to get with probability at least 1 6/(Ax 1)
16

---

T
Σ 1=1
c
E. 14:
S 72
E
Mi:
Ft
72
1=1
T
H1
(2, a) /1 (x, a1)
72
Σ
E
Σ
Σ
4
5t-
72
t=1
DEA dEA(())
T
H
/ (1, a)² /1: (z, a)²
(euccy-Schwwrz))
S 12H
E
Σ
Σ
72
1=1
#E aEA(x)
T
H
Mi. (I, a) Mi ax)
I 92H
E
Σ
1 _.
F(11
1=1
h=1
2E acA(())
T
H
e (zx (2,00,
(1
= H Σ
E
ΣΣ ZEN (E
Σ
F+1
+
(2,
(1, a)
= H22
Σ
(x, a)
+
(1,
72
1=1 DEX rEA(Z)
T
(1,
(as (x, 1)
S r2ll
Σ
+ -
(1)
722
DEX REA())
S 12ll I
72
Taking
V yr then leads to
Σ
(er ( 22/HHs(WeyT.
Summing the two inequalities yields the inequality of the theorem with a probability of at least 8-
C Balanced policy and
This section deals with the k(x²)) and local x(u²lz) of the main paper, and links it to the balanced policy μ²"
Recursive x computation Let n² be the positive sample policy. For any E Imin and æ E X of depth h, we define k,(("(())) the local sum of ratios against & in the subtree induced by x. i.e.
pnola', a')
Σ
Σ
x'EX, the history of a'Ee( 1 (1'()',)))
where, if (x), af... s/y, o²) is the history of (x',a').
(ne al'',a')= II u(a)la)).
We then formally define <(u*(z)) as <<u*lz)= = max (z))) For any a E 1mmns the following recursive formula stands
u(alx) a()( 1² (a(xr
ky(4)(x) = Σ
1+
Σ
kx(("(2') (z')
x' E.X. directly follows (z,aa
17

---

that follows from the definition of (z))))) The same kind of recursion can then be obtained for k())(z), because each appearance of μ in the previous equality can be maximized independently (depending on different information sets). This yields
k()(xz) = max
Σ
m(a 1 (a(ar)
1+
Σ
k(u(lat)
n(AA(E)
aEA((z)
x'E..xx' directly follows (x.a)
= max aEA((z) (a(z))
1
"( ((o)
a. direcilly fallows (2,a)
which allows for simple recursive computation of k(("lz)) Finally, once the whole recursive computation done, x(f()) itself can be computed by, defining X, the information sets of depth 1,
1((1))
Σ <(p(
31 BLEM
Balanced policy k(p=laa |x:) can also be minimized over 2r E IImin recursively from the leaves using the tree structure. Indeed, for each X, assuming that the minimizers of x(x*(=²) are already known for subsequent z', the policy μ² E AA(x) that minimizes the maximum along the actions a E A(x) can be computed from (1). Furthermore, we define AT a) and (xx) the total number of actions in the subtrees respectively induced by (I, a) and i.e.
AT (1x a) = (x..) is the bistory
Σ
AA(x') and (T
Σ ATx,a), eEA(Z)
we can show that min n Ellmin ((1))x)= (rr), and that the minimum is attained by the balanced policy μe defined by
n (a|z)) = AT a) AT(x)
Indeed, if we assume in (1) that the previous property holds for the k=(u|la |z'), then
A" (xx a)
x0(c² [x)
max aEA(z) (alx)
1+
Σ
A (x²))
= max
aEA(x)) μ (a|x)
x' xx directly follows (æ.a)
and the previous equality is minimized when the μ² (alar) are proportional to the (rx a), achieved by the balanced policy μ². With this policy, the same equality gives k(μ*(x) (x) = Az(x), which concludes the induction.
Finally, computing k(²*) yields
k(p²) = Σ x(u*(01)= = Σ A² Ax
31 EX
D Generalized dual stabilized online mirror descent
This section will establish the bound related to the updates (GDS-OMD) obtained with any Legendre function.
D.1
General Bregman divergence properties
We start this section by stating multiple properties of the Bregman divergence De for v convex function, continuously differentiable on an open Ω and defined on T2, proved by Cesa-Bianchi & Lugosi (2006).
Law of cosines: For any x e Si and w, z E Q the following cquality holds
(w(xw) = D (2 2) Dw (z, w) (V V V -2)
18

---

Algorithm 3 Generalized dual-stabilized online mirror descent
1: Input:
A sequence of dual increments ç
An open subset S2 R" and closed convex C S2
A sequence of Legendre regularizers (V²))e( on f2 such that for all & E (7), 1i+ vp is
convex
An initial primal iterate w EC
2: Output:
A sequence (w* xe(ty of primal iterates
3: Algorithm:
For t 1=110 to T
2f = (wD
v²+ 2' gt (wpi+((wr) (w"(
r+ = ViTt+ (1ptti((y(t)))))
w = IT IT (1
Bregman projection: : For a closed convex of Ω and V strictly convex, we can define the Bregman projection II over 52 by
I
(w)
arg min D (2, w)
sEC
This Bregman projection satisfies a generalized Pythagorean inequality, for w E Ω and C
(z w) 2 D (z, 11 (w)) + D (II (w), w)
Fenchel dual: We defined the Fenchel dual v of a Legendre function v for any & IR" by
V/ (E) = sup (E, w) ((w).
well
If consider Q² := (S). it can be shown that V is the inverse function of V over Q i.e. for any w E Ω V (w)) = w. Furthermore, for w, 2 E Ω
De (w, De (VV (z), V (v)).
Strong convexity: V is said to be 1-strongly convex with respect to norm ||-|| for all w,
(2) 2 V (w) + (V w) + ||w 211²
In this case, the Bregman divergence of the Fenchel dual Ap* satisfies for any εı, E2 E Ω*
D (E s |IE - 12
where |l. the dual norm of ||-I]-
D.2 GDS-OMD Analysis
We will assume in the following parts that the updates of the following algorithm are properly defined, which happens when all vectors y belong to the Fenchel dual space Q++1,* == Vi+++ (22). We make the same assumption on the regular OMD iterates 2f ggt
We start by giving equivalent formulation of the updates (GDS-OMD) through Algorithm Proposition D.1. Algorithm computes the updates (GDS-OMD) if they are properly defined, i.e. computes the sequence of primal iterates defined by
2+1 arg min (5", w) + Dwc (w, wo) + Deptti (w, w²)
WEC
19

---

Proof. By definition of w²+1 in Algorithm 3, we have for all iterations t E [T] and w E C
D Dyt-1 (w, /i++) v (Vo'+) w) Ci
('()) (w)+)(w) v (w]) (y w) +
(5", w) + (V'(w) (VV' (w)) +
(u't((w) v'(w) - (VVit) (w") VV'(w"), ("(w))w)) + Ci = (5', w) Daa (uc, w²) + De (w, + C2
where C1 and C2 are constants independent of the choice of w (but not independent of the other variables). As w++1 arg min Dæc- (w, w the updates of Algorithm coincide with the updates (GDS-OMD), as both minimize the same function at each iteration up to an additive constant.
The updates of Algorithm 3 are then used show Theorem 3.2 below. Compared to the ones of McMahan (2017) that also allow adaptive regularization, these updates do not suffer from the potential linear rates observed by Orabona & Pál (2018).
Theorem D.2. Let (w") be sequence of primal iterates generated by the updates (GDS-OMD).
with convex incremental functions. Then for any w² E D2
T
T
Σ (5', w² - -w²) S Dar (wi, w+) + Σ Dun. (VV'(w') - 5¹ (w))))
Proof. We can assume, without any incidence on the (w") (eE)) sequence, that v T++ T We also define for all E (T) the notations xp Tpt+1 TT' and
o' = (5' t ( + D (w+ w²) + Deo (wat1 .w'..
We then divide the sum into a stability and penalty terms:
Σ (c',ut u w!) = E0 (0'- - (5", (5', v))))
((5' wn)) ②t)
penalty
stability
and we look at upper-boundingg these two terms.
Penalty term: For all t [T], using the law cosines on the Bregman divergences of Vi and st, we have the two equalities:
De (wl, w²) De.(ww xb-1) + De (6+41 w²) - -VVV'(w) - ( wl w
and
Dir (w", w/) D (w+, w + + (Vi'(w (wtttt))) ) wt w(11).
Summing these two equalities, we get
Dæs (wo w²) + Dip (wt, (wt,w")) w
-Dg (wi, ra*t1) 1) + Des (vitt), .wt) ) + (1itt) w²) (5 wt 10 -
= Dyc 1 (w", l + - (,,ttt)
as by definition of att1 and ght1,
Vyt+i (wtt1) 42 - VV'(w')+ (w"(
Furthermore, as s+1 11 (1)tt),, the Pythagorean inequality for the Bregman divergence yields that
Det-i(wl, w(11) D Dorto (w,, w01 )+ + Ditti (w"+1 ,6(t1)= D Deeti (w², w wl)).
20

---

Injecting this in the previous equality and telescoping leads to
T ( - w()),/'))
= D (w ""w),,")))))) + DD (wi, w²) - D Docis (w), eltt1)
1=1
Do (wl, w²) + D (w! w-) D Deeti(wl w(()))
1=1
D Derti (w), w-) - Derti wltt)
S D yr (wi, w
as NT WT++1 by definition.
Stability term: We first notice, for all / E [T], that
( d² (5", wt w² w²=1) D (wt+1, ww)
D (1ttt ,w²)
S (5", wt r0 D (1+t+1 o1 w()
I (5t wt w- D (w+++1 w00)
where
a+t1 == arg min [<5* (b) Deg (w), w*)]
wen
is the wt iterate that would be obtained using a classical OMD step with vf, without the stabiliza- tion. By optimality, verifies
(w
-
and the law cosines then yields
D Dec (w", w²) D (w² 1) D (w w²) - (VV'((W) (V w² w
(0) D y (wo,, w + Dv (wx+11, w0) - (5", w r
Plugging this in the first inequality, we directly get
w0) - S Dus (wo,
and conclude using
Duc (w,, w = Dip.. (VV(()+))) (v)((w"))
Der. (VV'vVVV - vv'(w'))
E LocalOMD analysis
This section will focus on the dilated entropy approach to extensive-form games, and especially on the updates
arg min (P. + D (²) + Ddil Da -l (u,u+
(GDS-OMD dilated)
that are used by LocalOMD.
E.1
General analysis
The following proposition shows that each update of this form be computed recursively starting from the leaves of the tree. It requires for any f. E [T] the vector q² that satisfies for any x E X' of depth h
ot (x)
min
(7--
D dil, ( 1²) + Dill dil,
Patti-at (w,
(
pellmin
where - x means that the quantity considered on the sub-tree induced by x rather than the full information set tree, and dh: is defined in Appendix C.
21

---

Proposition E.1. Consider the previous updates (GDS-OMD dilated) and the vectors (em above. Both 4 and of can be computed recursively starting from the leaves of the tree through
p + arg migminnfe h2 (M) and (x)x) min (x)
AED)())
(EAA(=)
where
(x) = (f(z,))))) + (1) (a(u, + (a) Dz(u (-|x))
and the regularized loss (xx, a) is defined by
((r, a) (x) at ex'e directly follows (z.a)
E
d())).
Proof. First, note that + the unique minimizer associated each q' (x1) for 21 the information set of depth 1. Indeed, each of the sub-tree induced by the x1 can be considered as an independent problem. The idea will be to recursively minimize the q¹ (xx, starting from the leaves (i.e. the final information sets zz), and compute p²+ ([z) as the associated minimizer at each information set.
This minimization is done through, each i E X' of depth h, with decomposition of q' (1:). Indeed, separating the induced tree by x: between the root and the rest of the tree leads to
(xxx) arg min pellmin
(z, )), ). (1/a((z)) (u( (+(x))
+ (1/a t1 (z) - 1/))(x)) Dz(u(-1)) (11))
Σ p(aaz)
Σ
:Pht1:/ ) + Dat dil (1, + D Ddil--x'
a (M, u²)
+
eEA(x)
x'E directly follows (a,,0)
arg min A(A)
(.H, + (1/a Dz (1, + -1/(()) D Dz (112))
Σ m(a) (E)(x)
Σ
('(x')
2'EX1x directly follows (ur,a)
arg min (())(=)
(e(,,),,) + (z) + -
(x(
arg min minh (p) μεAA())
as each minimization on / E Imin is done on independent components. This justifies the recursive computation of both u²*1 and q'
This proposition directly provides the proof of correctness of LocalOMD, for which the regularized losses at time step are non-null only on the trajectory with
(xx a) = [[ ff
M..
We now want upper(bbund the regret associated with this sequence μ², The following lemma gives a valuable property that links the regularized loss and the estimated loss.
Lemma E.2. For any policy p' E Immin we have
(2,4%. - -ML (?.1h))))) G
ZEX
where q = mil (2,12) + Ddll (14, Ddil Dait1-or (1,
22

---

Proof. By definition of we have, for any Ilmin
(T.1h.)
(2,
Σ
Σ
(T,))
Σ
((ar)
ZEd aeAz
='((,,))>r''
(2.
ΣV
Σ
Σ
ZEX aEAp (x,0)tt'
(2.1ht) + Σ
x'EX
(P.,1h.) (dd
E d'(x') x'EX
x'ex
in which we identified the components of the second sum as the set of non-initial information sets. We then conclude using Exex, (x) q² by definition of the qº terms.
This lemma is then used to upper bound the estimated regret of the sequence generated by the updates (GDS-OM) dilated). Indeed, while we could apply Theorem 3.2, the associated stability term, which depends on the Fenchel dual of the dilated entropy, is not easy upper bound. Nonetheless, the proof of the following theorem is mostly the same but with slightly different definition of the stability and penalty terms.
Theorem E.3. Let (J())E(T) be the sequence of policies generated by the updates (GDS-OMD dilated). The following bound holds
iT S sup D ( at aleTTm
Σ a' (<))))(())) PEN
(V
(a, (V
a'(x)
peualty
stability
Proof. The separation between the stability and the penalty terms is the same as Theorem 3.2, but with ÿ (of Lemma E.2) defined after the projection rather than before. This leads to the decomposition
RT
(
Σ
((e ph g¹)
max ETTmin
penalty
stability
Penalty term: This part is similar to the general theorem. The optimality of p leads to, for any e [T)
v (u(+2) - g" (Vi. + (v1.).
where g E Q and xp = g++1 - V.. We use the same two law of cosines as in Theorem 3.2
Der ph.) D (u /1 + D (Hf." .P..) (ve'((t) vw' J. - p1:
(p = D (Mi (111) D (1tt1 .11.) (ve'(utt)) V ), -m4t) 1+1
which yields by summing
Dy (pl. pi.) + Det (HTss
Doitt (Dtts 1.tt + Da (Hft 4+1 .14.) + (oft ( (2 (e+ -1t11)
= Detti + g (2,
23

---

where we used (g.
- pi. 0 from the orthogonality. Summing over i [T] then gives, by
telescoping similarly to the general theorem,
T
T
q' (e.wi.)
Σ E
(uls + D D (ul: Detts mit!
D (H1:s)))) Derti (plo
Dey (11:
Stability term: From Lemma E.2 used with /1 ji,, we get an alternative expression of the stability term
(2.1h.) - ((,nt) - Σ (1)(4))
ZEA
This shows the stability term be decomposed in positive linear combination
( pi. 9' (1)) ((((e)) (1 -(xx)))
ZEX
and we will individually upperbound each of the terms of the combination. The method is again similar to the general theorem, but locally with the regularized loss. Defining w a az(x) and o == we+l V we have
(z, ). p (11)) (x)
(ar, )).1 11. (+|x)) 1 (-1e)
- Duy (1+*) (z))),(((())))) - Drp (11)) (1(a))
(2, ),p
( (1(x) x
Dw (1e (1 (-12), n² (1x))
(z,, (. (1|x) -
Dug (110), n¹ (+xx)
where
(-1x)) arg min
((((E))))) + D (it, n² (-1x))
MER,
By optimality, / (-1x)) verifies
VVL Vu (() - (z,
and the law of cosines yields
0 Dæy (4' (-1z), n² (-1z))
Dws (n' (-1x), (-1z) Dvg (H0),
VV - Vy
(-(z)) - -1 / (-1=))
= =Dy (x (-1z)) D ug (7 (11) (+1z)) (e :), (1 2-12))
Plugging this in the first inequality, we directly get
(e (z, ),, n² (-1x) of (x) < Dwy (1'((( (411)
and we get the individual upper bounds with
Dye (n*(1a) (.1x), (z+) (+(x)) = a' (x) (x
= a' (x:) (VW, (-(2)) (V
=a(r)DD v: VV
at))) 2' (z, -), (V
This upper bound on the estimated regret is then used with the learning rates considered in the main article.
24

---

E.2
Optimal rates analysis
We first consider the optimal rates of the main paper.
Theorem E.4. Using LoCalOMD with p² as the uniform policy, with the learning rates (x)
n/K((((1)) where ? Vlog(A)) ()(g(A))(e))/((HH) and with V, the Shannon entropy V. Vz(n)) EOEACE) m(a) log(u(a)), the regret is bounded with a probability at least 1 - 8 by
A S (4+2V3) H Voog((/)/(((
where L 1og(2(AA 1)/8).
Proof. We apply Theorem E.3, using the relations (x) =
and I (-=at]] 2
(1.()) (x, )) We again separately bound the penalty and stability terms.
Penalty term : We will denote by PEN this term defined by
PEN
Ddil (1T.. Ellli
sup
By definition of the dilated entropy, we have, using that n² is the uniform policy and that the Bregman divergence of the Shannon entropy is the Mullback-Leible divergence,
PEN = sup Σ (1,(0))(('11))) Do(u' (1p0,, (1)
jtt Ellmtn DEX
1 sup
(1(()))((111))
n ((aa))))((((((aa)))aa))) aEAlx)
Σ
17 nt Ellman NEX
(z)(z)
(=)=)()))1)) sup 1] Tt TEX
1
Σ log.)/
(i)(x)
aEA(x)
log(A)
(l.(c)
" p Elmin TEx (1) =((0(z))
sup
log(A)
(l.(ar sup
1 (2',, a²)
Σ
Σ
sup Ellmin 1= xx,
"
pl. μ ET e'Ex history of (EA())
1 (2t, aa),aa)
log( A)
M4. (x)
E
E
Mhe (at,, aa)
11
h=1 Mut Elimin x
sup
Ms. (i) H Emmli E'E i history of (EAA))
sup
1 (ol
log(A)
Σ (1,(z)
Mhel ,a)) Mh. (2)
(by independance)
sup
E
E
1
A=l pl Ellmin Te,, (i.(r)
x'EX(a is the history o' d'EA(rr)
log(A)
Σ
E
Σ
sup
(i,("',a))
"
h=1 pl Ellmin reAr E lat history of A(al)))
log(A)
(2,)
sup Σ Σ
pl Ellmin o'EX'''EAl (x'()aa a!)
"
(A)
HK((²)
"
where Xr is the set of information sets of depth h, the two sums being later merged on the basis of perfect recall. We now look at the stability term
Stability term: : We will denote by STA this term defined by
STA Σ Σ ('()))((())D
1 1 (x,-), vV,(((((xx)) a²
El
25

---

We first look an upper-bound of D -V (1))) or- der to do so, we upper-bound (in the symmetric matrix sense) the Hessian of Vi on I = V (u) (+1)))))) ,ا. (x, / [0. 10.11].
a'(a)
Because (z(1) A(e)(a)) (laa) log(u(a)) is the Shannon entropy.
(V)(()((a) = log(u(a)) + and thus ()) Diag((4uula))eeAta)
and the Hessian of V is given by
Vrr V (Z) Diag(u(())ae
In particular, upper bounded on by the matrix D defined by
D₁ = Diag(u(a))aaa
This yields that
D (V.(((. - at(x) (z.)), (0,,((()))
s 2 a'(x)
1 (ax (1pp))))pp
Σ (x,
20 (x)
aE.(m)
which leads to
STA S
Σ (z,
2a (
aEx
oEA(Z)
(x)
1
Σ (a= (alo))
(z) <(p))z) aEA(x)
ZER'
We can first notice from recursively comparing the minimizer j (-1oh) with (-(x)) that the regularized loss E, (a))) satisfies
(aih) < (,--", A.-0)) ,1441
re-using the notation at the beginning of the section, because the regularization does not evolve with time. The difficulty now to upper bound STA with high probability. In order to do so, we use the Lemma B.1 on the sequence (U") (U'))E(T defined by
(i(() U²: Σ (z=nt] (x) x(u(lz) aEA(2)
Σ
ZEX
with > (0,10 }} and 8' 8/2. This yields with probability at least 6/2
T
Σ
U²
Σ E B +
E [1)))(511) + +1/r.
On the one hand, we have, using tx (att) S x(u*)z)
and the previous inequality that
E U < Σ (z))'(())
Σ
(C--
Ph:
ZEX
aEAlm)
< Σ (x))
ZEX
< H²
26

---

On the other hand, using the same inequality,
(z)(z) ( {== (i.(() aEA(x)
Σ (a=at) (2(0), Ft-1
E [(("))| = E
(x) E { (Pi(a)² (' (alx) I -===1,] ())(
$ HE
F(-1
ZE.
aEA(x)
(1,()) Σ (a=ah} (a F1-1
S H
11,(z)
ZEX
aEA(m)
S HHs((()
(x))))()))
Σ
(E
SEX
aEA(x)
< HH((") SEX < HH'((F))
Σ (x)
The following upper bound on the stability term thus holds
STA Sn H2 :)
Taking y = =1/(H<k(p²) we obtain
STA STA n H2(x((())
As the bound of the theorem trivially holds if < ux(u") (the regret being bounded by T anyway), we even have assuming 7 2 ux(x")
STA S 3T
Conclusion: Combining all the previous bounds, the estimated regret is bounded, with a probability of at least - 8/2 by
RT log(A)
Hx((m)) 3T
"
Taking 7/ /log(A)ss(e)))(33T)) we obtain
RT 22/3 Tog A)ux((OSTT.
We finally conclude by combining this bound with Theorem 2.2 for the true regret, using 8'=5/2. such that the two inequalities hold with probability at least
E.3 Adaptive rates analysis
We end this appendix by considering the adaptive setting. We will assume that all regularizers v are 1 I-strongly convex with respect to some norms I|- and we will define
Ce
sup D=(p,
ZEX
Ci:
sup
zEX,aEA.
where 2²2 is the initial policy considered in the algorithm and [[z,a) is the loss vector ((x,,) equal to 1 for A(x) and 0 for a' E A(z)) (a). The following theorem is the formal statement of Theorem 4.1 the main article. While being quite general, the upper bound is unsurprisingly not as tight the previous one.
27

---

Theorem E.5. With such regularizers, assume that the learning rates are locally decreasing and let d2,2 Ryo be two constants such that for all information set x X.
T
max [E[--] (x)
()()))
S A and 1/1² (z)
1/n"(x) + Σ n (1))) (z=s)) S A2VT t=1
Then with a probability at least
- 6, the regret of Algorithm 2 is upper-boundee by
RI
max < 2 [ + Co 22 + +4/ (H(())) VT
where: lAx 1)/6).
The proof of this theorem will be based on the following lemma that bounds the regularized loss using the constant above.
Lemma E.6. For all [T] and h [H].
2 (of)) S (1+ (())
Proof. The proof done recursively on h, starting from the leaves. Indeed, for H, the property immediate as 0% (aa))) I 1/10 (abnl<))) I k(p*(a))) we assume that the property holds for depth h > 1, then
ah = min ((o))
(Pr.1)
Dr (4. (H, + (न:3)( ((x))) (/(x1)
D2 (M, pe (-la/))
(-1a))
( (((01))
1
D2 (4"(H)))
< (af) + A1
Then
(h-1(ah-1) (Ch-1 +
S (1 (/
$ (1 +au
$ (1 + (CC))((()))))))
which concludes the induction.
L
Proof. We now prove the theorem. We start with the estimated regret, that decompose between the penalty term and the stability term using theorem E.3.
Penalty term: The penalty term PEN is bounded by
PEN < sup
Delll (nf p1.)
1 ellmin
(1)(() Elliinn DEX o7 (x) pn. (x)
Da (+t))
sup
Σ (x)
< CTdaVT
sup
atellmon
dE
Stability term: For the stability term STA, we rely on Lemma E.6 and the 1-strong convexity of V with respect to Il. (see Appendix D.1) and get
28

---

STA
E ('())
-VV.(at((1b)) - a())) (x, ) Vy vVx(ei
(1,
(x)
[=1 xEd
11)(2)
11
1=
(z)
T
p= (1.()) (((ah))
(1(2)
(x
ElEEE
(1.(2r
A11+A))
n (x)
(z)))[(==)) (-=
(2) xx)22x)2
n' (-=ع) (z) ) k()))z)
tl
< C( Σ (1)
CC++A)CCCCR(PT 22
Conclusion: By summing these two upper bounds we get
पt S (1 (11 X2l )2|21] VT
< 2 X1) Cg X2
The bound finally obtained using the Theorem 2.2 that holds with a probability of least 1 and links the estimated regret to the true regret.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims are proven in the theorems or observed in the experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
29

---

Answer: [Yes]
Justification: Some limitations and possible improvements are mentioned the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well sell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only lested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- lant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proofs of the theorem (and the exact statement of Theorem 4.1) are provided the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All implemented algorithms are fully specified. open-access library (OpenSpiel) is used for an implementation of the games.
30

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer:
[Yes]
Justification:
A link to an anonymous repository with instructions to run the code is provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guide Snuiides/Coeeuumissee wttpsubbiisioooooioocoooocooe for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. wttpc//cccpppppcc.ecee gwwdes// SonddeSubmissioni
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
31

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The few details necessary redo the experiments are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The variance over the multiple simulation is visible on the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
The experiments were run personal computer as they do not require heavy computations.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: wttpppscccppppcceeeeieeee wewiiccccieennnn
Answer: [Yes]
Justification: the research conducted in the paper fully conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is mostly theoretical and not aware of any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
33

---

Justification:
This work presents no risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original paper behind OpenSpiel cited. The version used and the license are specified.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
34

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "ft3vhv8QGd", "reviewer": "Reviewer_1VRY", "summary": "I reviewed an earlier version of this paper. While I have some additional comments, my review is largely similar to my previous review, since the paper has only a few minor edits relative to the previous version, as far as I can ascertain.\n\nThe paper introduces algorithms designed to approximate Nash equilibria in zero-sum imperfect information games (IIG) with trajectory feedback. Specifically, the authors focus on the fixed-sampling framework. Past approaches have struggled with significant variance, largely due to the utilization of importance sampling across action sequences (McAleer et al. (2022) provide an algorithm that doesn't require importance sampling, but their techniques don't generalize to non-scale invariant regret-minimization-based algorithms such as OMD).\n\nThe proposed approach employs an adaptive Online Mirror Descent (OMD) algorithm. This involves using adaptive learning rates along with a dilated regularizer. The paper demonstrates that this method ensures a convergence rate of O\\tilde(T^{-\\frac{1}{2}) with high probability and exhibits a near-optimal dependence on the game parameters, when employed with appropriate choices of sampling policies.", "questions": "No specific questions beyond the weaknesses mentioned above.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a strong technical contribution in producing an adaptive trajectory-feedback-based adaptive OMD algorithm that doesn't rely on importance sampling and generalizing DS-OMD to use time-varying regularization.\n\nThe paper provides empirical evidence for the convergence and variance of their approach, compared to other approaches in the literature, and also provides code for their algorithm.", "weaknesses": "The paper could delineate its contributions better. As noted by most reviewers in a previous submission, the similarity to the regret circuit decomposition of CFR is apparent (and noted by the authors). Still, the difference could be further highlighted in the contributions, especially since this was confusing for several reviewers last time. A note was made by the authors last time regarding the interpretation of their method as regularization at the global level (whereas CFR doesn't have this sort of interpretation). While it is mentioned now that the proposed algorithm is an instance of GDS-OMD, I think these things could be further emphasized throughout the paper.\n\nAlong the same lines, one of the reviewers pointed out last time that things like $h_t$ and $q_t$ are not defined in the main body, and as far as I can tell, this is still an issue, even though the authors indicated that this would be clarified (even if not at the detailed technical level as done in the appendix) in the main body. It would be good for the authors to implement these changes, given that they assured the reviewers they would do this to improve the presentation.\n\nOne of the reviewers noted last time that the motivation for variance reduction is unclear. I agree with this. While the reviewers mention that variance reduction becomes a concern for performance in function approximation settings, it would be nice to see this in their experiments (since the current empirical evidence for the provided algorithm doesn't seem to indicate that there is much gain in performance beyond the variance reduction with the current approach).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first thank Reviewer 1VRY for taking the time to review our submission and for suggesting improvements. We address them below.\n\n> The paper could delineate its contributions better. As noted by most reviewers in a previous submission, the similarity to the regret circuit decomposition of CFR is apparent (and noted by the authors). Still, the difference could be further highlighted in the contributions, especially since this was confusing for several reviewers last time. A note was made by the authors last time regarding the interpretation of their method as regularization at the global level (whereas CFR doesn't have this sort of interpretation). While it is mentioned now that the proposed algorithm is an instance of GDS-OMD, I think these things could be further emphasized throughout the paper.\n\nLocalOMD indeed enjoys at the same time a local interpretation (as CFR) and a global interpretation (as the application of GDS-OMD updates). This is actually a unique feature of our algorithm.\nAs noted by Reviewer 1VRY, we mention this particularity several times:\n- At the beginning of the contribution section (l. 81), pointing the similarity to a paper studying a CFR approach.\n- In the local loss paragraph (l. 251), dedicated to this idea.\n- For justifying the use of the adaptive rates (l. 273).\n\nWe propose to add to the conclusion the following sentence:\n\n“LocalOMD enjoys simultaneously two interpretations: one as a Mirror Descent type algorithm working at the global level, with a single update performed at each iteration over the whole tree; and one as regret minimizers working locally at each information set, which makes it very similar to a CFR algorithm despite a fundamentally different approach.”\n\n> Along the same lines, one of the reviewers pointed out last time that things like \n$h_t$ and $q_t$ are not defined in the main body, and as far as I can tell, this is still an issue, even though the authors indicated that this would be clarified (even if not at the detailed technical level as done in the appendix) in the main body. It would be good for the authors to implement these changes, given that they assured the reviewers they would do this to improve the presentation.\n\nIndeed, the notations $h_t$ and $q_t$ are only defined in Algorithm 2 in the main paper, and not directly in the body. We tried to include them in the main text after the last submission with some necessary explanations of where these two terms come from to avoid further confusion. In particular we would need to reproduce appendix D.1 of [1] or appendix F of [2] about obtaining a practical implementation of the GDS-OMD update. However, this would obfuscate the main message of this paper with technical details already appearing in the literature. That is why we finally decided to skip them. \nIf a reviewer thinks that those explanations should be inserted here from existing papers, we could use the extra-page to include them nonetheless.\n\n\n> One of the reviewers noted last time that the motivation for variance reduction is unclear. I agree with this. While the reviewers mention that variance reduction becomes a concern for performance in function approximation settings, it would be nice to see this in their experiments (since the current empirical evidence for the provided algorithm doesn't seem to indicate that there is much gain in performance beyond the variance reduction with the current approach).\n\nThe high scale of the rewards is an issue that currently prevents the practical implementation of Mirror Descent algorithm with trajectory feedback: as explained at l. 258, the reward can be of order $\\mathcal{O}(A_X)$, which is incompatible with the function approximation settings. The main argument favoring the fixed sampling framework is that it allows the rewards to stay of order $\\mathcal{O}(HA)$, which becomes manageable. \n\nWe have included experiments demonstrating that this approach does indeed reduce variance in relatively small games. However, this issue of high variance is less significant in the tabular setting. Additionally, demonstrating that this modification enables function approximation with the trajectory-based Mirror Descent approach would require a separate paper, given the extensive technical adjustments needed to adapt a tabular algorithm to the function approximation setting, which is beyond the scope of our current submission.\n\n\n[1] Bai, Y., Jin, C., Mei, S., and Yu, T. Near-optimal learning of extensive-form games with imperfect information, International Conference on Machine Learning, 2022\n\n[2] Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Adapting to game trees in zero-sum imperfect information games, International Conference on Machine Learning, 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZCE8Y2rjNm", "reviewer": "Reviewer_yah9", "summary": "The paper studies the extensive-form game under the fixed sampling policy framework. It proposes the algorithm based on online mirror descent. The paper gives near-optimal regret bounds for the proposed algorithm, under different learning rate settings. The algorithm is justified with experiments.", "questions": "From the theorems the fixed and adaptive rate bounds have the same dependency on $T$. Is it correct to understand the motivation of the adaptive rate is only to remove the dependency on the importance sampling term $\\kappa$? When the balanced policy is used as the sampling policy, $\\kappa$ is reduced to a game-dependent term. In this case, is it correct think the adaptive rate setting as unnecessary?", "limitations": "/", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The the paper has detailed introduction and literature review, with a clear description of the problem setting and framework. The paper also makes sufficient comparisons to existing works under the same or different framework. \n\n2. The result has optimal dependency on $T$ and near-optimal dependency on other game-related parameters. The removal of the importance sampling term in the fixed-rate setting is a good contribution. \n\n3. The paper justifies it's theory with experiments. It makes comparison with a benchmark method and experiment result looks convincing.", "weaknesses": "1. The framework itself is still confusing. While the authors made some discussion of the framework in section 2.2, the advantage of fixed sampling policy seems not reflected in the paper's theoretical result. And in terms of the regret, the paper's result doesn't improve the regret of simultaneous regret minimization procedures. \n\n2. On the explanation of the theory, the paper can be improved by adding comparison to more benchmarks. The paper only compares the result with the result of simultaneous regret minimization procedure, and the conclusion is the bound matches but doesn't improve the existing result. It could be helpful to understand the paper's result by comparing previous results under the same fixed sampling policy framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer yah9 for the overall positive review. We would like to answer the points made below.\n\n> The framework itself is still confusing. While the authors made some discussion of the framework in section 2.2, the advantage of fixed sampling policy seems not reflected in the paper's theoretical result. And in terms of the regret, the paper's result doesn't improve the regret of simultaneous regret minimization procedures.\n\nThe optimal rate in the online case is $\\tilde{\\mathcal{O}}(H(A_X+B_Y)/\\epsilon^2))$ and is attained up to constant and logarithmic factors in [1] (note that the proof of the lower bound also works in the fixed sampling framework). For this reason, we cannot hope for theoretical improvements in this setting.\n \nThe purpose of fixed sampling is to remove the importance sampling term, that does not appear in the leading theoretical regret term but that would make (in practice) function approximations fail. Removing this problematic term requires different ideas and analysis.\n\n> On the explanation of the theory, the paper can be improved by adding comparison to more benchmarks. The paper only compares the result with the result of simultaneous regret minimization procedure, and the conclusion is the bound matches but doesn't improve the existing result. It could be helpful to understand the paper's result by comparing previous results under the same fixed sampling policy framework.\n\nWe are not aware of other papers that work within the fixed sampling framework with trajectory feedback besides those we have mentioned. If Reviewer yah9 can point additional references, we would be pleased to include them. Consequently, we primarily compare our theoretical results with those of [2]. Reference [3] only achieves a convergence rate of $\\mathcal{O}(1/\\epsilon^2)$ with respect to $\\epsilon$. In the introduction, we discuss the optimal rate already achieved in the online setting by [1]. \n\nWe will make an effort to reference these results more explicitly in our discussion.\n\n\n> From the theorems the fixed and adaptive rate bounds have the same dependency on $T$\n. Is it correct to understand the motivation of the adaptive rate is only to remove the dependency on the importance sampling term \n? When the balanced policy is used as the sampling policy, \n$\\kappa$ is reduced to a game-dependent term. In this case, is it correct think the adaptive rate setting as unnecessary?\n\nThe motivation behind the adaptive rate, in addition to being a more natural choice, is mostly practical: it does not require the balanced policy to be computed beforehand and the horizon $T$ to be known. Theoretically, the adaptive rate is indeed unnecessary, as using the balanced policy already allows for the best rate with respect to the game parameters. Nevertheless, considering the practical advantages of an adaptive policy, we wanted to also provide some theoretical guarantees for it. \n\nOur initial thought was that we could obtain the same optimal rate. However, we did not manage to prove it and now strongly believe it is not possible. Optimality with regards to the $\\epsilon$ dependency was possible nonetheless under some quite general assumptions (with fewer restrictions on the fixed sampling policy and the regularizer) which is already in our opinion a valuable result.\n\n[1] Fiegel, C., Ménard, P., Kozuno, T., Munos, R., Perchet, V., and Valko, M. Adapting to game trees in zero-sum imperfect information games, International Conference on Machine Learning, 2023\n\n[2] Bai, Y., Jin, C., Mei, S., and Yu, T. Near-optimal learning of extensive-form games with imperfect information, International Conference on Machine Learning, 2022\n\n[3] McAleer, S., Farina, G., Lanctot, M., and Sandholm, T. ESCHER: Eschewing importance sampling in games by computing a history value function to estimate regret, International Conference on Learning Representations 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XW7kMIZmw6", "reviewer": "Reviewer_HP7A", "summary": "The submission considers the problem of learning epsilon-Nash equilibria from trajectory feedback in zero-sum extensive-form games. The submission focuses on developing that avoids importance sampling over action sequences.", "questions": "I guess I'd be curious to hear the author's thoughts on whether providing grounding for [2]'s results is a promising direction.", "limitations": "I'll mention a limitation of my own review here: I did not confirm the correctness of the theory, so I'll defer to the other reviewer's on that point.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The submission is well-written, and the problem and solution are reasonable. The experiments are reasonable choices to demonstrate the efficacy of the solution.", "weaknesses": "My main criticism of the submission is that it purports its motivation to be motivated by solving large games. However, using a fixed sampling is untenable for learning good policies in large games, as the target policy and the behavioral policy will become too far apart. Model-free approaches to learning equilibria in large games (i.e., [1, 2]) learn on policy. It would be good for the submission to discuss this discrepancy and how it can be resolved in greater detail. I'll mention that the submission does already acknowledge this point and include some discussion at the end.\n\nAlso, it is worth noting that [2] showed empirical convergence for an on-policy algorithm with trajectory feedback and no importance sampling over action sequences. It would be interesting for the submission to discuss the feasibility of providing theoretical grounding for those results.\n\n[1] From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020)\n\n[2] A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games (2023)\n\nOne other comment I had:\n\n> Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022).\n\nThis claim and citation is a bit confusing. The whole point of McAleer et al. (2022) was to address this issue. The submission is citing a paper that refutes the claim of the sentence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer HP7A for the overall positive review and the interesting references. We would like to answer the remarks and the question below.\n\n> My main criticism of the submission is that it purports its motivation to be motivated by solving large games. However, using a fixed sampling is untenable for learning good policies in large games, as the target policy and the behavioral policy will become too far apart. Model-free approaches to learning equilibria in large games (i.e., [1, 2]) learn on policy. It would be good for the submission to discuss this discrepancy and how it can be resolved in greater detail. I'll mention that the submission does already acknowledge this point and include some discussion at the end.\n\nIndeed, similarly to [3], we do not expend too much on this point as the best choices may not be motivated by theory. While the balanced policy gives the best rates, it may not be the optimal choice in practice. As we played a bit with the sampling policy in our experiments, we realized that updating from time to time the sampling policy with the current average one also provides good empirical results. We conjecture that for practical applications, the choice would not matter that much, as long as it decently explores the tree. \n\nThis is why we mention the idea of restarting and taking the average policy as the new sampling one, as it achieves this purpose. We did not want to delve too much into this matter, as we think that this question would be better answered by more practical works, but we propose to add these insights to the paper.\n\n> Also, it is worth noting that [2] showed empirical convergence for an on-policy algorithm with trajectory feedback and no importance sampling over action sequences. It would be interesting for the submission to discuss the feasibility of providing theoretical grounding for those results.\n\nWe thank Reviewer HP7A for pointing out these empirical results and we will add this reference in our literature review.\nBefore answering, we would like to point out some differences between their theoretical setting and ours. First, they have a strong monotonicity assumption for the underlying operator $G$ they consider (in our case, $G$ would be $G:(\\mu_{1:},\\nu_{1:})-> (-\\ell^\\nu,\\ell^\\mu)$). This strong monotonicity assumption does not hold for their experiments, as the operator $G$ is linear with respect to the realization plan, hence they need to add some regularization, parameterized by the $\\alpha$ constant. Second, they consider a full feedback setting in theory, observing the outcomes of all possible trajectories at each episode.\n\nDespite these differences, we found out that their approach can still be adapted to our setting. An entropic regularization with the Kullback-Leibler divergence allows for the use of an importance sampling estimator, which gives an unbiased estimator of $G$ (formerly provided by the full feedback). The rate is no longer linear, but only in $\\mathcal{O}(T^{-1/2})$ for the exploitability with a fixed regularization. Then, as mentioned in [2] in commentary of Figure 2, the regularization can be decreased over time to converge to the real problem, but we think only a rate of $\\mathcal{O}(T^{-1/4})$ for the true exploitability can be achieved with this approach, by taking $\\alpha$ also of order $\\mathcal{O}(T^{-1/4})$. However, this approach again introduces the importance sampling over action sequences to deal with the trajectory feedback.\n\nIf the regularization is taken such that it compensates for the importance sampling term, then we obtain their empirical approach for dealing with the trajectory feedback. This still implies the need for an analysis with a regularization that varies with time, as the current policies will change. We think that the fact the analysis is done iteratively (as in their Theorem 3.4) rather than being based on the regrets helps in this regard, but we do not know yet if it is possible to provide some theoretical guarantees for this approach.\n\n\n>One other comment I had: \"Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022).\" This claim and citation is a bit confusing. The whole point of McAleer et al. (2022) was to address this issue. The submission is citing a paper that refutes the claim of the sentence.\n\nWe cited McAleer et al. (2022) as it raises the issue and tries to solve it using the fixed sampling framework considered in our submission but with a CFR-based algorithm. As explained later in the introduction, existing procedures *not relying on fixed sampling* suffer from the high variance issue. We acknowledge this sentence could be a bit confusing and we will replace it by:\n\n\"As noted by McAleer et al., 2022 most of the existing procedures suffer from high variance due to the use of importance sampling over sequences of actions.”\n\n[3] McAleer, S., Farina, G., Lanctot, M., and Sandholm, T. ESCHER: Eschewing importance sampling in games by computing a history value function to estimate regret, International Conference on Learning Representations 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces an algorithm to approximate Nash equilibria in zero-sum imperfect information games (IIG) with trajectory feedback using the fixed-sampling framework. They obtain a high-probability convergence rate.
The reviewers unanimously vote for accepting the paper and are quite enthusiastic about the current submission.
Decision: Accept (poster)