appReferences

# Monte Carlo Tree Search with Boltzmann Exploration

Michael Painter, Mohamed Baioumy, Nick Hawes, Bruno Lacerda
Oxford Robotics Institute
University of Oxford
{mpainter, mohamed, nickh<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

Planning under uncertainty is a core problem in Artificial Intelligence,
commonly modelled as a Markov Decision Process (MDP) or variant thereof. MDPs
can be solved using dynamic programming techniques to obtain an optimal policy
bellman1957markovian . However, computing a full optimal policy does not scale
to large state-spaces, necessitating the use of heuristic solvers
hansen2001lao ; bonet2003labeled and online, sampling-based, planners based on
Monte-Carlo Tree-Search (MCTS), such as the Upper Confidence Bound applied to
Trees (UCT) algorithm kocsis2006uct .

The UCT search policy is 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 it getting stuck in
local optima. Conversely, Maximum ENtropy Tree Search (MENTS) places a greater
emphasis on exploration by combining MCTS with techniques from maximum entropy
policy optimisation ziebart2008maximum ; haarnoja2017reinforcement ;
haarnoja2018soft . MENTS jointly maximises cumulative rewards and policy
entropy, where a temperature parameter controls the weight of the entropy
objective. However, MENTS is sensitive to this temperature parameter, and may
not converge to the reward maximising policy or require a prohibitively low
temperature to do so.

In this work, we consider scenarios where MCTS methods are used with a
simulator to 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 uses a Boltzmann search policy like MENTS, 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. it converges to the reward maximising policy in the limit).

The main contributions of this paper are: (1) Demonstrating that the maximum
entropy objective used in MENTS can be misaligned with reward maximisation,
thus preventing it from converging to the optimal policy; (2) Introducing two
new algorithms, BTS and DENTS, which preserve the benefits of using Boltzmann
search policies while being as simple to implement as UCT and MENTS, but
converge to the reward maximising policy; (3) Analysing MENTS, BTS and DENTS
through the lens of simple regret to provide theoretical convergence results;
(4) Highlighting and demonstrating that the Alias method alias1 ; alias2 can
be used with stochastic action selection to improve the asymptotic 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

We define a (finite-horizon) MDP as a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},p,R,H)$, where $\mathcal{S}$ is the set
of states; $\mathcal{A}$ is the set of actions;
$p:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the
transition function where $p(s^{\prime}|s,a,)$ is the probability of moving to
state $s^{\prime}$ given that action $a$ was taken in state $s$;
$R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward function;
and $H\in\mathbb{N}$ is the finite horizon. Let $\textnormal{Succ}(s,a)$
denote the set of successor states of $(s,a)$, i.e.
$\textnormal{Succ}(s,a)=\\{s^{\prime}\in\mathcal{S}\mid
p(s^{\prime}|s,a)>0\\}$.

A policy $\pi$ maps a state and timestep to a distribution over actions, and
we denote the probability of executing $a$ at state $s$ and timestep $t$ as
$\pi(a|s,t)$. Let $s_{t}$ denote the state after $t$ time-steps and $a_{t}$
the action selected at $s_{t}$, according to $\pi$. The expected value
$V^{\pi}$ and expected state-action value $Q^{\pi}$ of $\pi$ are defined as:

$\displaystyle V^{\pi}(s,t)$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{i=t}^{H}R\left(s_{i},a_{i}\right)\Big{|}s_{t}=s\right],$
(1) $\displaystyle Q^{\pi}(s,a,t)$
$\displaystyle=R(s,a)+\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}[V^{\pi}(s^{\prime},t+1)].$ (2)

The goal is to find the optimal policy $\pi^{*}$ with the maximum expected
reward: $\pi^{*}=\operatorname*{arg\,max}_{\pi}V^{\pi}$. The optimal value
functions are then defined as $V^{*}=V^{\pi^{*}},Q^{*}=Q^{\pi^{*}}$. For an
MDP, there always exists an optimal policy $\pi^{*}$ which is deterministic
kolobov2012planning .

###  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 entropy of the policy haarnoja2017reinforcement
; ziebart2008maximum . Formally, this is expressed as:

$\displaystyle
V^{\pi}_{\textnormal{sft}}(s,t)=\mathbb{E}_{\pi}\left[\sum_{i=t}^{H}R\left(s_{i},a_{i}\right)+\alpha\mathcal{H}\left(\pi\left(\cdot|s_{i},i\right)\right)\Big{|}s_{t}=s\right],$
(3)

where $\alpha\geq 0$ is a temperature parameter, and $\mathcal{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 $\alpha=0$.

An optimal value function for maximum entropy optimization is obtained using
the soft Bellman optimality equations haarnoja2018soft :

$\displaystyle
Q^{*}_{\textnormal{sft}}(s,a,t)=R(s,a)+\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}\left[V^{*}_{\textnormal{sft}}(s^{\prime},t)\right],$ (4)
$\displaystyle
V^{*}_{\textnormal{sft}}(s,t)=\alpha\log\sum_{a\in\mathcal{A}}\exp(Q^{*}_{\textnormal{sft}}(s,a,t)/\alpha),$
(5)

which corresponds to a standard Bellman backup, with the $\max$ replaced by a
softmax, shown in Equation (5). The optimal soft policy
$\pi^{*}_{\textnormal{sft}}=\operatorname*{arg\,max}_{\pi}V_{\text{sft}}^{\pi}$
can be computed directly nachum2017bridging as follows:

$\displaystyle\pi^{*}_{\textnormal{sft}}(a|s,t)=\exp((Q^{*}_{\textnormal{sft}}(s,a,t)-V^{*}_{\textnormal{sft}}(s,t))/\alpha).$
(6)

Note that the soft policy is always stochastic for any $\alpha>0$. Henceforth,
we will use soft value to refer to value functions indexed with ‘sft’,
(optimal) soft policy to refer to policies of the form given in Equation (6),
and standard value and (optimal) standard policy for values and policies of
the form given in Section 2.1, unless it is clear from the context.

For the remainder of this paper we will drop the timestep $t$ from policies
and value functions to simplify notation.

###  2.3 Monte-Carlo tree search

MCTS methods build a search tree $\mathcal{T}$ using Monte-Carlo 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 in $\mathcal{T}$ is reached. A new node
is added to $\mathcal{T}$ and its value is initialised using some function
$V^{\text{init}}$, often using a rollout policy to select actions until the
time horizon $H$ is reached. In the second phase, the return for the trial is
back-propagated up (or ‘backed up’) the tree to update the values of nodes in
$\mathcal{T}$. For a reader unfamiliar with MCTS, we refer to browne2012survey
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 to 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 in 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, so we may represent nodes using states. Our algorithms and
results do not make use of this assumption, and generalise to when this
assumption does not hold.

##### UCT

UCT kocsis2006uct applies the upper confidence bound (UCB) in its search
policy to balance exploration and exploitation. The $n$th trial of UCT
operates as follows: let $\mathcal{T}$ be the current search tree and let
$\tau=(s_{0},a_{0},...,a_{h-1},s_{h})$ denote the trajectory of the $n$th
trial, where $s_{h}\not\in\mathcal{T}$ or $h=H$. At each node $s_{t}$ the UCT
search policy $\pi_{\text{UCT}}$ will select a random action that has not
previously been selected, otherwise, it will select the action with maximum
UCB value:

$\displaystyle\pi_{\textnormal{UCT}}(s)$
$\displaystyle=\max_{a\in\mathcal{A}}\bar{Q}(s,a)+c\sqrt{\frac{\log
N(s)}{N(s,a)}},$ (7)

where, $\bar{Q}(s,a)$ is the current empirical Q-value estimate, $N(s)$ (and
$N(s,a)$) is how many times $s$ has been visited (and action $a$ selected) and
$c$ is an exploration parameter. Then, $s_{h}$ is added to the tree:
$\mathcal{T}\leftarrow\\{s_{h}\\}\cup\mathcal{T}$. The backup consists of
updating empirical estimates for $t=h-1,...,0$:

$\displaystyle\bar{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\bar{Q}(s_{t},a_{t})+\frac{\bar{R}(t)-\bar{Q}(s_{t},a_{t})}{N(s_{t},a_{t})+1},$
(8)

where $\bar{R}(t)=V^{\text{init}}(s_{h})+\sum_{i=t}^{h-1}R(s_{i},a_{i})$, and
$V^{\text{init}}(s_{h})=\sum_{i=h}^{H}R(s_{i},a_{i})$ if using a rollout
policy.

##### MENTS

MENTS xiao2019maximum combines maximum entropy policy optimization
haarnoja2017reinforcement ; ziebart2008maximum with MCTS. Algorithmically, it
is similar to UCT. The two differences are: (1) the search policy follows a
stochastic Boltzmann policy, and (2) it uses soft values that are updated with
dynamic programming backups. The MENTS search policy
$\pi_{\textnormal{MENTS}}$ is given by:

$\displaystyle\pi_{\textnormal{MENTS}}(a|s)$
$\displaystyle=(1-\lambda_{s})\rho_{\textnormal{MENTS}}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$
(9) $\displaystyle\rho_{\textnormal{MENTS}}(a|s)$
$\displaystyle=\exp\left(\frac{1}{\alpha}\left(\hat{Q}_{\textnormal{sft}}(s,a)-\hat{V}_{\textnormal{sft}}(s)\right)\right)$
(10)

where $\lambda_{s}=\min(1,\epsilon/\log(e+N(s))),$ $\epsilon\in(0,\infty)$ is
an exploration parameter and $\hat{V}_{\textnormal{sft}}(s)$ (and
$\hat{Q}_{\textnormal{sft}}(s,a)$) are the current soft (Q-)value estimates.
The soft value of the new node is initialised
$\hat{V}_{\textnormal{sft}}(s_{h})\leftarrow V^{\text{init}}(s_{h})$ and the
soft values are updated with backups for $t=h-1,...,0$:

$\displaystyle\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})$
$\displaystyle\leftarrow
R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s,a)}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}_{\textnormal{sft}}(s^{\prime})\right),$
(11) $\displaystyle\hat{V}_{\textnormal{sft}}(s_{t})$
$\displaystyle\leftarrow\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\hat{Q}_{\textnormal{sft}}(s_{t},a)\right).$
(12)

Each $\hat{Q}_{\textnormal{sft}}(s,a)$ is initialised using another function
$Q^{\text{init}}_{\text{sft}}(s,a)$ (but is typically zero).

###  2.4 Simple regret

UCB auer2002finite is 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
simple_regret_short ; simple_regret_long is more appropriate for analysing the
performance 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.

We consider the problem of MDP planning as a sequential decision problem,
where for each round $n$:

  1. 1.

the forecaster algorithm produces a search policy $\pi^{n}$ and samples a
trajectory $\tau\sim\pi^{n}$,

  2. 2.

the environment returns the rewards $R(s_{t},a_{t})$ for each $s_{t},a_{t}$
pair in $\tau$,

  3. 3.

the forecaster algorithm produces a recommendation policy $\psi^{n}$,

  4. 4.

if environment sends stop signal, then end, else return to step 1.

The simple regret of the forecaster on it’s $n$th round is then:

$\displaystyle\textnormal{reg}(s,\psi^{n})=V^{*}(s)-V^{\psi^{n}}(s).$ (13)

In MENTS the recommendation policy suggested in xiao2019maximum can be
written:

$\displaystyle\psi_{\text{MENTS}}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{Q}_{\textnormal{sft}}(s,a).$
(14)

We can now formally define consistency: an algorithm is consistent if and only
if its recommendation policy $\psi^{n}$ converges to an expected simple regret
of zero: $\mathbb{E}[\textnormal{reg}(s,\psi^{n})]\rightarrow 0$ as
$n\rightarrow\infty$. 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 it
implies it is an optimal policy.

##  3 Limitations of prior MCTS methods

In this section we use the D-chain problem introduced in coquelin2007_uct
(Figure 1) to highlight the limitations of UCT and MENTS. In the D-chain
problem, when an agent chooses action $a_{L}$, from some state $d$, it moves
to an absorbing state and receives a reward of $(D-d)/D$. In state $D$, action
$a_{R}$ corresponds to an absorbing state with reward $R_{f}=1$. The optimal
standard policy always selects action $a_{R}$.

Figure 1: An illustration of the (modified) D-chain problem, where 1 is the
starting state, transitions are deterministic and values next to states
represent rewards for arriving in that state.

In the 10-chain problem ($D=10$), UCT will recommend action $a_{L}$ from state
$1$ (Figure 2(a)). UCT requires $\Omega(\exp(...\exp(1)...))$ many trials ($D$
composed exponential functions) to recommend the optimal policy that reaches
the reward of $R_{f}=1$ coquelin2007_uct . This highlights the first
limitation mentioned in Section 1: UCT quickly disregards action $a_{R}$ 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_{f}=1$ (Figure 2(a)). However,
consider the modified 10-chain with $R_{f}=1/2$ instead. Repeated applications
of Equations (4) and (5) for $\alpha=1$ gives the optimal soft values of
$Q^{*}_{\textnormal{sft}}(1,a_{R})=\log(\exp(1/2)+\sum_{i=0}^{8}\exp(i/10))\approx
2.74$ and $Q^{*}_{\textnormal{sft}}(1,a_{L})=0.9$. So in the modified 10-chain
problem, we have
$Q^{*}_{\textnormal{sft}}(1,a_{R})>Q^{*}_{\textnormal{sft}}(1,a_{L})$ with
$\alpha=1$, whereas $Q^{*}(1,a_{R})<Q^{*}(1,a_{L})$. Thus, when MENTS
converges, it will recommend the wrong action with respect to the standard
objective (Figure 2(b)), i.e. it is not consistent. The modified 10-chain is
an 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 $\mathcal{M}$ and temperature $\alpha$ such that
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{MENTS}})]\not\to 0$
as $n\to\infty$. That is, MENTS is not consistent.

###### Proof.

Proof is by example with $\alpha=1$ in the modified 10-chain (Figure 1). ∎

We can reduce the value of $\alpha$ to decrease the importance of entropy in
the soft objective
$\mathbb{E}\left[R\left(s_{t},a_{t}\right)+\alpha\mathcal{H}\left(\pi\left(\cdot|s_{t}\right)\right)\right]$.
If $\alpha$ is small enough, then MENTS recommendations can converge to the
optimal standard policy (Theorem 3.2). Hence, MENTS with a low temperature can
solve the modified 10-chain problem (Figure 2(b)). However, in practice, a low
temperature will often cause MENTS to not sufficiently explore, as
demonstrated in the original D-chain (Figure 2(a)).

