论文标题
关于基于回合的零和马尔可夫游戏的加强学习
On Reinforcement Learning for Turn-based Zero-sum Markov Games
论文作者
论文摘要
我们考虑为基于两者转弯的零和游戏找到NASH均衡的问题。受Alphago Zero（AGZ）算法的启发，我们开发了一种基于增强学习的方法。具体而言，我们建议将“探索”，“策略改进”和“监督学习”结合起来的探索探索 - 兴奋剂（EIS）方法，以找到与NASH平衡相关的价值功能和策略。我们确定了这种方法的足够条件，以融合和正确性。对于EIS的具体实例，将随机策略用于“探索”，将蒙特卡洛树搜索用于“策略改进”，最近的邻居用于“监督学习”，我们确定该方法找到了$ \ varepsilon $ \ varepsilon $ - appproximate-appproximate-apppro-apppro-apppro-apppro-appproxiblium nash equilibium in $ \ \ \ \ \ \ \ \ \ \ \ varepss}（\ varepsiil}（\ varepsiron）（\ varepsiron）（\ varepsiron）游戏的潜在状态空间是连续的，并且$ d $维度是二维的。这几乎是最佳的，因为我们为任何策略建立了$ \widetildeΩ（\ varepsilon^{ - （d+2）}）$的下限。
We consider the problem of finding Nash equilibrium for two-player turn-based zero-sum games. Inspired by the AlphaGo Zero (AGZ) algorithm, we develop a Reinforcement Learning based approach. Specifically, we propose Explore-Improve-Supervise (EIS) method that combines "exploration", "policy improvement"' and "supervised learning" to find the value function and policy associated with Nash equilibrium. We identify sufficient conditions for convergence and correctness for such an approach. For a concrete instance of EIS where random policy is used for "exploration", Monte-Carlo Tree Search is used for "policy improvement" and Nearest Neighbors is used for "supervised learning", we establish that this method finds an $\varepsilon$-approximate value function of Nash equilibrium in $\widetilde{O}(\varepsilon^{-(d+4)})$ steps when the underlying state-space of the game is continuous and $d$-dimensional. This is nearly optimal as we establish a lower bound of $\widetildeΩ(\varepsilon^{-(d+2)})$ for any policy.
