ECE 290 Seminar: Reinforcement Learning for Large-Scale Games

Presenter: Dr. Joao Hesphanha, Distinguished Professor, University of California, Santa Barbara

Description: This talk addresses the use of reinforcement learning in two-player zero-sum Markov games with finite but large state spaces, for which the goal is to find minimax policies with “modest”’ computation. We use the qualifier “modest” to mean that we seek to certify policies as optimal without exploring the full state-space of the game.
The approach followed is strongly motivated by Q-learning, which was proposed in the late 1980s to extend the single-player dynamic programming principle to model-free reinforcement learning by eliminating the need for a known transition model. Extensions of Q-learning to two-player zero-sum games appeared shortly after. Since then, most of the work devoted to proving correctness of Q-learning relies on establishing that its iteration converges to a unique fixed-point of a Bellman-like equation, which generally requires exploring the full state-space.
We will see that, for zero-sum games, it is possible to construct provably correct optimal policies using algorithms inspired by Q-learning, without requiring convergence of the Q function over the whole state-space. In fact, the samples used to update the Q-function may not even explore the whole set of reachable states and, for certain classes of games, the fraction of explored states gets smaller and smaller as the size of the state-space increases.

Bio: João Pedro Hespanha received his Ph.D. degree in electrical engineering and applied science from Yale University, New Haven, Connecticut in 1998. From 1999 to 2001, he was Assistant Professor at the University of Southern California, Los Angeles. He moved to the University of California, Santa Barbara in 2002, where he currently holds a Distinguished Professor position with the Department of Electrical and Computer Engineering.

Dr. Hespanha is a Fellow of the International Federation of Automatic Control (IFAC) and of the IEEE. He was an IEEE distinguished lecturer from 2007 to 2013. His current research interests include multi-agent control systems; game theory; optimization; distributed control over communication networks (also known as networked control systems); stochastic modeling in biology; and network security. Additional information about his research and publications available at https://web.ece.ucsb.edu/~hespanha/.

Hosted by: Professor Soumya Bose, ECE Department

Zoom Link: https://ucsc.zoom.us/j/97975378707?pwd=ljcgaCfhMmhZ88Vt5dqQUBVQRjehOx.1

Room: E2-192