Title: UNDERSTANDING & GENERALIZING ALPHAGO ZERO

Abstract: 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.

1. INTRODUCTION:

In 2016, AlphaGo (Silver et al., 2016) became the first program to defeat the world champion in the game of Go. Soon after, another program, AlphaGo Zero (AGZ) (Silver et al., 2017b) , achieved even stronger performance despite learning the game from scratch given only the rules. Starting tabula rasa, AGZ mastered the game of Go entirely through self-play using a new reinforcement learning algorithm. The same algorithm was recently shown to achieve superhuman performance in Chess and Shogi (Silver et al., 2017a) . The goal of this paper is to develop a formal understanding of AGZ's learning algorithm, and to extend it to sequential decision problems beyond two-player games.

Overview of AGZ. AGZ is designed for a two-player zero-sum game such as Go. The core idea of AGZ is to generate training data from games of self-play, and use this data to train the policy via supervised learning. Specifically, AGZ uses a combined policy and value network architecture, i.e., a single neural network g θ with parameters θ. The input to the network is the state s, which encodes both the current player and the state of the game (e.g. board configuration in Go). The network then outputs g θ (s) = (π θ , v θ ), where the vector π θ (•|s) represents a probability distribution over the possible moves, and v θ is a scalar value representing the probability of the current player winning.

To generate the training data, AGZ simulates the game multiple times (starting with empty board in Go). During each simulation, AGZ plays the game against itself. That is, for each player's turn, it uses the current policy network g θ aided by a Monte-Carlo tree search (MCTS) (Kocsis & Szepesvári, 2006; Kocsis et al., 2006; Browne et al., 2012) to generate the next move. Specifically, for the current player and state, MCTS outputs a distribution π(•|s) over all possible actions, and AGZ picks an action by randomly sampling from this distribution. This generates a training data point (s, π(•|s), z), where z is a reward assigned retroactively based on whether the player taking the action won (+1) or lost (-1) that particular game.

With the training data obtained as above, the neural network parameters θ are continuously updated with a mini-batch of data M , sampled uniformly among all time-steps of the most recent game(s) of self-play. In particular, the parameters θ are optimized by stochastic gradient descent on the following 2 -regularized loss function that sums over mean-squared error and cross-entropy loss respectively,

EQUATION

where the quantity π(•|s) log π θ (•|s) represents the cross-entropy or KL divergence between the two distributions. The pseudocode describing the above algorithm is provided in Appendix A.

In (Silver et al., 2017b) , authors refer to MCTS as a "strong policy improvement operator". The intuition is that, starting with the current policy, MCTS produces a better target policy for the current state. Thus training the neural network to minimize cross entropy loss with respect to the target policy on the current state is a form of policy iteration (Sutton & Barto, 1998) , which will hopefully improve the neural network policy. Although this explanation seems natural, and is intuitively appealing, it is not at all clear why this MCTS-driven policy iteration should work.

The questions. We are interested in three key unanswered questions about AGZ:

Question 1. What is the optimal policy that AGZ is trying to learn?

We would like a formal model to understand how learning via self-play impacts the policy to which AGZ converges.

Question 2. Why is minimizing cross-entropy (or KL divergence) the right objective?

We seek to precisely characterize the distribution under which cross-entropy should be evaluated, and derive quantitative performance guarantees that explain what optimizing for this metric achieves.

Question 3. How does AGZ extend to generic sequential decision-making problems?

In generic sequential decision-making, the agent chooses actions and earns rewards while the state evolves per the environment. This is different from two-player zero-sum games for which AGZ was designed.

Summary of results.:

As the main contribution of this work, we answer all of the above questions.

AGZ's optimal policy is a Nash equilibrium. We study AGZ's learning algorithm under the formalism of two-player Markov games. The notion of self-play naturally defines the optimal policy as a Nash equilibrium for the two-player zero-sum game. That is, AGZ is attempting to learn this Nash equilibrium. See Section 2 and Section 4 for the details.

KL divergence bounds distance to optimal reward. AGZ uses the cross-entropy (or KL divergence) metric as a loss function for the supervised learning. To justify this theoretically, we develop a novel bound on the difference between the reward associated with two policies in terms of the cross-entropy distance between them. Specifically, let π = (π 1 , π 2 ) denote game-playing policy, where π 1 and π 2 are the policies of the respective players (e.g. the Black player and the White player in Go). We bound the difference between the cumulative discounted reward (i.e., the "return") achieved with an arbitrary policy π(•|s) compared to the optimal policy π * (•|s) (i.e., Nash equilibrium) in terms of the expected KL divergence between π(•|s) and π * (•|s). The expectation is with respect to states sampled according to rollouts with the optimal policy π * . The bound has the following form:

EQUATION

where R(π) and R(π * ) are the returns for policies π and π * respectively, C is a constant, I(s) denotes the player to play at state s, and ρ π * (s) is the appropriately normalized state visit frequencies when actions are taken according to policy π * . See Section 3 for precise definitions and details. In the process, we establish an invariant for Markov games that is equivalent to the result by (Kakade & Langford, 2002) established for the MDP setting (see Appendix D).

This result provides an immediate justification for AGZ's core learning algorithm. Notice that if the expected KL divergence between a given policy and the optimal policy (i.e. Nash equilibrium) goes to 0, then the return for that policy must approach that of the optimal policy. Therefore, if MCTS produces reasonable estimates of the optimal policy for the states that are sampled, then supervised learning with cross entropy loss for states sampled via the MCTS target policy should ideally converge to the desired optimal policy (i.e. Nash equilibrium). Interestingly enough, prior work has shown that MCTS asymptotically converges to the optimal actions in both two-player zero-sum games (Kocsis et al., 2006) as well as discounted MDPs (Chang et al., 2005; Kocsis & Szepesvári, 2006) .

Robust MDP as a two-player game. To extend AGZ beyond the two-player game setting, we introduce a robust MDP framework. As in a standard MDP, the agent chooses an action given the current state to earn a reward, and the state makes a transition according to the environment. In a traditional MDP, state transitions occur as per an (un)known fixed Markov kernel. In the robust MDP, the transition of state is decided by "nature," a separate decision maker that selects state transitions subject to environmental constraints. The goal of the agent is to choose actions to maximize the long-term reward, while the goal of nature is to choose state transitions (subject to environmental constraints) to minimize the long-term reward earned by the agent. In effect, robust MDP is a two-player zerosum game between the agent and nature. By transforming generic sequential decision-making to a two-player game, we can apply AGZ to a much broader class of problems. We note that a similar adversarial view has been explored recently to model reinforcement learning as simultaneous games (Pinto et al., 2017) . Our theoretical results provide new insights about such adversarial approaches in both turn-based and simultaneous game models.

