acceptodds
Under review as a conference paper at ICLR 2027

Simultaneously Perturbed Optimistic Gradient Methods for Payoff-Based Learning in Games

Abstract

We examine the long-run behavior of learning in a repeated game where the agents operate in a low-information environment, only observing their realized payoffs at each stage. We study this problem in the context of monotone games with unconstrained action spaces, where standard gradient schemes may lead to cycles. To account for the fact that only a single payoff observation can be made at each iteration we design and deploy a simultaneous perturbation gradient estimation method adapted to the challenges to the problem at hand, namely unbounded action spaces, gradients and rewards. We find that a two-timescale approach is effective at controlling the (unbounded) noise introduced by payoff-based gradient estimators in this setting. We show that the proposed simultaneously perturbed optimistic gradient (SPOG) algorithm converges to equilibrium with probability 1. In addition, by developing a new method to assess the rate of convergence of two-timescales stochastic approximation, we show that SPOG converges at rate in strongly monotone games. To the best of our knowledge, this is the first convergence rate result for games with unbounded action spaces, and it is faster than the sharpest known convergence rates for single-observation, payoff-based learning in strongly monotone games with bounded action spaces.

Primary area:
learning theory
Keywords:
Game theory, learning theory, multi-agent reinforcement learning, two-timescales stochastic approximation, stochastic approximation, monotone games, Nash equilibrium

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Jg55OpenReview ↗
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 XnX_n to a Nash equilibrium in the merely monotone case, and claims a O~(n−2/3)\widetilde O(n^{-2/3}) 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 O~(n−2/3)\widetilde O(n^{-2/3}) rate is not fully covered by the parameter range in the current theorem. I noticed that Assumption 3.2 on page 6 requires 0<d≤a<b<10<d\le a<b<1, but the parameters used in the main text to obtain the 2/32/3 exponent are a=d=2/3, b=1a=d=2/3,\ b=1. According to the exponent f=min⁡{d,a,2b−2a}f=\min\{d,a,2b-2a\} in Theorem 4.2, within the parameter range stated in the paper, 2/32/3 is only a supremum that can be approached. Yet equation (7) on the same page explicitly gives a O~(n−2/3)\widetilde O(n^{-2/3}) guarantee in mean squared distance, which does not follow directly from the current theorem. Simply extending the parameter range to include b=1b=1 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 O~(n−2/3)\widetilde O(n^{-2/3}) 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 O(n−1+ε)O(n^{-1+\varepsilon}) rate in mean squared distance for the last played action, with arbitrarily small ε>0\varepsilon>0, 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 2/32/3. 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: γ=1/2\gamma=1/2 is at the excluded boundary for Example 5.2, while αn−1Rn/δn\alpha_{n-1}R_n/\delta_n 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
  1. 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.

  2. 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

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:


  1. The headline O~(1/n2/3)\tilde O(1/n^{2/3}) rate is not fully covered by the parameter range in the current theorem. Assumption 3.2 requires 0<d≤a<b<10<d≤a<b<1, but the parameters used in the main text are a=d=2/3a=d=2/3 and b=1b=1. [...] The authors need to make these conditions explicit and complete the treatment of the logarithmic factors to fully support the claimed O~(1/n2/3)\tilde O(1/n^{2/3}) rate. [...]

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≤10<d \le a < b \le 1, so the choice a=d=2/3,b=1a=d=2/3, b=1 is admissible. This choice satisfies the remaining exponent conditions, since a+b=b+d=3b−2a=5/3>1a+b=b+d=3b-2a=5/3>1.

In more detail, the edge case b=1b=1 requires the condition βμ/2>f\beta \mu / 2 > f, where f=min⁡{d,a,2b−2a}f=\min\{d,a,2b-2a\} is the exponent of the advertised O~(1/nf)\tilde O(1/n^f) rate. We made this explicit in our revision, and the discussion following Assumption 3.2 also clarifies that the multiplier β\beta 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=bp=b, q=fq=f and P=βμP=\beta\mu to E∥Xn−x⋆∥2/(log⁡n)2\mathbb E\|X_n-x^\star\|^2/(\log n)^2. The highlighted part (in blue) distinguishes clearly between the cases b<1b<1 and b=1b=1, and verifies the requirement P>qP>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=E∥Xn−x⋆∥2(log⁡n)2,r_n=\frac{\mathbb E\|X_n-x^\star\|^2}{(\log n)^2}, the revised proof obtains, for sufficiently large nn,