######  Theorem 3.2.

For any MDP $\mathcal{M}$, after running $n$ trials of the MENTS algorithm
with $\alpha\leq\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|$, there exists
constants $C,k>0$ such that:
$\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{MENTS}})]\leq
C\exp(-kn)$, where
$\Delta_{\mathcal{M}}=\min\\{Q^{*}(s,a)-Q^{*}(s,a^{\prime})|Q^{*}(s,a)\neq
Q^{*}(s,a^{\prime}),s\in\mathcal{S},a,a^{\prime}\in\mathcal{A},t\in\mathbb{N}\\}$.

###### Proof outline.

We can show
$\hat{Q}_{\textnormal{sft}}(s,a)\overset{p}{\to}Q^{*}_{\textnormal{sft}}(s,a)$
(Corollary E.12.1) similarly to Thoerem 4.2. The bound on $\alpha$ is required
to ensure that $\pi^{*}(s_{0})=\pi^{*}_{\textnormal{sft}}(s_{0})$. ∎

In conclusion, similar MDPs can require vastly different temperatures for
MENTS to be 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 27 in the appendix.

(a) 10-chain.

(b) Modified 10-chain.

Figure 2: A comparison of MENTS, DENTS and UCT when run on the (modified)
10-chain.

##  4 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 to parameter selection that MENTS does. Both algorithms use 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 implies that this is not always the case
for MENTS).

###  4.1 Boltzmann Tree Search

Our first approach, 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 $\pi_{\textnormal{BTS}}$ and backups for the $n$th trial are
given by:

$\displaystyle\pi_{\textnormal{BTS}}(a|s)$
$\displaystyle=(1-\lambda_{s})\rho_{\textnormal{BTS}}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$
(15) $\displaystyle\rho_{\textnormal{BTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{1}{\alpha}\left(\hat{Q}(s,a)\right)\right),$
(16) $\displaystyle\hat{Q}(s_{t},a_{t})$ $\displaystyle\leftarrow
R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}(s^{\prime})\right),$
(17) $\displaystyle\hat{V}(s_{t})$
$\displaystyle\leftarrow\max_{a\in\mathcal{A}}\hat{Q}(s_{t},a),$ (18)

for $t=h-1,...,0$, where $\hat{V}$ and $\hat{Q}$ are the current Bellman
(Q-)value estimates, $\lambda_{s}=\min(1,\epsilon/\log(e+N(s)))$,
$\epsilon\in(0,\infty)$ is an exploration parameter and $\alpha$ is a search
temperature (unrelated to entropy). Each $\hat{V}(s)$ and $\hat{Q}(s,a)$ are
initialised using $V^{\text{init}}$ and $Q^{\text{init}}$ functions similarly
to MENTS. The Bellman values are used for recommendations:

$\displaystyle\psi_{\text{BTS}}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{Q}(s,a).$
(19)

By using Bellman backups, we can guarantee that the BTS recommendation policy
converges to the optimal standard policy for any temperature $\alpha$, given
enough time. In other words, BTS is consistent.

######  Theorem 4.1.

For any MDP $\mathcal{M}$, after running $n$ trials of the BTS algorithm with
a root node of $s_{0}$, there exists constants $C,k>0$ such that for all
$\varepsilon>0$ we have
$\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{BTS}})]\leq C\exp(-kn)$,
and also $\hat{V}(s_{0})\overset{p}{\to}V^{*}(s_{0})$ as $n\rightarrow\infty$.

###### Proof outline.

This result is a special case of Theorem 4.2 by setting $\beta(m)=0$. ∎

###  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 (17) and (18), but adds an
entropy backup. The entropy values are weighted by a bounded non-negative
function $\beta(N(s))$ in the DENTS search policy $\pi_{\textnormal{DENTS}}$:

$\displaystyle\pi_{\textnormal{DENTS}}(a|s)$
$\displaystyle=(1-\lambda_{s})\rho_{\textnormal{DENTS}}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$
(20) $\displaystyle\rho_{\textnormal{DENTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{1}{\alpha}\left(\hat{Q}(s,a)+\beta(N(s))\mathcal{H}_{Q}(s,a)\right)\right),$
(21) $\displaystyle\mathcal{H}_{V}(s_{t})$
$\displaystyle\leftarrow\mathcal{H}(\pi_{\textnormal{DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi_{\textnormal{DENTS}}(a|s_{t})\mathcal{H}_{Q}(s_{t},a),$
(22) $\displaystyle\mathcal{H}_{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\frac{N(s^{\prime})}{N(s_{t},a_{t})}\mathcal{H}_{V}(s^{\prime}),$
(23)

for $t=h-1,...,0$, where $\mathcal{H}_{V}(s)$ and $\mathcal{H}_{Q}(s,a)$ are
the entropy values of the search policy rooted at $s$ and $(s,a)$
respectively, and $\alpha,\lambda_{s}$ 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
$\hat{Q}(s,a)+\beta(N(s))\mathcal{H}_{Q}(s,a)$ as a soft value for $(s,a)$.
Hence, by setting $\beta(m)=\alpha$, the DENTS search will mimic the MENTS
search (demonstrated in Appendix D.4), and if $\beta(m)=0$ then the algorithm
reduces to the BTS algorithm. By using a decaying function for $\beta$ we
amplify values using entropy as an exploration bonus early in the search while
allowing for more exploitation later. Recommendations still use Bellman
values:

$\displaystyle\psi_{\text{DENTS}}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{Q}(s,a).$
(24)

Because the recommendation policy $\psi_{\text{DENTS}}$ uses the Bellman
values, we can guarantee that it will converge to the optimal standard policy,
and is consistent for any $\beta$.

######  Theorem 4.2.

For any MDP $\mathcal{M}$, after running $n$ trials of the DENTS algorithm
with a root node of $s_{0}$, if $\beta$ is a bounded function, then there
exists constants $C,k>0$ such that for all $\varepsilon>0$ we have
$\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{DENTS}})]\leq
C\exp(-kn)$, and also $\hat{V}(s_{0})\overset{p}{\to}V^{*}(s_{0})$ as
$n\rightarrow\infty$.

###### Proof outline.

Let $0<\eta<\pi_{\text{DENTS}}(a|s)$ for all $s,a$, which exists because
$\exp(\cdot)>0$ and $1/|\mathcal{A}|>0$ in Equation 20 (Lemma E.1), which can
be used with Hoeffding bounds to show for appropriate constants and any event
$E$ that $\\{\Pr(E)\leq C_{0}\exp(-k_{0}\varepsilon^{2}N(s_{t}))\\}$ iff
$\\{\Pr(E)\leq C_{1}\exp(-k_{1}\varepsilon^{2}N(s_{t},a_{t}))\\}$ iff
$\\{\Pr(E)\leq C_{2}\exp(-k_{2}\varepsilon^{2}N(s_{t+1}))\\}$. We can then
show
$\Pr(|\hat{Q}(s_{0},a)-Q^{*}(s_{0},a)|>\varepsilon)<C_{3}\exp\left(-k_{3}\varepsilon^{2}n\right)$
by induction, where the base case $\hat{V}(s_{H+1})=V^{*}(s_{H+1})=0$ holds
vacuously (Lemmas E.10, E.16 and Theorem E.17). Let $\Delta_{\mathcal{M}}$ be
a small constant (Equation (122)) such that $\forall
s,a.|\hat{Q}(s_{0},a)-Q^{*}(s_{0},a)|\leq\Delta_{\mathcal{M}}/2\implies\operatorname*{arg\,max}_{a}\hat{Q}(s,a)=\operatorname*{arg\,max}_{a}Q^{*}(s,a)$.
Setting $\varepsilon=\Delta_{\mathcal{M}}/2$ gives a bound on
$\Pr(\psi_{\text{DENTS}}\neq\pi^{*})$, which can then be used in the
definition of simple regret to give the result. ∎

###  4.3 Using the Alias method

The Alias method alias1 ; alias2 can be used to sample from a categorical
distribution with $m$ categories in $O(1)$ time, with a preprocessing step of
$O(m)$ time. Given any stochastic search policy, we can sample actions in
amortised $O(1)$ time, by computing an alias table every $|\mathcal{A}|$
visits to a node, and then sampling from that table. Note that when using the
Alias method we are making a trade off between using the most up to date
policy and the speed of sampling actions.

In Appendix C.1 we 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(|\mathcal{A}|)+|\mathcal{A}|))$ time when using the Alias
method, as opposed to the typical complexity of $O(nH|\mathcal{A}|)$.

###  4.4 Limitations and benefits

The main limitations of BTS and DENTS are as follows: (1) the DENTS decay
function $\beta$ 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 a 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) to 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 a
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 rents_your_tents , which use
relative and Tsalis entropy in place of Shannon entropy respectively, and the
H-MCTS algorithm karnin2013almost which combines UCT and Sequential Halving.

###  5.1 Gridworlds

To evaluate an algorithm with search tree $\mathcal{T}$, we complete the
partial recommendation policy $\psi_{\text{alg}}$ as follows:

$\displaystyle\psi(a|s)=\begin{cases}1&\text{ if }s\in\mathcal{T}\text{ and
}a=\psi_{\text{alg}}(s),\\\ 0&\text{ if }s\in\mathcal{T}\text{ and
}a\neq\psi_{\text{alg}}(s),\\\ \frac{1}{|\mathcal{A}|}&\text{
otherwise.}\end{cases}$ (25)

We sample a number of trajectories from $\psi$, and take the average return to
estimate $V^{\psi}$. Although we are evaluating the algorithms in an offline
planning setting, it 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
brockman2016openai , and the Sailing Problem peret2004line , commonly used to
evaluate tree search algorithms peret2004line ; kocsis2006uct ;
mcts_simple_regret ; brue1 . We chose these environments to compare our
algorithms in a domain with a sparse and dense reward respectively.

The _(Deterministic) Frozen Lake_ is a grid world environment with one goal
state. The agent can move in any cardinal direction at each time step, and
walking into a wall leaves the agent in the same location. Trap states exist
where the agent falls into a hole and the trial ends. If the agent arrives at
the goal state after $t$ timesteps, then a reward of $0.99^{t}$ is received.

The _Sailing Problem_ is 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 to travel each of 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 cost of
each action depends on the tack, the angle between the direction of the
agent’s travel and the wind.

####  5.1.2 Results

We used an 8x12 Frozen Lake environment and a 6x6 Sailing Problem for
evaluation, more environment details are given in Appendix D.1. Parameters
were selected using a 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 3(a)), entropy proved to be a 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 to 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 3(b)) UCT performs well due to 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 to pick the same actions over time, so it tends to pick a
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.

(a) 8x12 Frozen Lake.

(b) 6x6 Sailing Problem.

Figure 3: Results for gridworld environments. Further results are given in
Appendix D.3.

###  5.2 Go

For a more challenging domain we ran a round-robin tournament using the game
of Go, which has widely motivated the development of MCTS methods
gelly2007combining ; silver2016mastering ; silver2017mastering . 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 $\tilde{V}$ and policy network $\tilde{\pi}$ from
KataGo katago . Our baseline was the PUCT algorithm poly_uct2 , as described
in Alpha Go Zero silver2017mastering using prioritised UCB prioritised_ucb 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 is
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 (8)) outperformed using Bellman backups for Go (Appendix
D.5.1). 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 $\hat{Q}(s,a)\leftarrow\log\tilde{\pi}(a|s)+B$ and
$\hat{V}(s)\leftarrow\tilde{V}(s)$, where $B$ is a constant (adapted from Xiao
et al. xiao2019maximum ). With such an initialisation, the initial BTS policy
is $\rho_{\textnormal{BTS}}(a|s)\propto\tilde{\pi}(a|s)^{1/\alpha}$. For these
experiments we set a value of
$B=\frac{-1}{|\mathcal{A}|}\sum_{a\in\mathcal{A}}\log\tilde{\pi}(a|s)$.
Additionally, the stochastic search policy naturally lends itself to mixing in
a prior policy, so we can replace BTS search policy $\pi_{\textnormal{BTS}}$
(Equation (15)) with $\pi_{\textnormal{BTS,mix}}$:

$\displaystyle\pi_{\textnormal{BTS,mix}}(a|s)$
$\displaystyle=\lambda_{\tilde{\pi}}\tilde{\pi}(a|s)+(1-\lambda_{\tilde{\pi}})\pi_{\textnormal{BTS}}(a|s)$
(26)
$\displaystyle=\lambda_{\tilde{\pi}}\tilde{\pi}(a|s)+(1-\lambda_{\tilde{\pi}})(1-\lambda_{s})\rho_{\textnormal{BTS}}(a|s)+\frac{(1-\lambda_{\tilde{\pi}})\lambda_{s}}{|\mathcal{A}|},$
(27)

where $\lambda_{\tilde{\pi}}=\min(1,\epsilon_{\tilde{\pi}}/\log(e+N(s)))$, and
$\epsilon_{\tilde{\pi}}\in(0,\infty)$ controls the weighting for the prior
policy.

####  5.2.2 Results

Results of the round-robin are summarised in Table 1, and we discuss how
parameters were selected in Appendix D.5.1. BTS was able to 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 C.1 which allowed the
Boltzmann search algorithms to run significantly more trials per move than
PUCT. BTS and 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 $\tilde{V}$ and $\tilde{\pi}$. 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 a heuristic for
Go that the RAVE rave algorithm used: the value of a move is typically
unaffected by other moves on the board.

To validate the strength of our PUCT agent, we also compared it directly with
KataGo katago , 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 a 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.

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, we abbreviate the algorithm
names for space.

##  6 Related work

UCT kocsis2006uct ; kocsis2006improved is a widely used variant of MCTS.
Polynomial UCT poly_uct2 , replaces the logarithmic term in UCB with a
polynomial one (such as a square root), which has been further popularised by
its use in Alpha Go and Alpha Zero silver2016mastering ; silver2017mastering ;
silver2018general . Coquelin and Munos introduce the Flat-UCB and BAST
algorithms to adapt UCT for the D-chain problem coquelin2007_uct . However, we
consider an alternative approach for search in MCTS rather than adapting UCB.

