April 7, 2023 11:00 am – 12:00 pm
Location: TSRB auditorium
Dr. Zaiwei Chen
CMI postdoctoral fellow
The Computing + Mathematical Sciences (CMS) Department
California Institute of Technology
Abstract
We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which combines a discrete and doubly smoothed variant of the best-response dynamics with temporal-difference (TD)-learning and minimax value iteration. The resulting dynamics are payoff-based, convergent, rational, and symmetric among players. Our main results provide finite-sample guarantees. In particular, we prove the first-known $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexity bound for payoff-based independent learning dynamics, up to a smoothing bias. In the special case where the stochastic game has only one state (i.e., matrix games), we provide a sharper $\tilde{\mathcal{O}}(1/\epsilon)$ sample complexity. Our analysis uses a novel coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.
Biography
Dr. Zaiwei Chen is currently a CMI postdoctoral fellow in The Computing + Mathematical Sciences (CMS) Department at California Institute of Technology, hosted by Dr. Adam Wierman and Dr. Eric Mazumdar. Zaiwei obtained a Ph.D. degree in Machine Learning, an M.S. degree in Mathematics, and an M.S. degree in Operations Research from Georgia Institute of Technology, where he was advised by Dr. Siva Theja Maguluri and Dr. John-Paul Clarke. Before that, Zaiwei obtained his B.S. degree in Electrical Engineering at Chu Kochen Honors College, Zhejiang University.
Zaiwei was a recipient of the Simoudis Discovery Prize, and was named a PIMCO Postdoctoral Fellow in Data Science in 2022. His Ph.D. thesis won the Sigma Xi Best Ph.D. Thesis Award, and was selected as a runner-up for the 2022 SIGMETRICS Doctoral Dissertation Award. Before that, Zaiwei received the ARC-TRIAD Student Fellowship in 2021, and was selected as as one of 7 nominees to represent Georgia Institute of Technology at the 2021 Schmidt Science Fellows Award Competition. A proposal based on his research received The IDEaS-TRIAD Research Scholarship in 2020.