\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$.
  1. 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 O(n−1+ε)O(n^{{−1+ε}}) rate in mean squared distance for the last played action, with arbitrarily small ε>0ε>0, 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 2/32/3. 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.


  1. 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.

The parameters listed for Figure 1c in Appendix G also violate two conditions in Assumption 3.1: γ=1/2\gamma=1/2 is at the excluded boundary for Example 5.2, while αn−1Rn/δn\alpha_{n-1} R_n / \delta_n 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 γ=1/2\gamma=1/2 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 γ=0.2\gamma=0.2 and, writing tn=n+105t_n=n+10^5,

\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).
Reviewer_YAbdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPOG, an optimistic gradient method for payoff-based learning in monotone games with unbounded action spaces. It combines a gradient estimator that reuses previous payoff observations, two-timescale updates, and projections onto slowly expanding balls. The authors establish almost-sure convergence of the slow iterates to a Nash equilibrium and claim a convergence rate of (\widetilde O(n^{-2/3})) for strongly monotone games. Numerical experiments illustrate the method on two low-dimensional games.

Critical strengths
  1. Extending payoff-based learning guarantees to unbounded action spaces addresses a meaningful limitation of existing work.

  2. The algorithm and analysis specifically address the control of the gradient estimator and the tracking error between the two timescales.

Critical weaknesses
  1. The experiments illustrate convergence but do not clearly establish when unbounded action spaces create difficulties for existing methods or when the proposed components are necessary.

  2. Although parameter values are provided, sensitivity to the learning rates, perturbation radius, and projection envelope is not sufficiently explored.

  3. Some claims and assumptions appear inconsistent, and incorrect cross-references and extensive numbering of intermediate equations make the arguments harder to follow and check. For example, Section 4.4 refers to “Propositions 4.6 and 4.6,” and identifies the contractive coefficient as Eq. (12b), which appears to refer instead to Eq. (12a).

Questions for authors
  1. Could the authors clarify the conditions for the best rate when b=1b=1? Assumption 3.2 requires b<1b<1, while the recommended setting uses b=1b=1. For the recurrence in Appendix F.4, applying Chung's lemma to obtain the exponent f−εf-\varepsilon requires βμ/2>f−ε\beta\mu/2 > f-\varepsilon. Also, how does the O(n−f+ε)O(n^{-f+\varepsilon}) bound in Eq. (94) imply the O~(n−f)\widetilde{O}(n^{-f}) bound in Eq. (95)?

  2. Eq. (58) uses

    \leq \|v(Z_n)-v(z^\star(X_n))\|^2,$$ which does not hold in general. Could the authors correct this step and explain whether the subsequent bounds remain valid?
5 comments

Dear Reviewer YAbd,

Thank you for your time and your input. Please find our responses to your questions and remarks in the series of comments below:


The experiments illustrate convergence but do not clearly establish when unbounded action spaces create difficulties for existing methods or when the proposed components are necessary.