Empirical results. Is the robust MDP framework useful in practice? To answer this question, we consider the challenging problem of learning a scheduling algorithm for an input-queued switch, see McKeown (1999); McKeown et al. (1999) ; Giaccone et al. (2002) ; Shah & Wischik (2006) ; Shah et al. (2012) ; Maguluri & Srikant (2016) . Like a traffic junction, the role of an input-queued switch is to schedule the transfer of incoming packets to outgoing ports, e.g. across a network switch or a data center. In an input-queued switch with n incoming/outgoing ports, scheduling involves selecting one of the n! possible matchings between inputs and outputs. The goal is to transfer as many packets as possible across the switch while minimizing the packet delay. Scheduling algorithms for input-queued switches have been the subject of intensive research effort in the networking community, including attempts using approximate dynamic programming Moallemi et al. (2008) . This is because on one hand, input-queued switch is like the E-coli of network scheduling; progress on scheduling input-queued switches has provided many insights about more general network scheduling problems.

On the other hand, the problem is of great importance in its own right in practice.

We utilize the framework of robust MDP along with the AGZ algorithm to find a scheduling policy that attempts to minimize the average packet delay for any admissible packet arrival process to the switch. The resulting policy performs nearly as well as the best known policy in the literature (cf. Shah & Wischik (2006) ; Shah et al. (2012); Maguluri & Srikant (2016) ) and provides performance that is close to the fundamental lower bound. This is remarkable especially given that an equivalent policy was discovered after an intensive effort by experts spanning over three decades of research. See Section 5 for details.

In summary, this paper serves as a first attempt towards a principled understanding of AGZ under minimal assumptions. Given the large body of prior work in the context of decision making, we provided a brief overview of the most closely related previous work, and defer additional discussion of related work to Appendix B.

2. TWO-PLAYER GAME, ROBUST MDP & NASH EQUILIBRIUM:

We introduce a formal model to capture the essence of AlphaGo Zero (AGZ). In particular, we introduce the setting of two-player zero-sum game for which AGZ is primarily designed. Next, we shall explain how a generic MDP can be reduced to the setting of the two-player zero-sum game.

For the setting of two-player game, the ideal solution is given by the Nash Equilibrium. We posit that AGZ, in effect, is trying to learn this Nash equilibrium. The transformation of generic MDP to the setting of two-player zero-sum game allows us to extend AGZ for the setup of generic decision making. Therefore, it is sufficient to study the performance of AGZ for the setting of two-player zero-sum game to understand it's efficacy for generic setting as well.

Two-player zero-sum game. Most games, including Go, exhibit a "turn-based" feature: players take turns to make decisions. To capture this feature, we consider a two-player turn-based Markov game, where the two players alternatively take an action. Note that in general, turn-based Markov games can be viewed as a special class of stochastic games (a.k.a. Markov games) by assigning a dummy action, in each step, to the player who does not play in that step. We retain the turn-based formulation in the main text, since it is more closely aligned with the Go setting. Extension to the general Markov games is straightforward and is discussed in detail in Appendix E.

For simplicity, we denote the two players, player 1 and player 2, by P1 and P2. This game can be expressed as the tuple (S 1 , S 2 , A 1 , A 2 , r, P, γ). S 1 and S 2 are the set of states controlled by P1 and P2, respectively. For example, in Go, the two sets could be the board configurations whose current players are the Black player and the White player, respectively. Accordingly, A i (s) is the set of feasible actions for player i in any given state s ∈ S i . For turn-based games such as Go, it is typical to assume that S 1 ∩ S 2 = ∅1 . Let us denote by S = S 1 ∪ S 2 the entire state space of the game.

For each state s ∈ S, let I(s) ∈ {1, 2} indicate the current player to play. At state s, upon taking action a by the corresponding player I(s), player i ∈ {1, 2} receives a reward r i (s, a). In most two-player games such as Go and Chess, the two players play against each other, and the reward a player receives is equal to the negative reward (i.e., loss) of the other player. To reflect such structures, we henceforth focus on two-player zero-sum games where r 1 (s, a) = -r 2 (s, a). Without loss of generality, we let P1 be our reference and use the notation r(s, a) r 1 (s, a) for later definitions of value functions. The reward function is assumed to be uniformly bounded by some constant C R . In addition, let P (s, a) be the distribution of the new state after playing action a, in state s, by player I(s). Note that in Go/Chess, the state transitions are deterministic.

For each i ∈ {1, 2}, let π i be the policy for player i, where π i (•|s) is a probability distribution over A i (s). Denote by Π i the set of all policies of player i, and let Π = Π 1 × Π 2 be the set of all polices for the game. Given a policy π = (π 1 , π 2 ), the total discounted reward R(π) is given by

EQUATION

where ρ 0 : S → [0, 1] is the distribution of the initial state s 0 , and γ ∈ (0, 1) is the discount factor.

We use the following standard definition of the value function in games:

V π1,π2 (s) = E at,st+1,at+1,... ∞ k=0 γ k r(s t+k , a t+k )|s t = s ,

where a l ∼ π I(s l ) (•|s l ) and s l+1 ∼ P (s l , a l ). That is, V π1,π2 (s) is the expected total discounted reward for P1 if the game starts from state s, players P1 and P2 respectively use the policies π 1 and π 2 . A two-player zero-sum game can be seen as player P1 aiming to maximize the accumulated discounted reward while P2 attempting to minimize it.

Robust MDP as a two-player zero-sum game. We introduce setting of "robust" MDP to extend AGZ for generic decision making. Typically, the generic sequential decision making framework is captured through tuple (S, A, r, γ, P ): S is the set of all states, A is the set of all actions agent can take, r : S × A → R denotes the reward function, γ ∈ (0, 1) is discount factor, and for each (s, a) ∈ S × A, P s,a : S → [0, 1] denotes the Markov transition kernel with P s,a (s ) being the probability of transitioning into state s ∈ S from state s given action a. At each time instance t, given state s t ∈ S, agent takes action a t which leads to reward r(s t , a t ) and the nature makes the state transition to s t+1 ∈ S as per the Markov transition kernel P st,at . Given such a setting, traditionally there are two popular approaches. One, the Markov Decision Process (MDP), where one assumes the prior knowledge of nature, i.e. P , and solves for optimal policy for the agent defined through Bellman's equations and dynamic programming. This includes approaches such as policy iteration, value iteration or its variants, cf. Bertsekas et al. (2005); Bertsekas & Tsitsiklis (1995) . Second, the reinforcement learning (RL) where P is assumed to be unknown but aspects of it are learnt along-side of the optimal policy using approximate dynamic programming such as Q-learning.

In contrast, here we model nature as an adversary. Precisely, we model the decision making as a game between agent and nature. Agent is P1 and nature is P2. The agent is trying to chose action with the aim of maximizing reward while nature is trying to make state transition so that agent's reward is minimized. Of course, if nature can make arbitrary transitions then it will result into a degenerate setting where nature will always set state to the one that leads to minimal reward. In reality, there are constraints per which state can transition. Specifically, let C(s, a) ⊂ S be the set of all allowable states the transition is feasible. And nature tries to choose action a ∈ A 2 (s, a) that leads to state s ∈ C(s, a) to minimize (future) reward of the agent. Now, we can view this as a two-player zero-sum game. The player P1 is agent with possible actions A 1 = A with states S 1 = S, and denote by f (s, a) the state after selecting action a in state s. The player P2 is the nature with states S 2 = {f (s, a)|s ∈ S, a ∈ A} and actions A 2 = ∪ s∈S,a∈A A 2 (s, a). When player P1 takes action a ∈ A given state s ∈ S, the system transition to intermediate state f (s, a) and reward generated for P1 is r 1 (s, a). The player P2 receives reward r 2 (s, a) = -r 1 (s, a). Then given state f (s, a), P2 takes action a ∈ A 2 (s, a), the state transitions to s ∈ S 1 , reward generated for player P2 is r 2 (f (s, a), a ) and reward for P1 is