Maximum entropy policy optimization methods are well-known in the
reinforcement learning literature haarnoja2017reinforcement ; haarnoja2018soft
; ziebart2008maximum . MENTS xiao2019maximum is the first method to combine
the principle of maximum entropy and MCTS. Kozakowski et al. ants extend MENTS
to arrive at Adaptive Entropy Tree Search (ANTS), adapting parameters
throughout the search to match a prescribed entropy value. Dam et al.
rents_your_tents also extend MENTS using Relative and Tsallis entropy to
arrive at the RENTS and TENTS algorithms. Our work is closely related to
MENTS, however, we focus on reward maximisation and consider how entropy can
be used in MCTS without altering our planning objective.

Bubeck et al. simple_regret_short ; simple_regret_long 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 a uniform exploration produces an exponential bound on the simple
regret of recommendations. We use simple regret, but in the context of
sequential decision-making, to analyse the convergence of MCTS algorithms.

Tolpin and Shimony mcts_simple_regret extend simple regret to MDP settings,
showing an $O(\exp(-\sqrt{n}))$ bound on simple regret after $n$ trials by
adapting UCT. The subsequent work of Hay et al. hay2014selecting extends
mcts_simple_regret to consider a metalevel decision problem, incorporating
computation costs into the objective. Pepels et al. mcts_simple_regret_two
introduce a Hybrid MCTS (H-MCTS) motivated by the notion of simple regret.
H-MCTS uses a mixture of Sequential Halving karnin2013almost , and UCT.
Feldman et al. brue1 ; brue2 ; brue3 introduce the Best Recommendation with
Uniform Exploration (BRUE) algorithm. BRUE splits trials up to explicitly
focus on exploration and value estimation one at a time. BRUE achieves an
exponential bound $O(\exp(-n))$ on simple regret after $n$ trials brue1 .
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.

##  7 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 a 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^{*}(s_{0})$, which suggests a heuristic similar to
prst may be reasonable.

## References

  * [1] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2):235–256, 2002.
  * [2] David Auger, Adrien Couetoux, and Olivier Teytaud.  Continuous upper confidence trees with polynomial exploration–consistency.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 194–209. Springer, 2013.
  * [3] Richard Bellman.  A markovian decision process.  Journal of mathematics and mechanics, 6(5):679–684, 1957.
  * [4] Blai Bonet and Hector Geffner.  Labeled rtdp: Improving the convergence of real-time dynamic programming.  In ICAPS, volume 3, pages 12–21, 2003.
  * [5] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  arXiv preprint arXiv:1606.01540, 2016.
  * [6] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I 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 AI in games, 4(1):1–43, 2012.
  * [7] 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.
  * [8] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.  Pure exploration in finitely-armed and continuous-armed bandits.  Theoretical Computer Science, 412(19):1832–1852, 2011.
  * [9] Pierre-Arnaud Coquelin and Rémi Munos.  Bandit algorithms for tree search.  In Uncertainty in Artificial Intelligence, 2007.
  * [10] Tuan Q Dam, Carlo D’Eramo, Jan Peters, and Joni Pajarinen.  Convex regularization in monte-carlo tree search.  In International Conference on Machine Learning, pages 2365–2375. PMLR, 2021.
  * [11] Zohar Feldman and Carmel Domshlak.  Monte-carlo planning: Theoretically fast convergence meets practical efficiency.  arXiv preprint arXiv:1309.6828, 2013.
  * [12] Zohar Feldman and Carmel Domshlak.  On mabs and separation of concerns in monte-carlo planning for mdps.  In Twenty-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 tree search and rapid action value estimation in computer go.  Artificial Intelligence, 175(11):1856–1875, 2011.
  * [16] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine.  Reinforcement learning with deep energy-based policies.  In International Conference on Machine Learning, pages 1352–1361. PMLR, 2017.
  * [17] 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 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–62, 2001.
  * [19] Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony.  Selecting computations: Theory and applications.  arXiv preprint arXiv:1408.2048, 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 AI Perspective, volume 6.  Morgan & Claypool Publishers, 2012.
  * [25] Piotr Kozakowski, Mikołaj Pacek, and Piotr Miłoś.  Planning and learning using adaptive entropy tree search.  arXiv preprint arXiv: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 Marc Lanctot.  Minimizing simple and cumulative regret in 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):203–230, 2011.
  * [30] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis 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, Marc 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):1140–1144, 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.  Mcts based on simple regret.  In Proceedings of the AAAI Conference on 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, 17(9):972–975, 1991\.
  * [35] Alastair J 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:1902.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 D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al.  Maximum entropy inverse reinforcement learning.  2008\.

These appendices are structured as follows:

  * •

Appendix B gives details on how to adapt the BTS, DENTS, MENTS, RENTS and
TENTS algorithms to use average returns backups, rather than dynamic
programming backups, to arrive at the AR-BTS, AR-DENTS, AR-MENTS, AR-RENTS and
AR-TENTS algorithms respectively.

  * •

Appendix C covers algorithm details that we could not fit into the main paper.
Specifically:

    * –

in Appendix C.1 we discuss the computational complexity of BTS, DENTS and
MENTS in more detail, including what can be achieved by using the alias method
alias1,alias2;

    * –

in Appendix C.2 we give the specific details of how we adapted BTS, DENTS,
MENTS, RENTS and TENTS for two-player games and to utilise neural networks;

    * –

and in Appendix C.3 we summarise the differences between the MCTS algorithms
considered in this work in a table.

  * •

Appendix D generally covers additional details about experiments and results.
Specifically:

    * –

in Appendix D.1 we give more specific details about the gridworld envrionments
used in our experiments;

    * –

in Appendix D.2 we have a more detailed discussion about parameter
sensitivity, with additional results and discussion using the D-chain
environments in Appendix D.2.1 and in the Frozen Lake environment in Appendix
D.2.2;

    * –

in Appendix D.3 we give details for the hyperparameter search used to select
parameters in the gridworld domains;

    * –

in Appendix D.4 we show empirically that DENTS can follow a search policy very
similar to the MENTS search policy;

    * –

and in Appendix D.5 we give some additional details about our Go experiments,
including how we selected hyperparameters.

  * •

Appendix E constitutes the theoretical section of this work, beginning by
revisiting the MCTS stochastic process, introducing notation needed to reason
about convergence properties and then providing proofs for the results quoted
in the main paper and Appendix B. Appendix E has its own introduction/contents
to give an overview of how the theory is built up.

##  Appendix A Code

The code for this paper can be found at https://github.com/MWPainter/thts-
plus-plus/tree/xpr_go.

##  Appendix B Using average returns with Boltzmann search

In this section we consider how to adapt each of the algorithms considered in
this paper to use average returns. We start by describing AR-BTS and AR-DENTS
and then subsequently how AR-DENTS can be adapted to give AR-MENTS, AR-RENTS
and AR-TENTS. We also give an example of why the adaptations are necessary.

###  B.1 AR-BTS

We can replace the Bellman values used in BTS with average returns similar to
UCT, resulting in the subsequent AR-BTS algorithm. Recall that $\bar{Q}(s,a)$,
the average return at $(s,a)$, is defined by:

$\displaystyle\bar{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\bar{Q}(s_{t},a_{t})+\frac{\bar{R}(s_{t},a_{t})-\bar{Q}(s_{t},a_{t})}{N(s_{t},a_{t})+1},$
(28)

where $\bar{R}(s_{t},a_{t})=\sum_{i=t}^{H}R(s_{i},a_{i})$. An additional issue
that needs consideration when using average returns is that the resulting
empirical values will not converge to the optimal values when using a
stochastic policy, as we argue below. Hence, in AR-BTS we also decay the
search temperature, such that the Boltzmann policy tends towards a greedy
policy. So, let $\alpha$ be a non-negative function with $\alpha(m)\rightarrow
0$ as $m\rightarrow\infty$. The search policy used for AR-BTS is then:

$\displaystyle\pi_{\textnormal{AR-BTS}}(a|s)$
$\displaystyle=(1-\lambda_{s})\rho_{\textnormal{AR-
BTS}}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$ (29)
$\displaystyle\rho_{\textnormal{AR-BTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{1}{\alpha(N(s))}\left(\bar{Q}(s,a)\right)\right).$
(30)

The recommendation policy for AR-BTS then uses the $\bar{Q}$ average return
values:

$\displaystyle\psi_{\text{AR-BTS}}(s)$
$\displaystyle=\operatorname*{arg\,max}_{a\in\mathcal{A}}\bar{Q}(s,a).$ (31)

To see why the decaying search temperature is necessary, consider the MDP in
Figure 4, with a temperature of $\alpha(m)=1$. Consider the average return
$\bar{V}(2)$ from state $2$ that has been visited $N(2)$ times. The
probability of selecting action $a_{1}$ from state 2 will be $1/(1+e^{2})$,
and the probability of selecting action $a_{2}$ from state 2 will be
$e^{2}/(1+e^{2})$. So as $N(2)\rightarrow\infty$ we expect the average return
to converge to slightly less than two: $\bar{V}(2)\rightarrow
2e^{2}/(1+e^{2})<2$. Taking advantage of this, we can show that for any fixed
temperature $\alpha(m)=\alpha_{\text{fix}}$, there is an MDP that AR-BTS would
not be consistent. We summarise this result in Proposition B.1. Thus,
necessitating the use of the decaying search temperature.

Figure 4: An example MDP to demonstrate the necessity for a decaying search
temperature when using average returns.

######  Proposition B.1.

For any $\alpha_{\textnormal{fix}}>0$, there is an MDP $\mathcal{M}$ such that
AR-BTS with $\alpha(m)=\alpha_{\textnormal{fix}}$ is not consistent:
$\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{AR-BTS}})]\not\to 0$ as
$n\to\infty$.

###### Proof outline.

We give a proof outline in Section E.9, using an MDP similar to the one shown
in Figure 4. ∎

Additionally, provided the search temperature decays to zero, AR-BTS will be
consistent (Theorem B.2).

######  Theorem B.2.

For any MDP $\mathcal{M}$, if $\alpha(m)\rightarrow 0$ as $m\rightarrow\infty$
then $\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{AR-
BTS}})]\rightarrow 0$ as $n\rightarrow\infty$, where $n$ is the number of
trials.

###### Proof outline.

We give a proof outline in Section E.9. ∎

###  B.2 AR-DENTS

Using average returns in DENTS is similar to BTS. To compute the average
returns we use Equation (28) again. To compute the entropy values
$\mathcal{H}_{V}$ and $\mathcal{H}_{Q}$ to use in AR-DENTS, we use the same
entropy backups as in DENTS:

$\displaystyle\mathcal{H}_{V}(s_{t})$
$\displaystyle\leftarrow\mathcal{H}(\pi_{\textnormal{AR-
DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi_{\textnormal{AR-
DENTS}}(a_{t}|s_{t})\mathcal{H}_{Q}(s_{t},a_{t}),$ (32)
$\displaystyle\mathcal{H}_{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\frac{N(s^{\prime})}{N(s_{t},a_{t})}\mathcal{H}_{V}(s^{\prime}).$
(33)

The search policy in AR-DENTS is the same as in DENTS, but with the Bellman
value $\hat{Q}$ replaced by the average return value $\bar{Q}$:

$\displaystyle\pi_{\textnormal{AR-DENTS}}(a|s)$
$\displaystyle=(1-\lambda_{s})\rho_{\textnormal{AR-
DENTS}}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$ (34)
$\displaystyle\rho_{\textnormal{AR-DENTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{1}{\alpha(N(s))}\left(\bar{Q}(s,a)+\beta(N(s))\mathcal{H}_{Q}(s_{t},a_{t})\right)\right).$
(35)

The recommendation policy for AR-DENTS also use the $\bar{Q}$ average return
values:

$\displaystyle\psi_{\text{AR-DENTS}}(s)$
$\displaystyle=\operatorname*{arg\,max}_{a\in\mathcal{A}}\bar{Q}(s,a).$

Similarly to the AR-BTS result, we show that if $\alpha(m)\rightarrow 0$ and
$\beta(m)\rightarrow 0$, then AR-DENTS is consistent. Again, because we are
considering the AR versions of our algorithms from a practical viewpoint
rather than a theoretical one, we only show consistency without any specific
(simple) regret bounds.

######  Theorem B.3.

For any MDP $\mathcal{M}$, if $\alpha(m)\rightarrow 0$ and
$\beta(m)\rightarrow 0$ as $m\rightarrow\infty$ then
$\mathbb{E}[\textnormal{reg}(s_{0},\psi_{\textnormal{AR-DENTS}})]\rightarrow
0$ as $n\rightarrow\infty$, where $n$ is the number of trials.

###### Proof outline.

We give a proof outline in Section E.9. ∎

###  B.3 AR-MENTS, AR-RENTS and AR-TENTS

MENTS uses soft values, $\hat{Q}_{\textnormal{sft}}$, which are not obvious
how to replace with average returns. So to produce the AR variants of MENTS,
RENTS and TENTS we use AR-DENTS as a starting point.

##### AR-MENTS.

For AR-MENTS we use AR-DENTS, but set
$\beta(m)=\alpha(m)=\alpha_{\text{fix}}$. This algorithm resembles MENTS, as
the weighting used for entropy in soft values is the same as the Boltzmann
policy search temperature.

##### AR-RENTS.

To arrive at AR-RENTS, we replace any use of $\hat{Q}_{\textnormal{sft}}(s,a)$
with $\bar{Q}(s,a)+\beta(m)\mathcal{H}_{Q}(s,a)$. So we use Equations (28),
(32) and (33) for backups, but replace the Shannon entropy function
$\mathcal{H}$, with a relative entropy function
$\mathcal{H}_{\textnormal{relative}}$ in Equation (32). The relative entropy
function $\mathcal{H}_{\textnormal{relative}}$ uses the Kullback-Leibler
divergence between the search policy and the search policy of the parent
decision node. The search policy used is the same as in RENTS, with the
aforementioned substitution for soft values. See rents_your_tents for full
details on computing relative entropy and the search policy used in RENTS.

##### AR-TENTS.

Similarly, for AR-TENTS, we replace any use of
$\hat{Q}^{m}_{\textnormal{sft}}(s,a)$ with
$\bar{Q}^{m}(s,a)+\beta(m)\mathcal{H}_{Q}(s,a)$, and use Equations (28), (32)
and (33) for backups. This time, we replace the Shannon entropy function
$\mathcal{H}$, with a Tsallis entropy function
$\mathcal{H}_{\textnormal{Tsallis}}$ in Equation (32). Again, we use the same
search policy used in TENTS, with the substitution for soft values. See
rents_your_tents for how Tsallis entropy is computed and the corresponding
search policy for TENTS.

##  Appendix C Additional algorithm discussion

###  C.1 The alias method, implementation details and optimisations

The Alias method alias1 ; alias2 can be used to sample from fixed categorical
distribution in $O(1)$ time. If the distribution consists of $m$ categories,
then a preprocessing step of $O(m)$ is needed to construct the table, details
on how to construct the table can be found in alias2 . We provide a small
example of an alias table in Figure 5.

Figure 5: An example of an alias table for a categorical distribution over
four actions. To sample from the table we can draw a random index from $I\sim
U(\\{1,2,3,4\\})$, sample a uniformly random number from $x\sim U(0,1)$ and
then follow the pointer depending on if $x>\text{thresholds}[I]$ or not. For
example, sampling either $(I,x)=(2,0.5)$ or $(I,x)=(3,0.1)$ would lead to the
action $a_{3}$.

Any MCTS algorithm that samples actions from a stochastic distribution can
make use of the Alias method, for example all of the Boltzmann search
algorithms considered in this work. For a node with $A=|\mathcal{A}|$
actions/children, an MCTS algorithm that samples actions from a distribution
would typically on each trial: construct the distribution in $O(A)$ time, and
then sample from the distribution using a single uniform random number in
$O(A)$ time. However, we can instead construct a distribution every $A$ times
we visit a search node, which gives an amortised complexity of $O(1)$, and
then sampling from an alias table only takes $O(1)$ time.

It is worth noting that when we use the Alias method, we are not sampling from
the most up to date distributions possible, so we are making a trade off
between being able to sample actions more efficiently and using the most up to
date distributions. Moreover, when we use this method, we are making use of
the stochastic distribution that will still allow a variety of actions to be
sampled on different trials with a fixed distribution. In contrast, UCT uses a
deterministic distribution (recall Equation (7)) which selects the action with
maximum UCB value and different actions are selected on different trials by
changing the distribution (i.e. a new action is selected typically when the
confidence term becomes large enough, which requires the UCB values to be
computed each time).

We now consider the runtime complexity of running $n$ trials for different
algorithms. We summarise these complexities as part of Table 2 and we assume
that successor states can be sampled in $O(1)$ time, noting that if we are
given a tabular successor state distribution then we can use the Alias method
again to sample from it in $O(1)$ time.

####  C.1.1 BTS backup complexity

Firstly, recall the backups used by BTS for a trajectory
$\tau=(s_{0},a_{0},...,a_{h-1},s_{h})$:

$\displaystyle\hat{Q}(s_{t},a_{t})$ $\displaystyle\leftarrow
R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}(s^{\prime})\right),$
(36) $\displaystyle\hat{V}(s_{t})$
$\displaystyle\leftarrow\max_{a\in\mathcal{A}}\hat{Q}(s_{t},a).$ (37)

In Equation (36) observe that only the $\hat{V}(s_{t})$ term in the sum will
change, that is, for each
$s^{\prime}\in\\{s^{\prime\prime}\in\textnormal{Succ}(s_{t},a_{t})|s^{\prime\prime}\neq
s_{t+1}\\}$ that the value of $\hat{V}(s^{\prime})$ will be the same. Hence,
we can implement the update in $O(1)$ as:

$\displaystyle\hat{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\begin{cases}R(s_{t},a_{t})+\hat{V}(s^{\prime})&\text{if
}N(s_{t},a_{t})=1,\\\
\hat{Q}(s_{t},a_{t})-\frac{N(s_{t+1})-1}{N(s_{t},a_{t})-1}\hat{V}^{\text{old}}(s_{t+1})+\frac{N(s_{t+1})}{N(s_{t},a_{t})}\hat{V}(s_{t+1})&\text{if
}N(s_{t},a_{t})>1,\end{cases}$ (38)

where $\hat{V}^{\text{old}}(s_{t+1})$ is the previous value of
$\hat{V}(s_{t+1})$. To more efficiently implement Equation (37) we can use a
max heap, which will take $O(\log(A))$ to update the value of
$\hat{Q}(s_{t},a_{t})$ in the heap, and $O(1)$ to read out the maximum value.

Hence, an optimised version of the BTS backups will take $O(\log(A))$. So when
running BTS using the Alias method, we need a total of $O(\log(A))$ time to
perform the sampling and backups of each node visited, and additionally we
will initialise a new Alias table on every trial for the new node added. Hence
the runtime complexity of running $n$ trials of BTS with the Alias method will
take $O(n(H\log(A)+A))$.

####  C.1.2 DENTS backup complexity

When using the Alias method with DENTS, we also need to consider the entropy
backups too:

$\displaystyle\mathcal{H}_{V}(s_{t})$
$\displaystyle\leftarrow\mathcal{H}(\pi_{\textnormal{DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi_{\textnormal{DENTS}}(a|s_{t})\mathcal{H}_{Q}(s_{t},a),$
(39) $\displaystyle\mathcal{H}_{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\frac{N(s^{\prime})}{N(s_{t},a_{t})}\mathcal{H}_{V}(s^{\prime}).$
(40)

The backup for $\mathcal{H}_{Q}$ can be performed in $O(1)$ time, similarly to
Equation (38):

$\displaystyle\mathcal{H}_{Q}(s_{t},a_{t})$
$\displaystyle\leftarrow\begin{cases}\mathcal{H}_{V}(s_{t+1})&\text{if
}N(s_{t},a_{t})=1,\\\
\mathcal{H}_{Q}(s_{t},a_{t})-\frac{N(s_{t+1})-1}{N(s_{t},a_{t})-1}\mathcal{H}_{V}^{\text{old}}(s_{t+1})\hat{V}^{+}(s_{t+1})\frac{N(s_{t+1})}{N(s_{t},a_{t})}\mathcal{H}_{V}(s_{t+1})&\text{if
}N(s_{t},a_{t})>1,\end{cases}$ (41)

where $\mathcal{H}_{V}^{\text{old}}(s_{t+1})$ is the previous value of
$\mathcal{H}_{V}(s_{t+1})$.

The backup for $\mathcal{H}_{V}$ can also be implemented in amortised $O(1)$
time, by noting that we are only updating $\pi_{\textnormal{DENTS}}$ every $A$
visits. Let $\pi^{\text{old}}_{\textnormal{DENTS}}$ be the policy on the
previous trial. Then, we have to perform the full $O(A)$ backup when the
policy is updated every $A$ visits, but otherwise we can get away with an
$O(1)$ backup:

$\displaystyle\mathcal{H}_{V}(s_{t})$
$\displaystyle\leftarrow\begin{cases}\mathcal{H}(\pi_{\textnormal{DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi_{\textnormal{DENTS}}(a|s_{t})\mathcal{H}_{Q}(s_{t},a)&\text{if
}\pi_{\textnormal{DENTS}}\neq\pi^{\text{old}}_{\textnormal{DENTS}},\\\
\mathcal{H}_{V}(s_{t})+\pi_{\textnormal{DENTS}}(a|s_{t})\left(\mathcal{H}_{Q}(s_{t},a_{t})-\mathcal{H}^{\text{old}}_{Q}(s_{t},a_{t})\right)&\text{if
}\pi_{\textnormal{DENTS}}=\pi^{\text{old}}_{\textnormal{DENTS}},\end{cases}$
(42)

where $\mathcal{H}^{\text{old}}_{Q}(s_{t},a_{t})$ is the previous value of
$\mathcal{H}_{Q}(s_{t},a_{t})$.

As the entropy backups used in DENTS can be implemented in amortised $O(1)$
time, it follows that the complexity of running $n$ trials of DENTS with the
Alias method will also take $O(n(H\log(A)+A))$.

####  C.1.3 MENTS backup complexity

Recall the backups used for MENTS:

$\displaystyle\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})$
$\displaystyle\leftarrow
R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s,a)}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}_{\textnormal{sft}}(s^{\prime})\right),$
(43) $\displaystyle\hat{V}_{\textnormal{sft}}(s_{t})$
$\displaystyle\leftarrow\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\hat{Q}_{\textnormal{sft}}(s_{t},a)\right).$
(44)

The backup for $\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})$ can be implemented in
$O(1)$ similarly to Equation (38). However, considering how to implement
Equation (44) is more complex. Firstly, we point out the implementing the
equation exactly as written is infact numerically unstable, and in practise we
need to make use of the equation:

$\displaystyle\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\hat{Q}_{\textnormal{sft}}(s_{t},a)\right)=\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\left(\hat{Q}_{\textnormal{sft}}(s_{t},a)-C\right)\right)+C,$
(45)

where $C$ is an arbitrary constant. The value of $C$ needs to be chosen
carefully to avoid numerical underflow or overflow, and is typically set to
$C=\max_{a}\hat{Q}_{\textnormal{sft}}(s_{t},a)$. To efficiently compute this
backup, we can keep two auxilary variables:

$\displaystyle M(s_{t})$
$\displaystyle=\max_{a}\hat{Q}_{\textnormal{sft}}(s_{t},a)$ (46)
$\displaystyle E(s_{t})$
$\displaystyle=\sum_{a\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\left(\hat{Q}_{\textnormal{sft}}(s_{t},a)-M(s_{t})\right)\right).$
(47)

Now we can perform the backup for $\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})$ as
follows:

$\displaystyle M(s_{t})$
$\displaystyle\leftarrow\max_{a}\hat{Q}_{\textnormal{sft}}(s_{t},a)$ (48)
$\displaystyle E(s_{t})$ $\displaystyle\leftarrow\begin{cases}\exp(0)&\text{
if}N(s_{t})=1\\\
\left(E(s_{t})-\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{\text{old}}_{\textnormal{sft}}(s_{t},a_{t})-M^{\text{old}}(s_{t})\right)\right)\right)\exp\left(\frac{1}{\alpha}(M^{\text{old}}(s_{t})-M(s_{t}))\right)\\\
\ \ \ \ \
+\exp\left(\frac{1}{\alpha}\left(\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})-M(s_{t})\right)\right)&\text{
if}N(s_{t})>1.\end{cases}$ (49)
$\displaystyle\hat{V}_{\textnormal{sft}}(s_{t})$
$\displaystyle\leftarrow\alpha\log(E(s_{t}))+M(s_{t}),$ (50)

where
$M^{\text{old}}(s_{t}),\hat{Q}^{\text{old}}_{\textnormal{sft}}(s_{t},a_{t})$
are the previous values of $M(s_{t}),\hat{Q}_{\textnormal{sft}}(s_{t},a_{t})$
respectively. Similarly to the BTS backups, the requirement of computing a
$\max$ operation means that these backups can be computed in $O(\log(A))$
time, so the complexity of running $n$ trials of MENTS with the Alias method
takes $O(n(H\log(A)+A))$ time.

It may be possible to implement MENTS faster with a runtime of $O(n(H+A))$ if
we could set $M(s_{t})$ to some constant value, however this will likely
depend on the MDP and the scale of the rewards. Additionally, we found even
running this version of MENTS to be quite unstable, and had to resort to using
$O(A)$ backups for MENTS in our experiments.

####  C.1.4 RENTS and TENTS

Both RENTS and TENTS can utilise the Alias method too. We did not consider how
to optimise the backups for these algorithms.

####  C.1.5 Average return complexities

For the AR versions of the algorithms, we note that the backup from Equation
(28) can be implemented in $O(1)$ time. Following similar reasoning to the
previous algorithms, this means that running $n$ trials with the Alias method
for one of the average return algorithms will take $O(n(H+A))$ time.

####  C.1.6 Decaying the search temperature

Although theoretically using a fixed search temperature $\alpha$ is sufficient
for BTS and DENTS to converge, in practise algorithms may perform better with
a decaying search temperature $\alpha(m)$ as described in AR-BTS and AR-DENTS.
Note that the proofs of convergence for AR-BTS and AR-DENTS also hold for BTS
with a decaying temperature. A decaying search temperature would allow BTS and
DENTS to focus on deeper parts of the search tree over time.

###  C.2 Adapting Boltzmann search algorithms for two-player games and neural
nets

Now we will detail the adaptions required for each of BTS, DENTS, and MENTS to
be used for games. For completeness, we reiterate the adaptions for BTS.

To run our algorithms on games with two players we need to account for an
opponent that is trying to minimise the value of the game. The agent playing
as black (or the player) in Go will act on odd timesteps, and the opponent
playing as white will act on even timesteps. Fairly informally, this means
that the maximum entropy objective needs to be updated:

$\displaystyle
V^{\pi}_{\textnormal{sft}}(s,t)=\mathbb{E}_{\pi}\left[\sum_{i=t}^{H}R\left(s_{i},a_{i}\right)+(-1)^{t-1}\alpha\mathcal{H}\left(\pi\left(\cdot|s_{i}\right)\right)\Big{|}s_{t}=s\right].$
(51)

This means that each agent (the player and the opponent) will be
simultaneously trying to maximise their own entropy, whilst minimising the
others.

##### BTS

Values can be initialised with the neural networks as
$Q^{\text{init}}(s,a)=\log\tilde{\pi}(a|s)+B$ and
$V^{\text{init}}(s)=\tilde{V}(s)$, where $B$ is a constant (adapted from Xiao
et al. xiao2019maximum ). With such an initialisation, the initial BTS policy
is $\rho_{\textnormal{BTS}}(a|s)\propto\tilde{\pi}(a|s)^{1/\alpha}$.

The stochastic search policy naturally lends itself to mixing in a prior
policy, so we can replace BTS search policy $\pi_{\textnormal{BTS}}^{n}$
(Equation (15)) with $\pi_{\textnormal{BTS,mix}}$:

$\displaystyle\pi_{\textnormal{BTS,mix}}(a|s)$
$\displaystyle=\lambda_{\tilde{\pi}}\tilde{\pi}(a|s)+(1-\lambda_{\tilde{\pi}})\pi_{\textnormal{BTS}}(a|s)$
(52)
$\displaystyle=\lambda_{\tilde{\pi}}\tilde{\pi}(a|s)+(1-\lambda_{\tilde{\pi}})(1-\lambda_{s})\rho_{\textnormal{BTS}}(a|s)+\frac{(1-\lambda_{\tilde{\pi}})\lambda_{s}}{|\mathcal{A}|},$
(53)

