The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback Côme Fiegel 1 2 Pierre Menard 3 Tadashi Kozuno 4 Michal Valko 5 Vianney Perchet 1 2 6
arXiv:2604.16087v1 [cs.LG] 17 Apr 2026
Abstract
edly playing the game. Specifically, we consider the bandit feedback setting, where the payoff matrix is unknown and players only observe their losses or rewards.
We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of O(T −1/8 ) on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being Ω(T −1/4 ) in contrast to the usual Ω(T −1/2 ) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
Within the context of uncoupled learning, each player learns the minimax policy independently, without communication or knowledge of their opponent’s actions. This setup motivates the use of methods similar to those employed in classical single-player online learning (Cesa-Bianchi & Lugosi, 2006), where a player adapts to play optimally in an adversarially changing environment. These methods usually bound the player’s regret, defined as the difference between the best possible cumulative loss under a fixed policy and the actual cumulative loss incurred by the player. They are known to be applicable in the context of games to compute minimax policies (Cesa-Bianchi & Lugosi, 2006). They however have two well-known weaknesses: • The policies played over the iterations generally do not converge or even approach an equilibrium. • Instead, the average policy is computed and outputted as a proxy for convergence. While averaging tabular policies is simple and inexpensive, this step is not as simple for practical applications. For instance, it is not clear how to compute the average of policies represented by a neural network (Heinrich et al., 2015; McAleer et al., 2022).
1. Introduction In zero sum matrix games, two players each take a single action and accordingly receive for the first player a loss and the second player a gain of the same magnitude. Such games always admit for each player at least one minimax policy (a specific case of Nash equilibrium), assuming a stochastic choice of action (v. Neumann, 1928). Computing these policies, however, is non-trivial and requires knowledge of the underlying game matrix of payoffs.
In part for this reason, a significant portion of the recent literature studies methods with last-iterate convergence for which the actual policies played over time converge toward a Nash equilibrium. Some algorithms, such as Optimistic Mirror Descent (OMD, Popov 1980; Rakhlin & Sridharan 2013), exhibit this convergence despite being initially proposed for their regret-bounding properties, but with a vastly different analysis. For the OMD algorithm, in the deterministic full-information feedback setting, the rate of convergence of the exploitabilty gap toward zero is even improved, transitioning from O(1/T ) for the average to a linear rate for the last iterate (Wei et al., 2021).
We are interested in learning minimax policies by repeat*
Equal contribution 1 ENSAE Paris - CREST, Palaiseau, France Inria - FairPlay 3 ENS Lyon, Lyon, France 4 OMRON SINIC X, Tokyo, Japan 5 Stealth AI Startup / Inria / ENS 6 Criteo AI Lab, Paris, France. Correspondence to: Côme Fiegel <[email protected]>. 2
Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
However, the literature on last-iterate convergence with stochastic feedback is limited, and even more so when con1
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
sidering bandit feedback. While properties of the last-iterate convergence have been studied in the broader context of stochastic variational inequalities, these works often rely on assumptions that are not applicable to matrix games, such as second-order sufficiency (Azizian et al., 2021), in addition to not accounting for the bandit feedback aspect.
the output of the underlying algorithm, which is here regret-based.
• We also propose a more practical algorithm, based on a strong regularization of the problem, which does not require the computation of an average policy. It enjoys a O(T −1/4 ) rate, thanks to the use of an unbiased estimate of the losses in contrast to previous approaches. However, even if the last iterate converges, the algorithm is not completely anytime as the regularization must be chosen with the knowledge of the horizon T . To address this limitation, a doubling trick approach is stated, which features the same explorationexploitation trade-off.
Recently, some methods (Cai et al., 2023; Dong et al., 2024) were proposed for this specific problem. They however only obtained an upper bound of O(T −1/8 ) on the exploitability gap with high probability 1 . Considering the best known lower bound was Ω(T −1/2 ) from a reduction to the K-arms bandit problem, Cai et al. (2023) raised the question of whether a better lower bound was achievable. In this work, we address the following question: What is the best attainable rate for last-iterate convergence of uncoupled learning with bandit feedback in matrix games?
The different rates are summarized in Table 1.
2. Contributions 3. Related works
We focus in the above settings on zero-sum matrix games.
Variational inequalities The problem of finding a Nash equilibrium for a matrix game can be formulated as finding the solution of a specific Lipschitz variational inequality (Mancino & Stampacchia, 1972), which is furthermore monotone when the game is zero-sum.
• We provide a better lower bound for the problem of learning a minimax profile with uncoupled convergent algorithms and bandit feedback. This lower bound, of Ω(T −1/4 ) for the Lp convergence given p ∈ [2, ∞], shows that guaranteeing last-iterate convergence is harder than just guaranteeing convergence for the average iterates, which can be done at a rate O(T −1/2 ).
Finding algorithms for solving monotone variational inequalities is a major part of the optimization literature, starting with the proximal point algorithm (Martinet, 1970; Tyrrell, 1976). In particular, using two samples at each iteration, the Extra-Gradient method (Korpelevich, 1976; Nemirovski, 2004) has a O(1/T ) convergence for the average iterate. With a strongly monotone operator, the rate is even linear (Facchinei & Pang, 2004) for the last iterate.
Intuitively, this relies on the fact that, at least for some simple 2 × 2 games, there exists a minimax policy for one player that renders all actions of the other player equivalent, thereby preventing any learning on their part. Meanwhile, a policy converging to this minimax policy may not entirely prevent learning but will significantly slow it down, as the difference between the two action rewards converges to zero.
For stochastic variational inequality, in which only an unbi√ ased estimate of the operator is observed, a rate O(1/ T ) is obtained by Juditsky et al. (2011) for the average iterates. For strongly monotone operators, this rate can be improved to O(1/T ) (Nemirovski et al., 2009).
• This lower bound is also stated for p ∈ (0, 2], for which it improves to Ω(T −1/(2+p) ).
An important way to generalize some of the aforementioned methods is through the mirror descent approach, which extends Euclidean methods to other geometries, as discussed by Nemirovskiı̆ & IUdin (1983). This generalization is particularly crucial when dealing with bandit feedback, with the EXP3 algorithm, introduced by Auer et al. (2002), serving as a key example of this approach under the Kullback-Leibler geometry.
• We propose a general simple framework for transforming an algorithm with classical anytime guarantees into one with last-iterate guarantees, based on a simple exploration-exploitation trade-off. We use this framework to show that the above lower bound is tight: with e −1/(2+p) ) the EXP3-IX of Kocák et al. (2014), a O(T p rate can be attained for the L convergence, given any p in (0, 2]. However, the computation of some average policies is still needed, as the framework relies on
Instead of relying on two samples at each iteration as in the Extra-gradient method, the Optimistic Mirror Descent reuses the previous one as an estimate. While it can be traced back to Popov (1980), it has regained interest relatively recently (Chiang et al., 2012; Rakhlin & Sridharan, 2013).
1 Dong et al. (2024) obtained a rate O(T −1/4 ) on the KullbackLeibler divergence between the profile and the Nash equilibrium, which only translates in general into a rate O(T −1/8 ) for the exploitability gap
2
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Algorithm
Convergence
Rate
Cai et al. 2023 (Algorithm 1) Dong et al. 2024 (Algorithm 1)
High probability L2 High probability
e −1/8 ) O(T e −1/6 ) O(T e −1/8 ) O(T
Simultaneous Explore or Exploit (this paper) Uncoupled Regularized EXP3 (this paper)
Lp , p ∈ (0, 2] L2
e −1/(2+p) ) O(T e −1/4 ) O(T
Lower bound (this paper)
Lp , p ∈ (0, 2]
O(T −1/(2+p) )
e Table 1. Rate of convergence of the exploitability gap of algorithms with last-iterate guarantees under bandit feedback. The notation O hides logarithmic dependences in T , and in δ for algorithms that converges with probability at least 1 − δ.
Learning in games In the case of a deterministic feedback, classical√regret-bounding algorithms can be shown to enjoy a O(1/ T ) rate for the average iterates. Optimistic mirror descent in particular improves this rate to O(1/T ) (Rakhlin & Sridharan, 2013; Kangarshahi et al., 2018). Using a problem-dependent constant, the rate can even be shown to be linear (Tseng, 1995; Wei et al., 2021) for the last iterate. However, Cai et al. (2024) recently proved that for some algorithms, including OMD, obtaining a O(1/T ) rate for the last iterate without this problem-dependent constant is impossible.
max-player wants to maximize it. The two players are allowed to play stochastically: they n Pchoose two omixed policies µ ∈ A ∆A := µ, a=1 µ(a) = 1 and ν ∈ ∆B := n P o B ν, b=1 ν(b) = 1 and optimize their choice according to the expected loss L(µ, ν) defined by: L(µ, ν) = Ea∼µ,b∼ν [L(a, b)] . A tuple (µ, ν) ∈ ∆A × ∆B of policies will be called a profile
This work focuses on learning a minimax strategy with bandit feedback using uncoupled algorithms. In the context of smooth monotone games, several recent studies, building on the foundational work of Bravo et al. (2018), have explored a setting where only the value associated with the chosen policy profile is observed (Hsieh et al., 2019; Drusvyatskiy et al., 2022; Tatarenko & Kamgarpour, 2022; Huang & Hu, 2024; Ba et al., 2025). However, this approach does not account for the inherent stochasticity present in the K-arms bandit problem:: particularly in matrix games, this observed value represents the average of the rewards under the policies, rather than the reward of a single sampled action profile.
We look to obtain a minimax profile (a special case of the later Nash-equilibrium, Nash Jr 1950), defined as a profile (µ⋆ , ν ⋆ ) that satisfies µ⋆ ∈ arg min L(µ† , ν ⋆ ) µ† ∈∆A
and
ν ⋆ ∈ arg max L(µ⋆ , ν † ) , ν † ∈∆B
whose existence is guaranteed (v. Neumann, 1928). The proximity of a profile (µ, ν) to the set of Nash equilibria can be characterized using the exploitability gap: EG(µ, ν) = − min L(µ† , ν) + max L(µ, ν † ) µ† ∈∆A
ν † ∈∆B
Note that the exploitability gap is zero if and only if (µ, ν) is a Nash equilibrium.
Meanwhile, Abe et al. (2023) considered a stochastic feedback, but without the specific bandit aspect. Muthukumar et al. (2020) showed an impossibility result that some of the algorithms with no-regret guarantees cannot converge almost surely to a Nash equilibrium.
Sequential learning with bandit feedback We assume that at each iteration t, both players select some policies µt and ν t , sample two actions at ∼ µt and bt ∼ ν t , and get a stochastic loss ℓt ∈ [0, 1] associated to these two moves. Formally, we assume the existence, for each a ∈ A and b ∈ B, of a probability distribution p(a, b) on [0, 1] such that
In our setting, Cai et al. (2023) recently showed that a O(T −1/8 ) rate can be attained, a result later extended by Dong et al. (2024) to smooth monotone games.
∀t ∈ N, ℓt |F t−1 , at , bt ∼ p(at , bt )
4. Setting
and
Zero-sum matrix game Two players, called the min- and the max-player, respectively play actions a ∈ A and b ∈ B, in sets of cardinality A and B, to receive a loss L(a, b) ∈ [0, 1]: the min-player wants to minimize this loss, while the
Eℓ∼p(a,b) [ℓ] = L(a, b)
where F = (F t )t∈N is a filtration recursively defined by the observations, F t = σ ω, a1 , b1 , ℓ1 ..., at , bt , ℓt , 3
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
5. Lower bound
with ω the internal randomness (extra to the sampling of actions) of both players.
In this section, we establish that these assumptions combined are quite restrictive. Especially, we show it is impossible to guarantee a better rate than ⊗(T −1/(2+p) ) for the Lp last-iterate convergence with p ∈ (0, 2].
This filtration summarizes all information available to both players up to the beginning of round t + 1. A sequence of profile (µt , ν t )t∈N will especially be called a learning sequence if it is predictable with respect to F.
For this purpose, we will consider the following 2×2 games, for any ε ∈ [−1/12, 1/12]: B(2/3 − ε) B(1/3 + ε) Mε = B(1/3) B(2/3)
Last-iterate convergence We define, for all p > 0 the F -norm ∥·∥p (Banach, 1932) for some real random variable X by p 1
where B denotes a Bernoulli distribution.
∥X∥p := E [|X| ] p .
For these games, regardless of the choice of ε in the domain, it is easily shown that 1/2 ⋆ ν = 1/2
t
Now, let f = (f )t∈N be a positive sequence decreasing to 0. A learning sequence (µt , ν t ) will satisfy a Lp last-iterate convergence of rate f if
is the only min-max max player policy, with an associated value of 1/2. Furthermore, the exploitability gap of any profile (µt , ν t ) is at least proportional to the distance |δ t | between ν t and ν ⋆ , with δ t = ν t (1) − 1/2.
∀t ∈ N, ∥EG(µt , ν t )∥p ≤ f t . It is asymptotic if there simply exists some T0 ∈ N such that
On the contrary, the min-max min-player policy depends on the choice of ε, as there exists no policy for the min-player policy that is good regardless of this choice. Especially, the exploitability gap of any profile (µ, ν) can be shown to be at least proportional to |ε| for one of the two games M −ε and M ε .
∀t ≥ T0 , ∥EG(µt , ν t )∥p ≤ f t . This requires both players to play policies they deem nearoptimal during each iteration, instead of simply outputting one good policy each at the end of the procedure.
We therefore assume that the game matrix is either M ε or M −ε , but that the exact choice is unknown. At each iteration t, conditioning on F t−1 , the law of the reward vector (i.e. the law of the rewards for each action) for the min-player is given by: B (1/2 + δ t /3 − 2δ t ε) with M ε : B (1/2 − δ t /3) B (1/2 + δ t /3 + 2δ t ε) with M −ε : , B (1/2 − δ t /3)
Output convergence On the other end, an algorithm has an Lp output convergence of rate g, with g = (g t )t∈N a sequence decreasing to 0, if it can output a learning sequence (µ̂t , ν̂ t ) such that: ∀t ∈ N, ∥EG(µ̂t , ν̂ t )∥p ≤ g t . This restriction is weaker than the previous last-iterate convergence, as it does not put any constraint on the actual policies played at each round. It however still forces the algorithm to have anytime guarantees.
where we re-used the value δ t characterizing the difference between ν t and the min-max policy ν ⋆ . Guaranteeing an exploitability gap in o(ε) at any horizon T implies the min-player can discriminate between these two options. Using some additive properties of the KullbackLeibler divergence, we know that, without the observation of the max-player actions (bt )t∈N , this discrimination is only possible with an arbitrarily high probability when:
Uncoupled algorithm We say an algorithm is uncoupled if it independently controls the two players, without active communication between the two instances. In particular, we assume that observation of the opponent’s action is not possible. This definition is a bit informal as completely characterizing the impossibility of communication is hard mathematically. Indeed, even if direct communication is forbidden, the two instances are not isolated as the loss of one player still depends on the actions of the other. Nothing technically prevents one player from passing bits of information to the other through artificial choices of policies.
T X
µt (1)(δ t ε)2 I{at =1} = Ω(1) .
t=1
Given full control of δ t over the iterations, the ideal choice would be δ t = ±1/2, which gives the usual lower bound 4
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
|ε| ≥ Ω(T −1/2 ). However, the last-iterate convergence assumption implies that δ t must also converge to 0. Depending on how strong this convergence of δ t must be, the minimum value of |ε| that allows the discrimination greatly increases.
Algorithm 1 Simultaneous Explore or Exploit 1: Input: Algorithm A with Lp output convergence Sequence (pt ) ∈ [0, 1] 2: Initialize: k 0 ← 0 Draw u ∼ U ([0, 1]) common to both players 3: Algorithm: t = 1 to +∞: PFor t k t ← ⌊ i=1 pi + u⌋ If k t > k t−1 : t kt Play current profile (µkA , νA ) and update algorithm A Otherwise: t kt Play the output (µ̂kA , ν̂A ) 4: Output: Learning sequence of policies with L2 lastiterate convergence
This idea is formalized in the following theorem, proven in Appendix A. Theorem 5.1. Assume that the sampled action bt ∼ ν t of the max-player at each iteration t is never observed. Then, for any p ∈ (0, 2], no learning sequence can achieve simultaneously for all 2 × 2 matrix games described above an Lp last iterate convergence of −1
−1 4 p 2+p f = t , 118
t
even asymptotically. Remark 5.2. As mentioned in Section 4, the uncoupling of the two instances is hard to formalize mathematically. In the above theorem, this formalization is done through the assumption that the max player’s sampled action is never observed. As the max-player already knows its optimal policy ν ⋆ and consequently does not need this knowledge for learning, we consider this assumption to be reasonable.
vergence. Indeed, the anytime version of EXP3-IX (Kocák e −1/2 ) for the et al., 2014; Neu, 2015) achieves a rate of O(t average profile with high probability, which can be translated into the same rate for the Lp output convergence for any p > 0. While these two ways of converging are not equivalent, there is a procedure that transforms any algorithm A with Lp output convergence guarantees into one with Lp lastiterate convergence, at a price of a worse rate. The idea is simple: at each iteration, either both players ”explore” by playing one iteration of A and updating accordingly, or ”exploit” by both playing the current estimate.
Furthermore, this assumption of not observing the opponent’s moves is important for the rate. Indeed, the observation of these moves would allow the estimation of each e t−1/2 , assuming that entry of the game matrix at a rate O each action is played for a non-negligible proportion of the iterations. With this estimated game matrix, asymptotically playing the associated minimax profile would lead to the e t−1/2 rate for the exploitability gap. same O
If the probabilities (pt )t∈N of exploring at each iterations satisfy: lim pt = 0 t→ − +∞
and
+∞ X
pt = +∞ ,
The p > 2 case: Theorem 5.1 only deals with p ∈ (0, 2). For p ∈ (2, ∞], using ∥·∥p ≤ ∥·∥2 for any random variable (Rudin, 2006), we immediately get the following corollary. Corollary 5.3. Under the same assumption as Theorem 5.1, for any p ∈ (2, ∞], no learning sequence can achieve simultaneously for all 2 × 2 matrix games described above an Lp last iterate convergence of 1 −1 ft = t4 , 236 even asymptotically.
the resulting learning sequence has last-iterate convergence. Indeed, the first condition makes the exploration contribution to the exploitability gap negligible asymptotically, while the second ensures that the outputs of A converge to some minimax policies.
The next section shows that the lower bound cannot be improved in rate for p ∈ (0, 2], as it is tight up to some constant and logarithmic factors. We conjecture that, despite the above loose bounding, it also cannot be improved for p ∈ (2, ∞).
The procedure is summarized in Algorithm 1. The following lemma, proven in Appendix B, formalizes the above intuition, given some rate for the output of algorithm A.
t=1
The players need to be synchronized in their choices of exploration and exploitation steps. This can be done by sharing a single seed u ∼ U ([0, 1]) as shown in Lemma B.1 of the appendix.
Lemma 6.1. Assume that A satisfies an output convergence of rate g. Then Algorithm 1 satisfies an Lp last iterate convergence of rate f defined by
6. Exploration-Exploitation trade-off The above theorem shows that for uncoupled algorithms, Lp last-iterate convergence is strictly harder than output con-
1
ft = 2p 5
h
i 1 t pt p + g r
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
where rt =
jP t
k k p . k=1
theoretically prevents the convergence to the minimax policy, even in average (Kozuno et al., 2021). A simple way to counteract this issue is to use IX estimation (Neu, 2015) and add an additive term γ t to the denominator, but this biases the estimation and potentially worsens the rate. Theorem 7.2 shows that this bias is not necessary, at least for the L2 convergence.
We obtain the following theorem with the anytime version of EXP3-IX and the appropriate parameters. Theorem 6.2. Using Algorithm 1 with probabilities pt = t−p/(2+p) , and as A, the p algorithm EXP3-IX with paramt t eters ηmin = 2γmin = p log(A)/ (At) for the min-player t t and ηmax = 2γmax = log(B)/ (Bt) for the max-player, p we obtain an L last-iterate convergence rate of √ 1 1 f t = 17 A + B 2 p t− 2+p log 4(A + B)t2 /p .
Regularization Given τ > 0, we define the regularized zero-sum game Lτ over ∆A × ∆B with Lτ (µ, ν) = Eµ,ν [L(a, b)] + τ DKL (µ, µ0 ) − τ DKL (ν, ν 0 )
−1
e 2+p ) menThis approach thus reaches the optimal rate O(t tioned above for the Lp convergence, up to some logarithmic and constant factors. However, it has several drawbacks that make it not applicable in real settings:
where DKL is the Kullback-Leibler divergence between two distributions and (µ0 , ν 0 ) an arbitrary profile. This game admits a unique Nash equilibrium, which will be denoted by (µ⋆,τ , ν ⋆,τ ).
• No communication is required, but the players are not truly uncoupled in the usual sense as they still need to share a common seed (a sample from a uniform law at the beginning of the game). Note that this does not go against the hypothesis of Theorem 5.1, as this seed can be the random variable ω of the filtration F.
Similarly to the regularization of a convex function in order to make it strongly convex, the point of this transformation is to transform the monotone pseudo-gradient operator F : ∆A × ∆B → − RA+B defined by F (µ, ν) := (∇µ L(µ, ν), −∇ν L(µ, ν)) into a strongly monotone operator F τ (µ, ν) := (∇µ Lτ (µ, ν), −∇ν Lτ (µ, ν)), which satisfies, for all (µ, ν), (µ′ , ν ′ ) ∈ ∆A × ∆B :
• The exploitation steps are only performed to respect the anytime guarantees and have no practical use.
⟨F τ (µ, ν) − F τ (µ′ , ν ′ ), (µ − µ′ , ν − ν ′ )⟩ 2 2 ≥ τ ∥µ − µ′ ∥1 + ∥ν − ν ′ ∥1 .
• One of the main points of the last-iterate convergence is to avoid the computation of the average necessary in the regret-based algorithm. Not only is this computation still required here (the output of EXP3-IX is an average), but also needs to be done at almost every iteration.
A higher τ allows for faster convergence but at the price of a slightly different Nash-equilibrium (µ⋆,τ , ν ⋆,τ ). This implies a trade-off, as the exploitability gap of this regularized Nash equilibrium for the base game can be shown to be at most proportional to τ .
7. Regularized mirror descent Because of these drawbacks, we propose another algorithm instead based on some regularized dynamics for the convergence.
Regularized updates Given τ > 0, a common way of updating is to do a mirror-descent with the regularized pseudogradient F τ , which is for example used by in this setting Cai et al. (2023). We instead use the following updates:
Loss estimation As explained in the settings, at each iteration t, the mean loss vectors L(·, ν t ) and 1 − L(µt , ·) for respectively the min and max players are not observed, only one sample ℓt is observed by both players. It can however be estimated through the importance sampling estimators:
µt = arg min(1 − τ η t )DKL (µ, µτ,t ) + τ η t DKL (µ, µ0 )
ℓ̂tmin =
µ∈ ∆A t
ν = arg min(1 − τ η t )DKL (ν, ν τ,t ) + τ η t DKL (ν, ν 0 ) ν∈∆B D E τ,t+1 µ = arg min η t ℓ̂tmin , µ + DKL (µ, µt )
ℓ̂t I{a=at } µt (at )
µ∈∆A
D E ν τ,t+1 = arg min η t ℓ̂tmax , ν + DKL (ν, ν t ) .
1 − ℓ̂t ℓ̂tmax = t t I{b=bt } . ν (b )
ν∈∆B
While these estimators are unbiased, their variance is not bounded as the probabilities associated to any action can become arbitrarily small. For this reason, their use alone
This method is similar to the one proposed by Munos et al. (2023), but is here able to deal with non-symmetric games and bandit feedback. It works in two steps. First, the two 6
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Algorithm 2 Uncoupled Regularized EXP3 1: Input: Learning rates η t > 0 Regularization parameter τ > 0 2: Algorithm: Initialize µτ,1 and ν τ,1 to the uniform policies µ0 and ν 0 . For t = 1 to +∞: µt ← arg minµ∈ ∆A (1 − τ η t )DKL (µ, µτ,t ) + τ η t DKL (µ, µ0 ) ν t ← arg minν∈∆B (1 − τ η t )DKL (ν, ν τ,t ) + τ η t DKL (ν, ν 0 ) Sample and play at ∼ µt , bt ∼ ν t Observe ℓt D E µτ,t+1 ← arg minµ∈∆A η t ℓ̂tmin , µ + DKL (µ, µt ) D E ν τ,t+1 ← arg minν∈∆B η t ℓ̂tmax , ν + DKL (ν, ν t ) t
The following theorem, proven in Appendix C, formalizes this idea and provides guarantees for the final output of Algorithm 2. Theorem 7.2. Let T be a fixedp horizon. Then, using regular1/4 ization τ = ((A + B) /T ) 2/ (log(A) + log(B)) and the learning rates η t = 2/(τ (t + 1)) for all t, Algorithm 2 guarantees 1/4 p √ A+B T T ∥EG(µ , ν )∥2 ≤ 3 2 log(AB) . T With the correct choice of regularization, Algorithm 2 therefore benefits from an optimal L2 rate of O(T −1/4 ) for the final output. However, as explained above, this choice of regularization depends on the horizon T , and the above rate is thus only guaranteed near the final output. The actual last-iterate guarantee of the whole sequence up to T is given by T 1/4 f t ≍ min 1, 1/2 t
t
where ℓ̂tmin = µtℓ(at ) I{at } and ℓ̂tmax = ν1−ℓ t (bt ) I{bt } 3: Output: Learning sequence (µt , ν t ).
policies are regularized proportionally to the learning rate. This gives the two policies µt and ν t that are used to sample ℓt . Then a regular mirror step update (with the KullbackLeibler divergence) is applied with the unbiased estimate of the loss. The whole procedure is summarized in Algorithm 2.
which technically does not match the lower bound of Theorem 5.1. Remark 7.3. An intuitive way of fixing this issue would be to use an adaptive regularization parameter τ t ≍ t−1/4 that decreases over time. Unfortunately, we failed to show the convergence of this method. The main reason is that, while the regularized solution can be shown to converge to the minimax profile minimizing the entropy as τ t goes to 0, the convergence is sometimes too slow when one of the two minimax policies is on the border of the simplex. This can be interpreted through the perspectives of Azizian et al. (2021): the Legendre exponent of the entropy is different on the border.
These updates allow a relatively simple bound on the Kullback-Leibler divergence between the intermediate profiles (µτ,t , ν τ,t ) and the regularized Nash equilibrium, proven in Appendix C. Lemma 7.1. Let τ ∈ (0, 1]. Taking η t = 2/ (τ (t + 1)) along with µτ,1 = µ0 and ν τ,1 = ν 0 the uniform policies gives with the above updates 2(A + B) E DKL (µτ,⋆ , µτ,t ) + DKL (ν τ,⋆ , ν τ,t ) ≤ τ2 t for all t ∈ N.
8. Doubling trick and regularization In order to get the anytime guarantees required for Algorithm 2, the usual solution in the online learning literature is the doubling trick. It consists in starting the algorithm with a small horizon T1 , and recursively restarting it every time the horizon is reached with a new horizon Ti = 2Ti−1 . However, its use is not straightforward for this problem, as a complete restart of the algorithm would go directly against the last-iterate convergence assumption.
To our knowledge, this is the first result of a O(1/(τ 2 T )) rate for the Kullback-Leibler divergence between the regularized solution of a game and the iterates under the bandit √ setting for a matrix game. This improves the rate O(1/τ t) obtained by Dong et al. (2024), although this latter result was obtained with high probability (and not only in expectation), in addition of holding for any τ -strongly monotone operator.
For this reason, we propose to use the doubling trick with a slight adjustment. Instead of directly restarting with a weaker regularization and discarding the current iterate after every subloop i, the meta-procedure will perform a trade-off between playing the old instance i − 1, which has already been played over many iterations, and the new instance i, which has better asymptotical guarantees. Specifically, it will play the new instance with a certain probability pji , close to 0 at the beginning and increasing to 1 over the iteration
Using Pinsker inequality (Pinsker, 1964), this results in √ a O(1/(τ T )) bound for the 1-norm between (µτ,t , ν τ,t ) and (µτ,⋆ , ν τ,⋆ ). Considering that the gap between Lτ , for which (µτ,⋆ , ν τ,⋆ ) is optimal, and that L is at most proportional to τ , the best value of√τ for the trade-off seems to be obtained when τ ≍ 1/(τ T ) where ≍ denotes asymptotic equivalence up to a constant. This corresponds to τ ≍ T −1/4 , 7
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Algorithm 3 Doubling trick approach 1: Input: Algorithms A0 , A1 , A2 , ... Horizons T1 , T2 , ... ∈ N Parameters S1 , S2 , ... ∈ R>0 2: Initialize: Draw u ∼ U ([0, 1]) common to both players 3: Algorithm: For i = 1 to +∞: For j = 1 to Ti : j pji ← min{1, T1i e Si } Pj kij ← ⌊ l=1 pli + u⌋ If kij > kij−1 : Play one iteration of Ai Otherwise: Play one iteration of Ai−1 4: Output: Learning sequence of policies with L2 lastiterate convergence
j of subloop i as the new instance gets played more and obtains better guarantees. This meta-procedure is summarized in Algorithm 3. As in Algorithm 1, the two players need to be synchronized in their choice between the old and the new instances, hence the same seed is sampled for both at the initialization. The following theorem gives the rate of this meta-procedure. Theorem 8.1. Using Algorithm 3 with, for each Ai , the algorithms and parameterization of Theorem 7.2, along with Ti = 32(i2i ) and Si = 8(2i ), we obtain the bound 1/4 p A+B t t ∥EG(µ , ν )∥2 ≤ 30 log(AB) log(t) t for any total number of iterations t = T1 + ... + Ti−1 + j. The proof is given in Appendix C, and relies on a careful choice of the probabilities pji at each loop i to compensate for the imperfect anytime guarantees of Algorithm 2. More precisely, this probability pji must be inversely proportional to the squared exploitability gap of the new iterates. This squared exploitability gap is roughly given by the KullbackLeibler divergence between the iterates and the new regularized solution, whose inverse is proportional to the number of iterations from Lemma 7.1. This justifies an exponential increase up to 1, after which the procedure can be safely restarted.
This article opens the following research directions: Extensive-form games: These results could be extended to the more general setting of extensive-form games (Kuhn, 1953), in which the players take multiple successive actions without complete knowledge of the current game state. The two approaches proposed in this article could be adapted in a relatively straight-forward way (using IXOMD (Kozuno et al., 2021) as algorithm A for the first, and the dilated Shannon entropy (Kroer et al., 2015) as the regularizer for the second) and obtain the same rate with respect to the horizon T . However, an interesting question arises: what is the optimal dependence on the total size of the action sets? This becomes particularly important in the context of extensive-form games where the number of actions 2 is very large.
Synchronisation Algorithm 3 therefore reaches the optie −1/4 ) for the L2 last-iterate convergence, up mal rate O(T to logarithmic and constant factors. However, it shares some of the weaknesses of Algorithm 1, as it still requires the two players to synchronize their choices of either instance Ai or Ai−1 , with the latter being only played for the anytime guarantees.
More natural methods: Is it possible to obtain anytime lastiterate guarantees without relying on some synchronicity between the two players?
9. Conclusion We studied the convergence of uncoupled algorithms for learning zero-sum games with bandit feedback. We showed that imposing anytime last-iterate convergence worsens the rate compared to just requiring convergence of the average policies, with a lower bound of Ω(T −1/(2+p) ) for the Lp F norm of the exploitability gap given p ∈ (0, 2], in contrast of the usual rate O(T −1/2 ).
Stronger convergence: Is the Ω(T −1/4 ) lower bound tight for the uncoupled Lp convergence given p > 2, and for the uncoupled convergence with high probability? We especially wonder if these last two questions could be solved using a modified version of the optimistic mirror descent algorithm, for example by tweaking the estimated losses or the learning rates.
We then proposed two algorithms that match this rate. The first relies on some synchronization of the two players to balance between efficient exploration of the game and exploitation of a near-optimal policy. A second algorithm relies instead on a regularization of the game and also matches the rate for the L2 norm. However, the latter does not have the required anytime guarantees. A doubling trick effectively solves this issue, using a synchronization similar to the first algorithm.
Impact statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be 2
8
The number of state-action pairs to be precise.
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
specifically highlighted here.
Press, Cambridge, 2006. ISBN 978-0-52184108-5. doi: 10.1017/CBO9780511546921. URL https://www.cambridge.org/core/ books/prediction-learning-and-games/ A05C9F6ABC752FAB8954C885D0065C8F.
References Abe, K., Ariu, K., Sakamoto, M., Toyoshima, K., and Iwasaki, A. Last-iterate convergence with full and noisy feedback in two-player zero-sum games, 2023.
Chiang, C.-K., Yang, T., Lee, C.-J., Mahdavi, M., Lu, C.-J., Jin, R., and Zhu, S. Online Optimization with Gradual Variations. In Proceedings of the 25th Annual Conference on Learning Theory, pp. 6.1–6.20. JMLR Workshop and Conference Proceedings, June 2012. URL https://proceedings.mlr.press/v23/ chiang12.html. ISSN: 1938-7228.
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal on Computing, 32(1):48–77, January 2002. ISSN 0097-5397. doi: 10.1137/ S0097539701398375. URL https://epubs.siam. org/doi/10.1137/S0097539701398375. Publisher: Society for Industrial and Applied Mathematics.
Dong, J., Wang, B., and Yu, Y. Uncoupled and convergent learning in monotone games under bandit feedback. arXiv preprint arXiv:2408.08395, 2024.
Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P. The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities, 2021.
Drusvyatskiy, D., Fazel, M., and Ratliff, L. J. Improved Rates for Derivative Free Gradient Play in Strongly Monotone Games. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3403–3408, December 2022. doi: 10.1109/CDC51059.2022.9992950. URL https:// ieeexplore.ieee.org/document/9992950. ISSN: 2576-2370.
Ba, W., Lin, T., Zhang, J., and Zhou, Z. Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback. Operations Research, January 2025. ISSN 0030-364X. doi: 10.1287/opre.2021. 0445. URL https://pubsonline.informs.org/ doi/abs/10.1287/opre.2021.0445. Publisher: INFORMS.
Facchinei, F. and Pang, J.-S. (eds.). Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer, New York, NY, 2004. ISBN 9780-387-95580-3. doi: 10.1007/b97543. URL http:// link.springer.com/10.1007/b97543.
Banach, S. Théorie des opérations linéaires. 1932. URL https://eudml.org/doc/271931. Bravo, M., Leslie, D., and Mertikopoulos, P. Bandit Learning in Concave N-Person Games. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https:// papers.nips.cc/paper_files/paper/2018/hash/ 47fd3c87f42f55d4b233417d49c34783-Abstract. html.
Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-play in extensive-form games. In International conference on machine learning, 2015. Hiriart-Urruty, J.-B. and Lemaréchal, C. Fundamentals of Convex Analysis, pp. 163–208. 01 2001. ISBN 978-3540-42205-1. doi: 10.1007/978-3-642-56468-0 5.
Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. On the Convergence of Single-Call Stochastic ExtraGradient Methods. In Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019. URL https://inria.hal.science/hal-02403555.
Cai, Y., Farina, G., Grand-Clément, J., Kroer, C., Lee, C.-W., Luo, H., and Zheng, W. Fast LastIterate Convergence of Learning in Games Requires Forgetful Algorithms. November 2024. URL https://openreview.net/forum?id= hK7XTpCtBi&referrer=%5Bthe%20profile%20of% 20Gabriele%20Farina%5D(%2Fprofile%3Fid% 3D˜Gabriele_Farina1).
Huang, Y. and Hu, J. Zeroth-Order Learning in Continuous Games Via Residual Pseudogradient Estimates. IEEE Transactions on Automatic Control, pp. 1–16, 2024. ISSN 1558-2523. doi: 10.1109/TAC.2024. 3479874. URL https://ieeexplore.ieee.org/ document/10715648?denied=. Conference Name: IEEE Transactions on Automatic Control.
Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University
Juditsky, A. B., Nemirovski, A. S., and Tauvel, C. Solving variational inequalities with Stochastic Mirror-Prox 9
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
algorithm. Stochastic Systems, 1(1):17, 2011. doi: 10.1214/10-SSY011. URL https://hal.science/ hal-00318043. Kangarshahi, E. A., Hsieh, Y.-P., Sahin, M. F., and Cevher, V. Let’s be Honest: An Optimal No-Regret Framework for Zero-Sum Games. In Proceedings of the 35th International Conference on Machine Learning, pp. 2488–2496. PMLR, July 2018. URL https://proceedings.mlr. press/v80/kangarshahi18a.html. ISSN: 26403498. Kocák, T., Neu, G., Valko, M., and Munos, R. Efficient learning by implicit exploration in bandit problems with side observations. In Advances in Neural Information Processing Systems 27, 2014.
McAleer, S., Farina, G., Lanctot, M., and Sandholm, T. ESCHER: Eschewing importance sampling in games by computing a history value function to estimate regret. CoRR, abs/2206.04122, 2022. doi: 10.48550/arXiv.2206. 04122. URL https://doi.org/10.48550/arXiv. 2206.04122. Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T., Michi, A., Selvi, M., Girgin, S., Momchev, N., Bachem, O., Mankowitz, D. J., Precup, D., and Piot, B. Nash learning from human feedback, 2023. Muthukumar, V., Phade, S., and Sahai, A. On the Impossibility of Convergence of Mixed Strategies with Optimal No-Regret Learning. Mathematics of Operations Research, November 2020. ISSN 0364-765X. doi: 10.1287/moor.2022.0016. URL https://pubsonline. informs.org/doi/10.1287/moor.2022.0016. Publisher: INFORMS.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. 1976. Kozuno, T., Ménard, P., Munos, R., and Valko, M. Modelfree learning for two-player zero-sum partially observable Markov games with perfect recall. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, pp. 11987–11998, Red Hook, NY, USA, December 2021. Curran Associates Inc. ISBN 978-1-71384-539-3.
Nash Jr, J. F. Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48–49, 1950. 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–251, 2004.
Kroer, C., Waugh, K., Kilinç-Karzan, F., and Sandholm, T. Faster First-Order Methods for Extensive-Form Game Solving. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, pp. 817– 834, New York, NY, USA, June 2015. Association for Computing Machinery. ISBN 978-1-4503-3410-5. doi: 10.1145/2764468.2764476. URL https://doi.org/ 10.1145/2764468.2764476.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust Stochastic Approximation Approach to Stochastic Programming. SIAM Journal on Optimization, 19 (4):1574–1609, January 2009. ISSN 1052-6234. doi: 10.1137/070704277. URL https://epubs.siam.org/ doi/10.1137/070704277. Publisher: Society for Industrial and Applied Mathematics.
Kuhn, H. W. Extensive Games and the Problem of Information. Annals of Mathematics Studies, 28:193–216, 1953.
Nemirovskiı̆, A. S. and IUdin, D. B. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983. ISBN 978-0-471-10345-5. Google-Books-ID: 6ULvAAAAMAAJ.
Mancino, O. G. and Stampacchia, G. Convex programming and variational inequalities. Journal of Optimization Theory and Applications, 9(1):3–23, January 1972. ISSN 1573-2878. doi: 10.1007/BF00932801. URL https://doi.org/10.1007/BF00932801. Martinet, B. Brève communication. Régularisation d’inéquations variationnelles par approximations successives. Revue française d’informatique et de recherche opérationnelle. Série rouge, 4(R3): 154–158, 1970. ISSN 0373-8000, 2777-3515. doi: 10.1051/m2an/197004R301541. URL https://www. esaim-m2an.org/articles/m2an/abs/1970/03/ m2an197004R301541/m2an197004R301541.html. Number: R3 Publisher: EDP Sciences. 10
Neu, G. Explore no more: improved high-probability regret bounds for non-stochastic bandits. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2, volume 2 of NIPS’15, pp. 3168–3176, Cambridge, MA, USA, December 2015. MIT Press. Pinsker, M. Information and information stability of random variables and processes. 1964. Popov, L. D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845– 848, November 1980. ISSN 1573-8876. doi: 10.
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
1007/BF01141092. URL https://doi.org/10.1007/ BF01141092. Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, volume 2 of NIPS’13, pp. 3066–3074, Red Hook, NY, USA, December 2013. Curran Associates Inc. Rudin, W. Real and Complex Analysis. Tata McGrawHill, 2006. ISBN 978-0-07-061987-6. Google-Books-ID: 3d8umJoRd08C. Tatarenko, T. and Kamgarpour, M. On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games, February 2022. URL http: //arxiv.org/abs/2202.11147. arXiv:2202.11147 [math]. Tseng, P. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1):237–252, 1995. ISSN 0377-0427. doi: https://doi.org/10.1016/0377-0427(94) 00094-H. Proceedings of the International Meeting on Linear/Nonlinear Iterative Methods and Verification of Solution. Tyrrell, R. R. Monotone Operators and the Proximal Point Algorithm | SIAM Journal on Control and Optimization, 1976. URL https://epubs.siam.org/doi/10. 1137/0314056. v. Neumann, J. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1):295–320, December 1928. ISSN 1432-1807. doi: 10.1007/BF01448847. URL https://doi.org/10.1007/BF01448847. 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: //proceedings.mlr.press/v134/wei21a.html.
11
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
A. Lower bound Theorem 5.1. Assume that the sampled action bt ∼ ν t of the max-player at each iteration t is never observed. Then, for any p ∈ (0, 2], no learning sequence can achieve simultaneously for all 2 × 2 matrix games described above an Lp last iterate convergence of −1
ft =
−1 4 p 2+p t , 118
even asymptotically. Proof. We will use the games mentioned in the main body, defined with: 2/3 − ε 1/3 + ε ε M = with ε ∈ [−1/12, 1/12]. 1/3 2/3 where the entries of the matrix indicate the parameters of some i.i.d Bernoulli for the actual game. We will assume that the learning sequence satisfies an asymptotic Lp last iterate convergence with f of the form −1
f t = Cp t 2+p
with Cp ∈ (0, 1] ,
and show that this is impossible for all games given Cp low enough. Notations Let z t denote the knowledge of both players up to round t included with z t := ω, a1 , ℓ1 , ..., at , ℓt , such that the sequences (µt ) and (ν t ) of policies are predictable with respect to the filtration (σ(z t ))t∈N rather than F from the assumption. We will consider the games M 0 , M εT and M −εT with a fixed choice of εT that we will specify later. Let P0 , PT and P−T respectively be the probabilities associated to playing these games, with ∥·∥0, p , ∥·∥T, p and ∥·∥−T, p the associated p (pseudo)-norms. For any random variable X and θ ∈ Z, we will denote by PX θ the probability distribution on X given Pθ . T −T Now, T , let E and E respectively be the two events E T := µT (1) ≤ 1/2 and E −T := T given an horizon µ (1) ≥ 1/2 . E T denotes a suboptimal choice for the game M εT , and E −T a suboptimal choice for the game M −εT as we will show in the next section. Under P0 , one of these two events happens with a probability of at least 1/2, we will denote it with θT ∈ {−T, T } 1/2 + δ t For clarity, we will take the strategy of the max-player ν t to be in the form with δ t ∈ [−1/2, 1/2].. 1/2 − δ t Link between the policies and exploitability gaps The exploitability gap will be lower bounded twice in this section: for T T the max-player under the game M 0 and for the min-player under the games M ε and M −ε . We will use the fact that the value of all of these games is 1/2. Given a max-player policy ν t , we have M 0 .ν t =
1/2 + δ t /3 1/2 − δ t /3
which implies (for M 0 ), EG(µt , ν t ) ≥ 1/2 − minµ µ, M 0 .ν t = δ t /3 T µ (1) T On the other hand, given a min-player policy µ = and any ε ∈ [−1/12, 1/12], 1 − µT (1) T
(M ε ) .µT =
1/3 + 1/3µT (1) − εµT (1) . 2/3 − 1/3µT (1) + εµT (1)
(with the M T notation for the transpose). Then, using the vectors e1 = 12
1 0 and e2 = , 0 1
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
E D T e2 , (M εT ) .µT ≥ 1/2 + εT /2, With M εT under event E T = µT (1) ≤ 1/2 : E D T hence: EG(µt , ν t ) ≥ max ν, (M εT ) .µT − 1/2 ≥ εT /2 ν
E D T e1 , M −εT .µT ≥ 1/2 + εT /2, With M −εT under event E −T = µT (1) ≥ 1/2 : E D T hence: EG(µt , ν t ) ≥ max ν, M −εT .µT − 1/2 ≥ εT /2 ν
In both cases, the exploitability gap is at least εt /2. Asymptotic KL divergence From the definition of the sequence (z t ) and the additive properties of the KL divergence, we obtain the following inequalities DKL
T T Pz0 , PzθT
= DKL
0 0 Pz0 , PzθT
+ E0
" T X
DKL
z t |z t−1 z t |z t−1 P0 , PθT
#
t=1 ω = DKL (Pω 0 , Pθ T ) + E0
" T X
DKL
at |z t−1 at |z t−1 P0 , PθT
# + E0
t=1
= E0
" T X
" T X
DKL
ℓt |z t−1 ℓt |z t−1 P0 , PθT
#
t=1
# t
t
t
t
T
µ (1)DKL 1/2 + δ /3, 1/2 + δ /3 − 2δ sign(θ )εT
t=1
≤ 24ε2T E0
" T X
# δ
t 2
t=1
≤ 24ε2T E0
" T X
# δ
t p
t=1
≤ 24ε2T E0
" T X
# p 3EG(µt , ν t )
t=1
≤ 216ε2T
T X
p
∥EG(µt , ν t )∥0,p
t=1
where we especially used the reversed Pinsker inequality with 1/6 ≤ 1/2 + δ t /3 − 2δ t sign(θT )εT ≤ 5/6, and the previous lower bound of the exploitability gap under P0 . For the third equality: ω • DKL Pω 0 , Pθ T is 0 as the internal randomness do not depend on the model. t t−1 a |z at |z t−1 • DKL P0 , PθT is also 0, for all t, as the choice of the action (conditionally on the previous move) also does not depend on the model. t t−1 t t−1 ℓ |z ℓ |z • From the computations above, DKL P0 , PθT corresponds to the KL divergence between a Bernoulli B(1/2 + δ t /3) and a Bernoulli B(1/2 + δ t /3 − 2δ t sign(θT )εT ) if the first move is played by the first player, 0 otherwise. Now assume that the restriction holds for all t > T0 , then for any T > T0 13
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
DKL
T T Pz0 , PzθT
≤ 216ε2T
T0 +
!
T X
f
t p
t=T0 +1
≤ 216ε2T
T0 +
T X
t
−p 2+p
!
t=1
≤ 216ε2T
!
Z T t
T0 +
2 2+p −1
dt
0
2 2 + p 2+p T T0 + 2 2 ≤ 216ε2T T0 + 2 T 2+p . = 216ε2T
Which implies the asymptotic bound: T −2 T lim sup DKL Pz0 , PzθT T 2+p ≤ 432ε2T . T→ − +∞ Probability of a suboptimal choice
Defining ∥·∥T V the total variation between two probabilities P and Q: ∥P − Q∥T V = sup |P(E) − Q(E)| E event
and using the measurability of E we get
θT
with respect to σ z
T
T
, the fact that P0 (E θ ) ≥ 1/2 by definition and Pinsker inequality,
h i T T T T lim inf PθT (E θ ) ≥ lim inf P0 (E θ ) − Pz0 − PzθT T→ − +∞ T→ − +∞ TV r 1 1 T T ≥ − lim sup DKL Pz0 , PzθT 2 T→ − +∞ 2 √ 1 1 ≥ − 6 6 lim sup εT T 2+p 2 T→ − +∞ . This implies that fixing εT = 241√6 T Final bound
−1 2+p
forces the probability of this suboptimal choice to be at least 14 asymptotically. T
Combining the previous choice of εT with the suboptimality of µT under E θ ,
T h i p1 T 1 1 p T 2+p lim inf ∥EG(µT , ν T )∥θT , p T 2+p ≥ lim inf PθT E θ EθT EG(µT , ν T ) E θ T→ − +∞ T→ − +∞ T p1 ε 1 T ≥ lim inf PθT E θ T 2+p T→ − +∞ 2 T p1 1 = √ lim inf PθT E θ − +∞ 48 6 T → −1
4p ≥ √ . 48 6 1 As 481√6 > 118 , this implies that the guarantees cannot be attained asymptotically for all games assuming f is defined with −1
−1 4 p 2+p f = t . 118
t
14
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
B. Proofs for the Simultaneous Explore or Exploit approach Lemma B.1. Let (pt ) ∈ [0, 1]N . The sequence of Bernoulli random variables (B t )t∈N defined by B t = ⌊st + u⌋ − ⌊st−1 + u⌋
st =
where
t X
pi
and
u ∼ U([0, 1])
i=1
satisfies: ∀t ∈ N,
E[B t ] = pt
and
t X
B i ≥ st .
i=1
Proof. Let x, y ∈ R such that 0 ≤ y − x ≤ 1. Let {·} denote the fractional part. We distinguish two cases with the same result: • If {x} ≤ {y} (and consequently ⌊x⌋ = ⌊y⌋), then P (⌊x + u⌋ + 1 = ⌊y + u⌋) = P (u ∈ [1 − {y}, 1 − {x})) = {y} − {x} = y − x • If {x} > {y} (which necessarily implies ⌊x⌋ = ⌊y⌋ − 1), P (⌊x + u⌋ + 1 = ⌊y + u⌋) = P (u ∈ [0, 1 − {x}) ∪ [1 − {y}, 1]) = 1 − {x} + {y} = y − x . Using, for each t ∈ N, x = st−1 and y = st yields the first equality. The inequality is obtained by telescoping the term: T X
B i = sT + u − ⌊u⌋ ≥ sT
i=1
. Lemma B.2. Assume that A satisfies an output convergence of rate g. Then Algorithm 1 satisfies an Lp last iterate convergence of rate f defined by h 1 i t 1 f t = 2 p pt p + g r jP k t k where rt = p . k=1 Proof. Using the previous lemma where B t is the action of exploring, we obtain as g is non-increasing, 1 ∥EG(µt , ν t )∥p = E EG(µt , ν t )p p h i p1 t t = pt E EG(µt , ν t ) + (1 − pt )E EG(µ̂k , ν̂ k t p p1 t ≤ p + gr h i t 1 p ≤ 2 p pt + g r Pt where we used the notation k t = ⌊ k=1 pk + u⌋ and the inequalities, for all x, y ∈ R>0 : (x + y)q ≤ 2q−1 (xq + y q ) (x + y)q ≤ (xq + y q )
for q ≥ 1
for q < 1
from the convexity of xq
as y 7→ (x + y)q − xq − y q is decreasing on R>0 .
15
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
q A Theorem B.3. (Neu, 2015) Given A arms and δ ∈ (0, 1), setting η t = 2γ t = log At for all t, the bound of EXP3-IX is s ! p AT T R ≤ 4 AT log(A) + 2 + 1 log(2/δ) log A with probability 1 − δ t t Applying this theorem to both Rmin and Rmax with δ ′ = δ/2 gives the bound, with probability at least 1 − δ: s s ! ! p p At Bt t t Rmin + Rmax ≤ 4 At log(A) + 2 + 1 log(4/δ) + 4 Bt log(B) + 2 + 1 log(4/δ) log A log B √ p √ ≤ 8 (A + B)t log(A + B) + 2 At + 2 Bt log(4/δ) p ≤ 8 (A + B)t log(4(A + B)/δ)
where we used very loose upper bounds for simplicity. Theorem 6.2. Using Algorithm 1 with probabilities pt = t−p/(2+p) , and p pas A, the algorithm EXP3-IX with parameters t t t t ηmin = 2γmin = log(A)/ (At) for the min-player and ηmax = 2γmax = log(B)/ (Bt) for the max-player, we obtain an Lp last-iterate convergence rate of √ 1 1 f t = 17 A + B 2 p t− 2+p log 4(A + B)t2 /p . Proof. Lp bound We first show that the average policy played by EXP3-IX converges for the Lp norm. Let p ∈ (0, 2] and t ∈ N, we consider δ = p/tp in the above inequality. Then, as the sum of the two regrets is bounded by T , 1 ∥EG(µ̂t , ν̂ t )∥p = E EG(µ̂t , ν̂ t )p p p p1 1 t t ≤ Rmin + Rmax t p i p1 p 1h p ≤ δt + (1 − δ) 8 (A + B)t log(4(A + B)/δ) t p i p1 p 1h ≤ . p + 8 (A + B)t log(4(A + B)t2 /p) t As for all x ≥ 1, from the concavity of the log function, 1
p
1
1
p
(p + xp ) p = e p log(p+x ) ≤ e p log(x )+1 = ex , we obtain
r t
t
∥EG(µ̂ , ν̂ )∥p ≤ 6
A+B log 4(A + B)t2 /p t
p
Lemma application We apply Lemma 6.1 with pt = t− 2+p . As in this case, Z t+1 2 t p 2 2+p − 2+p 2+p r ≥ u du ≥ (t + 1) − 1 ≥ 2 t 2+p − 2 . p 1 We obtain (loosely) a rate h i t 1 1 f t = 2 p (pt ) p + g r h i √ √ 1 1 1 ≤ 2 p t− 2+p + 11 2 A + B log 4(A + B)t2 /p t− 2+p √ 1 1 ≤ 2 p 17 A + B log 4(A + B)t2 /p t− 2+p .
16
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
C. Proofs for the Regularized EXP3 algorithm Notations: In this section, the computations will be done directly in the space W = ∆A × ∆B using w = (µ, ν) and the operators, for τ > 0, F (w) = (L(·, ν), 1 − L(µ, ·)) F̂ t = (ℓ̂tmin , ℓ̂tmax ) h(w) =
A X
µ(a) (log(µ(a)) − 1) +
a=1
B X
ν(b) (log(ν(b)) − 1)
b=1
F τ (w) = (L(·, ν), 1 − L(µ, ·)) + τ ∇h(w) − ∇h(w0 ) D(w, w′ ) = DKL (µ, µ′ ) + DKL (ν, ν ′ ) . With these notations, we have the following properties: • F is a monotone operator over W , and the solutions w⋆ ∈ W of the variational inequalities ∀w ∈ W, ⟨F (w⋆ ), w⋆ − w⟩ ≤ 0 are the Nash equilibrium of the game associated to L. • F τ is a strongly monotone operator. It has only one solution wτ,⋆ , for which the above inequality is always an equality and satisfies for all w, w′ ∈ W : ⟨F τ (w) − F τ (w′ ), w − w′ ⟩ = τ (D(w, w′ ) + D(w′ , w)) • E(F̂ t |F t−1 ) = F (wt ) • D is the Bregman divergence associated to h, and especially satisfies the law of cosines, for all x, y, z ∈ W : D(x, z) = D(x, y) + D(y, z) + ⟨∇h(z) − ∇h(y), y − x⟩ Before proving the lemma, we can notice that the updates of Algorithm 2 can be rewritten in the W space (if τ η t ≤ 1): wt = arg min(1 − η t τ )D(w, wτ,t ) + η t τ D(w, w0 ) w∈W D E wτ,t+1 = arg min η t F̂ t , w + D(w, wt ) w∈W
which are equivalent to the updates, taking the gradient of the above expressions, ∇h(wt ) ≡ (1 − τ η t )∇h(wτ,t ) + τ η t ∇h(w0 ) ∇h(wτ,t+1 ) ≡ ∇h(wt ) − η t F̂ t where we used the notations x ≡ y ⇐⇒ ∀w ∈ W, ⟨x − y, w⟩ = 0 Lemma C.1. Let τ ∈ (0, 1]. Taking η t = 2/ (τ (t + 1)) along with µτ,1 = µ0 and ν τ,1 = ν 0 the uniform policies gives with the above updates 2(A + B) E DKL (µτ,⋆ , µτ,t ) + DKL (ν τ,⋆ , ν τ,t ) ≤ τ2 t for all t ∈ N. 17
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. Updates: From the law of cosines applied to the two updates, we have: (1)
(1 − η t τ )D(wτ,⋆ , wτ,t ) = (1 − η t τ )D(wτ,⋆ , wt ) + (1 − η t τ )D(wt , wτ,t ) + (1 − η t τ ) ∇h(wτ,t ) − ∇h(wt ), wt − wτ,⋆ ≥ (1 − η t τ )D(wτ,⋆ , wt ) + η t τ ∇h(wt ) − ∇h(w0 ), wt − wτ,⋆
and (2)
D(wτ,⋆ , wτ,t+1 ) = D(wτ,⋆ , wt ) + D(wt , wτ,t+1 ) + ∇h(wτ,t+1 ) − ∇h(wt ), wt − wτ,⋆ D E = D(wτ,⋆ , wt ) + D(wt , wτ,t+1 ) − η t F̂ t , wt − wτ,⋆ .
(2) − (1) yields when conditioned on F t−1 : E D(wτ,⋆ , wτ,t+1 )|F t−1 ≤ (1 − η t τ )D(wτ,⋆ , wτ,t ) + E D(wt , wτ,t+1 )|F t−1 + η t τ D(wτ,⋆ , wt ) − η t wt − wτ,⋆ , F τ (wt ) = (1 − η t τ )D(wτ,⋆ , wτ,t ) + E D(wt , wτ,t+1 )|F t−1 + η t τ D(wτ,⋆ , wt ) − η t wt − wτ,⋆ , F τ (wt ) − F τ (wτ,⋆ ) = (1 − η t τ )D(wτ,⋆ , wτ,t ) + E D(wt , wτ,t+1 )|F t−1 − η t τ D(wt , wτ,⋆ ) ≤ (1 − η t τ )D(wτ,⋆ , wτ,t ) + E D(wt , wτ,t+1 )|F t−1 , Second order bound: We now want to show 2 A + B E D(wt , wτ,t+1 )|F t−1 ≤ η t . 2 We start by showing 2 A E DKL (µt , µτ,t+1 )|F t−1 ≤ η t 2 and the rest will follow by symmetry. This inequality is classic in the bandit literature, but we provide a quick proof below for completeness. If we define µ̃τ,t+1 as the unprojected update defined by: ∇hA (µ̃τ,t+1 ) = ∇hA (µt ) − η t ℓ̂tmin we know, because of the generalized Pythagorean theorem (Hiriart-Urruty & Lemaréchal, 2001), that E DKL (µt , µτ,t+1 )|F t−1 ≤ E DKL (µt , µ̃τ,t+1 )|F t−1 . Then, using the convex conjugate h⋆ (Hiriart-Urruty & Lemaréchal, 2001), the following holds, using classical properties of the Bregman divergence: E DKL (µt , µ̃τ,t+1 )|F t−1 = E Dh⋆A (∇hA (µ̃τ,t+1 ), ∇hA (µt ))|F t−1 h i = E Dh⋆A (∇hA (µt ) − η t ℓ̂tmin , ∇hA (µt ))|F t−1 2
E i (η t ) hD 2 ⋆ E ∇ hA (∇h(µt )).ℓ̂tmin , ℓ̂tmin |F t−1 2 2 A (η t ) X t ℓt (a)2 = µ (a) t 2 µt (a) 2 a=1 µ (a)
≤
≤ ηt
2 A 2 18
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
where we used Taylor inequality along with the fact that the hessian ∇2 h⋆A (∇hA (µ)) = ∇2 hA (µ)−1 = Diag(µ(a))a=1,...,A is increasing on all components with respect to µ, which implies the negativity of the third-order term. Indeed, each component of the unprojected policy decreases along the update. Recursion We then have the recursive property, taking the global expectation: A+B E D(wτ,⋆ , wτ,t+1 ) ≤ (1 − η t τ )E D(wτ,⋆ , wτ,t ) + (η t )2 . 2 2 With η t = τ (t+1) , this is everything we need for the desired property
A+B E D(wτ,⋆ , wτ,t ) ≤ 2 2 . τ t Indeed, for t = 1, the property immediately follows from, as wτ,1 is the uniform profile, D(wτ,⋆ , wτ,1 ) = h(wτ,⋆ ) ≤ log(A) + log(B) ≤
A+B τ2
and τ ≤ 1 by assumption. Then, assuming the property holds for t, we notice that for t + 1 2 A+B A+B E D(wτ,⋆ , wt+1 ) ≤ 2 1 − +2 2 2 t+1 τ .t τ (t + 1)2 2 1 A+B 1 − + =2 τ2 t t(t + 1) (t + 1)2 A+B 1 1 ≤2 − τ2 t t(t + 1) A+B . =2 2 τ (t + 1)
Lemma C.2. For a zero-sum game with rewards in (0, 1), the exploitability gap is 1-Lipchitz with respect to the 1-norm. Proof. Let w = (µ, ν) and w′ = (µ′ , ν ′ ) be two profiles in ∆A × ∆B , then |EG(w) − EG(w′ )| = sup L(µ† , ν) − sup L(µ† , ν ′ ) − sup L(µ, ν † ) + sup L(µ′ , ν † ) µ†
µ†
ν†
ν†
≤ sup L(µ† , ν) − sup L(µ† , ν ′ ) + sup L(µ, ν † ) − sup L(µ′ , ν † ) µ†
µ† ′
ν†
ν†
′
≤ ∥ν − ν ∥1 + ∥µ − µ ∥1 ≤ ∥w − w′ ∥1 following the fact that, for any (µ† , ν † ), ν 7→ L(µ† , ν) and µ 7→ L(µ, ν † ) are both 1-Lipschitz as the coefficients of the matrix are in [0, 1]. p 1/4 Theorem 7.2. Let T be a fixed horizon. Then, using regularization τ = ((A + B) /T ) 2/ (log(A) + log(B)) and the learning rates η t = 2/(τ (t + 1)) for all t, Algorithm 2 guarantees √ ∥EG(µT , ν T )∥2 ≤ 3 2
A+B T
19
1/4
p
log(AB) .
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. We can safely assume T ≥ A + B ≥ 4 as the bound is immediate otherwise. We first notice, at iteration T : • From the optimality of wτ,⋆ up to the regularization, EG(wτ,⋆ ) ≤ τ DKL (wτ,⋆ , w0 ) ≤ τ (log(A) + log(B)) . • From Pinsker inequality and Lemma 7.1, 2
∥wτ,T − wτ,⋆ ∥1 ≤ 2DKL (wτ,⋆ , wτ,T ) ≤
4(A + B) . τ2 T
• By definition of wT as an arg min, (1 − η T τ )DKL (wT , wτ,T ) + τ η T DKL (wT , w0 ) ≤ η T τ DKL (wτ,T , w0 ). Hence, re-using Pinsker inequality, 2
∥wT −wτ,T ∥1 ≤ 2DKL (wT , wτ,T ) ≤ 2
ηT τ 8 DKL (wτ,t , w0 ) ≤ 4η T τ (log(A) + log(B)) = (log(A) + log(B)) 1 − ηT τ T +1
where we used η T = τ (T2+1) , and in particular η T τ ≤ 12 as T ≥ 3 by assumption. With all these inequalities together, along with Lemma C.2 for the 1-Lipschitzness of the exploitability gap, h 2 i E EG(wT )2 ≤ E EG(wτ,⋆ ) + ∥wT − wτ,⋆ ∥1 h 2 i ≤ E EG(wτ,⋆ ) + ∥wτ,T − wτ,⋆ ∥1 + ∥wT − wτ,T ∥1 h i 2 2 ≤ 3 E EG(wτ,⋆ )2 + ∥wτ,T − wτ,⋆ ∥1 + ∥wT − wτ,T ∥1 4(A + B) 8 2 ≤ 3 τ 2 (log(A) + log(B)) + + (log(A) + log(B)) . τ2 T T +1
2 In particular, with τ 2 = log(A)+log(B)
q
A+B T , we obtain,
! r A+B 8 T 2 E EG(w ) ≤ 3 4 + (log(A) + log(B)) T T hence, as T ≥ 4 and A + B ≥ 4, r A+B T 2 E EG(w ) ≤ 18 (log(A) + log(B)) T and by taking the square root, √ ∥EG(wT )∥2 ≤ 3 2
A+B T
1/4
p
log(A) + log(B) .
Theorem 8.1. Using Algorithm 3 with, for each Ai , the algorithms and parameterization of Theorem 7.2, along with Ti = 32(i2i ) and Si = 8(2i ), we obtain the bound 1/4 p A+B t t ∥EG(µ , ν )∥2 ≤ 30 log(AB) log(t) t for any total number of iterations t = T1 + ... + Ti−1 + j. 20
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. Let EG(i, s) be the exploitability gap of sub-algorithm Mi after s iterations. With the notations √ CA,B = 18 A + B (log(A) + log(B)) , q 2 A+B we have from the proof of Theorem 7.2, taking T = s and τ 2 = log(A)+log(B) Ti , √ E EG(i, s)2 ≤ CA,B
Ti s
assuming s ≤ Ti . Pj We will also use the notation, for any j ≤ Ti , sji = l=1 plk , the expected sum of calls of sub-algorithm Mi during the loop i. Note that, because of the sampling method, the actual number of calls s will be at least sji − 1. We notice, for any 12 Si log(Ti ) ≤ j ≤ Si log(Ti ), j+1
sji =
e Si − 1 1 Ti e Si − 1
and in particular, j+1
e Si − 1 −1 1 Ti e Si − 1 4Si j+1 ≥ e Si − 2 5Ti 4(1 − 2e−2 ) Si j+1 ≥ e Si 5 Ti Si j+1 ≥ e Si (∗) 2Ti
sji − 1 =
j+1
1
where we used e Si ≤ 1 + S1i + S12 ≤ 1 + 4S5 i , e Si ≥ e
log(Ti ) 2
≥ e2 .
i
Now, for any j ≤ Ti and t = T1 + ... + Ti−1 + j. We have E EG(µt , ν t )2 = pji E EG(i, s)2 + (1 − pji ) E EG(i − 1, s′ )2 | {z } | {z } α(i,j)
β(i,j)
T
i−1 where s ≥ suk − 1 and s′ ≥ si−1 − 1.
First term
(α(i, j)):
• Either j ≤ S2i log(Tk ), then α(i, j) ≤ pji ≤ √1T using EG(i, s) ≤ 1 i
•
Either 12 Si log(Ti ) < j ≤ Si log(Tj ), in this case, using (∗) we obtain s ≥ sji − 1 ≥ This yields
Si j+1 Si e Si ≥ pji 2Ti 2
√ α(i, j) ≤ 2CA,B
Ti 1 = 8iCA,B √ . Si Ti
• Either Si log(Ti ) < j, in this case, using (∗) again with ⌊Si log(Ti )⌋ instead of j, we obtain: s ≥ sji − 1 ≥ sji − 1 ≥ 21
Si Si j+1 e Si ≥ 2Ti 2
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
which again yields:
√ α(i, j) ≤ 2CA,B
Ti 1 = 8iCA,B √ . Si Ti
as pji ≤ 1. Second term
(β(i, j))
For the second term, which depends on the total number of call of algorithm Mi−1 , we will lower-bound this number using only the calls during the loop i − 1. As Ti−1 ≥ ⌊Si−1 log(Ti−1 )⌋, we have, using inequality (∗) on the loop i − 1, with the previous quantity, as above, Si−1 Ti−1 s′ ≥ si−1 − 1 ≥ svi−1 − 1 ≥ 2 and we obtain: p Ti−1 1 β(i, j) ≤ 2CA,B = 8(i − 1)CA,B p . Si−1 Ti−1 Final bound • Ti ≥
: To conclude, we will also need the simple inequalities:
Pi−1
l=1 Tl (and thus t ≤ 2Ti if t is in loop i).
• 4Ti−1 ≥ Ti • i ≤ log(Ti−1 )/ log(2) Using these, we obtain, for any i, j and t = T1 + ... + Ti−1 + j: E EG(µt , ν t )2 = α(i, j) + β(i, j) 1 1 ≤ 8iCA,B √ + 8(i − 1)CA,B p Ti Ti−1 √ √ 8 log(Ti ) 2 + 2 2 CA,B √ ≤ log(2) t √ 8 √ log(t) ≤ 2 + 2 2 CA,B √ . log(2) t Finally, taking the square root and using the definition of CA,B , s √ A + B 1/4 p 144 √ t t ∥EG(µ , ν )∥2 ≤ 2+2 2 (log(A) + log(B)) log(t) log(2) t 1/4 p A+B (log(A) + log(B)) log(t) . ≤ 30 t
22