r 1 (f (s, a), a ) = -r 2 (f (s, a), a ). Let r(s, a) r 1 (s, a) + r 1 (f (s, a), a

). We denote by s t the states that are observed and a t ∈ A 1 be the actions taken by player P1 at time t. Then the cumulative discounted reward earned by player P1 is precisely ∞ t=0 γ t r(s t , a t ). Thus, reward of player P1 precisely matches that of the original decision making agent and the setting of decision making is precisely converted into a zero-sum game between two players, agent and nature.

Given the above transformation, in the remainder of this work, we will focus on two-player zero-sum game with interest in both the classical turn-based game as well as the robust MDP setup described. The analysis of AGZ in the two-player zero-sum game naturally will apply to the generic decision making setting through the above described transformation.

Nash equilibrium. In the game setting, we are interested in the minimax equilibrium solutions. To describe this concept, we view the value function V π1,π2 as a vector in R |S| . Given two vectors U and W , we use the notation U ≤ W to indicate element-wise comparisons. Recall that P1 is the reward maximizer while P2 is the minimizer. Definition 1. (Optimal Counter Policy) Fix a policy π 2 ∈ Π 2 for P2. A policy π 1 for P1 is said to be an optimal counter-policy against π 2 , if and only if

V π1,π2 ≥ V π 1 ,π2 , ∀π 1 ∈ Π 1 .

Similarly, a policy π 2 ∈ Π 2 for P2 is said to be an optimal counter-policy against a fix policy π

1 ∈ Π 1 for P1, if and only if V π1,π2 ≤ V π1,π 2 , ∀π 2 ∈ Π 2 .

In a two-player zero-sum game, it has been shown that the pairs of optimal policies coincide with the Nash equilibrium of this game (Patek, 1997; Hansen et al., 2013; Perolat et al., 2015) . In particular, a pair of policies (π * 1 , π * 2 ) is called an equilibrium solution of the game, if π * 1 is an optimal counter policy against π * 2 and π * 2 is an optimal counter policy against π * 1 . The value function of the optimal policy, 3)) is unique. In the sequel, we will simply refer to the strategy π * = (π * 1 , π * 2 ) as the optimal policy. Using our key result Theorem 2, in Section 4, we shall argue that AGZ in effect is trying to learn this Nash equilibrium.

