SDS Colloquium Series

Shi PU, Assistant Professor, School of Data Science, CUHK-Shenzhen

Junfeng WU, Associate Professor, School of Data Science, CUHK-Shenzhen

Abstract

In this talk we focus on the role played by system theory in analysis and design of learning algorithms in games. Over the years, a plethora of algorithms/dynamics have been proposed: from best-response play, (projected) gradient-play and proximal dynamics to fictitious-play, payoff-based play or Q-learning (reinforcement-learning), the list is long. Why is it that in certain game settings some algorithms work while others don’t? How can we relax their assumptions and how can we generalize them in a systematic manner?

This is a topic of increased interest in recent years. In this talk we review some of our group’s contributions towards answering them. Our approach is based on exploiting system theory principles and connections to passivity/dissipativity. We show that some popular game-theoretic algorithms can be cast as instances of a feedback interconnection between a dissipative/passive dynamical system and some game mapping. Once this is done, convergence analysis of learning dynamics follows from standard passivity theory, based on simple and concise arguments. We also discuss how passivity-inspired ideas can be used to design novel algorithms and learning dynamics, for both Nash and generalized Nash equilibrium problems. We follow with discussion of higher-order learning dynamics designed based on passivity. We close with extensions to learning for agents with intrinsic dynamics.

Biography