In the unconstrained case, the main issue is the stability of an algorithm: a cascade of "bad" noise realizations could drive the iterates of the algorithm very far from equilibrium, and recovering from such a cascade could be, in principle, impossible. As we explain in Section 3, this is the main reason for introducing the various projection guardrails that we did (like SPOG's slowly-expanding envelopes); in games with compact domains, this is of course not needed because the induced sequence of play is, de facto, bounded.

Because of this, algorithms that have been designed for compact domains do not implement any boundedness guardrails and, as such, they are susceptible to instabilities when transferred to unbounded domains. We did not include a collapse of this kind in our numerical experiments because we felt that this would be an unfair comparison for any algorithm designed to work with a compact domain (many of which are tuned with prior knowledge of the game's diameter, which, of course, is infinite in the unconstrained case).

As for the various components of SPOG, they have complementary roles and objectives:

  • The previous-payoff subtraction mechanism helps control the variance of the estimator.
  • The γ\gamma-damped fast dynamics provide a stable calibration target, while timescale separation controls the calibration error
  • Finally, as we explain above, the expanding projection envelopes provide deterministic control on the iterates of the algorithm (and thus on the encountered gradients and payoffs), while eventually accommodating any fixed equilibrium. All of the above components are necessary for the analysis—and, in fact, they dovetail in an essential way.

Although parameter values are provided, sensitivity to the learning rates, perturbation radius, and projection envelope is not sufficiently explored.

We revised the discussion following Assumption 3.2 to explicitly distinguish between game-independent exponent choices and the game-dependent tuning of γ\gamma and β\beta.; in particular, 0<γ<min⁡{12L,12GN}0 < \gamma < \min\{\frac{1}{2L}, \frac{1}{2G\sqrt{N}}\} and the optimal b=1b=1 rate requires β>4/(3μ)\beta>4/(3\mu). We briefly discuss how the requirement on γ\gamma might be circumvented by implementing a variable γn\gamma_n, converging to zero on a third, even slower, timescale, but a detailed analysis would sidetrack the main narrative of the paper, so we believe it is better to defer it to future work.

As for the more general parameter conditions in Assumption 3.1, the main requirements to keep in mind are

\qquad \frac{\alpha_{n-1}R_n}{\delta_n}\to0.$$ These conditions leave open a wide array of parameter schedules, so the parameter choice is quite robust, and sensitivity is not an issue. We briefly mention this in our discussion of the transient regime in Remark 4.3: relaxing the perturbation-radius decay $\delta_n$ can improve the theoretical bound on the variance-control transient, at the cost of a weaker asymptotic rate $\mathcal O(n^{-2/3+\epsilon})$, for any small $\epsilon > 0$. This remark is intended to offer an analytical insight into the tuning trade-offs, and we would be happy to expand on it if you think further details are warranted. --- > Some claims and assumptions appear inconsistent, and incorrect cross-references and extensive numbering of intermediate equations make the arguments harder to follow and check. For example, Section 4.4 refers to “Propositions 4.6 and 4.6,” and identifies the contractive coefficient as Eq. (12b), which appears to refer instead to Eq. (12a). Thank you for catching these typos! We did a detailed pass, briefly as outlined below: * **Corrected proposition reference in Section 4.4**: The blue text replaces the typo “Propositions 4.6 and 4.6” with a precise explanation using Proposition 4.6 and the fixed-point identity: a subsequential limit is shown to be a Nash equilibrium, followed by convergence of the entire sequence. * **Corrected contractive coefficient**: Section 4.4 now explicitly writes $1-\mu\beta_n+\beta_n\delta_n$, which appears in revised Eq. (20a)—formerly Eq. (12a)—and specifies that it is contractive for sufficiently large $n$. * **Clarified assumptions and proof dependencies**: The blue revisions to Proposition 4.6. and its proof establish the gradient summability result displayed in equation (19) under Assumptions 2.3-3.1 aligning the proposition with its use in Theorem 4.1.

Could the authors clarify the conditions for the best rate when b=1b=1? Assumption 3.2 requires b<1b<1, while the recommended setting uses b=1b=1.

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≤10<d \le a < b \le 1, so the choice a=d=2/3,b=1a=d=2/3, b=1 is admissible. This choice satisfies the remaining exponent conditions, since a+b=b+d=3b−2a=5/3>1a+b=b+d=3b-2a=5/3>1.

In more detail, for b=1b=1, Theorem 4.2 requires βμ/2>f\beta \mu / 2 > f, where f=min⁡{d,a,2b−2a}f=\min\{d,a,2b-2a\}, in order to attain the advertised O~(1/nf)\tilde O(1/n^f) rate. This additional condition is sufficient to establish the stated rate of convergence at the endpoint b=1b=1. We have 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=bp=b, q=fq=f and P=βμP=\beta\mu to E∥Xn−x⋆∥2/(log⁡n)2\mathbb E\|X_n-x^\star\|^2/(\log n)^2. The highlighted part (in blue) distinguishes clearly between the cases b<1b<1 and b=1b=1, and verifies the requirement P>qP>q for Chung's Lemma.

We also took the opportunity of the revision to track the logarithmic factors directly, and we now display them clearly in the revised statement of Theorem 4.2 Namely, with a=d=2/3a=d=2/3 and b=1b=1 we get f=2/3f=2/3, and hence, under the sufficient condition β>4/(3μ)\beta > 4/(3\mu), SPOG's convergence rate is:

=O\\!\left(\frac{(\log n)^2}{n^{2/3}}\right).$$ > For the recurrence in Appendix F.4, applying Chung's lemma to obtain the exponent $f−ε$ requires $βμ/2>f−ε$. Also, how does the $O(n^{{−f+ε}})$ bound in Eq. (94) imply the $O^{{~}}(n^{{−f}})$ bound in Eq. (95)? This was also an oversight: our intention was to streamline the presentation by suppressing logarithmic factors via the $\widetilde O$ notation, but we went too fast. We took the opportunity of the revision to track the logarithmic factors directly, as you may see in the revised blue text in Appendices F.1 and F.4. In more detail, defining $$r_n=\frac{\mathbb E\|X_n-x^\star\|^2}{(\log n)^2},$$ Appendix F.4 now gives, for sufficiently large $n$ $$r_{n+1}\le \left(1-\frac{\beta\mu}{2n^b}\right)r_n +O\\!\left(n^{-(b+f)}\right).$$ Chung’s lemma applies with $p=b$, $q=f$, and $P=\beta\mu/2$. Thus, at $b=1$, the condition $\beta\mu/2>f$ directly verifies $P>q$, giving $r_n=O(n^{-f})$. The revised Theorem 4.2 now explicitly states the rate $$\mathbb E\|X_n-x^\star\|^2 =O\\!\left(\frac{(\log n)^2}{n^f}\right),$$ with no polynomial $\epsilon$-loss. For $a=d=2/3,\ b=1$, the additional condition is $\beta>4/(3\mu)$, resulting in the advertised $\widetilde O(n^{-2/3})$ rate stated in the theorem. > Eq. (58) uses $$|v(z^{{⋆}}(X_{n})){|}^{2}−|v(Z_{n}){|}^{2}≤|v(Z_{n})−v(z^{{⋆}}(X_{n})){|}^{2},$$which does not hold in general. Could the authors correct this step and explain whether the subsequent bounds remain valid? Excellent catch, thanks for noticing this. We have provided a complete replacement for this argument in our revision (without any extra assumptions), and we also detail it below for your convenience. #### Short version Our revised proof of Lemma E.1 controls the conditional bias of the cross-term arising from the original Eq. (53b) and the negative square-gradient term in the original Eq. (53c) *jointly* instead of independently. Basically, completing the square *before* bounding these terms avoids introducing the difference of squared norms in the original Eq. (57c), and therefore removes the need for the (incorrect) inequality that you pointed out in Eq. (58) of our original paper. #### Longer version Let $$A_n=(1-\alpha_n)(Z_n-z^\star(X_n)) +\gamma\alpha_n\bigl(v(Z_n)-v(z^\star(X_n))\bigr),$$ so Lipschitz continuity gives $\|A_n\|\le\|Z_n-z^\star(X_n)\|$ when $0<\alpha_n\le1$ and $\gamma L<1$. Taking the conditional expectation in revised Eq (76) and using $\mathbb E_N \xi_{n+1}=b_{n+1}$, the sum of the two terms (76b), (76c) satisfies the identity $$\begin{align} &2\gamma\alpha_n\langle b_{n+1},(1-\alpha_n)(Z_n-z^\star(X_n))-\gamma\alpha_n v(z^\star(X_n))\rangle-\gamma^2\alpha_n^2\|v(Z_n)\|^2 \\\\ &=2\gamma\alpha_n\langle b_{n+1},A_n\rangle +\gamma^2\alpha_n^2\|b_{n+1}\|^2 -\gamma^2\alpha_n^2\|v(Z_n)+b_{n+1}\|^2. \end{align}$$ Dropping the non-positive square and applying Young’s inequality then yields $$\gamma\alpha_n\delta_n\|Z_n-z^\star(X_n)\|^2 +\left(\gamma^2\alpha_n^2+\frac{\gamma\alpha_n}{\delta_n}\right) \|b_{n+1}\|^2.$$ The corrected argument recovers original Eq. (59), now Eq. (82), by conservatively enlarging the remaining coefficient $\gamma^2L^2\alpha_n^2$ to $2\gamma^2L^2\alpha_n^2$. Thus the fast-descent estimate and subsequent time-rescaled bound remain valid. Note that Lemma E.1 now explicitly applies for sufficiently large $n$, ensuring that $\alpha_n\le1$; as for the condition $\gamma L<1$, this already follows from Assumption 3.1. ---

Thank you again for your time and comments. We remain at your disposal for any clarifications, and we are looking forward to a constructive discussion.

Kind regards,

The authors

Reviewer_p2PpOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers learning Nash equilibria in unconstrained monotone games when each player observes only its own realized payoff. It introduces Simultaneously Perturbed Optimistic Gradient (SPOG), combining an adjusted simultaneous-perturbation estimator, which subtracts the previous payoff observation, with a two-timescale optimistic update and projections onto slowly expanding balls. The authors prove almost-sure last-iterate convergence in monotone games and claim an Õ(n^{-2/3}) rate in expected squared distance under strong monotonicity. Two simple two-player games illustrate the behavior relative to optimistic first-order and zeroth-order schemes.

Critical strengths
  • The paper studies last-iterate convergence in unconstrained monotone games using only one payoff observation per iteration, addressing a difficult problem in payoff-based learning.
  • The paper establishes almost-sure convergence under monotonicity and derives an asymptotic (\tilde O(n^{-2/3})) rate under strong monotonicity, supported by a detailed stochastic-approximation framework.
Critical weaknesses
  • The claimed optimal rate uses (b=1), while Assumption 3.2 requires (b<1). The stated (\tilde O(n^{-2/3})) guarantee is therefore not directly covered by the theorem's assumptions.
  • Appendix D.2 uses (|x|\leq R) for a product of radius-(R) player balls, although the joint norm can reach (\sqrt{N}R), leaving the fixed-point inclusion insufficiently justified.
  • Experiments cover only two deterministic toy games. Robustness to noisy payoffs and higher dimensions remains untested, while the theoretical rate may require a long asymptotic transient.
Questions for authors
  • Can the authors justify the endpoint (b=1) in Theorem 4.2 and correct the product-ball norm argument in Appendix D.2?
  • How does SPOG perform with independent payoff noise and higher-dimensional games, particularly before reaching the asymptotic regime?
3 comments

Dear Reviewer p2Pp,

Thank you for your constructive input. Please find our responses to your questions and remarks in the series of comments below:


The claimed optimal rate uses b=1b=1, while Assumption 3.2 requires b<1b<1. The stated O~(n−2/3)\tilde O(n^{-2/3}) guarantee is therefore not directly covered by the theorem's assumptions.

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≤10<d \le a < b \le 1, so the choice a=d=2/3,b=1a=d=2/3, b=1 is admissible. This choice satisfies the remaining exponent conditions, since a+b=b+d=3b−2a=5/3>1a+b=b+d=3b-2a=5/3>1.

In more detail, for b=1b=1, Theorem 4.2 requires βμ/2>f\beta \mu / 2 > f, where f=min⁡{d,a,2b−2a}f=\min\{d,a,2b-2a\}, in order to attain the advertised O~(1/nf)\tilde O(1/n^f) rate. This additional condition is sufficient to establish the stated rate of convergence at the endpoint b=1b=1. We have 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=bp=b, q=fq=f and P=βμP=\beta\mu to E∥Xn−x⋆∥2/(log⁡n)2\mathbb E\|X_n-x^\star\|^2/(\log n)^2. The highlighted part (in blue) distinguishes clearly between the cases b<1b<1 and b=1b=1, and verifies the requirement P>qP>q for Chung's Lemma.

We also took the opportunity of the revision to track the logarithmic factors directly, and we now display them clearly in the revised statement of Theorem 4.2 Namely, with a=d=2/3a=d=2/3 and b=1b=1 we get f=2/3f=2/3, and hence, under the sufficient condition β>4/(3μ)\beta > 4/(3\mu), SPOG's convergence rate is:

=O\\!\left(\frac{(\log n)^2}{n^{2/3}}\right).$$ --- > Appendix D.2 uses $|x|\leq R$ for a product of radius-$R$ player balls, although the joint norm can reach $\sqrt{N}R$, leaving the fixed-point inclusion insufficiently justified. Good catch, thanks! We corrected this error, and Appendix D.2 in our revision now uses the correct joint bound on $\|x\|$, yielding $\|z^\star(x)\|\le1+2\sqrt N R$. The revised proof (in blue) then bounds each player's component $\|z_i^\star(x)\|$ separately to establish the claimed inclusion. For your convenience, the revision is as follows: using the fixed-point identity $z_i^\star(x) = x_i+\gamma v_i(z^\star(x)$ and the gradient bound in Assumption 2.3(iv), Eq. (50) now gives $$\begin{aligned} \|z_i^\star(x)\| &\le R+\gamma G(1+\|z^\star(x)\|)\\\\ &\le R+\gamma G(2+2\sqrt N R)\\\\ &\le2R+\frac1{\sqrt N}\le3R. \end{aligned}$$ where the final inequalities use the restriction $\gamma G\sqrt N\le1/2$ from Assumption 3.1 together with $N\ge1$ and $R>1$. These componentwise bounds prove that $$z^\star\\!\left(\prod_i R\mathbb B^{D_i}\right) \subseteq\prod_i3R\mathbb B^{D_i},$$ establishing Lemma D.1 under its original assumptions. --- > Experiments cover only two deterministic toy games. Robustness to noisy payoffs and higher dimensions remains untested, while the theoretical rate may require a long asymptotic transient. Our paper is primarily theoretical, so the two games that we provided were only intended to illustrate the algorithm's behaviour under selected settings, for illustration purposes only. A systematic empirical study of these issues, including parameter sensitivity, would be interesting, but beyond the scope of our paper, whose aim is the theoretical treatment of the question in hand. --- > Can the authors justify the endpoint (b=1) in Theorem 4.2 and correct the product-ball norm argument in Appendix D.2? Please see above: both points have been fixed and revised in the paper. --- > How does SPOG perform with independent payoff noise and higher-dimensional games, particularly before reaching the asymptotic regime? Our analysis assumes unperturbed payoff observations; a full treatment of the noisy payoff case would take us too far afield, so we did not undertake it. As for the high-dimensional regime, our theoretical results accommodate general monotone games of any dimension, but Remark 4.3 introduces a theoretical tuning trade-off: namely, a slower perturbation decay improves the bound on the variance-control constant at the cost of a weaker asymptotic rate. However, a systematic assessment of the finite-time impact of this choice is difficult to obtain, especially since we focus on the behavior of the generated sequence of play (which has no inherent averaging mechanism). Examining the resulting transient would be a very interesting question for future research, we agree. --- Thank you again for your time and comments. We remain at your disposal for any clarifications, and we are looking forward to a constructive discussion. Kind regards, The authors

Thanks for the explanation and clarification. The proof issues are resolved, but my concern about the limited experiments remains, so I will keep my score.

AuthorsOpenReview ↗

Added experiments

Dear reviewer p2Pp,

Thank you for your time and your reply. We were very glad to see that your concerns about the proofs were resolved!

Regarding our experiments: since this is your only lingering concern, we undertook a significant expansion of Section 5 and Appendix G with a new series of numerical results to provide further empirical evidence on the robustness and scalability of SPOG.

Specifically, we added a series of runs for large games (10210^2 dimensionality), a sensitivity analysis for the various parameter tunings of SPOG, and a robustness check for the case where the players' payoff observations are perturbed by noise. Our experiments cover both strongly and merely monotone games and, despite the longer transients in some edge cases, demonstrate the convergence envelope of SPOG, in line with (and complementing) our theoretical guarantees.

We hope that these additional results address your remaining concerns about the breadth of our numerical evaluation.

Please let us know if you have any remaining questions!

Kind regards,

The authors

PS: You will find the new simulations and experiments in the revised pdf of our paper (highlighted in blue).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.