Summary
This paper studies online learning of quantum algorithms based on the matrix multiplicative weight (MMW) updates. A main technical contribution is to introduce a weaker version called the minimal-information matrix multiplicative weights (3MW), which only requires zeroth-order gradient sampler and can achieve an overall regret of O(T^{-1/4}). In addition, for N-player quantum games, the paper proved a convergence result that 3MW guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
Strengths
From my perspective, the most notable strength of this paper is the nice observation that less information is required to make MMW works. Considering that MMW has wide applications in quantum algorithms for machine learning and optimization, I believe that the result may be of general interest. Technically, this is achieved by exploiting ideas from machine learning, in particular bandit optimization, which provides interesting perspective for designing future quantum algorithms.
Weaknesses
The most notable weakness is the claim in intro that the result by Jain and Watrous [21] with O(\sqrt{T}) regret for quantum online learning algorithms remains the tightest known bound for Nash equilibrium learning in quantum games. This is not true, as a recent paper by Gao et al. https://arxiv.org/abs/2304.14197 gave a quantum algorithm with poly-loga regret for zero-sum games. Compared to this paper, the results obtained by this paper is sub-optimal.
Another notable weakness is that the dependence in dimension is at least D, and does not present a quantum speedup here. In fact, a main merit of applying MMW into quantum algorithms is that MMW provides fast quantum algorithms for solving relevant problems. An important paper was Brandao and Svore https://arxiv.org/pdf/1609.05537.pdf in FOCS 2017, which can solve semidefinite programs with complexity square-root in D. If the current framework 3MW has at least linear dependence in D, it will prohibit its further applications in quantum computing.
Questions
1. Can the authors further comment on whether the convergence rate of the proposed 3MW algorithm, or in other words the online regret, can be further improved? Given the existence of works such as Gao et al. mentioned above, it would be helpful if the authors can provide a more complete picture here.
2. I’m confused by the sentence “in contrast to classical finite games, quantum games have an infinite continuum of pure states” in the abstract. On classical computers, even if we play games with finite cardinality, we can still choose mixed strategies and the set of probability distributions supported on a finite set can be uncountable.
3. It would in general be helpful if the authors can introduce more on the applications of 3MW. In particular, in MMW the payoff gradient of player i is defined as V_i(X_t). However, in most existing quantum papers, V_i is very simple: the identity function. For instance, in the above Brandao-Svore paper as well as several important follow-up works that solves semidefinite programs with quantum speedup, V_i is the identity function and the update is simply a learning rate \eta * X_t.
In all, it’s nice to know that 3MW can be applied with bandit information and for general V_i, but this should probably be further motivated about why we need to consider more complicated V_i’s.
4. In numerical experiments, around Page 29, the authors claimed that the their algorithms achieved a rate of convergence closer O(1/T) instead of the weaker O(1/\sqrt{T}) or O(1/T^{1/4}) bounds. However, I didn’t see detailed evidence for this; it would be helpful if the authors can present more detailed data and plots for demonstrating this phenomenon.
Note that this is related to my question 1: if the convergence rate is ~O(1/T), the overall online regret will be poly-log. So it is probably worth closer study about this, both theoretically and experimentally.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Limitations
This work is mainly theoretical so I don't think there are notable limitations, but it would work better if the authors can articulate this more clearly.