where $\lambda_{\tilde{\pi}}=\min(1,\epsilon_{\tilde{\pi}}/\log(e+N(s)))$, and
$\epsilon_{\tilde{\pi}}\in(0,\infty)$ controls the weighting for the prior
policy. To run BTS on a two-player game we need to account the opponent trying
to minimise the value of the game. In BTS we can negate the values used in the
search policy, and replace the max operation with a min in Bellman backups.
That is, we replace equations (16) and (18) with:

$\displaystyle\rho_{\textnormal{BTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{-1}{\alpha}\hat{Q}(s,a)\right),$ (54)
$\displaystyle\hat{V}(s_{t})$
$\displaystyle=\min_{a\in\mathcal{A}}\hat{Q}(s_{t},a).$ (55)

Finally, when making a recommendation as the opponent, we use the replace the
recommendation policy with:

$\displaystyle\psi_{\text{BTS}}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}\hat{Q}(s,a).$
(56)

##### MENTS

For MENTS we can use the same initialisations as in BTS, that is
$Q^{\text{init}}_{\text{sft}}(s,a)=\log\tilde{\pi}(a|s)+B$ and
$V^{\text{init}}(s)=\tilde{V}(s)$, with the same value for $B$. The prior
policy $\tilde{\pi}$ is mixed into the MENTS search policy in the same way as
for BTS (Equation 53).

At opponent nodes, we can replace any use of the temperature $\alpha$ by
$-\alpha$, which effectively turns the softmax into a softmin and gives the
highest density to the lowest values in the search policy. So at opponent
nodes, we replace Equations (10) and (12) by:

$\displaystyle\rho_{\textnormal{sft}}(a|s)$
$\displaystyle=\exp\left(\frac{-1}{\alpha}\left(\hat{Q}_{\textnormal{sft}}(s,a)-\hat{V}_{\textnormal{sft}}(s)\right)\right),$
(57) $\displaystyle\hat{V}_{\textnormal{sft}}(s_{t})$
$\displaystyle=-\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{-1}{\alpha}\hat{Q}_{\textnormal{sft}}(s_{t},a)\right).$
(58)

Finally, to make a recommendation as the opponent, we replace the
recommendation policy with:

$\displaystyle\psi_{\text{MENTS}}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}\hat{Q}_{\textnormal{sft}}(s,a).$
(59)

##### DENTS

For DENTS we again use the same initialisations as BTS, setting
$Q^{\text{init}}(s,a)=\log\tilde{\pi}(a|s)+B$ and
$V^{\text{init}}(s)=\tilde{V}(s)$, using the same value for $B$. And again,
the prior policy $\tilde{\pi}$ is mixed into the DENTS search policy in the
same way as for BTS (Equation 53).

At opponent nodes, we update the search policy and backups by replacing
Equations (21) and (22) by the following:

$\displaystyle\rho_{\textnormal{DENTS}}(a|s)$
$\displaystyle\propto\exp\left(\frac{-1}{\alpha}\left(\hat{Q}(s,a)+\beta(N(s))\mathcal{H}_{Q}(s_{t},a_{t})\right)\right),$
(60) $\displaystyle\mathcal{H}_{V}(s_{t})$
$\displaystyle=-\mathcal{H}(\pi_{\textnormal{DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi_{\textnormal{DENTS}}(a_{t}|s_{t})\mathcal{H}_{Q}(s_{t},a_{t}),$
(61)

and we use replacement for Bellman backups as BTS does in Equation (55).
Finally, the recommendation policy for an opponent is:

$\displaystyle\psi_{\text{DENTS}}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}\hat{Q}(s,a).$
(62)

###  C.3 Comparison of MCTS algorithms

In Table 2 we summarise the properties of UCT, MENTS, BTS and DENTS so that
they can be easily compared.

We also summarise here the benefits that using a stochastic (Boltzmann) policy
for action selection can provide:

  * •

Using a stochastic policy allows the Alias method (as described in Section
C.1) to be used, which can significantly increase the number of trials that
can be run in a fixed time period;

  * •

Using a stochastic policy naturally encourages exploration as it will still
always have some probability of sampling each action;

  * •

And the entropy can be computed of a stochastic distribution, which can then
be used as an exploration bonus.

The benefits of additional exploration from entropy and the stochastic
distribution include: helping to find delayed/sparse rewards in the
environment; confirming that bad actions are in fact bad; and, greater
exploration leads to less contention between threads in a multi-threaded
implementation (discussed in Section C.3.2).

| UCT | MENTS | BTS | DENTS
---|---|---|---|---
Is consistent for any setting of hyperparameters
(Simple regret tends to 0 as $n\rightarrow\infty$) | $\checkmark$ | X | $\checkmark$ | $\checkmark$
Utilises entropy for exploration
(E.g. Helpful for sparser rewards) | X | $\checkmark$ | X | $\checkmark$
Samples actions stochastically
(from a Boltzmann distribution) | X | $\checkmark$ | $\checkmark$ | $\checkmark$
Optimises for cumulative regret
(penalises suboptimal actions during planning) | $\checkmark$ | X | X | X
Optimises for simple regret
(does not penalise exploration during planning) | X | X | $\checkmark$ | $\checkmark$
Complexity to run $n$ trials | $O(nHA)$
Complexity to run $n$ trials using the Alias method
(with backups implemented as efficiently as possible) | N/A | $O(n(H\log(A)+A))$
Table 2: Summary of complexities for different algorithms considered in this
work, considering average return variants and alias table optimisations.

####  C.3.1 When to use each MCTS algorithm

Although the best way to know for sure which MCTS algorithm will be the best
for a given problem is to directly try it and compare performance, there are
some properties of problems that give a good indication of which algorithm
would be a good fit.

Two properties of environments that would make them more amenable to using
entropy for exploration are large delayed rewards, and, containing trap states
(i.e. states where the agent cannot move to another state for the rest of the
trial). The Frozen Lake environment (Section 5.1.1) demonstrates both of these
properties, there is a large reward that the agent only gets when it reaches
the goal, and there are holes that the agent falls into. Hence, if a problem
contains large delayed rewards or trap states, then DENTS would likely be the
best fit.

When the reward signal is dense or engineered so that optimal policy can be
found without needing additional exploration, then using entropy for
additional exploration may cause unnecessary additional exploration, in which
case using UCT or BTS would be more suitable.

Finally, we note that there may be more properties of problems that we have
not considered in this work that make them ameniable to different algorithms.
For example, as mentioned in Section 3 that sometimes it may be desirable for
an agent to follow a maximum entropy policy to explore and learn in an unknown
environment, in which case MENTS, RENTS or TENTS may be more preferrable.

####  C.3.2 Discussion on multi-threading in MCTS

In this section we give a brief discussion about why Boltzmann search policies
naturally utilise multi-threading more than UCT. Consider a two-armed bandit,
with actions $a_{1}$ and $a_{2}$, and corresponding rewards of $0$ and $1$
respectively. Intuitively, an emphasis on exploration will lead to less
contention between threads as they will explore different parts of the search
tree.

When running UCB on this multi-armed bandit, with a bias of $2.0$, it will
pull $a_{1}$ a total of $20$ times in the first $1000$ pulls, and then it will
only pull $a_{1}$ a total of $9$ times in the next $4000$ pulls, as it begins
to exploit. If we had multiple threads trying to pull arms simultaneously, but
they could not pull arm $a_{2}$ simultaneously, then it would lead to lots of
contention between the threads.

In stark contrast, when using a Boltzmann policy, with a temperature of $1.0$
on this multi-armed bandit, the expected number of pulls for $a_{1}$ will be
$268$ pull for every $1000$ total pulls. In a multi-threaded environment,
having around a quarter of the threads pulling arm $a_{1}$ rather than all
threads pulling arm $a_{2}$ naturally leads to less contention and waiting.

Although this is an unrealistic example, it highlights the problem at hand:
the exploitation of UCB leads to contention between threads in a multi-
threaded setting. Moreover, this can be witnessed in Section D.5, Table
LABEL:table:go_trials_per_move where UCT is able to run fewer trials in the
earlier moves of a Go game.

Aditionally, it is worth observing that both UCT and BTS have parameters that
control the amount of exploration (the bias $c$ and search temperature
$\alpha$ for UCT and BTS respectively). However, because UCT is designed with
cumulative regret in mind, it will always towards picking the same action on
successive trials, as can be seen in our simple example.

##  Appendix D Additional results and discussion

###  D.1 Gridworld environment details

For space, the specific maps for the gridworlds are omitted from the results
section in the main paper. In the gridworld maps, S denotes the starting
location of the agent, F denotes spaces the agent can move to, H denote holes
that end the agents trial and G is the goal location.

In Figure 6(a) we give an 8x8 Frozen Lake environment that is used in Section
D.2 to demonstrate how the different algorithms perform with a variety of
temperatures. Figure 6(b) gives the 8x12 Frozen Lake Environment that is used
for hyperparameter selection in Section D.3. And in Figure 6(c) we give the
8x12 Frozen Lake Environment that is used to test the algorithms in Section 5.
Each of these maps was randomly generated, with each location having a
probability of $1/5$ of being a hole, and the maps were checked to have a
viable path from the starting location to the goal location.

Aditionally, we give the map used in the 6x6 Sailing Problem, and the wind
transition probabilities in Figure 7. In the Sailing domain, actions and wind
directions can take values in $\\{0,1,...,7\\}$, with a value of $0$
representing North/up, $2$ representing East/right, $4$ representing
South/down and $6$ representing West/right. The remaining numbers represent
the inter-cardinal directions. In Section D.3 the wind direction was set to
North (or $0$) in the initial state, and for testing in Section 5, the initial
wind direction was set to South-East (or $3$).

SFFFFFHF
FFFFFFFF
FHFHFFFF
FFFFFFHH
FFFHFFFF
FHHHFFFF
FFFFFHFF
FFFFFFFG

(a) 8x8 Frozen Lake.

SFHFFFHFFFFF
FFFFFFFHFFFF
HFFFFFHFFFFF
FHFFHFFFFFFF
HHFFFFFFFFFF
FHFFFFHFFFFF
FHFFFHHFHFFF
FFFFFFFFFHHG

(b) 8x12 Frozen Lake.

SFHFFFFFFFHF
FFFFFFFFFFFF
FHFFFFHFFFFF
FFFHFFFFFFHF
FFFFFFFFFFFF
FFFFHFFFHFFF
FFHFFFFFFFFH
FFFFFFFFFFFG

(c) 8x12 Test Frozen Lake.

Figure 6: Maps used for experiments using the Frozen Lake environment in
Sections 5, D.2 and D.3. S is the starting location for the agent, F
represents floor that the agent can move too, H are holes that end the agents
trial and G is the goal location.

FFFFFG
FFFFFF
FFFFFF
FFFFFF
FFFFFF
SFFFFF

(a) 6x6 Sailing Problem map.

$\displaystyle\begin{pmatrix}0.4&0.3&0.0&0.0&0.0&0.0&0.0&0.3\\\
0.4&0.3&0.3&0.0&0.0&0.0&0.0&0.0\\\ 0.0&0.4&0.3&0.3&0.0&0.0&0.0&0.0\\\
0.0&0.0&0.4&0.3&0.3&0.0&0.0&0.0\\\ 0.0&0.0&0.0&0.4&0.2&0.4&0.0&0.0\\\
0.0&0.0&0.0&0.0&0.3&0.3&0.4&0.0\\\ 0.0&0.0&0.0&0.0&0.0&0.3&0.3&0.4\\\
0.4&0.0&0.0&0.0&0.0&0.0&0.3&0.3\end{pmatrix}$ (b) Wind transition
probabilities.

Figure 7: The map used for the 6x6 Sailing Problem and the wind transition
probabilities. For the wind transition probabilities, the $(i,j)th$ element of
the matrix denotes the probability that the wind changes from direction $i$ to
direction $j$, where $0$ denotes North/up, $1$ denotes North-East/up-right,
and so on.

###  D.2 Futher discussion on parameter sensitivity

In this section we provide a more detailed discussion on sensitivity to the
temperature parameter in MENTS xiao2019maximum , RENTS and TENTS
rents_your_tents . We provide more thorough results on D-chain environments,
with each algorithm, and varying both the temperature parameter and the
$\epsilon$ exploration parameter. Additionally, we provide results using the
8x8 Frozen Lake environment (Figure 6(a)) using a variety of temperatures to
demonstrate how each algorithm performs with different temperatures in that
domain.

####  D.2.1 Parameter sensitivity in D-Chain

Figure 8: An illustration of the (modified) D-chain problem, where 1 is the
starting state, transitions are deterministic and values next to states
represent rewards for arriving in that state.

We run each algorithm with a variety of $\alpha$ temperatures, and the
$\epsilon$ exploration parameter on the 10-chain environments (Figure 8).
Additionally, we ran UCT with a variety of bias parameters. Figures 9, 10, 11,
12, 13 and 14 give results for the 10-chain environment, with algorithms UCT,
MENTS, RENTS, TENTS, BTS and DENTS respectively. Figures 15, 16, 17, 18, 19
and 20 give results for the modified 10-chain environment, with algorithms
UCT, MENTS, RENTS, TENTS, BTS and DENTS respectively.

As expected with UCT, regardless of how the bias parameter is set, in both the
10-chain ($D=10$, $R_{f}=1.0$) and modified 10-chain ($D=10$, $R_{f}=0.5$)
environments, it only achieves a value of $0.9$. See Figures 9 and 15 for
plots.

As discussed in Section 3, for higher temperatures in MENTS it will find the
reward of $R_{f}$ in both the 10-chain and modified 10-chain environments. At
a temperature of $\alpha=0.15$ MENTS is able to find the reward of $R_{f}=1$
on the 10-chain (Figure 10), but will still recommend a policy that gives the
reward of $R_{f}=0.5$ on the modified 10-chain (Figure 16). At a temperature
of $\alpha=0.1$ MENTS will struggle to find the reward of $R_{f}=1$ in the
10-chain, without the help of the exploration parameter, but this is the first
temperature we tried that was able to recommend the optimal policy in the
modified 10-chain (Figure 16). For low temperatures, such as $\alpha=0.01$,
MENTS was able to find the optimal policy, but in the case of the 10-chain
with $R_{f}=1$ it can only do so with the help of a higher exploration
parameter.

When we ran TENTS on the (modified) 10-chain, we see results that parallel
MENTS, see Figures 12 and 18. Interestingly, RENTS was only able to find the
reward of $R_{f}=1$ on the 10-chain environment if we used a low temperature,
$\alpha=0.01$ and a high exploration parameter, $\epsilon=10$. Otherwise,
RENTS tended to behave similarly to UCT on these environments, see Figures 11
and 17.

In contrast, BTS was able to find the reward of $R_{f}=1.0$ in the 10-chain
when a high search temperature or high exploration parameter was used (Figure
13). And, in the modified 10-chain, BTS always achieves a reward of $0.9$
regardless of how the parameters are set (Figure 19). DENTS performance on the
10-chain (Figure 14) and modified 10-chain (Figure 20) was similar to BTS, but
tended to find the reward of $R_{f}=1$ in the 10-chain marginally faster. For
the decay function $\beta$ in DENTS, we always set $\beta(m)=\alpha/\log(e+m)$
for these experiments.

To demonstrate that the $\epsilon$ exploration parameter is insufficient to
make up for a low temperature, we also consider the 20-chain ($D=20$,
$R_{f}=1$) and modified 20-chain ($D=20$, $R_{f}=0.5$) problems. We don’t give
plots for all algorithms on both of the 20-chain environments like we do for
10-chain environments, but opt for the plots that demonstrate something
interesting.

In Figure 21 we see MENTS on the 20-chain is able to find the reward of
$R_{f}=1$ for higher temperatures. However, this time, the exploration
parameter does not make much of an impact when using lower temperatures.
Moreover, a large exploration parameter appears to negatively impact MENTS
ability to find $R_{f}=1$. This makes sense considering that a uniformly
random policy will find the reward at the end of the chain once every $2^{10}$
trials in the 10-chain, but only once every $2^{20}$ in the 20-chain. Again,
on the modified 20-chain, MENTS is only able to recommend the optimal policy
for low temperatures (see Figure 22).

When we ran BTS on the 20-chain, it was unsuccessful at finding the final
reward of $R_{f}=1$, which makes sense as it is not using entropy for
exploration, and it is unlikely to follow a random policy to the end of the
chain (Figure 23). For DENTS, we again used a decay function of
$\beta(m)=\alpha/\log(e+m)$ for simplicity, and unfortunately it was only able
to make slow progress towards finding the final reward of $R_{f}=1$ for high
temperatures. However, if we independently set the values of $\alpha$ and

However, DENTS on the 20-chain begins to make slow progress towards finding
the final reward of $R_{f}=1$, but requires a higher temperature to be used,
as we decay the weighting of entropy over time (Figure 24). Again we used a
decay function of $\beta(m)=\alpha/\log(e+m)$ here for simplicity, and if we
properly select them DENTS is more than capable of solving the 20-chain. For
example we show that using DENTS with $\alpha=0.5$, $\beta(m)=10/\log(e+m)$
and $\epsilon=0.01$ in Figure 26, where $\alpha$ is set low enough that there
is still a high probability of following the chain to the end, $\beta$ is set
to be large initially to encourage exploring with the entropy reward and
$\epsilon$ is set low to avoid random exploration ending trials before
reaching the end of the chain. If we were to run DENTS and BTS on the modified
20-chain they would recommend the optimal policy giving a value of $0.95$ for
all of the parameters we searched over (not shown).

Finally, in Figure 25 we also consider running DENTS, but instead setting
$\beta(m)=\alpha$ to replicate MENTS. The main difference between DENTS in
this case and MENTS is the recommendation policy, where DENTS uses the Bellman
values for recommendations, rather than soft values. So even in cases where
the MENTS search is more desirable, we can replicate it with DENTS while
providing recommendations for the standard objective. Moreover, running DENTS
with $\beta(m)=\alpha$ on the modified 20-chain would always yield the optimal
value of $0.95$ because of the use of Bellman values for recommendations (not
shown).

Bias set using prst .

Bias $=0.1$.

Bias $=1$.

Bias $=2$.

Bias $=10$.

Bias $=100$.

Figure 9: Results for UCT on the 10-chain ($D=10$, $R_{f}=1.0$), for varying
bias parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 10: Results for MENTS on the 10-chain ($D=10$, $R_{f}=1.0$), for
varying temperatures and exploration parameters.

$\alpha=1000,\epsilon=0.01$

$\alpha=1000,\epsilon=0.1$

$\alpha=1000,\epsilon=1$

$\alpha=1000,\epsilon=10$

$\alpha=100,\epsilon=0.01$

$\alpha=100,\epsilon=0.1$

$\alpha=100,\epsilon=1$

$\alpha=100,\epsilon=10$

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.01,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 11: Results for RENTS on the 10-chain ($D=10$, $R_{f}=1.0$), for
varying temperatures and exploration parameters.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.7,\epsilon=0.01$

$\alpha=0.7,\epsilon=0.1$

$\alpha=0.7,\epsilon=1$

$\alpha=0.7,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.3,\epsilon=0.01$

$\alpha=0.3,\epsilon=0.1$

$\alpha=0.3,\epsilon=1$

$\alpha=0.3,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 12: Results for TENTS on the 10-chain ($D=10$, $R_{f}=1.0$), for
varying temperatures and exploration parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 13: Results for BTS on the 10-chain ($D=10$, $R_{f}=1.0$), for varying
temperatures and exploration parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 14: Results for DENTS on the 10-chain ($D=10$, $R_{f}=1.0$), for
varying temperatures and exploration parameters. The decay function was set to
$\beta(m)=\alpha/\log(e+m)$.

Bias set using prst .

Bias $=0.1$.

Bias $=1$.

Bias $=2$.

Bias $=10$.

Bias $=100$.

Figure 15: Results for UCT on the modified 10-chain ($D=10$, $R_{f}=0.5$), for
varying bias parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 16: Results for MENTS on the modified 10-chain ($D=10$, $R_{f}=0.5$),
for varying temperatures and exploration parameters.

$\alpha=1000,\epsilon=0.01$

$\alpha=1000,\epsilon=0.1$

$\alpha=1000,\epsilon=1$

$\alpha=1000,\epsilon=10$

$\alpha=100,\epsilon=0.01$

$\alpha=100,\epsilon=0.1$

$\alpha=100,\epsilon=1$

$\alpha=100,\epsilon=10$

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.01,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 17: Results for RENTS on the modified 10-chain ($D=10$, $R_{f}=0.5$),
for varying temperatures and exploration parameters.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.7,\epsilon=0.01$

$\alpha=0.7,\epsilon=0.1$

$\alpha=0.7,\epsilon=1$

$\alpha=0.7,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.3,\epsilon=0.01$

$\alpha=0.3,\epsilon=0.1$

$\alpha=0.3,\epsilon=1$

$\alpha=0.3,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 18: Results for TENTS on the modified 10-chain ($D=10$, $R_{f}=0.5$),
for varying temperatures and exploration parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 19: Results for BTS on the modified 10-chain ($D=10$, $R_{f}=0.5$), for
varying temperatures and exploration parameters.

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

$\alpha=0.01,\epsilon=0.01$

$\alpha=0.01,\epsilon=0.1$

$\alpha=0.01,\epsilon=1$

$\alpha=0.01,\epsilon=10$

Figure 20: Results for DENTS on the modified 10-chain ($D=10$, $R_{f}=0.5$),
for varying temperatures and exploration parameters. The decay function was
set to $\beta(m)=\alpha/\log(e+m)$.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

Figure 21: Results for MENTS on the 20-chain ($D=20$, $R_{f}=1.0$), for
varying temperatures and exploration parameters.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

Figure 22: Results for MENTS on the modified 20-chain ($D=20$, $R_{f}=0.5$),
for varying temperatures and exploration parameters.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

Figure 23: Results for BTS on the 20-chain ($D=20$, $R_{f}=1.0$), for varying
temperatures and exploration parameters.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

Figure 24: Results for DENTS on the 20-chain ($D=20$, $R_{f}=1.0$), for
varying temperatures and exploration parameters. The decay function was set to
$\beta(m)=\alpha/\log(e+m)$.

$\alpha=10,\epsilon=0.01$

$\alpha=10,\epsilon=0.1$

$\alpha=10,\epsilon=1$

$\alpha=10,\epsilon=10$

$\alpha=1,\epsilon=0.01$

$\alpha=1,\epsilon=0.1$

$\alpha=1,\epsilon=1$

$\alpha=1,\epsilon=10$

$\alpha=0.5,\epsilon=0.01$

$\alpha=0.5,\epsilon=0.1$

$\alpha=0.5,\epsilon=1$

$\alpha=0.5,\epsilon=10$

$\alpha=0.2,\epsilon=0.01$

$\alpha=0.2,\epsilon=0.1$

$\alpha=0.2,\epsilon=1$

$\alpha=0.2,\epsilon=10$

$\alpha=0.15,\epsilon=0.01$

$\alpha=0.15,\epsilon=0.1$

$\alpha=0.15,\epsilon=1$

$\alpha=0.15,\epsilon=10$

$\alpha=0.1,\epsilon=0.01$

$\alpha=0.1,\epsilon=0.1$

$\alpha=0.1,\epsilon=1$

$\alpha=0.1,\epsilon=10$

$\alpha=0.05,\epsilon=0.01$

$\alpha=0.05,\epsilon=0.1$

$\alpha=0.05,\epsilon=1$

$\alpha=0.05,\epsilon=10$

Figure 25: Results for DENTS on the 20-chain ($D=20$, $R_{f}=1.0$). The decay
function was set to $\beta(m)=\alpha$, so that DENTS mimics MENTS search
policy. Figure 26: Results for DENTS on the 20-chain ($D=20$, $R_{f}=1.0$),
with $\alpha=0.5$, $\beta(m)=10/\log(e+m)$ and $\epsilon=0.01$.

####  D.2.2 Parameter sensitivity in Frozen Lake

We also ran MENTS, RENTS, TENTS, BTS and DENTS with a variety of temperatures
on the 8x8 Frozen Lake environment given in Figure 6(a). Again, we set
$\beta(m)=\alpha/\log(e+m)$ for the decay function in DENTS, and we used an
exploration parameter of $\epsilon=1$ for all of the algorithms.

In Figures 27 and 29 we can see that MENTS and TENTS take the scenic route to
the goal state for medium temperatures, where the reward for reaching the goal
is still significant, but they can obtain more entropy reward by wondering
around the gridworld for a while first. For higher temperatures they
completely ignore the goal state, opting to rather maximise policy entropy.
Interestingly, RENTS in Figure 28 fared better than MENTS and TENTS and never
really ignored the goal state at the temperatures that we considered.

In contrast, both BTS and DENTS were agnostic to the temperature parameter in
this environment (with $\epsilon=1$) and were always able to find the goal
state. We include the plots for BTS and DENTS in all of Figures 27, 29 and 28
for reference and as a comparison for MENTS, RENTS and TENTS.

(a) $\alpha=1$

(b) $\alpha=0.5$

(c) $\alpha=0.1$

(d) $\alpha=0.05$

(e) $\alpha=0.01$

(f) $\alpha=0.005$

Figure 27: MENTS with a variety of temperatures on an 8x8 Frozen Lake
environment. BTS and DENTS are included for reference.

(a) $\alpha=1$

(b) $\alpha=0.5$

(c) $\alpha=0.1$

(d) $\alpha=0.05$

(e) $\alpha=0.01$

(f) $\alpha=0.005$

Figure 28: RENTS with a variety of temperatures on an 8x8 Frozen Lake
environment. BTS and DENTS are included for reference.

(a) $\alpha=1$

(b) $\alpha=0.5$

(c) $\alpha=0.1$

(d) $\alpha=0.05$

(e) $\alpha=0.01$

(f) $\alpha=0.005$

Figure 29: TENTS with a variety of temperatures on an 8x8 Frozen Lake
environment. BTS and DENTS are included for reference.

###  D.3 Grid world hyper-parameter search and additional results

To select hyper-parameters for the experiments detailed in Section 5.1, we
performed a hyper-parameter search. The search was run on the 8x12 Frozen Lake
environment from Figure 6(b), and the results in Section 5.1 were run on the
8x12 Frozen Lake envrionment from Figure 6(c). For the Sailing problem, we
performed the search using an initial wind direction of North, and the result
in Section 5 used an initial wind direction of South-East.

To avoid the search space from becoming too large, we set some parameters
manually. A good rule of thumb for initial values is to assure that
$Q^{\text{init}}_{\text{sft}}(s,a)<Q^{*}_{\textnormal{sft}}(s,a)$ and
$Q^{\text{init}}(s,a)<Q^{*}(s,a)$. Explicitly this means that an initial value
of zero is not a good choice for the Sailing problem, as rewards are negative
(i.e. it has costs). In the Sailing environment, we actually set the initial
values to $-200$, so that they were equal to the lowest possible return from a
trial (the trial length was set to $50$, and an agent can incur a cost of at
most $-4$ per timestep). To simplify the search space, we initially set the
decay function in DENTS to $\beta(m)=\alpha/\log(e+m)$ and tune it after.

For the remaining parameters, we considered all combinations of the following
values:

  * •

UCT Bias: prst, 100.0, 10.0, 1.0, 0.1;

  * •

MENTS exploration coefficient: 2.0, 1.0, 0.3, 0.1, 0.03, 0.01;

  * •

Temperature: 100.0, 10.0, 1.0, 0.1, 0.01, 0.001;

  * •

HMCTS UCT budget: 100000, 30000, 10000, 3000, 1000, 300, 100, 30, 10.

Where a UCT bias of prst refers to the adaptive bias introduced by Keller and
Eyerich prst, and ‘temperature’ refers to the relevant temperature for the
algorithm (i.e. search temperature in BTS and DENTS, and the temperature for
Shannon/Relative/Tsallis entropy in MENTS/RENTS/DENTS). After that search, for
DENTS we considered the decay functions of the form
$\beta(m)=\beta_{\text{init}}/\log(e+m)$ and considered the following values:

  * •

DENTS initial entropy temperature ($\beta_{\text{init}}$): 100.0, 10.0, 1.0,
0.1.

The final set of hyperparameters is given in Tables 3 and 4, which were used
in the gridworld experiments in Section 5.1. Not included in the tables: prst
was selected for the UCT bias in both Frozen Lake and the Sailing problem.

Algorithm | Exploration Parameter ($\epsilon$) | Temperature ($\alpha$) | Initial Values ($Q^{\text{init}}$, $Q^{\text{init}}_{\text{sft}}$)
---|---|---|---
MENTS | 1.0 | 0.001 | 0
RENTS | 2.0 | 0.001 | 0
TENTS | 1.0 | 0.001 | 0
BTS | 2.0 | 0.1 | 0
DENTS | 1.0 | 0.1 | 0
Table 3: Final hyperparameters used for Frozen Lake in Section 5.1. Not included in the table: prst was selected for the bias in UCT, prst was selected for the bias and 3000 for the UCT budget in HMCTS and $\beta_{\text{init}}=1.0$ was selected as the initial entropy temperature for DENTS.  Algorithm | Exploration Parameter ($\epsilon$) | Temperature ($\alpha$) | Initial Values ($Q^{\text{init}}$, $Q^{\text{init}}_{\text{sft}}$)
---|---|---|---
MENTS | 1.0 | 10.0 | -200
RENTS | 1.0 | 10.0 | -200
TENTS | 2.0 | 0.1 | -200
BTS | 1.0 | 10.0 | -200
DENTS | 1.0 | 10.0 | -200
Table 4: Final hyperparameters used for the Sailing Problem in Section 5.1.
Not included in the table: prst was selected for the bias in UCT, prst was
selected for the bias and 30 for the UCT budget in HMCTS and
$\beta_{\text{init}}=10.0$ was selected as the initial entropy temperature for
DENTS.

###  D.4 DENTS with a constant $\beta$

To empirically demonstrate that DENTS search policy can mimic the search
policy of MENTS, we ran DENTS with $\alpha=1.0,\beta(m)=\alpha$ on the
10-chain environment, and compared it to MENTS with $\alpha=1.0$. We also ran
DENTS with $\alpha=0.001,\beta(m)=\alpha$ in the Frozen Lake environment, and
compared it to MENTS with $\alpha=0.001$ which is what was selected in the
hpyerparameter search (Appendix D.3). Results are given in Figure 30. Note
that in the 10-chain, only MENTS has a dip in performance initially, which is
due to the two algorithms using different recommendation policies.

(a) 10-chain.

(b) Frozen Lake.

Figure 30: Comparing DENTS with MENTS, by setting
$\beta_{\text{DENTS}}(m)=\alpha_{\text{MENTS}},\alpha_{\text{DENTS}}=\alpha_{\text{MENTS}}$,
where $\alpha_{\text{MENTS}}$ is the temperature used for MENTS, and
$\alpha_{\text{DENTS}},\beta_{\text{DENTS}}$ are the temperatures used by
DENTS.

###  D.5 Additional Go details, results and discussion

Recall from Appendix C.2 that we initialised values with the neural networks
as $Q^{\text{init}}(s,a)=\log\tilde{\pi}(a|s)+B$ and
$V^{\text{init}}(s)=\tilde{V}(s)$, where $B$ is a constant (adapted from Xiao
et al. xiao2019maximum ). For these experiments we set a value of
$B=\frac{-1}{|\mathcal{A}|}\sum_{a\in\mathcal{A}}\log\tilde{\pi}(a|s)$.
Initialising the values in such a way tends to lead to the values of
$Q^{\text{init}}(s,a)$ being in the range $[-20,20]$, to account for this, we
scaled the results of the game to $100$ and $-100$, which means that any
parameters selected are about $100$ times larger than they would be if we had
not have used this scaling.

In these experiments we used a recommendation policy that recommends the
action that was sampled the most, i.e. $\psi(s)=\max_{a}N(s,a)$, as this tends
to be more robust to any noise from neural network outputs.

To select each parameter we ran a round robin tournament where we varied the
value of one parameter. The agent that won the most games was used to select
the parameter moving forward, and in the case of a tie we used the agent which
won the most games. If the winning agent had the largest or smallest value,
then we ran another tournament adjusting the values accordingly.

We tuned all of these algorithms using the game of 9x9 Go with a komi of 6.5,
and giving each algorithm 2.5 seconds per move. For our final results we used
the same parameters on 19x19 Go with a komi of 7.5, giving each algorithm 5.0
seconds per move.

####  D.5.1 Parameter selection for Go and supplimentary results

In this section we work through the process used to select parameters for the
Go round robin tournament used in Section 5.2. Predominantly parameters were
chosen by playing out games of Go between agents. The parameters used for PUCT
were copied from Kata Go and Alpha Go Zero katago,silver2017mastering.

Initially we set the values of $\epsilon,\epsilon_{\tilde{\lambda}}$ to
$0.03,1.0$. In Tables 5 and 6 we give results of tuning the search temperature
for BTS and AR-BTS. For AR-BTS we tried different values of
$\alpha_{\text{init}}$ in $\alpha(m)=\alpha_{\text{init}}/\sqrt{m}$.

Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 3-12 | 4-11 | 3-12 | 1-14
1 | 14-1 | - | 8-7 | 9-6 | 7-8
0.3 | 14-1 | 8-7 | - | 7-8 | 11-4
0.1 | 15-0 | 11-4 | 9-6 | - | 9-6
0.03 | 14-1 | 8-7 | 4-11 | 8-7 | -
Table 5: Results for round robin to select the temperature parameter $\alpha$ for BTS. The value of 0.1 won all four of its matches so was selected.  Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 7-8 | 9-6 | 12-3 | 12-3
1 | 15-0 | - | 12-3 | 15-0 | 15-0
0.3 | 13-2 | 11-4 | - | 14-1 | 15-0
0.1 | 14-1 | 10-5 | 11-4 | - | 15-0
0.03 | 13-2 | 5-10 | 8-7 | 13-2 | -
Table 6: Results for round robin to select the temperature parameter
$\alpha_{\text{init}}$ for AR-BTS. The value of 1.0 won all four of its
matches so was selected.

We then tuned the weighting of the prior policy $\epsilon_{\tilde{\lambda}}$.
In Tables 7 and 8 we give results of tuning the prior policy weight for BTS
and AR-BTS.

Black \White | 10 | 5 | 3 | 2 | 1
---|---|---|---|---|---
10 | - | 5-10 | 3-12 | 1-14 | 3-12
5 | 14-1 | - | 12-3 | 11-4 | 11-4
3 | 15-0 | 15-0 | - | 12-3 | 12-3
2 | 15-0 | 12-3 | 12-3 | - | 10-5
1 | 15-0 | 14-1 | 12-3 | 9-6 | -
Table 7: Results for round robin to select the weighting of the prior policy $\epsilon_{\tilde{\lambda}}$ for BTS. The value of 2.0 won the most matches so was selected.  Black \White | 3 | 2 | 1 | 0.75 | 0.5
---|---|---|---|---|---
3 | - | 14-1 | 9-6 | 13-2 | 14-1
2 | 12-3 | - | 12-3 | 15-0 | 10-5
1 | 12-3 | 13-2 | - | 11-4 | 13-2
0.75 | 11-4 | 10-5 | 12-3 | - | 14-1
0.5 | 11-4 | 13-2 | 9-6 | 7-8 | -
Table 8: Results for round robin to select the weighting of the prior policy
$\epsilon_{\tilde{\lambda}}$ for AR-BTS. The value of 1.0 won the most matches
so was selected.

Following that, we then tuned MENTS exploration parameter $\epsilon$. In
Tables 9 and 10 we give results of tuning the exploration parameter for BTS
and AR-BTS. Although we selected the lowest value we tried here, we note that
with such a value that a random action would have been sampled very few times,
so the result of the hyperparameter selection was essentially that $\epsilon$
should be as low as possible.

Black \White | 0.1 | 0.03 | 0.01 | 0.003 | 0.001
---|---|---|---|---|---
0.1 | - | 12-3 | 10-5 | 8-7 | 7-8
0.03 | 9-6 | - | 8-7 | 13-2 | 12-3
0.01 | 11-4 | 9-6 | - | 7-8 | 12-3
0.003 | 13-2 | 9-6 | 11-4 | - | 11-4
0.001 | 12-3 | 11-4 | 8-7 | 9-6 | -
Table 9: Results for round robin to select the exploration parameter $\epsilon$ for BTS. The value of 0.003 won the most matches so was selected.  Black \White | 0.1 | 0.03 | 0.01 | 0.003 | 0.001
---|---|---|---|---|---
0.1 | - | 12-3 | 14-1 | 12-3 | 13-2
0.03 | 15-0 | - | 11-4 | 14-1 | 14-1
0.01 | 15-0 | 11-4 | - | 13-2 | 13-2
0.003 | 15-0 | 14-0 | 14-1 | - | 13-2
0.001 | 14-1 | 14-1 | 14-1 | 15-0 | -
Table 10: Results for round robin to select the exploration parameter
$\epsilon$ for BTS. The value of 0.001 won the most matches so was selected.

Then we tuned the (fixed and constant) search temperatures for MENTS, AR-
MENTS, RENTS, AR-RENTS, TENTS and AR-TENTS in tables 11, 12,13, 14,15 and 16.

Black \White | 0.3 | 0.1 | 0.03 | 0.01 | 0.003
---|---|---|---|---|---
Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
3 | - | 9-6 | 9-6 | 11-4 | 10-5
1 | 11-4 | - | 11-4 | 9-6 | 10-5
0.3 | 9-6 | 7-8 | - | 11-4 | 6-9
0.1 | 4-11 | 4-11 | 0-15 | - | 4-11
0.03 | 2-13 | 2-13 | 0-15 | 0-15 | -
Table 11: Results for round robin to select the temperature parameter $\alpha$ for MENTS. The value of 1.0 won the most matches so was selected.  Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 2-13 | 1-14 | 3-12 | 5-10
1 | 14-1 | - | 11-4 | 13-2 | 15-0
0.3 | 15-0 | 12-3 | - | 12-3 | 14-1
0.1 | 15-0 | 9-6 | 9-6 | - | 15-0
0.03 | 15-0 | 8-7 | 9-6 | 14-1 | -
Table 12: Results for round robin to select the temperature parameter $\alpha$ for AR-MENTS. The value of 0.3 won the most matches so was selected.  Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 7-8 | 9-6 | 10-5 | 9-6
1 | 13-2 | - | 12-3 | 11-4 | 12-3
0.3 | 10-5 | 11-4 | - | 10-5 | 5-10
0.1 | 3-12 | 2-13 | 1-14 | - | 3-12
0.03 | 3-12 | 0-15 | 0-15 | 0-15 | -
Table 13: Results for round robin to select the temperature parameter $\alpha$ for RENTS. The value of 1.0 won the most matches so was selected.  Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 4-11 | 2-13 | 9-6 | 3-12
1 | 15-0 | - | 12-3 | 13-2 | 13-2
0.3 | 15-0 | 13-2 | - | 14-1 | 15-0
0.1 | 15-0 | 10-5 | 13-2 | - | 15-0
0.03 | 13-2 | 13-2 | 12-3 | 14-1 | -
Table 14: Results for round robin to select the temperature parameter $\alpha$ for AR-RENTS. The value of 0.3 won the most matches so was selected.  Black \White | 300 | 100 | 30 | 10 | 3
---|---|---|---|---|---
300 | - | 3-12 | 5-10 | 7-8 | 9-6
100 | 6-9 | - | 9-6 | 12-3 | 12-3
30 | 8-7 | 7-8 | - | 9-6 | 11-4
10 | 0-15 | 2-13 | 2-13 | - | 6-9
3 | 1-14 | 1-14 | 2-13 | 5-10 | -
Table 15: Results for round robin to select the temperature parameter $\alpha$ for TENTS. The value of 1.0 won the most matches so was selected.  Black \White | 30 | 10 | 3 | 1 | 0.3
---|---|---|---|---|---
30 | - | 14-1 | 15-0 | 14-1 | 14-1
10 | 15-0 | - | 13-2 | 15-0 | 15-0
3 | 15-0 | 14-1 | - | 14-1 | 15-0
1 | 15-0 | 15-0 | 14-1 | - | 15-0
0.3 | 15-0 | 15-0 | 14-1 | 15-0 | -
Table 16: Results for round robin to select the temperature parameter $\alpha$
for AR-TENTS. The value of 3.0 won the most matches so was selected.

Finally, we considered entropy temperatures of the form
$\beta(m)=\beta_{\text{init}}/\sqrt{m}$ for DENTS and AR-DENTS, and tuned the
value of $\beta_{\text{init}}$, in Tables 17 and 18 for DENTS and AR-DENTS
respectively.

Black \White | 0.1 | 0.03 | 0.01 | 0.003 | 0.001
---|---|---|---|---|---
0.1 | - | 10-5 | 12-3 | 8-7 | 11-4
0.1 | 13-2 | - | 11-4 | 13-2 | 10-5
0.1 | 12-3 | 11-4 | - | 10-5 | 11-4
0.1 | 7-8 | 13-2 | 13-2 | - | 10-5
0.1 | 13-2 | 13-2 | 11-4 | 11-4 | -
Table 17: Results for round robin to select the initial entropy temperature $\beta_{\text{init}}$ for BTS. The value of 0.3 won the most matches so was selected.  Black \White | 3 | 1 | 0.3 | 0.1 | 0.03
---|---|---|---|---|---
3 | - | 11-4 | 12-3 | 12-3 | 14-1
1 | 13-2 | - | 11-4 | 13-2 | 13-2
0.3 | 14-1 | 13-2 | - | 13-2 | 14-1
0.1 | 12-3 | 12-3 | 12-3 | - | 11-4
0.03 | 12-3 | 13-2 | 13-2 | 14-1 | -
Table 18: Results for round robin to select the initial entropy temperature
$\beta_{\text{init}}$ for BTS. The value of 0.3 won the most matches so was
selected.

After tuning all of the algorithms, we compared each algorithm to their AR
version in table LABEL:tab:y010, and the AR versions universally outperformed
their counterparts. We used all of the selected parameters in 19x19 Go to run
our final experiments given in Table 1.

Black \White | MENTS | AR-MENTS | BTS | AR-BTS | DENTS | AR-DENTS
---|---|---|---|---|---|---
MENTS | - | 0-25 |  |  |  |
AR-MENTS | 25-0 | - |  |  |  |
BTS |  |  | - | 16-9 |  |
AR-BTS |  |  | 22-3 | - |  |
DENTS |  |  |  |  | - | 21-4
AR-DENTS |  |  |  |  | 22-3 | -
Black \White | RENTS | AR-RENTS | TENTS | AR-TENTS |  |
RENTS | - | 2-23 |  |  |  |
AR-RENTS | 24-1 | - |  |  |  |
TENTS |  |  | - | 8-17 |  |
AR-TENTS |  |  | 23-2 | - |  |
Table 19: Results for the matches of each algorithm against its AR version.

Finally, we also ran AR-BTS against Kata Go directly limiting each algorithm
to 1600 trials. KataGo beat AR-BTS by 31-19, confirming that the aditional
exploration is outweighed by the information contained in the neural networks,
and in Go the Boltzmann search algorithms gain their advantage via the Alias
method and being able to run more trials quickly.

##  Appendix E Proofs

This proof section is structured as follows:

  1. 1.

First, in Section E.1 we revisit MCTS as a stochastic process, defining some
additional notation that was not useful in the main body of the paper, but
will be for the following proofs;

  2. 2.

Second, in Section E.2 we introduce preliminary results, that will be useful
building blocks for proofs in later Theorems;

  3. 3.

Third, in Section E.3 we show some general results about soft values that will
also be useful later;

  4. 4.

Fourth, in Section E.4 simple regret is then revisited, and we show that any
bounds on the simple regret of a policy are equivalent to showing bounds on
the simple regret of an action;

  5. 5.

Fifth, in Section E.5 we show in a general way, that if a value function
admits a concentration inequality, then the corresponding Q-value function
admits a similar concentration inequality;

  6. 6.

Sixth, in Section E.6 we show concentration inequalities for MENTS about the
optimal soft values, and give bounds on the simple regret of MENTS, provided
the temperature parameter is sufficiently small;

  7. 7.

Seventh, in Sections E.7 and E.8 we also provide concentration inequalities
around the optimal standard values for BTS and DENTS, and give simple regret
bounds, irrespective of the temperature paramters;

  8. 8.

Finally, in Section E.9 we consider results that are relavant for the
algorithms using average returns from Section B.

###  E.1 Revisiting the MCTS stochastic process

In this subsection we recall the relevant details of the MCTS stochastic
process, and introduce additional notation that will be useful in the proofs
that were not necessary in the main paper. We will also recall the details for
the UCT, MENTS, BTS and DENTS processes. We will use the phrase any Boltzmann
MCTS process to refer to any one of the MENTS, BTS and DENTS processes. In
particular, we index the (Q-)values with the number visits to the relevant
node.

An MCTS process begins with a search tree $\mathcal{T}^{0}=\\{s_{0}\\}$ that
contains only the root node/initial state. Let
$\tau^{n}=(s_{0}^{n},a_{0}^{n},...,s_{h-1}^{n},a_{h-1}^{n},s_{h}^{n})$ be a
random variable for the $n$th trajectory or trial, where
$s_{0}^{n},...,s_{h-1}^{n}\in\mathcal{T}^{n-1}$ and
$s_{h}^{n}\not\in\mathcal{T}^{n-1}$ (or $h=H$), and where actions are selected
or sampled using $\pi^{n}$ the search policy for the $n$th trial. A new node
is added to the search tree
$\mathcal{T}^{n}=\\{s_{h}^{n}\\}\cup\mathcal{T}^{n-1}$. (Q-)Value estimates
are kept at each node in the tree, and new values are initialised using the
functions $V^{\text{init}}(s)$ and $Q^{\text{init}}(s,a)$, which are typically
implemented as a constant value, using a rollout policy or using a neural
network. Finally, the (Q-)value estimates are updated in a backup phase.

In the following, it will be useful to write $N(s)$ the number of times state
$s$ was visited, and $N(s,a)$ the number of times action $a$ was selected from
state $s$ as a sum of indicator random variables. Let $T(s_{t})$ (and
$T(s_{t},a_{t})$) be the set of trajectory indices that $s_{t}$ was visited on
(and action $a_{t}$ selected), that is:

$\displaystyle T(s_{t})$ $\displaystyle=\\{i|s^{i}_{t}=s_{t}\\}$ (63)
$\displaystyle T(s_{t},a_{t})$
$\displaystyle=\\{i|s^{i}_{t}=s_{t},a^{i}_{t}=a_{t}\\}.$ (64)

This allows the counts $N(s_{t}),$ $N(s_{t},a_{t})$ and $N(s_{t+1})$ (with
$s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})$) to be written as sums of indicator
random variables:

