Learning in Games with Lossy Feedback
We consider a game-theoretical multi-agent learning problem where the feedback information can be lost during the learning process and rewards are given by a broad class of games known as variationally stable games. We propose a simple variant of the classical online gradient descent algorithm, called reweighted online gradient descent (ROGD) and show that in variationally stable games, if each agent adopts ROGD, then almost sure convergence to the set of Nash equilibria is guaranteed, even when the feedback loss is asynchronous and arbitrarily corrrelated among agents. We then extend the framework to deal with unknown feedback loss probabilities by using an estimator (constructed from past data) in its replacement. Finally, we further extend the framework to accomodate both asynchronous loss and stochastic rewards and establish that multi-agent ROGD learning still converges to the set of Nash equilibria in such settings. Together, these results contribute to the broad lanscape of multi-agent online learning by significantly relaxing the feedback information that is required to achieve desirable outcomes.
This paper certainly seems to contain some new insights and interesting results but my main complaint is that it is so ill-placed in context and literature which makes it a tough read for both the expert and non-expert. On the one hand I think the authors miss really a lot of literature both in their introduction and related work section (see below), and on the other hand (more importantly) I think there are some recent related works that are not referred to or discussed, which make it hard for the reader to grasp what now exactly the main contribution of the work is and how much is already covered in the literature.   Comments:  - The references to MAL in general in the introduction are fairly weak and oversees quite a number of important publications; the authors should give credit to the right publications where these are due. Also note that the overview paper is quite outdated and more recent overviews are available, thinking of Hernandez-Leal, Tuyls & Weiss, Bloembergen et al. (JAIR), Shoham et al. (and several of the response papers in AIJ) etc.  There is also a lot of literature on joint learning dynamics which is simply not referred to (see Bloembergen et al., Lanctot et al.)  - Related work also need a lot more references and needs to make the connection to regret-based dynamics such as the work of Klos et  al. (ECML), Lanctot et al., and e.g. NFSP etc.  - Fictitious play and n-regret have been very clearly linked (see e.g. Viosat et al., Jofani et al., Cannot and Pilouras), papers that really need to be referred and discussed; there is overlap with the work in this paper and it is not discussed.  - Some of the argumentation in the intro certainly makes sense, but a large part of the literature seems to be overlooked, and these works need to be discussed and given credit for.  - in the intro maybe good to say you don’t consider stochastic rewards.  - The reweighed online GD trick, by reweighing with probability p_i, defined as the expected value over the indicator value is not well explained. One weakness though is that it assumed the p_i’s are known (tackled in the last section though).  - The definition of the energy function really lacks some intuition; it requires an effort to follow the discussion from here on due to a lack of description of the ideas of the author(s).  - The main contributions in section 4 look nice, but I am unsure about all the the technicalities due to the compressed nature of writing this down (the supplementary material provides more clarity though)  - Update after reading author response: I am happy with the authors response but do expect them to make the changes committed to.