V π * 1 ,π * 2 , is the unique fixed point of a γ-contraction operator Hansen et al. (2013). Consequently, the value of the equilibrium solution, R π * 1 , π * 2 = E s0∼ρ0 [V π * 1 ,π * 2 (s 0 )] (cf. Equation (

3. KEY THEOREM:

As our key result, we establish a novel bound on the difference of the expected rewards of any policy and that of the optimal one (i.e., Nash equilibrium) in terms of the KL divergence (i.e., cross entropy) of these two policies. This will play a crucial role in justifying AGZ trying to learning the Nash equilibrium as argued in Section 4.

Define ρ π (s) as the unnormalized discounted visit frequencies for state s under policy π = (π 1 , π 2 ):

EQUATION

where s 0 ∼ ρ 0 and actions a t are taken according to policy π I(st) . Note that s∈S ρ π (s) = 1/(1 -γ); let ρ π = (1 -γ)ρ π be the normalized probability distribution. It is easy to see that as γ → 1, ρ π approaches µ π , the stationary distribution induced by the policy π; in particular, ρ π * approaches µ * for large enough discount factor. Theorem 2. Given a two-player zero-sum game, for any policy π = (π 1 , π 2 ) and Nash equilibrium

EQUATION

)

where C is a constant depending only on γ and C R .

We remark that the above bound in fact holds for any pair of policies π and π. The inequality (5) corresponds to taking π = π * . The proof of Theorem 2 is provided in Appendix D.

4. ALPHAGO ZERO LEARNS NASH EQUILIBRIUM:

Using Theorem 2, we shall argue that AGZ tries to approximate an ideal policy for learning the Nash equilibrium. To that end, we first describe this ideal policy suggested by Theorem 2 and then we discuss how AGZ approximates it.

4.1. IDEAL POLICY FOR LEARNING NASH EQUILIBRIUM:

Consider a parametrized class of policies

{(π θ1 , π θ2 )|θ 1 ∈ R m1 , θ 2 ∈ R m2 } such that there exists θ * = (θ * 1 , θ * 2 ) so that (π θ * 1 , π θ * 2 ) = (π * 1 , π * 2 )

, the desired Nash equilibrium. We shall assume that such a θ * is unique that we wish to find. Theorem 2 suggests that such θ * can be found by minimizing the right-hand side of (5). To that end, define

EQUATION

The gradient algorithm for finding θ * would suggest iteratively update θ as

EQUATION

Assuming f does not have spurious stationary points, the algorithm (with appropriately decaying constants α) will converge to θ * . This is an ideal policy. Because it requires calculating ∇ θ f (θ) which involves computing expectation with respect to ρ π * , the normalized stationary distribution with respect to optimal policy. Next, we argue that AGZ implements stochastic approximation to (7).

4.2. AGZ'S APPROXIMATIONS OF IDEAL POLICY:

AGZ implements idealized policy in (7) through a sequence of approximations that we describe next. As a consequence, if all the approximations work out, then AGZ would end up finding the optimal policy, i.e the Nash equilibrium.

Optimal policy oracle via MCTS. To evaluate ∇ θ f (θ) or f (θ), it is sufficient to have access to an oracle that given a state s, it provides π * I(s) (•|s). Because, once we have access to such an oracle, starting with s 0 ∼ ρ 0 , we can sample states s t , t ≥ 1 iteratively as follows: given s t , obtain action a t ∼ π * I(st) (•|s t ), observe a new state s t+1 . Then, with respect to randomness over sampling of a t and resulting randomness in state transitions

EQUATION

EQUATION

Therefore, with access to the oracle described, stochastic approximation of ( 7) can be implemented. The pseudocode of this ideal algorithm, together with addition discussions on the form of the updates, may be found in Appendix F.

In principle, any approximate oracle with reasonable theoretical guarantees can be applied to replace the optimal oracle in practice. AGZ uses Monte Carlo Tree Search (MCTS) to obtain such an approximate oracle (Chang et al., 2005; Kocsis & Szepesvári, 2006; Kocsis et al., 2006) . MCTS has many variants; the basic version, known as UCT (UCB applied to Trees), uses ideas from UCB (Upper Confidence Bounds) algorithm to guide the tree search. For this algorithm, it has been shown that the probability of taking suboptimal actions converges to zero (Kocsis & Szepesvári, 2006) , and hence, the empirical action distribution eventually converges to the optimal action distribution π * (•|s). We also note that in AGZ's network, it has a value function component as its output. This value function is only used during the MCTS phase to guide the search (in particular, to evaluate the newly expanded nodes), rather than directly applied to select actions. That is, we could view this UCT style search, aided by the value function, as a variant of MCTS with the hope of obtaining a more efficient approximate oracle than the vanilla MCTS.

Stochastic gradient descent. A naive stochastic approximation to (7) as mentioned above may obtain many samples of the random variable on the left-hand side in (8). However, that may require a lot more simulations and could be wasteful. Alternatively, the Stochastic Gradient Descent (SGD) would suggest making bolder updates: compute and update the gradient continually. And this is precisely what AGZ implements.

Existence of and convergence to θ * . For the ideal gradient algorithm ( 7) to be able to find optimal policy, there are two key assumptions made: (1) there exists θ * so that π * = π θ * , and (2) the gradient algorithm finds such a θ * starting from any initial parameter θ. The implicit assumption made in AGZ implementation is that the policy neural network utilized is flexible enough that (1) is expected to satisfy. The assumption (2) is the mystery behind the success of any generic neural network based solution. And AGZ(-like) implementation hopes that (2) works out through various cleverness in terms of architecture choice and learning algorithm.

5. AGZ FOR ROBUST MDP -A CASE-STUDY:

AGZ has been successful in the context of two-player games. The robust MDP formulation makes it applicable to the setting of generic sequential decision making. To understand how well AGZ does when applied to robust MDP, we consider a challenging networking problem as a case-study: scheduling transfer of packets in an input-queued switch.

Background. A router or a switch in Internet or a data center has several input ports and output ports. A data transmission cable is attached to each of these ports. Packets arrive at the input ports. The function of the switch is to work out which output port each packet should go to, and to transfer packets to the correct output ports. This last function is called switching. There are a number of possible architectures; we will consider the commercially popular input-queued switch architecture.

The switch operates in discrete time. At each time slot, the switch fabric can transmit a number of packets from input ports to output ports, subject to the two constraints that each input can transmit at most one packet, and that each output can receive at most one packet. In other words, at each time slot the switch can choose a matching from inputs to outputs. In general, for an n-port switch, there are N = n 2 queues. Packets arriving at input k destined for output are stored at input port k, in queue Q k, . The schedule σ ∈ R + n×n is given by σ k, = 1 if input port k is matched to output port in a given time slot, and σ k, = 0 otherwise. By the matching constraints, the corresponding schedule set S is defined to be σ ∈ {0, 1} n×n :

n m=1 σ k,m ≤ 1, n m=1 σ m, ≤ 1, 1 ≤ k, ≤ n .

Suppose data packets arrive at queue (k, ) at rate λ k, for 1 ≤ k, ≤ n. Then, the effective load induced on the system, ρ(λ), is given by ρ

(λ) = max 1≤k, ≤n n m=1 λ k,m , n m=1 λ m, .

Robust MDP for scheduling. The robust MDP corresponding to scheduling can be formulated as follows. At each time, agent wishes to choose schedule σ ∈ S based on the system state

Q = [Q k, ] ∈ R +

n×n and earns reward equal to the negative of the sum of all queues. This reward guides the agent to minimize the average queue size.

The nature, on the other hand, determines new packet arrivals leading to changes in the system state (i.e., the queue occupancies). We restrict nature by requiring that the arrivals, or change in queue-size, belongs to set Λ(x) = {λ ∈ R + n×n : ρ(λ) ≤ x} for some fixed x ∈ (0, 1).

The constraint x < 1 is an example of an environmental constraint imposed on the nature. This constraint is required for the packet arrival process to be admissible. Specifically, for x > 1, there is no scheduling policy that can stabilize the switch queues, because at most on packet can get serviced from any input or output port.

Evaluation. Given the robust MDP formulation as explained above, we apply AGZ to the corresponding transformed two-player zero-sum game, and evaluate the performance of the resulting policy. Details of our experiments can be found in Appendix G. We compare the performance of AGZ with respect to the standard SARSA policy (Rummery & Niranjan, 1994) . We also compare it with Maximum Weight Matching scheduling algorithm parameterized by a parameter α > 0 denoted as MWM-α. MWM is a classical scheduling algorithm. Specifically, MWM-α chooses schedule σ ∈ S such that σ ∈ arg max σ∈S k, σk, Q α k, . The MWM-1 algorithm was proposed in 1990s McKeown et al. (1999) and was shown to be within factor 2 of the fundamental lower bound recently Maguluri & Srikant (2016) . It has also been argued that MWM-α improves performance as α → 0 + (Shah & Wischik, 2006) . Our evaluation results are shown in Figures 1 and 2 . We evaluate the AGZ scheduling policy on 80 different arrival traffic scenarios, each with load equal to 0.9. Figure 1 shows the empirical CDF of the average queue sizes on these 80 evaluations. As can be seen, the AGZ policy (called AdvMCTS) outperforms vanilla SARSA. It also outperforms MWM-1 and performs nearly as well as MWM-0.1. A similar conclusion is observed in Figure 2 where we compare performance of algorithms in terms of the average queue size at different loads varying between 0 and 1, averaged over 16 traffic arrival patterns. We note that the dashed line in both plots represents the fundamental lower bound, cf. Shah et al. (2012) . This performance of AGZ is remarkable given the fact that it has taken three decades of research to arrive at similar performing algorithms in the literature.

6. CONCLUSION:

Motivated to explain the success of AlphaGo Zero (AGZ), in this paper, we provide a formal framework to study AGZ. Specifically, we explain that AGZ attempts to learn the Nash equilibrium for two-player zero-sum games. In the process, we establish a novel bound on difference of reward earned under two different policies in terms of cross-entropy between the two policies for the setting of two-player games. By formulating generic sequential decision making through the framework of robust Markov Decision Process, we show how to view these problems as a two-player zero-sum game. This allows extending AGZ beyond games. We present a case-study for performance of AGZ for robust MDP in the context of input-queued switch scheduling. We find that AGZ performs remarkably well and its performance is nearly as good as the best-known scheduling policies. sample an action a t ∼ π t (•|s t ) and observe a new state s t+1 for the other player to play. 5: end for 6: Store Data: the episode terminates and an reward r L ∈ {-1, 1} is observed. Then, the data for each time step t = 0, 1, . . . , T is stored as (s t , π t (•, |s t ), z t ), where z t = ±r T is the game winner from the perspective of the current player at step t. 7: Update Parameters: when decide to update the parameters θ, sample a mini-batch M and run gradient descent:

θ ← θ -α∇ θ M -π(•|s) log π θ (•|s) + (z -v θ ) 2 + λ θ 2 B RELATED WORKS

In the recent years, deep reinforcement learning has emerged as a generic yet effective learning method, achieving remarkable performance across a variety of fields ranging from game playing (Mnih et al., 2015; Jaderberg et al., 2016; Silver et al., 2017b; a) , simulated physical tasks (Lillicrap et al., 2015; Schulman et al., 2015b) to chemistry (Segler et al., 2018 ). An important instantiation, self-play reinforcement learning, has been integrated with other techniques-including MCTS and supervised learning-to achieve superhuman performance in games without human knowledge; as exemplified by the AlphaGo Zero. The success of AlpahGo Zero has inspired some recent RL algorithms (Jiang et al., 2018; Efroni et al., 2018; Sun et al., 2018) . However, exactly capturing AlphaGo Zero and understanding the success of it is very limited beyond natural intuitions. To our best knowledge, this is the first attempt towards a principled and theoretical understanding for its underlying ingredients, under minimal assumptions.

The ideal variant of AlphaGo Zero falls into the general category of policy-based methods for reinforcement learning (Williams, 1992; Sutton et al., 2000; Marbach & Tsitsiklis, 2001; Kakade, 2002; Greensmith et al., 2004; Schulman et al., 2015a) , a line of research that receives considerable interest due to its advantage of directly parameterizing the policy. Most of the prior algorithms were obtained via directly optimizing the expected return R(π θ ) of a parameterized policy. For example, the classical REINFORCE algorithm (Williams, 1992) attempts to maximize the return by gradient ascent with unbiased estimator of the gradient ∇R(π θ ). The recent TRPO algorithm (Schulman et al., 2015a) attempts to maximize a lower bound of R(π). In contrast, the algorithm of AlphaGo Zero that we study approaches the problem indirectly: it minimizes the KL divergence (or cross entropy) between current policy π and optimal policy π * ; in this work, we argue that this step corresponds to minimizes a valid upper bound on the difference between R(π) and the optimal R(π * ).

In the practical version of the algorithm, idealized oracle is replaced with MCTS, which, by itself, is a well studied and widely applicable technique (Chang et al., 2005; Coulom, 2006; Kocsis & Szepesvári, 2006; Kocsis et al., 2006; Browne et al., 2012) . In particular, MCTS has been shown to asymptotically converge to the optimal actions in both discounted MDPs (Chang et al., 2005; Kocsis & Szepesvári, 2006) and two-player zero-sum games (Kocsis et al., 2006) . However, the interplay between policy-based learning methods and MCTS, investigated in this paper, is new.

We note that our results are applicable in the context of the two-player stochastic games which have been extensively studied in the literature, see (Littman, 1994; Patek, 1997; Hansen et al., 2013; Perolat et al., 2015) .

C PRELIMINARY FACTS:

The following inequalities are used for developing our technical results:

Jensen's Inequality: Let X be a random variable and φ be a convex function, then φ

(E[X]) ≤ E[φ(X)].

Pinsker's Inequality: Let µ and ν be two probability distributions, then the total variation distance T V (µ, ν) and the KL divergences D KL (µ µ) satisfies

T V (µ, ν) ≤ 1 2 D KL (µ, ν) Note that if µ and ν are discrete distributions, then T V (µ, ν) = 1 2 ω∈Ω |µ(ω) -ν(ω)|.

D PROOF OF THEOREM 2:

We define the state-action value or Q function associated with policy π = (π 1 , π 2 ) as follows: for each s ∈ S, a ∈ A,

Q π1,π2 (s, a) = E st+1,at+1,... ∞ k=0 γ k r(s t+k , a t+k )|s t = s, a t = a .

Define the corresponding advantage function A π1,π2 : for each s ∈ S, a ∈ A,

EQUATION

Recall that the reward function r(•, •) is assumed to be uniformly bounded by some constant C R . An immediate consequence is that for any policy π = (π 1 , π 2 ), s ∈ S, a ∈ A,

|A π1,π2 (s, a)| = |Q π1,π2 (s, a) -V π1,π2 (s)| ≤ 2 1 -γ max s ∈S,a ∈A |r(s , a )| = 2C R 1 -γ . That is, |A π1,π2 (s, a)| ≤ C A = 2C R

1-γ for each s ∈ S and a ∈ A. For two policies π = (π 1 , π2 ) and π = (π 1 , π 2 ), we can express the difference in policy performance R(π) -R(π), as a sum of per-timestep advantages over π, in the same fashion as Kakade and Langford's result (Kakade & Langford, 2002) for MDP. This is done in the following lemma, whose proof is given in Appendix D.1. Lemma 3. Given any two policies π = (π 1 , π2 ) and π = (π 1 , π 2 ), we have

EQUATION

)

