International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Track H


An Efficient Algorithm for Approximating Nash Equilibrium in Zero-sum Imperfect-information Games

Ying Wen

Shanghai Jiao Tong University

Abstract:
Policy Space Response Oracle methods (PSRO) provide a general solution to learn Nash equilibrium in two-player zero-sum games but suffer from two drawbacks: (1) the computation inefficiency due to the need for consistent meta-game evaluation via simulations, and (2) the exploration inefficiency due to finding the best response against a fixed meta-strategy at every epoch. In this work, we propose Efficient PSRO (EPSRO) that largely improves the efficiency of the above two steps. Central to our development is the newly-introduced subroutine of no-regret optimization on the unrestricted-restricted (URR) game. By solving URR at each epoch, one can evaluate the current game and compute the best response in one forward pass without the need for meta-game simulations. Theoretically, we prove that the solution procedures of EPSRO offer a monotonic improvement on the exploitability, which none of existing PSRO methods possess. A desirable property of EPSRO is that it is parallelizable, this allows for highly efficient exploration in the policy space that induces behavioral diversity. We test EPSRO on three classes of games, and report a 50x speedup in wall-time and 10x data efficiency while maintaining similar exploitability as existing PSRO methods on Kuhn and Leduc Poker games.

Bio:
Ying Wen is a tenure-track Assistant Professor in John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. His research interests include machine learning, multi-agent systems and human-centered interactive systems etc. He has published over 20 research papers about machine learning on top-tier international conferences(ICML, NeurIPS, ICLR, IJCAI, and AAMAS). He has been serving as a PC member at ICML, NeurIPS, ICLR, AAAI, IJCAI, ICAPS and a reviewer at TIFS,Operational Research etc. He was granted Best Paper Award in AAMAS 2021 Blue Sky Track and the Best System Paper Award in CoRL 2020.