Title: On Synchronous, Asynchronous, and Randomized Best-Response schemes for computing equilibria in Stochastic Nash games,
Abstract: This work considers a stochastic Nash game in which each player solves a
parameterized stochastic optimization problem. In deterministic regimes,
best-response schemes have been shown to be convergent under a suitable
spectral property associated with the proximal best-response map. However, a
direct application of this scheme to stochastic settings requires obtaining
exact solutions to stochastic optimization at each iteration. Instead, we
propose an inexact generalization in which an inexact solution is computed via
an increasing number of projected stochastic gradient steps. Based on this
framework, we present three inexact best-response schemes: (i) First, we
propose a synchronous scheme where all players simultaneously update their
strategies; (ii) Subsequently, we extend this to a randomized setting where a
subset of players is randomly chosen to their update strategies while the
others keep their strategies invariant; (iii) Finally, we propose an
asynchronous scheme, where each player determines its own update frequency and
may use outdated rival-specific data in updating its strategy. Under a suitable
contractive property of the proximal best-response map, we derive a.s.
convergence of the iterates for (i) and (ii) and mean-convergence for (i) --
(iii). In addition, we show that for (i) -- (iii), the iterates converge to the
unique equilibrium in mean at a prescribed linear rate. Finally, we establish
the overall iteration complexity in terms of projected stochastic gradient
steps for computing an $\epsilon-$Nash equilibrium and in all settings, the
iteration complexity is ${\cal O}(1/\epsilon^{2(1+c) + \delta})$ where $c = 0$
in the context of (i) and represents the positive cost of randomization (in
(ii)) and asynchronicity and delay (in (iii)). The schemes are further extended
to linear and quadratic recourse-based stochastic Nash games.