where the expectation is taken over trajectories τ := (s 0 , a 0 , s 1 , a 1 . . .), and the notation E τ ∼π [•] indicates that actions are sampled from policy π = (π 1 , π2 ) to generate τ.

Using definition of unnormalized visit frequency (cf. ( 4)) we can rewrite (10) as follows:

EQUATION

)

We are now ready to prove Theorem 2. We shall focus on proving the inequality (5) for the optimal policy π * . The proof for a general policy π can be done by replacing π * with π. We shall use π as a "reference" policy in the remainder of the proof.

By taking π = π * and π = π in (11), we obtain

EQUATION

)

By taking π = π and π = π in (11), we obtain

EQUATION

)

Therefore, we have As a consequence, we have To conclude, we have

EQUATION

ρ π (s) -ρ π * (s) = γ

EQUATION

)

Concluding proof of Theorem 2: Substituting ( 15) into ( 14) yields

R(π) -R(π * ) ≤ C A 1 -γ s a ρ π * (s) π I(s) (a|s) -π * I(s) (a|s) = C A (1 -γ) 2 s (1 -γ)ρ π * (s) a π I(s) (a|s) -π * I(s) (a|s) = 2C A (1 -γ) 2 E s∼ ρπ * T V π * I(s) (•|s) π I(s) (•|s) (a) ≤ √ 2C A (1 -γ) 2 E s∼ ρπ * D KL π * I(s) (•|s) π I(s) (•|s) (b) ≤ √ 2C A (1 -γ) 2 E s∼ ρπ * D KL π * I(s) (•|s) π I(s) (•|s) ,

where (a) follows from Pinker's inequality and (b) follows from Jensen's inequality. This concludes the proof of Theorem 2.

D.1 PROOF OF LEMMA 3:

By the definition of the advantage function (cf. 9), for each policy π = (π 1 , π 2 ),

A π (s, a) = Q π (s, a) -V π (s) = E s ∼P (s,a) [r(s, a) + γV π (s ) -V π (s)] .

Therefore,

E τ ∼π ∞ t=0 γ t A π (s t , a t ) = E τ ∼π ∞ t=0 γ t r(s t , a t ) + γV π (s t+1 ) -V π (s t ) = E τ ∼π ∞ t=0 γ t r(s t , a t ) -V π (s 0 ) (16) = E τ ∼π ∞ t=0 γ t r(s t , a t ) -E s0 V π (s 0 ) = R(π) -R(π).

In above, ( 16) is the result of telescoping summation.

E STOCHASTIC GAMES:

A Stochastic Game (SG) (also called Markov Games) is a generalization of an MDP to a n-player setting. SGs are widely used to model sequential decision making in multi-agent systems. Each player controls the SG through a set of actions. In the case of a turn-based game-we use it to model the game of Go-each state is controlled by a single player. In a general SG, at each step of the game, all players simultaneously choose an action. The reward each player gets after one step depends on the state and the joint action of all players. Furthermore, the transition kernel of the SG is controlled jointly by all the players.

