Search-based Reinforcement Learning through Bandit Linear Optimization

1 Introduction

Monte-Carlo tree search commonly uses UCT (Upper Confidence Bounds for Trees) [Kocsis and Szepesv´ari, 2006] or some variant thereof as the method for action selection in the search tree. One of these variants, PUCT (Polynomial Upper Confidence Bounds for Trees) [Rosin, 2011], is used in several search-based reinforcement learning (RL) algorithms, e.g. AlphaZero [Silver et al., 2017], MuZero [Schrittwieser et al., 2019] and recently Player of Games [Schmid et al., 2021]. A possible explanation for the choice for this variant in AlphaZero and subsequent algorithms is due to the fact that the PUCT action selection formula is parametrized by a prior policy, which allows for a learned prior action distribution to be utilized to guide the search procedure.

In [Grill et al., 2020]

tation inspired by ideas from MPO, a model-free policyoptimization algorithm [Abdolmaleki et al., 2018]. A key insight was that the empirical visit distribution of actions in PUCT approximates the solution of a regularized policyoptimization objective. Consequently, a method was derived to compute the exact solution to this regularized policyoptimization objective, allowing their implementation to work significantly better than the standard PUCT implementation when the amount of search iterations is low, since this setting suffers the most from the approximative nature of PUCT. Another disadvantage of PUCT arises in the domain of simultaneous move games. The straightforward extension of PUCT to this domain suffers from the same theoretical issues as Decoupled UCT (DUCT) [Tak et al., 2014], i.e. asymptotic convergence to a Nash equilibrium is not guaranteed, despite Decoupled (P)UCT performing favorably in practice compared to some algorithms that do converge to a Nash equilibrium [Tak et al., 2014]. In this work we seek to expand on the work in [Grill et al., 2020] by deriving a search-based reinforcement learning algorithm that converges to a Nash equilibrium in simultaneous move games, while having strong empirical performance at the same time.

∗Contact Author

Contributions. We analyze the implicit regularized policyoptimization objective from PUCT and find that this is equivalent to log-barrier regularization, which is a special case of Tsallis entropy [Tsallis, 1988] regularization, i.e. with the α parameter set to zero. This raises the question whether there are other values of α that would result in improved performance. Previous literature on bandit algorithms indicates that the answer to this question is affirmative. Concretely, setting α to 0.5, combined with an appropriate learning rate, achieves the theoretically optimal regret bound of O(√KT), with K being the size of the action space and T the amount of search iterations. Other values of α fail to obtain this regret bound. We find that in a certain sense, regularization with α = 0.5 combined with an appropriate learning rate corresponds to a hybrid of UCT and PUCT and we experimentally verify that this results in an increased rate of improvement for our reinforcement learning agents, both in the setting with few search iterations and beyond.

2 Background

2.1 Two-Player Zero-SumMarkov Games

We consider a finite-horizon discounted two-player zero-sum Markov game, which can be described by a tuple M = (X,A,P, r, γ): a state space X, an action space A, a transition probability function P : X × A × A → ∆(X), a reward function r : X × A × A → [0, 1] and a discount factor γ ∈ (0, 1]. A policy or strategy π is defined as a point on the n-dimensional simplex S, where n is equal to the size of the action space A. We will use the terms "policy" and "strategy" interchangeably, with the former being more common in RL literature and the latter being more common in game-playing literature. The RL problem consists in finding a policy which maximizes the discounted cumulative reward Eπθ [∑t≥0 γ t rt ].To scale the method to large environments, we assume that the learned policy πθ is parameterized by a neural network θ.

2.2 Regret and Nash Equilibria

In this work we focus on simultaneous move games, as opposed to sequential move games such as chess and Go, or games where the player plays against a non-adversarial environment, e.g. the Atari57 suite of games. The reason for our particular interest in simultaneous move games is due to the fact that the action selection strategy of AlphaZero, i.e. PUCT, does not guarantee convergence to a Nash equilibrium, i.e. a pair of policies where neither player gains by unilaterally changing its own policy. One can show this by constructing a counterexample analogously to the one in [Shafiei et al., 2009] for UCT.

To remedy this we construct an algorithm that is Hannan consistent, or equivalently: an algorithm with no external regret. We now formally define the notion of external regret used in this work.

Definition 1 (External Regret). The external regret for playing a sequence of strategies π1, ..., πT and a sequence of cost vectors g1, ..., gT , is defined as

