On the Convergence of No-Regret Learning Dynamics in Time-Varying Games

Summary

This paper considers the problem of online learning in time-varying games under different setups. Specifically, the authors consider the case where all the players apply optimistic gradient descent (OGD) algorithm with a certain choice of learning rate. The main results that in the two-player bilinear game setup, the sum of squared duality gap is bounded by $O(1+V_{\epsilon-NE}+V_A)$, recovering the best-known result in the stationary game setup. This result is based on the bounded second-order path length of the learning dynamic and the important observation that sum of dynamic regret with respect to (approximated) Nash is (almost) non-negative. Next, they extend this result to the strongly convex-concave game with multiple steps and obtain similar duality gap guarantees. The author also consider the potential game and general-sum game setup with guarantees on the duality gap and CEgap bound respectively. Experiments are also done to support their theoretical results.

Strengths

- The problem considered in this paper is important and the authors show that the classic OGD algorithm achieves desirable average duality-gap and other equilibrium-related gap bound with provable guarantees. - The authors also do experiments on time-varying potential games and time-varying zero-sum games to verify their obtained NEgap bound.

Weaknesses

The main concern is the novelty of this paper. Specifically, this paper shares similarity to the results in [60] in many perspectives, although the authors explain in many places in the paper that how their results are different from [60]. - One of the main lemma Lemma A.1 is the same as the DRVU property shown in [60]. - Property A.3 is very similar to Eq.(32) shown in [60]. - Example shown in Proposition 3.2 is almost the same as the example shown in Appendix C, case 2 in [60]. - From the technical perspective, I feel like the analysis is very similar to the one shown in [60]. While [60] does not consider the approximated NE path-length, it is not hard to extend their analysis to the approximated NE path-length by replacing P_T with \epsilon-NE path-length +T\epsilon. Also, the boundedness of the second-order dynamic is also shown in Lemma 16/18 in [60]. - In addition, as mentioned by the authors, there are parameter-tuning issues in achieving better individual regret guarantees in bilinear and strongly convex-concave games, which is also handled by the meta-base structure proposed in [60]. The authors also derive results for general-sum games and potential games. Given Property 3.8 that the sum of regret with respect to CE is positive, it seems that the average CEgap bound is also not very hard to obtain given the bounded second-order dynamic of OGD.

Questions

- As mentioned in the above section, can the authors explain more in detail on the main technical difficulties and challenges compared to the analysis shown in [60]. - In Property 3.1, the authors argue that this extends the exact NE path-length in [60] to the approximated NE path-length. In [60], they also provide a bound with respect to W_T, which is the variance of the game matrix. Can the authors explain more on the comparison between the epsilon-NE path-length and W_T? Is there a case where both the exact NE path-length and the W_T are large but the epsilon-NE path-length is very small?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See Weakness section.

Summary

In this work the authors consider no-regret learning in multiagent games where the underlying game varies across different rounds. They study several classes of games and various learning algorithms that the agents can use. Naturally, the results they obtained are parametrized by variation measures of the underlying game that the agents participate in. To be more precise: * For time varying zero-sum games, they focus on the setting where both of the agents are using optimistic gradient descent (OGD), which is a variant of gradient descent that puts a bias on more recent rounds of the game. Interestingly, they show that almost all iterates of OGD are approximate Nash equilibria provided that some variation measures related to changes in the set of approximate equilibria of the games and the underlying payoff matrices are $o(T)$. * Then, they consider sequences of games where the games in each round are strongly convex-concave. For this class of games, they are able to show a similar result as above, but under weaker variation conditions for the underlying sequence of games. * Finally, they consider time-varying general-sum games. Naturally, since Nash equilibria are not tractable in this setting, they consider convergence to correlated equilibria. They prove similar results as above, but now the variation measure they use is related to the set of correlated equilibria of the game. Their results have implications to other settings as well such as meta-learning and dynamic regret guarantees in static games.

Strengths

* The paper studies a very natural problem and provides strong results under various settings of interest, which also have implications in other settings, as I mentioned in the summary. * For the most part, the paper is easy to follow and the authors have done a good job placing their work in the literature. * The authors are not trying to oversell the proof technique, which is heavily inspired by prior works, but uses some natural and clever modifications. For example, instead of letting the variation measure to depend on variations of the set of exact Nash equilibria which would make the problem very difficult to handle since this set is very sensitive to any changes of the payoff matrices, the authors consider variations of the set of approximate Nash equilibria, which behaves much nicer. Since the results are strong and general, I don't think that the authors should be penalized for the fact that the proof techniques are not very novel.

Weaknesses

* Some parts of the paper might be a bit hard to follow for non-experts, especially in Section 1.1. For example, the MVI property and the RVU bound were not defined. I think the authors could make the transition to this section a bit smoother, although I understand that the space limitations are making it trickier. * Even though the variation measures the authors use are intuitive and it makes sense that the regret should scale with these quantities, there are no lower bounds to show the extent to which these results are optimal. Some minor comments: * In Proposition 3.10, it might be useful to state which dynamic benchmark you consider for their dynamic regret bound. * With this bibliography style it is a bit hard to keep track of the references, although I understand that it saves some valuable space.

Questions

* What are the technical challenges to generalize the results to the bandit or some other partial feedback model? * Would there be any benefit if you considered a variational measure wrt approximate correlated equilibria in general sum games instead of exact correlated equilibria? * To what extent do you think that the results are tight? * Do the results for two-player zero-sum games generalize to multiagent zero-sum polymatrix games? I don't see any inherent obstacles to do that using your approach, but I might be missing something. * Another class of general sum games that is tractable in the single-shot setting are games in which the underlying matrices are rank-1. Is there any hope to obtain similar results for this class of games? I would imagine that the techniques would need to be substantially different from your approach. * In Theorem 3.3 (and similar results) if the parameter $L$ is not known does the usual guess-and-double trick work to get the bound?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

