- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The content of the paper is built around three claims on learnability of various properties related to Nash equilibrium in zero-sum matrix games.
The first claim says that game value and exploitability is stable w.r.t. small changes of the matrix entries whereas this is not true for the equilibrium strategies. Consequently, one cannot have a Lipschitz continuous function from the space of -matrices to the strategy space.
The second claim deals with matrix games where the matrix entries are noisy and one can only sample them. The paper assumes that they are i.i.d. and follow normal distribution. Given a matrix game, it might be close in the matrix space to the boundary where the equilibrium strategies suddenly change. So the question is whether a learning algorithm can recognize on which size of the boundary the true matrix is. The paper provides such an algorithm (called TARGET) that works for an extremely complicated class of games so that its definition is only sketched in the main text.
The last claim deals with the situation where we must sample first without knowing in advance which equilibrium-related property is the requested output. The paper quantifies the ratio how much the expected error change in comparison with the situation where we know the property in advance.
Critical strengths
I find the topic quite interesting and worth of pursuing. The paper brings a finer classification of what is meant by equilibrium learnability. It usually assumes outputting low-exploitable pair of strategies whereas this paper investigates finer questions we might have regarding the equilibrium of a noisy game.
Critical weaknesses
I have several concerns regarding the presentation. It is exceptionally long (125 pages) for a conference paper. So it is hard to compress the main message into the main 9-pages text. Still, I think that could be done in a human readable fashion. However, the paper fails completely to communicate its results. If the text is meant for a human researcher, it must provide a certain level of guidance supporting the understanding of presented results. This is not the case for the paper under review. It is structured as a machine-like sequence of facts without any insights. Most of the crucial definitions are postponed to the appendix, still the theorems in the main text use them without any explanation. This makes comprehension of the main text impossible as one has to always inspect the appendix. What is the point to state formally a theorem if it uses undefined symbols without any intuitive explanation? The presentation issue is well demonstrated by the last concluding section. It does not provide a reasonable scientific conclusion. It looks more like a summary log. For instance, the paragraph "Proof and implementation map" starts with the sentence "The logical chain is auditable." I guess that a human researcher would never write something like that.
My second concern is applicability of Theorem 3.1 supporting the second paper's claim. As I wrote above the class of games where Theorem 3.1 applies is quite complicated. The theorem assumes known numerical margins for an unknown interface, a complete finite atlas, independent Gaussian measurements of chosen payoff entries, and a game lying close to the boundary. It naturally rises the question of its applicability. How could we obtain or certify the class margins and atlas for an unknown game, and what is the computational cost of doing so w.r.t. the matrix size?
Questions for authors
I have no question.