arXiv:2604.15242v1 [cs.LG] 16 Apr 2026
Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier Côme Fiegel1 , Pierre Ménard2 , Tadashi Kozuno3 , Michal Valko3 , Vianney Perchet1,4,5 1 ENSAE Paris – CREST, France 2 ENS Lyon, France 3 Isara Labs
4 Criteo AI Lab
5 Inria Fairplay, Paris, France
Abstract We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Ω(𝑡 −1/4 ). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this Õ (𝑡 −1/4 ) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate. Keywords: Game Theory, Bandits, Online Mirror Descent.
1
Introduction
Matrix games model games involving a finite number of players, each taking a single action and subsequently receiving a reward. In the zero-sum case, implicitly two-players, a single reward is considered, which is maximized by one and minimized by the other. In this case, the minimax policies (von Neumann, 1928) model policies that are optimal against the worst opponents. The problem of finding such policy can be studied in the context of sequential learning, in which the two players will repeatedly play the game in order to find this optimal policy. A classical way of obtaining this bound is through the regret. Assuming that the players observe the expected outcome of each action, basic methods then allow a O (𝑡 −1/2 ), improvable to O (𝑡 −1 ) with optimistic methods (Popov, 1980; Rakhlin and Sridharan, 2013). These regret-bounding methods generally only ensure an ergodic convergence: their output is the average of the policies played over time. A significant part of the literature focuses on obtaining a last-iterate convergence instead: a direct convergence of the policies played by each player. Interestingly, this requirement does not deteriorate the guarantee; a problem-independent 1
Optimal last-iterate convergence in matrix games
2
rate of O (𝑡 −1 ) is still achievable (Kangarshahi et al., 2018), as well as a problem-dependent linear rate (Wei et al., 2021). In the bandit setting, the players are only allowed to observe their action and the related outcome at every iteration of the game. In this case, the optimal convergence is of O (𝑡 −1/2 ) with regretbounding methods (Audibert and Bubeck, 2009; Zimmert and Seldin, 2019). Meanwhile, very few articles studied the last-iterate convergence in the bandit case, with Cai et al. (2023) first achieving a O 𝑡 −1/8 rate with high probability and O 𝑡 −1/6 in expectation. More recently, Fiegel et al. (2025) showed that if the two players are uncoupled and are not allowed to communicate their action, then only a O (𝑡 −1/4 ) rate is achievable. It proposed two methods with this rate, but none really obtained the optimal rate in the desired setting: one relied on a coupling of the players, while the other one was not fully last-iterate, in particular with the guarantees only holding close to some chosen horizon 𝑇 . Main contributions: • We propose and analyse Algorithm 1. It relies on a mirror descent approach, along with a varying regularization using the log-barrier. These two ingredients, when combined with a vastly different analysis focusing on the dual, enable the first real Õ (𝑡 −1/4 ) anytime last-iterate convergence in the bandit setting. • We additionally show that this approach can be easily extended to extensive-form games with perfect recall, using a dilation (Kroer et al., 2015) of the same regularizer.
2
Problem formulation
Zero-sum matrix game: Two players, called the min- and the max-player, respectively play actions 𝑎 ∈ A and 𝑏 ∈ B and receive a stochastic loss ℓ (𝑎, 𝑏) ∈ [0, 1]: the min-player wants to minimize this loss, while the max-player wants to maximize it. The two players are allowed to play stochastically: they choose two mixed policies 𝜇 ∈ Δ A := Í Í {𝜇, 𝑎 𝜇 (𝑎) = 1} and 𝜈 ∈ Δ B := {𝜈, 𝑏 𝜈 (𝑏) = 1} and optimize their expected outcome: ℓ (𝜇, 𝜈) = E𝑎∼𝜇,𝑏∼𝜈 [ℓ (𝑎, 𝑏)] . 𝑊 = Δ A × Δ B will denote the set of mixed profiles. We look to obtain a minimax profile, defined as a profile (𝜇★, 𝜈 ★) ∈ 𝑊 that satisfies 𝜇★ ∈ arg min ℓ (𝜇, 𝜈 ★) 𝜇 ∈ΔA
and 𝜈 ★ ∈ arg max ℓ (𝜇★, 𝜈) , 𝜈 ∈ΔB
whose existence is guaranteed (von Neumann, 1928). The proximity of a profile (𝜇, 𝜈) to the set of minimax profiles can be characterized using the exploitability gap: 𝐸𝐺 (𝜇, 𝜈) = − min ℓ (𝜇 ′, 𝜈) + max ℓ (𝜇, 𝜈 ′ ) . ′ ′ 𝜇 ∈ΔA
𝜈 ∈ΔB
In terms of game theory, the exploitability gap is a better measure of proximity to the minimax than any other distance defined solely in terms of probability distributions, say the total variation (which has no strategic interpretation). Indeed, the exploitability gap is zero if and only if (𝜇, 𝜈) is a minimax profile. Sequential learning with bandit feedback: We assume that at each iteration 𝑡, both players select policies 𝜇𝑡 and 𝜈 𝑡 , sample two actions 𝑎𝑡 ∼ 𝜇𝑡 and 𝑏 𝑡 ∼ 𝜈 𝑡 , and observe a loss ℓ 𝑡 ∼ ℓ (𝑎𝑡 , 𝑏 𝑡 ) associated to these two moves. More formally, a filtration F = (F 𝑡 )𝑡 ∈N is defined recursively by the observations, along with some extra randomness 𝜔: F 𝑡 = 𝜎 𝜔, 𝑎 1, 𝑏 1, ℓ 1 ..., 𝑎𝑡 , 𝑏 𝑡 , ℓ 𝑡 ,
Optimal last-iterate convergence in matrix games
3
and the sequence of profiles (𝜇𝑡 , 𝜈 𝑡 ) = 𝑤 𝑡 ∈ 𝑊 N will need to be predictable with respect to F . Theorem 5.1 of Fiegel et al. (2025) shows that, in this setting, a convergence to 0 of 𝐸𝐺 (𝑤 𝑡 ) cannot be guaranteed at a rate better than O (𝑡 −1/4 ) if the game is unknown and the two players are not allowed to communicate their own action.
3
Characterization as a variational inequality problem
This problem can be usefully formulated as a variational inequality, but this requires first introducing the concept of the pseudo-gradient. Definition 3.1. The pseudo-gradient of ℓ is defined as 𝐹 :𝑊 → − R𝐾 (𝜇, 𝜈) ↦→ ∇𝜇 ℓ (𝜇, 𝜈), 1 − ∇𝜈 ℓ (𝜇, 𝜈) . Definition 3.2. (Stampacchia, 1964) Given an operator 𝐹 : 𝑊 → − R𝐾 , with 𝑊 ⊂ R𝐾 , we define the (weak) variational inequality problem as finding some 𝑤 ★ ∈ 𝑊 that satisfies ∀𝑤 ∈ 𝑊 ,
𝐹 (𝑤 ★), 𝑤 ★ − 𝑤 ≤ 0
As shown by the next lemma, this problem can be seen as a generalization of the problem of finding a minimax profile in our setting. Property 3.3. Since the loss ℓ is convex-concave, then the following holds: 𝑤 ★ is a Nash equilibrium ⇔ 𝑤 ★ solves the variational inequality above . Furthermore, since ℓ is actually linear in both of its components, ⟨𝐹 (𝑤), 𝑤 − 𝑤 ′ ⟩ EG(𝑤) = max ′ 𝑤 ∈𝑊
However, as the problem lies in the bandit setting, 𝐹 is not observed directly when playing. A standard solution is to introduce and to define importance-sampling estimates. Definition 3.4. The importance-sampling estimate of the loss of each player at iteration 𝑡 is defined by 1 − ℓ𝑡 ℓ𝑡 𝑡 𝑡 bmax,IS 𝑡} I and ℓ (𝑏) = I {𝑏=𝑏𝑡 } ℓbmin,IS (𝑎) = {𝑎=𝑎 𝜇 (𝑎)𝑡 𝜈 (𝑏)𝑡 where 𝑎𝑡 and 𝑏 𝑡 are the actions sampled at iteration 𝑡, and ℓ 𝑡 the loss observed by both players. The importance-sampling estimate of the operator 𝐹 can then be estimated at each iteration at 𝑤 𝑡 using 𝑡 𝑡 𝐹ˆ (𝑤 𝑡 ) = ℓbmin,IS , ℓbmax,IS This estimate is unbiased as long as 𝑤𝑖𝑡 > 0 for all actions 𝑖, i.e. : E𝑡 𝐹ˆ (𝑤 𝑡 ) = 𝐹 (𝑤 𝑡 ) . where E𝑡 [·] := E ·|F 𝑡 . Remark 3.5. This estimator is unbiased, yet it is not bounded, and its variance can become
Optimal last-iterate convergence in matrix games
4
arbitrarily large. Indeed, E𝑡 ∥ 𝐹ˆ𝑡 (𝑤 𝑡 ) ∥ 22 h h i i ∑︁ 1 ∑︁ 1 𝑡 𝑡 𝑡 2 𝑡 𝑡 2 𝑡 𝑏 = 𝑏 𝑎 = 𝑎 + E 1 − ℓ 𝑏 = 𝑏 P = E ℓ 𝑎 = 𝑎 P 𝑡 𝑡 𝑡 𝑡 2 2 𝑤 𝑎𝑡 𝑎 𝑏 𝑤𝑡 𝐴+𝑏
=
∑︁ 1
𝑡 E𝑡
𝑎
h ℓ
𝑡 2
i
𝑎 = 𝑎𝑡 +
𝑤𝑎
∑︁
1
𝑏
𝑡 𝑤 𝐴+𝑏
h E𝑡
1−ℓ
𝑡 2
𝑏 = 𝑏𝑡
i
and this quantity diverges as the probability associated with any action with a non-surely null loss goes to 0.
4
Intuition of the approach
As the game is zero-sum, 𝐹 is monotone (Martinet, 1970; Tyrrell, 1976), i.e., it satisfies the following property: ∀𝑤, 𝑤 ′ ∈ 𝑊 , ⟨𝐹 (𝑤) − 𝐹 (𝑤 ′ ), 𝑤 − 𝑤 ′ ⟩ ≥ 0 . This property explains why the game is solvable; however, obtaining last-iterate convergence is not straightforward, especially in the bandit setting. A method previously studied to obtain it consists in adding some regularization to the operator 𝐹 . Given some Legendre function Ψ (Hiriart-Urruty and Lemaréchal, 2001), the operator 𝐹𝜏 is defined, given 𝜏 > 0, by 𝐹𝜏 (𝑤) = 𝐹 (𝑤) + 𝜏∇Ψ(𝑤) . In particular, if Ψ is 1-strongly convex with respect to some norm ∥·∥, then 𝐹𝜏 becomes 𝜏-strongly monotone, i.e. ∀𝑤, 𝑤 ′ ∈ 𝑊 , ⟨𝐹𝜏 (𝑤) − 𝐹𝜏 (𝑤 ′ ), 𝑤 − 𝑤 ′ ⟩ ≥ 𝜏 ∥𝑤 − 𝑤 ′ ∥ 2 . Used with
Ψentropy (𝑤) = −
∑︁
𝑤𝑖 log(𝑤𝑖 )
𝑖
which is 1-strongly convex with respect to the ∥·∥ 1 norm and combined with mirror descent, this regularization was proven to guarantee a (primal) convergence of the exploitability gap through a convergence of the iterates 𝑤 𝑡 to the regularized solution 𝑤 ★,𝜏 of 𝐹𝜏 . The exploitability gap was then computed as a result, with an additional dependency on 𝜏. We propose here another way of bounding the exploitability gap, by considering instead the dual norm ∥𝐹𝜏 (𝑤 𝑡 ) ∥★ of the regularized operator on the iterates. We start by providing the intuition by using the Euclidean norm as a regularizer (which is 1-strongly-convex with respect to itself). Gradient descent: With Ψ = 21 ∥·∥ 22 the Euclidean norm, the mirror descent reduces to the gradient descent. Given a constant learning rate 𝜂, ignoring the constraints: 𝑤 𝑡 +1 = 𝑤 𝑡 − 𝜂 𝑡 𝐹ˆ𝜏 (𝑤 𝑡 ) = 𝑤 𝑡 − 𝜂 𝑡 𝐹ˆ (𝑤 𝑡 ) + 𝜏𝑤 𝑡 . We further assume here that the unbiased estimate 𝐹ˆ of 𝐹 has a bounded second-order: E𝑡 ∥ 𝐹ˆ (𝑤 𝑡 ) ∥ 22 ≤ 𝜎 2
and by extension
E𝑡 ∥ 𝐹ˆ𝜏 (𝑤 𝑡 ) ∥ 22 ≤ 𝜎𝜏2 := (𝜎 + 𝜏) 2 .
Note that this assumption is not realistic as demonstrated by Remark 3.5. The next proposition aims to illustrate this method of bounding in the dual, in this Euclidean setting for simplicity, relying on this assumption. A more formal result, using the log-barrier, will be stated in the next section.
Optimal last-iterate convergence in matrix games
5
Proposition 4.1. (Informal) Let 𝜏0 = 𝜏𝑡 −1/4 and 𝜂 𝑡 = 𝜏1 𝑡 −3/4 . Then, with the above gradient descent and second-order assumption on the noise: E ∥𝐹 (𝑤 𝑡 ) ∥ 2 = O (𝑡 −1/4 ) Proof. (Informal) At every iteration 𝑡, with 𝐿 = 𝐾 + 𝜏 𝑡 : E𝑡 ∥𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) ∥ 22 − ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 = 2 E𝑡 𝐹𝜏 𝑡 𝑤 𝑡 +1 − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝐹𝜏 𝑡 (𝑤 𝑡 ) 2 + E𝑡 ∥𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 −2 ≤ 𝑡 𝐹𝜏 𝑡 E𝑡 𝑤 𝑡 +1 − 𝐹𝜏 𝑡 (𝑤 𝑡 ), E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 2 + 𝐿 2 E𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 22 𝜂 2 −2 𝑡 ≤ 𝑡 𝜏 ∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 22 + 𝐿𝜂 𝑡 E𝑡 ∥ 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 𝜂 2 ≤ −2𝜏 𝑡 𝜂 𝑡 ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 + 𝐿𝜂 𝑡 𝜎𝜏 −2 = ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 + (𝐿𝜎𝜏 /𝜏) 2 𝑡 −3/2 𝑡 where we used, in this order, the unbiasedness of 𝐹ˆ along with the definition of 𝑤 𝑡 +1 , the 𝐿Lipschitzness of 𝐹𝜏 𝑡 , the 𝜏 𝑡 -monotonicity of 𝐹𝜏 𝑡 and the second order assumption on 𝐹ˆ𝜏 𝑡 . Simultaneously, ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) ∥ 22 − ∥𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) ∥ 22 = 2(𝜏 𝑡 +1 − 𝜏 𝑡 ) 𝑤 𝑡 +1, 𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) 2 + 𝜏 𝑡 +1 − 𝜏 𝑡
2
∥𝑤 𝑡 +1 ∥ 22
𝜏 𝜏2 ≤ 𝑡 −5/4 ∥𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) ∥ 2 + 𝑡 −5/2 2 16
where we used
𝜏 𝜏 𝑡 +1 − 𝜏 𝑡 ≤ 𝑡 −5/4 4 These two inequalities together lead to a recursive inequality of the type: 1 𝑡 +1 2 ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 + O (𝑡 −3/2 ) E𝑡 +1 ∥𝐹𝜏 𝑡 +1 (𝑤 )∥ 2 ≤ 1 − 𝑡
which leads to a bound, at every 𝑡, ∥E 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 22 = O (𝑡 −1/2 ) . The final bound is then obtained using ∥𝐹 (𝑤 𝑡 ) ∥ 2 ≤ ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥ 2 + 𝜏 𝑡 . ■ As previously mentioned, this result could not be applied to our setting mainly because the bounded second-order assumption does not hold on 𝐹ˆ (𝑤 𝑡 ), at least with the Euclidean norm.
5
Main algorithm
Given some Legendre regularizer Ψ, the mirror descent is defined iteratively by, given 𝜂 𝑡 as the learning rates and 𝜉 𝑡 as some steps: 𝑤 𝑡 +1 = arg min 𝐷 Ψ (𝑤, 𝑤 𝑡 ) + 𝜂 𝑡 𝜉 𝑡 , 𝑤 𝑤 ∈𝑊
Optimal last-iterate convergence in matrix games
6
Algorithm 1 Regularized Mirror Descent with log-barrier - Min-player 1: Input: Learning rate 𝜂 Regularization strength 𝜏 Starting iteration 𝑇0 Confidence 𝛿 Í𝐴 𝑡 +𝑇 2: Define: Ψmin (𝜇) = − 𝑖=1 log(𝜇𝑖 ), 𝜂 𝑡 ← 𝜂.(𝑡 + 𝑇0 ) −3/4 and 𝜏 𝑡 ← 𝜏 . log( 𝛿 0 ) (𝑡 + 𝑇0 ) −1/4 𝜇 0 is initialized to the uniform policy. 3: Algorithm: For 𝑡 = 0 to +∞: Sample and play action 𝑎𝑡 ∼ 𝜇𝑡 Observe loss ℓ 𝑡 𝑡 ,𝜇 𝜇𝑡 +1 ← arg min𝜇 ∈ΔA 𝐷 Ψmin (𝜇, 𝜇𝑡 ) + 𝜂 𝑡 ℓˆmin 𝑡 where ℓˆ𝑡 ← 𝑡 ℓ 𝑡 I {𝑎𝑡 } + 𝜏 𝑡 ∇Ψmin (𝜇𝑡 ) min
𝜇 (𝑎 )
where 𝐷 Ψ (𝑤, 𝑤 ′ ) = Ψ(𝑤) − Ψ(𝑤 ′ ) − ⟨∇Ψ(𝑤 ′ ), 𝑤 − 𝑤 ′ ⟩ is the Bregman divergence (Hiriart-Urruty and Lemaréchal, 2001). As in the previous section, we propose to use as the step the regularized importance sampling estimate, given some regularization strength 𝜏 𝑡 : 𝜉 𝑡 = 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) = 𝐹ˆ (𝑤 𝑡 ) + 𝜏 𝑡 ∇Ψ(𝑤 𝑡 ) . Algorithm 1, presented from the point of view of the min-player, uses this approach with the log-barrier as Ψ, defined by: ∑︁ Ψlog-barrier (𝑤) = − log(𝑤𝑖 ) . 𝑖
It enjoys a convergence with high probability at a near-optimal rate, proven in the appendix, relying on some assumption on the parameters. Assumption 5.1. We assume that the parameters 𝜂, 𝜏 and 𝑇0 of the algorithm satisfy • 𝜂𝜏1 = 𝑜 (1) • 𝜂 = 𝑜 (1) 𝑇0 2 4 • 𝜂𝜏 ≤ log(𝑇 4 and 𝑇0 ≤ log(1/𝛿) 𝜏 0) Given the first two parameters 𝜂 and 𝜏, the existence of some 𝑇0 that satisfies the third assumption is always guaranteed. For clarity reasons in the proof, the exact constants are not computed, but only depend on 𝐾 and 𝛿. These constants would be high in theory, but we conjecture that they would be reasonable in practice. Theorem 5.2. If both players run Algorithm 1 with parameters satisfying Assumption 5.1, then for any confidence 𝛿 > 0, with probability at least 1 − 𝛿: 𝑡 + 𝑇0 𝑡 EG(𝑤 ) ≤ 2𝐾𝜏 log (𝑡 + 𝑇0 ) −1/4 . 𝛿 at every iteration 𝑡. The improvements over the past approaches are mostly achieved through two means: • The different analysis based on the convergence of the dual norm of 𝐹𝜏 𝑡 (𝑤 𝑡 ) instead of the explicit convergence to some regularized solution. It allows the use of a varying 𝜏 𝑡 , which leads to true last-iterate results not relying on a fixed known horizon. • The use of the log-barrier as a regularizer, which is more "stable" than the Shannon entropy and which allows stating the results with high probability rather than in expectation. The main difference can be seen in the quantity ∥ 𝐹ˆ (𝑤 𝑡 ) ∥ 2∇2 Ψ(𝑤𝑡 ) −1 linked to the variation of the primal iterates, which is bounded almost surely at every iteration with the log-barrier, and only in expectation with the Shannon entropy.
Optimal last-iterate convergence in matrix games
6
7
Analysis of the Algorithm
We present in this section the main aspects of the proof of Theorem 5.2. The lemmas specifically are proven in Section A of the appendix We start by defining some norms directly linked to the regularizer, but at specific points of the domain. Definition 6.1. For any 𝑤 ∈ R𝐾>0 , let ⟨·, ·⟩ 𝑤 and ⟨·, ·⟩★,𝑤 be the scalar products defined by ⟨𝑥, 𝑦⟩ 𝑤 = 𝑥, ∇2 Ψ(𝑤)𝑦
and
⟨𝑥, 𝑦⟩★,𝑤 = 𝑥, ∇2 Ψ(𝑤 𝑡 ) −1𝑦
with the associated norms √︁ ∥𝑥 ∥ 𝑤 = ⟨𝑥, ∇2 Ψ(𝑤)𝑥⟩
and
∥𝑥 ∥★,𝑤 =
√︁
⟨𝑥, ∇2 Ψ(𝑤) −1𝑥⟩ .
These norms, defined locally, play the role of the ∥·∥ 2 norm of the Section 4 and now really satisfy the assumption on the second-order moment. √ Lemma 6.2. For every 𝑤 ∈ 𝑊 , 𝐹 is 𝐾-Lipschitz with respect to these two norms, i.e: √ ∀(𝑤 1, 𝑤 2 ) ∈ 𝑊 2, ∥𝐹 (𝑤 1 ) − 𝐹 (𝑤 2 ) ∥★,𝑤 ≤ 𝐾 ∥𝑤 1 − 𝑤 2 ∥ 𝑤 The unbiased importance-sampling estimate 𝐹ˆ of 𝐹 at 𝑤 satisfies almost surely: ∥ 𝐹ˆ (𝑤) ∥★,𝑤 ≤ 2 To deal with the constraints, the norm of 𝐹𝜏 (𝑤) is not considered directly, and a more precise quantity is used instead (equivalent without the constraints as the normal cone would be reduced to {0}). Definition 6.3. We define, for any 𝑤 ∈ 𝑊 ∩ R𝐾>0 , the normal cone 𝑁𝑊 (𝑤) = 𝑓 ∈ R𝐾 ∀𝑤 ′ ∈ 𝑊 ⟨𝑓 , 𝑤 − 𝑤 ′ ⟩ ≥ 0 and, given 𝜏 ≥ 0, 𝑑𝜏 (𝑤) = 𝑑 ∥ · ∥ ★,𝑤 (𝑁𝑊 (𝑤), −𝐹𝜏 (𝑤)) This quantity can be used to bound the exploitability gap at every iteration. Lemma 6.4. Assume that 𝑤 ∈ 𝑊 ∩ R𝐾>0 satisfies, for 𝜏 ≥ 0: 𝑑𝜏 (𝑤) ≤ 𝜏 . Then ⟨𝐹 (𝑤), 𝑤 − 𝑤 ′ ⟩ ≤ 2𝜏𝐾 EG(𝑤) = max ′ 𝑤 ∈𝑊
It justifies using a recursive bound on 𝑑𝜏 𝑡 (𝑤 𝑡 ) similar to the one of Proposition 4.1, replacing the gradient descent updates with the mirror descent updates. However, obtaining the same kind of recursive bound requires solving many issues that have to be simultaneously treated in the analysis: • The updates now rely on some second order approximation, such as 𝑤 𝑡 +1 = 𝑤 𝑡 − 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) + O ((𝜂 𝑡 ) 2 ) which have to be analyzed more carefully.
Optimal last-iterate convergence in matrix games
8
• Some extra terms appear because of the norm now changing from ∥·∥★,𝑤𝑡 to ∥·∥★,𝑤𝑡 +1 at every iteration. • The constraints (𝑤 must remain in the product of simplices 𝑊 ) have to be taken into account in the recursive formula. The extra terms are all handled with the next theorem, which formalizes the recursion that appeared in the proof of Proposition 4.1 in addition of providing the bound with high-probability. The iteration indexes are additionally offset by 𝑇0 to ensure that some initial conditions are satisfied. Lemma 6.5. Let 𝛿 ∈ (0, 1), 𝑇0 ∈ N, 𝑈 be a non-negative stochastic process adapted to some filtration F , and 𝑇1 be the stopping time defined by 1 𝑡 + 𝑇0 𝑡 𝑇1 = min 𝑡 𝑈 > √ log . 𝛿 𝑡 + 𝑇0 Assume that we have for all 𝑡 ≤ 𝑇1 :
1 𝑈 0 ≤ √ log(𝑇0 ) 𝑇0
and ∀𝑡 ∈ N, 𝑡 < 𝑇1 =⇒ 𝑈
𝑡 +1
1 = 1− 𝑈 𝑡 + 𝑏 𝑡 +1 + 𝑊 𝑡 +1 𝑡 + 𝑇0
3
where 𝑏 𝑡 +1 ≤ (𝑡 + 𝑇0 + 1) − 2 and (𝑊 𝑡 )𝑡 >0 is a stochastic processes adapted to F that satisfies E𝑡 𝑊 𝑡 +1 = 0
and
𝑊
𝑡 +1 2
3
(𝑡 + 𝑇0 + 1) − 2 𝑡 ≤ 𝑈 . 2
Then P(𝑇1 < +∞) ≤ 𝛿 . Its proof is given in Section A and is based on a variation of the proof of the Azuma-Hoeffding inequality. Used with 𝑈 𝑡 ≃ 𝑑𝜏 𝑡 (𝑤 𝑡 ), this lemma yields a bound of 𝑑𝜏 𝑡 (𝑤 𝑡 ) over all iterations with a probability at least 1 −𝛿, and thus a bound of the exploitability gap. However, the multiple difficulties mentioned earlier lead to a proof that is quite complex due to the high number of additional terms appearing in the recursion.
7
Extension to extensive-form games
Extensive-form games (von Stengel, 1996) are a generalization of the matrix games, in which players take successive actions instead. For 𝑛 players, it consists of • A tree of states S of height 𝐻 , partitioned for the min- and max-player into respectively the sets of information sets X and Y. • Two action sets, A and B one for each player. • An initial state 𝑠 1 ∈ S and a state-transition probability kernel (𝑝ℎ )ℎ∈ [𝐻 −1] with 𝑝ℎ : S × A × B → Δ(S) for each ℎ ∈ [𝐻 − 1]. • A loss function (ℓℎ )ℎ∈ [𝐻 ] with ℓℎ : S × A × B → [0, 1] 𝑛 . Each game proceeds as follows: • The game starts at depth 1 and state 𝑠 1 . • At depth ℎ ∈ [𝐻 ], every player 𝑖 observes the information set 𝑥𝑖,ℎ ∈ X𝑖 associated with the current state 𝑠ℎ , then choose some action 𝑎ℎ ∈ A and 𝑏ℎ ∈ B. • As a result, every player 𝑖 receives the loss ℓ𝑖,ℎ (𝑠ℎ , 𝑎ℎ , 𝑏ℎ ) and if ℎ < 𝐻 , the state transitions to a new state 𝑠ℎ+1 ∼ 𝑝 (·|𝑠ℎ , 𝑎ℎ , 𝑏ℎ ) in S.
Optimal last-iterate convergence in matrix games
9
Perfect recall: We further assume that the players perfectly remember their past observations and actions. Consequently, for any action set 𝑥ℎ of depth ℎ, there exists a unique path (𝑥 1, 𝑎 1, , ..., 𝑥ℎ−1, 𝑎ℎ−1, 𝑥ℎ ) that leads to it for the min-player, and (𝑦1, 𝑏 1, , ..., 𝑦ℎ−1, 𝑏ℎ−1, 𝑦ℎ ) for the max-player. The same algorithm can be applied under these settings with some small changes. One of the first changes is due to the fact that, in contrast to the matrix setting, the loss is not linear with respect to each player’s policy. It is nonetheless linear with respect to each of the following sequence-form policy. Definition 7.1 (Sequence-form policy and pseudo-gradient). (von Stengel, 1996) Let 𝜇 = (·|𝑥)𝑥 ∈ X be a policy for the min-player. The associated sequence-form policy 𝜇→ − is defined by, for all action sets 𝑥ℎ of depth ℎ and action 𝑎ℎ 𝜇→ − 𝑥ℎ (𝑎ℎ ) =
ℎ Ö
𝜇 (𝑎ℎ ′ |𝑥ℎ ′ )
ℎ ′ =1
where (𝑥 1, 𝑎 1, , ..., 𝑥ℎ−1, 𝑎ℎ−1, 𝑥ℎ ) is the unique path that leads to 𝑥ℎ . 𝜈→ − is defined similarly for the max-player. The sequence-form policy profiles 𝑤 = (𝜇→ − , 𝜈→ − ) can similarly be defined, and will be directly referred to as 𝑊 , as the expected loss given these policies. It can in particular, be used to define the pseudo-gradient 𝐹 as in the previous sections: 𝐹 :𝑊 → − R𝐾 (𝜇→ − , 𝜈→ − ) ↦→ ∇𝜇→ − E
"𝐻 −1 ∑︁
#! ℓℎ (𝜇→ − , 𝜈→ −)
, 𝐻 − ∇𝜈→ − E
"𝐻 −1 ∑︁
ℎ=0
#!! ℓℎ (𝜇→ − , 𝜈→ −)
.
ℎ=0
The same importance-sampling estimate can be defined in the extensive-form setting. Definition 7.2. An importance-sampling estimate can be defined similarly, using this time the sequence-form policies: 𝑡 ℓbmin (𝑥ℎ , 𝑎ℎ ) =
ℓ𝑡 I{𝑥ℎ =𝑥 𝑡 ,𝑎ℎ =𝑎𝑡 } ℎ ℎ → − (𝑥ℎ , 𝑎ℎ )
𝜇𝑡
𝑡 (𝑏) = and ℓbmax
1 − ℓ𝑡 I{ 𝑦ℎ =𝑦𝑡 ,𝑏ℎ =𝑏𝑡 } . ℎ ℎ → − (𝑦ℎ , 𝑏ℎ )
𝜈𝑡
The importance-sampling estimate of the operator 𝐹 can again be estimated with: 𝑡 𝑡 𝐹ˆ (𝑤 𝑡 ) = ℓbmin , ℓbmax This estimate is also unbiased as long as 𝑤 𝑡 (𝑥, 𝑎) > 0 for all states 𝑥 and actions 𝑎: E𝑡 𝐹ˆ (𝑤 𝑡 ) = 𝐹 (𝑤 𝑡 ) . And this estimate satisfies the same properties as before. Lemma 7.3. Let 𝐾 = |𝐴| |𝑋 | + |𝐵| |𝑌 | be the total number of actions over √ both trees. The operator 𝐹 is linear and monotone. For any 𝑤 ∈ 𝑊 , it is also 𝐻 𝐾-Lipschitz with respect to the ∥·∥ 𝑤 and ∥·∥★,𝑤 norms: √ ∀(𝑤 1, 𝑤 2 ) ∈ 𝑊 2, ∥𝐹 (𝑤 1 ) − 𝐹 (𝑤 2 ) ∥★,𝑤 ≤ 𝐻 𝐾 ∥𝑤 1 − 𝑤 2 ∥ 𝑤 and the above unbiased estimate 𝐹ˆ satisfies: ∥ 𝐹ˆ (𝑤) ∥★,𝑤 ≤ 2𝐻
Optimal last-iterate convergence in matrix games
10
Algorithm 2 Extensive-form Regularized Mirror Descent with log-barrier - Min-player 1: Input: Learning rate 𝜂 Regularization strength 𝜏 Starting iteration 𝑇0 Confidence 𝛿 Í Í 𝑡 −3/4 2: Define: Ψmin (𝜇) = − 𝑥 𝑎 log(𝜇→ − 𝑥 (𝑎)), 𝜂 ← 𝜂.(𝑡 + 𝑇0 ) −1/4 0 and 𝜏 𝑡 ← 𝜏 . log( 𝑡 +𝑇 𝛿 ) (𝑡 + 𝑇0 ) 0 𝜇 is initialized to the uniform policy. 3: Algorithm: For 𝑡 = 0 to +∞: For each ℎ = 0 to 𝐻 − 1: 𝜇 𝑡 𝑡 (·) → − 𝑥ℎ 𝑡 𝑡 𝑡 Sample and play action 𝑎ℎ ∼ 𝜇 (·|𝑥ℎ ) = 𝜇𝑡 (or 𝜇→ 𝑡 − 𝑥 0 (·) if ℎ = 0) (𝑎ℎ−1 ) 𝑡 → − 𝑥ℎ−1 Observe loss ℓℎ𝑡 𝑡 ,𝜇 Update 𝜇𝑡 +1 ← arg min𝜇 ∈ΔA 𝐷 Ψmin (𝜇, 𝜇𝑡 ) + 𝜂 𝑡 ℓˆmin Í𝐻 −1 ℓℎ𝑡 𝑡 where ℓˆmin ← ℎ=0 + 𝜏 𝑡 ∇Ψmin (𝜇𝑡 ) 𝑡 𝑡 I 𝑥 𝑡 ,𝑎𝑡 𝜇 → − 𝑥 𝑡 (𝑎 ) { ℎ ℎ } ℎ
For this reason, Algorithm 2 enjoys the same kind of guarantees as Algorithm 1. Theorem 7.4. If both players run Algorithm 2 with parameters satisfying Assumption 5.1, then for any confidence 𝛿 > 0, with probability at least 1 − 𝛿: 𝑡 + 𝑇0 𝑡 (𝑡 + 𝑇0 ) −1/4 . EG(𝑤 ) ≤ 2𝐾𝜏 log 𝛿 at every iteration 𝑡. The proof is indeed the same as in Theorem 5.2, simply using instead the properties of Lemma 7.3.
8
Conclusion
Algorithms 1 and 2 solve the main issue behind the approaches of Fiegel et al. (2025). Using the more stable log-barrier regularization, it achieves a last-iterate convergence with high probability without initial knowledge of the horizon. The analysis, completely presented in the appendix, relies on an analysis in the dual space. It raises the following open questions: • While the main idea of the proof (recursively upper-bounding 𝑑 𝜏 (𝑤 𝑡 )) is straightforward, it is quite long as all the above details need to be accounted for. Is a simpler proof achievable? • Is the use of the log-barrier regularization really necessary for the adaptivity of 𝜏 to work? Or can other regularization also be adaptive to the horizon, potentially without the high probability guarantees? • Could an optimistic mirror descent approach work for this problem, and would it be more efficient in practice? • Currently, the updates of Algorithm 2 are quite expensive as they act on the whole tree at each iteration, implying a time complexity of at least Ω(𝐾) at each iteration. Does there exist an efficient way of computing them (by only updating along the trajectory when needed for example). 𝑡
References Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory, 2009.
Optimal last-iterate convergence in matrix games
11
Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In Neural Information Processing Systems, 2023. Côme Fiegel, Pierre Menard, Tadashi Kozuno, Michal Valko, and Vianney Perchet. The harder path: Last iterate convergence for uncoupled learning in zero-sum games with bandit feedback. In International Conference on Machine Learning, 2025. Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Fundamentals of Convex Analysis, pages 163–208. Springer, 2001. Ehsan Asadi Kangarshahi, Ya-Ping Hsieh, Mehmet Fatih Sahin, and Volkan Cevher. Let’s be honest: An optimal no-regret framework for zero-sum games. In International Conference on Machine Learning, 2018. Christian Kroer, Kevin Waugh, Fatma Kilinç-Karzan, and Tuomas Sandholm. Faster first-order methods for extensive-form game solving. In ACM Conference on Economics and Computation, 2015. B. Martinet. 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. L. D. Popov. 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, 1980. Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Neural Information Processing Systems, 2013. Guido Stampacchia. Formes bilinéaires coercitives sur les ensembles convexes. In Comptes Rendus de l’Académie des Sciences, Paris, 1964. Rockafellar Ralph Tyrrell. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 1976. J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295–320, 1928. Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220–246, 1996. Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on Learning Theory, 2021. Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In International Conference on Artificial Intelligence and Statistics, 2019.
Optimal last-iterate convergence in matrix games
12
The appendix aims to prove Theorems 5.2 and 7.4.
A
Proof - Main lemmas
We start by proving the lemmas stated in the main article. Lemma 6.4. Assume that 𝑤 ∈ 𝑊 ∩ R𝐾>0 satisfies, for 𝜏 ≥ 0: 𝑑𝜏 (𝑤) ≤ 𝜏 . Then ⟨𝐹 (𝑤), 𝑤 − 𝑤 ′ ⟩ ≤ 2𝜏𝐾 EG(𝑤) = max ′ 𝑤 ∈𝑊
Proof. We will use that ∇Ψ(𝑤) = (−𝑤𝑖−1 )𝑖 ∈ [𝐾 ]
and
∇2 Ψ(𝑤) = Diag (𝑤𝑖−2 )𝑖 ∈ [𝐾 ]
Let 𝑔 ∈ 𝑁𝑊 (𝑤) such that 𝑑𝜏 (𝑤) = ∥𝐹𝜏 (𝑤) + 𝑔∥★,𝑤 . From the assumption, we first notice that, for all 𝑖 ∈ [𝐾], by definition of the norm ∥·∥★,𝑤 , 2
𝑤𝑖2 𝐹 (𝑤)𝑖 + 𝑔𝑖 − 𝜏𝑤𝑖−1 ≤ 𝜏 2 , which is equivalent to |𝑤𝑖 (𝐹 (𝑤)𝑖 + 𝑔𝑖 ) − 𝜏 | ≤ 𝜏 , and which implies in particular 𝐹 (𝑤)𝑖 + 𝑔𝑖 ≥ 0. Then, for any 𝑤 ′ ∈ 𝑊 , ⟨𝐹 (𝑤), 𝑤 − 𝑤 ′ ⟩ ≤ ⟨𝐹 (𝑤) + 𝑔, 𝑤 − 𝑤 ′ ⟩ ≤ ⟨𝐹 (𝑤) + 𝑔, 𝑤⟩ = ⟨𝐹𝜏 (𝑤) + 𝑔, 𝑤⟩ + 𝜏𝐾 √ ≤ 𝐾𝑑𝜏 (𝑤) + 𝜏𝐾 ≤ 2𝜏𝐾 where we used, in this order: • the definition of the normal cone associated to 𝑤, • 𝐹 (𝑤) + 𝑔 being in the non-negative quadrant as shown above • ⟨∇Ψ(𝑤), 𝑤⟩ = −𝐾 by definition of ∇Ψ, • the Cauchy-Schwarz inequality, as 𝐾 ∑︁ 𝑖=1
!2 𝑤𝑖 (𝐹𝜏 (𝑤)𝑖 + 𝑔𝑖 )
≤𝐾
𝐾 ∑︁
𝑤𝑖2 (𝐹𝜏 (𝑤)𝑖 + 𝑔𝑖 ) 2
𝑖=1
■ Lemma 6.5. Let 𝛿 ∈ (0, 1), 𝑇0 ∈ N, 𝑈 be a non-negative stochastic process adapted to some filtration F , and 𝑇1 be the stopping time defined by 1 𝑡 + 𝑇0 𝑡 𝑇1 = min 𝑡 𝑈 > √ log . 𝛿 𝑡 + 𝑇0
Optimal last-iterate convergence in matrix games
Assume that we have for all 𝑡 ≤ 𝑇1 :
13
1 𝑈 0 ≤ √ log(𝑇0 ) 𝑇0
and ∀𝑡 ∈ N, 𝑡 < 𝑇1 =⇒ 𝑈
𝑡 +1
1 = 1− 𝑈 𝑡 + 𝑏 𝑡 +1 + 𝑊 𝑡 +1 𝑡 + 𝑇0
3
where 𝑏 𝑡 +1 ≤ (𝑡 + 𝑇0 + 1) − 2 and (𝑊 𝑡 )𝑡 >0 is a stochastic processes adapted to F that satisfies E𝑡 𝑊 𝑡 +1 = 0
and
𝑊
𝑡 +1 2
3
(𝑡 + 𝑇0 + 1) − 2 𝑡 ≤ 𝑈 . 2
Then P(𝑇1 < +∞) ≤ 𝛿 . Proof. We define the stochastic process 𝑄 adapted to F by √
𝑄 𝑡 = 𝑒 𝑡 +𝑇0𝑈 −log(𝑡 +𝑇0 ) 𝑡
for all 𝑡 ≤ 𝑇1 , and show that (𝑄 𝑡 ∧𝑇1 )𝑡 is a super-martingale. Take 𝑡 < 𝑇1 , we first observe, using Hoeffding Lemma and the assumption on 𝑊 , that: √ 𝑡 i h √ 𝑡 +𝑇0 +1𝑈 𝑡 √𝑈 𝑡 +𝑇0 +1𝑊 𝑡 2 𝑡 +𝑇0 +1 ≤𝑒 ≤ 𝑒 2(𝑡 +𝑇0 ) E𝑠 𝑒
Then, i h √ 𝑡 +1 E𝑠 𝑄 𝑡 +1 = E𝑠 𝑒 𝑡 +𝑇0 +1𝑈 −log(𝑡 +𝑇0 +1) i √ h √ √ 𝑡 𝑡 +1 𝑡 +1 = 𝑒 𝑡 +𝑇0 +1(1−1/(𝑡 +𝑇0 ) )𝑈 E𝑡 𝑒 𝑡 +𝑇0 +1𝑊 𝑒 𝑡 +𝑇0 +1𝑏 −log(𝑡 +𝑇0 +1) √
≤ 𝑒 𝑡 +𝑇0 +1(1−1/(2(𝑡 +𝑇0 ) ) )𝑈 𝑒 1/(𝑡 +𝑇0 +1) −log(𝑡 +𝑇0 +1) √
𝑡
≤ 𝑒 𝑡 +𝑇0𝑈 𝑒 − log(𝑡 +𝑇0 ) 𝑡
= 𝑄𝑡 where we relied, in this order, on • the assumption regarding 𝑈 𝑡 +1 , • the above inequality from Hoeffding Lemma, • the upperbound of 𝑏 𝑡 +1 , √ √ • the inequality 𝑠 + 1(1 − 1/(2𝑠)) ≤ 𝑠 for 𝑠 = 𝑡 + 𝑇0 , as √ √ 𝑠 +1− 𝑠 =
∫ 𝑠+1 𝑠
𝑑𝑢 √ ≤ 2 𝑢
∫ 𝑠+1 𝑠
𝑑𝑢 1 √ = √ ≤ 2 𝑠 2 𝑠
√ 𝑠 +1 , 2𝑠
1 • the inequality 𝑠+1 − log(𝑠 + 1) ≤ − log(𝑠) for 𝑠 = 𝑇 + 𝑇0 , as
log(𝑠 + 1) − log(𝑠) =
∫ 𝑠+1 𝑠
This proves that (𝑄 𝑡 ∧𝑇1 ) is a super-martingale.
𝑑𝑢 ≥ 𝑢
∫ 𝑠+1 𝑠
𝑑𝑢 1 = . 𝑠 +1 𝑠 +1
Optimal last-iterate convergence in matrix games
14
Then, using Ville’s inequality 1 𝑡 + 𝑇0 P(𝑇1 < +∞) = P ∃𝑡 ≥ 𝑇0, 𝑈 > √ log 𝛿 𝑡 + 𝑇0 √︁ 1 𝑡 = P ∃𝑡 ≥ 𝑇0, 𝑡 + 𝑇0𝑈 − log(𝑡 + 𝑇0 ) > log 𝛿 = P ∃𝑠 ≥ 𝑇0, 𝑄 𝑡 ∧𝑇1 > 1/𝛿
𝑡
≤ E(𝑄 0 )𝛿 ≤𝛿 which concludes.
■
√ Lemma 6.2. For every 𝑤 ∈ 𝑊 , 𝐹 is 𝐾-Lipschitz with respect to these two norms, i.e: √ ∀(𝑤 1, 𝑤 2 ) ∈ 𝑊 2, ∥𝐹 (𝑤 1 ) − 𝐹 (𝑤 2 ) ∥★,𝑤 ≤ 𝐾 ∥𝑤 1 − 𝑤 2 ∥ 𝑤 The unbiased importance-sampling estimate 𝐹ˆ of 𝐹 at 𝑤 satisfies almost surely: ∥ 𝐹ˆ (𝑤) ∥★,𝑤 ≤ 2 Proof. As for all 𝑖, 𝑤𝑖 ≤ 1, and, for a given action of one player, the reward is Lipschitz with respect to the policy of the opponent in 𝐿 1 : 2 ∥𝐹 (𝑤 ) − 𝐹 (𝑤) ∥★,𝑤 = ′
𝐾 ∑︁
(𝑤𝑖 ) 2 |𝐹 (𝑤 ′ )𝑖 − 𝐹 (𝑤)𝑖 | 2
𝑖=1
=
𝐴 ∑︁
2
2
′
(𝑤𝑖 ) |𝐹 (𝑤 )𝑖 − 𝐹 (𝑤)𝑖 | +
𝑖=1
≤
≤
𝐴+𝐵 ∑︁ 𝑖=1+1
𝐴 ∑︁
(𝑤𝑖 )
𝐴+𝐵 ∑︁
2
2
𝑤 ′𝑗 − 𝑤 𝑗
+
𝐴+𝐵 ∑︁
𝑖=1
𝑗=𝐴+1
𝑖=𝐴+1
𝐴 ∑︁
𝐴+𝐵 ∑︁
𝐴+𝐵 ∑︁
(𝑤𝑖 ) 2 𝐵
𝑖=1
≤𝐾
(𝑤𝑖 ) 2 |𝐹 (𝑤 ′ )𝑖 − 𝐹 (𝑤)𝑖 | 2
𝐾 ∑︁
2
𝑤 ′𝑗 − 𝑤 𝑗 +
𝑗=𝐴+1
𝑤 ′𝑗 − 𝑤 𝑗
(𝑤𝑖 )
2
𝐴 ∑︁
2
𝑤 ′𝑗 − 𝑤 𝑗
𝑗=1
(𝑤𝑖 ) 2𝐴
𝑖=𝐴+1
𝐴 ∑︁
𝑤 ′𝑗 − 𝑤 𝑗
𝑗=1
2
𝑗=1
≤𝐾
1 2 𝑤 ′𝑗 − 𝑤 𝑗 2 (𝑤 𝑗 ) 𝑗=1
𝐾 ∑︁
≤ 𝐾 ∥𝑤 ′ − 𝑤 ∥ 2𝑤 √ hence 𝐿 = 𝐾 As 𝑤 0 is the product of uniform policies, 2 ∥𝐹 (𝑤 0 ) ∥★,𝑤 =
𝐾 ∑︁ 𝑖=1
as 𝐴 ≥ 2 and 𝐵 ≥ 2
2
(𝑤𝑖0 ) 2 𝐹 (𝑤 0 )𝑖 ≤
𝐾 ∑︁ 𝑖=1
(𝑤𝑖0 ) 2 =
1 1 + ≤1 𝐴 𝐵
2
Optimal last-iterate convergence in matrix games
15
And, using the important sampling estimator, ∥ 𝐹ˆ (𝑤) ∥★,𝑤 =
𝐾 ∑︁
(𝑤𝑖 ) 2 𝐹ˆ (𝑤)𝑖
2
𝑖=1
=
𝐴 ∑︁
2 (𝑤𝑖 ) 2 ℓbmin,𝑖 +
𝑖=1
≤
𝐴+𝐵 ∑︁
(𝑤𝑖 ) 2 ℓbmax,𝑖
2
𝑖=𝐴+1
𝐴 ∑︁
I2{𝑖 } +
𝑖=1
𝐵 ∑︁
I2{𝑖 }
𝑖=𝐴+1
=2 ■ Lemma 7.3. Let 𝐾 = |𝐴| |𝑋 | + |𝐵| |𝑌 | be the total number of actions over √ both trees. The operator 𝐹 is linear and monotone. For any 𝑤 ∈ 𝑊 , it is also 𝐻 𝐾-Lipschitz with respect to the ∥·∥ 𝑤 and ∥·∥★,𝑤 norms: √ ∀(𝑤 1, 𝑤 2 ) ∈ 𝑊 2, ∥𝐹 (𝑤 1 ) − 𝐹 (𝑤 2 ) ∥★,𝑤 ≤ 𝐻 𝐾 ∥𝑤 1 − 𝑤 2 ∥ 𝑤 and the above unbiased estimate 𝐹ˆ satisfies: ∥ 𝐹ˆ (𝑤) ∥★,𝑤 ≤ 2𝐻 Proof. The proof is the same as above, with an extra sum on the depth ℎ.
B
■
Proof - Technical lemmas
We now use the notations, given 𝑊 = Δ A × Δ B for the affine subset of R𝐾≥0 with 𝐾 = 𝐴 + 𝐵, 𝑊0 for the linear component, and 𝐺 for its orthogonal. We will use the fact that, in the relative interior of 𝑊 , the dual cone of any point with respect to 𝑊 is always 𝐺. Lemma B.1. For all 𝑡 ≥ 𝑇0 , where
∥ 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 ≤ 𝜎 ′ √ 𝜎′ = 𝜎 + 𝜏0 𝐾
and 𝜎 is either 2 or 2𝐻
In particular, ∥𝑝 𝑡 ∥★,𝑤𝑡 ≤ 𝜎 ′ Proof. From the triangular inequality, ∥ 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 ≤ ∥ 𝐹ˆ (𝑤 𝑡 ) ∥★,𝑤𝑡 + 𝜏 𝑡 ∥∇Ψ(𝑤 𝑡 ) ∥★,𝑤𝑡 v u t 𝐾 𝑡 2 ∑︁ 𝑤 𝑖 ≤ 𝜎 + 𝜏𝑡 𝑡 𝑤 𝑖 𝑖=1 √ = 𝜎 + 𝜏𝑡 𝐾 and we conclude using the fact that (𝜏 𝑡 )𝑡 ≥𝑇0 is decreasing. The second inequality is a consequence of Jensen inequality and the unbiasedness of the estimator 𝐹ˆ. ■
Optimal last-iterate convergence in matrix games
16
Lemma B.2. Assume 𝑇0 ≥ 𝑒 4 , then (𝜏 𝑡 )𝑡 is decreasing and 𝜏 𝑡 − 𝜏 𝑡 +1 ≤
𝜏𝑡 𝜏0 ≤ 4(𝑡 + 𝑇0 ) 4(𝑡 + 𝑇0 )
Proof. Let ℎ be the function defined on R>0 1
log(𝑢) − 4 ℎ(𝑢) = 𝑢 ℎ is differentiable and satisfies
log(𝑢) − 5 𝑢 4 4 Both ℎ and its derivative are thus decreasing on (𝑒 4, +∞), and we obtain 5
ℎ ′ (𝑢) = 𝑢 − 4 −
𝜏 𝑡 − 𝜏 𝑡 +1 = 𝜏 |ℎ(𝑡 + 𝑇0 ) − ℎ(𝑡 + 𝑇0 + 1)| ∫ 𝑡 +𝑇0 +1 =𝜏 ℎ ′ (𝑢)𝑑𝑢 𝑡 +𝑇0
∫ 𝑡 +𝑇0 +1 ≤𝜏 𝑡 +𝑇0 ∫ 𝑡 +𝑇0 +1
≤𝜏 𝑡 +𝑇0
|ℎ ′ (𝑢)| 𝑑𝑢 log(𝑢) − 5 𝑢 4 𝑑𝑢 4
5 log(𝑡 + 𝑇0 ) (𝑡 + 𝑇0 ) − 4 𝑑𝑢 4 𝑡 +𝑇0 5 log(𝑡 + 𝑇0 ) =𝜏 (𝑡 + 𝑇0 ) − 4 4 𝜏𝑡 = 4(𝑡 + 𝑇0 ) 𝜏0 , ≤ 4(𝑡 + 𝑇0 )
∫ 𝑡 +𝑇0 +1
≤𝜏
where the last property follows the fact the (𝜏 𝑡 )𝑡 sequence is decreasing if 𝑇0 ≥ 𝑒 4 .
■
Lemma B.3. Assume 𝜎 ′𝜂 0 ≤ √1 , then for all 𝑡 ≥ 𝑇0 12
𝑤𝑖𝑡 ∀𝑖 ∈ [𝐾], ≤ 𝑤𝑖𝑡 +1 ≤ 2𝑤𝑖𝑡 2 Proof. Let
𝐷𝜙 (𝑥, 𝑦) := ℎ(𝑥/𝑦)
where ℎ(𝑟 ) = 𝑟 − log(𝑟 ) − 1
be the component-wise value of the Itakura-Saito divergence. It satisfies the following properties: Í𝐾 Í𝐾 ˜ = 𝑖=1 • 𝐷 Ψ (𝜇, 𝜇) 𝐷𝜙 (𝜇𝑖 , 𝜇˜𝑖 ) = 𝑖=1 ℎ(𝜇𝑖 /𝜇˜𝑖 ) by definition of the Itakura-Saito divergence 1 2 • ℎ(𝑟 ) ≤ (1 − 𝑟 ) for all 𝑟 ≥ √ as, from Taylor-Lagrange formula, there exists 𝑟˜ between 1 and 2 𝑟 such that ℎ(𝑟 ) = ℎ(1) + (𝑟 − 1)ℎ ′ (1) +
(𝑟 − 1) 2 ′′ (𝑟 − 1) 2 ℎ (𝑟˜) = ≤ (𝑟 − 1) 2 2 2𝑟˜2
• ℎ(𝑟 ) is non-negative for all 𝑟 > 0 • ℎ(𝑟 ) ≤ 1/6 implies 𝑟 ∈ (1/2, 2), as ℎ is a convex function with ℎ(1) = 0, ℎ(1/2) ≈ 0.193 and ℎ(2) ≈ 0.307.
Optimal last-iterate convergence in matrix games
17
Now, let 𝜇˜𝑡 +1 be the result of an unrestricted mirror step at time 𝑡, defined as the only vector of
R𝐾 that satisfies
∇Ψ( 𝜇˜𝑡 +1 ) = ∇Ψ(𝜇𝑡 ) − 𝜂 𝑡 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 )
This implies
𝜇𝑡 +1 = arg min 𝐷 Ψ (𝜇, 𝜇˜𝑡 +1 ) . 𝜇 ∈𝑊
As such, for all 𝑖 ∈ [𝐾], 𝜇𝑖𝑡
= 1 − 𝜂 𝑡 𝑤𝑖𝑡 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 )𝑖 𝑡 +1
𝜇˜𝑖
𝜇𝑖𝑡
and in particular,
𝜇˜𝑖𝑡 +1
1 1 ≥ 1 − 𝜎𝜂 𝑡 ≥ 1 − √ ≥ √ . 12 2
Then, using the generalized Pythagorean theorem for Bregman divergence, and the previous properties: 𝐷 Ψ (𝜇𝑡 , 𝜇𝑡 +1 ) ≤ 𝐷 Ψ (𝜇𝑡 , 𝜇˜𝑡 +1 ) − 𝐷 Ψ (𝜇𝑡 +1, 𝜇˜𝑡 +1 ) ≤ 𝐷 Ψ (𝜇𝑡 , 𝜇˜𝑡 +1 ) 𝐾 ∑︁
=
ℎ(𝜇𝑖𝑡 /𝜇˜𝑖𝑡 +1 )
𝑖=1 𝐾 ∑︁
≤
𝜇𝑖𝑡
−1
2
𝜇˜𝑖𝑡 +1 𝑖=1 𝐾 2 ∑︁ = 𝜂 𝑡 𝑤𝑖𝑡 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 )𝑖 𝑖=1 ≤ (𝜂 𝑡 𝜎 ′ ) 2 ≤ (𝜂𝑇0 𝜎 ′ ) 2 ≤
1 12
as (𝜂 𝑡 )𝑡 ≥𝑇0 is decreasing. In particular, for all 𝑖 ∈ [𝐾], 𝑡 𝜇𝑖 1 ≤ ℎ 𝑡 +1 12 𝜇𝑖 and we obtain the lemma. ■ For any 𝑡 ≥ 𝑇0 , we define 𝑝 𝑡 and 𝑔𝑡 to be respectively: 𝑔𝑡 = arg min ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) − 𝑔∥★,𝑤𝑡
and 𝑝 𝑡 = 𝐹𝜏 𝑡 (𝑤 𝑡 ) − 𝑔𝑡
𝑔∈𝐺
The same is done with 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ), with 𝑝ˆ𝑡 and 𝑔ˆ𝑡 : 𝑔ˆ𝑡 = arg min ∥ 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) − 𝑔∥★,𝑤𝑡
and 𝑝ˆ𝑡 = 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) − 𝑔𝑡
𝑔∈𝐺
Lemma B.4. For any 𝑤 ∈ 𝑊 and 𝜉 ∈ R𝐾 , we have the equivalence: ∇2 Ψ(𝑤) −1 · 𝜉 ∈ 𝑊0
⇐⇒
0 = arg min ∥𝜉 − 𝑔∥★,𝑤 𝑔∈𝐺
and, for all 𝑤 0 ∈ 𝑊0 𝑤 0 ∈ 𝑊0
⇐⇒
0 = arg min ∥𝑤 0 − ∇2 Ψ(𝑤) −1 · 𝑔∥ 𝑤 𝑔∈𝐺
Proof. Pythagorean with 𝑊0 ⊥ 𝐺 In particular, this implies that ∇2 Ψ(𝑤 𝑡 ) −1 · 𝑝ˆ𝑡 ∈ 𝑊0 and ∇2 Ψ(𝑤 𝑡 ) −1 · 𝑝 𝑡 ∈ 𝑊0 .
■
Optimal last-iterate convergence in matrix games
C
18
Proof - First order approximations of the next iterate
The following assumption implies that the learning rate 𝜂 is small enough for the second-order terms to be negligible compared to the first-order terms. Assumption C.1. 32𝜎 ′𝜂 0 ≤ 1 The idea behind the next lemma is that ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 and ∇2Ψ(𝑤 𝑡 ) −1𝑝 𝑡 multiplied by the learning rate 𝜂 𝑡 respectively approximate 𝑤 𝑡 − 𝑤 𝑡 +1 and 𝑤 𝑡 − E𝑡 𝑤 𝑡 +1 up to some second order terms. For inequality (1), we use the previous assumption to upper-bound this second order term by 𝜎 ′𝜂 𝑡 . Proposition C.2. For all 𝑡 ≥ 𝑇0 , the following inequalities hold: ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 ≤ 2𝜎 ′𝜂 𝑡
(1)
∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ∥ 𝑤𝑡 ≤ 32(𝜎 ′𝜂 𝑡 ) 2
(2)
And, from the triangle inequality, 2 ∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 ≤ 𝜂 𝑡 ∥𝑝 𝑡 ∥★,𝑤𝑡 + 32 𝜎 ′𝜂 𝑡 .
(3)
Proof. We start by showing ∥𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 ∥ 𝑤𝑡 ≤ 32(𝜎 ′𝜂 𝑡 ) 2 , and the three inequalities will follow. We first notice, from Lemma B.4, that ∥𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 ∥ 𝑤𝑡 ≤ ∥𝑤 𝑡 +1 − 𝑤 𝑡 + ∇2 (𝑤 𝑡 ) −1 ∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥ 𝑤𝑡 as 𝑝ˆ𝑡 − ∇Ψ(𝑤 𝑡 ) + ∇Ψ(𝑤 𝑡 +1 ) ∈ 𝐺 Now, let 𝐽𝑖𝑡 be the interval of values between 𝑤𝑖𝑡 and 𝑤𝑖𝑡 +1 . From Taylor-Lagrange inequality applied to 𝑢 → − 1/𝑢, and the two points 1/𝑤𝑖𝑡 +1 and 1/𝑤𝑖𝑡 we have for all 𝑖 ∈ [𝐾], 2 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 + (𝑤𝑖𝑡 ) 2 1/𝑤𝑖𝑡 +1 − 1/𝑤𝑖𝑡 = (𝑤˜ 𝑖𝑡 ) 3 1/𝑤𝑖𝑡 +1 − 1/𝑤𝑖𝑡 for some 𝑤˜ 𝑖𝑡 ∈ 𝐽𝑖𝑡 . Dividing the first term by 𝑤˜ 𝑖𝑡 and summing over 𝑖, we obtain, by definition of Ψ: 2 ∥𝑤 𝑡 +1 − 𝑤 𝑡 + ∇2 (𝑤 𝑡 ) −1 ∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥ 𝑤˜ 𝑡 = ∥∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥★, 𝑤˜ 𝑡 Then, from Lemma B.3, as 𝑤˜ 𝑖𝑡 ≥ 𝑤𝑖𝑡 /2 for all 𝑖 ∈ [𝐾] we obtain 2 ∥𝑤 𝑡 +1 − 𝑤 𝑡 + ∇2 (𝑤 𝑡 ) −1 ∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥ 𝑤𝑡 ≤ 2∥∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥★, 𝑤˜ 𝑡 and combined with the first inequality, 2 ∥𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 ∥ 𝑤𝑡 ≤ 2∥∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥★, 𝑤˜ 𝑡
(★)
Now, for all 𝑖, we notice the existence of some 𝑤 𝑖𝑡 ∈ 𝐽𝑖𝑡 , again from Taylor Lagrange, such that, for all 𝑖 ∈ [𝐾]: 2 1/𝑤𝑖𝑡 +1 − 1/𝑤𝑖𝑡 = 1/ 𝑤 𝑖𝑡 𝑤𝑖𝑡 − 𝑤𝑖𝑡 +1 hence
∇2 Ψ(𝑤 𝑡 ) −1 ∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ) = 𝑤 𝑡 − 𝑤 𝑡 +1 ∈ 𝑊0
which gives, applying Lemma B.4, 2 2 𝑡 𝑡 +1 ∥∇Ψ(𝑤 𝑡 ) + ∇Ψ(𝑤 𝑡 +1 ) ∥★,𝑤 ) − 𝑔∥★,𝑤 𝑡 = min ∥∇Ψ(𝑤 ) + ∇Ψ(𝑤 𝑡 . 𝑔∈𝐺
Optimal last-iterate convergence in matrix games
19
Combining this with Lemma B.3, we obtain 2 𝑡 𝑡 +1 2 ∥∇Ψ(𝑤 𝑡 ) − ∇Ψ(𝑤 𝑡 +1 ) ∥★, ) ∥★,𝑤𝑡 𝑤˜ 𝑡 ≤ 4∥∇Ψ(𝑤 ) − ∇Ψ(𝑤 2 ≤ 4∥𝜂 𝑡 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤 𝑡 2 ′ 𝑡 2 ≤ 16∥𝜂 𝑡 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤 𝑡 = 16 𝜎 𝜂
which yields with (★), ∥𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 ∥ 𝑤𝑡 ≤ 32(𝜎 ′𝜂 𝑡 ) 2 (2) then follows using the convexity of the norm and Jensen inequality, as E𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 = ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 . (1) and (3) follows from the triangle inequality as ∥∇2 Ψ(𝑤 𝑡 ) −1𝑝ˆ𝑡 ∥ 𝑤𝑡 = ∥𝑝ˆ𝑡 ∥★,𝑤𝑡 ≤ ∥ 𝐹ˆ𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 = 𝜎 ′ and
∥∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ∥★,𝑤𝑡 = ∥𝑝 𝑡 ∥★,𝑤𝑡 .
where we also used 32𝜎 ′𝜂 0 ≤ 1 from Assumption C.1 for (1).
■
Proposition C.3. For any 𝑡 ≥ 𝑇0 and 𝜉, 𝜉 ′ ∈ R𝐾 , the following inequality holds: ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 +1 − ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 ≤ 8𝜎 ′𝜂 𝑡 ∥𝜉 ∥★,𝑤𝑡 ∥𝜉 ′ ∥★,𝑤𝑡 . Furthermore, if 𝜉 and 𝜉 ′ are measurable with respect to F 𝑡 , 2 E𝑡 ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 +1 − ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 ≤ ∥𝑝 𝑡 ∥★,𝑤𝑡 𝜂 𝑡 + 36 𝜎 ′𝜂 𝑡 ∥𝜉 ∥★,𝑤𝑡 ∥𝜉 ′ ∥★,𝑤𝑡 . To prove this proposition, we start with the following lemma that characterizes the variation of the squared coefficients that appear in the regularization. Lemma C.4. For all 𝑖 ∈ [𝐾] and 𝑡 ≥ 𝑇0 : 𝑤𝑖𝑡 +1 and
h E𝑡
𝑤𝑖𝑡 +1
2i
− 𝑤𝑖𝑡
2
2
− 𝑤𝑖𝑡
≤ 𝑤𝑖𝑡
2
2
≤ 4 𝑤𝑖𝑡
2
∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡
2∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 + E𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 2𝑤𝑡
Proof. For all 𝑎, 𝑏 ∈ R, the following equality holds: 𝑏 2 − 𝑎 2 = 2𝑎(𝑏 − 𝑎) + (𝑏 − 𝑎) 2 . From Lemma B.3, we have
𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 ≤ 2, 𝑤𝑖𝑡
Optimal last-iterate convergence in matrix games
20
and with 𝑎 = 𝑤𝑖𝑡 and 𝑏 = 𝑤𝑖𝑡 +1 , the first equality yields 2 2 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 = 2𝑤𝑖𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 + (𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 ) 2 ≤ 2𝑤𝑖𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 + 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 =
2 𝑤𝑖𝑡
2
𝑤 𝑡 +1 − 𝑤 𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 2 𝑖 𝑡 𝑖 + 𝑖 𝑡 𝑖 𝑤𝑖 𝑤𝑖
2
!
2 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 𝑤𝑖𝑡 2 ≤ 4 𝑤𝑖𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 . ≤ 4 𝑤𝑖𝑡
For the second inequality, the idea is the same, but the second order term cannot be upper-bounded by the first: h 2i 2 E𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 = E𝑡 2𝑤𝑖𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 + (𝑤𝑖𝑡 − 𝑤𝑖𝑡 ) 2 h i 2 ≤ 2𝑤𝑖𝑡 E𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 + E𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 #! " 𝑡 +1 𝑡 𝑡 +1 − 𝑤 𝑡 2 E 𝑤 − 𝑤 𝑤 𝑡 2 𝑖 𝑖 𝑖 𝑖 + E𝑡 = 𝑤𝑖𝑡 2 𝑤𝑖𝑡 𝑤𝑖𝑡 2 ≤ 𝑤𝑖𝑡 2∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 + E𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 2𝑤𝑡 . ■ Now, going to the proof of proposition C.3. Proof. With the first inequality of Lemma C.4, ′
′
⟨𝜉, 𝜉 ⟩★,𝑤𝑡 +1 − ⟨𝜉, 𝜉 ⟩★,𝑤𝑡 =
𝐾 ∑︁
𝜉𝑖 𝜉𝑖′
h
𝑤𝑖𝑡 +1
2
− 𝑤𝑖𝑡
2i
𝑤𝑖𝑡 +1
2
− 𝑤𝑖𝑡
2
𝑖=1
≤
𝐾 ∑︁
𝜉𝑖 𝜉𝑖′
𝑖=1
≤ 4∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡
𝑘 ∑︁
𝜉𝑖 𝜉𝑖′ 𝑤𝑖𝑡
2
𝑖=1
≤ 4∥𝑤
𝑡 +1
− 𝑤 ∥ 𝑤𝑡 ∥𝜉 ∥★,𝑤𝑡 ∥𝜉 ′ ∥★,𝑤𝑡 𝑡
using Cauchy-Schwarz for the last inequality. The bound follows from (1) of Proposition C.2 as ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 ≤ 2𝜎 ′𝜂 𝑡 For the second inequality, with the second inequality of Lemma C.4 and Cauchy-Schwarz: E𝑡 ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 +1 − ⟨𝜉, 𝜉 ′ ⟩★,𝑤𝑡 𝐾 h h ∑︁ 2i 2i = 𝜉𝑖 𝜉𝑖′ E𝑡 𝑤𝑖𝑡 +1 − 𝑤𝑖𝑡 𝑖=1
≤
𝐾 ∑︁
𝜉𝑖 𝜉𝑖′ E𝑡
h
𝑤𝑖𝑡 +1
2i
− 𝑤𝑖𝑡
2
𝑖=1 𝐾 𝑡 +1 𝑡 +1 ∑︁ 2 𝑡 𝑡 2 ≤ 2∥E𝑡 𝑤𝑖 − 𝑤 ∥ 𝑤𝑡 + E𝑡 ∥𝑤 − 𝑤 ∥ 𝑤𝑡 𝜉𝑖 𝜉𝑖′ 𝑤𝑖𝑡 𝑖=1
= 2∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 + E𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 2𝑤𝑡 ∥𝜉 ∥★,𝑤𝑡 ∥𝜉 ′ ∥★,𝑤𝑡
Optimal last-iterate convergence in matrix games
21
and we conclude using (3) of Proposition C.2, 2 ∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 ≤ ∥𝜂 𝑡 𝑝 𝑡 ∥★,𝑤𝑡 + 32 𝜎 ′𝜂 𝑡 and with (1) again:
2 E𝑡 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 2𝑤𝑡 ≤ 2𝜎 ′𝜂 𝑡 ≤ 4(𝜎 ′𝜂 𝑡 ) 2 ■
Proposition C.5. ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 +1 ≤ 𝜌 (𝑡 + 𝑇0 ) −3/4 where
𝜏0 √ 𝜌 = 𝜎 ′𝜂 4𝐿 + 2𝜏 0 + 𝐾 4
In particular, ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 ≤ 2𝜌 (𝑡 + 𝑇0 ) −3/4 Proof. We first notice that for any 𝑤, 𝑤 ′ ∈ 𝑊 2 ∥∇Ψ(𝑤 ′ ) − ∇Ψ(𝑤) ∥★,𝑤 ′ =
2 ∑︁ 𝐾 2 1 1 1 (𝑤𝑖′ ) 2 − ′ + 𝑤𝑖′ − 𝑤𝑖 = ∥𝑤 ′ − 𝑤 ∥ 𝑤 = 2 𝑤𝑖 𝑤𝑖 (𝑤𝑖 ) 𝑖=1 𝑖=1
𝐾 ∑︁
Now, ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 +1 ≤ ∥𝐹 (𝑤 𝑡 +1 − 𝐹 (𝑤 𝑡 ) ∥★,𝑤𝑡 + 𝜏 𝑡 ∥∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ) ∥★,𝑤𝑡 +1 + 𝜏 𝑡 − 𝜏 𝑡 +1 ∥∇Ψ(𝑤 𝑡 +1 ) ∥★,𝑤𝑡 +1 v u t 𝐾 𝑡 +1 2 ∑︁ 𝑤 𝑖 𝑡 +1 𝑡 𝑡 𝑡 +1 𝑡 𝑡 𝑡 +1 ≤ 𝐿∥𝑤 − 𝑤 ∥ 𝑤𝑡 +1 + 𝜏 ∥𝑤 − 𝑤 ∥ 𝑤𝑡 + 𝜏 − 𝜏 𝑡 +1 𝑤 𝑖 𝑖=1 √ ≤ 2𝐿 + 𝜏 0 ∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 + 𝜏 𝑡 − 𝜏 𝑡 +1 𝐾 √ 𝜏0 ≤ 2𝜎 ′𝜂 𝑡 2𝐿 + 𝜏 0 + 𝐾 4(𝑡 + 𝑇0 ) 3 3 𝜏0 √ 𝐾 (𝑡 + 𝑇0 ) − 4 ≤ 2𝜎 ′𝜂 2𝐿 + 𝜏 0 (𝑡 + 𝑇0 ) − 4 + 4
where we used, in this order: • The triangle inequality • Lemma 6.2 and the previous property • Lemma B.3 and the fact that the sequence (𝜏 𝑡 )𝑡 is decreasing. • Lemma C.2 and Lemma B.2 • The definition of 𝜂 𝑡 The second inequality follows from Lemma B.3. ■
D
Proof - Recursive bound
Let 𝑑 = (𝑑 𝑡 )𝑡 ≥1 be the sequence defined by 2 𝑑 𝑡 := 𝑑𝜏 𝑡 (𝑤 𝑡 ) = ∥𝑝 𝑡 ∥★,𝑤 𝑡
Remember that ∥𝑝 𝑡 ∥★,𝑤𝑡 = min ∥𝐹𝜏𝑡 (𝑤 𝑡 ) − 𝑔∥★,𝑤𝑡 = ∥𝐹𝜏𝑡 (𝑤 𝑡 ) − 𝑔𝑡 ∥★,𝑤𝑡 𝑔∈𝐺
Optimal last-iterate convergence in matrix games
22
2 2 2 𝐾 𝑡 Then, as ∥𝑥 + 𝑦 ∥★,𝑤 𝑡 +1 = ∥𝑥 ∥ ★,𝑤 𝑡 +1 + 2 ⟨𝑥, 𝑦⟩★,𝑤 𝑡 +1 + ∥𝑦 ∥ ★,𝑤 𝑡 +1 for any 𝑥, 𝑦 ∈ R , with 𝑥 = 𝑝 and 𝑦 = 𝐹𝜏 𝑡 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) 2 𝑡 𝑑 𝑡 +1 − 𝑑 𝑡 ≤ ∥𝐹𝜏𝑡 +1 (𝑤 𝑡 +1 ) − 𝑔𝑡 ∥★,𝑤 𝑡 +1 − ∥𝑝 ∥ ★,𝑤 𝑡 2 𝑡 2 𝑡 +1 = ∥𝑝 𝑡 ∥★,𝑤 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 +1 𝑡 +1 − ∥𝑝 ∥ ★,𝑤 𝑡 + 2 𝐹𝜏 𝑡 +1 (𝑤 2 + ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤 𝑡 +1
Let
2 𝑡 2 Δ𝑡1 = ∥𝑝 𝑡 ∥★,𝑤 𝑡 +1 − ∥𝑝 ∥ ★,𝑤 𝑡
𝛼 𝑡 = 2 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 Δ𝑡2 = 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 +1 − 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 2 𝑉 𝑡 = ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤 𝑡 +1
Then, we can separate the bound between the terms: 𝑑 𝑡 +1 − 𝑑 𝑡 ≤ Δ𝑡1 + 𝛼 𝑡 + Δ𝑡2 + 𝑉 𝑡 Lemma D.1. For any 𝑡 ≥ 𝑇0 , √ Δ𝑡1 − E𝑡 Δ𝑡1 ≤ 16(𝜎 ′ ) 2𝜂 𝑡 𝑑 𝑡 and
√ 3 𝛼 𝑡 − E𝑡 𝛼 𝑡 ≤ 4𝜌 𝑑 𝑡 (𝑡 + 𝑇0 ) − 4
Proof. We use Lemma C.3 for the first term: 2 𝑡 𝑡 2 Δ𝑡1 = ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) − 𝑔𝑡 ∥★,𝑤 𝑡 +1 − ∥𝐹𝜏 𝑡 (𝑤 ) − 𝑔 ∥ ★,𝑤 𝑡 2 ≤ 8𝜎 ′𝜂 𝑡 ∥𝐹𝜏 𝑡 (𝑤 𝑡 ) − 𝑔𝑡 ∥★,𝑤 𝑡 √ ≤ 8(𝜎 ′ ) 2𝜂 𝑡 𝑑 𝑡 .
For 𝛼 𝑡 , we obtain with Cauchy-Schwarz and Proposition C.5: 𝛼 𝑡 = 2 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 ≤ 2∥𝑝 𝑡 ∥★,𝑤𝑡 ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 √ 3 = 2𝜌 𝑑 𝑡 (𝑡 + 𝑇0 ) − 4 The two inequalities are then obtained using the fact that, for any random variable 𝑋 , |𝑋 | ≤ 𝑐
a.s. =⇒ |𝑋 − E𝑡 [𝑋 ] | ≤ 2𝑐
a.s. . ■
Lemma D.2.
E𝑡 Δ𝑡1 ≤ 𝜂 𝑡 (𝑑 𝑡 ) 3 + 36(𝜎 ′ ) 4 (𝜂 𝑡 ) 2
Optimal last-iterate convergence in matrix games
23
Proof. We use the second inequality of Lemma C.3 and obtain: h i 2 𝑡 2 E𝑡 Δ𝑡1 = E𝑡 ∥𝑝 𝑡 ∥★,𝑤 𝑡 +1 − ∥𝑝 ∥ ★,𝑤 𝑡 2 𝑡 𝑡 ′ 𝑡 2 ≤ ∥𝑝 𝑡 ∥★,𝑤 𝑡 𝜂 ∥𝑝 ∥ ★,𝑤 𝑡 + 36 𝜎 𝜂 √ 2 = 𝑑 𝑡 𝜂 𝑡 𝑑 𝑡 + 36 𝜎 ′𝜂 𝑡 ≤ 𝜂 𝑡 (𝑑 𝑡 ) 3 + 36(𝜎 ′ ) 4 (𝜂 𝑡 ) 2 ■ Lemma D.3.
√ 𝜏𝑡 E𝑡 𝛼 𝑡 ≤ −2𝜏 𝑡 +1𝜂 𝑡 𝑑 𝑡 + (𝑡 + 𝑇0 ) 𝐾𝑑 𝑡 + 128𝐿(𝜂 𝑡 ) 2 (𝜎 ′ ) 3 2
Proof. We first divide E𝑡 𝛼 𝑡 into several terms: E𝑡 𝛼 𝑡 = 2 E𝑡 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 = 2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 + 2𝜏 𝑡 +1 E𝑡 ∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 + 2(𝜏 𝑡 − 𝜏 𝑡 +1 ) ∇Ψ(𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 First term: We start by multiplying this first term by 𝜂 𝑡 . 2𝜂 𝑡 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 = −2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) , ∇2 Ψ(𝑤 𝑡 )E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ★,𝑤𝑡 + 2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) , ∇2 Ψ(𝑤 𝑡 )E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 𝑝 𝑡 ★,𝑤𝑡 = −2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) , E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) , E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ≤ 0 + 2∥𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) ∥★,𝑤𝑡 ∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ∥ 𝑤𝑡 ≤ 2𝐿∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 ∥E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 + 𝜂 𝑡 ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ∥ 𝑤𝑡 3 ≤ 128𝐿 𝜎 ′𝜂 𝑡 Where we used in this order: • The fact that 𝐹 is a linear monotone operator, hence E𝑡 𝐹 𝑤 𝑡 +1 − 𝐹 𝑤 𝑡 , E𝑡 𝑤 𝑡 +1 − 𝑤 𝑡 ≥ 0 • Cauchy-Schwarz as ⟨𝑥, 𝑦⟩ = ∇2 Ψ(𝑤) 1/2𝑥, ∇2 Ψ(𝑤) −1/2𝑦 ≤ ∥𝑥 ∥ 𝑤 ∥𝑦 ∥★,𝑤 • Assumption 6.2: ∥𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ) ∥★,𝑤𝑡 ≤ 𝐿∥𝑤 𝑡 +1 − 𝑤 𝑡 ∥ 𝑤𝑡 • Inequalities (2) and (1) of Lemma C.2 Dividing by 𝜂 𝑡 , we then obtain 2 E𝑡 𝐹 (𝑤 𝑡 +1 ) − 𝐹 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 ≤ 128𝐿(𝜂 𝑡 ) 2 (𝜎 ′ ) 3 Second term: We use the fact that ∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ) + 𝜂 𝑡 𝑝ˆ𝑡 ∈ 𝐺
Optimal last-iterate convergence in matrix games
24
and hence, taking the expectation with respect to F 𝑡 , E𝑡 ∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ) + 𝜂 𝑡 𝑝 𝑡 ∈ 𝐺 . From Lemma B.4, as ∇2 Ψ(𝑤 𝑡 ) −1𝑝 𝑡 ∈ 𝑊0 this yields 2𝜏 𝑡 +1 E𝑡 ∇Ψ(𝑤 𝑡 +1 ) − ∇Ψ(𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 = −2𝜏 𝑡 +1 𝜂 𝑡 𝑝 𝑡 , 𝑝 𝑡 ★,𝑤𝑡 = −2𝜏 𝑡 +1𝜂 𝑡 𝑑 𝑡 Third term: From Cauchy-Schwarz again, 2(𝜏 𝑡 − 𝜏 𝑡 +1 ) ∇Ψ(𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 ≤ 2(𝜏 𝑡 − 𝜏 𝑡 +1 ) ∥∇Ψ(𝑤 𝑡 ) ∥★,𝑤𝑡 ∥𝑝 𝑡 ∥★,𝑤𝑡 √ = 2(𝜏 𝑡 − 𝜏 𝑡 +1 ) 𝐾𝑑 𝑡 √ 𝜏𝑡 ≤ (𝑡 + 𝑇0 ) 𝐾𝑑 𝑡 2 where we used Lemma B.2 for the last inequality. Lemma D.4.
■ 3
Δ𝑡2 ≤ 8𝜌 (𝜎 ′ ) 2𝜂 𝑡 (𝑡 + 𝑇0 ) − 4 3
𝑉 𝑡 ≤ 𝜌 2 (𝑡 + 𝑇0 ) − 2 Proof. From Proposition C.3 and Proposition C.5, we obtain Δ𝑡2 = 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 +1 − 𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ), 𝑝 𝑡 ★,𝑤𝑡 ≤ 4𝜎 ′𝜂 𝑡 ∥𝐹𝜏 𝑡 +1 (𝑤 𝑡 +1 ) − 𝐹𝜏 𝑡 (𝑤 𝑡 ) ∥★,𝑤𝑡 ∥𝑝 𝑡 ∥★,𝑤𝑡 √ 3 ≤ 8𝜎 ′𝜂 𝑡 𝜌 𝑑 𝑡 𝜌 (𝑡 + 𝑇0 ) − 4 3
≤ 8𝜌 (𝜎 ′ ) 2𝜂 𝑡 (𝑡 + 𝑇0 ) − 4 The second inequality directly follows from Proposition C.5 .
E
■
Proof - Final bound
Remember that
𝑑 𝑡 +1 − 𝑑 𝑡 ≤ Δ𝑡1 + 𝛼 𝑡 + Δ𝑡2 + 𝑉 𝑡
In this section, we use 𝑠 = 𝑡 + 𝑇0 Let, for all 𝑡 and associated 𝑠, 𝑈𝑡 =
𝑑𝑡 , log(𝑠/𝛿).𝜏 2
𝑑𝑡 1 𝑏 𝑡 +1 = E𝑡 𝛼 𝑡 + Δ𝑡1 + ess sup Δ𝑡2 + 𝑉 𝑡 F 𝑡 + 𝑠 log(𝑠/𝛿).𝜏 2 and 𝑊 𝑡 +1 = 𝛼 𝑡 + Δ𝑡1 − E𝑡 𝛼 𝑡 + Δ𝑡1
1 log(𝑠/𝛿).𝜏 2
From dividing (4) by log(𝑠𝛿).𝜏 2 , on both side, we obtain 𝑈 𝑡 +1 ≤
𝑑 𝑡 +1 log(𝑠/𝛿).𝜏 2
1 ≤ 𝑑 𝑡 + 𝛼 + Δ𝑡1 + Δ𝑡2 + 𝑉 𝑡 log(𝑠/𝛿).𝜏 2 1 ≤ 1 − 𝑈 𝑡 + 𝑏 𝑡 +1 + 𝑊 𝑠+1 𝑠
(4)
Optimal last-iterate convergence in matrix games
25
We need to show that 𝑈 𝑇0 , 𝑏, and 𝑊 satisfy the conditions of Lemma 6.5 for correctly chosen parameters. For this purpose, we remind the following assumption: Assumption 5.1. We assume that the parameters 𝜂, 𝜏 and 𝑇0 of the algorithm satisfy • 𝜂𝜏1 = 𝑜 (1) • 𝜂 = 𝑜 (1) 𝑇0 2 4 • 𝜂𝜏 ≤ log(𝑇 4 and 𝑇0 ≤ log(1/𝛿) 𝜏 0) Given the first two parameters 𝜂 and 𝜏, the existence of some 𝑇0 that satisfies the third assumption is always guaranteed. The third assumption is used to ensure that 𝜂 0𝜏 0 ≤ 1 (for the algorithm to be well defined), and log(𝑇 ) 𝑈 𝑇0 ≤ √𝑇 0 for the starting condition of Lemma 6.5 to be satisfied. 0
Lemma E.1. In this context, at each iteration 𝑡 ≤ 𝑇1 , the 𝑏 sequence satisfies: 𝑏 𝑡 +1 ≤ (𝑠 + 1) −3/2 Proof. From Lemma D.3, 1 E𝑡 𝛼 𝑡 2 log(𝑠/𝛿).𝜏 1 𝜏𝑡 √ 𝑡 𝑡 2 ′ 3 𝑡 +1 𝑡 𝑡 𝐾𝑑 + 128𝐿(𝜂 ) (𝜎 ) = −2𝜏 𝜂 𝑑 + 2𝑠 log(𝑠/𝛿).𝜏 2 Then, decomposing each term • As 𝜂𝜏1 = 𝑜 (1), −2𝜏
1 1 5 𝑡 𝑡 𝑡 𝑑𝑡 𝜂𝑑 ≤− 𝜏 𝜂𝑑 + log(𝑠/𝛿) 4 𝑠 log(𝑠/𝛿)
𝑡 +1 𝑡 𝑡
𝑥 • From the inequality, for any 𝑥, 𝑦 > 0, 𝑥 ≤ 2 + 2𝑦 𝑥𝑦
𝜂𝑡 𝜏 𝑡 𝑑 𝑡 1 1 𝜏𝑡 𝐾 𝜏𝑡 √ 𝑡 ≤ + 𝐾𝑑 2 2 𝑡 2𝑠 log(𝑠/𝛿).𝜏 4 log(𝑠/𝛿).𝜏 𝑠𝜂 log(𝑠/𝛿).𝜏 2 𝜂𝑡 𝜏 𝑡 𝑑 𝑡 𝑠 −3/2 1 ≤ + 4 log(𝑠/𝛿).𝜏 2 4 where we also used 𝜂𝜏1 = 𝑜 (1) for the last inequality • Using 𝜂 = 𝑜 (1), 𝜏1 = 𝑜 (1) and log(𝑠/𝛿), 128𝐿(𝜂 𝑡 ) 2 (𝜎 ′ ) 3
1 (𝑠 + 1) −3/2 ≤ log(𝑠/𝛿)𝜏 2 4
Then, from Lemma D.2: 𝑡 1 1 E Δ1 ≤ 𝜂 𝑡 (𝑑 𝑡 ) 3 + 36(𝜎 ′ ) 4 (𝜂 𝑡 ) 2 𝑡 log(𝑠/𝛿).𝜏 2 log(𝑠/𝛿).𝜏 2 Again, by considering each term, • Using the recursive assumption 1 1 𝜂 𝑡 (𝑑 𝑡 ) 3 ≤ 𝜂𝑡 𝑑 𝑡 ≤ 𝜂𝑡 𝜏 𝑡 𝑑 𝑡 2 log(𝑠/𝛿).𝜏 log(𝑠/𝛿).𝜏 2
Optimal last-iterate convergence in matrix games
26
• As 𝜂 = 𝑜 (1) and 𝜏1 = 𝑜 (1) again, 36(𝜎 ′ ) 4 (𝜂 𝑡 ) 2
1 (𝑠 + 1) −3/2 ≤ log(𝑠/𝛿).𝜏 2 4
Finally, from Lemma D.4 • As 𝜂 = 𝑜 (1) and 𝜏1 = 𝑜 (1) (𝑠 + 1) −3/2 1 1 𝑡 ′ 2 𝑡 − 34 Δ ≤ 8𝜌 (𝜎 ) 𝜂 𝑠 ≤ log(𝑠/𝛿).𝜏 2 2 log(𝑠/𝛿).𝜏 2 4 • As 𝜏1 = 𝑜 (1) and log(𝑠/𝛿) > 1, 1 1 (𝑠 + 1) −3/2 𝑡 2 − 32 𝑉 ≤ 𝜌 𝑠 ≤ log(𝑠/𝛿).𝜏 2 log(𝑠/𝛿).𝜏 2 4 Summing all these terms, we obtain that the 𝑑 𝑡 terms compensate with each other, implying 𝑏 𝑡 +1 ≤ (𝑠 + 1) −3/2 . ■ Lemma E.2. Under this setting, at each iteration 𝑡, the 𝑊 sequence is bounded by 𝑊
𝑡 +1 2
3
(𝑠 + 1) − 2 𝑡 ≤ 𝑈 2
Proof. From the first inequality of Lemma D.1 √ 1 1 Δ𝑡1 − E𝑡 Δ𝑡1 ≤ 16(𝜎 ′ ) 2𝜂 𝑡 𝑑 𝑡 2 log(𝑠/𝛿).𝜏 log(𝑠/𝛿).𝜏 2 (𝑠 + 1) −3/4 √ 𝑡 ≤ 𝑈 4 where we used 𝜂 = 𝑜 (1), 𝜏 > 1 and the definition of 𝑈 𝑡 . Similarly, with the second equality of the lemma, we also get √ 3 1 1 𝛼 𝑡 − E𝑡 𝛼 𝑡 ≤ 4𝜌 𝑑 𝑡 𝑠 − 4 2 log(𝑠/𝛿).𝜏 log(𝑠/𝛿).𝜏 2 √ 𝑠 −3/4 ≤ 4𝜌 𝑈 𝑡 𝜏 (𝑠 + 1) −3/4 √ 𝑡 ≤ 𝑈 . 4 Summing the two inequalities above and squaring yields the result.
■
These two lemmas are finally used for the proof of the main theorem Theorem 5.2. If both players run Algorithm 1 with parameters satisfying Assumption 5.1, then for any confidence 𝛿 > 0, with probability at least 1 − 𝛿: 𝑡 + 𝑇0 𝑡 EG(𝑤 ) ≤ 2𝐾𝜏 log (𝑡 + 𝑇0 ) −1/4 . 𝛿 at every iteration 𝑡.
Optimal last-iterate convergence in matrix games
27
Proof. Using the two lemmas above along with the parameters defined by Assumption 5.1, we obtain that the sequence 𝑈 satisfies the assumptions of Lemma 6.5. Hence, at all iterations 𝑡, √ 𝑑𝑡 ≤ 𝑠 log(𝑠/𝛿) 2 log(𝑠/𝛿)𝜏 Equivalent to
𝑑 𝑡 ≤ (𝜏 𝑡 ) 2
This lets us apply Lemma 6.4, which yields EG(𝑤 𝑡 ) ≤ 2𝜏 𝑡 𝐾 . ■ Theorem 7.4. If both players run Algorithm 2 with parameters satisfying Assumption 5.1, then for any confidence 𝛿 > 0, with probability at least 1 − 𝛿: 𝑡 + 𝑇0 𝑡 (𝑡 + 𝑇0 ) −1/4 . EG(𝑤 ) ≤ 2𝐾𝜏 log 𝛿 at every iteration 𝑡. Proof. The proof is the same as above.
■