AlphaGo Zero (AGZ) (Silver et al., 2017b) introduced a new tabula rasa reinforcement learning algorithm that has achieved superhuman performance in the games of Go, Chess, and Shogi with no prior knowledge other than the rules of the game. This success naturally begs the question whether it is possible to develop similar high-performance reinforcement learning algorithms for generic sequential decision-making problems (beyond two-player games), using only the constraints of the environment as the "rules." To address this challenge, we start by taking steps towards developing a formal understanding of AGZ. AGZ includes two key innovations: (1) it learns a policy (represented as a neural network) using supervised learning with cross-entropy loss from samples generated via Monte-Carlo Tree Search (MCTS); (2) it uses self-play to learn without training data. We argue that the self-play in AGZ corresponds to learning a Nash equilibrium for the two-player game; and the supervised learning with MCTS is attempting to learn the policy corresponding to the Nash equilibrium, by establishing a novel bound on the difference between the expected return achieved by two policies in terms of the expected KL divergence (cross-entropy) of their induced distributions. To extend AGZ to generic sequential decision-making problems, we introduce a robust MDP framework, in which the agent and nature effectively play a zero-sum game: the agent aims to take actions to maximize reward while nature seeks state transitions, subject to the constraints of that environment, that minimize the agent's reward. For a challenging network scheduling domain, we find that AGZ within the robust MDP framework provides near-optimal performance, matching one of the best known scheduling policies that has taken the networking community three decades of intensive research to develop.
This paper seeks to understand the AlphaGo Zero (AGZ) algorithm and extend the algorithm to regular sequential decision-making problems. Specifically, the paper answers three questions regarding AGZ: (i) What is the optimal policy that AGZ is trying to learn? (ii) Why is cross-entropy the right objective? (iii) How does AGZ extend to generic sequential decision-making problems? This paper shows that AGZ’s optimal policy is a Nash equilibrium, the KL divergence bounds distance to optimal reward, and the two-player zero-sum game could be applied to sequential decision making by introducing the concept of robust MDP. Overall the paper is well written. However, there are several concerns about this paper.
In fact, the key results obtained in this paper is that minimizing the KL-divergence between the parametric policy and the optimal policy (Nash equilibrium) (using SGD) will converge to the optimal policy. It is based on a bound (2), which states that when the KL-divergence between a policy and the optimal policy goes to zero then the return for the policy will approach that of the optimal policy. This bound is not so surprising because as long as certain regularity condition holds, the policies being close should lead to the returns being close. Therefore, it is an overclaim that the KL-divergence bound (2) provides an immediate justification for AGZ’s core learning algorithm. As mentioned earlier, the actual conclusion in Section 4.2 is that minimizing the KL-divergence between the parametric policy and the optimal policy by SGD will converge to the optimal policy, which is straightforward and is not what AlphaGo Zero does. This is because there is an important gap: the MCTS policy is not the same as the optimal policy. The effect of the imperfection in the target policy is not taken into account in the paper. A more interesting question to study is how this gap affect the iterative algorithm, and whether/how the error in the imperfect target policy accumulates/diminishes so that iteratively minimizing KL-divergence with imperfect \pi* (by MCTS) could still lead to optimal policy (Nash equilibrium).
Furthermore, the robust MDP view of the AGZ in sequential decision-making problems is not so impressive either. It is more or less like a reformulation of the AGZ setting in the MDP problem. And it is commonly known that two-player zero-sum game is closely related to minimax robust control. Therefore, it cannot be called as “generalizing AlphaGo Zero” as stated in the title of the paper.