where ∆n is the n-dimensional simplex: ∆n = {π ∈ Rn , ∑i πi = 1, πi ≥ 0}

Note that the cost vectors gt are the negation of the obtained rewards. An algorithm is said to be Hannan consistent if its external regret is sublinear as a function of T, i.e. RT = o(T), which implies that on average the algorithm performs as well as the best fixed strategy in hindsight. If both players use a Hannan consistent algorithm in self-play in a zero-sum normal form game, the average strategies chosen converge to a Nash equilibrium of the game [Blum and Mansour, 2007]. Common Hannan-consistent algorithms for simultaneous move games are Exp3 [Auer et al., 2003] and Regret Matching (RM) [Hart and Mas-Colell, 2001].

Though there is one caveat, since normal form games, or matrix games, entail only a limited subset of simultaneous move games. More generally, we are interested in results for zero-sum extensive form games with simultaneous moves, or stacked matrix games (SMG). In these games we have the additional requirement that the selection strategy needs to satisfy the guaranteed exploration condition, which ensures that the whole game tree can be covered. Moreover, one has to be careful in the way the value of child nodes are estimated, since one can construct an estimation method that fails to converge to a Nash equilibrium, despite using a Hannan consistent algorithm. Both of these results are discussed extensively in [Kovar´ık and Lis´y, 2018].

2.3 Bandit Linear Optimization

Bandit linear optimization [Abernethy et al., 2008; Hazan, 2019] can be thought of as online linear optimization in the bandit setting. The bandit setting implies that only partial information is available to each agent with regard to the valuation of strategies. More concretely, an agent observes only the scalar value g⊤ t πt in Definition 1, as opposed to the full cost vector gt. Thus, it is not possible to determine the reward for counterfactual strategies.

Just like solving a zero-sum matrix game is equivalent to solving a linear optimization problem, the case where the entries of the matrix, i.e. the Q-values, have to be estimated through sampling corresponds to a bandit linear optimization problem. In this work we utilize a notion of performing MCTS that is inspired by ideas from bandit linear optimization literature. In particular, while MCTS typically results in an empirical visit distribution, i.e. the distribution of visit counts for each action by the search, we instead store the average strategy throughout the search, where the individual strategies can be mixed, i.e. comprising multiple actions. The implications on the MCTS implementation are further detailed in Section 4.

3 Methodology

3.1 PUCT and the Logarithmic Barrier

The PUCT action selection strategy, used in AlphaZero and originally defined in [Rosin, 2011], selects the best action a∗ as follows:

where c is a numerical constant, n(x, a) is the number of times that action a has been selected from state x during the search, and Q(x, a) is an estimate of the Q-value for stateaction pair (x, a) computed from search statistics.

In Proposition 1 in [Grill et al., 2020] it is shown that this can be rewritten as

where DKL denotes the reversed KL-divergence since πθ is the target distribution, and where the learning rate λN is defined as

and where the empirical visit distribution ˆπ is defined as

In other words: a∗ is the action maximizing the partial derivative with respect to its visit count and the resulting strategy at time step t is the one-hot vector 1t(a∗ ). The empirical visit distribution ˆπ is consequently updated by incrementing na∗.

Additionally they note that, if we maximize the function over the simplex S, then instead of obtaining a discrete approximate solution, we obtain the optimal mixed strategy

We can rewrite this as

and because πθ is a constant vector we can simplify the expression as

Thus, we obtain an optimization problem that is regularized by a log-barrier, which is a regularization method that was first proposed in the bandit setting in [Foster et al., 2016]. Note that it is the approximative nature of PUCT that prevents Hannan consistency, which causes its failure to converge to a Nash equilibrium. Sampling from ¯π on the other hand, does lead to a Hannan consistent action selection algorithm, but we will see in Section 3.2 that we can utilize the Tsallis entropy to generalize to a whole family of Hannan consistent algorithms.

3.2 GeneralizationWith Tsallis Entropy

We now give the definition of the (negative) Tsallis entropy Hα(x), originally described by Tsallis [1988]:

where x is a point on a simplex. Regularization using a logbarrier happens to be a special case of regularization based on the Tsallis entropy, i.e. the case where α is zero. It is straightforward to see that if α = 0, then Hα(x) as defined above becomes meaningless, since the same value is obtained regardless of the values xi. Therefore the Tsallis entropy for α = 0 is defined asH0(x) ≜ - ∑

In the Appendix we show how this definition originates from the Hα(x) entropy formula.

