# Improved Rates for Derivative Free Gradient Play in Strongly Monotone Games

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2021.

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

- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [Zeroth-Order Stackelberg Control in Combinatorial Congestion Games](https://mlsanity.com/paper/2602.23277/) (2026)
- [Decentralized Bandit Learning of Markov Perfect Equilibria](https://mlsanity.com/paper/2610.14333/) (2026)

## Abstract (arXiv)

The influential work of Bravo et al. 2018 shows that derivative free play in strongly monotone games has complexity O(d2/varepsilon3), where varepsilon is the target accuracy on the expected squared distance to the solution. This note shows that the efficiency estimate is actually O(d2/varepsilon2), which reduces to the known efficiency guarantee for the method in unconstrained optimization. The argument we present simple interprets the method as stochastic gradient play on a slightly perturbed strongly monotone game.