$\displaystyle
N(s_{t})=\sum_{i=1}^{n}\mathbbm{1}[s^{i}_{t}=s_{t}]=|T(s_{t})|,$ (65)
$\displaystyle
N(s_{t},a_{t})=\sum_{i=1}^{n}\mathbbm{1}[s^{i}_{t}=s_{t},a^{i}_{t}=a_{t}]=|T(s_{t},a_{t})|,$
(66) $\displaystyle N(s_{t},a_{t})=\sum_{i\in
T(s_{t})}\mathbbm{1}[a^{i}_{t}=a_{t}],$ (67) $\displaystyle
N(s_{t+1})=\sum_{i\in T(s_{t},a_{t})}\mathbbm{1}[s^{i}_{t+1}=s_{t+1}].$ (68)

Additionally, we make the assumption that for any two states
$s,s^{\prime}\in\mathcal{S}$ that $s=s^{\prime}$ if and only if the
trajectories leading to them are identical. This assumption is purely to
simplify notation, so that nodes in the tree have a one-to-one correspondence
with states (or state-action pairs).

##### The UCT process.

The UCT search policy can be defined as:

$\displaystyle\pi_{\textnormal{UCT}}^{n}(s_{t})$
$\displaystyle=\max_{a\in\mathcal{A}}\text{UCB}^{n}(s_{t},a),$ (69)
$\displaystyle\text{UCB}^{n}(s_{t},a)$
$\displaystyle=\begin{cases}\infty&\text{if }N(s_{t},a)=0\\\
\bar{Q}^{N(s_{t},a)}(s_{t},a)+c\sqrt{\frac{\log
N(s_{t})}{N(s_{t},a)}}&\text{if }N(s_{t},a)>0\end{cases}$ (70)

