Wenhan Huang

PAC Learnability of Approximate Nash Equilibrium in Bimatrix Games

2021 · arXiv (Cornell University)

Computing Nash equilibrium in bimatrix games is PPAD-hard, and many works have focused on the approximate solutions. When games are generated from a fixed unknown distribution, learning a Nash predictor via data-driven approaches can be …