Countering Feedback Delays in Multi-Agent Learning
We consider a model of game-theoretic learning based on online mirror descent (OMD) with asynchronous and delayed feedback information. Instead of focusing on specific games, we consider a broad class of continuous games defined by the general equilibrium stability notion, which we call λ-variational stability. Our first contribution is that, in this class of games, the actual sequence of play induced by OMD-based learning converges to Nash equilibria provided that the feedback delays faced by the players are synchronous and bounded. Subsequently, to tackle fully decentralized, asynchronous environments with (possibly) unbounded delays between actions and feedback, we propose a variant of OMD which we call delayed mirror descent (DMD), and which relies on the repeated leveraging of past information. With this modification, the algorithm converges to Nash equilibria with no feedback synchronicity assumptions and even when the delays grow superlinearly relative to the horizon of play.
If we accept that distributed learning is interesting, then this article presents a nice treatment of distributed mirror descent in which feedback may be asynchronous and delayed. Indeed, we are presented with a provably convergent learning algorithm for continuous action sets (in classes of games) even when individual players' feedback are received with differing levels of delay; further more the regret at time T is controlled as a function of the total delay to time T.  This is a strong result, achieved by using a suite of very current proof techniques - lambda-Fenchel couplings serving as primula-dual Bregman divergences and associated tools.
I have some concerns, but overall I think this is a good paper.
- (very minor) In the first para of Section 2.2, "following learning scheme" actually refers to Algorithm 1, over the page.
- Lemma 3.2. If the concept of variational stability implies that all Nash equilibria of a game are in a closed and convex set, to me this is a major restriction on the class of games for which the result is relevant. Two example classes are given in the supplementary material, but I think the main paper should be more upfront about what kinds of games we expect the results to hold in.
- At the bottom of page 5, we are presented with an assumption (buried in the middle of a paragraph) which is in some sense the converse to Lemma 4.2. While the paper claims the assumption is very weak, I would still prefer it to be made more explicitly, and some more efforts made to explain why it's weak, and what might make it fail
- In Algorithm 2, the division by |G^t_i| is very natural. Why is something similar not done in Algorithm 1?
- (Minor) Why do we talk about "Last iterate convergence"?  This is a term I'm unfamiliar with. I'm more used to "convergence of intended play" or "convergence of actual play".
- References 15 and 16 are, I think, repeats?
- You should probably be referencing recent works e.g. [Mertikopoulos] and [Bervoets, S., Bravo, M., and Faure, M]