Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
S. McAleer;John Lanier;Roy Fox;P. Baldi
中科院分区：
文献类型：
--
作者：
S. McAleer;John Lanier;Roy Fox;P. Baldi
当信息状态数很大时，在零和信息博弈中寻找近似纳什均衡是一个挑战。策略空间响应神谕（PSRO）是一种基于博弈论的深度强化学习算法，保证收敛到近似纳什均衡。然而，PSRO需要在每次迭代时训练强化学习策略，这对于大型游戏来说太慢了。我们通过反例和实验表明，DCH和整流PSRO，现有的两种方法来扩大PSRO，未能收敛，即使在小游戏。我们介绍管道PSRO（P2 SRO），第一个可扩展的一般方法，在大型零和信息博弈中寻找近似纳什均衡。P2 SRO能够通过维护强化学习工作者的分层管道来并行化PSRO，并保证收敛，每个训练都针对层次结构中较低级别生成的策略。我们发现，与现有的方法不同，P2 SRO收敛到一个近似的纳什均衡，这样做的速度更快，并行工人的数量增加，在各种不完美信息的游戏。我们还介绍了一个开源的环境，为拦河坝，一个变种的拦河坝与一个近似的游戏树的复杂性为10 ^{50}$。P2 SRO能够在弹幕机器人上实现最先进的性能，并击败所有现有的机器人。
Finding approximate Nash equilibria in zero-sum imperfect-information games is challenging when the number of information states is large. Policy Space Response Oracles (PSRO) is a deep reinforcement learning algorithm grounded in game theory that is guaranteed to converge to an approximate Nash equilibrium. However, PSRO requires training a reinforcement learning policy at each iteration, making it too slow for large games. We show through counterexamples and experiments that DCH and Rectified PSRO, two existing approaches to scaling up PSRO, fail to converge even in small games. We introduce Pipeline PSRO (P2SRO), the first scalable general method for finding approximate Nash equilibria in large zero-sum imperfect-information games. P2SRO is able to parallelize PSRO with convergence guarantees by maintaining a hierarchical pipeline of reinforcement learning workers, each training against the policies generated by lower levels in the hierarchy. We show that unlike existing methods, P2SRO converges to an approximate Nash equilibrium, and does so faster as the number of parallel workers increases, across a variety of imperfect information games. We also introduce an open-source environment for Barrage Stratego, a variant of Stratego with an approximate game tree complexity of $10^{50}$. P2SRO is able to achieve state-of-the-art performance on Barrage Stratego and beats all existing bots.