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

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 $\tilde{\mathcal{O}}(n^{-2/3})$ 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.