Summary
This paper considers the problem of developing quantum, low-regret, algorithms for solving zero-sum games. This paper provides a quantum algorithm which matches the state-of-the-art for solving zero-sum games while improving upon the regret of the associated algorithm. The paper achieves this result by providing a stochastic variant of optimistic mirror descent which they then implement by a quantum algorithm for developing multiple samples from a suitable Gibbs distribution. Additionally, the paper discusses implications and lower bounds for linear programming more broadly.
Strengths
Zero sum games are an important optimization problem in many disciplines. The mere fact that the paper shows how to depart from previous quantum algorithms for solving zero sum games (in using optimistic mirror descent versus mirror descent) while retaining state-of-the-art bounds is interesting and potentially useful for further study of the problem. Additionally, by following this alternative approach the paper obtains improved regret and a type of parallelism in solving the problem. This is an interesting advancement for the study of the problem. Finally, this alternative optimization method gives rise to a different Gibb’s distribution sampling problem than the one considered in prior work. Furthermore, the paper gives an interesting algorithm for solving it which could motivate further study. Finally, the additional discussion of linear programming provided in the paper (though seemingly straightforward) is a nice addition as well.
Weaknesses
It is not clear how substantial the departure from this paper from prior work is, how novel the advancements are, and how complete the comparison of this paper to prior work is. While I think the advancements of the paper are interesting and potentially exciting (as discussed in the strength section), I fear that the paper does not well-articulate them or situate them. For example:
* A comparison of the techniques in the Gibb’s sampling algorithm of this procedure and those in prior quantum-zero sum games algorithm does not seem to be provided. This seems particularly important as the techniques were key to recent advances in quantum algorithms for solving zero-sum-games.
* It is not clear what exactly the benefits of low regret are over prior work and why previous results couldn’t be used to obtain low-regret (e.g. by only considering a subsequence of the iterates taken). I think the low-regret aspect is interesting and this algorithm is potentially more parallel than prior algorithm’s with state-of-the-art complexity and the sampling problems considered may be simpler than in prior work; however I am not sure that the paper argues this clearly.
* It is not clear what obstacles were present to obtaining the result. It would help if the paper clarified whether moving from mirror-descent to optimistic mirror-descent was the main insight and the rest was straightforward (though technical and important) or if further insights were needed.
Some additional comments along this line are given “Questions.”
Questions
My main questions / comments are the items in the previous “Weaknesses” section. Beyond what was written there: How does the Gibb’s sampling compare to prior work? Is it simpler in any way? The same? Is a completely different techniques used? Is there a major insight of the paper beyond the use of stochastic optimistic mirror descent?
Beyond this, below are some more detailed suggestions, questions, and comments:
* Line 1: “for zero-sum games” --> “for solving zero-sum games”
* Line 4: “yielding a quadratic improvement” as written, I am concerned this is suggesting that it is the first such improvement.
* Line 27: “For, this approximation task, online learning becomes significant” – I am not exactly sure what was meant by this.
* Line 33: It might be beneficial to define regret or explain the model more clearly earlier so the improvement over prior work is clearer. (Regret is well-known in general, but when stated for a static optimization problem, the definition is less clear.)
* Line 39: I believe zero-sum games were shown to be solvable in $\tilde{O}(1/\epsilon)$ iterations earlier, e.g. “Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems” by Nemirovski in 2004. I’m less sure about whether this works in regret context but in any event I believe should be mentioned when discussing the history of solving zero-sum games.
* Line 81: it might be good to clarify whether this is a new feature of this algorithm or not
* Line 130 – 135: it might be good to clarify why prior work could or could not be used for this problem
My main questions / comments are the items in the previous “Weaknesses” section. Beyond what was written there: How does the Gibb’s sampling compare to prior work? Is it simpler in any way? The same? Is a completely different techniques used? Is there a major insight of the paper beyond the use of stochastic optimistic mirror descent?
Beyond this, below are some more detailed suggestions, questions, and comments:
* Line 1: “for zero-sum games” --> “for solving zero-sum games”
* Line 4: “yielding a quadratic improvement” as written, I am concerned this is suggesting that it is the first such improvement.
* Line 27: “For, this approximation task, online learning becomes significant” – I am not exactly sure what was meant by this.
* Line 33: It might be beneficial to define regret or explain the model more clearly earlier so the improvement over prior work is clearer. (Regret is well-known in general, but when stated for a static optimization problem, the definition is less clear.)
* Line 39: I believe zero-sum games were shown to be solvable in $\tilde{O}(1/\epsilon)$ iterations earlier, e.g. “Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems” by Nemirovski in 2004. I’m less sure about whether this works in regret context but in any event I believe should be mentioned when discussing the history of solving zero-sum games.
* Line 81: it might be good to clarify whether this is a new feature of this algorithm or not
* Line 130 – 135: it might be good to clarify why prior work could or could not be used for this problem
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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.
Limitations
This is primarily a theory paper, and it is unclear how applicable this is. However, the weaknesses and questions discussed reflect limitations for which further discussion might be beneficial.