Consider a zero-sum two-player SG. We use the same notation for the two players as the turn-based game, i.e., P1 and P2 for player 1 and player 2, respectively. This game can be described by a tuple (S, A 1 , A 2 , P, r, ρ 0 , γ) where A 1 (s) and A 2 (s) are the set of actions player 1 and player 2 can take in state s respectively; P : S × A 1 × A 2 × S → R is the state transition probability; r : S × A 1 × A 2 → R is the reward for both players; ρ 0 is the distribution of the initial state s 0 and γ is the discounted factor. Let π i : S × A i → [0, 1] denote the randomized policy of player i, with π i (a|s) denoting the probability of taking action a given state s. This formulation has been used to model adversarial reinforcement learning Pinto et al. (2017) .

At each timestep t, both players observe the state s t and take actions a 1 t ∼ π 1 (•|s t ) and a 2 t ∼ π 2 (•|s t ). In the zero-sum game, without loss of generosity we assume that P1 gets a reward r 1 t = r t = r(s t , a 1 t , a 2 t ) while P2 gets a reward r 2 t = -r t . If P1 and P2 respectively use the stationary policies π 1 and π 2 , the cumulative reward for P1 is given by

R 1 (π 1 , π 2 ) = R(π 1 , π 2 ) = E s0 ∼ρ0 a 1 t ∼π1(•|st) a 2 t ∼π2(•|st) st+1∼P (•|st,a 1 t ,a 2 t ) ∞ t=0 γ t r(s t , a 1 t , a 2 t ) .

Each player tries to maximize his discounted cumulative reward. In this formulation, P1 aims to maximize R 1 (π 1 , π 2 ) while the goal of P2 is to minimize it. In a zero-sum two player SG, it has been shown that the pairs of optimal policies conincide with the Nash equilibrium of this game. That is, the value attained at the minimax equilibrium is the optimal value: R * = min

π1 max π2 R 1 (π 1 , π 2 ) = max π2 min π1 R 1 (π 1 , π 2 ).

Let π * = (π * 1 , π * 2 ) denote the pair of optimal policies that attain the optimal value. The result for two-player stochastic game setting is a similar upper bound as in the turn-based game case. Theorem 4. In a two-player zero-sum SG, for a policy pair π = (π 1 , π 2 ),

EQUATION

)

where C is a constant depending only on γ and C R .

The proof of Theorem 4 follows the same line of argument as that of Theorem 2. We use the following standard definitions of the state-action value function Q π1,π2 , the value function V π1,π2 and the advantage function A π1,π2 :

Q π1,π2 (s, a, a ) = E st+1,at+1,a t+1 ... ∞ k=0 γ k r(s t+k , a t+k , a t+k )|s t = s, a t = a, a t = a , V π1,π2 (s) = E at,st+1,at+1,... ∞ k=0 γ k r(s t+k , a t+k , a t+k )|s t = s , A π1,π2 (s, a, a ) = Q π1,π2 (s, a, a ) -V π1,π2 (s).

Like in the setting of turn-based games, the advantage function is uniformly bounded. Specifically, for any policy π

= (π 1 , π 2 ), s ∈ S, a ∈ A, a ∈ A, |A π1,π2 (s, a, a )| = |Q π1,π2 (s, a, a ) -V π1,π2 (s)| ≤ 2 1 -γ max s∈S,a∈A,a ∈A |r(s, a, a )| = 2C R 1 -γ .

Similar to the turn-based game setting, we can express the difference in policy performance R(π) -R(π) as a sum of per-timestep advantages over π, as stated in the following lemma. The proof is similar to that of Lemma 3 and is omitted here.

Lemma 5. Given any two policies π = (π 1 , π2 ) and π = (π 1 , π 2 ), we have

EQUATION

where the expectation is taken over trajectories τ := (s 0 , a 0 , s 1 , a 1 . . .), and the notation E τ ∼π [•] indicates that actions are sampled from policy π to generate τ.

Let ρ π be the unnormalized discounted visit frequencies, defined the same as (4):

ρ π (s) = P (s 0 = s) + γP (s 1 = s) + γ 2 P (s 2 = s) + . . . ,

Consistently, let ρ π be the corresponding normalized probability distribution. Then, analogous to the turn-based game setting, we can rewrite (18) as follows:

EQUATION

Now ( 19) implies equalities similar to (12) and ( 13). Using a policy π as the reference policy, we can bound R(π) -R(π * ) as follows:

R(π) -R(π * ) = R(π) -R(π) -R(π * ) -R(π) = s a a ρ π (s)π 1 (a|s)π 2 (a |s) -ρ π * (s)π * 1 (a|s)π * 2 (a |s) A π (s, a, a ) ≤C A s a a ρ π (s)π 1 (a|s)π 2 (a |s) -ρ * π (s)π 1 (a|s)π 2 (a |s) + ρ * π (s)π 1 (a|s)π 2 (a |s) -ρ π * (s)π * 1 (a|s)π * 2 (a |s) ≤C A s ρ π (s) -ρ π * (s) + C A s a a ρ π * (s) π 1 (a|s)π 2 (a |s) -π * 1 (a|s)π * 2 (a |s) (20)

Following identical steps of arguments utilized to bound R.H.S. of ( 14) in the proof of Theorem 2, we can obtain the bound on the first term in the R.H.S. of (20) as follows:

EQUATION

)

For each s ∈ S, a ∈ A 1 , a ∈ A 2 , we use the notation π(a, a |s) = π 1 (a|s)π 2 (a |s)

to represent the joint action distribution of the two players under the policy (π 1 , π 2 ). Substituting ( 21) into (20) yields

R(π) -R(π * ) ≤ C A 1 -γ s a a ρ π * (s) π 1 (a|s)π 2 (a |s) -π * 1 (a|s)π * 2 (a |s) = C A (1 -γ) 2 s (1 -γ)ρ π * (s) a a π 1 (a|s)π 2 (a |s) -π * 1 (a|s)π * 2 (a |s) = 2C A (1 -γ) 2 E s∼ ρπ * T V π * (•, •|s) π(•, •|s) (a) ≤ √ 2C A (1 -γ) 2 E s∼ ρπ * D KL π * (•, •|s) π(•, •|s) (b) ≤ √ 2C A (1 -γ) 2 E s∼ ρπ * D KL π * (•, •|s) π(•, •|s) = √ 2C A (1 -γ) 2 E s∼ ρπ * D KL π * 1 (•|s) π 1 (•|s) + D KL π * 2 (•|s) π 2 (•|s) ,

where (a) follows from Pinker's inequality and (b) follows from Jensen's inequality. This concludes the proof of Theorem 4.

F ADDITIONAL DISCUSSIONS ON THEOREM 2 AND THE IDEAL ALGORITHM:

Theorem 2 translates the distance between a trained policy π and the optimal one to the distance of their expected rewards. It reinforces the intuition that if the expected KL divergence for the two policies is small, then the difference of respected rewards should also be small. Crucially, note that the expectation is taken with respect to ρ π * . This fact allows one to use Monte Carlo methods to run stochastic gradient descent (SGD) for policy optimization (i.e., the upper bound), and hence, obtain a higher expected reward. The following pseudocode summarizes the ideal learning algorithm discussed in Section 4.1, which is suggested by our Theorem 2.

Algorithm 2 Supervised Policy Optimization (theoretical) 

EQUATION