where, after $n$ trials, $\bar{Q}^{N(s,a)}(s,a)$ is the empirical estimate of
the value at node $(s,a)$, where action $a$ has been selected $N(s,a)$ from
state $s$. The backup consists of updating empirical estimates for
$t=h-1,...,0$:

$\displaystyle\bar{V}^{N(s_{t})+1}(s_{t})$
$\displaystyle=\bar{V}^{N(s_{t})}(s_{t})+\frac{\bar{R}(t)-\bar{V}^{N(s_{t})}(s_{t})}{N(s_{t})+1},$
(71) $\displaystyle\bar{Q}^{N(s_{t},a_{t})+1}(s_{t},a_{t})$
$\displaystyle=\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})+\frac{\bar{R}(t)-\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})}{N(s_{t},a_{t})+1},$
(72)

where $\bar{R}(t)=V^{\text{init}}(s_{h})+\sum_{i=t}^{h-1}R(s_{i},a_{i})$, and
values are initialised as $\bar{V}^{1}(s)=V^{\text{init}}(s)$ and
$\bar{Q}^{0}(s,a)=0$.

##### The MENTS process.

The policy for the MENTS process at state $s$ on the $n$th trial is:

$\displaystyle\pi^{n}_{\text{MENTS}}(a|s)=(1-\lambda_{s})\exp\left(\left(\hat{Q}^{N(s,a)}_{\textnormal{sft}}(s,a)-\hat{V}^{N(s)}_{\textnormal{sft}}(s)\right)/\alpha\right)+\frac{\lambda_{s}}{|\mathcal{A}|},$
(73)

where $\lambda_{s}=\min(1,\epsilon/\log(e+N(s)))$, $\epsilon\in(0,\infty)$.
The estimated soft values are computed using the backups for $t=h-1,...,0$:

$\displaystyle\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})$
$\displaystyle=\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a)/\alpha\right),$
(74) $\displaystyle\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$
$\displaystyle=R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s,a)}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}^{N(s^{\prime})}_{\textnormal{sft}}(s^{\prime})\right).$
(75)

The soft (Q-)values are initialised as
$\hat{V}^{1}_{\textnormal{sft}}(s)=V^{\text{init}}(s)$ and
$\hat{Q}^{0}_{\textnormal{sft}}(s,a)=Q^{\text{init}}_{\text{sft}}(s)$
(typically $Q^{\text{init}}_{\text{sft}}(s)=0$).

##### The DENTS process.

Let $\beta:\mathbb{R}\rightarrow[0,\infty)$ be a bounded function. The policy
for the DENTS process at state $s$ on the $n$th trial is:

$\displaystyle\pi^{n}_{\text{DENTS}}(a|s)=(1-\lambda_{s})\rho^{n}(a|s)+\frac{\lambda_{s}}{|\mathcal{A}|},$
(76)

where $\lambda_{s}=\min(1,\epsilon/\log(e+N(s)))$, $\epsilon\in(0,\infty)$ and
where $\rho$ is given by:

$\displaystyle\rho^{n}_{\text{DENTS}}(a|s)\propto\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)+\beta(N(s))\mathcal{H}_{Q}^{N(s,a)}(s,a)\right)\right).$
(77)

The Bellman values and entropy values are computed using the backups for
$t=h-1,...,0$:

$\displaystyle\hat{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$
$\displaystyle=R(s_{t},a_{t})+\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\left(\frac{N(s^{\prime})}{N(s_{t},a_{t})}\hat{V}^{N(s^{\prime})}(s^{\prime})\right),$
(78) $\displaystyle\hat{V}^{N(s_{t})}(s_{t})$
$\displaystyle=\max_{a\in\mathcal{A}}\hat{Q}^{N(s_{t},a)}(s_{t},a),$ (79)
$\displaystyle\mathcal{H}_{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$
$\displaystyle=\sum_{s^{\prime}\in\textnormal{Succ}(s_{t},a_{t})}\frac{N(s^{\prime})}{N(s_{t},a_{t})}\mathcal{H}_{V}^{N(s^{\prime})}(s^{\prime}),$
(80) $\displaystyle\mathcal{H}_{V}^{N(s_{t})}(s_{t})$
$\displaystyle=\mathcal{H}(\pi^{n}_{\text{DENTS}}(\cdot|s_{t}))+\sum_{a\in\mathcal{A}}\pi^{n}_{\text{DENTS}}(a_{t}|s_{t})\mathcal{H}_{Q}^{N(s_{t},a_{t})}(s_{t},a_{t}),$
(81)

The (Q-)values are initialised as $\hat{V}^{1}(s)=V^{\text{init}}(s)$ and
$\hat{Q}^{0}(s,a)=Q^{\text{init}}_{\text{sft}}(s)$ (typically
$Q^{\text{init}}_{\text{sft}}(s)=0$). The entropy values are initialised as
$\mathcal{H}_{Q}^{0}(s,a)=0$ and
$\mathcal{H}_{V}^{1}(s)=\mathcal{H}(\pi^{n}_{\text{DENTS}}(\cdot|s_{t}))$,
where the node for $s$ is created on the $n$th trial.

Because we need to reason about $\pi^{n}_{\text{DENTS}}$, and subsequently
$\rho^{n}_{\text{DENTS}}$, we give the exact form of
$\rho^{n}_{\text{DENTS}}$:

$\displaystyle\rho^{n}_{\text{DENTS}}(a|s)$
$\displaystyle=\frac{\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)+\beta(N(s))\mathcal{H}_{Q}^{N(s,a)}(s,a)\right)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a^{\prime})}(s,a^{\prime})+\beta(N(s))\mathcal{H}_{Q}^{N(s,a^{\prime})}(s,a^{\prime})\right)\right)}.$
(82)

Let $V_{\rho}^{N(s)}(s)$ be defined as the value:

$\displaystyle
V_{\rho}^{N(s)}(s)=\alpha\log\left[\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a^{\prime})}(s,a^{\prime})+\beta(N(s))\mathcal{H}_{Q}^{N(s,a^{\prime})}(s,a^{\prime})\right)\right)\right],$
(83)

and notice that the value of $\exp(V_{\rho}^{N(s)}(s)/\alpha)$ is equal to the
denominator in Equation (82), and so by rearranging we can write
$\rho^{n}_{\text{DENTS}}$ as

$\displaystyle\rho^{n}_{\text{DENTS}}(a|s)$
$\displaystyle=\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)+\beta(N(s))\mathcal{H}_{Q}^{N(s,a)}(s,a)-V_{\rho}^{N(s)}(s)\right)\right),$
(84)

and subsequently, we can write

$\displaystyle\pi^{n}_{\text{DENTS}}(a|s)=(1-\lambda_{s})\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)+\beta(N(s))\mathcal{H}_{Q}^{N(s,a)}(s,a)-V_{\rho}^{N(s)}(s)\right)\right)+\frac{\lambda_{s}}{|\mathcal{A}|}.$
(85)

##### The BTS process.

The BTS process is a special case of the DENTS process when $\beta(m)=0$ for
all $m\in\mathbb{N}$.

###  E.2 Preliminaries

Now we will provide lemmas are useful to avoid having to repeat the same
argument in multiple proofs. In the following it will be useful to know that
any action at any node in any MCTS process, for any number of trials, there is
a minimum positive probability that it is chosen.

######  Lemma E.1.

Consider any Boltzmann MCTS process. There exists some
$\pi^{\textnormal{min}}>0$, such that for any state $s_{t}\in\mathcal{S}$, for
all $a_{t}\in\mathcal{A}$ and any number of trials $n\in\mathbb{N}$ we have
$\pi^{n}(a_{t}|s_{t})>\pi^{\textnormal{min}}$.

###### Proof outline.

Firstly, we consider the case of the MENTS process. Define the $Q^{\min}$
function as follows:

$\displaystyle
Q^{\min}(s_{t},a_{t})=\min_{s_{t+1},a_{t+1},...,s_{H},a_{H}}\sum_{i=t}^{H}\min(0,Q^{\text{init}}_{\text{sft}}(s_{i}),R(s_{i},a_{i})).$
(86)

And define the $V^{\max}$ function as:

$\displaystyle V^{\max}(s_{t})$