The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We thank reviewer TkNJ for taking the time to review our article and for the clarity suggestion. We address the concerns below.

Nevertheless, I think there is no fundamental difference between the definitions of “output convergence” and the average-iterate convergence.

We preferred to state the results and Lemma 6.1 under the assumption that $\mathcal{A}$ has a convergence of its output, whether it comes from averaging (as in the EXP3-IX algorithm that we use) or other means. We preferred to state it this way, as the output could also come from a reweighted average for example, or by sampling uniformly at random a policy among the ones played.

Therefore, I have to say I do not think that the authors really establish an algorithm that has anytime last-iterate convergence and operates in a truly uncoupled manner, like the algorithm in [1].

While the anytime algorithms require a common seed and are not uncoupled in the same sense as in [1], they match the definition of uncoupledness that is required for the lower bound stated in Theorem 5.1 to hold. This lower bound relies on the absence of communication between the iterations and does not exclude an agreement before the start of the iterations. One of the main points of the two anytime algorithms was especially to characterize the minimax rate.

Furthermore, we would argue that the main weakness of Algorithm 2, the lack of anytime guarantees, is not problematic in practice. One of the main applications of last-iterate is to avoid the averaging of complex representation as explained in line 32-right, and the anytime convergence is not important for this matter.

Lemma 6.1 is a key lemma in this work and I would suggest the authors give more discussions and the proof sketch (if possible) in the paper.

The paragraphs above Lemma 6.1 provide the key point behind the lemma and can be seen as a proof sketch, we will add more quantitative arguments and re-organize the section to make it more apparent.

Besides, on the RHS of Line 302-329, the authors just introduce the design of the “regularized mirror descent” but without giving any discussions or explanations about this. Why can this kind of design enable a convergence rate of $\mathcal{O}(1/T)$ for the Bregman divergence?

We could add that the “regularized mirror descent” algorithm can roughly be seen as applying a regular mirror descent with the regularized operator $F_\tau$, hence the name, the two-steps update making the computation and the proof easier. This regularization makes the operator strongly monotone. Similarly to how strong convexity accelerates the convergence to the minimum, strong monotonicity makes the mirror descent convergent at a rate $\mathcal{O}(1/T)$. We propose to add a proof sketch of Lemma 7.1 to explain how we obtain this result.

Further, what is the intuition behind the LHS of Line 336 and 338? Since $\mu^0$ is a uniform distribution, I think the operation on Line 336 is equivalent to the following FTRL-style update?

Indeed, the two updates are equivalent. However, the intuition between Line 336 $\mu^{t} \gets argmin_{\mu_\in\Delta_A} (1-\tau\eta^t)KL(\mu,\mu^{\tau,t}) + \tau\eta^t KL(\mu,\mu^0)$ is to regularize the iterates toward the uniform, to "stabilize" the algorithm and allow the convergence. This specific regularization is not normally present in FTRL and only appears in the above equation because of the $(1-\eta^t\tau)$ factor.

We thank Reviewer eajt for the review and for pointing out a result that we missed in one of our references.

I think related works have been substantially discussed. The only comment I have is regarding the results in [1]. For uncoupled learning in zero-sum games, there are two results in [1] for last-iterate convergence rates measured by the duality gap: (1) $\mathcal{O}(T^{-1/8})$ high-probability bound and (2) $\mathcal{O}(T^{-1/6})$ bound in expectation. This paper discusses the first one but not the second one. Since the current paper focuses on last-iterate convergence in expectation, comparing the second bound in [1] would make the discussion more complete.

Indeed, this $\mathcal{O}(t^{-1/6})$ result in expectation is an unhighlighted result of [1] that we missed and that should appear in Table 1. Their result is stated for the $\ell^1$ norm in Theorem 4 of Appendix $C$, but a slight change to the proof seems to make it hold for the $\ell^2$ norm.

Could you explain how to derive line 682 from line 679-680? Maybe it is trivial, but I think some explanation would be helpful for the readers.