A natural question to ask at this point is whether setting α to zero, like AlphaZero 1 approximately does through the use of PUCT, is indeed the optimal choice. It turns out that, combined with an appropriate learning rate, the case where α is set to 0.5 actually has the best theoretical guarantees on the regret, i.e. it obtains the optimal adversarial asymptotic regret bound of O(√KT) [Audibert and Bubeck, 2009; Abernethy et al., 2015]. Comparatively, setting α to 0 yields a bound of O(√KT log T ) [Wei and Luo, 2018] and setting α to 1 yields a bound of O(√KT logK) [Seldin and Lugosi, 2017].

1 To the best knowledge of the authors the naming of AlphaZero is not related to setting this α parameter to zero and this matching is thus a mere coincidence.

3.3 Combining PUCT and UCT

We have established that the reversed KL-divergence is equivalent to the f-divergence with f(x) = -log(x), i.e. the logbarrier. The f-divergence that results from a Tsallis entropy regularizer with α = 0.5 can be easily computed from Equation (7) and is also equivalent to the squared Hellinger distance

When we replace the KL-divergence in Equation (5) with this f -divergence, we obtain the following formula after simplifying:

where the subscript on ¯π denotes the value of α and λ∗N denotes the learning rate for the f-divergence from Equation (9), such that the optimal regret bound is obtained. In Lemma 1 we determine λ∗N and subsequently, through proving Proposition 1, we show how ¯π0.5 resembles a combination of PUCT and UCT.

Lemma 1. λ∗N = λN

Proof. This follows directly from Theorem 3 in [Zimmert and Seldin, 2018] and setting α to 0.5.

Proposition 1. ¯π0.5 is the strategy that results from combining the f-divergence from UCT with the learning rate λ from PUCT.

Proof. First we define the action selection formula for UCT:

Note that πθ can be assumed to be the uniform distribution when there is no better estimate for the prior. Now we rewrite a∗UCT such that we can determine its underlying f -divergence and learning rate:

which then becomes

Then we rewrite a∗UCT using Lemma 2 in [Grill et al., 2020]:

with Df being the f-divergence from Equation (9). In combination with Lemma 1 this concludes the proof.

4 Implementation

4.1 Separation of ˆπ and ¯π

In each MCTS iteration we compute ¯π for both players as

However, ¯π depends on the Q-values q. In sequential MCTS, q is readily available from the child nodes, but in simultaneous MCTS this typically gets computed as q = Qπopp, with Q being the matrix of running mean Q-values for action pairs and πopp being the current best estimate of the opponent's strategy. In a standard Decoupled (P)UCT implementation we set πopp to be equal to ˆπopp, the empirical visit distribution of the opponent. However, due to the previously mentioned inaccuracy of ˆπ, we instead leverage the ¯π solutions from previous MCTS iterations. A naive approach would be to set πopp to the computed ¯πopp from the last iteration, but this is problematic because ¯π itself does not converge to a Nash equilibrium, whereas its average does, as mentioned in Section 2.2. Therefore, it is beneficial to use a (weighted) average of the ¯π solutions from all the previous iterations.

Note that storing a weighted average of ¯π solutions implies that an extra variable has to be kept inside of the nodes next to the already present variable storing the empirical visit distribution ˆπ. With the approach described above, the latter variable is only needed for computing the running mean of the Q-values obtained from the search.

4.2 Efficient Computation of ¯π

In each MCTS iteration a convex optimization problem as in Equation (15) needs to be solved to compute the policy ¯π. It turns out that computing ¯π can be done in a computationally efficient way. Analogously to Proposition 4 in [Grill et al., 2020], where the α = 0 case is studied, one can derive for the Tsallis entropy α = 0.5 case:

with 1 being the the vector such that ∀a : 1a = 1. Therefore

with α set such that ∑b ¯πb = 1 and ∀b : ¯πb ≥ 0. Note that the α parameter here is different from the Tsallis-α.

We find the following bounds on α, using a similar derivation as [Grill et al., 2020]:

As ∑b ¯πα[b] is strictly decreasing on α ∈ (αmin, αmax), we can then compute ¯π easily using dichotomic search over (αmin, αmax). Alternatively, it is also possible to utilize Newton's method to determine ¯π as done in [Zimmert and Seldin, 2018].

4.3 Weighing of ¯π Solutions