which follows from the same arguments as for Theorem 2. This bound differs from (5) in that the expectation is taken with respect to ρ π rather than ρ π * . Therefore, to minimize the R.H.S. of ( 23), one would run SGD to update θ by sampling from the current policy π θ rather than from the optimal π * . As the minimization of D KL π * I(s) (•|s) π θ I(s) (•|s) can be done only approximately, it is important to focus on those states s frequently visited by the optimal policy-these are important states that tend to have higher values and hence have a larger impact on the return of a policy. Therefore, optimizing the R.H.S. of (5) as done in Algorithm 2, rather than that of (23), is more likely to require less samples and produce a solution with better generalization performance.

Additionally, we note that the bound ( 5) is no longer valid if ρπ * is replaced by an arbitrary distribution ρ. As an example, pick a particular state s 0 , and assume that ρ(s 0 ) = 1. Suppose that π equals π * at s 0 , but otherwise takes extremely bad actions. One sees that in this case E s∼ ρ D KL π * I(s) (•|s) π I(s) (•|s) = 0, but R(π) may be very far from R(π * ). This observation further demonstrates the delicacy of the bound in Theorem 2 and the importance of sampling from ρπ * . Before closing, let us remark on a subtle difference between the upper bound of Theorem 2 and what is actually optimized by the ideal algorithm, Algorithm 2. Note that based on Theorem 2, we are interested in minimizing

E s∼ρ π * D KL π * I(s) (•|s) π I(s) (•|s) .

That is, if one was to use SGD, the state should be sampled from the discounted visit frequencies ρ π * . In contrast, Algorithm 2 samples actions from µ * ; that is, states are sampled under the distribution induced by π * without discounting. However, this difference can be essentially ignored as we argue now. Let µ * be the stationary distribution under policy π * , i.e., µ * (s) = lim t→∞ P (s t = s). Notice that as γ → 1, by the definition of ρ π * (s) in ( 4), ρ π * (s) (1 -γ)ρ π * (s) → µ * (s). In practice, large γ (γ ≈ 1) is used. Therefore, the difference between the two is very minimal, which justifies that the procedure used in Algorithm 2 is a valid approximation.

Finally, as discussed in Section 4.2, in practice, the optimal oracle is replaced with an approximate version, with MCTS being one particular example. In addition, We also note that in developing such an algorithm, one could have parametrized the two policies separately in the form π = (π θ1 , π θ2 ), as presented in the ideal algorithm above, by using for example one neural network for each player's policy. Depending on current player I(s) at state s, one of the networks is chosen and the output is π I(s) (•|s). However, it is also valid if we add I(s) into the input, that is, one can use only one neural network: the input to it is (s, I(s)) and the output is interpreted as π θ (•|s, I(s)), the policy for player I(s) at state s. The theory still holds provided the network is expressive enough. The two polices π 1 and π 2 now share the same parameters θ. Such a joint parametrization corresponds to the self-play setting in AlphaGo Zero, where a single network is used and the input to it is both the current board and the player to play.

G SWITCH SCHEDULING:

G.1 BASIC SETUP Switch scheduling is a classical problem where at each time slot, a controller selects a matching between the n input ports and the n output ports to transmit packets. Figure 3 illustrates an example of an input-queued switch with three input ports and three output ports. Packets arriving at input k destined for output are stored at input port k, in queue Q k, , thus there are N = 9 queues in total. We consider the case where the new data packets are arriving at queue (k, l) at rate λ k,l for 1 ≤ k, l ≤ n, according to Bernoulli distributions. That is, the number of packets arriving at queue Q ij is a Bernoulli random variable with mean λ ij . We call the matrix λ the traffic matrix, and let us denote by Λ(x) the set of traffic matrices with effective load less than or equal to x. Overall, the queue length for each queue evolves according to:

EQUATION

)

where σ is the matching selected by the controller.

To train a robust controller, we model the nature, i.e., the arrival processes that determine the state transitions, as the adversary (the second player), whose action determines the packets' arrival rates. With this two-player setup, we now introduce the relevant quantities used during training: (a) Naturally, the state S of the switch is the current queue lengths, i.e., S = {Q ij } 1≤i,j≤N . (b) The action a of the controller is a matching σ between the input ports and the output ports. For any state S, the set of feasible actions for the controller, A(S), is exactly the set of possible matchings. (c)

The action ã of the adversary is a traffic matrix λ, and the set of actions of the adversary is the set of traffic matrices with load less than or equal to x, i.e., A d (S) = Λ(x). (d) At state S, the reward r 1 (S, A) for the controller is the negative total queue lengths after an action A (played either by the controller or the nature) is applied, i.e., r(S, A)i,j (q ij of state S ), where S is the state after an action is applied. Naturally, this reward function encourages the controller to keep queues small and hence, smaller packet delay. On the other hand, the adversary's goal is to compete with the controller by increasing the average queue size. The reward r 2 (S, A) for the adversary is always equal to -r 1 (S, A).

As a proof of concept, we consider a 3-port instance in our experiment. This means that we have 9 queues in total. We also restrict the maximum queue size to be 100. At first glance, n = 3 may seem small. However, the system actually has a huge state space with 10 18 configurations. Overall the scheduling problem is hard, even for seemingly small instances. When n = 3, there are 6 matchings, from which the controller can choose to play. To match the number of controller's actions, we also choose 6 random traffic matrices as the possible actions for the adversary. To make sure the system is stable, the 6 traffic matrices are all doubly-stochastic matrices with load x < 1.

G.2 TRAINING ROBUST CONTROLLER:

The overall training process proceeds as implied by our theoretical result. The controller, P1, and the adversary/nature, P2, take turns to pick an action: the controller schedules packets by picking one of the 6 matchings, σ, and then the state evolves to max(S -σ, 0); the adversary adds packets by selecting one of the 6 traffic matrices, λ. The number of arriving packets for each queue is then sampled according to a Bernoulli distribution with mean given by the corresponding entry in λ, and the state evolves to (S + Ber(λ)); the above process continues. Each action, either from P1 or P2, is chosen by first running a finite-time MCTS and then playing the optimal action according to the resulting policy from MCTS. The policy network of each player is trained by supervised learning with cross-entropy loss. The optimal actions returned from MCTS serves as the training data.

Policy and value networks. We train two policy networks: one for the controller P1 and one for the adversary P2. Additionally, similar to AGZ, we also train a value network V θ to help with MCTS, i.e., the optimal oracle is approximated by running a finite-time oracle that combines MCTS and a value network together. Note that this choice is largely motivated by the nature of the problem. Unlike AGZ, which is essentially an episodic game, the switch scheduling problem is a continuing task, where the system runs forever to schedule queued packets and receive new packets. The trees need to be very deep in order for the system to operate in stationary states. With the value network, one could quickly evaluate new nodes and update the statistics during tree search. This might speed up the MCTS process and hopefully, lead to a more efficient approximation for the optimal oracle. Note that only one value network is needed. In a zero-sum game, the value of the controller should be the negative value of the adversary. Finally, we remark that this overall setup indeed aligns with our theory. Only the policy networks are trained to take actions: the value network is merely used to guide our MCTS search to generate training data for the policy networks.

