REVIEW 2 cited by
On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games
read the original abstract
We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in \cite{tat_kam_TAC}. These rates are achieved under the standard assumption of convexity of the game, strong monotonicity and differentiability of the pseudo-gradient. In particular, we show the algorithm achieves $O(\frac{1}{T})$ in the two-point function evaluating setting and $O(\frac{1}{\sqrt{T}})$ in the one-point function evaluation under additional requirement of Lipschitz continuity of the pseudo-gradient. These rates are to our knowledge the best known rates for the corresponding problem classes.
Forward citations
Cited by 2 Pith papers
-
Last-Iterate Guarantees for Learning in Co-coercive Games
Vanilla SGD achieves O(log(t)/t^{1/3}) last-iterate convergence to Nash equilibria in co-coercive games under affine noise scaling, plus almost-sure and time-average convergence.
-
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
In bandit-feedback zero-sum games, uncoupled algorithms achieve last-iterate Nash convergence at the optimal rate of O(T^{-1/4}).
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.