Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games

Summary

This paper investigates the first-order query complexity of two-player zero-sum games. More precisely, given a bi-matrix zero-sum game $(A,-A^\top)$ (with $A \in \mathbb{R}^{k\times k}$) a first-order query is a set of strategies $(x,y)$. The answer to such a query is the set of vectors $(A y, -A^\top x)$ respectively denoting the payoff vectors of the row (x) and the column (y) agent. The authors try to understand what is the necessary number of first-order queries so as to compute a min-max equilibrium of the respective zero-sum game once the matrix $A$ is unknown. The authors establish that in order to compute an exact min-max equilibrium at least $\Omega(K)$ first-order queries are needed. The latter result coincides with the first-order complexity of the naive algorithm that first $learns$ the whole matrix $A$ and then computes an exact min-max equilibrium. Then the authors show that in order to compute an $\epsilon$-approximate min-max equilibrium $\Omega(\log(1/\epsilon K))$ first-order queries are needed. The latter result approximately matches the best-known upper bound ($O(\frac{\log K}{\epsilon})$) obtained by Optimistic MWU.

Strengths

I think that this is a solid work. The first-order complexity model is very well-motivated since it captures exactly the information exchange model of no-regret dynamics with full information feedback. Thus any lower-bound on the first-order complexity directly implies lower bounds on the convergence rates of such no-regret dynamics. The current state of the art convergence results of such no-regret dynamics is $O( \frac{\log K}{\epsilon})$ that is approximately matched by the provided lower bound. I also think that the paper introduces some interesting techniques that can be of use so as to completely settle the first-order query complexity for computing min-max equilibrium.

Weaknesses

The only weakness of the paper is the fact that it does not match the current upper bound. That being said I believe that this work is an important first-step.

Questions

Minor: You may want to include also this references for regret-based algorithms for the computation of CCE in general-sum games. Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update, Piliouras et al. 2022

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

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

3 good

Limitations

N/A

Summary

This paper studies the query complexity lower bound of first-order methods for finding exact and approximate Nash equilibria in two-player zero-sum games. It is first established that if the matrix entries come from a fixed countable set, one query suffices to reconstruct the full matrix and hence to compute the exact Nash equilibrium. This rules out most existing lower bound constructions as they use rational or otherwise countable matrix entries. A new approach is then used to establish an $\Omega(K)$ lower bound for finding the exact Nash and $\tilde{\Omega}(\log 1/K\epsilon)$ lower bound for finding an $\epsilon$-approximate Nash (for sufficiently small $\epsilon$), where $K$ is the number of actions.

Strengths

- This paper studies a fundamental yet perhaps overlooked problem in game theory; as mentioned by the authors, it is indeed surprising that none of the established lower bounds apply to this setting. To the best of my knowledge, the results obtained in this paper are indeed the first non-trivial lower bounds for noiseless first-order methods in two-player zero-sum games. - The paper is well-written and offers a good explanation (Theorem 4) why it is non-straightforward to adapt existing constructions to two-player zero-sum games.

Weaknesses

- The current lower bound rate is still quite far from the existing upper bound in terms of the dependence on $\epsilon$. Typos: Line 16: Although not exactly a typo, the submodular optimization problem is never mentioned in the main text. Line 59: "build build" Line 519: the first term should be $\lambda_1x_1$ instead.

Questions

Lines 287 and 322: a common Nash equilibrium for all matrices in $\varepsilon_t$ may not exist, right? Does the statement here mean that "suppose that a common Nash equilibrium exist"?

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Contribution

3 good

Limitations

This work is mainly theoretical and does not entail direct societal consequences

Summary

Define the gap of a two player zero sum game with payoff matrix M and mixed strategies p and q as: gap(M,p,q):=max_j (M^Tp)_j - min_i(Mq)_i An equilibrium is called \eps approximate if the gap is at most 2\eps. An important question is to compute the approximate Nash equilibrium by observing the gradients of the objectives in a sequential manner. Of course the number of observations / queries needs to be optimized. Rakhlin and Sridharan showed that O(\ln K/\eps^2) queries suffice for K X K matrix games. The authors here improve their bound to O(\ln K/\eps) - which is optimal - for small \eps (\eps < 1/K^4). They also show a lower bound that rules out certain algorithms for improving the upper bound to match the lower bound for all \eps.

Strengths

- Learning the \eps approximate Nash equilibrium is an interesting and important open problem in its own right, not to mention several applications. - The techniques in the paper are interesting by themselves.

Weaknesses

- The actual result is fairly technical and may not be of broad interest since the improvement is marginal (only for \eps < 1/K^4).

Questions

- How robust are your techniques/bounds when the observations are noisy? Often we don't have access to precise gradients.

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, they have been presented clearly.

Summary

This paper delves into the complexities associated with identifying a mixed Nash equilibrium within the context of a zero-sum game. Specifically, it scrutinizes situations where the algorithm does not directly observe the payoff matrix. Instead, it learns about it by querying its product with either a column vector or row vector. The challenge of computing Nash equilibria in this model has been extensively studied, however, prior to this study, little was known about lower boundaries. The study's central findings include a K-2 query lower bound for calculating an exact equilibrium and a lower bound that exceeds the constant when 1/epsilon is super-polynomial in K for calculating an epsilon-approximate equilibrium. The methodology for deriving these lower bounds involves the identification of an adversary capable of answering an arbitrary series of first-order queries. This adversary ensures that the all-ones vector remains considerably distanced from the linear span of query responses for the maximum possible steps, while concurrently guaranteeing that the set of matrices congruent with query responses remains non-empty. Early on, the paper also introduces a minor result highlighting the complexities inherent in proving lower boundaries within this model. If provided with a countable set of numbers known to encompass all the entries of the payoff matrix, a single first-order query is sufficient to reconstruct these entries and consequently, identify a mixed equilibrium. Although this result is simple, its proof capitalizes on the assumption that responses to first-order queries comprise vectors of infinite-precision real numbers. While this algorithm lacks practicality (an aspect openly acknowledged in the paper), its existence accentuates the challenge associated with establishing lower bounds in a model that facilitates such powerful queries.

