Local and Adaptive Mirror Descents in Extensive-Form Games

Authors: côme  fiegel
pierre  ménard
tadashi  kozuno
rémi  munos
vianney  perchet
michal  valko
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 03:16:36

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.

Main paper: 
 introduction: 
 The extensive-form representation of a game (Osborne & Rubinstein, 1994) can be depicted as a tree whose nodes correspond to the game states. At each state, the players choose some available actions and, based on 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 to 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 to the losses of his opponent, the min-player. The primary goal is to design an algorithm learning ε-optimal strategies (von Neumann, 1928) . To achieve this, one can use the self-play framework, where an agent controls both players for T episodes. At the beginning of each episode, the agent prescribes a 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 T episodes, this protocol returns a guess of strategies with a 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, a well-studied approach is to 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/ √ T ) (Cesa-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 to 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 a 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 et 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, we 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 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, as 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 et 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 a regret minimization procedure applied to a local loss on each information set, similarly to Farina et al. (2019b) .• We prove that LocalOMD achieves, in this fixed sampling framework, a O 1/ε 21 sample complexity 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 O H 3 (A X + B Y )/ε 2 near-optimal sample complexity for learning ε-optimal strategies in a tabular setting, where H is the height of the tree, A X the total number of available actions for the min-player and B Y the same quantity for the max-player. This sample complexity was also achieved in the fixed policy framework by BalancedCFR (Bai et al., 2022) , but with a less generalizable procedure that updates the policy at one depth at a time. • We generalize the dual-stabilization technique introduced by Fang et al. (2020) to analyze OMD with a time-varying 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 ∼ ℓ(•|s h , a h , b h ) in [0, 1] and 1 -ℓ h according to the loss distribution ℓ. This is repeated until a final state s H of a fixed depth H is reached, after which the episode finishes.We will denote by Π min and Π max the set of behavioral policies of the minand max-players. Because of the perfect recall assumption, such policies, with an independent stochastic choice of action for each information set, are enough to describe the entire set of strategies (Laraki et al., 2019) . We will also denote by A X and B Y the total number of actions for respectively the min-and max-players, i.e. Regret and ε-optimal strategies We are interested in learning ε-optimal policies through selfplay over multiple episodes. A useful notion for this objective is the regret as explained in the introduction. We first define the value V µ,ν = E µ,ν [ H h=1 ℓ h ] as the expected sum of losses (for the min-player) with respect to a pair of policies (µ, ν) ∈ Π min × Π max . Given a sequence (µ t , ν t ) t∈ [T ] in Π min × Π max , the regrets of the min-and max-players are then defined byR T min := max µ † ∈Πmin T t=1 (V µ t ,ν t -V µ † ,ν t ) and R T max := max ν † ∈Πmax T t=1 (V µ t ,ν † -V µ t ,ν t ) .Minimizing the regret of both players leads to the computation of an ε-optimal profile (equivalent to an ε-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-Bianchi & Lugosi, 2006; Kozuno et al., 2021) From a sequence(µ t , ν t ) t∈[T ] in Π min × Π max a certain time-averaged profile (µ, ν) is ε-optimal with ε = R T min + R T max /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 on 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 1 -ℓ h instead.Algorithm 1 Learning procedures with fixed sampling policies for two players 1: Input: Fixed sampling policies µ s and ν s . Initial policies µ 1 and ν 1 and update procedure for each player 2: For t = 1 to TThe min-player observes the full outcome of an episode with the policies (µ s , ν t )The max-player observes the full outcome of an episode with the policies (µ t , ν s )The min-and max-player respectively update µ t+1 and ν t+1 based on their past observations 3: Output: The time-averaged policies µ, ν 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 ∈ X and action a ∈ A(x), the existence of a unique depth h ∈ [H] and history (x 1 , a 1 , ..., x h , a h ) such that x h = x and a h = a. Using this unique history, we define the realization plan µ 1: ∈ R A X (von Stengel, 1996) associated to a policy µ ∈ Π min with, for any x ∈ X and a ∈ A(x) by µ 1: (x, a) := Π h i=1 µ(a i |x i ). It denotes the combined probability of choosing actions that lead to (x, a). We will especially define Q max := {µ 1: , µ ∈ Π min } the treeplex, i.e. the set of all possible realization plans.Loss and regret linearization For ν a max-player policy, the unique history also allows for the definition of adversarial transitions p ν 1: ∈ R X and adversarial losses ℓ ν ∈ R A X with:p ν 1: (x) := p(x 1 |s 0 ) h i=2 p ν (x i |x i-1 , a i-1 ) and ℓ ν (x, a) := p ν 1: (x)ℓ ν h (x, a)where p(x 1 |s 0 ) is the probability that x 1 is initially observed by the min-player, and, assuming that the max-player policy is set to ν, p ν (•|(x i-1 , a i-1 )) denotes the probability of transitioning to x i when (x i-1 , a i-1 ) is reached, and ℓ ν h the average loss ℓ h 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 (a 1 , ..., a h-1 ).Using a chain-rule argument, we get the relation V µ,ν = ⟨ℓ ν , µ 1: ⟩, given a pair of policies (µ, ν) ∈ Π min × Π max , where ⟨•, •⟩ is the standard inner product of R A X , defined by ⟨z 1 , z 2 ⟩ := x∈X a∈A(x) z 1 (x, a)z 2 (x, a). The regret can then be rewrittenR T min = max µ † ∈Πmin T t=1 ℓ t , µ t 1: -µ † 1:where ℓ t := ℓ ν t , which effectively reduces the problem to a linear regret problem over the convex polytope Q min of realization plans.Several techniques exist to sequentially choose policies (µ t ) t∈[T ] minimizing R T min , assuming that the losses ℓ t are observed after each round t (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 (x t 1 , a t 1 , ..., x t H , a t H ) and partial losses (ℓ t 1 , ..., ℓ t H ) of each round. 
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 simultaneously 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 an observation phase, in which they play their fixed sampling policy µ s or ν s , and an interaction phase, in which they play their updated policy µ t or ν t . 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 R T min and R T max associated to the sequence (µ t , ν t ) t∈[T ] , the previous Theorem 2.1 then characterizes the optimality of the outputted time-averaged profile (µ, ν).While theoretically optimal algorithms already exist using simultaneous regret minimization procedures (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, as the probability of choosing a sequence of action reaching a given information set is fixed, the average estimations of the losses do not need to be re-weighted based on the inverse of a 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 exploitation, 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 a 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 RT min the estimated regret byRT min := max µ † ∈Πmin T t=1 ℓ t , µ t 1: -µ † 1:where the ℓ t are the importance-sampling estimated loss vectors, defined for each information set x of depth h and action a ∈ A(x) byℓ t (x, a) := I {x=x t h ,a=a t h } µ s 1: (x, a)ℓ t h with x t h the visited information set, a t h the chosen action and ℓ t h the loss at depth h of episode t. The following theorem states that upper-bounding this estimated regret is enough to upper-bound the actual regret, up to an additional additive term. Its proof is given in Appendix B and relies on Bernstein-type inequalities. Theorem 2.2. Assume that the estimated losses are obtained with a fixed positive sampling policy µ s as above. Then, for any sequence (µ t ) t∈[T ] of Π min and any δ ∈ (0, 1), the following bound holds with a probability at least 1 -δ R T min ≤ max RT min , 0 + 4 ιHκ(µ s )Twhere ι := log A X +1 δ and κ(µ s ) := max µ∈Πmin x∈X a∈Ax µ1:(x,a) µ s 1: (x,a) . A similar proposition is proved by Farina et al. (2020) . Our bound is specific to the importancesampling loss estimator, but tighter by a factor κ(µ s )/H. Remark 2.3. The quantity κ(µ s ) can be efficiently computed recursively for each of the sub-trees induced by an information set x ∈ X , and we will denote by κ(µ s |x) 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 κ(µ ⋆ ) = A X . The related computations are provided in Appendix C.Question: Does the paper discuss the limitations of the work performed by the authors?Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a 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 architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it 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 is 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 Ω ⊂ R n be a non-empty open convex, and Ω be its closure. A function Ψ : Ω -→ R is said to be Legendre if Ψ is strictly convex, continuously differentiable on Ω and ∀y ∈ Ω\Ω, lim x-→y ∥∇Ψ(x)∥ = +∞ . The Bregman divergenceD Ψ : Ω × Ω - → R of a Legendre function Ψ is defined as D Ψ (x, y) := Ψ(x) -Ψ(y) -⟨∇Ψ(y), x -y⟩. The Fenchel conjugate Ψ ⋆ : R n - → R ∪ {+∞} of Ψ is defined by Ψ ⋆ (ξ) = sup x∈Ω ⟨ξ, x⟩ -Ψ(x).In an extensive-form game with perfect recall, algorithms based on the Online Mirror Descent (OMD) typically compute at each time step t the updateµ t+1 = arg min µ∈Πmin ℓ t , µ 1: + D Ψ (µ 1: , µ t 1: ) (OMD)where ℓ t is the estimated loss and Ψ : Q min -→ R a 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 ∈ X a Legendre regularizer Ψ x over a convex domainΩ x ⊂ R |A(x)| ≥0that contains the simplex ∆ A(x) := µ, a∈A(x) µ(a) = 1 . For a given list of positive weights α = (α(x)) x∈X , the dilated entropy Ψ dil α satisfies for any µ ∈ Π min :Ψ dil α (µ 1: ) := x∈X α(x)µ 1: (x)Ψ x (µ(•|x))where µ 1: (x) := a∈A(x) µ 1: (x, a). Using this dilated entropy as the regularizer, the OMD updates become µ t+1 = arg minµ∈Πmin ℓ t , µ 1: + D dil α (µ 1: , µ t 1: )whereD dil α (µ 1: , µ t 1: ) := x∈X α(x)µ 1: (x)D x (µ 1: (•|x), µ t 1: (•|x)) and (D x ) x∈X are the individual Bregman divergences of the (Ψ x ) x∈X . 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.The regularizer Ψ sometimes needs to change over time. For example, when T is unknown, a regularizer of the form Ψ t = Ψ/η t is usually considered, with η t = t -1/2 the learning rate. Fiegel et al. (2023) gives another example of time-varying regularization, adapting the regularization to 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 η t+1 = 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 (Ψ t ) t∈[T ] defined on a convex domain Ω ⊂ R n , and that the player chooses a sequence of primal iterates (w t ) t∈[T ] (respectively the updated realization plans (µ t 1: ) t∈[T ] of our settings) in a closed convex set C (respectively the treeplex Q min ) included in Ω, according to a sequence of dual increments (ξ t ) t∈[T ] in R n (respectively the estimated losses ( ℓ t ) t∈[T ] ) observed sequentially. Fang et al. (2020) proposed in the presence of non-increasing learning rates, to use a technique called dual-stabilization to recover the classical OMD bounds. We noticed that their updates can be interpreted asw t+1 = arg min w∈C ξ t , w + D Ψ t w, w t + D Ψ t+1 -Ψ t w, w 1 (GDS-OMD)with Ψ t+1 -Ψ t incremental functions assumed to be convex, generalizing their special case Ψ t+1 = Ψ/η t+1 . The following theorem, proven in Appendix D shows that classical OMD guarantees can be recovered with these updates. Theorem 3.2. Let (w t ) t∈[T ] be a sequence of primal iterates generated by the updates (GDS-OMD), with convex incremental functions. Then for any w † ∈ Ω,T t=1 ξ t , w t -w † ≤ D Ψ T (w † , w 1 ) + T t=1 D Ψ t,⋆ ∇Ψ t (w t ) -ξ t , ∇Ψ t (w t )where the (Ψ t,⋆ ) t∈[T ] are the respective Fenchel conjugates of the(Ψ t ) t∈[T ] .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 1 instead of the sequence (w t ) t , which is important for some (Ψ t ) t sequences (Orabona & Pál, 2018) . Remark 3.3. AdaGrad for stochastic gradient descent (Duchi et al., 2011) is an interesting example of regularizatiom with convex increments (and not only through a decreasing learning rate). It uses the adaptive regularizationΨ t+1 = ∥•∥ 2 (G t ) 1/2, where G t is a positive semi-definite matrix defined with the gradients g k by eitherG t = t k=1 g k g T k or, more efficiently, by G t = Diag t k=1 g k g T k .Algorithm 2 LocalOMD 1: Input: Sampling policy µ s ∈ Π min and initial policy µ 1 ∈ Π min Bregman divergences D x for each information set x ∈ X Sequences of (possibly adaptive) learning rates (η t (x)) t,x for each round t and information set x. 2: For t = 1 to T Observes the outcome of an episode using the fixed strategy µ s q t H+1 ← 0 For h = H to 1:ℓ t h ← I {a=a t h } ℓ t h + q t h+1 µ s (a t h |x t h ) µ t+1 (•|x) ← arg min µ∈∆ A(x) h t x (µ) q t h ← min µ∈∆ A(x) h t x (µ) where h t x (µ) := ℓ t h , µ + 1 η t (x t h ) D x (µ, µ t (•|x t h ))+ 1 η t+1 (x t h ) - 1 η t ′ +1 (x t h ) D x µ, µ 1 (•|x t h) and t ′ is the last round in which x t h was visited For all non-visited x ∈ X :µ t+1 (•|x) ← µ t (•|x) 3: Output: The time-averaged policy µAdaptive dilatation In the extensive-form game setting based on the dilated entropy Ψ dil α , this stabilization can be applied to have weights (α t (x)) x∈X ,t∈[T ] that vary with times. The convexity assumption of Ψ dil α t+1 -Ψ dil α t then rewrites to having locally non-decreasing weights for each x ∈ X . In this particular case, the updates are obtained with the formulaµ t+1 = arg min µ∈Πmin ℓ t , µ 1: + D dil α t (µ, µ t ) + D dil α t+1 -α t (µ, µ 1 ) . (DDS-OMD)4 LocalOMD algorithm 
algorithm: 
 Let us now consider the fixed sampling framework introduced in Section 2.2. Given a sequence (η t (x)) t∈[T ] of locally non-increasing learning rates for each x ∈ X , we introduce the LocalOMD algorithm described in Algorithm 2, that uses the updates (DDS-OMD) above with the adaptive weights α t (x) = 1/(µ s 1: (x)η t (x)). Dividing the loss by the importance sampling term 1/µ s 1: (x) through the learning rates lets it 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 ℓ t h , a 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 µ s (a|x) of choosing the last action a ∈ A(x) in the important sampling, instead of the combined probability µ s 1: (x, a) of the realization plan. A similar decomposition was observed by Farina et al. (2019a) for the non-stochastic 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 be of order O(A X ) (approximately A H in 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 A X 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 is only H times the cost of a local update. If D x is the Kullback-Leibler divergence, the local updates then simplify to some Exponential Weights updates and the total time complexity of an iteration becomes O(HA), where A is an upper-bound on the local number of actions.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 x ∈ X as a separate problem through the local losses ℓ t h , 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 a large class of regularizers (Ψ x ) x∈X and learning rates (η t (x) x∈X ,t∈[T ] ), the regret has a O( T log(1/δ)) upper bound (hiding the game-dependent terms) with a probability at least 1 -δ. Such learning rates include, for all x ∈ X of depth h,η t (x) = η t k=1 I {x=x k h } , or the adaptive version η t (x) = η t k=1 I {x=x k h } ℓ k h 2 .The adaptive learning rates mentioned for this theorem generally enjoy better performances in practice. Furthermore, they require no initial computation and are easily updated.The following theorem uses a constant learning rate that locally depends on the κ(µ s |x) quantities of Remark 2.3, and on the A := max x∈X |A(x)| quantity that upper bounds the local number of available actions on the whole tree. Theorem 4.2. Using LocalOMD with µ 1 as the uniform policy, with the learning rates η t (x) = η/κ(µ s |x) where η = log(A)κ(µ s )/(3HT ), and with Ψ x the Shannon entropy Ψ x (µ) = a∈A(x) µ(a) log(µ(a)), we have with a probability at least 1 -δ and ι = log(2(A X + 1)/δ),R T min ≤ 4 + 2 √ 3 H 3/2 log(A)ικ(µ s )T .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 κ(µ ⋆ ) = A X , we obtain with Theorem 2.1 the rate O H 3/2 √ A X T , near-optimal up to the H dependency (Bai et al., 2022) . 
experiments: 
 We implemented LocalOMD, with the parameters of Theorem 4.1 and Theorem 4.2, then tested it 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) , Leduc 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 a grid search. The code is available at https: //github.com/anon5493/LocalOMD-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 t while still performing a single update on the policy of each player. The exploitability gap, along with the variance across the different instances of the simulation, is plotted in Figure 1 , top. Note that this variance across the instances is different from the variance of the estimated loss vector ℓ t our method tries to reduce, which is plotted in the Figure 1 , down.Focusing on the exploitability gap, we observe that the two versions of LocalOMD 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 Leduc poker.In the second figure, we observe that the algorithms based on a fixed sampling procedure indeed get a 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. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as 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. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusion: 
 We studied the use of a fixed sampling OMD procedure for the computation of ε-optimal strategies. This approach relies, for each player, on an uncoupling between the observation policy and the interaction policy as 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 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.We would like to conclude by providing the following interesting research directions.Problem-dependent optimality For a given game structure and fixed sampling policy µ s , is there a policy-dependent lower bound O( κ(µ s )T ) on the regret? We wonder if the κ(µ s ) quantity of Remark 2.3 denotes some sort of complexity related to the problem.General sum game Using the same techniques as Bai et al. (2022) , in a general sum game with potentially more than two players, LocalOMD can be shown to converge to an ε-approximate normalform 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 importance-sampling of the previous actions in the usual semi-bandit framework that observes with the current policy? The answer is not obvious since the current approach heavily relies on the fact that the sampling policy is fixed. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The experiments were run on a personal computer as they do not require heavy computations.Guidelines:• The answer NA means that the paper does not include experiments.• 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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 we are 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 no 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] 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 nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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. 
 
 Appendix: A Related worksIn this section, we review previous works on learning an ε-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, a first line of work recasts the setting through the sequence-form representation of a game as a linear program which can be solved efficiently (Romanovsky, 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 Kroer et al., , 2018 Kroer et al., , 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 Kroer et al. ( , 2020) ) use the MirrorProx algorithm (Nemirovski, 2004) . These methods have a rate of convergence of order O(poly(H, A X , B Y )/ε).A third approach, counterfactual regret minimization (Zinkevich et al., 2007) , leverages local regret minimization, i.e. minimizing a type of regret at each information set. Popular algorithms are based on the regret-matching algorithm (Hart & Mas-Colell, 2000; Gordon, 2007) such as 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 O(poly(H,A X , B Y )/ε 2 ).Nevertheless, all the methods described above need to 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-sampling MCCFR algorithm (Lanctot et al., 2009) .Trajectory feedback A way to 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 et 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 O(poly(H, S, A, B)/ε 2 ) 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 to 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 O(poly(H, S, A, B)/ε 2 ).Model-free Another line of work (Lanctot et 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 et al., 2020) builds an importance sampling estimate of the counterfactual regret by playing according to a 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 at each information set is not necessarily a good choice. Instead, Farina et 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 ε-optimal strategies with high probability, MCCFR needs at most O(H 3 (A X + B Y )/ε 2 ) realizations of 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 a player, see also Farina et al. (2021b) . They prove a sample complexity, for the proposed algorithm, IXOMD, of orderO(H 2 (XA X + Y B Y )/ε 2 ). Interestingly, they do not need to know in advance the structure of the information set space to obtain this bound. However, the sample complexity of IXOMD does not match the lower bound for this setting which is of order O((A X + B Y )/ε 2 ). 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 a sample complexity of order O(H 3 (A X + B Y )/ε 2 ).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. In this section, we aim to establish Theorem 2.2 of the main paper. We start by stating a Bernstein-type 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 (U t ) t∈[T ] be a sequence of random variables with respect to a filtration F, and γ > 0 be a fixed constant such that for all t, γU t ≤ 1. Then with a probability of at least 1 -δ ′ :T t=1 U t -E U t F t-1 ≤ γ T t=1 E (U t ) 2 F t-1 + 1 γ log( 1 δ ′ )Proof. For any t ∈ [T ], using the inequalities exp(x) ≤ 1 + x + x 2 for all x ≤ 1 and 1 + x ≤ exp(x) for all x ∈ R, we haveE exp γU t F t-1 ≤ E 1 + γU t + γ 2 (U t ) 2 F t-1 = 1 + γE U t F t-1 + γ 2 E (U t ) 2 F t-1 ≤ exp γE U t F t-1 + γ 2 E (U t ) 2 F t-1 .This implies that the random process (S t ) t∈[T ] defined byS t := exp t k=1 γ U k -E U k F k-1 - t k=1 γ 2 E (U k ) 2 F k-1is a super-martingale, with S 0 = 1. Using the Markov inequality, we then getP 1 γ log(S T ) > 1 γ log 1 δ ′ = P S T > 1 δ ′ ≤ δ ′ E(S T ) ≤ δ ′which immediately yields the stated inequality with probability at least 1 -δ ′ .This lemma is then used for Theorem 2.2. The filtration (F t ) t∈[T ] will be used, such that F t is the sigma-algebra of all variables of the self-play algorithm up to the execution of episode t + 1. Theorem B.2. Assume that the estimated losses are obtained with a fixed positive sampling policy µ s as above. Then, for any sequence (µ t ) t∈[T ] of Π min and any δ ∈ (0, 1), the following bound holds with a probability at least 1 -δ .R T min ≤Proof. We want to show that, with probability at least 1 -δ, that t t=1 ℓ t -ℓ t , µ t 1: -µ 1: ≤ 4 ιHκ(µ s )T holds for all µ ∈ Π min . Then the property follows after re-organizing the inequality and maximizing over µ. In order to do so, we divide this term into two parts:T t=1 ℓ t -ℓ t , µ t 1: -µ 1: = T t=1 ℓ t -ℓ t , µ 1: EST I + T t=1 ℓ t -ℓ t , µ t 1:EST II .We will furthermore assume that HT ≥ ικ(µ s ), as otherwise, 4 ιHκ(µ s )T ≤ 4HT and the property immediately follows from R T min ≤ HT . Upper bound of EST I For all x ∈ X of depth h and a ∈ A(x), we apply Lemma B.1 to the random process U t x,a = ℓ t h I {x=x t h ,a=a t h } with δ ′ = δ/(AX + 1) and a fixed γ 1 ∈ (0, 1] we will specify later. This yields, with a probability at least 1 -δ ′ , thatT t=1 ℓ t h I {x=x t h ,a=a t h } -E ℓ t h I {x=x t h ,a=a t h } F t-1 ≤ γ 1 T t=1 E ℓ t h 2 I {x=x t h ,a=a t h } F t-1 + ι γ 1 ≤ γ 1 T t=1 E ℓ t h I {x=x t h ,a=a t h } F t-1 + ι γ 1 .By definition of the estimated loss, ℓ t h I {x=x t h ,a=a t h } /µ s 1: (x, a) = ℓ t (x, a). We thus divide by µ s 1: (x, a) both sides of the inequality, and the unbiasedness of the loss estimator yieldsT t=1 ℓ t (x, a) -ℓ t (x, a) ≤ γ 1 T t=1 ℓ t (x, a) + ι γ 1 µ s 1 : (x, a).This inequality holds for all (x, a) with a probability of at least 1 -δA X /(A X + 1). Taking the scalar product with any µ ∈ Π min then givesT t=1 ℓ t -ℓ t , µ 1: ≤ γ 1 T t=1 ℓ t , µ 1: + 1 γ 1 x∈X a∈A(x) µ 1: (x, a) µ s 1: (x, a) ≤ γ 1 HT + ι γ 1 κ(µ s ) .Using γ 1 = ικ(µ s )/(HT ) ≤ 1 (by assumption), finally yields EST I ≤ 2 ιHκ(µ s )T .Upper bound of EST II For this upper bound, we apply Lemma B.1 directly to the sequence U t = -ℓ t , µ t 1: . We now choose γ 2 ∈ R + (no further assumption is needed on γ 2 as the sequence is negative) and apply the lemma to get with probability at least 1 -δ/(A X + 1)T t=1 ℓ t -ℓ t , µ t 1: ≤ γ 2 T t=1 E ℓ t , µ t 1: 2 F t-1 + ι γ 2 = γ 2 T t=1 E      H h=1 ℓ t h x∈X a∈A(x) I {x=x t h ,a=a t h } µ t 1: (x, a) µ s 1: (x, a)   2 F t-1    + ι γ 2 (Cauchy-Schwarz) ≤ γ 2 H T t=1 E   H h=1 ℓ t h 2 x∈X a∈A(x) I {x=x t h ,a=a t h } µ t 1: (x, a) 2 µ s 1: (x, a) 2 F t-1   + ι γ 2 ≤ γ 2 H T t=1 E   H h=1 ℓ t h x∈X a∈A(x) I {x=x t h ,a=a t h } µ t 1: (x, a) µ s 1: (x, a) 2 F t-1   + ι γ 2 = γ 2 H T t=1 E   H h=1 x∈X a∈A(x) ℓ t (x, a) µ t 1: (x, a) µ s 1: (x, a) F t-1   + ι γ 2 = γ 2 H T t=1 x∈X a∈A(x) ℓ t (x, a) µ t 1: (x, a) µ s 1: (x, a) + ι γ 2 (as ℓ t (x, a) ≤ 1) ≤ γ 2 H T t=1 x∈X a∈A(x) µ t 1: (x, a) µ s 1: (x, a) + ι γ 2 ≤ γ 2 Hκ(µ s )T + ι γ 2 .Taking γ 2 = ι Hκ(µ s )T then leads to T t=1 ℓ t -ℓ t , µ t 1: ≤ 2 ιHκ(µ s )T .Summing the two inequalities yields the inequality of the theorem with a probability of at least 1 -δ.This section deals with the κ(µ s ) and local κ(µ s |x) of the main paper, and links it to the balanced policy µ ⋆ .Recursive κ computation Let µ s be the positive sample policy. For any µ ∈ Π min and x ∈ X of depth h, we define κ µ (µ s |x) the local sum of ratios against µ in the subtree induced by x, i.e.κ µ (µ s |x) := x ′ ∈X ,x is in the history of x ′ a ′ ∈A(x ′ ) µ h: (x ′ , a ′ ) µ s h: (x ′ , a ′ ) where, if (x ′ 1 , a ′ 1 ..., x ′ h ′ , a ′ ) is the history of (x ′ , a ′ ), µ h: (x ′ , a ′ ) := Π h ′ i=h µ(a ′ i |x ′ i ) .We then formally define κ(µ s |x) as κ(µ s |x) := max µ∈Πmin κ µ (µ s |x). For any µ ∈ Π min , the following recursive formula standsκ µ (µ s |x) = a∈A(x) µ(a|x) µ s (a|x)   1 + x ′ ∈X ,x ′ directly follows (x,a) κ µ (µ s |x ′ )  that follows from the definition of κ µ (µ s |x). The same kind of recursion can then be obtained for κ(µ s |x), because each appearance of µ in the previous equality can be maximized independently (depending on different information sets). This yieldsEQUATIONwhich allows for a simple recursive computation of κ(µ s |x). Finally, once the whole recursive computation is done, κ(µ s ) itself can be computed by, defining X 1 the information sets of depth 1,κ(µ s ) = x1∈X1 κ(µ s |x 1 ) .Balanced policy κ(µ s |x) can also be minimized over µ s ∈ Π min recursively from the leaves using the tree structure. Indeed, for each x ∈ X , assuming that the minimizers of κ(µ s |x ′ ) are already known for subsequent x ′ , the policy µ s ∈ ∆ A(x) that minimizes the maximum along the actions a ∈ A(x) can be computed from (1). Furthermore, if we define A τ (x, a) and A τ (x) the total number of actions in the subtrees respectively induced by (x, a) and x, i.e.A τ (x, a) := 1 + x ′ ∈X ,(x,a) is in the history of x ′ |A(x ′ )| and A τ (x) := a∈A(x) A τ (x, a) ,we can show that min µ s ∈Πmin κ(µ s |x) = A τ (x), and that the minimum is attained by the balanced policy µ ⋆ defined byµ ⋆ (a|x) := A τ (x, a) A τ (x) .Indeed, if we assume in (1) that the previous property holds for the κ(µ s |x ′ ), thenκ(µ s |x) = max a∈A(x) 1 µ s (a|x)   1 + x ′ ∈X ,x ′ directly follows (x,a) A τ (x ′ )   = max a∈A(x) A τ (x, a) µ s (a|x)and the previous equality is minimized when the µ s (a|x) are proportional to the A τ (x, a), achieved by the balanced policy µ ⋆ . With this policy, the same equality gives κ(µ ⋆ |x) = A τ (x), which concludes the induction.Finally, computing κ(µ ⋆ ) yieldsκ(µ ⋆ ) = x1∈X1 κ(µ ⋆ |x 1 ) = x1∈X1 A τ (x 1 ) = A X .This section will establish the bound related to the updates (GDS-OMD) obtained with any Legendre function.We start this section by stating multiple properties of the Bregman divergence D Ψ for Ψ a convex function, continuously differentiable on an open Ω and defined on Ω, proved by Cesa-Bianchi & Lugosi (2006) .Law of cosines : For any x ∈ Ω and w, z ∈ Ω, the following equality holdsD Ψ (x, w) = D Ψ (x, z) + D Ψ (z, w) -⟨∇Ψ(w) -∇Ψ(z), x -z⟩ .Algorithm 3 Generalized dual-stabilized online mirror descent 1: Input:A sequence of dual increments ξ t An open subset Ω ∈ R n and a closed convex C of Ω A sequence of Legendre regularizers (Ψ t ) t∈[T ] on Ω such that for all t ∈ [T ], Ψ t+1 -Ψ t is convex An initial primal iterate w 1 ∈ C 2: Output:A sequence (w t ) t∈[T ] of primal iterates 3: Algorithm:For t = 1 to T z t = ∇Ψ t (w t ) y t+1 = z t -ξ t + ∇Ψ t+1 (w 1 ) -∇Ψ t (w 1 ) ŵt+1 = ∇Ψ t+1,⋆ (y t+1 ) w t+1 = Π Ψ t+1 C ( ŵt+1 )Bregman projection : For C a closed convex of Ω, and Ψ strictly convex, we can define the Bregman projectionΠ Ψ C over Ω by Π Ψ C (w) = arg min z∈C D Ψ (z, w) .This Bregman projection satisfies a generalized Pythagorean inequality, for w ∈ Ω and z ∈ CD Ψ (z, w) ≥ D Ψ (z, Π Ψ C (w)) + D Ψ (Π Ψ C (w), w)Fenchel dual : We defined the Fenchel dual Ψ ⋆ of a Legendre function Ψ for any ξ ∈ R n by Ψ ⋆ (ξ) = sup w∈Ω ⟨ξ, w⟩ -Ψ(w) .If we consider Ω ⋆ := ∇Ψ(Ω), it can be shown that ∇Ψ ⋆ is the inverse function of ∇Ψ over Ω ⋆ , i.e. for any w ∈ Ω, ∇Ψ ⋆ (∇Ψ(w)) = w. Furthermore, for w, z ∈ Ω,D Ψ (w, z) = D Ψ ⋆ (∇Ψ ⋆ (z), ∇Ψ ⋆ (y)) .Strong convexity: Ψ is said to be 1-strongly convex with respect to a norm ∥•∥ if for all w, z ∈ ΩΨ(z) ≥ Ψ(w) + ⟨∇Ψ(w), z -w⟩ + 1 2 ∥w -z∥ 2 .In this case, the Bregman divergence of the Fenchel dual Ψ ⋆ satisfies for anyξ 1 , ξ 2 ∈ Ω ⋆ D Ψ ⋆ (ξ 1 , ξ 2 ) ≤ ∥ξ 1 -ξ 2 ∥ 2 ⋆where ∥•∥ ⋆ is the dual norm of ∥•∥.We will assume in the following parts that the updates of the following algorithm are properly defined, which happens when all vectors y t+1 belong to the Fenchel dual space Ω t+1,⋆ := ∇Ψ t+1 (Ω). We make the same assumption on the regular OMD iterates z t -ξ t .We start by giving an equivalent formulation of the updates (GDS-OMD) through Algorithm 3.Proposition D.1. Algorithm 3 computes the updates (GDS-OMD) if they are properly defined, i.e. computes the sequence of primal iterates defined byw t+1 = arg min w∈C ξ t , w + D Ψ t w, w t + D Ψ t+1 -Ψ t w, w 1 .Proof. By definition of ŵt+1 in Algorithm 3, we have for all iterations t ∈ [T ] and w ∈ CD Ψ t+1 (w, ŵt+1 ) = Ψ t+1 (w) -∇Ψ t+1 ( ŵt+1 ), w + C 1 = Ψ t (w) + Ψ t+1 (w) -Ψ t (w) -y t+1 , w + C 1 = ξ t , w + Ψ t (w) -∇Ψ t (w t ), w + Ψ t+1 (w) -Ψ t (w) -∇Ψ t+1 (w 1 ) -∇Ψ t (w 1 ), w + C 1 = ξ t , w + D Ψ t w, w t + D Ψ t+1 -Ψ t w, w 1 + C 2where C 1 and C 2 are constants independent of the choice of w (but not independent of the other variables). As w t+1 = arg min w∈C D Ψ t+1 (w, ŵt+1 ), the updates of Algorithm 3 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 to 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 t ) t∈[T ] be a sequence of primal iterates generated by the updates (GDS-OMD), with convex incremental functions. Then for any w † ∈ Ω,T t=1 ξ t , w t -w † ≤ D Ψ T (w † , w 1 ) + T t=1 D Ψ t,⋆ ∇Ψ t (w t ) -ξ t , ∇Ψ t (w t )Proof. We can assume, without any incidence on the (w t ) t∈[T ] sequence, that Ψ T +1 = Ψ T . We also define for all t ∈ [T ] the notations φ t = Ψ t+1 -Ψ t and qt = ξ t , ŵt+1 + D Ψ t ( ŵt+1 , w t ) + D φ t ( ŵt+1 , w 1 ) .We then divide the sum into a stability and a penalty terms:T t=1 ξ t , w t -w † = T t=1 qt -ξ t , w † penalty + T t=1ξ t , w t -qt stability and we look at upper-bounding these two terms.Penalty term: For all t ∈ [T ], using the law of cosines on the Bregman divergences of Ψ t and φ t , we have the two equalities:EQUATIOND φ t (w † , w 1 ) = D φ t (w † , ŵt+1 ) + D φ t ( ŵt+1 , w 1 ) -∇φ t (w 1 ) -∇φ t ( ŵt+1 ), w † -ŵt+1 .Summing these two equalities, we getD Ψ t (w † , w t ) + D φ t (w † , w 1 ) = D Ψ t+1 (w † , ŵt+1 ) + D Ψ t ( ŵt+1 , w t ) + D φ t ( ŵt+1 , w 1 ) -ξ t , w † -ŵt+1 = D Ψ t+1 (w † , ŵt+1 ) + qt -ξ t , w †as by definition of ŵt+1 and y t+1 , ∇Ψ t+1 ( ŵt+1 ) = y t+1 = -ξ t + ∇Ψ t (w t ) + ∇φ t (w 1 ) .Furthermore, as w t+1 = Π t+1 C ( ŵt+1 ), the Pythagorean inequality for the Bregman divergence yields thatD Ψ t+1 (w † , ŵt+1 ) ≥ D Ψ t+1 (w † , w t+1 ) + D Ψ t+1 (w t+1 , ŵt+1 ) ≥ D Ψ t+1 (w † , w t+1 ) .Injecting this in the previous equality and telescoping leads toT t=1 qt -ξ t , w † = T t=1 D Ψ t (w † , w t ) + D φ t (w † , w 1 ) -D Ψ t+1 (w † , ŵt+1 ) ≤ T t=1 D Ψ t (w † , w t ) + D φ t (w † , w 1 ) -D Ψ t+1 (w † , w t+1 ) = D Ψ T +1 (w † , w 1 ) -D Ψ T +1 (w † , w t+1 ) ≤ D Ψ T (w † , w 1 ) as Ψ T = Ψ T +1 by definition.Stability term: We first notice, for all t ∈ [T ], thatξ t , w t -qt = ξ t , w t -ŵt+1 -D Ψ t ( ŵt+1 , w t ) -D φ t ( ŵt+1 , w 1 ) ≤ ξ t , w t -ŵt+1 -D Ψ t ( ŵt+1 , w t ) ≤ ξ t , w t -wt+1 -D Ψ t ( wt+1 , w t )where wt+1 := arg minw∈Ω ξ t , w + D Ψ t ( w, w t )is the wt+1 iterate that would be obtained using a classical OMD step with Ψ t , without the stabilization. By optimality, it verifies ∇Ψ t ( wt+1 ) = ∇Ψ t (w t ) -ξ t and the law of cosines then yieldsD Ψ t (w t , w t ) = D Ψ t (w t , wt+1 ) + D Ψ t ( wt+1 , w t ) -∇Ψ t (w t ) -∇Ψ t ( wt+1 ), w t -wt+1 (0) = D Ψ t (w t , wt+1 ) + D Ψ t ( wt+1 , w t ) -ξ t , w t -wt+1 .Plugging this in the first inequality, we directly get ξ t , w t -qt ≤ D Ψ t (w t , wt+1 ) and we conclude usingD Ψ t (w t , wt+1 ) = D Ψ t,⋆ (∇Ψ t ( wt+1 ), ∇Ψ t (w t )) = D Ψ t,⋆ (∇Ψ t (w t ) -ξ t , ∇Ψ t (w t )) .This section will focus on the dilated entropy approach to extensive-form games, and especially on the updatesµ t+1 = arg min µ∈Πmin ℓ t , µ 1: + D dil α t (µ, µ t ) + D dil α t+1 -α t (µ, µ 1 ) (GDS-OMD dilated)that are used by LocalOMD.The following proposition shows that each update of this form can be computed recursively starting from the leaves of the tree. It requires for any t ∈ [T ] the vector q t that satisfies for any x ∈ X of depth h q t (x) = min µ∈Πmin ℓ t,→x , µ →x h:+ D dil,→x α t (µ, µ t ) + D dil,→x α t+1 -α t (µ, µ 1 )where → x means that the quantity is considered on the sub-tree induced by x rather than the full information set tree, and µ h: is defined in Appendix C.Proposition E.1. Consider the previous updates (GDS-OMD and the vectors (q t ) t∈[T ] above. Both µ t+1 and q t can be computed recursively starting from the leaves of the tree throughµ t+1 = arg min µ∈∆ A(x)h t x (µ) and q t (x) = minµ∈∆ A(x) h t x (µ)whereh t x (µ) = ℓ t (x, •), µ + (1/α t (x)) D x (µ, µ t (•|x)) + 1/α t+1 (x) -1/α t (x) D x (µ, µ 1 (•|x))and the regularized loss ℓ t (x, a) is defined byℓ t (x, a) := ℓ t (x, a) + x ′ ∈X |x ′ directly follows (x,a)q t (x ′ ) .Proof. First, note that µ t+1 is the unique minimizer associated to each q t (x 1 ) for x 1 the information set of depth 1. Indeed, each of the sub-tree induced by the x 1 can be considered as an independent problem. The idea will be to recursively minimize the q t (x), starting from the leaves (i.e. the final information sets x H ), and compute µ t+1 (|x) as the associated minimizer at each information set.This minimization is done through, at each x ∈ X of depth h, with a decomposition of q t (x). Indeed, separating the induced tree by x between the root and the rest of the tree leads toq t (x) = arg min µ∈Πmin ℓ t (x, •), µ(•|x) + (1/α t (x)) D x (µ(•|x), µ t (•|x)) + 1/α t+1 (x) -1/α t (x) D x (µ(•|x), µ 1 (•|x)) + a∈A(x) µ(a|x) x ′ ∈X |x' directly follows (x,a) ℓ t,→x ′ , µ →x ′ h+1: + D dil,→x ′ α t (µ, µ t ) + D dil,→x ′ α t+1 -α t (µ, µ 1 ) = arg min µ∈∆ A(x) ℓ t (x, •), µ + (1/α t (x)) D x (µ, µ t (•|x)) + 1/α t+1 (x) -1/α t (x) D x (µ, µ 1 (•|x)) + a∈A(x)µ(a)x ′ ∈X |x' directly follows (x,a)q t (x ′ ) = arg min µ∈∆ A(x) ℓ t (x, •), µ + (1/α t (x)) D x (µ, µ t (•|x)) + 1/α t+1 (x) -1/α t (x) D x (µ, µ 1 (•|x)) = arg min µ∈∆ A(x) h x (µ)as each minimization on µ ∈ Π min is done on independent components. This justifies the recursive computation of both µ t+1 and q t . This proposition directly provides the proof of correctness of LocalOMD, for which the regularized losses at time step t are non-null only on the trajectory withℓ t (x, a) = I {x=x t h ,a=a t h } µ s 1: (x) ℓ t h .We now want to upper(bound the regret associated with this sequence µ t . The following lemma gives a valuable property that links the regularized loss and the estimated loss.Lemma E.2. For any policy µ ′ ∈ Π min , we haveℓ t , µ ′ 1: - x∈X µ ′ 1: (x)q t (x) = ℓ t , µ ′ 1: -qt where qt = min µ∈Πmin ℓ t , µ 1: + D dil α t (µ, µ t ) + D dil α t+1 -α t (µ, µ 1 )Proof. By definition of ℓ t we have, for any µ ∈ Π minℓ t , µ ′ 1: = ℓ t , µ ′ 1: + x∈X a∈Ax µ ′ 1: (x, a) x ′ |(x,a)-→x ′ q t (x ′ ) = ℓ t , µ ′ 1: + x∈X a∈Ax x ′ |(x,a)-→x ′ µ ′ 1: (x ′ )q t (x ′ ) = ℓ t , µ ′ 1: + x ′ ∈X \X1 µ ′ 1: (x ′ )q t (x ′ ) = ℓ t , µ ′ 1: + x ′ ∈X µ ′ 1: (x ′ )q t (x ′ ) - x ′ ∈X1 q t (x ′ )in which we identified the components of the second sum as the set of non-initial information sets. We then conclude using x∈X1 q t (x) = qt by definition of the q t terms.This lemma is then used to upper bound the estimated regret of the sequence generated by the updates (GDS-OMD 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 to upper bound. Nonetheless, the proof of the following theorem is mostly the same but with a slightly different definition of the stability and penalty terms. Theorem E.3. Let (µ t ) t∈[T ] be the sequence of policies generated by the updates (GDS-OMD dilated). The following bound holdsRT ≤ sup µ † ∈Πmin D dil α T (µ † 1: , µ 1 1: ) penalty + T t=1 x∈X α t (x)µ t 1: (x)D ⋆ x ∇Ψ x (µ t 1: (•|x)) - 1 α t (x) ℓ t (x, •), ∇Ψ x (µ t 1: (•|x)) stability .Proof. The separation between the stability and the penalty terms is the same as in Theorem 3.2, but with qt (of Lemma E.2) defined after the projection rather than before. This leads to the decompositionRT = max µ † ∈Πmin T t=1 qt -ℓ t , µ † 1: penalty + T t=1 ℓ t , µ t 1: -qt stability .Penalty term: This part is similar to the general theorem. The optimality of µ t+1 leads to, for anyt ∈ [T ], ∇Ψ t+1 (µ t+1 1: ) = -ℓ t -g t + ∇Ψ t (µ t 1: ) + ∇φ t (µ 1 1:) . where g t ∈ Q ⊥ max and φ t = Ψ t+1 -Ψ t . We use the same two law of cosines as in Theorem 3.2D Ψ t (µ † 1: , µ t 1: ) = D Ψ t (µ † 1: , µ t+1 1: ) + D Ψ t (µ t+1 1: , µ t 1: ) -∇Ψ t (µ t 1: ) -∇Ψ t (µ t+1 1: ), µ † 1: -µ t+1 1: D φ t (µ † 1: , µ 1 1: ) = D φ t (µ † 1: , µ t+1 1: ) + D φ t (µ t+1 1: , µ 1 1: ) -∇φ t (µ 1 1: ) -∇φ t (µ t+1 1: ), µ † 1: -µ t+1 1:which yields by summingD Ψ t (µ † 1: , µ t 1: ) + D φ t (µ † 1: , µ 1 1: ) = D Ψ t+1 (µ † 1: , µ t+1 1: ) + D Ψ t (µ t+1 1: , µ t 1: ) + D φ (µ t+1 1: , µ 1 1: ) -ℓ t + g t , µ † 1: -µ t+1 1: = D Ψ t+1 (µ † 1: , µ t+1 1: ) + qt -ℓ t , µ † 1:where we used g t , µ † 1: -µ t+1 1:= 0 from the orthogonality. Summing over t ∈ [T ] then gives, by telescoping similarly to the general theorem,T t=1 qt -ℓ t , µ † 1: = T t=1 D Ψ t (µ † 1: , µ t 1: ) + D φ t (µ † 1: , µ 1 1: ) -D Ψ t+1 (µ † 1: , µ t+1 1: ) = D Ψ T +1 (µ † 1: , µ 1 1: ) -D Ψ T +1 (µ † 1: , µ t+1 1: ) ≤ D Ψ T (µ † 1: , µ 1 1: )Stability term: From Lemma E.2 used with µ ′ = µ t , we get an alternative expression of the stability termℓ t , µ t 1: -qt = ℓ t , µ t 1: - x∈X µ t 1: (x)q t (x)This shows the stability term can be decomposed in a positive linear combinationℓ t , µ t 1: -qt = x∈X µ t 1: (x) ℓ t (x, •), µ t (•|x) -q t (x)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 Ψ t x := α t (x)Ψ x and φ tx := Ψ t+1x-Ψ t x , we have ℓ t (x, •), µ t (•|x) -q t (x) = ℓ t (x, •), µ t (•|x) -µ t+1 (•|x) -D Ψ t x (µ t+1 (•|x), µ t (•|x)) -D φ t x (µ t+1 (•|x), µ 1 (•|x)) ≤ ℓ t (x, •), µ t (•|x) -µ t+1 (•|x) -D Ψ t x (µ t+1 (•|x), µ t (•|x)) ≤ ℓ t (x, •), µ t (•|x) -μt+1 (•|x) -D Ψ t x (μ t+1 (•|x), µ t (•|x)) where μt+1 (•|x) := arg min μ∈Ωx ℓ t (x, •), μ + D Ψ t x (μ, µ t (•|x))By optimality, μt+1 (•|x) verifies∇Ψ t x (μ t+1 (•|x)) = ∇Ψ t x (µ t (•|x)) -ℓ t (x,•) and the law of cosines yields0 = D Ψ t x (µ t (•|x), µ t (•|x)) = D Ψ t x (µ t (•|x), μt+1 (•|x)) + D Ψ t x (μ t+1 (•|x), µ t (•|x))- ∇Ψ t x (µ t (•|x)) -∇Ψ t x (μ t+1 (•|x)), µ t (•|x) -μt+1 (•|x) = D Ψ t x (µ t (•|x), μt+1 (•|x)) + D Ψ t x (μ t+1 (•|x), µ t (•|x)) -ℓ t (x, •), µ t (•|x) -μt+1 (•|x)Plugging this in the first inequality, we directly getℓ t (x, •), µ t (•|x) -q t (x) ≤ D Ψ t x (µ t (•|x), μt+1 (•|x)) and we get the individual upper bounds withD Ψ t x (µ t (•|x), μt+1 (•[x)) = α t (x)D Ψx (µ t (•|x), μt+1 (•[x)) = α t (x)D Ψ ⋆ x (∇Ψ x (μ t+1 (•[x)), ∇Ψ x (µ t (•|x))) = α t (x)D Ψ ⋆ x ∇Ψ x (µ t (•|x)) - 1 α t (x) ℓ t (x, •), ∇Ψ x (µ t (•|x))This upper bound on the estimated regret is then used with the learning rates considered in the main article.We first consider the optimal rates of the main paper. Theorem E.4. Using LocalOMD with µ 1 as the uniform policy, with the learning rates η t (x) = η/κ(µ s |x) where η = log(A)κ(µ s )/(3HT ), and with Ψ x the Shannon entropy Ψ x (µ) = a∈A(x) µ(a) log(µ(a)), the regret is bounded with a probability at least 1 -δ byR T min ≤ 4 + 2 √ 3 H 3/2 log(A)ικ(µ s )T where ι = log(2(A X + 1)/δ) .Proof. We apply Theorem E.3, using the relations α t (x) = 1/(µ s 1: (x)η t (x)) andI {x=x t h } ℓ t h = µ s 1: (x) ℓ t (x, •).We again separately bound the penalty and stability terms. Penalty term : We will denote by PEN this term defined byPEN := sup µ † ∈Πmin D dil α T (µ † 1: , µ 1 1: ) .By definition of the dilated entropy, we have, using that µ 1 is the uniform policy and that the Bregman divergence of the Shannon entropy is the Kullback-Leibler divergence,PEN = sup µ † ∈Πmin x∈X µ † 1: (x)κ(µ s |x) ηµ s 1: (x) D Ψ (µ † (•|x), µ 1 (•|x)) = 1 η sup µ † ∈Πmin x∈X µ † 1: (x)κ(µ s |x) µ s 1: (x) a∈A(x) µ † (a|x) log(µ † (a|x)/µ 1 (a|x)) ≤ 1 η sup µ † ∈Πmin x∈X µ † 1: (x)κ(µ s |x) µ s 1: (x) a∈A(x) µ † (a|x) log(1/µ 1 (a|x)) ≤ log(A) η sup µ † ∈Πmin x∈X µ † 1: (x) µ s 1: (x) κ(µ s |x) = log(A) η sup µ † ∈Πmin H h=1 x∈X h µ † 1: (x) µ s 1: (x) sup µ ′ ∈Πmin x ′ ∈X |x is in the history of x ′ a ′ ∈A(x ′ ) µ ′ h: (x ′ , a ′ ) µ s h: (x ′ , a ′ ) ≤ log(A) η H h=1 sup µ † ∈Πmin x∈X h µ † 1: (x) µ s 1: (x) sup µ ′ ∈Πmin x ′ ∈X |x is in the history of x ′ a ′ ∈A(x ′ ) µ ′ h: (x ′ , a ′ ) µ s h: (x ′ , a ′ ) (by independance) = log(A) η H h=1 sup µ † ∈Πmin x∈X h µ † 1: (x) µ s 1: (x) x ′ ∈X |x is in the history of x ′ a ′ ∈A(x ′ ) µ † h: (x ′ , a ′ ) µ s h: (x ′ , a ′ ) = log(A) η H h=1 sup µ † ∈Πmin x∈X h x ′ ∈X |x is in the history of x ′ a ′ ∈A(x ′ ) µ † 1: (x ′ , a ′ ) µ s 1: (x ′ , a ′ ) = log(A) η H h=1 sup µ † ∈Πmin x ′ ∈X a ′ ∈A(x ′ ) µ † 1: (x ′ , a ′ ) µ s 1: (x ′ , a ′ ) = log(A) η Hκ(µ s )where X h 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 bySTA := T t=1 x∈X α t (x)µ t 1: (x)D ⋆ x ∇Ψ x (µ t 1: (•|x)) - 1 α t (x) ℓ t (x, •), ∇Ψ x (µ t 1: (•|x))We first look at an upper-bound of D⋆ x ∇Ψ x (µ t 1: (•|x)) -1 α t (x) ℓ t (x, •), ∇Ψ x (µ t 1: (•|x)). In order to do so, we upper-bound (in the symmetric matrix sense) the Hessian of Ψ ⋆x on I := ∇Ψ and the Hessian of Ψ ⋆ x is given byx (µ t 1: (•|x)) -γ α t (x) ℓ t (x, •) γ ∈ [0, 1] . Because Ψ x (µ) = a∈A(x) µ(a)∇ 2 Ψ ⋆ (y) = ∇ 2 Ψ x (y) -1 = Diag{y(a)} a∈A(x) .In particular, it is upper bounded on I by the matrix D µ defined byD µ := Diag{µ(a)} a∈A(x)This yields thatD ⋆ x ∇Ψ x (µ t 1: (•|x)) - 1 α t (x) ℓ t (x, •), ∇Ψ x (µ t 1: (•|x)) ≤ 1 2 ∥ 1 α t (x) ℓ t (x, •)∥ 2 D t µ (•|x) = 1 2α t (x) 2 a∈A(x) µ t (a|x) ℓ t (x, a) 2 which leads to STA ≤ T t=1 x∈X µ t 1: (x) 2α t (x) a∈A(x) µ t (a|x) ℓ t (x, a) 2 = η 2 T t=1 x∈X I {x=x t h } µ t 1: (x) µ s 1: (x) 1 κ(µ s |x) a∈A(x) I {a=a t h } µ t (a|x) ℓ t h (a) 2 .We can first notice from recursively comparing the minimizer µ t+1 , re-using the notation at the beginning of the section, because the regularization does not evolve with time. The difficulty is now to upper bound STA with high probability. In order to do so, we use the Lemma B.1 on the sequence (U t ) t∈[T ] defined byU t := x∈X I {x=x t h } µ t 1: (x) µ s 1: (x) 1 κ(µ s |x) a∈A(x) I {a=a t h } µ t (a|x) ℓ t h (a) 2with γ ′ = γ ∈ (0, 1/(H 2 κ(µ s ))] and δ ′ = δ/2. This yields with probability at least 1 -δ/2T t=1 U t ≤ T t=1 E U t F t-1 + γ T t=1 E (U t ) 2 F t-1 + ι/γ .On the one hand, we have, using ℓ t h (a t h ) ≤ κ(µ s |x) and the previous inequality thatE U t F t-1 ≤ x∈X p t (x)µ t (x) a∈A(x)ℓ t,→x , µ t,→x h:≤ x∈X p t (x)µ t (x)H ≤ H 2 .On the other hand, using the same inequality,E (U t ) 2 F t-1 = E      x∈X I {x=x t h } µ t 1: (x) µ s 1: (x) a∈A(x) I {a=a t h } ℓ t h (a), µ t (a|x)   2 F t-1    ≤ HE   x∈X I {x=x t h } µ t 1: (x) 2 µ s 1: (x) 2 a∈A(x) I {a=a t h } ℓ t h (a) 2 , µ t (a|x) 2 F t-1   ≤ Hκ(µ s )E   x∈X I {x=x t h } µ t 1: (x) µ s 1: (x) a∈A(x) I {a=a t h } ℓ t h (a), µ t (a|x) F t-1   ≤ Hκ(µ s ) x∈X p t (x)µ t (x) a∈A(x) ℓ t,→x , µ t,→x h: ≤ Hκ(µ s ) x∈X p t (x)µ t (x)H ≤ H 3 κ(µ s ) .The following upper bound on the stability term thus holdsSTA ≤ η H 2 T + γH 3 κ(µ s )T + ι γ .Taking γ = 1/(H 2 κ(µ s )), we obtainSTA ≤ η 2H 2 T + H 2 ικ(µ s )As the bound of the theorem trivially holds if T < ικ(µ s ) (the regret being bounded by T anyway), we even have assuming T ≥ ικ(µ s ) STA ≤ 3ηH 2 T .Combining all the previous bounds, the estimated regret is bounded, with a probability of at least 1 -δ/2 by RT ≤ log(A) η Hκ(µ s ) + 3ηH 2 T .Taking η = log(A)κ(µ s )/(3HT ), we obtainRT ≤ 2 √ 3 H 3/2 log(A)ικ(µ s )T .We finally conclude by combining this bound with Theorem 2.2 for the true regret, using δ ′ = δ/2, such that the two inequalities hold with a probability at least 1 -δ.We end this appendix by considering the adaptive setting. We will assume that all regularizers Ψ x are 1-strongly convex with respect to some norms ∥•∥ x , and we will defineC Ψ : = sup x∈X ,µ∈∆ Ax D x (µ, µ 1 (•|x)) C ⋆ Ψ : = sup x∈X ,a∈Ax ∥I {x,a} ∥ ⋆ xwhere µ 1 is the initial policy considered in the algorithm and I {x,a} is the loss vector ℓ(x, •) equal to 1 for a ∈ A(x) and 0 for a ′ ∈ A(x)\ {a}. The following theorem is the formal statement of Theorem 4.1 in the main article. While being quite general, the upper bound is unsurprisingly not as tight as the previous one.Theorem E.5. With such regularizers, assume that the learning rates are locally decreasing and let λ 1 , λ 2 ∈ R >0 be two constants such that for all information set x ∈ X ,max t∈[T -1] 1 η t+1 (x) - 1 η t (x) ≤ λ 1 and 1/η T (x) + T t=1 η t (x)I {x=x t h } ≤ λ 2 √ TThen with a probability at least 1 -δ, the regret of Algorithm 2 is upper-bounded byR T max ≤ 2 [(1 + λ 1 ) C Ψ C ⋆ Ψ κ(µ s )] 2 λ 2 |X | + 4 Hκ(µ s )ι √ Twhere ι = log((A X + 1)/δ).The proof of this theorem will be based on the following lemma that bounds the regularized loss using the λ 1 constant above. Lemma E.6. For all t [T ] and h ∈ [H],ℓ t h (a t h ) ≤ (1 + λ 1 C Ψ )κ(µ s |x t h ) .Proof. The proof is done recursively on h, starting from the leaves. Indeed, for h = H, the property is immediate asℓ t h (a t h ) ≤ 1/µ s (a t H |x t H ) ≤ κ(µ s |x t H ).If we assume that the property holds for a depth h > 1, thenq t h = min µ∈∆ A(x t h ) ℓ t h , µ + 1 η t (x t h ) D x µ, µ t (•|x t h ) + 1 η t+1 (x t h ) - 1 η t (x t h ) D x µ, µ 1 (•|x t h ) ≤ ℓ t h , µ t (•|x t h ) + 1 η t+1 (x t h ) - 1 η t (x t h ) D x µ t (•|x t h ), µ 1 (•|x t h ) ≤ ℓ t h (a t h ) + λ 1 C Ψ . Then ℓ t h-1 (a t h-1 ) = (ℓ t h-1 + q t h )/µ s (a t h-1 |x t h-1 ) ≤ (1 + λ 1 C Ψ + ℓ t h (a t h ))/µ s (a t h-1 |x t h-1 ) ≤ (1 + λ 1 C Ψ )(1 + κ(µ s |x t h ))/µ s (a t h-1 |x t h-1 ) ≤ (1 + λ 1 C Ψ )κ(µ s |x t h-1) which concludes the induction.Proof. We now prove the theorem. We start with the estimated regret, that we decompose between the penalty term and the stability term using theorem E.3.The penalty term PEN is bounded byPEN ≤ sup µ † ∈Πmin D dil α T (µ † 1: , µ 1 1: ) ≤ sup µ † ∈Πmin x∈X 1 η T (x) µ † 1: (x) µ s 1: (x) D x (µ † (•|x), µ 1 (•|x)) ≤ C Ψ λ 2 √ T sup µ † ∈Πmin x∈X µ † 1: (x) µ s 1: (x) ≤ C Ψ λ 2 κ(µ s ) √ T .Stability term: For the stability term STA, we rely on Lemma E.6 and the 1-strong convexity of Ψ x with respect to ∥•∥ x (see Appendix D.1) and getSTA = T t=1 x∈X α t (x)µ t 1: (x)D ⋆ x ∇Ψ x (µ t 1: (•|x)) - 1 α t (x) ℓ t (x, •), ∇Ψ x (µ t 1: (•|x)) ≤ T t=1 x∈X µ t 1: (x) α t (x) ∥ ℓ t (x, •)∥ ⋆ 2 x ≤ T t=1 x∈X η t (x)I {x=x t h } µ t 1: (x) µ s 1: (x) ∥ ℓ t h ∥ ⋆ 2 x ≤ [C ⋆ Ψ ] 2 T t=1 x∈X η t (x)I {x=x t h } µ t 1: (x) µ s 1: (x) ℓ t h (a t h ) 2 ≤ [(1 + λ 1 ) C Ψ C ⋆ Ψ ] 2 T t=1 x∈X η t (x)I {x=x t h } µ t 1: (x) µ s 1: (x) κ(µ s |x) 2 ≤ [(1 + λ 1 ) C Ψ C ⋆ Ψ 2 κ(µ s ) T t=1 x∈X η t (x)I {x=x t h } 1 µ s 1: (x) κ(µ s |x) ≤ [(1 + λ 1 ) C Ψ C ⋆ Ψ κ(µ s )] 2 T t=1 x∈X η t (x)I {x=x t h } ≤ [(1 + λ 1 ) C Ψ C ⋆ Ψ κ(µ s )] 2 λ 2 |X | √ T .By summing these two upper bounds we getRT ≤ C Ψ λ 2 κ(µ s ) + [(1 + λ 1 ) C Ψ C ⋆ Ψ κ(µ s )] 2 λ 2 |X | √ T ≤ 2 [(1 + λ 1 ) C Ψ C ⋆ Ψ κ(µ s )] 2 λ 2 |X | √ TThe bound is finally obtained using the Theorem 2.2 that holds with a probability of at least 1 -δ and links the estimated regret to the true regret.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 in 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.For algorithms with a probability at least 1 -δ of a correct output, the symbol O hides dependencies logarithmic in AX , BY and δFarina, G., Kroer, C., and Sandholm, T. Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions. In Advances in Neural Information Processing Systems, 2019a. 


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

Reviews: review: paper_summary: paper_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.

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

The 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.
strength_weakness: strength_weakness: 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.

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

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).
questions: questions: No specific questions beyond the weaknesses mentioned above.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

2. 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.
questions: 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: limitations: /
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.

[1] From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020)

[2] A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games (2023)

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

Comments: title: Response
comment: Thank you for your detailed response; my understanding of your paper and contribution has improved and I have raised my score.

I hope that the authors consider the suggestions provided by reviewers from past submissions and the current submission. Going back to suggestions pointed out in a review of an earlier submission, even the very minor point of correcting the stylization of the game "Liar's Dice" was not corrected, even though this was acknowledged by the authors as something to be fixed. I only bring this up because as I noted in my review there was not much change in this submission relative to the last submission that I reviewed (indeed, this is why I pointed out "weaknesses" corresponding to discussion between past reviewers and the authors); I hope that if the paper gets accepted, the authors end up implementing the changes they suggest they will in their rebuttals.

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

I agree that would make a good addition to the conclusion.

> That is why we finally decided to skip them. If a reviewer thinks that those explanations should be inserted here from existing papers, we could use the extra-page to include them nonetheless.

Makes sense. I agree that it is not necessary to include them in the main body to prevent the obfuscation of the contribution of this paper.
Sorry, our response to this remark may not have been very clear. The first two paragraphs were about their theoretical setting (with a regularized full feedback and on-policy), but the third paragraph was indeed referring to these experiments with trajectory feedback, trying to bridge the gap between the two.

We think that proving guarantees for their algorithm would be a very good contribution, but we do not know yet if it is doable (maybe this would not work well on carefully engineered games).

The main difficulty is the regularization: this kind of update can make sense theoretically if the regularization is chosen to compensate for it at each iteration. However, this also implies that the solution of the regularized game changes over time, which is hard to analyze.
> We thank Reviewer HP7A for pointing out these empirical results and we will add this reference in our literature review. Before 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 they consider (in our case, would be). This strong monotonicity assumption does not hold for their experiments, as the operator is linear with respect to the realization plan, hence they need to add some regularization, parameterized by the constant. Second, they consider a full feedback setting in theory, observing the outcomes of all possible trajectories at each episode.

There may be a misunderstanding about the point I was making here. I was specifically pointing to their experiments with black box feedback (not full feedback) in Figure 13. The reference provides no theory for these experiments, but I think they are still interesting because they seem to be converging 1) on policy, 2) without importance sampling over sequences, 3) using black box feedback. I would be curious to hear any speculation the authors' may have on whether or not deriving guarantees for algorithms having those properties is a promising direction for this literature.