Monte Carlo Tree Search with Boltzmann Exploration
Authors: Michael Painter
Mohamed Baioumy
Nick Hawes
Bruno Lacerda
Venue: NeurIPS 2023 poster (2023)
Keywords: Monte Carlo Tree Search
Planning
Entropy
Reinforcement Learning

Abstract: Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound applied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially appears inferior to other actions. Maximum ENtropy Tree-Search (MENTS) incorporates the maximum entropy principle into an MCTS approach, utilising Boltzmann policies to sample actions, naturally encouraging more exploration. In this paper, we highlight a major limitation of MENTS: optimal actions for the maximum entropy objective do not necessarily correspond to optimal actions for the original objective. We introduce two algorithms, Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS), that address these limitations and preserve the benefits of Boltzmann policies, such as allowing actions to be sampled faster by using the Alias method. Our empirical analysis shows that our algorithms show consistent high performance across several benchmark domains, including the game of Go.

Monte Carlo Tree Search with Boltzmann Exploration
Michael Painter, Mohamed Baioumy, Nick Hawes, Bruno Lacerda Oxford Roboties Institute University of Oxford
{mpainter, mohamed, nickh, bruno)ārobots. ox. ac uk
Abstract
Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound ap- plied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially appears inferior to other actions. Maximum ENtropy Tree-Search (MENTS) incorporates the maxi- mum entropy principle into an MCTS approach, utilising Boltzmann policies to sample actions, naturally encouraging more exploration. In this paper, highlight a major limitation of MENTS: optimal actions for the maximum entropy objective do necessarily correspond to optimal actions for the original objective. We introduce two algorithms, Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS), that address these limitations and preserve the benefits of Boltzmann policies, such as allowing actions to be sampled faster by using the Alias method. Our empirical analysis shows that our algorithms show consistent high performance across several benchmark domains, including the game of Go.
Introduction
Planning under uncertainty is a core problem in Artificial Intelligence, commonly modelled Markov Decision Process (MDP) or variant thereof. MDPs can be solved using dynamic programming techniques to obtain an optimal policy 33. However, computing a full optimal policy does not scale to large state-spaces, necessitating the use of heuristic solvers [18 4 and online, sampling based, planners based on Monte-Carlo Tree-Search (MCTS), such as the Upper Confidence Bound applied to Trees (UCT) algorithm (22).
The UCT search policy designed to minimise cumulative regret, so manages a trade-off between exploration and exploitation. To exploit, UCT often selects the same action on successive trials, which can result in getting stuck local optima. Conversely, Maximum ENtropy Tree Search (MENTS) places a greater emphasis on exploration by combining MCTS with techniques from maximum entropy policy optimisation [38] 16 [7]. MENTS jointly maximises cumulative rewards and policy entropy. where a femperature parameter controls the weight of the entropy objective. However, MENTS is sensitive this temperature parameter, and may not converge the reward maximising policy require prohibitively low temperature to do so.
In this work, consider scenarios where MCTS methods are used with a simulator plan how an agent should act. We introduce two algorithms for this scenario that address the above limitations. First, we present Boltzmann Tree Search (BTS) which but optimises for reward maximisation only. Secondly, we introduce Decaying ENtropy Tree Search (DENTS), which adds entropy backups to BTS, but is still consistent (i.e. converges to the reward maximising policy in the limit).
Boltzmann search policy like MENTS,
The main contributions of this paper are: (1) Demonstrating that the maximum entropy objective used MENTS can be misaligned with reward maximisation, thus preventing it from converging to the optimal policy; (2) Introducing two algorithms, BTS and DENTS, which preserve the benefits
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of using Boltzmann search policies while being as simple to implement as UCT and MENTS, but converge the reward maximising policy; (3) Analysing MENTS, BTS and DENTS through the lens of simple regref to provide theoretical convergence results; (4) Highlighting and demonstrating can be used with stochastic action selection improve the asymptotic
that the Alias method [35] k
complexity of running a fixed number of trials over existing MCTS algorithms: and (5) Demonstrating
the performance improvements of Boltzmann search policies used in BTS and DENTS in benchmark gridworld environments and the game of Go.
2 Background
2.1 Markov Decision Processes
where is the set of states; A is the set of actions; p 8 A S [0, 1] is the transition function where p(s' |s, a.) is the probability of moving to state s' given that action a was taken in state 8; R S x A + I is the reward function; and H N is the finite horizon. Let Suce(s, a) denote the set of successor states of (s, a). i.e. Succ(s, a) = {s' E p(s'|s, (iss|s,00 a) 0}.
We define a (finite-horizon) MDP as a tuple M (S, H).
A policy maps state and timestep to distribution over actions, and we denote the probability of executing a at state s and timestep I as π (a|s, l). Let 8, denote the state after / time-steps and d, the action selected at 8t, according to π. The expected value V and expected state-action value Q of are defined as:
H (s, = E, Σ
R (8c ai) 8: =
as, ((00) + By (e (5',,+++))
(2)
The goal is to find the optimal policy x² with the maximum expected reward: x² arg max V The optimal value functions are then defined as V =V" -²* Q For an MDP, there always exists an optimal policy xt which is deterministic (24]
2.2 Maximum entropy policy optimization
In planning and reinforcement learning, the agent usually aims to maximise the expected sum of rewards. In maximum entropy policy optimisation, the objective is augmented with the expected Formally, this is expressed as:
entropy of the policy [16] 38
V (s, = Ex Σ R (s., 0;) + aHl (I (-)s;,))) 5t
where 2 is temperature parameter, and H is the Shannon entropy function. The temperature determines the relative importance of the entropy against the reward and thus controls the stochasticity of the optimal policy. The conventional reward maximisation objective can be recovered by setting a 0.
An optimal value function for maximum entropy optimization is obtained using the soft Bellman optimality equations [7:
(s, a, t) = R(s, a) + E. (p() (s', (s),t)) t)].
(s, = a log Σ exp(Qin a, t)/a),
(5)
aEA
which corresponds standard Bellman backup. with the max replaced by a softmax, shown in Equation (5) The optimal soft policy n = arg max, V can be computed directly [26] as follows: T (als, 1) = exp( (s, a, () (s,(s, ())aa).
Note that the soft policy is always stochastic for any a > O. Henceforth, we will use soft value to refer value functions indexed with 'sft', (optimal) soft policy to refer policies of the form given in Equation (6). and standard value and (optimal) standard policy for values and policies the form given in Section 2.1 unless is clear from the context.
For the remainder of this paper we will drop the timestep from policies and value functions to simplify notation.

---

2.3 Monte-Carlo tree search
MCTS methods build search tree T using Monte-Carle trials. Each trial is split into two phases: starting from the root node, actions are chosen according to a search policy and states sampled from the transition distribution until the first state not 7 is reached. A new node added T and its value is initialised using some function /init often using a rollout policy to select actions until the time horizon is reached. In the second phase, the return for the trial is back-pu propagated up (or "backed up") ) the tree to update the values of nodes in T. For reader unfamiliar with MCTS, we refer to [6] for a review of the MCTS literature, as many variants of MCTS exist and may vary from our description.
Two critical choices in designing an MCTS algorithm are the search policy (which needs balance exploration and exploitation) and the backups (how values are updated). MCTS algorithms are often designed to achieve consistency (i.e. convergence to the optimal action the limit), which implies that running more trials will increase the probability that the optimal action is recommended.
To simplify notation we assume that each node in the search tree corresponds to a unique state, we may represent nodes using states, Our algorithms and results do not make use of this assumption, and generalise when this assumption does not hold.
UCT UCT [22 applies the upper confidence bound (UCB) in its search policy to balance exploration and exploitation. The nith trial of UCT operates as follows: let T the current search tree and let (50, 40, .... 0h-1, Sh) denote the trajectory of the nth trial, where sa & T or h H. At each node 8; the UCT search policy тuet will select a random action that has not previously been selected, otherwise, will select the action with maximum UCB value:
log N(s) (ss a)
TUCT (8) max ((s, a) + V a
where, Q(s, a) is the current empirical Q-value estimate, (s) (and N(s,, a)) is how many times s has been visited (and action selected) and is exploration parameter. Then, 8h is added to the tree: T + { UT. The backup consists of updating empirical estimates for = h 1,...,.. 0:
((s.. a1) + R(t) (())
(8)
N(s, az) +
A-1 R(s,, a:), and (ini())) E R(s, a:) if using rollout policy. where R(t) (sn) EI=
MENTS MENTS 37 combines maximum entropy policy optimization 16 38 with MCTS.
Algorithmically. it is similar to UCT. The two differences are: (1) the search policy follows stochastic Boltzmann policy, and (2) it uses soft values that are updated with dynamic programming backups. The MENTS search policy TMENTS given by:
A
AMENTS (a|s) (1 {s) +
[A]
PMENTS (a|s) exp (1
- )
(10)
where X, min(1,c/ log(E + N(s))), (0) is exploration parameter and (s) (and (sn(s, a)) are the current soft (Q-)value estimates. The soft value of the new node is initialised ((n()) +- (s,) and the soft values are updated with backups for = h 1,...,0.
(No)) ((s,, Ka((s')
N(8))
Qan ar) + R(st,a,) + Σ
(11)
s'ESSnc((,,a
V(((s)) + a log
Σ exp
(12)
acA
Each (s, a) is initialised using another function Qinit a) (but is typically zero).
3

---

1
0R8
2
GR
3
D
ag
ar
a1
R
D-1
D
D
D
D
D
Figure I: An illustration of the (modified) D-chain problem, where 1 is the starting state, transitions deterministic and values next states represent rewards for arriving in that state.
2.4 Simple regret
frequently used in MCTS methods to minimise cumulative regret during the tree search. Cumulative regret is most appropriate in scenarios where the actions taken during tree search have an associated real-world cost. However, MCTS methods often use a simulator during the tree search, where the only significant real-world cost is associated with taking the recommended action after the tree search. In such scenarios, simple regret 7 S of algorithms, as it only considers the cost of the actions that are actually executed. Under simple regret, algorithms are not penalised for under-exploiting during the search, thus can explore more, which leads to better recommendations by allowing algorithms to confirm that bad actions are indeed of lower value.
UCB [
is more appropriate for analysing the performance
We consider the problem of MDP planning as sequential decision problem, where for each round n:
the forecaster algorithm produces a search policy x" and samples a trajectory n²"
2. the environment returns the rewards R(st, (x) for each Se; or pair in T,
3. the forecaster algorithm produces recommendation policy v
4. if environment sends stop signal, then end, else return to step 1.
The simple regrer of the forecaster on it's nthh round is then:
reg(s, w²) = (s)) - yV (s).
(13)
In MENTS the recommendation policy suggested in 337 can be written:
MEMNTSS = arg max (s,
(14)
aEA
We can now formally define consistency: an algorithm is consistent if and only if its recommendation policy z converges to expected simple regret of zero: BBreg(s,, vb)] + 0 as - oc. Note that because we are considering randomised algorithms, there is a distribution over the possible recommendation policies that could have been produced. If a policy has a simple regret of zero then implies it is an optimal policy.
Limitations of prior MCTS methods
In this section the D-chain problem introduced in 9 (Figure highlight the limitations of UCT and MENTS. In the D-chain problem, when an agent chooses action ag, from some state d, moves to absorbing state and receives reward of (D d In state D, action a corresponds to an absorbing state with reward Rg = 1. The optimal standard policy always selects action aR-
In the 10-chain problem (D = 10), UCT will recommend action az from state 1 (Figure 2ap. UCT requires ((exp((..exp) ())..) many trials (D composed exponential functions) to recommend the optimal policy that reaches the reward of R 1 19). This highlights the first limitation mentioned in Section M UCT quickly disregards action aR at the initial state, to exploit the reward of 0.9.
When MENTS is run on the 10-chain problem, with the help of the entropy term it quickly finds the final reward of R, 1 (Figure 2a). However, consider the modified 10-chain with R 1/2 instead. Repeated applications of Equations 4 and (5) for 1 gives the optimal soft values of Qin (1, aR) log(exp(1/2) D sp(ii/10) 2.74 and Q (1, 0.9. So in the modified

---

1.0
0.9
Monte- Caro Value Estinate
0.9
Monte Care Value Estimate
0.7
0.8
0.6
Algorihi
0.5
Algotthm
UC
UCT
0.5
DENT3
0.4
DENTS
MENTS(1
04
MENTS(D 01)
MENTS(P 01)
50C
1000
1500
2000
2500
3000
530
1000
1500
2000
2500
3000
Numbor of Trials
Numbor of Triale
(a) 10-chain.
(b) Modified 10-chain.
Figure 2: comparison of MENTS, DENTS and UCT when run on the (modified) 10-chain.
10-chain problem, have (i,
(1, aL) with 1, whereas (1, an) Q" a1)
Thus, when MENTS converges, will recommend the wrong action with respect to the standard objective (Figure 2b i.e. it is not consistent. The modified 10-chain is example of Proposition
3.1 which states that MENTS will not always converge to the standard optimal policy.
Proposition 3.1. There exists an MDP M and temperature a such that EE(re((s, v (MNNTs) / as + co. That is, MENTS is not consistent.
Proof. Proof is by example with a in the modified 10-chain (Figure
We reduce the value of decrease the importance of entropy in the soft objective [R ()) + aH (π (+1s))). a is small enough, then MENTS recommendations can converge to the optimal standard policy (Theorem 3.2). Hence, MENTS with low temperature modified 10-chain problem (Figure 2b). However, in practice, a low temperature will often cause MENTS to not sufficiently explore, as demonstrated in the original D-chain (Figure 2ap.
solve the
Theorem 3.2. For any MDP M, after rumning trials of the MENTS algorithm with a < AM/3E log [A], there exists constants C, such that: E E[reg(So So. d'MENTS]] )] I Cexp(-king (s, S, a, a' E A, N].
where AM- = min(Q"
(200"((s0)) (s,a) (s,
Proof outline. We can show (s, a) & Q a) (Corollary E.12.1 similarly Thoerem 4.2
The bound on a is required to ensure that x (50) = ग (s0).
In conclusion, similar MDPs can require vastly different temperatures for MENTS to effective. We discuss MENTS sensitivity to the temperature parameter further in Appendix D.2 and demonstrate this parameter sensitivity in the Frozen Lake environment (Section 5.1 in Figure the appendix.
Boltzmann search
We now introduce two algorithms that utilise Boltzmann search policies similar to MENTS and admit bounded simple regrets that converge to zero without restrictive constraints on parameters. Thus, they do not suffer from sensitivity parameter selection that MENTS does. Both algorithms action selection and value backups that are easy to implement and use. We designed these algorithms with consistency in mind, which in practice, means that if we run more trials then we (with high probability) will recommend a better solution (note that Proposition 3.1 limlies that this is not always the case for MENTS).
4.1 Boltzmann Tree Search
Our first approach, put put simply, replaces the use of soft values in MENTS with Bellman values. We call this algorithm Boltzmann Tree Search (BTS). BTS promotes exploration through the stochastic

---

Boltzmann search policy, like MENTS, while using backups that optimise for the standard objective, like UCT. The search policy Tbts and backups for the nth trial are given by:
A
(Bts(a|s) = (1 - As) +
(15)
[A]
Pets(als) x exp (1 (Q(s.0)))
(16)
N(6) (N(s ((6))
(s) t R(s), +
Σ
(17)
x' (
((s) t max (s). aEA
(18)
for h 1,....0. O, where V and Q the current Bellman (Q-)value estimates, X min(1, e/ + N(s))), E (0, oo) is an exploration parameter and a is search temperature (unrelated to entropy). Each (s) and ((s, a) are initialised using Vinit and Qinit functions similarly MENTS. The Bellman values are used for recommendations:
(B) arg max Q(,
(19)
aEA
By using Bellman backups, we can guarantee that the BTS recommendation policy converges to the optimal standard policy for any temperature a, given enough time. In other words, BTS consistent.
Theorem 4.1. For any MDP M, after running trials of the BTS algorithm with root node of 80, there exists constants C, le > 0 such that for all & > 0 we have El (8o; dBBS))] & C eex(-knng and also (ss) 2g (so)
+
Proof outline. This result is a special case of Theorem 4.2 by setting 3(m) = O.
4.2 Decaying Entropy Tree Search
Secondly, we present Decaying ENtropy Tree Search (DENTS), which can effectively interpolate
between the MENTS and BTS algorithms. DENTS also uses the dynamic programming backups from equations 177 and (18), but adds an entropy backup. The entropy values are weighted by bounded non-negative function (sN in the DENTS search policy AENTTs:
As
TDENTS(a|s) (1 P-)N) +
(20)
TAI
PDENTs(als) x exp (1 (
(21)
Hv + H((TDENT((11s)) + Σ (a)
(22)
aEA
N(s')
HQ
Σ
((s,, az) Hy
(23)
a.)
0, where Hy (s) and HQ a) are the entropy values of the search policy rooted and (s, a) respectively, and a, A₂ are the same as for BTS, as described in Section 4.1 Initial values are the same as Section 4.1 and the entropy values are initialised to zero. In DENTS we can view Q(s, a) + (() (s, a) as soft value for (s, a). Hence, by setting 3(m) a, the DENTS search will mimic the MENTS search (demonstrated in Appendix D.4). and if (m) then the algorithm reduces to the BTS algorithm. By using decaying function for 3 we amplify values using entropy as an exploration bonus early in the search while allowing for more exploitation later. Recommendations still use Bellman values:
for
UDENTS = arg max ((s,
(24)
aEA
Because the recommendation policy e'DENTS uses the Bellman values, we can guarantee that will converge to the optimal standard policy, and is consistent for any B.

---

Theorem 4.2. For any MDP M, after running trials of the DENTS algorithm with a root node of so, if B is a bounded function,, then there exists constants C, k > 0 such that for all >> 0 we have Eireg(Sv: su, VDENTS)) )1 I C
and also ((s) 2 (So) as n + cc.
TDENTS(als) for all 8, a, which exists because exp(-) > 0 and 1/|A| > 0 in Equation 20 (Lemma E.I.p which can be used with Hoeffding bounds to show for appropriate constants and any event E that (Pr(E) S Co (oxp(-koe))) Coexpp(kke"N(s))) iff (Pr(E) I C1 exp( (oxp(=kje" (s,,
Proof outline. Let 0 "
(ss, a,)}} iff (Pr(E) I C2 exp(pp - 22e (8(+1))) We can then show Pr(IQ(so, a) (s. > E) <
C3 exp (-kgE"n) by induction, where the base case (1 = V (s = holds vacuously (Lemmas E. 16 and Theorem E. Let AM be a small constant (Equation (122) such that Vs, a. ((o: a) - ( a)l S Am/2
arg m (ss a) = arg max, (* a). Setting = AM/2 2 gives bound on PI(UDENTS o T() which can then be used in the definition of simple regret to give the result.
4.3 Using the Alias method
The Alias method [35 34] can be used to sample from a categorical distribution with m categories in O(1) time, with a preprocessing step of (m)) time. Given any stochastic search policy, we can sample actions in amortised O(1) time, by computing an alias table every |.A] visits to a node, and then sampling from that table. Note that when using the Alias method we are making trade off between using the most up to date policy and the speed of sampling actions.
In Appendix C Tw discuss this idea in more detail, and give an informal analysis of the complexity to run n trials. BTS, DENTS and MENTS can run n trials in O(n( H log([AA)) + (A)) time when using the Alias method, as opposed to the typical complexity of O(nH (A).
4.4 Limitations and benefits
The main limitations of BTS and DENTS are as follows: (1) the DENTS decay function 3 can be non- trivial to set and tune; (2) the focus on simple regret and exploration means they are not appropriate to use when actions taken during the tree search/planning phase have real-world cost; (3) the backups implemented directly as presented above are computationally more costly than computing the average returns that UCT uses; (4) when it is desirable for an agent to follow the maximum entropy policy, then MENTS would be preferable, for example if the agent needs to explore to learn and discover an unknown environment.
The main benefits of using a stochastic policy for action selection are: (1) they allow the Alias method (Section 4.3) be used to speed up trials; (2) they naturally encourage exploration as actions are sampled randomly, which is useful for discovering sparse or delayed rewards and for confirming that actions with low values do in fact have a low value; and (3) the entropy of stochastic policy can be computed and used as an exploration bonus. In Appendix C.3 we summarise and compare the differences between the algorithms considered in this work in more detail.
5 Results
This section compares the proposed BTS and DENTS against MENTS and UCT on a set of goal-based MDPs and in the game of Go. For additional baselines, we also compare with the RENTS and TENTS algorithms [10], which use relative and Tsalis entropy in place of Shannon entropy respectively, and the H-MCTS algorithm
20 which combines UCT and Sequential Halving.
5.1 Gridworkds
To evaluate an algorithm with search tree T, we complete the partial recommendation policy vaat as follows:
if E T and a = vaagg
(alss)
0
if E T and a a Gaag (s),
(25)
otherwise.
7

---

Monte- Monte-Cari Value Estinato
0.8
Monte- Estimate
Algorihhm
Algorithm
UCT
UCT
MENTS
MENTS
-40
BTS
DENTS
DENTS
RENTS
RENTS
-100
HM
-120
HMGTS
100
200
300
400
150
250
300
Number of Trials 0x1003)
Number Trials (x1003)
(a) 8x12 Frozen Lake.
(b) 6x6 Sailing Problem.
Figure Results for gridworld environments. Further results are given in Appendix D.3
We sample number of trajectories from eh and take the average return to estimate V Although we are evaluating the algorithms in an offline planning setting, still indicates how the algorithms perform in an online setting where we interleave planning in simulation with letting the agent act.
5.1.1 Domains
To validate our approach, we use the Frozen Lake environment 5 and Sailing Problem (28). commonly used to evaluate tree search algorithms [28 22 compare our algorithms in a domain with sparse and dense reward respectively.
33 13
We chose these environments to
The (Deterministicc Frozen Lake is grid world environment with one goal state. The agent can move any cardinal direction at each location. Trap states exist where the agent falls into a hole and the trial ends. If the agent arrives at the goal state after timesteps, then a reward of 0.99* is received.
step, and walking into wall leaves the agent in the same
The Sailing Problem a grid world environment with one goal state, at the opposite corner to the starting location of the agent. The agent has 8 different actions travel each the 8 adjacent states. In each state, the wind is blowing in a given direction and will stochastically change after every transition. The agent cannot sail directly into the wind. The of each action depends the tack, the angle between the direction of the agent's 's travel and the wind.
5.1.2 Results
We used 8x12 Frozen Lake environment and a 6x6 Sailing Problem for evaluation, more environ- ment details are given in Appendix D.I Parameters were selected using hyper-parameter search (Appendix D.3. Each algorithm is run 25 times on each environment and evaluated every 250 trials using 250 trajectories. A horizon of 100 was used for Frozen Lake and 50 for the Sailing Problem.
In Frozen Lake (Figure Ba), entropy proved to be useful exploration bonus for the sparse reward. Values in UCT and BTS remain at zero until a trial successfully reaches the goal. However, entropy guides agents avoid trap states, where the entropy is zero. DENTS was able to perform similarly to MENTS, and BTS was able to improve its policy over time more than UCT.
In the Sailing Problem (Figure 3b UCT performs well due the dense reward. BTS and DENTS also manage to keep up with UCT. MENTS and TENTS appear to be slightly hindered by entropy in this environment. The relative entropy encourages RENTS pick the same actions over time, tends to pick direction and stick with it regardless of cost.
Finally, BTS and DENTS were able to perform well in both domains with a sparse and dense reward structure, whereas the existing methods performed better on one than the other, hence making BTS and DENTS good candidates for a general purpose MCTS algorithm.

---

5.2 Go
For more challenging domain we ran round-robin tournament using the game of Go, which has widely motivated the development of MCTS methods [14] 30 32]. In each match, each algorithm played 50 games as black and 50 as white. Area scoring is used to score the games, with a komi of
7.5. We used an openly available value network V and policy network from KataGo [36]. Our baseline was the PUCT algorithm 2. as described in Alpha Go Zero [3 using prioritised UCB [29] to utilise the policy neural network. Each algorithm was limited to 5 seconds of compute time per move, allowed to use 32 search threads per move, and had access to 80 Intel Xeon E5-2698V4 CPUs clocked at 2.2GHz, and a single Nvidia V100 GPU on a shared compute cluster.
To use Boltzmann search in Go, we adapted the algorithms to account for an opponent that wishes to minimise the value of a two-player game. This achieved by appropriately negating values used in the search policy and backups, which is described precisely in Appendix C.2
Additionally, we found that adapting the algorithms to use average returns (recall Equation outperformed using Bellman backups for Go (Appendix [D..T). The Bellman backups were sensitive to and propogated noise from the neural network evaluations. We use the prefix 'AR' to denote the algorithms using average returns, such as AR-DENTS. Full details for these algorithms are given in Appendix B
5.2.1 Using neural networks with Boltzmann search
This section describes how to use value and policy networks in BTS. Adapting MENTS and DENTS are similar (Appendix C.2 Values can be initialised with the neural networks as Q(, a) <- log {a)ss) + B and V (s) f (ss), where B is a constant (adapted from Xiao et al. (37). With such an initialisation, the initial BTS policy is PBTS (ats(als) x {als))//a For these experiments we set value of B- | to mixing in a prior policy, so we can replace BTS search policy TBIS (Equation (15) with m
T EaEa A log (a s). Additionally, the stochastic search policy naturally lends itself
TBTS (als) x {xa((as) + Xa TBTTss(())s))
(26)
=>xã(alss) + (1 )1 Ae) (1 -1-a (1-dx)4, Ax
(27)
[A]
where Aa min(1, e log(e (s))), and ea e (0, oo) controls the weighting for the prior policy.
5.2.2 Results
Results of the round-robin are summarised in Table and we discuss how parameters were selected in Appendix D.5.I BTS was able run the most trials per move and beat all of the other algorithms other than DENTS which it drew. We used the optimisations outlined in Appendix [ which allowed the Boltzmann search algorithms DENTS were able to beat PUCT with results of 57-43 and 58-42 respectively. Using entropy did not seem to have much benefit in these experiments, as can be witnessed by MENTS only beating TENTS, and DENTS drawing 50-50 with BTS. This is likely because the additional exploration provided by entropy is vastly outweighed by utilising the information contained in the neural networks V and f. Interestingly RENTS had the best performance out of the prior works, losing 43-57 to PUCT, and the use of relative entropy appears to take advantage of heuristic for Go that the RAVE [15 algorithm used: the value of a move typically unaffected by other moves on the board.
run significantly more trials per move than PUCT. BTS and
To validate the strength of our PUCT agent, we also compared it directly with KataGo (36], limiting each algorithm to 1600 trials per move. Our PUCT agent won 61-39 in 9x9 Go, and lost 35-65 in 19x19 Go, suggesting that our PUCT agent is strong enough to provide meaningful comparison for our other general purpose algorithms. Finally, note that we did not fine-tune the neural networks, so the Boltzmann search algorithms directly used the networks that were trained for use in PUCT.
Related work
UCT 22
a widely used variant of MCTS. Polynomial UCT 2 replaces the logarithmic term in UCB with polynomial one (such square root), which has been further popularised by its use
23

---

Black White
PUCT
AR-M
AR-R
AR-T
AR-B
AR-D
Trials/move
PUCT
33-17
27-23
42-8
17-33
15-35
1054
AR-MENTS
12-48
13-37
38-12
10-40
12-38
4851
AR-RENTS
20-30
24-26
39-11
18-32
14-36
3672
AR-TENTS
8-42
11-39
9-41
6-44
10-40
5206
AR-BTS
25-25
35-15
31-19
34-16
15-35
5375
AR-DENTS 23-27
36-14
29-21
36-14
15-35
4677
Table 1: Results for the Go round-robin tournament. The first column gives the agent playing as black. The final column gives the average trials run per move across the entire round-robin. In the top row, abbreviate the algorithm names for space.
in Alpha Go and Alpha Zero 30
Coquelin and Munos introduce the Flat-UCB and BAST algorithms to adapt UCT for the D-chain problem [9]. However, we consider an alternative approach for search in MCTS rather than adapting UCB.
32
31)
Maximum entropy policy optimization methods are well-known the reinforcement learning litera- ture [66 17 38). MENTS 37 is the first method to combine the principle of maximum entropy and MCTS. Kozakowski et al. 25 extend MENTS to arrive at Adaptive Entropy Tree Search (ANTS), adapting parameters throughout the search to match prescribed entropy value. Dam et al. [TO] also extend MENTS using Relative and Tsallis entropy to arrive at the RENTS and TENTS algorithms. Our work is closely related MENTS, however, focus reward maximisation and consider how entropy can be used in MCTS without altering our planning objective.
Bubeck al. S introduce simple regret in the context of multi-armed bandit problems (MABs). They alternate between pulling arms for exploration and outputting a recommendation They show for MABs that uniform exploration produces exponential bound the simple regret of recom- mendations. We use simple regret, but in the context of sequential decision- decision-making, to analyse the convergence of MCTS algorithms.
Tolpin and Shimony 33 extend simple regret MDP settings, showing an (eepp( -vn) bound on simple regret after n trials by adapting UCT. The subsequent work of Hay et al. [19 extends
33 to consider a metalevel decision problem, incorporating computation costs into the objective.
Pepels et al. [27] introduce Hybrid MCTS (H-MCTS) motivated by the notion of simple regret.
H-MCTS uses a mixture of Sequential Halving (00], and UCT. Feldman et al. [3 [2] introduce
the Best Recommendation with Uniform Exploration (BRUE) algorithm. BRUE splits trials up to
explicitly focus on exploration and value estimation one at time. BRUE achieves an exponential
simple regret after trials [3] Prior work that considers simple regret in MCTS has focused on adaptations to UCT, whereas this work focuses on algorithms that sample actions from Boltzmann distributions, rather than using UCB for action seclection.
bound (eexp--n)
Conclusion
We considered the recently introduced MENTS algorithm, compared and contrasted it to UCT, and discussed the limitations of both. We introduced two new algorithms, BTS and DENTS, that are consistent, converge to the optimal standard policy, while preserving the benefits that come with using a stochastic Boltzmann search policy. Finally, we compared our algorithms in gridworld environments and Go, demonstrating the performance benefits of utilising the Alias method, that entropy can be useful exploration bonus with sparse rewards, and more generally, demonstrating the advantage of prioritising exploration in planning, by using Boltzmann search policies.
An interesting area of future work may include investigating good heuristics for setting parameters in BTS and DENTS. We noticed that the best value for the search temperature tended to be the same order of magnitude as the optimal value at the root node V* (s0)), which suggests a heuristic similar (21) may be reasonable.
References
[1] Peter Auer. Nicolo Cesa Bianchinn and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
10

---

[2] David Auger, Adrien Couetoux, and Olivier Teytaud. Continuous upper confidence trees with polynomial exploration-connisteeyy In Joint European Conference Machine Learning and Knowledge Discovery in Databuses, pages 194-209. Springer. 2013.
[3] Richard Bellman. markovian decision process. Journal of mathematics and mechanics, 6(5)667--684, 1957.
Blai Bonet and Hector Geffner. Labeled rtdp: Improving the convergence of real-time dynamic program- ming. In ICAPS, volume 3, pages 12-21, 2003.
[5] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wajeiech Zaremba. Openai gym. arXiv preprint 1rXivv1606.0154 2016.
[6] Cameron Browne, Edward Powley, Daniel Whitehouse. Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
[7] Sébastien Bubock, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference Algorithuic learning theory, pages 23 23-37. Springer, 2009.
[8] Sébastien Bubeck. Rémi Munos, and Gilles Stoltz. Pure exploration in finitely- armed and continuous armmed bandits. Theoretical Computer Science, (12((19)1832-118 1852, 2011.
[9] Pieare-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search. In Unceriainty in Artificial Intelligence, 2007.
[10] Tuan Q Dam, Carlo D' D'Eramo, Jan Peters, and Joni Pajarinen, Convex regularization in monte-carlo tree search. In International Conference Machine Learning, pages 2365-2375. PMLR, 2021.
[11] Zohar Feldman and Carmel Domshlak. Monte-carlo planning: Theoretically fast convergence meets practical efficiency. arXiv preprint 130.vv300966266 2013.
[12] Zohar Feldman and Carmel Domshlak. On mabs and separation of concerns in monte-carlo planning for mdps. In Twenty-Foud Fourth International Conference on Automated Planning and Scheduling, 2014.
[13] Zohar Feldman and Carmel Domshlak. Simple regret optimization in online planning for markov decision processes. Journal of Artificial Intelligence Research, 51:165 205, 2014.
[14] Sylvain Gelly and David Silver. Combining online and offline knowledge in uct. In Proceedings of the 24th international conference on Machine learning, pages 273-280, 2007.
[15] Sylvain Gelly and David Silver. Monte-carlo search and rapid action value estimation in computer go. Artificial Intelligence, 1856 2011.
[16] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-hased policies. International Conference on Machine Learning, pages 1352-1361. PMLR, 2017.
[17] Tuomas Haarojj,, Aurick Zhou, Pieter Abbecl, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870, PMLR, 2018.
[18] Eric A Hansen and Shlomo Zilberstein. Lao"; A heuristic search algorithm that finds solutions with loops. Artificial Intelligence, 129(1-2):35-66 62, 2001.
[19] Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony. Selecting computations: Theory and applications. arXiv preprint 4Xivv:408.224 2014.
[20] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR, 2013.
[21] Thomas Keller and Patrick Eyerich. Prost: Probabilistic planning based on uct. In Twenty-Second International Conference on Automated Planning and Scheduling, 2012.
[22] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-293. Springer, 2006.
[23] Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006.

---

[24] Andrey Kolobov. Planning with Markov Decision Processes: An Al Perspective, volume 6. Morgan & Claypool Publishers, 2012.
[25] Piotr Kozakowski, Mikolaj Pacek, and Piotr Mitos. Planning and learning using adaptive entropy tree search. arXiv preprint 0rX1v:2102.06808. 2021.
[26] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30, 2017.
[27] Tom Pepels, Tristan Cazenave, Mark HM Winands, and Mare Lanctot. Minimizing simple and cumulative regret monte-carlo tree search. In Workshop on Computer Games, pages 1-15. Springer, 2014.
[28] Laurent Péret and Frédérick Garcia. On-line search for solving markov decision processes via heuristic sampling. learning, 16:2, 2004.
[29] Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):003-300, 2011.
[30] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittweserr, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[31] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419)) (1164419)1140-111 140-1 144, 2018.
[32] 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-359 2017.
[33] David Tolpin and Solomon Shimony. Mets based on simple regret. In Proceedings of the AAAI Conference Artificial Intelligence, volume 26, pages 570-576, 2012.
[34] Michael D Vose. A linear algorithm for generating random numbers with a given distribution. IEEE Transactions on software engineering, 1709):72-975, 1991.
[35] Alastair Walker. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters, 8(10):127-128. 1974.
[36] David J Wu, Accelerating self-play learning in go. arXiv preprint arXiv: 10565, 2019.
[37] Chenjun Xiao, Ruitong Huang. Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. Advances in Neural Information Processing Systems, 32, 2019.
[38] Brian Zichart, Andrew Maas, Andrew Bagnell, Anind K Dey, al. Maximum entropy inverse reinforcement learning. 2008
12


Reviews:
[{"review_id": "FEK5vYEX1z", "reviewer": "Reviewer_nux6", "summary": "The paper presents two MCTS based algorithms called  Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS). These algorithms overcome the limitation of two state-of-the-art algorithms pUCT and MENTS of under and over exploration respectively. Further, the paper provides simple “simple regret” analysis and shows state-of-the-art performance on benchmark tasks.", "questions": "1. Line number 18 - What do you mean by “exact methods”?\n2. Why H-MCTS [27] (or other algorithms that focus on simple regret) is not used as a baseline?\n3. Are there no approaches that study how to decrease alpha in MENTS so that Theorem 2-like statement holds?\n4. How to set the value of alpha in BTS?\n5. Why are RENTS and TENTS not compared on Frozen Lake?\n", "limitations": "Limitations are clearly mentioned in the paper.              ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is very well structured and easy to follow for the most part.\n2. The empirical results are impressive, especially on Go.\n3. The algorithms are novel to my knowledge and are inspiring.\n", "weaknesses": "1. The motivation for analyzing simple regret instead of cumulative regret is not clear. This limits the contribution of the proposed approach to some extent. (I will update the score post rebuttal, given the authors' response).\n2. The paper puts all the theoretical proof in the appendix. Please provide at least a proof sketch in the main paper. \n3. Section 6.1 is not clearly written. What do you mean by “ To utilize ... a terminal/goal state.” (lines 232-234)\n\nMinor\n1. Graphs in Figure 2 are of poor quality. Please consider using transparent lines or a variety of dashed lines (different patterns of dashes) to represent different algorithms.\n2. Please increase the font size of the text in Figure 3.\n\nNote: I haven't carefully taken a look at the proofs in the appendix. I might update my score based on correctness.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Firstly thank you for taking the time to review our work and provide helpful feedback.\n\n> The motivation for analyzing simple regret instead of cumulative regret is not clear. This limits the contribution of the proposed approach to some extent.\n\nCumulative regret is more appropriate in situations where taking actions during the planning/learning stage corresponds to interacting with the real world, and hence there is a need to explicitly consider the cost accumulated by taking actions. However, our setting considers planning using a model or simulator, without any interaction with the real world during the planning stage. Simple regret is more appropriate in this setting, because it ignores the cost of simulated actions during planning, and only considers the cost of the action executed in the real world, once the planning stage is complete. By considering simple regret, algorithms are not penalised for under-exploiting during the planning stage and are thus able to explore more effectively, leading to better recommended actions.\n\nPlease also note Reviewer f8iz’s comments on the importance of using simple regret in our work. They provided some suggestions for motivating its use similar to Tolpin & Shimony et al [1, 2], which we paraphrased above and will add to the paper.\n\n> The paper puts all the theoretical proof in the appendix. Please provide at least a proof sketch in the main paper.\n\nWe will add short proof outlines to the paper, and make space for this by making the introduction and background sections more concise.\n\n> Section 6.1 is not clearly written. What do you mean by “ To utilize ... a terminal/goal state.” (lines 232-234)\n\nWe wanted to make clear that we use horizons that are long enough for the trials to terminate because the agent either reached the goal or fell into a hole, rather than terminating because the max horizon length was reached. We used planning horizons of 100 and 50 on the Frozen Lake and Sailing environments, respectively. We will edit the paper to make this clearer.  \n\n> Line number 18 - What do you mean by “exact methods”?\n\nWe were referring to methods that compute a full policy, such as value iteration. We will update the wording to instead specify methods that compute a full policy.\n\n> Why H-MCTS [27] (or other algorithms that focus on simple regret) is not used as a baseline?\n\nWe will update the paper to include H-MCTS in the evaluation. To the best of our knowledge, prior MCTS algorithms designed for simple regret, such as H-MCTS [3] and BRUE [4], are adapted from UCT. As such we believe that our empirical results using UCT still give a good indication of how these other algorithms would perform in practise. \n\n> Are there no approaches that study how to decrease alpha in MENTS so that Theorem 2-like statement holds?\n\nWe actually tried decaying the temperature parameter in MENTS with respect to node visits. It is true that such an algorithm can achieve a similar simple regret bound to BTS and DENTS, but we found it didn’t work well in practise. To try and explain why: consider the maximum entropy objective from Equation (3) in the paper. Reducing the value of $\\alpha$ changes the weighting of the entropy at that node in Equation (3). When the root node’s $\\alpha$ becomes small, the search policy (Equation (11)) becomes increasingly greedy and stops exploring close to the root node. The root node’s child values $\\hat{Q}^{N(s_0,a)}_{\\text{sft}}(s_0,a)$ include values that were computed from backups with high values of $\\alpha$ because they have been visited less times than the root. This becomes problematic because the algorithm stops exploring close to the root node, and selected greedily based on Q-values that were propagated from nodes still considering high values of $\\alpha$. It was the issues with this algorithm that motivated our design of DENTS, to explicitly compute separate Bellman and (subtree) entropy values and decay the weighting on the entropy term.\n\n> How to set the value of alpha in BTS?\n\n$\\alpha$ is a hyperparameter that needs to be tuned to get the best performance out of BTS, similar to the temperature in MENTS and the bias parameter in UCT. Across our experiments, the best value of alpha tended to be in the range of $V^*(s_0)/2$ to $V^*(s_0)/10$, so it may be possible set $\\alpha=\\hat{V}(s)/2$ for example to scale $\\alpha$ using value estimates in the tree similar to [5].\n\n> Why are RENTS and TENTS not compared on Frozen Lake?\n\nWe did run RENTS and TENTS on Frozen Lake, the results can be seen in Figure 29 in the appendix. It was an oversight to not include them in the main paper, and we will update Figure 3 to include these results and present them more clearly. RENTS and TENTS performed similarly to MENTS and DENTS, which is in line with the maximum entropy objective (and its variants) being a useful exploration bonus in this sparse reward environment.\n\nAs suggested we will make the following updates to the paper:\n- Update the graphs in Figure 2 to use different line styles with markers to make the overlapping lines more clear\n- Increase the font sizes in figures for clarity\n\n[1] David Tolpin and Solomon Shimony. Mcts based on simple regret. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pages 570–576, 2012 \n\n[2] Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony. Selecting computations: Theory and applications. arXiv preprint arXiv:1408.2048, 2014\n\n[3] Tom Pepels, Tristan Cazenave, Mark HM Winands, and Marc Lanctot. Minimizing simple and cumulative regret in monte-carlo tree search. In Workshop on Computer Games, pages 1–15. Springer, 2014\n\n[4] Zohar Feldman and Carmel Domshlak. Simple regret optimization in online planning for markov decision processes. Journal of Artificial Intelligence Research, 51:165–205, 2014\n\n[5] Thomas Keller and Patrick Eyerich. Prost: Probabilistic planning based on uct. In Twenty-Second International Conference on Automated Planning and Scheduling, 2012"}, {"review_id": "4txeDirwSH", "reviewer": "Reviewer_gH3c", "summary": "<< I have read the authors' rebuttal and have raised my score based on the discussion >>\n\nThe paper addresses challenges in online tree-based search algorithms, such as UCT, which have shortcomings such as being prone to local optima and a slower convergence rate to the optimal action. An alternative approach, Maximum ENtropy Tree Search (MENTS), despite theoretically optimal performance, has practical limitations like sensitivity to the temperature parameter, a tendency to over explore, and increased computational expense. The authors present two new algorithms to address these issues: Boltzmann Tree Search (BTS) and Decaying ENtropy Tree Search (DENTS). BTS employs a Boltzmann search policy, focusing solely on reward maximisation, whereas DENTS introduces entropy backups that can be used with varying weighting in the search. Both algorithms preserve the exploratory benefits of MENTS, and importantly, they consistently converge to the optimal reward maximising policy. Key contributions of the paper include highlighting the misalignment of the entropy objective in MENTS with reward maximisation, introducing BTS and DENTS, providing an analysis of MENTS, BTS, and DENTS through the lens of simple regret, and demonstrating the improved performance of BTS and DENTS over other MCTS algorithms in specific environments and games.", "questions": "Q1: I found it somewhat surprising that MENTS performed relatively poorly on the game of Go, especially considering its strong performance in other domains. Can you confirm whether the temperature hyperparameter for MENTS was appropriately tuned in this case?\n\nQ2: What methodologies were employed by the authors to tune the hyperparameters for different baseline algorithms, including BTS and DENTS?\n\nQ3: To better understand the influence of hyperparameters on BTS and DENTS and gauge their robustness, would it be possible for the authors to compare their performance for varying values of the alpha parameter?", "limitations": "The authors discussed the limitations of their work. No discussion needed regarding potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Novelty: The presented Boltzmann Tree Search (BTS) algorithm is a variant of the Maximum ENtropy Tree Search (MENTS), substituting the soft update value in equation 13 with the max operator in equation 19. The Decaying ENtropy Tree Search (DENTS) proposes a novel method for decaying exploration to ultimately converge to the optimal solution, an aspect MENTS struggles with due to its focus on maintaining entropy in the search policy. The novelty of this paper's contributions, while discernible, seems to be limited.\n\nClarity: While the paper is generally well-written, comprehension is somewhat impeded by the multitude of mathematical symbols and technical jargon used throughout. An effort to streamline and elucidate the language could significantly enhance readability.\n\nSignificance: The paper's experimental results highlight DENTS' robustness to the adjustment of the temperature hyperparameter, a critical element in MENTS. Moreover, the simplicity of the proposed changes augments their potential for practical adoption in the field.", "weaknesses": "W1: The novelty of the work seems somewhat limited. It remains unclear whether the improvements result from the incorporation of entropy in the case of DENTS or from the use of hard updates instead of soft updates in BTS.\n\nW2: The paper emphasizes the sensitivity of MENTS to the temperature hyperparameter. It is true that many online search algorithms rely on hyperparameter tuning for optimal performance. However, it is noteworthy that MENTS outperforms both BTS and DENTS on the 10-chain and gridworld tasks when the temperature hyperparameter is appropriately tuned. Therefore, it could be argued that the only advantage of using BTS or DENTS is their lesser dependency on temperature. Yet, with the correct tuning of this singular parameter, MENTS could potentially offer a superior solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Firstly, thank you for reviewing our work and giving us valuable feedback.\n\n> Q3: To better understand the influence of hyperparameters on BTS and DENTS and gauge their robustness, would it be possible for the authors to compare their performance for varying values of the alpha parameter?\n\nWe varied the temperature parameters of all of the algorithms on an 8x8 Frozen Lake environment (Figure 5a) in Figures 26, 27 and 28 in Appendix C.2.2. These figures show that for high temperatures in Frozen Lake, MENTS and TENTS fail to find the optimal paths, while BTS and DENTS for the same temperatures do find the optimal paths. RENTS did not suffer from the same parameter sensitivity in Frozen Lake, however, it also behaved similarly to UCT (i.e. it never found the reward of 1.0) on the D-chain environments as can be seen in Figures 10 and 16 from Appendix C.2.1 (the corresponding results for UCT are given in Figures 8 and 14).\n\n> W1: The novelty of the work seems somewhat limited. It remains unclear whether the improvements result from the incorporation of entropy in the case of DENTS or from the use of hard updates instead of soft updates in BTS.\n\nWe believe there are advantages to using Boltzmann search policies in MCTS, as they allow for greater exploration during planning, and are able to achieve better simple regret bounds than UCT [1]. Thus, theoretically they can provide better recommendations. \n\nUsing entropy encourages exploration and for example can be advantageous in domains with sparse rewards such as Frozen Lake. However, it can also hinder performance in some environments, as can be seen in our results for Go where BTS outperformed the other algorithms. However, BTS will outperform DENTS when the reward signal is more dense and tailored to drive exploration without needing entropy, since BTS doesn’t have the additional computational overhead of the entropy backup. As such, it is useful to utilise the advantages of Boltzmann search policies, while having the option whether to use an entropy objective or not, depending on how informative the reward signal is.\n\n> W2: … However, it is noteworthy that MENTS outperforms both BTS and DENTS on the 10-chain and gridworld tasks when the temperature hyperparameter is appropriately tuned. Therefore, it could be argued that the only advantage of using BTS or DENTS is their lesser dependency on temperature. Yet, with the correct tuning of this singular parameter, MENTS could potentially offer a superior solution.\n\nIn cases where MENTS would outperform BTS, we can tune DENTS to match the performance of MENTS. Specifically, we can set $\\beta(m)=\\alpha$ in DENTS, so that the search policy is similar to the MENTS search policy, while still using Bellman values for recommendations. See Figure 1 in the rebuttal pdf to see DENTS running under this configuration versus MENTS on the D-chain and Frozen Lake environments. \n\n> Q2: What methodologies were employed by the authors to tune the hyperparameters for different baseline algorithms, including BTS and DENTS?\n\nTo tune the algorithms on the gridworld environments, we performed a grid-search over the UCT bias, search temperature $\\alpha$ and MENTS exploration parameter $\\epsilon$ that were relevant for each algorithm. For DENTS we set $\\beta(m)=\\alpha/\\log(e+m)$. In Frozen Lake the parameters that achieved the best value after 500k trials on the 8x12 Frozen Lake from Figure 5b were selected for the test environment from Figure 5c. In the Sailing problem we performed the same routine, using an initial wind direction of North for parameter selection and initial wind direction of South-East for evaluation. Full details are given in Appendix C.4.\n\nIn the Go experiments, we tuned parameters using round-robin tournaments varying one parameter at a time. We selected the value that won the most matches (a match being the combined score playing an equal number of games as black and white) and broke ties using the number of games won over the tournament. Full details are given in Appendix C.5.\n\n> Q1: I found it somewhat surprising that MENTS performed relatively poorly on the game of Go, especially considering its strong performance in other domains. Can you confirm whether the temperature hyperparameter for MENTS was appropriately tuned in this case?\n\nWe followed the methodology outlined above for tuning MENTS temperature for Go. However, the temperature selected in the paper was the smallest value that we tried, suggesting that lower values might perform better. We have since run more games to tune the MENTS hyperparameter (Table 2 in author rebuttal) and have updated the results for 9x9 Go (Table 3 in author rebuttal). After updating the MENTS temperature parameter it still lost all of its matches, with its closest result being a 31-69 loss to TENTS. MENTS migt not perform as well on Go because often in games there will be *critical moves* that an agent needs to make and entropy may encourage prioritising moves that are not the critical move. Full details on hyperparameter selection for the Go experiments can be found in Appendix C.5.2. \n\n[1]  Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23–37. Springer, 2009. "}, {"review_id": "9goiggMdg7", "reviewer": "Reviewer_yYGy", "summary": "This paper proposes two new algorithms, Boltzmann Tree Search (BTS) and Decaying Entropy Tree Search (DENTS), based on the Maximum Entropy Tree Search (MENTS) method. The authors prove that in certain situations, MENTS fails to converge to the optimal policy. They analyze BTS and DENTS using simple regret and show that these algorithms will recommend the optimal actions. Finally, the authors evaluate various MCTS algorithms, where BTS and DENTS significantly outperform other MCTS algorithms.", "questions": "1. The authors mention that MENTS may struggle to converge under certain specific circumstances by using the D-Chain as an example. However, it is unclear whether this phenomenon generally happens in other environments.\n\n2. The author mentions the difficulty of selecting β. The experiments also show that BTS (DENTS with β=0) performs better than DENTS. Do the authors conduct any analysis or have any suggestions for β? In what scenarios where DENTS will perform better than BTS?\n\n3. The author claims that DENTS will be similar to MENTS when setting β(m) = α, is there any experimental/theoretical explanation for this part? The relationship is a bit unclear from the mathematical formula.\n\n4. How does MCTS operate in a stochastic environment for Sailing problems?\n\n5. Why were RENTS and TENTS only tested on the 6x6 Sailing Problem and not on the 8x12 Frozen Lake?\n\nOther minor suggestions:\n1. The lines in Figure 2 are overlapping, making it difficult to see clearly.\n2. In equation (4), should it be $V_{\\text{sft}}^{\\pi}(s', t)$ or $V^{\\pi}_{\\text{sft}}(s', t + 1)$?", "limitations": "The authors addressed their limitations in section 5.3.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-structured, with clear explanations of the concepts and methods used.\n2. The paper identifies the limitations of MENTS and proposes two new algorithms, BTS and DENTS, to address the issues of MENTS. The authors conduct theoretical analysis and perform experiments to validate their proposed solutions.\n3. The experiments show that the proposed algorithms outperform other MCTS algorithms.", "weaknesses": "It is not quite convincing for the baseline program used in the Go experiments. The Komi in 9x9 Go is usually set to 7 (a balanced setting for both players). Black will have an advantage when Komi is set to 6.5. In addition, in Table 1, does PUCT have the same performance (strength) as KataGo? Why not compare the AR-* methods to KataGo directly? Besides, it is quite confusing why the author uses 128 CPU threads. To the best of my knowledge, this is not the best machine configuration for running KataGo. Using 128 CPU threads may even hurt the performance of KataGo. Moreover, in line 266, the authors said they added Dirichlet noise at the root node. In AlphaGo Zero, there is no need to add Dirichlet noise during evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Firstly, thank you for your review and comments to help us improve our paper.\n\n> The Komi in 9x9 Go is usually set to 7 (a balanced setting for both players). Black will have an advantage when Komi is set to 6.5.\n\nWe chose a komi of 6.5 because it is commonly used by humans in 9x9 Go and a half-integer komi ensures all games were decisive. Black will have an advantage in 9x9 Go with a komi of 6.5 and the comparison is still fair as each algorithm is given an equal number of games as black and white.\n\n> In addition, in Table 1, does PUCT have the same performance (strength) as KataGo? Why not compare the AR-* methods to KataGo directly?\n\nWe didn’t compare the AR-* algorithms directly to KataGo because our paper is about general purpose search algorithms. To ensure the evaluation is implementation independent we used a common implementation between our MCTS algorithms. KataGo uses a variety of heuristics on top of standard PUCT [1] and is a domain-specific library that has been optimised for Go. Our work does not intend to be a new state-of-the-art for Go, and KataGo will beat our algorithms given the same time constraints. Our algorithms could be incorporated into and potentially improve an MCTS agent such as KataGo. However, this is beyond the scope of this paper, which proposes a general-purpose planning approach.\n\n> Besides, it is quite confusing why the author uses 128 CPU threads. … In AlphaGo Zero, there is no need to add Dirichlet noise during evaluation.\n\nWe ran `./katago benchmark` and it recommended 32 search threads for KataGo. In Table 1 in our author rebuttal, we also found that the best number of threads to use for PUCT was 32. \n\nWhen updating our results (Table 3 of the author rebuttal), we ran PUCT with and without adding Dirichlet noise. In each match, the agent with Dirichlet noise won more games so we have kept those results, suggesting that considering novel moves was still useful. We also ran PUCT+Dirichlet noise against PUCT, and the agent adding noise won with a score of 28-23. \n\n> The authors mention that MENTS may struggle to converge under certain specific circumstances by using the D-Chain as an example. However, it is unclear whether this phenomenon generally happens in other environments.\n\nMENTS parameter sensitivity can also be demonstrated in the Frozen Lake environment, as can be seen in Figure 26 in the appendix. This figure includes BTS and DENTS running with the same temperatures for reference. \n\n> The author mentions the difficulty of selecting β. The experiments also show that BTS (DENTS with β=0) performs better than DENTS. Do the authors conduct any analysis or have any suggestions for β? In what scenarios where DENTS will perform better than BTS?\n\nIn our experiments, we typically set $\\beta(m)=\\alpha/\\log(e+m)$ to reduce the search space over hyperparameters. The best way to set $\\beta$ will depend on the environment. Currently, as a rule of thumb, we recommend using $\\beta(m)=\\beta_{\\text{init}}/\\log(e+m)$ and then tuning the value of $\\beta_{\\text{init}}$ for the specific environment. If a large amount of exploration is desired then $\\beta_{\\text{init}}$ can be set to a large value, while still allowing $\\beta$ to decay to zero at the root of the tree and encourage exploration in deeper parts of the tree. Sometimes entropy may be disadvantageous, such as in our Go experiments, in which case using BTS ($\\beta(m)=0$) performs better.\n\nDENTS will outperform BTS when entropy is a useful exploration bonus, such as in cases where rewards are sparse and Frozen Lake is a good example of this. In Frozen Lake states that correspond to falling down a hole have an entropy of 0, and so the entropy bonus encourages DENTS (and other entropy algorithms) to explore paths that don’t fall into the holes. This benefit can be seen in Figure 3a, where BTS is slower to converge than DENTS and MENTS.\n\n> The author claims that DENTS will be similar to MENTS when setting β(m) = α, is there any experimental/theoretical explanation for this part? The relationship is a bit unclear from the mathematical formula.\n\nFigure 1 in the author rebuttal empirically demonstrates the similarity of running DENTS with $\\beta(m)=\\alpha$ and MENTS on the D-chain and Frozen Lake environments. A theoretical relationship may be possible as Lemma 4 and Corollary 5 from [2] suggests that optimal soft values can be written as a sum of an optimal soft Q-values and an entropy term, similar to the “soft values” we use in DENTS.\n\n> How does MCTS operate in a stochastic environment for Sailing problems?\n\nMCTS handles stochastic environments by using decision and chance nodes. Decision nodes correspond to states, chance nodes correspond to state-action pairs, and child nodes are selected by sampling from the transition distribution $p(s’|s,a)$. The work in [3] is a good reference for the use of MCTS for planning under uncertianty. \n\n> In equation (4), should it be t or t+1?\n\nIt should be $t+1$, thank you.\n\n> Why were RENTS and TENTS only tested on the 6x6 Sailing Problem and not on the 8x12 Frozen Lake?\n\n(Repeated from response to reviewer nux6) \nWe did run RENTS and TENTS on Frozen Lake, the results can be seen in Figure 29 in the appendix. It was an oversight to not include them in the main paper, and we will update Figure 3 to include these results and present them more clearly. RENTS and TENTS performed similarly to MENTS and DENTS, which is in line with the maximum entropy objective (and its variants) being a useful exploration bonus in this sparse reward environment.\n\n[1] https://github.com/lightvector/KataGo/blob/master/docs/KataGoMethods.md\n\n[2] Nachum, Ofir, et al. \"Bridging the gap between value and policy based reinforcement learning.\" Advances in neural information processing systems 30 (2017)\n\n[3] Keller, Thomas, and Malte Helmert. \"Trial-based heuristic tree search for finite horizon MDPs.\" Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 23. 2013"}, {"review_id": "uE9vZ4PVHV", "reviewer": "Reviewer_f8iz", "summary": "This paper introduces two variants of MCTS designed to perform more exploration during search than the commonly used UCT search policy, while resolving an issue with a previously introduced MCTS variant, Maximum ENtropy Tree Search (MENTS), which was designed to explore more than UCT, but which does not converge to the optimal policy / value function with an increasing number of MCTS trials.\n\nTo address this issue, the authors modify MCTS in two different ways. In the first variant, Boltzmann Tree Search (BTS), the authors use a Boltzmann search policy during the selection/search phase of MCTS, instead of using UCT, but perform a regular Bellman backup to compute state and action values. In the second variant, Decaying ENtropy Tree Search (DENTS), they modify MENTs to separately keep track of the policy entropy and the (unmodified) value functions, allowing them to slowly decay the entropy contribution over time, while using the entropy-augmented value functions to drive exploration during search. Both variants of MCTS are consistent -- i.e. they value function they compute for the root node converges to the optimal value as the number of MCTS trials increases, and the simple regret decays exponentially with respect to the number of MCTS trials.\n\nThe authors evaluate BTS and DENTS against baseline methods on both toy MDP problems, and in a 9x9 Go round-robin tournament. They find that BTS and DENTS perform similarly or slightly better than existing baselines on the toy problems, and consistently outcompete other methods (modified to make use of neural-networks) in the Go tournament.", "questions": "- Why does the search temperature $\\alpha$ in DENTS differ from the entropy weighting term $\\beta$? By default (e.g. in MENTS) this should be the same -- is there a reason why it makes sense have them vary separately? Why not decay $\\alpha$ with increasing node visits as well?\n\n- In the AR version of DENTS used for the Go experiments, both $\\alpha$ and $\\beta$ are decayed. AR-MENTS is then described as a variant of AR-DENTS, where $\\alpha$ is set equal to $\\beta$. But in AR-MENTS, are $\\alpha$ and $\\beta$ set to a fixed value, or decayed with increasing node visits? I'm assuming it's the former, in which case that should be clarified in the Appendix, but if it's the latter, how is AR-MENTS different from AR-DENTS?\n\n- What is the value of DENTS over BTS, or vice versa? Are their high-level rules for when one should be preferred over the other?\n\nMinor comments:\n- There seems to be some inconsistency in notation in equations 11 and 19 vs. the text surrounding them -- $N(s)$ and $N(s, a)$ are used in the equations, but the text uses $m_s$ and $m_a$.\n\nPost-Rebuttal Response:\n\nThe author's have addressed my questions, and provided additional experiments showing how their proposed methods compare favorably against existing baselines. I continue to recommend acceptance.", "limitations": "One benefit of computing the max entropy policy, as MENTS does, is that it might help with exploration when *acting* (not just planning) --- this is perhaps helpful when the agent doesn't have an accurate model of the world, and needs to learn it over time. Adding some discussion on this point would be good, since it seems like a potential limitation of \n\nApart from that, the authors have addressed the limitation of BTS and DENTS that the require $O(|\\mathcal{A}|)$ backups relative to UCT, which may hinder performance when actions spaces are large.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper clearly explains an existing problem with MENTS not converging to the optimal root-node policy with increasing trials  (e.g. using the D-chain problem to illustrate the point).\n- The \"fix\" that this paper proposes to MENTS is intuitive and clearly explained.\n- The theoretical results appear to be sound, with extensive proofs (though I did not check these carefully).\n- The empirical results demonstrate that BTS & DENTS can improve upon baseline search policies like UCT and MENTS in non-trivial problems (i.e. Go), while generally performing no worse than the baselines on simpler problems.", "weaknesses": "- The motivation for increasing exploration during planning/search could be better explained.\n  - In particular, I think the authors could better highlight that UCT was justified in the context of selecting actions in the real-world, and that per Tolpin & Shimony et al [1, 2], using UCT in *simulation* doesn't make as much sense, since computational actions are less costly than actual actions.\n  - This better motivates the use of a Boltzmann search policy, since exploring more when \"thinking\" could ultimately lead to better exploitation when finally acting / executing.\n  - Similarly, the authors could better explain their choice of using simple regret (instead of cumulative regret) as the metric for an MCTS algorithm, following the discussion / reasoning in [1, 2]. Cumulative regret doesn't matter if the cost of computation is effectively zero (and only matters slightly if computation cost is much smaller the actual cost of acting).\n\n- I don't think this should count very much against the paper, given the extensive effort at formally proving the stated results (which I think is valuable, and should be recognized), but it's arguably the case that BTS are DENTS are fairly incremental and straightforward extensions of MENTS.\n\n[1] David Tolpin and Solomon Shimony. Mcts based on simple regret. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pages 570–576, 2012.\n\n[2] Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony. Selecting computations: Theory and applications. arXiv preprint arXiv:1408.2048, 2014.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review and providing us with helpful comments.\n\n> The motivation for increasing exploration during planning/search could be better explained.\n\nThank you for the suggestions on clarifying the motivations for using simple regret and increasing exploration. We will make sure to update the paper with language similar to the explanation we gave to reviewer nux6 with the help of your review.\n\n> Why does the search temperature $\\alpha$ in DENTS differ from the entropy weighting term $\\beta$? By default (e.g. in MENTS) this should be the same -- is there a reason why it makes sense have them vary separately? Why not decay $\\alpha$ with increasing node visits as well?\n\nIn DENTS we separated the $\\alpha$ and $\\beta$ parameters so that the temperature of the Boltzmann search policy can be separated from the weighting of the entropy objective. Firstly, we want to decay the value of $\\beta$ to avoid the parameter sensitivity problems that MENTS suffers from in the modified D-chain and Frozen Lake environments. Specifically, if $\\beta$ is not decayed, then we risk prioritising entropy more in the search policy than the standard objective (as can be seen in Figure 26 in the appendix). In contrast, having $\\alpha > 0$ is a necessary condition for the exponential simple regret bound so that all actions are always explored with some minimum probability. We could let $\\alpha\\rightarrow 0$ in DENTS and it would be *consistent* (as per the definition in lines 153/154 of the paper), but it would not achieve a similar simple-regret bound to BTS. We could have alternatively allowed $\\alpha\\rightarrow\\alpha_{\\min}$, but we decided to keep $\\alpha$ fixed for a cleaner presentation.\n\n> In the AR version of DENTS used for the Go experiments, both $\\alpha$ and $\\beta$ are decayed. AR-MENTS is then described as a variant of AR-DENTS, where $\\alpha$ is set equal to $\\beta$. But in AR-MENTS, are $\\alpha$ and $\\beta$ set to a fixed value, or decayed with increasing node visits? I'm assuming it's the former, in which case that should be clarified in the Appendix, but if it's the latter, how is AR-MENTS different from AR-DENTS?\n\nYou are correct in assuming the former. For AR-MENTS, $\\beta(m)=\\alpha(m)=\\alpha_{fix}$ for some fixed value $\\alpha_{fix}$. We will clarify.\n\n> What is the value of DENTS over BTS, or vice versa? Are their high-level rules for when one should be preferred over the other?\n\nBTS will outperform DENTS when the reward signal is more dense and tailored to drive exploration since doesn’t have the additional computational overhead of the entropy backup. Note that in complex environments this often requires reward engineering where specifying an appropriate reward is a difficult task in of itself versus using entropy for exploration.\n\n(Repeated from response to reviewer yYGy) \nDENTS will outperform BTS when entropy is a useful exploration bonus, such as in cases where rewards are sparse and Frozen Lake is a good example of this. In Frozen Lake states that correspond to falling down a hole have an entropy of 0, and so the entropy bonus encourages DENTS (and other entropy algorithms) to explore paths that don’t fall into the holes. This benefit can be seen in Figure 3a, where BTS is slower to converge than DENTS and MENTS.\n\n> One benefit of computing the max entropy policy, as MENTS does, is that it might help with exploration when acting (not just planning) --- this is perhaps helpful when the agent doesn't have an accurate model of the world, and needs to learn it over time. Adding some discussion on this point would be good, since it seems like a potential limitation of\n\nThank you for pointing this out, we will make sure to add this as an additional limitation. Our algorithms may not be useful when converging to the maximum entropy policy is desirable. As you mention, exploration while acting will be useful when the agent does not have an accurate model of the world and still needs to learn it, and MENTS would be more appropriate in these scenarios."}]

Author rebuttal:
We have attached a pdf with updated results following comments from the reviewers. 

In Figure 1 of the attached pdf we have updated results for DENTS running under the $\beta(m)=\alpha$ configuration in both the D-chain and Frozen Lake environments. These show empirically that DENTS can still match the performance of MENTS when MENTS is properly tuned. 

We have run experiments to test the best number of threads to use in Go for PUCT and BTS (and other algorithms using Boltzmann policies), which can be found in Table 1. We tried using {16, 32, 64, 128} threads, and these results suggest that 32 threads were optimal for PUCT and that 128 was best out of the values tried for BTS. 

Originally we tried temperature parameters from {1000, 500, 100, 50, 10} for all algorithms using Boltzmann policies (noting that rewards were scaled to be in the range [-100,100]). For MENTS and TENTS the best-performing temperature was 10, suggesting that the optimal temperature may be lower. Table 2 gives results from the updated tuning of the MENTS and TENTS temperatures, with the best-performing temperatures being 0.5 and 10 respectively. Note that the TENTS temperature remains unchanged at a value of 10, which beats all higher temperatures tried (Table 9 in paper appendix) and all lower temperatures (Table 2 in attached pdf).

In Table 3 we give updated results for MENTS and PUCT for the 9x9 Go round-robin. These matches were run giving all algorithms 32 threads and used the updated temperature of 0.5 for MENTS. The additional tuning of MENTS led it to win a few more games but ultimately the closest it came to winning a match was its 31-69 loss to TENTS. Similarly, the results for PUCT did not significantly change, BTS and DENTS won by a larger margin in these reruns but PUCT did draw with RENTS this time round.

In Table 4 of the attached pdf we give results on 19x19 Go (using the standard komi of 7.5 for 19x19 Go), which used the same parameters selected on 9x9 Go, and each agent was still given 15s to make a move. The only agent that was able to beat PUCT was BTS with a match score of 57-43. In 19x19 Go, PUCT was able to run a similar number of trials per move as BTS (\~5000), in contrast to the results in 9x9 Go from Table 1 of the paper where PUCT (\~13000) could not run as many trials as BTS (\~17000). Note that BTS is often able to run more trials because the emphasis on exploration leads to less contention between threads. Also note that these results were run prior to the rebuttal period, so do not reflect any of the changes described above. However, because the updated results in Table 3 of the attached pdf are not significantly different to the results from Table 1 of the paper, we don’t expect these results to significantly change when we re-run them with updated parameters.

Finally, since the submission, we have realised that the Alias method [1,2] for sampling from categorical can be used to significantly optimise action selection in all the algorithms we considered apart from PUCT. This improvement is an asymptotic improvement in complexity and we will add a complexity analysis in the appendix of the updated paper. In Table 5 in the attached pdf we give results on 19x19 Go using this optimisation, where a significant difference between the number of trials each algorithm was able to run can be seen between Tables 4 and 5. Again, because the updated results in Table 3 gave no substantial changes, we don’t expect any significant changes in these results either.

[1] Walker, Alastair J. "New fast method for generating discrete random numbers with arbitrary frequency distributions." Electronics Letters 8.10 (1974): 127-128.

[2] Vose, Michael D. "A linear algorithm for generating random numbers with a given distribution." IEEE Transactions on software engineering 17.9 (1991): 972-975.


Meta-review: The paper presents new Monte Carlo tree search variants based on using Boltzmann exploration. The paper not only proves several results about bounds for simple regret, it also shows several experiments on hard cases identified in the literature, standard benchmarks used in the literature (Sailing domain) and on 9x9 Go using the expert policy and value function from KataGo. Several reviewers had some criticisms including the motivations behind simple regret and questions about missing comparisons to baselines or mentions of previous work. The authors responded very well with several new experiments and clarifications. The discussions substantially affected the quality of the work and opinions of the reviewers. I agree with all of the reviewers' that much of the new content (and clarifications made in the discussion) should be incorporated in the camera-ready version of the paper, in the appendix if it does not fit in the main paper. Overall, this paper makes several significant novel contributions to the community.
Decision: Accept (poster)