Training. The networks are all feed-forward neural networks. Each neural network has 2 hidden layers with 24 ReLU units each. The input to these networks is a 3 × 3 state vector, i.e., the configuration of the 9 queues. Policy networks have a softmax layer at the end with 6 output units representing a probability distribution over the 6 possible actions. After each action, the networks are trained immediately (i.e., batch size = 1). The policy networks are trained to minimize the cross-entropy loss between its output (i.e., the predicted distribution over actions) and the policy obtained from MCTS. As elaborated before, the switch scheduling problem is posed as a continuing RL task. For such problems, minimizing the average reward is a more suitable measure. We train the value network using the differential semi-gradient SARSA (Sutton & Barto, 1998) algorithm. In particular, at each time after the controller receives a reward r at a state S, the network is updated. We use Adam as our optimizer with a learning rate of 10 -4 .

MCTS.:

In each state that is either controlled by the scheduler or the adversary, an MCTS search is executed, guided by the value function V θ . The overall MCTS process is similar to the one used in AGZ. For each state controlled by the scheduler, it performs multiple iterations of MCTS. In each iteration, the basic search process uses a UCT (Kocsis et al., 2006) style approach to select the moves to traverse the tree. As in AGZ, once a new node is expanded, its value is evaluated using the value function V θ and then propagated upwards to update the value estimates for all nodes on the search path.

The path traversed during each iteration of the MCTS search tree alternates between the controller picking an action that maximizes its estimated average reward and the adversary minimizing it. At the end of the final iteration, the action from the root that has the maximum value is chosen to be the controller's action for the current step. Note that this action becomes the training data for the policy network of the controller. For each state controlled by the adversary P2, it also performs a similar MCTS, using -V θ as its value function to guide the search, and selects the traffic matrix with the maximum value from its point of view in the end. For both the controller and the adversary, we perform 500 iterations of MCTS search at each step. The MCTS search tree is restricted to a maximum depth of 10.

:

This is a reasonable assumption in general in any setting when only one player is taking a "turn" to play, since one may incorporate the "turn" of the player as part of the state, and thus by definition a player 1's state space (i.e. when it is player 1's turn) is disjoint from that of player

2's turn.

Figures and Tables:

Figure 1: Empirical CDF of the avg queue size.

First term in R.H.S. of (14): We can rewrite ρ π as followsρ π (s) = P (S 0 = s) + ∞ t=1 γ t P (S t = s|π) = P (S 0 = s) t = s|π, S t-1 = s )P (S t-1 = s |π) = P (S 0 = s) + s ) (a|s )P (s|s , a) P (S t-1 = s |π) = P (S 0 = s) + s a π I(s ) (a|s )P (s|s , a) ∞ t=1 γ t P (S t-1 = s |π) = P (S 0 = s) + γ s a π I(s ) (a|s )P (s|s , a)ρ π (s ).

s ) (a|s )P (s|s , a)ρ π (s )s a π I(s ) (a|s )P (s|s , a)ρ π * (s ) + γ s a π I(s ) (a|s )P (s|s , a)ρ π * (s )s a π * I(s ) (a|s )P (s|s , a)ρ π * (s ) ≤ γ s a π I(s ) (a|s )P (s|s , a) ρ π (s ) -ρ π * (s ) + γ s a P (s|s , a)ρ π * (s ) π I(s ) (a|s ) -π * I(s ) (a|s ) . Summation over s ∈ S on both sides yields s ρ π (s) -ρ π * (s) ≤ γ s s a π I(s ) (a|s )P (s|s , a) ρ π (s ) -ρ π * (s ) (s|s , a)ρ π * (s ) π I(s ) (a|s ) -π * I(s ) π * (s ) π I(s ) (a|s ) -π * I(s ) (a|s ) s P (s|s , a) = γ s ρ π (s ) -ρ π * (s ) + γ s a ρ π * (s ) π I(s ) (a|s ) -π * I(s ) (a|s ) .

To better appreciate the power of Algorithm 2 and Theorem 2, let us consider two closely related metrics that also upper bound |R(π) -R(π * )|. Interchanging the roles of π * and π in (5) gives the boundR(π) -R(π * ) ≤ C E s∼ρ π D KL π I(s) (•|s) π * I(s) (•|s) , which suggests optimizing the metric E s∼ρ π D KL π I(s) (•|s) π * I(s) (•|s) . Doing so is, however, of little use: since optimal policy π * I(s) (•|s) is supported only on the optimal actions, the divergenceD KL π I(s) (•|s) π * I(s) (•|s) is always +∞ unless π I(s) (•|s) is also optimal. Another possibility is to use the bound

Figure 3: An input-queued switch, and two example matchings of inputs to outputs. Packets arriving at input k destined for output are stored at input port k, in queue Q k, , thus with three input ports and three output ports, there are N = 9 queues in total.

Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems, pp. 1057-1063, 2000. some time (1600 simulations), with state s t as the root and the current player taking the first action; obtain the action distribution π t (•|s t ) based on empirical visit counts.

Table content: <table><tr><td colspan="2">Appendices</td></tr><tr><td colspan="2">Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement A PSEUDOCODE FOR ALPHAGO ZERO</td></tr><tr><td colspan="2">learning. In Reinforcement Learning, pp. 5-32. Springer, 1992.</td></tr><tr><td colspan="2">We provide the pseudocode for AlghaGo Zero in Algorithm 1, which concisely summarizes the</td></tr><tr><td colspan="2">overview in the Introduction.</td></tr><tr><td colspan="2">Algorithm 1 Training Algorithm for Each Episode</td></tr><tr><td colspan="2">1: Sampling: Suppose that the current episode ends in L steps.</td></tr><tr><td colspan="2">2: for each step t = 0, 1, . . . , L do</td></tr><tr><td>3:</td><td>run MCTS for</td></tr></table>

Peer review (iclr2019):
 The paper proposes a formal framework to claim that Alpha Zero might converges to a Nash equilibrium. The main theoretical result is that the reward difference between a pair of policy and the Nash policy is bounded by the expected KL of these policy on a state distribution sampled from the Nash policies. The paper is quite heavy on notations and relatively light on experimental results. The main theoretical results is a bit remote from the case Alpha Zero is applied to. Indeed the bound is in 1/(1-/gamma) while Alpha Zero works with gamma = 1. Also Casting a one player environment as a two player game in which nature plays the role of the second player makes the paper very heavy on notations. In the experimental sections, the only comparison with RL types algorithm is with SARSA, it would be interesting to know how other RL algorithms, perhaps model free, would compare to this, i.e. is Alpha Zero actually necessary to solve this tasks? --- p 1 * it uses the current policy network g_theta* : policy and value network. p 2 / appendix No need to provide pseudo code for alpha zero the original paper already describes that? p2 (2). It seems a bit surprising to me that the state density rho does not depend upon pi but only on pi star? p4: Not sure why you need to introduce R(pi), isnt it just V_pi (s_0) ? Also usually the letter R is used for the return i.e. the sum of discounted reward without the expectation, so this notation is a bit confusing? p5: paragraph2: I don*t quite see the point of this. p8: "~es, because at most on packet can get serviced from any input or output port.~" typo ?