This paper studies learning dynamics in games that change over time. This is a similar setting to [60], but while [60] focuses on regret guarantees, this paper focuses on iterate convergence to NE. The main result states that for bilinear zero-sum games, running optimistic OGD guarantees that, $$ \sum_{t=1}^T EqGap_t = O(V_{NE-\epsilon}^T + V_A^T), $$ where $EqGap_t$ is the NE gap (i.e., the difference between the player utility and best response), $V_{NE-\epsilon}^T$ is the variation of $\epsilon$-approximate NEs of the games $+\epsilon T$ (in fact they allow different $\epsilon$ for each $T$), and $V_A^T$ measures the variation of the game matrices. $V_{NE-\epsilon}^T$ can be much smaller compared to the variation of the exact NEs. The paper continues by providing variation-dependent bound for strongly convex games. Next, they provide a bound on the sum of NE gaps for general sum-potential games (which depends on some notion of variation of the potential function), as well as bound on the sum of CE gaps in general games. Finally, they present results for *dynamic* regret in static games.

Strengths

The paper provides a set of interesting results. These include, - Various results on the sum of NE gaps. Specifically, I find the notion of $V_{NE-\epsilon}^T$ very elegant, and indeed, it seems like a much more reasonable notion for characterizing the complexity of time-varying-games instance. - Bounds on the dynamic regret in static games - even though this is a basic question, according to the authors these are the first results that show $\sqrt{T}$ dynamic regret in games (they also show $\log T$ dynamic regret under a stronger feedback model)

Weaknesses

- The main text lacks proofs/proof sketches. So it is impossible to understand the main ideas and techniques, even at a high level, without diving into the full technical proofs in the appendix (+ it makes it hard to evaluate the technical contribution of the paper). - In several places, it is quite hard to follow the text. Specifically, section 1.1 is rather technical, given that it is part of the intro. In addition, the section on general games that starts in line 287 was not sufficiently clear to me. For example, the authors mention that *"there exist matrices $A_1, . . . , A_n$, with each matrix $A_i$ depending solely on the utility of Player i..."* but what are exactly these matrices represent? What does the value of the optimization problem in (3) represents? Why does *"incorporating the 0 vector will be useful"*? and why does there exist $\mu^\star$ that satisfy the condition in line 300? - Lack of comparison to previous work: what is the result of [30] and how is it compars to your result in "meta-learning"? How does Corollary 3.4(2) compares to the result in [60] (except for the difference between $V_{NE-\epsilon}^T$ and $V_{NE}^T$)

Questions

What is the difference between the sum NE gaps (Corollary 3.4) and dynamic regret (line 342)? See additional questions in the Weaknesses part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

The paper studies optimistic gradient descent for time-varying games. Authors prove convergence bounds for zero sum games involving the first order variation of approximate nash equilibrium, which can be significantly tigher than variation bounds involving exact nash equilibria and second order bounds in payoff matrices. The paper also includes refined convergence bounds involving second-order variation for strongly-convex-concave games. The results also have implications for meta-learning, where games are repeated many times. The authors also extend results to time-varying general-sum multiplayer games with correlated equilibria, extending exisiting meta-learning similarity measures to general sum games and proving new single-player regret bounds. Techniques are applied to static games, improving our understanding of dynamic regret.

Strengths

Nonstationarity is an important and challenging area of study for learning in games, and is under-explored. Bounds involving approximate nash equilibrium variation can be significantly tighter than existing bounds involving variation in exact nash equilibria. The results for general sum games solving two independent open problems. Ideas provide improved understanding of dynamic regret for static games, including both positive and negative result. The paper is well written, including a variety of results while still providing technical exposition on insights behind the proofs and contextualizing the result.

Weaknesses

Observation 3.11 requires two point feedback, so it's less clear this is a significant improvement. The paper could probably be a bit more self contained. The paper borrows ideas from [60], like a dynamic RVU bound but it is hard to follow without additional context.

Questions

Typo 88: accelerates-> accelerated

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes.

Authors' Rebuttal

I would like to thank the authors for their detailed response. I don't have any further questions.

Thanks for the authors' response

Thanks for the authors' response on my questions and the comparison between the submission and [60]. However, I am still not convinced the technical contribution of this submission compared with [60]. - While the authors argue that "using RVU-type bounds and second-order path lengths is very standard in this line of work", the main theorem (Theorem 3.1) of this submission is by directly combining the dynamic RVU-type bound proposed in [60] and the property of (almost) non-negative sum-of-regret property, which has already been shown in [60] (see Equation (32) of [60]) and section 3.1 of [Anagnostides et al., 2022]. As mentioned, the only difference I think is that [60] consider the exact NE divergence but the authors consider the approximate NE divergence, which is not hard to be obtained by extending the analysis in [60] by replacing P_T with \epsilon-NE path-length +T\epsilon following in Lemma 16/18 in [60]. From the technical perspective, the extension to poly-matrix zero-sum games, convex-concave games and the general sum game (using CE) is not complicated based on the (almost) non-negative sum-of-regret property as shown in proposition 3.2 in [Anagnostides et al., 2022]. - While the author argued on the choice of \eta, I believe in [60], if the measure is only for equilibrium gap (duality gap in [60]), constant learning rate is also enough to prove the results as I think using a meta-base algorithm design in [60] is mainly about adapting to different metrics. Also as mentioned in Section A.1.5, to achieve better regret bound, an adaptive tuning method proposed in [60] is necessary. Then this is exactly what is proposed in [60]. Based on the above, I am not convinced that the contribution is significant. [Anagnostides et al., 2022] On Last-Iterate Convergence Beyond Zero-Sum Games, ICML 2022