The link between the two lines is relatively direct computation-wise, but it is far from obvious and deserves more explanation. The internal randomness $\omega$ of the two players is independent of the game by construction, which implies that $\mathcal{D}(P_0^{\omega},P_{\theta^T}^{\omega})$ is $0$. The same can be said of $a^t|z^{t-1}$ for any $t$: the policy $\mu^t$ of the min-player is predictable with respect to $(\sigma(z^t))$, and the action $a^t$ is sampled from $\mu^t$ independently from the past. This implies that $\mathcal{D}((P_0^{a^t|z^{t-1}},P_{\theta^T}^{a^t|z^{t-1}})$ is also $0$ for all $t$.

Finally, the terms of the sum come from developing the observation of the min-player given the predictable policy $(1/2+\delta^t,1/2-\delta^t)$ of the opponent, as explained in line 189-right of the main paper. These explanations will be added to the proof.

We would like to express our sincere gratitude to Reviewer U4sa for their very comprehensive and constructive feedback. We appreciate the encouragement, particularly the acknowledgement of our "honest and transparent presentation of results".

We prepared a response for all of the questions, but we were greatly limited by the 5000 characters limit. We will only be able to submit (once) the response to the rest of the questions (especially some of the longest replies) after the reviewer's response.

Q1

For our analysis to hold, the regularization term currently needs to be the same for both players for Algorithm 2. As it is a hyper-parameter, we consider this requirement to be substantially weaker than actual communication.

Q2

The reason we use this shared seed that allows the sampling of a shared Bernoulli with parameter $p^i$ at each iteration, and not a Bernoulli directly is to make sure the two players have exactly the same sample $B^i$. The two players indeed need to explore and exploit simultaneously, as the exploitation (i.e. playing the output of $\mathcal{A}$) of one would otherwise bias the exploration of the other: the guarantees of $\mathcal{A}$ only holds if both players play the algorithm over the relevant iterations.

Q3

If at each iteration $i$, the actions $a^i$ and $b^i$ are observed by the two players, then, for any entry $(a,b)$ of the matrix, the expected value of this entry can be estimated by averaging all of the observations for which $(a^i,b^i)=(a,b)$. Assuming that each action profile is played on average $\Omega(t)$ times over $t$ iterations as $t$ scales to $+\infty$, then each entry of the matrix can be estimated with a precision of $\tilde{\mathcal{O}}(t^{-1/2})$ using Hoeffding inequality. Suppose each player computes its minimax strategy associated with the resulting estimated matrix (which can be done "offline", without observations) and plays it at each iteration. It can then be shown that the exploitability gap scales with the precision of $\tilde{\mathcal{O}}(t^{-1/2})$.

Q4

As explained in line 620, the proof also uses random matrices with Bernoulli entries, the entries of the matrix $M^\epsilon$ being the parameter of these Bernoulli. The confusion might come from lines 647-669, where we do the computation directly using this matrix, as the exploitability gap is defined for the expected loss matrix. We will add a sentence to clarify.

Markov games question

We are not sure we fully understand the question. We assume that "learning rate" refers to our guarantees. While their second algorithm reduced to a single stage seems to be similar to their first algorithm on matrix games, the opposite transformation (transforming an algorithm that works on matrices into an algorithm that works on Markov games) is not trivial. In particular, their approach relies on estimating the value associated with each state.

gradient descent question

Any mirror descent algorithm (including gradient descent) would not converge in general. In particular, if a fully mixed equilibrium exists, then the divergence between this equilibrium and the iterates is non-decreasing on expectation at each iteration. We think optimistic gradient descent would not work, but we think optimistic multiplicative weights update (which relies on the Shannon entropy instead) could if we use two different rates for the intermediate iterates and the actual iterates. We are not sure whether the optimal rate of $\mathcal{O}(t^{-1/4})$ is attainable with this method and if an additional problem-dependent constant would be necessary.

page 19

Typo

page 18

Indeed, this property does not hold for any regularizer, although it works for the most common ones, such as Shannon, Tsallis or the log-barrier (we only get $\nabla h^3 \leq 0$ for the $\ell_2$ regularizer).

page 17

It follows the fact that the gradient of the minimizer of a convex function belongs to the opposite of the (here constant) normal cone associated with this point and the constraints.

page 16

(a) This choice was made as Lemma C.1 relies on the estimated loss being non-negative. (b) typo

page 13

Each term $t$ is the expectation of the same KL divergence with $\theta^{t-1}$ taken under $P_0^{z^{t-1}}$. As $z^{t-1}$ is the only random variable in each term of the sum, this is the same as taking the expectation under $P_0$ directly.

line 689

See reviewer 3.

Questions for authors

While a learning sequence is predictable using the internal randomess and the past actions and reward, a non-learning sequence could be based on the unknown entries of the matrix $L$, for example, which would go against the lower bound.

The next intuition is correct

In this setting, it is easier to consider that we announce our mixed strategy to an authority, which then returns both the sampled action and the associated reward. Otherwise, the convergence would indeed fail with the pure strategies.

We thank Reviewer bHVB for taking the time to review our submission and especially for pointing out the issues in the notations. We address the concerns below.

It is concerning that the abstract claims both proposed algorithms achieve the optimal convergence rate. Could the authors kindly clarify whether the algorithms match the lower bound up to constant factors, only in terms of the order of $T$ or if the rates differ by logarithmic factors (e.g., $\log (T)$)?

The rate is indeed only matched up to logarithmic factors, and we do not try to hide it in the paper. In the abstract, this comes from an oversight due to the change of the $\tilde{\mathcal{O}}$ notation to $\mathcal{O}$ as the lower bound does not include any log factor. We will change the abstract to address this confusion.

The consistent use of Big-$\mathcal{O}$ notation to express lower bounds throughout the paper is somewhat confusing, as Big-$\Omega$ notation is typically used for lower bounds. For instance, this appears in Section 1 when referencing the lower bound from [Cai et al., 2023], as well as in Table 1 and Section 2. Could the authors kindly clarify whether this usage is intentional?

This is an oversight, and we will change the relevant Big-$\mathcal{O}$ notations into Big-$\Omega$ (including in the abstract).

Could the authors kindly provide appropriate citations for the transformation procedure described in Section 6?

While the idea behind the transformation procedure is natural, we are not aware of an article using this trick to transform an average profile convergence into a last-iterate convergence. If you have any precise references in mind that we did not stumble upon, please do not hesitate to give them so that we can add them to the paper

The notation $\ell^p$ ($\ell^t$) appears to be used with different meanings in various parts of the paper, which may lead to confusion. It would be helpful if the authors could clarify or standardize the notation to improve readability.

Indeed, we use the notation $\ell^p$ for the convergence of the sequence and $\ell^t$ for the loss, and we assumed changing one of the two would bring more confusion. As the two refer to two completely different objects, we considered this overlap of notation acceptable. However, we propose to instead talk of the convergence of the sequence of the random variables $EG(\mu^t,\nu^t)$ in the $L^p$ space toward $0$, which we also believe to be better in addition of avoiding this overlap.

Could the authors confirm whether, to the best of their knowledge, the convergence rate upper and lower bounds presented in this work are the tightest currently known?

The rates presented in Table 1 are the tightest currently known for high probability convergence. There also exists a $\mathcal{O}(t^{-1/6})$ rate for the $\ell^2$ convergence that was pointed to us that we will add to the table (and which we directly improve).

If so, could the authors kindly elaborate on the analytical tools or techniques they employed to derive a tighter lower bound on the convergence rate compared to prior works?

The idea of the tighter lower bound is the focus of section 5 and is based on improving the classical lower bound on best arm identification (see e.g. [1]) for our context. This lower bound is based, from the point of view of one player, on the difficulty between distinguishing a sequence of $T$ Bernoulli $\mathcal{B}(1/2)$ and a sequence of $T$ Bernoulli $\mathcal{B}(1/2-\varepsilon)$, which is required to guarantee $\epsilon$-optimality. We show that $\epsilon$-optimality in the context of last-iterate convergence for games can require distinguishing between a sequence of $T$ Bernoulli $\mathcal{B}(1/2)$ and a sequence of $T$ Bernoulli $\mathcal{B}(1/2-\varepsilon_t)$ for $t$ varying between $1$ and $T$, with $\varepsilon_t=\mathcal{O} (EG(\mu^t,\nu^t))$. This implies a trade-off at each iteration between getting more information on the $\varepsilon$-optimal strategy and playing near-optimal profiles $(\mu^t,\nu^t)$, which explains the worse rate.

[1] Jean-Yves Audibert, Sébastien Bubeck. Best Arm Identification in Multi-Armed Bandits, COLT 2010