Convex Regularization in Monte-Carlo Tree Search
Authors: Tuan Quang Dam
Carlo D'Eramo
Jan Peters
Joni Pajarinen
Venue:  (2021)
Keywords: Monte-Carlo Tree Search
Entropy regularization
Reinforcement Learning

Abstract: Monte-Carlo planning and Reinforcement Learning (RL) are essential to sequential decision making. The recent AlphaGo and AlphaZero algorithms have shown how to successfully combine these two paradigms to solve large scale sequential decision problems. These methodologies exploit a variant of the well-known UCT algorithm to trade off the exploitation of good actions and the exploration of unvisited states, but their empirical success comes at the cost of poor sample-efficiency and high computation time. In this paper, we overcome these limitations by studying the benefit of convex regularization in Monte-Carlo Tree Search (MCTS) to drive exploration efficiently and to improve policy updates, as already observed in RL. First, we introduce a unifying theory on the use of generic convex regularizers in MCTS, deriving the first regret analysis of regularized MCTS and showing that it guarantees an exponential convergence rate. Second, we exploit our theoretical framework to introduce novel regularized backup operators for MCTS, based on the relative entropy of the policy update and on the Tsallis entropy of the policy. We provide an intuitive demonstration of the effect of each regularizer empirically verifying the consequence of our theoretical results on a toy problem. Finally, we show how our framework can easily be incorporated in AlphaGo and AlphaZero, and we empirically show the superiority of convex regularization w.r.t. representative baselines, on well-known RL problems across several Atari games.

Under review as a conference paper at ICLR 2021
CONVEX REGULARIZATION IN MONTE-CARLO TREE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Monte-Carlo planning and Reinforcement Learning (RL) are essential sequen- tial decision making. The recent AlphaGo and AlphaZero algorithms have shown how to successfully combine these two paradigms to solve large scale sequential decision problems. These methodologies exploit variant of the well-known UCT algorithm trade off the exploitation of good actions and the exploration of unvis- ited states, but their empirical success comes at the cost of poor sample-efficiency and high computation time. In this paper, we overcome these limitations by study- ing the benefit of convex regularization in Monte-Carle Tree Search (MCTS) drive exploration efficiently and to improve policy updates, as already observed First, Rirsi we introduce a unifying theory the use of generic convex regularizers in MCTS, deriving the first regret analysis of regularized MCTS and showing that it guarantees an exponential convergence rate. Second, we exploit our theoretical framework to introduce novel regularized backup operators for MCTS, based on the relative entropy of the policy update and on the Tsallis entropy of the policy. We provide an intuitive demonstration of the effect of each regularizer empirically verifying the consequence of our theoretical results on toy problem. Finally, we show how our framework can easily be incorporated in AlphaGo and AlphaZero, and we empirically show the superiority of convex regularization w.r.t represen- tative baselines, on well-known RL problems across several Atari games.
INTRODUCTION
Monte-Cario Tree Search (MCTS) is a well-known algorithm to solve decision-making problems through the combination of Monte-Carlo planning with an incremental tree structure (Coulom
2006). Although standard MCTS is only suitable for problems with discrete state and action spaces,
recent advances have shown how to enable MCTS in continuous problems (Silver al., 2016 Yee
et al. 2016). Most remarkably, AlphaGo (Silver et al. 2016) and AlphaZero (Silver et al. 201 7b a) couple MCTS with neural networks trained using Reinforcement Learning (RL) (Sutton & Barto
1998) methods, e.g., Deep Q-Learning (Mnih et al. 2015). to speed up learning of large scale prob- lems with continuous state space. In particular, a neural network is used to compute value function estimates of states a replacement of time-consuming Monte-Carlo Carlo rollouts, and another neural network is used to estimate policies as a probability prior for the therein introduced PUCT action selection method, variant of well-known UCT sampling strategy commonly used in MCTS for exploration (Kocsis et al.) 2006). Despite AlphaGo and AlphaZero achieving state-of-the-art per- formance in games with high branching factor like Go (Silver al., 2016) and Chess (Silver al.) 2017a), both methods suffer from poor
mostly due to the polynomial conver- gence rate of PUCT (Xiao al. 2019). This problem, combined with the high computational time to evaluate the deep neural networks, significantly hinder the applicability of both methodologies.
In this paper, we provide unified theory the use of convex regularization in MCTS, which proved to be efficient solution for driving exploration and stabilizing learning in RL (Schulman et al.) 2015 2017 Нaarnoja et al. 2018 Buesing et al. 2020). In particular, we show how a regularized objective function in MCTS can be seen an instance of the Segeendre-Fenchhe transform, similar to previous findings on the use of duality in RL (Mensch& & Blondel 2018 Geist et al. 2019 Nachum & Dai 2020) and game theory Shalev-Shwartz & Singer 2006 Pavel 2007). Establishing theoretical framework, we can derive the first regret analysis of regularized MCTS, and prove that generic convex regularizer guarantees an exponential convergence rate the solution of the reg-

---