We said in Section 2.2 that the average of the strategies, i.e. the average of ¯π solutions, converges to a Nash equilibrium. However, we found empirically that logarithmically increasing the weight of the ¯π solutions in the average leads to faster convergence due to quicker decay of the impact of old solutions. We show that we are still guaranteed convergence to a Nash equilibrium by proving Proposition 2, which states that, asymptotically, there is no difference between an unweighted average and a log-weighted average.

Proposition 2.

Proof. First we rewrite the left-hand side as

Using Stirling's approximation one has

We can now rewrite (16) as

and using dot product notation one has

which is implied by

To show that (17) holds, we first note that the dot product of both sides is equal to n by using Stirling's approximation. This, combined with the norm of the right-hand side being equal to √n, implies that the norm of the left-hand side must be ≥ √n, and equal to √n only if both vectors are identical. Since the absolute values of the elements of the vector on the left-hand side are all ≤ 1, the norm must be ≤ √n, implying that both vectors are equal.

4.4 Imputation of Q-values

To get a better Q-value estimation of the unvisited nodes, we set the Q-value of the unvisited nodes to be the mean Q-value of the visited nodes each time a tree node is selected, similar to the implementation of ELF OpenGo [Tian et al., 2019].

5 Experiments

5.1 Test Domain

As test domain we use an adaptation of the bot programming game Mad Pod Racing (MPR) - formerly known as Coders Strike Back (CSB) - on the CodinGame competitive programming platform. This is the platform's most popular game, with supposedly over 100,000 participants. The top entries are based on a variety of reinforcement learning algorithms, such as AlphaZero, DQN 2 [Mnih et al., 2013] and A2C [Mnih et al., 2016].

MPR/CSB is a zero-sum two-player simultaneous move game with a continuous action and state space in which each agent controls two Star Wars-themed pods, which participate in a race against the pods of the opponent. However, for testing our algorithm we will instead use a simplified version of the game which we call Pod Pursuit. Here each player controls one pod, with one player focusing strictly on preventing the other player from completing the race. This leads to an asymmetric game that has some high-level similarity to pursuit-evasion games. These types of games are commonly studied in simultaneous move settings [Bosansky et al., 2016]. Additionally, pursuit-evasion games tend to suit UCT well due to a high frequency of the states requiring pure strategies [Bosansky et al., 2016]. Thus making it more challenging to compete against UCT with an algorithm seeking a (possibly mixed) Nash equilibrium strategy.

Another reason why we deem this game as a good test domain for our algorithm is because it is a game that is highly suited for reinforcement learning, or stated alternatively: it is very difficult to obtain comparable results with alternative methods. On top of that, the game is simple enough to enable successful training on high-end consumer hardware, yet playing optimally is (highly) non-trivial. Lastly, we note that the CodinGame platform has been used before to conduct reinforcement learning research, e.g. [Kowalski and Miernik, 2020].

5.2 Game Description

Pod Pursuit 3 is a fully observable asymmetric zero-sum twoplayer simultaneous move game featuring two pods. Pod 1's task is to hit one or more checkpoints in a given order, with a limited amount of turns for each checkpoint. Pod 2's task is to prevent Pod 1 from completing its task by blocking its path. The pods move continuously in a minimalist 2D physics engine, though the actions and friction are applied in discrete turns. Each turn the players determine the next action to apply to their pod, where each action consists out of both a thrust and an angle. As in the original game, both pods also have to ability to shield instead of thrust, which causes their mass to increase tenfold for one turn, at the cost of not being able to apply thrust for some turns. While the ability to shield may seem like a gimmick at first, it has profound consequences on the game. For example, we conjecture that the ability to shield results in any game state being a theoretical win for Pod 1, assuming the absence of a turn limit. Otherwise, some positions would be trivial wins for Pod 2. An illustration of the game is provided in Figure 1. In Figure 1a we can see how both pods start out in an idle state, both facing the first checkpoint from an equal distance, separated by a distance of 1000. In Figure 1b we can see how the pods have left their starting position and how Pod 2 is now in a position where it can prevent Pod 1 from easily capturing the next checkpoint. In Table 1 we show an overview of the relevant parameters for the physics engine. We choose to leave the parameters unit-less in general, but the interaction between the different quantities should happen as if they were SI units with the exception of the angle, which is in degrees instead of radians. The game features two types of collisions: pod-pod collisions and pod-checkpoint collisions. Pod-pod collisions are elastic and have a minimum impulse of 120. Pod-checkpoint collisions happen when the center of the pod is within the radius of the checkpoint and do not result in a physical effect.

