Abstract: We consider a model of multi-agent online learning under imperfect information, where the reward structures of agents are given by a general continuous game. After introducing a general equilibrium stability notion for continuous games, called variational stability, we examine the well-known online mirror descent (OMD) learning algorithm (a broad family of no-regret online learning algorithms) and show that the “last iterate” (that is, the actual sequence of actions) of OMD converges to variationally stable Nash equilibria. Subsequently, we look at more realistic and more challenging environments, where imperfect information exists. We look at three types of imperfect information: noisy feedback, delayed feedback and lossy feedback. We discuss various models in these imperfect-information settings, as well as how traditional online mirror descent algorithms can be adapted to yield strong convergence guarantees. Finally, we discuss some applications.

Bio: Zhengyuan Zhou is a final-year PhD candidate in Electrical Engineering at Stanford University and has received a B.E. in Electrical Engineering and Computer Sciences and a B.A. in mathematics from UC Berkeley. His research interests include learning, optimization, control, game theory and applied probability.  He will join NYU Stern Business School as an Assistant Professor.