# On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games

arXiv: https://arxiv.org/abs/2202.11147 · HTML: https://mlsanity.com/paper/2202.11147/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2022.

## Built on by (most cited first, 4 of 4)

- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach](https://mlsanity.com/paper/2407.21294/) (2024)
- [Last-Iterate Guarantees for Learning in Co-coercive Games](https://mlsanity.com/paper/2604.19065/) (2026)

## Abstract (arXiv)

We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in citetatkamTAC. 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(frac1T) in the two-point function evaluating setting and O(frac1√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.