Under review as a conference paper at ICLR 2021
ularized objective function, which improves the polynomial rate of PUCT. These results provide a theoretical ground for the use of arbitrary entropy-base -bssed regularizers in MCTS until now limited to maximum entropy (Xiao et al. 2019). among which we specifically study the relative entropy of policy updates, drawing on similarities with trust-region and proximal methods in RI. (Schulman et al. 2013 2017b), and the Tsallis entropy; used for enforcing the learning of sparse policies (Lee et al. 2018). Moreover, we provide an empirical analysis of the toy problem introduced in Xiao et al. (2019) to intuitively evince the practical consequences of our theoretical results for each regularizer. Finally, we empirically evaluate the proposed operators in AlphaGo and AlphaZero increasing complexity, from classic RL problems to an extensive analysis of Atari games, confirm- ing the benefit of our novel operators compared to maximum entropy and, in general, the superiority of convex regularization MCTS w.r.t. classic methods.
problems of
2
PRELIMINARIES
2.1 MARKOV DECISION PROCESSES
We consider the classical definition of finite-horizon Markov Decision Process (MDP) 5- tuple M = (S. A, R. P, 7). where S is the state space, A is the finite discrete action space, R 8 x A + is the reward function,
S A + S is the transition kernel, and E 1) is the discount factor. A policy E 11 S x A + IR is a probability distribution of the event of executing an action a in a state s. A policy æ induces a value function corresponding to the expected cumulative discounted reward collected by the agent when executing action a in state and following the policy ı thereafter: (* a) E
kk=p > rr++k+1ls; = s, = a, x], where r1+1 is the reward obtained after the i-th transition. An MDP solved finding the op- timal policy x², which is the policy that maximizes the expected cumulative discounted re- ward. The optimal policy corresponds to the one satisfying the optimal Bellman equation (Bell-) man 1954) Q"(ss a) _ P(s'ls,
[E
(1, a) [R(8, a, s') + 7 maxa' (* a')] ds', and is the fixed point of the optimal Bellman operator T'Q a) Js (P(s'ss, a) [R(s, a, s') + y max.' Q(s',a')) ds' Additionally, we define the Bellman operator under the policy . as (s)((, - Ss P(s'|s, (s, a) [R(s, a, s') + 7 ( ((((s, , dd) ds', the optimal value function V (*(s) - max.cA Q"'(s, a). and the value function under the policy π as (s) - max.Ed Q=
2.2 MONTE-CARIAL TREE SEARCH AND UPPER CONFIDENCE BOUNDS FOR TREES
Monte-Carlo Tree Search (MCTS) is a planning strategy based on a combination of Monte-Carlo sampling and tree search to solve MDPs. MCTS builds tree where the nodes are the visited states of the MDP, and the edges are the actions executed each state. MCTS converges to the optimal policy (Kocsis et al. 2006; Xiao et al. 2019). iterating over loop composed of four steps:
1. Selection: starting from the root node, tree-policy is executed to navigate the tree until a node with unvisited children, i.e. expandable node, reached;
2. Expansion: the reached node is expanded according to the tree policy;
3. Simulation: run rollout, e.g. Monte-Carlo simulation, from the visited child of the cur- rent node to the end of the episode;
4. Backup: use the collected reward to update the action-values Q(-) of the nodes visited in the trajectory from the root node to the expanded node.
The tree-policy used to select the action to execute in each node needs to balance the use of al- ready known good actions, and the visitation of unknown states. The Upper Confidence bounds for Trees (UCT) sampling strategy (Kocsis et al. 2006) extends the use of the well-known UCB1 sampling strategy for multi-armed bandits (Auer et al., 2002). to MCTS. Considering each node corresponding to state 8 different bandit problem, UCT selects an action a E A applying an upper bound to the action-value function
log N(s)
UCT(s, Q)s,0)((+)))))) + +
(1)
as)
2

---

Under review as a conference paper at ICLR 2021
where (ss, a) is the number of executions of action a in state [(s) = E, NNss a),, and is constant parameter to tune exploration. UCT asymptotically converges to the optimal action-value function Q", for all states and actions, with the probability of executing suboptimal action at the root node approaching O with polynomial rate O for a simulation budget (Kocsis et al. 2006 Xiao al. 2019).
REGULARIZED MONTE-CARLE TREE SEARCH
The success of RL methods based on entropy regularization comes from their ability to achieve state-of-the-art performance in decision making and control problems, while enjoying theoretical guarantees and ease of implementation (Haarnoja et al., 2018 Schulman et al. 2015 Lee et al., 2018). However, the use entropy regularization is MCTS is still mostly unexplored, although its advantageous exploration and value function estimation would be desirable reduce the detrimen- tal effect of high-branching factor in AlphaGo and AlphaZeero. To the best of our knowledge, the MENTS algorithm (Xiao al., 2019) is the first and only method to combine MCTS and entropy regularization. In particular, MENTS uses a maximum entropy regularizer in AlphaGo, proving an exponential convergence rate to the solution of the respective softmax objective function and achieving state-of-the-ant art performance in some Atari games (Bellemare et al., 2013). In the fol- lowing, motivated by the success in RL and the promising results MENTS, we derive a unified
theory of regularization in MCTS based on the Legendre-Feenhher transform (Geist et al. 2019), that generalizes the use of maximum entropy MENTS an arbitrary convex regularizer. Notably, our theoretical framework enables to rigorously motivate the advantages of using maximum entropy and other entropy- based regularizers, such as relative entropy or Tsallis entropy, drawing connections with their RL counterparts TRPO (Schulman et al., 2015 and Sparse DQN (Lee et al. 2018). as MENTS does with Soft Actor-Critt Critic (SAC) (Haarnoja et al. 2018).
3.1 LEGENDRE-FENCHER TRANSFORM
Consider an MDP M (S,A, P, 7) as previously defined, Let Ω R be a strongly convex function. For policy T. = T T(- s)) and Q. = (ss,.) E RA, the Segendre-Fenchhee transform (or convex conjugate) of Ω is Ω TR RR, defined as:
Ω (Q.) max Tr, Q. T(((Ts)
EIE
where the temperature specifies the strength of regularization. Among the several properties of the Legendre-Fencher transform, we use the following (Mensch & Blondel 2018 Geist et al. 2019).
Proposition 1
Let Ω be strongly convex.
Unique maximizing argument: VΩ" is Lipschitz and satisfies
VΩ" (Q+)= arg max Tx, Q. 7(( n.Ell,
Boundedness: if there are constants Lo and Un such that for all n. E II we have Ly S M(T.) < Un, then
max Q2(a) - -Up s (22 S max (a - TLg. aEA
(4)
aEA
Contraction: for any Q1, E SxA
(Q1) (Q2) 11x0 5 Q1 Q2 10x
(5)
Although the Legendre--Fenchl transform Ω applies to every strongly convex function, for the purpose of this work only consider representative set of entropic regularizers.
3.2 REGULARIZED BACKUP AND TREE POLICY
In MCTS, each node of the tree represents a state s E S and contains a visitation count N(s, a). Given trajectory, define n(sr) the leaf node corresponding to the reached state sT. Let
3

---

Under review as a conference paper at ICLR 2021
So: Go, $1, d1..., ST be the state action trajectory in simulation, where n(sr) is leaf node of T-
Whenever a node (syr) is expanded, the respective action values (Equation 6 are initialized as Qn(ST, a) 0, and (ST, a) 0 for all E A. For all nodes in the trajectory, the visitation count updated by N (st, (z) = (8( at) + 1, and the action-values by
r(ss; a+) + 7P [r(s), ai) + 7222 (Q2(((14))777)) if
if
Qa(();
where Qn()(+1) E R with components Qa(51+1, a), Va E A. and p is an estimate returned from an evaluation function computed in sy, e.g. a discounted cumulative reward averaged over multiple rollouts, or the value-function of node n($T+1) returned by a value-function approximator, e.g. a neural network pretrained with deep Q-learning (Mnih al., 2015), done in (Silver et al. 2016 Xiao et al., 2019). We revisit the E2W sampling strategy limited to maximum entropy regulariza- tion (Xiao et al., 2019) and, through the use of the convex conjugate in Equation (6). we derive novel sampling strategy that generalizes to any convex regularizer
A
(e(ar)s:) = (1 \.,)V (Q((ss)))))) +
[A]
where As =|Al/tog(E, +1) with 0 as exploration parameter, and V depends the measure in use (see Table for maximum, relative, and Tsallis entropy). We call this sampling strategy Extended Empirical Exponential Weight (E3W) to highlight the extension of E2W from maximum entropy to a generic convex regularizer.
3.3 CONVERGENCE RATE TO REGULARIZED OBJECTIVE
We show that the regularized value Vn can be effectively estimated the root state E S, with the assumption that each node the tree has a ww -ussubgaussian distribution. This result extends the analysis provided in (Xiao al. 2019), which is limited to the use of maximum entropy.
Theorem At the root node where (s) is the number of visitations, with O, Vn(() is the estimated value, with constant C and Ö, we have
N(8) N())))2
P((Va()) Vi((s) > Cexpl- Co N
(8)
where Vn(() (Q.) and (s) S2 (Q:). From this theorem, we obtain that the convergence rate choosing the best action a" the root node, when using the E3W strategy, exponential.
Theorem Let 0t be the action returned by E3W at step t. For large enough and constants C, Ō
Piaa # a²) S Clexp( Co(log(t))3
(9)
4 ENTROPY-REGULARIZATOO BACKUP OPERATORS
From the introduction of unified view of generic strongly convex regularizers as backup operators in MCTS, we narrow the analysis to entropy-based regularizers. For each entropy function, Table T shows the Legendre-Fenchè transform and the maximizing argument, which can be respectively replaced in our backup operation (Equation (6) and sampling strategy E3W (Equation 77. Using maximum entropy retrieves the maximum entropy MCTS problem introduced in the MENTS algo- rithm (Xiao et al.] 2019). This approach closely resembles the maximum entropy RL framework used to encourage exploration (Haarnoja et al. 2018 Schulman et al., 2017a). We introduce two novel MCTS algorithms based on the minimization of relative entropy of the policy update, inspired by trust-region (Schulman et al. 2013) and proximal optimization methods (Schulman et al. (011b)) 7b) in RL, and on the maximization of Tsallis entropy, which has been more recently introduced in RL as an effective solution to enforce the learning of sparse policies (Lee et al.) 2018). We call these algorithms RENTS and TENTS. Contrary to maximum and relative entropy, the definition of the
4

---

Under review as a conference paper at ICLR 2021
Legendre- Feahreel and maximizing argument of Tsallis entropy is non-trivial, being
(2t) 7 -spmax spmaa(Qr(s, (Qr(s,))TT)
(10)
VQ*( = max ((((.,)) Eaex Qe(s, Q 1.0)
(11)
[4]
where spmax is defined for any function f f:8x
as
(s,
(Eack (s, - 1)2 1
spmax(f(s,))
Σ
(12)
2
2/172
2
aEK
and K. is the set of actions that satisfy 1 + is(s af))
j= (8), with a; indicating the action
with the i-th largest value of f(s a) (Lee al. 2018).
Table 1: List of entropy regularizers with Legendre-Fencher transforms and maximizing arguments.
Entropy
Regularizer (((T))
Legendre-Fenchel (Qa)
Max argument (Qa)
Maximum
[(ass) log ((as)
log E.
2(am))
log E. (ala(a Reiaia
-- (als)e
Relative
T (b/sa) s)e
Tsallis
(l (a)ss)
11 -1)
Equation 10
Equation (11)
4.1 REGRET ANALYSIS
At the root node, let each children node be assigned with a random variable X,, with mean value V,, while the quantities related to the optimal branch are denoted by e.g. mean value V At each timestep n, the mean value of variable X, is Vi.-- The pseudo-regret (Coquelin & Munos 2007) at the root node, at timestep n, defined as RUUCT" nV" - Vi, Similarly, we define the regret of E3W at the root node of the tree as
Rs = nV* Σ V.
= nV Σ 1 - i,,, = nV' Σ Σ (a(s)))),
(13)
1=1
where ite(-) is the policy at time step t, and I(-) is the indicator function.
- Theorem Let K2 = (a.ls) + / log f/20, and X² = (al'(a - 1, /o los 8/2m, where (.ls) is the policy with respect to the mean value vector V-) the root node For any 8 > O, with probability at least 1 d, constant L,P, C, C so that the pseudo regret R2 satisfies
nV
Σ Vi
p 1 1-7 (
I, +Un La)
)) < Rm < nV* Σ Vi v.(xx
L. T,,(Un (pin-Lan )
p 1
This thcorem provides bounds for the regret of E3W using a generic convex regularizer Qt thus, we easily retrieve from the regret bound for each entropy regularizer. Let m min, V (als).
Corollary Maximum entropy: nV* E, Vi ( L log (A)) S Rn nv n n. L(" L( 1rm_//a
Corollary 2 Relative entropy:
V -n E. Ve (Ki L(" 7[og LAI = - ) < Rr SnV' - E, E,Vi vi(xi - I r1log (olos|/l-11 ((1000114-
1-7
Corollary 3 Tsallis entropy:
n/* - En Vi (ks + ( [A]
T [1)
12 ( -1 T
2/A 1- }
Rr
2|A
1
5

---

Under review as a conference paper at ICLR 2021
Remarks. The regret bound of UCT and its variance have already been analyzed for non- regularized MCTS with binary tree (Coquelin & Munos| 2007). On the contrary, our regret bound analysis in Theorem 3 applies corollaries, we observe that the maximum and relative entropy share similar results, although the bounds for relative entropy are slightly smaller due to 1. Remarkably, the bounds for Tsallis en- tropy become tighter for increasing number of actions, which translates in limited regret in problems with high branching factor. This result establishes the advantage of Tsallis entropy complex prob- lems w.r.t. to other entropy regularizers, as empirically confirmed by the positive results in several Atari games described in Section
generic regularized MCTS. From the specialized bounds in the
m.
4.2 ERROR ANALYSIS
We analyse the error of the regularized value estimate at the root node nss) w.r.t. the optimal value: Eg
Vn(s) (s).
Theorem For any and generie convex regularizer 92 with some constant C, C₁ with prob- ability at least 8, En satisfies
Co"llog T(Un- La) 2N(s)
Co2 lo2log 2N((s)
1-7 I En S
V
(14)
To give a better understanding of the effect of each entropy regularizer in Table I we specialize
the bound in Equation [4] to each of them. From (Lee et al. 2018), know that for maximum
entropy ())))) = Σ. Te log Tr, we have log [A|] I ((x)))
S 0: for relative entropy (((T)) =
KL(Te] (T- if we define m min, Te- 1 (a]s) s), then we can derive 0 S ((T.) I log |A| +
log 1: and for Tsallis entropy ((x.)) = (1l me 112 1). we have
- S ((m)) S Then.
2AA
Ča² log C 2N(s)
T log |Al
Čo log C 2N(ss)
Corollary maximum entropy error:
S Sen S
1-7
Co² log 2s(s)
T(log] AA| - log 1n)
Čo² Co2 log C 2N(ss)
Corollary relative entropy error:
S Snn S
&
1-7
Co2 log C 2N((s
|4| 1 7 S Snn S 2| 1-7
Co2 log of 2N(s)
Corollary 6 Tsallis entropy error:
These results show that when the number of actions |A| is large, TENTS enjoys the smallest error; moreover, we also see that lower bound of RENTS is always smaller than for MENTS.
EMPIRICAL EVALUATION
In this section, we empirically evaluate the benefit of the proposed entropy-based MCTS regular- izers. First, we complement our theoretical analysis with an empirical study of the synthetic tree toy problem introduced Xiao et al. (2019), which serves as a simple scenario give an inter- pretable demonstration of the effects of our theoretical results in practice. Second, we compare to AlphaGo and AlphaZero (Silver et al., 2016 2017a). recently introduced to enable MCTS solve large scale problems with high branching factor. Our implementation is a simplified version of the original algorithms, where we remove various tricks in favor of better interpretability. For the same reason, do not compare with the most recent and oftte-of-thearr variant of AlphaZero known as MuZero (Schrittwieser et al. 2019), as this is a slightly different solution highly tuned to maximize performance, and detailed description of its implementation not available.
5.1 SYNTHETIC TREE
This toy problem is introduced in Xiao et al. (0199) to highlight the improvement of MENTS over UCT. It consists of tree with branching factor k and depth d. Each edge of the tree is assigned

---

Under review as a conference paper at ICLR 2021
k=16 d=1
k=4
d=2
k=8 d=3
k=12 d=4
k=16 d=5
0.05
0.04
0.08
0.4
0.03
0.06
0.3
0.10
0.02
0.04
0.2
0.01
0.02
0.05
0.1
0.2
0.00
0.00
0.00
0.0
0.0
0.20
0.25
0.4
0.15
0.20
0.3
0.5
0.8
0.15
0.4
0.6
0.10
0.2
0.3
0.10
0.2
0.4
0.05
0.05
0.1
0.1
0.2
0.00
0.00
0.0
0.0
0.0
1500
800
1250
500
500
600
1000
600
400
750
400
300
400
500
100
200
200
100
200
0
5e3
10e3
5e3
10e3
5e3 Simulations
10e3
5e3
10e3
5e3 10e3
Simulations
# Simulations
Simulations
Simulations
UCT
MENTS
RENTS
TENTS
Figure 1: For each algorithm, show the convergence of the value estimate the root node to the respective optimal value (top), to the UCT optimal value (middle), and the regret (bottom).
UCT
Fg
MENTS
UCT
FUCT
MENTS
UCT
MENTS
4
4
4
6-
6
6
0.7 6
6
1400
8
8
8
8
8
8
10-
10
10
0.6 10
10
1200
0,25
0.5
1000
1 4 RENTS
12345 4
0.20
12345
123 45
0.4
123 4
1 4
800
TENTS
0.15
RENTS
TENTS
0.3
RENTS
TENTS
6
6
0.10
0.2
400
8
B
8
10
10
10-
0.1
200
12
12
0.00
14
0.0
14
0
1 3
12345
12345
12345
12345
12345
(a)
(b)
(c)
For different branching factor (rows) and depth (columns), the heatmaps show: the absolute еттоr of the value estimate at the root node after the last simulation of each algorithm w.r.. respective optimal value (a), and w.r.t. the optimal value of UCT (b); regret at the root node (c).
Figure 2:
random value between 0 and 1. At each leaf, a Gaussian distribution is used evaluation function resembling the return of random rollouts. The mean of the Gaussian distribution is the sum of the values assigned to the edges connecting the root node to the considered leaf, while the 0.0 For stability, all the means are normalized between and 1. As in Xiao et al. (2019), we create 5 trees on which we perform 5 different runs in each, resulting in 25 experiments, for all the combinations of branching factor = (2, 4, 6, 8, 10, 12, 14, 16} and depth d d= (1, 3, 4, 5). computing: (i) the value estimation error at the root node w.r.t the regularized optimal value: Eg = Vi V (ii) the value estimation error at the root node w.r.t. the unregularized optimal value: EUCT
standard deviation
Vn V V*ucT; (iii) the regret R in Equation (33). For fair comparison, we use fixed 7 = 0.1 and = 0.1 across all algorithms. Figure T and 2 show how UCT and each regularizer behave for different configurations of the tree. We observe that, while RENTS and MENTS converge slower for increasing tree sizes, TENTS is robust w.r.t. the size of the tree and almost always converges faster than all other methods the respective optimal value. Notably, the optimal value of TENTS seems to be very close to the one of UCT, i.c. the optimal value of the
'The value of the standard deviation is not provided in Xiao et al 2019). After trying different values, observed that results match the in Xiao al. (2019) when using 0.05.

---

Under review as a conference paper at ICLR 2021
Ca
Acrobol-v1
300
250
-100
Toba Rewards
200
Total Rewards
-150
150
200
100
UCT
MENIS
-250
UCT
MENTS
RENTS
RENTS
TENTS
-300
TENTS
100
200
Epicode
300
400
500
0
100
200
500
400
500
Episade
(a) Cartpole
(b) Acrohot.
Figure 3: Cumulative rewards of AlphaZero with UCT and entropy- operators, in CartPole (a) and Acrobot (b). Results are averaged over 5 and 10 seeds and show 95% confidence intervals.
unregularized objective, and also converges faster than the one estimated by UCT, while MENTS and RENTS are considerably further from this value. In terms of regret, UCT explores less than the regularized methods and it is less prone to high regret, at the cost of slower convergence time. Nevertheless, the regret of TENTS is the smallest between the ones of the other regularizers, which seem to explore too much. These results show a general superiority of TENTS in this toy problem, also confirming our theoretical findings about the advantage of TENTS in terms of approximation error (Corollary ()) and regret (Corollary 3 in problems with many actions.
5.2 ENTROPY-REGULARIIZD ALPIAZZER
In its standard form, AlphaZero Silver et al. 2017a) uses the PUCT sampling strategy, variant of UCT (oossis al. 2006) that samples actions according to the policy
VN(s)
PUCT(s. = Q(s. cP(ss 1+ N(s
(15)
where P is a prior probability on action selection, and e is an exploration constant. A value network and a policy network are used to compute, respectively, the action-value function Q and the prior policy P. We use single neural network, with 2 hidden layers composed of 128 ELU units, and two output layer respectively for the action-value function and the policy. We run 500 AlphaZero episodes, where each episode is composed of 300 steps. A step consists of running 32 MCTS simulations from the root node, as defined in Section 2 using the action-value function computed by the value network instead of using Monte-Carlo rollouts. At the end of each cycle, the average action-value the root node computed and stored, the tree is expanded using the given sampling strategy, and the root node is updated with the reached node. At the end of the episode, a minibatch of 32 samples is built from the 300 stored oction-valucs and the network is trained with one step of gradient descent using RMSProp with learning rate 0.001. The entropy-regularized variants of AlphaZero can be simply derived replacing the average backup operator, with the desired entropy function, and replacing PUCT with E3W using the respective maximizing argument and 0.
Cartpole and Acrobot. Figure shows the cumulative reward of standard AlphaZero based on PUCT, and the three entropy-regularized variants, on the Cartpole and Acrobot discrete control problems (Brockman et al. 2016). While standard AlphaZero clearly lacks good convergence and stability, the entropy-based variants behave differently according the problem. First, although not significantly superior, RENTS exhibits the most stable learning and faster convergence, confirm- ing the benefit of relative entropy in control problems as already known for trust-region methods in RL (Schulman et al., 2015). Second, considering the small number of discrete actions in the problems, TENTS cannot benefit from the learning of sparse policies and shows slightly unstable learning in Cartpole, even though the overall performance is satisfying in both problems. Last, MENTS solves the problems slightly slower than RENTS, but reaches the same final performance. Although the results on these simple problems are not conclusive to assert the superiority of one method over the other, they definitely confirm the advantage of regularization in MCTS, and hint at the benefit of the use of relative entropy in control problems. Further analysis more complex
8

---

Under review as a conference paper at ICLR 2021
Table 2: Average in Atari 100 seeds per game. Bold denotes statistically significant
difference to the highest mean (t-test, < 0.05). Bottom row shows no difference to highest mean.
UCT
MoxMCTS
MENTS
RENTS
TENTS
Alien
1. 488.80 80
1. 461 10
1. 508.60 60
1. 547 80
1. 568. 60
Amidar
115.02
124.92
123.30
125.58
121.84
Asterix
85
484.50
576.00
5. 743 50
5. 647 00
Astoroids
873.
899.60 60
1, 414.70
1, 486.40
1, 642 10
720.00
277.00
35,
BankHleist
475.50
458.60
622.30
636.70
631.40
BeamRider
2, 616.72
2. 66166.3 30
2. 1.82.215
2, 658.991
2, 804 88
Breakout
303
296.14
309 03
300.35
316.68
Contipede
782.18
1, 728.69
2.012.86
2. 253 42
2. 258 89
AemonAArack
579.30
640.80
1,04.500
1. 124.470
1,3.30
124.20
125.79
134.88
Prestbite
1,210000
1, 332.10
388.20 20
2. 369 80
2. 260 60
Gopher
3, 348.0.0
3, 303.00
3, 536.40
3. 373.8.0
3, 447.80 80
009.95
010.1555
044.55
McPacman
1. 940.020
1, 107.10
2,018.30
2. 190.30
2. 094 40
Phoemx
747.30
2, 626.60
3, 098.80
2, 582.30
3, 975.30
Obert
19977722
033.50
8, 051.225
8,254.00
137.77
Robotank
11.43
11.00
11.59
11.51
11.47
Senquest
3, 276.40
3, 217.20 20
4.311
3. 345.20
3, 1,324.40
Solaris
895.
923.20
118.020
115.00
127
Spuce Invaders
778.45
835.90
832.55
867.35
822.95
WizardOWor
685.00
666.00
211.000
1. 2.2.000
1, 231.00
Highest mean
6/22
7/22
17/22
16/22
22/22
control problems will be desirable (c.g. MuJoCo Todorov al. 2012)). but the need to account for continuous actions, a non-trivial setting for MCTS, makes it out of the scope of this paper.
5.3 ENTROPY-RREGULARIZEE ALPHAGO
The learning time of AlphaZero can be slow in problems with high branching factor, due the need of a large number of MCTS simulations for obtaining good estimates of the randomly initialized action-values. To overcome this problem, AlphaGo (Silver et al. 2016) initializes the action-values using the values retrieved from pretrained network, which is kept fixed during the training.
popular benchmark for testing deep RL method- ologies (Mnih et al. [0155] Van Hasselt et al.) 2016;; [Bellemare et al. (017] but still relatively disregarded in MCTS. We use a Deep Q-Network, pretrained using the same experimental set- ting of Mnih et al. (2015), to initialize the action-value function of each node after expansion as Qina(s, = (Q(s, a) V(s)) /r. for MENTS and TENTS, as done in Xiao et al. (2019). For RENTS init Q Qinat (s, a) log (atio((a)s) s)) (Q(s. a) V(s) /T, where P Prior the Boltzmann distribution induced by action-values Qss.-) computed from the network. Each experimental run consists of 512 MCTS simulations. The temperature is optimized for each algorithm and game via grid-search between 0.01 and 1. The discount factor is 0.99, and for PUCT the exploration constant
Atari. Atari 2600 (Bellemare al.) 2013)
0.1. Table 2 shows the performance, in terms of cumulative reward, of standard AlphaGo with PUCT and our three regularized versions, on 22 Atari games. Moreover, we test also AlphaGo using the MaxMCTS backup (Khandelwal al., 2016) for further comparison with clas- sic baselines. We observe that regularized MCTS dominates other baselines, in particular TENTS achieves the highest scores in all the 22 games, showing that sparse policies are more effective in Atari. This can be explained by Corollary [ which shows that Tsallis entropy can lead to lower error at the root node even with a high number of actions compared to relative or maximum entropy.
CONCLUSION
We introduced a theory of convex regularization in Monte-Carlo Tree Search (MCTS) based on the Fegchele-Fenchel transform. Exploiting this theoretical framework, we studied the regret of MCTS when using a generic strongly convex regularizer, and we proved that has an exponential convergence rate. We these results motivate the of entropy regularization in MCTS, particularly considering maximum, relative, and Tsallis entropy. Finally, we test regularized MCTS algorithms in discrete control problems and Atari games, showing its advantages over other methods.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256, 2002.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volie Volume 70, pp. 449-458. JMLR. org. 2017.
Richard Bellman. The theory of dynamic programming. Technical report, Rand corp santa monica ca, 1954.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint wwxiv::666.015444 2016.
Lars Buesing, Nicolas Heess, and Theophane Weber. Approximate inference in discrete distribu- tions with monte carlo tree search and value functions. In International Conference on Artificial Intelligence and Statistics, pp. 624-634. PMLR, 2020.
Guillaume Chaslot, Mark Winands, Jaap Van Den Herik, Jos Uiterwijk, and Bruno Bouzy. Progres- sive strategies for monte-carlo tree search. New Mathematics and Natural Computation, 4(03): 343-357, 2008.
Benjamin E Childs, James H Brodeur, and Levente Kocsis. Transpositions and move groups in monte carlo tree search. In 2008 IEEE Symposium On Computational Intelligence and Games. IEEE, 2008.
Pierre-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search. arXiv preprint cx/0703062, 2007.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference Machine Learning, pp. 2160-21669 2019.
Sylvain Gelly and David Silver. Combining online and offline knowledge uct. In Proceedings of the 24th international conference on Machine learning, pp. 273-280, ACM, 2007.
Sylvain Gelly and Yizao Wang. Exploration exploitation in go: Uct for monte-carlo go. In NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploita- fion Workshop, 2006.
Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. arXiv preprint arXiv:2007.12509 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1861-1870, 2018.
David P Helmbold and Aleatha Parker- Wood. All-moves-as-first heuristics in monte-carlo go. In IC-AI, pp. 605-610, 2009.
Man-BBptiste Hooek, Chang-Shing Lee, Arpad Rimmel, Fabien Teytaud, Mei-Hui Wang, and Oliver Teytaud. Intelligent agents for the game of go. IEEE Computational Intelligence Magazine, 2010.
Piyush Khandelwal, Elad Liebman, Scott Nickum, and Peter Stone. On the analysis of complex backup strategies in monte carlo tree search. In International Conference on Machine Learning, 2016.
10

---

Under review as a conference paper at ICLR 2021
Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search, 2006.
Tomáš Kozelek. Methods of mets and the game arimaa, 2009.
Kyungjae Lee, Sungjoon Choi, and Songhwai Oh. Sparse markov decision processes with causal sparse tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3(3):146611473 2018.
Richard J Lorentz.
Improving monte- carle tree search in havannah. In International Conference on Computers and Games, pp. 105-115. Springer, 2010.
Jincheng Mei, Chenjun Xiao, Ruitong Huang, Dale Schuurmans, and Martin Müller. On princi- pled entropy exploration in policy optimization. Proceedings of the 28th International Joint Conference Artificial Intelligence, pp. 3130-3136. AAAI Press, 2019.
Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. International Conference on Machine Learning. pp. $462-3471, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529-533) 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928-1937, 2016.
William H Montgomery and Sergey Levine. Guided policy search via approximate mirror descent. In Advances in Neural Information Processing Systems, pp. pp. 4008 4016,4006.400 2016.
Ofir Nachum and Bo Dai. Reinforcement learning via fonkfel-ro duality. CoRR,
Abs/2001.01866. 2020.
Vlad Niculae and Mathieu Blondel. A regularized framework for sparse and structured neural atten- tion. In Advances Neural Information Processing Systems, pp. 3338-3348, 2017.
Lacra Pavel. An extension of duality to game-theoretic framework. Automatica, 43(2):226 -377, 2007.
Gavin Adrian Rummery. Problem solving with reinforcement learning. PhD thesis, University of Cambridge Ph. D. dissertation, 1995.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference Machine Learning (ICML), pp. 1889-1897, 2015.
John Schulman, Xi Chen, and Picter Abbeel. Equivalence between policy gradients and soft q- learning. arXiv preprint arXiv:1704.04440 2017a.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1rXiv:1707.0634 2017b.
Shai Shalev-Shwartz and Yoram Singer. Convex repeated games and fenchel duality. Advances in neural information processing systems, 19:1265-1272. 2006.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser. loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.001 2017a.
11

---

Under review as a conference paper at ICLR 2021
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)354-355) 2017b.
Richard Sutton and Andrew Barto. Introduction reinforcement learning, volume 135, MIT press Cambridge, 1998.
Gerald Tesauro, VT Rajan, and Richard Segal. Bayesian inference in monte-carlo tree search. arXiv preprint 12X3vv:2003.555. 2012.
Fabien Teytaud and Olivier Teytaud. On the huge benefit of decisive moves in monte-carlo tree search algorithms. In Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, pp. 359-364. IEEE, 2010.
E. Todorov, T. Frez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
David Tom. Investigating uct and rave: Steps towards a more robust method, 2010.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Thirtieth AAAI conference on artificial intelligence. 2016.
Tom Vodopivec, Spyridon Samothrakis, and Branko Ster. On monte carlo tree search and reinforce- ment learning. Journal of Artificial Intelligence Research, 60:881-936, 2017.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. In Advances Neural Information Processing Systems, pp. 9516 9524, 2019.
Timothy Yee, Viliam Lisý, Michael H Bowling, and S Kambhampati. Monte carlo tree search in continuous action spaces with execution uncertainty. In IJCAI, pp. 690-697, 2016.
A RELATED WORK
Entropy regularization is common tool for controlling exploration in Reinforcement Learning (RL) and has lead to several successful methods (Schulman et al., 2015 Haarnoja et al. 2018 Schulman al., 701 Mnih et al., 2016). Typically specific forms entropy are utilized such as maxi- mum entropy (Haarnoja et al. 2018) or relative entropy (Schulman et al. 2015). This approach an instance the more generic duality framework, commonly used in convex optimization the- ory. Duality has been extensively studied in game theory (Shalev-Shwarzz Shwartz & Singer 2006 Pavel 2007) and more recently in RL, for instance considering mirror descent optimization Montgomery & Levine 2016 Mei et al. 2019), drawing the connection between MCTS and regularized policy optimization (Grill et al. 2020). or formalizing the RI. objective via Legendre-Rockafee ity (Nachum & Dai 2020). Recently (Geist et al., 2019) introduced regularized Markov Decision Processes, formalizing the RL objective with a generalized form of convex regularization, based on the Legendre-Fencher transform. In this paper, we provide a novel study of convex regulariza- tion in MCTS, and derive relative entropy (KL-divergence) and Tsallis entropy regularized MCTS algorithms, i.. RENTS and TENTS respectively. Note that the recent maximum entropy MCTS algorithm MENTS (Xiao et al.) 2019) is a special case of our generalized regularized MCTS. Unlike MENTS, RENTS can take advantage any action distribution prior, in the experiments the prior is derived using Deep Qllearning (Mnih et al. 2015). On the other hand, TENTS allows for sparse action exploration and thus higher dimensional action spaces compared to MENTS. In experiments, both RENTS and TENTS outperform MENTS.
dual-
Several works focus on modifying classical MCTS to improve exploration. UCBI-tuned (Auer et al. 2002) modifies the upper confidence bound of UCBI to account for variance in order to im- prove exploration. (Tesauro et al., 2012) proposes a Bayesian version of UCT, which obtains better estimates of node values and uncertainties given limited experience. Many heuristic approaches
12

---

Under review as a conference paper at ICLR 2021
based on specific domain knowledge have been proposed, such as adding bonus term to value esti-
mates (Gelly & Wang 2006; Teytaud & Teytaud 20i0dChilds
Childs et al., 2008; Kozelek 2009 Chaslot
et al. 2008) or prior knowledge collected during policy search (Gelly & Silver, 2007| Helmbold
& Parker-Wood 2009 Lorentz, 2010; Tom,, 2010; Hooek et al., 2010). (Khandelwal et al., (016)
formalizes and analyzes different on-policy and off-policy complex backup approaches for MCTS
planning based on RL techniques. (Vodopivec et al. 2017)) proposes an approach called SARSA-
UCT, which performs the dynamic programming backups using SARSA (Rummery, 1995). Both
(Khandelwal wal et al. (016) and |Vodopivec et al., (017)) directly borrow value backup ideas from RL estimate the value at each tree node, but they do not provide any proof of convergence.
B PROOFS
Let f and r be respectively the average and the the expected reward at the leaf node, and the reward distribution at the leaf node be
Lemma For the stochastic bandit problem E3W guarantees that, t 2 4.
2a
P (1 r Fz 21>2 log(2
<4|A|exp)
+t)
(log(2 t))3)
Proof 1 Let us define (a)a) as the number of times action have been chosen until time t, and 14
Ne(a) E (a), where as (a(a) is the E3W policy at time step s. By choosing Xs log(1+e] follows that for all a and 4,
8/(s +1)
(( Σ T. (a)
log(1 8)
log(1 + 8)
(log(1 + 8))2
8/(8 + 1)
1 1
ds log (2 t)
log(1 + +) (log(1 + 8))2
log 2
2 log( + t)
From Theorem 2.19 in Wainwright 2019. we have the following concentration inequality:
2
20a }.
P(IN((a) - M() > e) s 2expl
2
2 0²
where o² < 1/4 is the variance of a Bernoulli distribution with ग. (k) at time step s. We define the event
E. = E A,( - (((a)ss))
and consequently
26
(()N(()) N.(a)) 2 5) exp( -rt))
(16)
Conditioned on the event E., for Tlog(2-7) we have Na(a) 2 the definition of sub- gaussian,
Toog244y For any action by
- fc(a)) 802 log( log(2 + +t)
20 log( Ne(a)
S P (r(a) (r(a))f((a)) fr((a) > >1
5
by choosing 5 satisfying log(?)
(log(2+1))3 we have
/202 log(?)
exxp (- (-
1
P (r(a) - -F((a))
(~(log(2 (log(2 t))3
Ni(a)
13

---

Under review as a conference paper at ICLR 2021
Therefore, for t 2
20
20
P
Pz 11
SP r| Fr 11,0>
Ee ((E
1og(2 + +t)
log(2 +t)
20
P
(r(a) -r(aa)
+P(EE - 2| exp
(Tloo(( (log(2 + t))3
log(2 +
+ 2|A|
exp
(2og(2 + 0))3
(2 + 1))3
Lemma Given two policies म. (1) (522 and (22) (2(()(() 31, such that || | - (2) 1 L (()) - (2) 1lp
Proof 2 This comes directly from the fact that ग = ( is Lipschitz continuous with Eo (P-norm. Note that p has different values according to the choice of regularizer. Refer to Niculae & Blondel (007) for a discussion of each norm using Shannon entropy and Tsallis entropy regularizer. Relative entropy shares the same Properties with Shannon Entropy.
Lemma 3 Consider the E3W policy applied tree. At any node of the tree with depth d Let us define N; (s, a) x² (a)s).t, and N.(s, a) E.= Ta(als), where (a(als) is the policy at time step There exists some C and O such that
Ct Togi
t
< ČlAlLexp(
(log 1)3
Proof 3 We denote the following event,
20
Er,. = (11 (x((8.)) 11
log(2 - k)) }.
Thus, conditioned on the event Ni Er, and for t 2 we bound (Ñe(s, N;;
[N(ss, a) (s) <
ht((as)) -- <a(a|s)| +
A
k=1
|| (xx(s1)) -m 1
k=1
|| (.(s)) - x" (11s) 1lp +
Σ
A
A=1
(u(ss).) Q(s',)) l1e + Σ
Au (Lemma 2)
$ P
11 ( - Q((''-) 1100 +
Au Property of p-norm)
km
Pr("" ..) - -r(s",,) 1la0
Xu (Contracction
k=1
2o
A
log(2 k))
k=1
$ >
2a
dk +
|A|
dk
log(2 + k)
k=u log(1 + k))
k=
Ct.
s logt"
14

---

Under review as a conference paper at ICLR 2021
for some constant C depending [A], d, o, L, and Finally,
Ct log
t (log(2 t))
2
P(E,.)
4|A exp(
i=1
i=1
v 4 Al exp(
(log(2 + t))3
O expe (log(t))3))
Lemma 4 Consider the E3W policy applied to tree. At any node of the tree, Let us define Ni (8, a) = πt t, and Ne(s. a) as the number of times action a have been chosen until time
step I. There exists some C and C such that
Ct
t
P((Ne(s, - ()))))) (NC
S Ötexpl
log!
(log 1)3
Proof 4 Based the result from Lemma have
P(IN((s, (o (s) > (1 C) logt S Ctexpl
(log t)3
Ct.
<(( (s, log
(() (e(s,a))
logt
4 A|ppt (log(2 2 + t))3²
} + 2/A| expl (log(2 + t)) [ 3 and 16
O(texp(- (logt)a)).
Theorem At the root node of the tree, defining N(s) as the number of visitations and Va- (s) as the estimated value at node for >> O, we have
N(s) Č(log(2 + N(
P([Va(s) VH > c) > Cexpff
Proof 5 We prove this concentration inequality by induction. When the depth of the tree is D = 1, from Proposition 7 we get
Va(s) Vi(()) =I 9" - S (Q% S 1loo (Contraction)
where i is the average rewards and r" is the mean reward. So that
P([v((s) [=(s))>>)) P(r - 1100> E).
From Lemma 1, with c= [og(2+N(s))* we have
204
N(s)c
P((Va(s) > < 7" 110)))
() 4|A/cxpf
20 + N(s)))
N(s)c
Ceepl Č(log(2 (())))
Let assume we have the concentration bound at the depth - 1, Let us define Va((a) = Qn(s,a), where Sa is the state reached taking action o. from state then at depth D
N(8a)c
P((Va(s=) - Vi)(sa) > >) S Cexpf- (log(2 N(s))))
(17)
Now at the depth D, because of the Contraction Property, we have
Va(s) - [i)(s < 7 || Qa(s..) (h 10 >1Qa(s a) (h(
15

---

Under review as a conference paper at ICLR 2021
So that
P(IVa(s) Vi((s) e)
S P(r ll Qn(s,a) ()(s, ||>
N(sa)e
S C. expl
Callog(2 + . (8a)))²
N(sa)e
S Ca expl Collog(2 (s)))
From 17 we can have lim ((s)) = oo because if 3L, (s.)) < L, we can find >
for which 17 is not satisfied. From Lemma 4, when N(s) is large enough, we have N(sa)
(a (for example (sa) > 1 (s))) that means we can find C and Ô that satisfy
N(s)c
P(IVa(s) Vā(()) e) S Ceepl- C(log(2 + N(s)))
Lemma At any node s of the tree, (s) is the number of visitations. We define the event
E. = (V a in A, (N) - (s) N² where N =
2
where e > and Vi- (s) is the estimated value at node s. We have
N(s)
(s)V)(() Vī(()) elEs)= s Cexpl- C(log(2 + N(
Proof The proof is the same in Theorem 2. We prove the concentration inequality by induction.
When the depth of the tree is D = 1, from Proposition 7 we gel
(V((s) (=) =11 2 (Qn(s.)) S (Q)(s.)) || 7 || f-r 11xo (Contraction Property)
where the average rewards and r" is the mean rewards. So that
(((V(()) - Vir (3)] > c) s P(y r 10c c).
From Lemma with 1og(2+N(s]) and given E., we have
207
N(s) 20og1 + N(s)))
P((Va(() - Vi((s) > e) < P(7 || 8- r" 1100 e) S 4|A/expl
N(s)e
= C Cexpl Č(lg(( + (()))))
Let assume we have the concentration bound at the depth D - 1, Let us define Va(sa) = Qn(s,a), where Sy is the state reached taking action o from state s, then at depth D
N(sa)c
(P(Va(ss)) - Vi > s Cexpf C(lo((2 + N(s))))
Now depth D. because of the Contraction Property and given E., we have [V((s) - (s) < > Qn(s,.) - (s.s..) I1x0 71Qa(s,a) - Qh(s, (3,,, satisfied).
So that
P((Vo(s) - V(((s) A IP(7 || Qn(s, - Ch(s, a) ||>
N(sa)e
S C. expl
Ca(log(2 + N(sa)))2 N(sa)e
< C. expl
-
Ca (log(2 + N(s)))
N(s)c
I Cxxpf- Cllog(2 (s)) (because of E.)
16

---

Under review as a conference paper at ICLR 2021
Theorem 2 Let at be the action returned by algorithm E3W at iteration t. Then for large enough, with some constants C,C,
P(ay F a²) Ctexpl- Co(log(t))s
Proof Let us define event E. as in Lemma Let a' be the action with largest value estimate at the root node state The probability that E3W selects a sub- sub-optimal arm at s is
(aa # )²) S Σ P(Vn((#a)) V7(8. El,) + PP(E))
Σ P((Va((a) Vi((s)) (Va(s.-) ((a 2 Vir(s.)) Vi(s.)).. +
Let us define A (i)() - (sa) therefore for A > 0, we have
P(a # a²) S Σ P((V[(s.) Vi((s.)) (Va(s..) ((²(s=))) 2 ALE.) + +P(E))
P([Vo(sa)) Vir(sa)] E.) + P((VV((())) (= 2 BAIE.) + F(E))
Ca expl N(s)(aB)
(3s) } + P(E)). Ca. (log(2 + N(s)))²
+ Ca- expl Clogo(2 N(s)))
where + 1, a > 0, 3 > 0, and (s) is the number of visitations the root node s. Let us define
π min (ad) (BA)
}, and C Ι max max(C,. (Ca: Co } we have
C. C.
t
Pla + a") Cexpl- Co(log(2 + 1))2
} + P(E.).
From Lemma 4, 3C', O' for which
P(E)) < c' C'Lexpl-
C" (log((1))3 )
so that
P((a + d') < O(texpl- (log(1))3 H).
Theorem 3 Consider an E3W policy applied to the tree. Let K2 = (a)ls) + & VOo² for 4/2n,
1 / Co" log 8/2m, where V (.(s) is the policy with respect the mean value vector V(-) the root node For any ō >> with probability at least 1 5, 3 constant L. C, so that the pseudo regret R2 satisfies
X VI
n n
Σ Vi
- ( P
L ((-l-LLL) La)) Rr S nv Σ V. Vi
_
L r(Un (
p
Proof 8 From Lemma 2 given two policies n (1) = ()1) and (2) = ( 3I, such that
|| ((1) (2) 1155 L (1) (2) |155 L 1 || (1) - (2) 1000
p
From 13 we have the regret
R, = nV
Σv
V. Σ (arls))
(18)
1=1
where Re(.)) is the policy at time step t, and I(()) is the indicator function. V is the optimal branch at the root node, V, is the mean value function of the branch with respect to action i, V(.) is the |
17

---

Under review as a conference paper at ICLR 2021
vector of value function the root node. (-) is the |A] estimation vector of value function the root node. T.. ()) = (V(()()) is the policy with respect to the (-) vector at the root node.
Then for any ò 0, with probability least 1 - 8, we have
[T(all)) - #,(a;|))| I (.(ss) - (t((1s) 1 L
IV())
Vv) llso (Lemma 2)
(19)
P
S -(() T(Un- Ln)
log 2N(s)
C x
1 1-6 +
(Theorem 4)
So that
L
T(UB - Ln)
Coolog C | 2N(ss)
+ L (T(Un= - Ln)
-Ln)
Co2 log à
T(a,ss)
8
S ( S T(ails)
+ +V 2N(s)
p
p
1 1
so that
L T(U - Ln)
Co log 2n
C &
R2 = nV
Σ
Vi
ae(a.ls) S nv - -E V; Σ
(aails))
+
P
6
t=1
i
L [TTUU== Ln)
C Coolog
Ry S nV Σ
T((als))
+
8
p
1-6
2n
_ TUg La)
Co log 2n
C 0
RS S nv - n Σ V. (Tailss)
1
(20)
And
- - Ln)
L
Co2 log C 2n
Rn 2 nº
Σvi
Vi Σ (T(ails)
+
+
p
1-8
Rn 2 nV* n Σ (T(alss))++
1
I T(T Tuae)
Co2 log o
+ +V
p 1 1-8
2n
In case of Maximum Entropy and Relative Entropy p = 1, because
|| (1) - (2)) 11 L || (1) - (2) 1100.
So that we have for MENTS
Vv Σ V. Ni L( log
(1(118114)1 (A1)) S Rn S snV= -n n Σ Vi Xi L( log LAl)
For RENTS, we have
T (log |A1| m ))) S Rm <vv -n Evi(xe I( (1ogg) |A|| - (n) n Σ V. (BL D(
1-7
1-9
where m = mina (als).
In case of Tsallis Entropy p = 2 Nicullae & Blondel (2017)). so that
nV" n Σ V.
L /
2 A 1-)) S R. S nv*
AA1 -
Σv Vi(xi
7. 2/A| 1 1-7
L IA| |||-1 -1
K4
Before derive the next theorem, we state here the Theorem in Geist et al. (2019)
Boundedness: for two constants Ln and U2 such that for all क e II, we have Lg S 1(x)) S
Un. then
(s) T(Un Lo)
S VV((s)= $ Vs)...
(21)
1-7
18

---

Under review as a conference paper at ICLR 2021
Where is the temperature and is the discount constant.
Theorem 4 For any > 0, with probability at least 1 - 6, the satisfies
Co2 log B T(Un Ln)
Coo C
S SE S V 2N(s)
2N(s)
1 1-7
Proof 9 From Theorem 2, let define ò C Cexpl
2N(s) Coa
}, that
Oo log & then for any 2N(a)
5 > O, we have
P((V(()) - Vā(()) - Co2 log
2 1 -
2N(ss)
Then, for any d > O, with probability at least 1 - 8, we have
Co2 log _
Va(s) (i)(s]] S
(N(ss
Co2 log C (N((s)
Co 8 25((s)
8
I Vn(() (o(()) V
C log C 2N(s)
Coolog + (8).
+ Vi((s) S Va(() S
2N((s)
From Proposition 1, we have
Co2 log 8 + V*))s
T(U Ln)
Čo C 8 (s)...
Vn((s) S V
(x)
1 1-7
2N(s)
19


Reviews:
[{"review_id": "iLloUJEHCan", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-Summary \n\nThe authors consider planning for Markov Decision Process. Precisely they study the benefit of convex regularization in Monte-Carlo Tree Search (MCTS). They generalize the E2W by xiao et al., 2019 by considering any strictly convex function as regularizer instead of the intial negative entropy. They provide a regret analysis of this algorithm named E3W and prove that EW3 converges at an exponential rate to the solution of the regularized objective function. Then they consider three particular instances MENTS with the Shannon entropy as a regularizer, RENTS with relative entropy to the previous policy as regularizer, and TENTS with the Tsallis entropy. They compare empirically these algorithms with PUCT as policy search in Alpha-go style MCTS on CartPol, Acrobot, and Atari games.\n\n\n-Score justification/Main comments:\nThe setting is not clearly written and some key definitions are not introduced properly (see specific comments below). Given that it is hard to understand the main results.\n\n\n-Detailed comments \n\nP2: It is V^\\pi(s) = \\sum_{a} \\pi(a|s) Q^\\pi(s,a). Is the number of actions finite?\n\nP3, (2): You mean \\max_{\\pi_s} \\sum_{a} \\pi(a|s) Q^\\pi(s,a) -\\tau \\Omega(\\pi_s) ? Because T_{\\pi}Q is a function of (s,a) and I do not understand the notation T_{\\pi_s}Q_s (and Proposition 1 will be wrong since in (4) the bound on the rewards should appear, e.g. take Q_s = 0).\n\nP3, (4): absolute value for |\\Omega^*(Q_1) - ....|\n\nP4, (7): what is the link with (6)? Here, by the choice of \\lambda you force the exploration as with \\epsilon-greedy with is what UCT is trying to avoid.\n\nP4, Theorem 1: Could you define the estimated value V_\\Omage(s). But at the end we would like to be close to the true optimal value V^*, can you deduce a bound for |V_\\Omega -V^*|.\n\nP4, Theorem 2: I assume that a^* is the optimal value for the regularizd objective? \n\nP4: In TRPO, Schulman et al, 2015, it is rather the reverse relative entropy than the relative entropy which is used.\n\nP5, Table 1: there should be the temperature parameter \\tau here.\n\nP5: V_i is not defined, a_i either, it is a sum over i in which set? I do not understand your definition of the regret. \n\nP5, Theorem 3: There is a sign issue in 13 since le left hand is greater than the right-hand. So the regret of E3W is linear?\n\nP7, figure 1: Is it UCT or PUCT used for the experiments because in the main test you say it is PUCT? And I would not say that UCT is \"clearly the worst\" approach in Figure 1.\n\nP9, appendix B: According to your setting the reward is deterministic. I do not understand. And it is an assumption no? Which leaf node?\n\nP10: Could you define properly r(a) and \\hat{r}(a)? Why there is a sum over k in the inequality below \"therefore\", is it a sum over a? And there is an issue with the parenthesis. I do not understand how you can control the term in exp(-1/(\\log(2+...))^3) by  exp(-t/(\\log(2+...))^3) in the last inequality.", "extra_scores": {}, "extra_text": {}}, {"review_id": "W6GOPpnJ9ej", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a general framework for regularized Monte Carlo tree search, thereby generalizing the maximum entropy Monte Carlo planning of Xiao et al. The main result(s) looks very interesting, but some of the definitions and results don't seem right.\n\nThe main issue\n=============\n\nThe main problem is Proposition 1 and the definition of the convex conjugate:\n1) The definition of the convex conjugate in (2) differs significantly from the standard one (e.g., the definition in the two cited papers) due to the multiplier \\tau. In fact, this \\tau, unless set to 1, strongly questions the validity of (3) - and basically all the usual properties that are true for the standard definition of convex conjugates.\n2) The contraction property in Proposition 1 also seems strange. It is well known that the Bellman operators are contractions, but the property claimed here is not true for the standard definition of the convex conjugate: if \\Omega^* is a contraction, then \\Omega should also be a contraction which, in turn, would imply \\Omega^*=0 due to \\Omega***=\\Omega*. Finally, in case \\Omega* is indeed a contraction, the contraction parameter should depend on \\tau as well.\n\nAs Proposition 1 is essential to the main result, the above issues make the the correctness of the main result questionable.\n\n\nAdditional remarks\n================\n\nFirst of all, it would be nice to have a brief summary of how the analysis works and what the main idea is.\n\nSection 3.2: the part of the trajectory discussed above (6) presumably corresponds to the selection part, not the simulation. Additionally, it is not clear how equation (7) was obtained. Please discuss it in more detail.\n\nRegarding (10) and (11): please prove these equations or add a citation to some work where they are proved.\n\nEquation (13): what is V_i? (Presumably, i_n stands for the action taken in step n.)\n\nRegarding the experiments, they do show the superiority of proposed method on some benchmark tasks, such as CartPole, Acrobot and a couple of Atari games. However, it is not clear whether these tasks are the best to test UCT as the strength of UCT is the doing in-depth exploration on search trees with large branching factors, where the actions could have significant consequences in a very delayed fashion (in terms of reward).", "extra_scores": {}, "extra_text": {}}, {"review_id": "ELek3t3hHxS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper generalizes and build on top of the MENTS/E2W, and shows that the entropy regularization can be replaced with any convex regularization. It uses the tools of convex conjugates and duality to derive the theoretical results and the algorithm/updates. Empirical results on Atari games confirm the value of policy regularization in MCTS.\n\nStrong points:\n - Theory generalizes MENTS/E2W\n\n- Experiments further support the value of regularized polices, showing that entropy is not the only thing that \"works\".\n\n- Paper brings important and interesting insights into MCTS, which is potentially very impactfull.\n\n- Previous work is (to my understanding) well cited.\n\n- While the paper relies on non-trivial operations, it's well written.\n\n- The resulting algorithms/updates are \"easy\" to implement.\n\nWeak points:\n- This paper is very much incremental to MENTS/E2W, one could say it \"just generalizes\" MENTS.\n\n- Missing connection to previous results of policy/values dualities (please see additional feedback)\n\n- The empirical results are not very exciting.\n\nReasons for score: \nWhile the empirical results don't bring anything exciting (especially when contrasted to MENTS), they still bring interesting insights. It almost seems that any regularization is relevant. Furthermore, the presented theory/connection coming from the duality is important - I do not think this connection of duality was presented in the MENTS paper. Thus it's satisfying to know that this is where the \"magic\" of softmax and entropy as used in MENTS is coming from.  The reason I really like this paper is that it helps to build more intuition about the regularized policies in MCTS, all the while generalizing the underlying theory.\n\nAdditional feedback:\nOn high level, this paper essentially explores the duality of policies and corresponding (regularized) values. This idea/result/notion of duality between policy and value appears quite often (a quick example that comes to my mind being extensive form games but surely others), and I think few sentences on this would help the reader to feel \"less surprised\" about some of the presented derivations and techniques, and overall better place it in the context of previous relevant work. Reading this paper, one could think that the duality of policies/values is novel observation, while in general it's not.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0HM4Uy_4K0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n \nThe paper provides theoretical analysis of the regularized backup for MCTS. The paper carries out detailed analysis (regret, errors analysis) on three instantiations of the regularizations. Finally, the paper provides some empirical gains on certain toy domains and some atari games.\n\n##########################################################################\n\nReasons for score: \n\n \nOverall, I vote for rejection. I am not very familiar with the theoretical results of the MCTS literature - however, it seems that the idea of adding convex regularization is not new in rl literature overall. I cannot be a good judge for the theoretical contribution and I will focus more on the empirical side of the paper.\n \n##########################################################################Pros: \n\n \n1. Related work. The paper seems to miss some highly related literature, in particular:\n\n[1] Buesing et al, Approximate Inference in Discrete Distributions with Monte Carlo Tree Search and Value Functions, AISTATS 2020\n\n[2] Grill et al, Monte Carlo Tree Search as Regularized Policy Optimization, ICML 2020\n\n[1] uses entropy-regularized MCTS backup; [2] relates MCTS to policy optimization with convex regularization. In particular, [2] proposes that the conventional MCTS backup used in Alpha-Zero (which is different from the max-MCTS backup), is carrying out approximate regularizations. I hope that the author could clarify on the connection between this work and these two pieces of prior work.\n \n2. Regarding results in Table 2, I wonder how many seeds do the authors run per game per algorithmic baseline. Does each number correspond to a mean value across a few seeds, or it is just a single run? Could the author also clarify how the t-test is done to denote significant differences? I would expect such tests to be run on averages over a collection of seeds.\n \n##########################################################################\n\nPlease address and clarify the concerns above.\n\n \n#########################################################################", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the reviewers pointed out a lack of rigor of this submission, unclear contributions, not too convincing claims and empirical gains. I thank the authors for the effort put in revising the paper and responding to the reviewer concerns. However, the reviewers did not deem them convincing enough.
Decision: Reject