Strengths

n/a

Weaknesses

The paper has some discernible weaknesses which impact its overall effectiveness and value. They are listed as follows: 1. Lack of Clarity: The exposition in the paper lacks clarity and coherence which makes it difficult to follow the arguments and understand the results. Better structuring and clear, concise language would greatly improve the readability and accessibility of the paper. 2. Absence of Experiments: There are no empirical evaluations or experiments provided to support the theoretical results. Experimental results are key in illustrating the practical applications and feasibility of the proposed methods. Therefore, including such results is crucial for providing a comprehensive understanding of the paper's contributions. 3. Uncertain Significance of the Results: While the results of the paper are novel, their actual importance and impact on the field are uncertain. The paper would greatly benefit from a discussion explaining the broader implications of the results, their potential applications, and how they advance the current state of knowledge in the field. Without such context, it is hard to assess the true significance of the findings.

Questions

This paper leaves me in a state of indecision, and being the more positive reviewer, this doesn't appear to be a promising sign for the paper. The rather tepid scores possibly reflect my collective sentiment towards the main result, which is the lower bound. It appears to be quantitatively modest, and we're uncertain about the significance of obtaining upper/lower bounds in this exact query model that permits the use of "funny bit tricks". It's unclear how vital these aspects are in terms of contributing to the field, and this ambiguity might be affecting our overall reception of the paper. Let me give some recommendations about improving the clarity of your theoretical paper: 1. **Abstract and Introduction**: Ensure that these sections provide a clear and concise overview of the key ideas and contributions of the paper. Avoid using overly technical terms and jargon in these sections, as many readers will try to get an understanding of your work from these parts before diving into the main content. 2. **Theoretical Concepts**: Each theoretical concept, model or algorithm that you introduce should be clearly defined and explained. When introducing a new concept, briefly review its background and the relevant literature. Also, explicitly state the assumptions you are making. 3. **Equations and Theorems**: Always explain the intuition and significance behind every equation or theorem before diving into rigorous mathematical proofs. Make sure to annotate your equations adequately and define all terms and variables used. Whenever possible, accompany your mathematical results with visualizations or intuitive examples. This crucially misses in the main part of your results 4. **Results Section**: In the results section, don't just state your results, but also explain their implications. Make sure to clearly relate your results back to the problems and questions you outlined in the introduction. 5. **Language and Flow**: Aim for a clear, concise, and precise language. Avoid long and convoluted sentences. Make sure each section and subsection follows logically from the previous ones, helping to guide the reader through your narrative. 6. **Discussion and Conclusion**: Use these sections to clearly summarize your contributions and their implications. Discuss how your results fit into the bigger picture of your research field. 7. **Appendix**: Put additional details, proofs, and technicalities that are not essential for understanding the main ideas of your paper in the appendix. This way, you can keep the main text more readable without losing any necessary detail. Add explanatory paragraphs after theorems I strongly believe that the paper is not submitted in the correct conference venue.

Rating

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

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

n/a

Summary

This paper focuses on the query complexity of learning (approximate) Nash equilibria in zero-sum matrix games. The authors provide lower bounds on the query complexity for exact and approximate equilibria. They also show that if the game matrix has entries in a known countable set, the learner can recover the full matrix in one single first-order query. The paper discusses related work on lower and upper bounds for similar problems. The authors present upper bounds for the query complexity of finding approximate equilibria and introduce two strategies for obtaining equilibria with large approximation values. They also propose a potential improvement to the lower bounds by finding a different proxy for the gap. The paper includes proofs, examples, and explanations to support the theorems and corollaries related to the query complexity of learning game matrices. Overall, the paper contributes to the understanding of the query complexity of learning Nash equilibria in matrix games and provides insights into the lower and upper bounds for this problem.

Strengths

The paper presents original and valuable contributions to the understanding of the query complexity of learning Nash equilibria in matrix games. It introduces new results and insights, providing lower bounds on the query complexity for both exact and approximate equilibria, and proposing a potential improvement to the lower bounds. The quality of the paper is high, with rigorous proofs, clear examples, and a comprehensive discussion of related work. The paper is also well-structured and clearly written, making it accessible to readers. In terms of significance, the paper’s contributions can inform the development of more efficient algorithms for learning Nash equilibria in matrix games, with practical applications in various domains. Overall, the paper is a valuable addition to the existing literature in this field.

Weaknesses

The paper provides valuable insights into the query complexity of learning Nash equilibria in matrix games. However, the novelty of the results is somewhat limited as they largely build upon existing literature, such as the connection between regret and equilibria. The paper partially resolves the first-order query complexity of approximate Nash Equilibria in finite games, but further analysis is needed for tighter results. The paper’s focus is primarily on theoretical analysis and proofs, without experimental evaluation, and the results are mainly theoretical with no direct societal consequences.

Questions

Please refer to weaknesses.

Rating

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

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

3 good

Contribution

3 good

Limitations

The author has clearly acknowledged the limitations of their work, specifically that it only partially resolves the first-order query complexity of approximate Nash Equilibria in finite games and further analysis is needed for tighter results. In terms of broader impact, the results are mainly theoretical and do not have direct societal consequences.

answer

Thank you for response. I have carefully read the other reviews as well as your responses. I believe that your result are interesting for the learning in games community of Neurips and thus I have decided to raise my current score.