- Rating
- 4(+2)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 3(+1)
Read review
Paper summary
This paper studies monotone games with unbounded continuous action spaces, where each player can observe only one payoff value of their own per round. The authors propose SPOG, which combines differences between current and past payoffs, updates on fast and slow timescales, and slowly expanding projection envelopes. The paper analyzes the almost sure convergence of the slow iterate to a Nash equilibrium in the merely monotone case, and claims a rate in mean squared distance in the strongly monotone case. Experiments on two two-player games illustrate the algorithm's convergence behavior.
Critical strengths
This combination of settings is valuable in itself: putting a single payoff observation per round, unbounded action spaces, and mere monotonicity together means dealing with the variance of payoff-based estimates, stability on an unbounded domain, and the rotational behavior of games. I especially value the setting of Theorem 4.1, since last-iterate convergence under mere monotonicity is a substantial challenge.
The motivation behind the algorithm is also clear: the fast process tracks a fixed point determined by the slow iterate and controls estimation errors as the region explored by the iterates grows (Lemma 3.3 bounds the size of the estimator). This avoids having to assume a bounded set containing the equilibrium in advance, which is a real step forward from existing work on compact sets.
Critical weaknesses
1. The headline rate is not fully covered by the parameter range in the current theorem. I noticed that Assumption 3.2 on page 6 requires , but the parameters used in the main text to obtain the exponent are . According to the exponent in Theorem 4.2, within the parameter range stated in the paper, is only a supremum that can be approached. Yet equation (7) on the same page explicitly gives a guarantee in mean squared distance, which does not follow directly from the current theorem. Simply extending the parameter range to include would not resolve this: at this endpoint, the convergence exponent supported by the current error recursion also depends on the step-size constants, and Chung's lemma used in the proof requires corresponding additional conditions. My point is that the authors need to make these conditions explicit and complete the treatment of the logarithmic factors to fully support the claimed rate. So a complete rate result that actually covers this parameter choice is needed, or the quantitative claims in the abstract and main text should be narrowed accordingly. I don't think the current analysis adequately supports the claims being made.
2. Both comparisons used to claim a rate advantage need to be revised. On page 9, the paper attributes beating the optimal lower bound for one-point zeroth-order methods to adjusted SPSA. I'm not convinced by this explanation: the lower bound in Shamir (2013) concerns a feedback model that allows independent noise in function values, which is different from the exact payoff feedback used in this paper each round. Also, that lower bound applies to general query strategies, not just conventional SPSA. Reusing past payoffs can reduce variance, but that alone does not establish that an information-theoretic lower bound has been surpassed under the same model.
The other comparison is the claim in the abstract and Contribution 3 on page 2 that the rate is faster than the best known rate in the bounded, strongly monotone case. Theorem 3 in Huang and Hu's published journal version (IEEE Transactions on Automatic Control, 2025) already gives an rate in mean squared distance for the last played action, with arbitrarily small , under conditions including a compact convex domain and a Lipschitz pseudo-gradient. It also requires only one exact payoff observation per round. Strong monotonicity meets its monotonicity requirement, so its exponent does give a faster rate than . This result assumes a fixed bounded domain and cannot replace this paper's result on unbounded domains. But since this paper claims to improve on the fastest rate in the bounded case, it needs to address this result directly. I suggest including it in Table 1 together with its applicable conditions, and revising the rate comparisons in the abstract and Contribution 3. If the authors think it falls outside the scope of this comparison, please explain the specific differences in assumptions. This point only affects the claim of a rate advantage; the convergence contribution for unbounded, merely monotone games should still be assessed separately.
3. The experiments still provide rather limited support for the rate and the stabilization mechanism. OG+SPSA uses the same residual estimation idea, so it is a useful comparison. But the difference in Figure 1c is shown for only one parameter setting, and it's not clear whether it would still hold with different step sizes. The authors have already explained that OG/OG+ use gradient feedback with Gaussian noise, while SPOG uses exact payoff feedback, so it is hard to attribute the speed differences in the plots solely to the algorithmic structure. The parameters listed for Figure 1c in Appendix G also violate two conditions in Assumption 3.1: is at the excluded boundary for Example 5.2, while grows logarithmically instead of tending to zero. The connection between the existing curves and the theoretical guarantees still needs to be explained.
Appendix G already explains that the chosen exponents are close to the theoretical ones, and that the parameter sequences are shifted and rescaled to avoid decaying too quickly. I suggest further explaining how their departures from Assumption 3.1 affect the interpretation of the experiments, and adding a setting that satisfies the theoretical conditions. To examine the role of the fast process more directly, the authors could build on the existing OG+SPSA comparison by using the same projection rules and checking the effect of step-size choices, or report how the estimator's fluctuations evolve over iterations. This would more directly test the stabilization mechanism emphasized in the paper.
Questions for authors
-
Gaps in the convergence proof for the merely monotone case. For the step sizes, Theorem 4.1 only requires Assumption 3.1, but Proposition 4.6 and Appendix F.2, which its proof relies on, use the power-law step sizes in Assumption 3.2. Please complete the argument for summability of the errors under the general step-size conditions; applying the Robbins–Siegmund theorem directly to equation (77) may be an option. Appendix F.3 also needs a correction where it infers that the unweighted calibration error vanishes from the vanishing of the weighted error in Proposition 4.5. One possible route is to use a subsequence with vanishing residual from Proposition 4.6, together with the fixed-point relation, to identify the limit point. These look more like repairable gaps in the proof.
-
Error estimate for the fast process. The upper bound used in equation (58) in the appendix—that a difference of squared norms is bounded above by the squared norm of the difference—does not hold for general vectors. After fixing it, please check that the contraction term and the orders of the error terms used later still hold.
6 comments
Reply 2/4
- Both comparisons used to claim a rate advantage need to be revised. On page 9, the paper attributes beating the optimal lower bound for one-point zeroth-order methods to adjusted SPSA. I'm not convinced by this explanation: the lower bound in Shamir (2013) concerns a feedback model that allows independent noise in function values, which is different from the exact payoff feedback used in this paper each round. Also, that lower bound applies to general query strategies, not just conventional SPSA. Reusing past payoffs can reduce variance, but that alone does not establish that an information-theoretic lower bound has been surpassed under the same model.
We understand your concern that the lower bound of Shamir (2013) concerns independently noisy payoff observations for general querying strategies (including using previous observations), while our setting uses exact payoff observations. We agree that this explanation is not on point, so we removed it altogether in our revision.
The other comparison is the claim in the abstract and Contribution 3 on page 2 that the rate is faster than the best known rate in the bounded, strongly monotone case. Theorem 3 in Huang and Hu's published journal version (IEEE Transactions on Automatic Control, 2025) already gives an rate in mean squared distance for the last played action, with arbitrarily small , under conditions including a compact convex domain and a Lipschitz pseudo-gradient. It also requires only one exact payoff observation per round. Strong monotonicity meets its monotonicity requirement, so its exponent does give a faster rate than . This result assumes a fixed bounded domain and cannot replace this paper's result on unbounded domains. But since this paper claims to improve on the fastest rate in the bounded case, it needs to address this result directly. I suggest including it in Table 1 together with its applicable conditions, and revising the rate comparisons in the abstract and Contribution 3. If the authors think it falls outside the scope of this comparison, please explain the specific differences in assumptions.
Thank you for bringing the work of Huang and Hu to our attention. We were not aware of it, and it definitely falls within scope.
In our revision, we have updated Table 1 to include the asymptotic result of Huang and Hu for compact domains, with the extra assumptions of strong-pseudomonotonicity, and one-point feedback. We have also added a discussion of their results in Section 2.2.
Finally, we have also revised the abstract and the description of our contributions to remove the claimed advantage over bounded-domain algorithms. As you stress in your comment, our primary contribution is—and remains—that of establishing payoff-based convergence guarantees on unbounded domains (which are not covered by Huang and Hu's bounded-domain result), and we have framed it precisely as such.
For your convenience, we have highlighted all these additions and revised statements in blue.
- The experiments still provide rather limited support for the rate and the stabilization mechanism. OG+SPSA uses the same residual estimation idea, so it is a useful comparison. But the difference in Figure 1c is shown for only one parameter setting, and it's not clear whether it would still hold with different step sizes. The authors have already explained that OG/OG+ use gradient feedback with Gaussian noise, while SPOG uses exact payoff feedback, so it is hard to attribute the speed differences in the plots solely to the algorithmic structure.
Our paper is primarily theoretical, so the simulations that we provided were only intended to illustrate the algorithm's behaviour under selected settings, for illustration purposes only. A systematic empirical study of the issues that you mention would be interesting, but beyond the scope of our paper, whose aim is the theoretical treatment of the question in hand.
As for the comparison between OG+ and SPOG, the starting point is that gradient information (even if noisy), is inherently more valuable for learning than exact payoff observations. This is well-documented in online learning and online convex optimization, so the fact that SPOG—a bandit, payoff-based algorithm—manages to achieve the same level of performance as a gradient-based algorithm is, in our view, an important point to keep in mind.
Beyond this, we agree that a full numerical comparison would be of interest in itself, but this would take us too far afield (and well beyond the scope of the current paper), so we defer this to future work.
Reply 3/4
The parameters listed for Figure 1c in Appendix G also violate two conditions in Assumption 3.1: is at the excluded boundary for Example 5.2, while grows logarithmically instead of tending to zero. The connection between the existing curves and the theoretical guarantees still needs to be explained.
This was an oversight, apologies. When introducing the logarithmic factors, we failed to consistently update the perturbation schedule used in the experiments and the condition. We therefore reran the experiments and replaced Figure 1 using admissible SPOG parameters. The revised Appendix G, in blue, specifies these parameters and verifies Assumption 3.1. In particular, we now use and, writing ,
\delta_n=(1000/t_n)^{2/3}(\log t_n)^2,\qquad R_n=100\log t_n.$$ These choices give $$\frac{\alpha_{n-1}R_n}{\delta_n}= 50^{2/3}\left(\frac{t_n}{t_n-1}\right)^{2/3} \frac{1}{\log t_n} \longrightarrow0.$$ In Appendix G we now also verify the remaining parameter monotonicity and summability requirements from the assumptions. The updated Figure 1c therefore illustrates SPOG with parameters exactly as in Theorem 4.1. Thank you again for catching this. --- > Appendix G already explains that the chosen exponents are close to the theoretical ones, and that the parameter sequences are shifted and rescaled to avoid decaying too quickly. I suggest further explaining how their departures from Assumption 3.1 affect the interpretation of the experiments, and adding a setting that satisfies the theoretical conditions. To examine the role of the fast process more directly, the authors could build on the existing OG+SPSA comparison by using the same projection rules and checking the effect of step-size choices, or report how the estimator's fluctuations evolve over iterations. This would more directly test the stabilization mechanism emphasized in the paper. Thank you for bringing this to our attention. We have now rerun the experiments and replaced Figure 1 using SPOG parameters satisfying Assumption 3.1. The revised Appendix G specifies the complete parameter sequences and verifies the restrictions, limits and summability conditions required by Assumption 3.1. --- > For the step sizes, Theorem 4.1 only requires Assumption 3.1, but Proposition 4.6 and Appendix F.2, which its proof relies on, use the power-law step sizes in Assumption 3.2. Please complete the argument for summability of the errors under the general step-size conditions; applying the Robbins–Siegmund theorem directly to equation (77) may be an option. Good catch, thank you. In our revision, we have corrected both arguments, cf. the blue text in Appendices F.2–F.3. Proposition 4.6 now explicitly assumes Assumptions 2.3–3.1, matching Theorem 4.1 (this was an oversight). As you will see, the revised Appendix F.2 works directly from the fast descent inequality, without using the rates from Assumption 3.2. Setting $$D_n=\frac{\beta_n}{\alpha_n}\|Z_n-z^\star(X_n)\|^2,$$ taking expectations and telescoping gives the revised version of Eq. (105), namely: $$\frac12\sum_{n=n_0}^{m}\beta_n\mathbb E\|Z_n-z^\star(X_n)\|^2 \leq \mathbb ED_{n_0} +C\sum_{n=n_0}^{m} \left(\beta_n\delta_n+\alpha_n\beta_nR_n^2+ \frac{\beta_n^3R_n^2}{\alpha_n^2}\right).$$ The initial expectation is finite because of the projections, and Assumption 3.1 makes the series on the right finite. As a result of this, the revised version Eq. (106) establishes the required summability of the calibration contribution. In the slow descent inequality (Eq. (92) in the revision), we set the monotonicity parameter to zero, which is valid for every monotone game. We note also that the multiplicative coefficient $\beta_n\delta_n$ and the additive bias term $O(\beta_n\delta_n)$ are both summable, as is the second-moment term is $O(\beta_n^2R_n^2)$, thanks to the fact that $\beta_n=o(\alpha_n)$ and $\sum_n\alpha_n\beta_nR_n^2<\infty$. Together with the calibration summability established above, these bounds allow us to apply Robbins–Siegmund, obtaining almost-sure convergence of $|X_n-x^\star|^2$ to a finite limit. Te residual summability is now stated explicitly in Proposition 4.6, Eq. (19).
Reply 1/4
Dear Reviewer Jg55,
Thank you for your time and your input. Please find our responses to your questions and remarks in the series of comments below:
This was an oversight which has been corrected in our revision, apologies for the confusion. Assumption 3.2 now correctly permits 0<d≤a<b≤1, so the choice a=d=2/3,b=1 is admissible. This choice satisfies the remaining exponent conditions, since a+b=b+d=3b−2a=5/3>1.
In more detail, the edge case b=1 requires the condition βμ/2>f, where f=min{d,a,2b−2a} is the exponent of the advertised O~(1/nf) rate. We made this explicit in our revision, and the discussion following Assumption 3.2 also clarifies that the multiplier β requires game-dependent tuning. We have also made this point more explicit in the proof of Theorem 4.2 in Appendix F.4, where we apply Chung's Lemma (Lemma B.3), with p=b, q=f and P=βμ to E∥Xn−x⋆∥2/(logn)2. The highlighted part (in blue) distinguishes clearly between the cases b<1 and b=1, and verifies the requirement P>q for Chung's Lemma.
We also took the opportunity of the revision to track the logarithmic factors directly, which we now display explicitly the revised statement of Theorem 4.2. Our revision also includes the reworked text in blue in Appendices F.1 and F.4 regarding the complete treatment of the logarithmic factors.
For your convenience, the revised argument reads as follows. Letting rn=(logn)2E∥Xn−x⋆∥2, the revised proof obtains, for sufficiently large n,
\left(1-\frac{\beta\mu}{2n^b}\right)r_n +O\\!\left(n^{-(b+f)}\right).$$ Chung’s lemma therefore applies with $p=b$, $q=f$, and $P=\beta\mu/2$; the added endpoint condition $\frac{\beta\mu}{2}>f$ thus ensures $P>q$. This gives us that $r_n=O(n^{-f})$, and hence, for $a=d=2/3$ and $b=1$, the stated condition becomes $\beta>4/(3\mu)$. Therefore, under the theorem’s remaining assumptions, SPOG's convergence rate ultimately becomes $$\mathbb E\|X_n-x^\star\|^2 =O\\!\left(\frac{(\log n)^2}{n^{2/3}}\right).$$ under the choice $a=d=2/3$ and $b=1$, which leads to $f=2/3$.