2 A write-up of a DQN implementation can be found here: https://github.com/pb4git/Nash-DQN-CSB-Article

3 Implementation at: https://github.com/mpeelm/Pod-Pursuit

Figure 1: Depictions of two game states. The heading of the pods is indicated with a triangle and the velocity vector with an arrow.

Figure 2: Training BLO-Alpha0.5, BLO-Alpha0 and AlphaZero for 250 iterations, where in each iteration the network parameters are updated based on the result of 4000 games, resulting in a total of one million games played for each algorithm. Every model is trained three times independently and the shown data points are the mean performance. The Elo rating is computed in a tournament setting that includes all 45 models.

5.3 AlgorithmComparison

In our experiments we are interested in the comparison of three algorithms. Firstly, we test a baseline straightforward extension of AlphaZero for simultaneous move games, employing Decoupled PUCT as search method. As in the AlphaZero paper, we make use of Dirichlet noise in the root node. The parameters for the noise are ϵ = 0.25 and α = 1. Secondly, we test BLO-Alpha0, which replaces AlphaZero's PUCT with the search detailed in Section 4, but with the Tsallis-α set to zero. And lastly, we test BLO-Alpha0.5, which is identical to BLO-Alpha0, except for using regularization based on the Tsallis entropy with α = 0.5.

Each algorithm uses the outcomes and computed policies from self-play games to update an MLP with three hidden layers with dimension 88 and ReLU as activation function. The optimizer used is SGD with momentum (0.9) and a constant learning rate of 0.1. The inputs of the network are the (scaled) relative positions between the pods and the next two checkpoints (12 inputs), as well as the (scaled) velocity vectors of the pods (4 inputs) and the one-hot encoded shield timers (8 inputs). This yields a total of 24 inputs. The network has both a value-head and a policy-head and the latter has 7 actions that discretize the action space into actions with thrust in {0, 200} and angles in {-18, 0, 18}, plus a shield action with angle 0. Lastly, we use a discount factor γ of 0.99 and the constant c in the definition of λN is set to 1.

In Figure 2a we can see the (relative) Elo rating of the three algorithms when each algorithm gets 50 search iterations per turn. We can observe that BLO-Alpha0.5 does significantly better than the other two algorithms, while BLO-Alpha0 still yields a modest improvement over AlphaZero, which is expected due to the results obtained for low simulation budgets in [Grill et al., 2020]. However, when we look at Figure 2b, in which 200 iterations are used per turn, we can see that the BLO algorithms still perform better than AlphaZero's PUCT, which shows that even for higher simulation budgets it is worthwhile to use a more precise search algorithm.

For the BLO algorithms we opted not to use Dirichlet noise. While Dirichlet noise can be beneficial during the early training, later on it actually tends to slow down improvement. We attempted to run AlphaZero without Dirichlet noise as well, but found that this hurts AlphaZero's ability to improve severely at 50 search iterations per turn. Increasing the amount of search iterations has been observed to overcome this, and thus allows AlphaZero to learn without Dirichlet noise, but we found that even in this setting, the presence of Dirichlet noise is beneficial to learning. Taking this into consideration we don't deem the asymmetry of the presence of Dirichlet noise among the algorithms as something that hurts the validity of our experiments.

6 Conclusion

We have shown that the PUCT algorithm used by AlphaZero and MuZero corresponds to an MCTS using log-barrier regularization. This insight has allowed us to use the Tsallis entropy to generalize to different kinds of divergences. Previous work on bandit algorithms has shown that Tsallis entropy with α = 0.5 obtains the theoretically optimal regret bound. After experimentally testing the impact of the value of α on the rate of improvement for a search-based reinforcement learning algorithm, we found that setting α to 0.5 yields significant improvements compared to the log-barrier regularization used by PUCT. Additionally, we developed our algorithm with an ideology rooted in bandit linear optimization, most notably leading to the maintaining of the average strategy in the MCTS nodes instead of the usual empirical visit counts. We tested our algorithm on a simultaneous move game since these kinds of games have an especially strong theoretical need for an alternative to PUCT due to the failure of PUCT to converge to a Nash equilibrium, but we expect that our findings will translate well to other domains, such as sequential move games and non-adversarial games.

Acknowledgments

This research received funding from the Flemish Government under the "Onderzoeksprogramma Artifici¨ele Intelligentie (AI) Vlaanderen" programme. We also want to thank Roman Ring and Nicolas Vercheval for helpful discussions.