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. Furthermore, we
prove that the no-regret optimization has a regret bound of
$\mathcal{O}(\sqrt{T\log{[(k^2+k)/2]}})$, where $k$ is the size of restricted
policy set. Most importantly, 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.

该研究提出了 Efficient PSRO 方法来解决传统 Policy Space Response Oracle 方法中存在的计算和探索效率低的问题，通过引入 no-regret optimization 和 parallelization 等技术，有效地优化了算法，在保证 Kuhn 和 Leduc Poker 博弈中的可利用度的情况下，提高了 50x 的速度和 10 倍的数据效率。