Online Learning of Decision Trees with Thompson Sampling

Ayman Chaouki Jesse Read Albert Bifet

LIX, Ecole Polytechnique, IP Paris AI Institute, University of Waikato LIX,
Ecole Polytechnique, IP Paris AI Institute, University of Waikato LTCI,
Télécom Paris, IP Paris

###### Abstract

Decision Trees are prominent prediction models for interpretable Machine
Learning. They have been thoroughly researched, mostly in the batch setting
with a fixed labelled dataset, leading to popular algorithms such as C4.5, ID3
and CART. Unfortunately, these methods are of heuristic nature, they rely on
greedy splits offering no guarantees of global optimality and often leading to
unnecessarily complex and hard-to-interpret Decision Trees. Recent
breakthroughs addressed this suboptimality issue in the batch setting, but no
such work has considered the online setting with data arriving in a stream. To
this end, we devise a new Monte Carlo Tree Search algorithm, Thompson Sampling
Decision Trees (TSDT), able to produce optimal Decision Trees in an online
setting. We analyse our algorithm and prove its almost sure convergence to the
optimal tree. Furthermore, we conduct extensive experiments to validate our
findings empirically. The proposed TSDT outperforms existing algorithms on
several benchmarks, all while presenting the practical advantage of being
tailored to the online setting.

##  1 INTRODUCTION

Interpretable Machine Learning is crucial in sensitive domains, like medicine,
where high-stakes decisions have to be justified. Due to their extraction of
simple decision rules, Decision Trees (DTs) are very popular in this context.
Unfortunately, finding the optimal DT is NP-complete (Laurent and Rivest,,
1976), and for this reason, popular batch algorithms greedily construct a DT
by splitting its leaves according to some local gain metric, such approach is
used in ID3 (Quinlan,, 1986), C4.5 (Quinlan,, 2014) and CART (Breiman et al.,,
1984) to name a few. Due to this heuristic nature, these approaches offer no
optimality guarantees. In fact, they often lead to suboptimal DTs that are
unnecessarily complex and hard to interpret, contradicting the main motivation
behind DTs.

In many modern applications, data is supplied through a stream rather than a
fixed data set, this renders most batch algorithms obsolete, which led to the
emergence of the data stream (or online) learning paradigm (Bifet and Kirkby,,
2009). The classic batch DT algorithms are ill-suited for online learning
since they calculate a splitting gain metric on a whole data set. In response,
Domingos and Hulten, (2000) introduced the VFDT algorithm, which constructs
DTs in an online fashion. VFDT estimates the gain of each split using a
statistical test based on Hoeffding’s inequality. This approach yielded a
principled algorithm and laid the foundation for subsequent developments
(Hulten et al.,, 2001; Bifet and Gavalda,, 2009; Manapragada et al.,, 2018),
with advances primarily focusing on improving the quality of the statistical
tests (Jin and Agrawal,, 2003; Rutkowski et al.,, 2012, 2013). Much like their
batch counterparts, these online methods are heuristic in nature, and
consequently, they are susceptible to the suboptimality issue.

In this work, we propose a method that circumvents these limitations, yielding
an online algorithm proven to converge to the optimal DT. We consider online
classification problems with categorical attributes, for which we seek the
optimal DT balancing between the accuracy and the number of splits. To achieve
this, we frame the problem as a Markov Decision Process (MDP) where the
optimal policy leads to the optimal DT. We solve this MDP with a novel Monte
Carlo Tree Search (MCTS) algorithm that we call Thompson Sampling Decision
Trees (TSDT). TSDT employs a Thompson Sampling policy that converges almost
surely to the optimal policy. In our experiments, we highlight the limitations
of traditional greedy online DT methods, such as VFDT and EFDT (Manapragada et
al.,, 2018), and demonstrate how TSDT effectively circumvents these
shortcomings. Due to the lack of literature on optimal online DTs, we compare
TSDT with recent successful batch optimal DT algorithms by feeding benchmark
datasets to TSDT as streams, TSDT clearly outperforms DL8.5 (Aglin et al.,,
2020) and matches or surpasses the performance of OSDT (Hu et al.,, 2019).

##  2 RELATED WORK

In the batch setting, the suboptimality issue of DTs has been the subject of
multiple research papers focused mainly on mathematical programming, see
(Bennett,, 1994; Bennett and Blue,, 1996; Norouzi et al.,, 2015; Bertsimas and
Dunn,, 2017; Verwer and Zhang,, 2019). These methods optimise internal splits
within a fixed DT structure, making the problem more manageable but
potentially missing the optimal DT. Recently, branch and bound methods were
proposed to mitigate this issue and yielded the DL8.5 algorithm (Aglin et
al.,, 2020) and OSDT (Hu et al.,, 2019) among others. A subsequent algorithm,
GOSDT (Lin et al.,, 2020), generalises OSDT to other objective functions
including F-score, AUC and partial area under the ROC convex hull. However,
these methods are limited to binary attributes, necessitating a preliminary
binary encoding of the data. Moreover, the choice of this binary encoding may
significantly influence the complexity of the solution, as demonstrated in our
experiments. All the aforementioned methods operate solely in the batch
learning paradigm, lacking a straightforward extension to the online setting.

The closest work to ours is perhaps (Nunes et al.,, 2018) since the authors
use MCTS, see (Browne et al.,, 2012) for a survey about MCTS. Nunes et al.,
(2018) define a rollout policy that completes the selected DT with C4.5 on an
induction set, then it estimates the value of the selected DT by evaluating
its performance on a validation set. This approach does not differentiate
between DTs of different complexities, in fact, the authors rely on a custom
definition of terminal states in terms of predefined maximum depth and number
of instances, alongside C4.5’s pruning strategy. Additionally, by virtue of
using C4.5, a pure batch algorithm, this algorithm is not applicable for data
streams.

Our proposed method is a Value Iteration approach (Sutton and Barto,, 2018)
that uses Thompson Sampling policy within a MCTS framework. Unlike Temporal
Difference methods, such as Q-Learning and SARSA, general convergence results
for Monte Carlo methods remain an open theoretical question, noted in (Sutton
and Barto,, 2018, p. 99 and p. 103) as ”one of the most fundamental open
theoretical questions”. Some convergence results were established under
specific assumptions. Wang et al., (2020) prove almost sure optimal
convergence of the policy for Monte Carlo with Exploring Starts, while Dong et
al., (2022) show a similar result for Monte Carlo UCB. These results pertain
to MDPs with finite random length episodes where the optimal policy does not
revisit states. In our case, although our MDP features similar properties, the
rewards are unknown and merely estimated. We investigate the convergence
properties of MCTS with Thompson Sampling policy within our specific MDP. To
the best of our knowledge, no prior work has carried such analysis under this
assumption. The closest related work, found in (Bai et al.,, 2013), only
considers discounted MDPs with finite fixed horizons, and does not provide a
formal convergence proof, see (Bai et al.,, 2013, Section 3.5).

##  3 PROBLEM FORMULATION

Let $X=\left(X^{\left(1\right)},\ldots,X^{\left(q\right)}\right)$ be the input
with categorical attributes and $Y\in\\{1,\ldots,K\\}$ the class to predict.
Data samples $\left(X_{i},Y_{i}\right)$ arrive incrementally through a stream,
they are i.i.d. and follow a joint probability distribution $P_{X,Y}$. Let $T$
be a DT and $\mathcal{L}\left(T\right)$ the set of leaves of $T$, for each
leaf $l\in\mathcal{L}\left(T\right)$ and class $k\in\\{1,\ldots,K\\}$, let
$p\left(l\right)=\mathbb{P}\left[X\in l\right]$ denote the probability of
event ”The subset of the input space, described by leaf $l$, contains $X$” and
$p_{k}\left(l\right)=\mathbb{P}\left[Y=k|X\in l\right]$ the probability that
$Y=k$ given $X\in l$. For any input $X$ we also denote $l\left(X\right)$ the
leaf $l$ that contains $X$, i.e. the leaf $l$ such that $X\in l$. Let
$\mathcal{H}\left(T\right)=\mathbb{P}\left[T\left(X\right)=Y\right]$ be the
accuracy of $T$ where
$T\left(X\right)=T\left(l\left(X\right)\right)=\textrm{Argmax}_{k}\\{p_{k}\left(l\left(X\right)\right)\\}$
is the predicted class of $X$ according to $T$. If we define our objective to
maximise as $\mathcal{H}\left(T\right)$, then the full DT that exhaustively
employs all the possible splits is a trivial solution. However, this solution
is an uninterpretable DT of maximum depth that just classifies the inputs
point-wise, as such, it is of no interest. We seek to balance between
maximising the accuracy and minimising the complexity, the latter condition is
for interpretation purposes. To this end, we introduce the regularised
objective:

$\mathcal{H}_{r}\left(T\right)=\mathbb{P}\left[T\left(X\right)=Y\right]-\lambda\mathcal{S}\left(T\right)$

Where $\lambda\geq 0$ is a penalty parameter and $\mathcal{S}\left(T\right)$
is the number of splits in $T$. We note that Hu et al., (2019) introduce a
similar objective, but the authors penalise the number of leaves
$|\mathcal{L}\left(T\right)|$ rather than the number of splits
$\mathcal{S}\left(T\right)$. Our choice is motivated by the MDP we define in
the following section.

###  3.1 Markov Decision Process (MDP)

We introduce our undiscounted episodic MDP with finite random length episodes
as follows:
State: Our state space is the space of DTs.
Action: There are two types of actions, split actions split a leaf with
respect to an attribute and the terminal action ends the episode, in which
case we transition from the current state $T$ to the terminal state denoted
$\overline{T}$ which represents the same DT as $T$.
Transition Dynamics: When taking an action, we transition from state $T$ to
state $T^{\prime}$ deterministically, in which case we denote the transition
$T\rightarrow T^{\prime}$. The set of next states from $T$ is denoted
$\textrm{Ch}\left(T\right)$, which signifies the children of $T$.
Reward: In any non-terminal state $T$, split actions yield reward $-\lambda$
and the terminal action yields reward
$\mathcal{H}\left(T\right)=\mathbb{P}\left[T\left(X\right)=Y\right]$, _which
is unknown_. $r\left(T,T^{\prime}\right)$ is the reward of the transition
$T\rightarrow T^{\prime}$.

In the next paragraph, we link the search for the optimal policy to that of
the optimal DT.
A stochastic policy $\pi$ maps each non-terminal state $T$ to a distribution
over $\textrm{Ch}\left(T\right)$, for any
$T^{\prime}\in\textrm{Ch}\left(T\right)$ we denote
$\pi\left(T^{\prime}|T\right)$ the probability of the transition $T\rightarrow
T^{\prime}$ according to $\pi$. If $\pi$ is deterministic, $\pi\left(T\right)$
is the next state from $T$ according to $\pi$. Let
$T=T^{\left(0\right)}\overset{\pi}{\rightarrow}T^{\left(1\right)}\overset{\pi}{\rightarrow}\ldots,\overset{\pi}{\rightarrow}T^{\left(N\right)}$
be the episode that stems from following policy $\pi$ starting from state $T$;
$T^{\left(N\right)}=\overline{T^{\left(N-1\right)}}$ is terminal. The value of
$\pi$ at $T$ is defined as:

$\mathcal{V}^{\pi}\left(T\right)=\mathbb{E}\left[\sum_{j=1}^{N}r\left(T^{\left(j-1\right)},T^{\left(j\right)}\right)\right]$

For convenience, we also define, for all terminal states $\overline{T}$,
$\mathcal{V}^{\pi}\left(\overline{T}\right)=\mathcal{H}\left(\overline{T}\right)=\mathcal{H}\left(T\right)$.
If $\pi$ is deterministic, then we get:

$\displaystyle\mathcal{V}^{\pi}\left(T\right)=\lambda\mathcal{S}\left(T\right)+\mathcal{H}_{r}\left(T^{\left(N-1\right)}\right)$

Let $R$ denote the root state (DT with only one leaf), we have
$\mathcal{S}\left(R\right)=0$ and therefore:

$\mathcal{V}^{\pi}\left(R\right)=\lambda\mathcal{S}\left(R\right)+\mathcal{H}_{r}\left(T^{\left(N-1\right)}\right)=\mathcal{H}_{r}\left(T^{\left(N-1\right)}\right)$

Let $\pi^{*}\in\textrm{Argmax}_{\pi}\mathcal{V}^{\pi}\left(R\right)$, the
optimal policy $\pi^{*}$ exists and is deterministic because our MDP is
finite. Let
$R\overset{\pi^{*}}{\rightarrow}\ldots,\overset{\pi^{*}}{\rightarrow}T^{*}\overset{\pi^{*}}{\rightarrow}\overline{T^{*}}$,
then
$\mathcal{H}_{r}\left(T^{*}\right)=\mathcal{V}^{\pi^{*}}\left(R\right)\geq\mathcal{V}^{\pi}\left(R\right)$
for any policy $\pi$. On the other hand, any DT $T$ is constructed from a
series of splits of the root $R$, thus there always exists a policy $\pi$ such
that
$R\overset{\pi}{\rightarrow}\ldots,\overset{\pi}{\rightarrow}T\overset{\pi}{\rightarrow}\overline{T}$,
and consequently
$\mathcal{V}^{\pi}\left(R\right)=\mathcal{H}_{r}\left(T\right)$. As a result,
$\mathcal{H}_{r}\left(T^{*}\right)\geq\mathcal{H}_{r}\left(T\right)$ for any
DT $T$, establishing the optimality of $T^{*}$. We can find $T^{*}$ by
deriving $\pi^{*}$ first and then following it.

###  3.2 Tree representation of the State-Action Space

As is custom in MCTS, the State-Action space is represented as a Tree called
the Search Tree. We refer to the nodes of the Search Tree as Search Nodes to
avoid confusion with the nodes of DTs. These Search Nodes serve as
representations of states, which are DTs in the context of our MDP. The edges
within the Search Tree correspond to actions. Throughout this work, we refer
to DTs, states and Search Nodes interchangeably. The root of the Search Tree
is the initial state $R$ (the root DT), and its leaves, called Search Leaves,
are the terminal states. Figure 1 depicts a segment of the Search Tree.

Figure 1: Each Search Node is a state and each edge an action. The left-most
edge is the terminal action, hence why both the parent and child Search Nodes
represent the same DT. The remaining edges are split actions with respect to
the black leaf.

##  4 TSDT

In this section, we introduce our method. If we know
$\mathcal{V}^{\pi^{*}}\left(\overline{T}\right)=\mathcal{H}\left(T\right)$ for
all Search Leaves $\overline{T}$, then we can Backpropagate these values up
the Search Tree and recursively deduce $\mathcal{V}^{\pi^{*}}\left(T\right)$
for all internal Search Nodes with the Bellman Optimality Equation:

$\mathcal{V}^{\pi^{*}}\left(T\right)=\max_{T^{\prime}\in\textrm{Ch}\left(T\right)}\Big{\\{}-\lambda\mathds{1}\Big{\\{}T^{\prime}\neq\overline{T}\Big{\\}}+\mathcal{V}^{\pi^{*}}\left(T^{\prime}\right)\Big{\\}}$
(1)

Unfortunately, the values $\mathcal{V}^{\pi^{*}}\left(\overline{T}\right)$ are
unknown, this prompts us to estimate them, but which Search Leaves should we
prioritise? We need a policy with an efficient Exploration-Exploitation trade-
off. Several notable options can be considered, among which UCB (Auer et al.,,
2002), that was popularised, in the context of MCTS, by the UCT algorithm
(Kocsis and Szepesvári,, 2006). UCB is out of the scope of this paper, we
analyse it in one of our ongoing works. We consider Thompson Sampling instead.
To use this policy, we need to estimate the values within a Bayesian
framework.

###  4.1 Estimating $\mathcal{V}^{\pi^{*}}\left(\overline{T}\right)$ for a
Search Leaf $\overline{T}$

For any Search Leaf $\overline{T}$, we have:

$\displaystyle\mathcal{V}^{\pi^{*}}\left(\overline{T}\right)$
$\displaystyle=\mathcal{H}\left(T\right)=\mathbb{P}\left[T\left(X\right)=Y\right]$
$\displaystyle=\sum_{l\in\mathcal{L}\left(T\right)}p\left(l\right)\mathbb{E}\left[\mathds{1}\\{T\left(X\right)=Y\\}|X\in
l\right]$ (2)

From Equation (2), given observed data
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$, we define the posterior on
$\mathcal{V}^{\pi^{*}}\left(\overline{T}\right)$ with:

$\theta_{\overline{T}}=\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)\theta_{T,l}$
(3)

Where $\hat{p}\left(l\right)$ is an estimator of $p\left(l\right)$ and
$\theta_{T,l}$ follows a posterior distribution on
$\mathbb{E}\left[\mathds{1}\\{T\left(X\right)=Y\\}|X\in l\right]$ given
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$. Since
$\mathbb{E}\left[\mathds{1}\\{T\left(X\right)=Y\\}|X\in l\right]$ is the mean
of a Bernoulli variable, we are tempted to use its Beta conjugate prior with
the following updates:

$\displaystyle\theta_{T,l}$
$\displaystyle\sim\textrm{Beta}\left(\alpha_{T,l},\beta_{T,l}\right)$
$\displaystyle\alpha_{T,l}$
$\displaystyle=1+\sum_{i=1}^{N}\mathds{1}\\{X_{i}\in
l\\}\mathds{1}\\{T\left(X_{i}\right)=Y_{i}\\};$ $\displaystyle\beta_{T,l}$
$\displaystyle=1+\sum_{i=1}^{N}\mathds{1}\\{X_{i}\in
l\\}-\sum_{i=1}^{N}\mathds{1}\\{X_{i}\in
l\\}\mathds{1}\\{T\left(X_{i}\right)=Y_{i}\\}$

However, the challenge pertains to the unknown nature of
$T\left(X_{i}\right)=\textrm{Argmax}_{k}\\{p_{k}\left(l\left(X_{i}\right)\right)\\}$.
We solve this issue with the empirical average estimates:

$\displaystyle\forall{l\in\mathcal{L}\left(T\right)}:\hat{p}_{k}^{\left(i\right)}\left(l\right)$
$\displaystyle=\frac{\sum_{j=1}^{i}\mathds{1}\\{X_{j}\in
l\\}\mathds{1}\\{Y_{j}=k\\}}{\sum_{j=1}^{i}\mathds{1}\\{X_{j}\in l\\}}$
$\displaystyle\hat{T}_{i}\left(l\right)$
$\displaystyle=\textrm{Argmax}_{k}\\{\hat{p}_{k}^{\left(i\right)}\left(l\right)\\}$
(4)

Then we rather update $\alpha_{T,l}$ and $\beta_{T,l}$ with:

$\displaystyle\alpha_{T,l}$
$\displaystyle=1+\sum_{i=2}^{N}\mathds{1}\\{X_{i}\in
l\\}\mathds{1}\\{\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\\};$ (5)
$\displaystyle\beta_{T,l}$
$\displaystyle=1+\sum_{i=2}^{N}\mathds{1}\\{X_{i}\in l\\}$
$\displaystyle-\sum_{i=2}^{N}\mathds{1}\\{X_{i}\in
l\\}\mathds{1}\\{\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\\}$ (6)

Now $\theta_{\overline{T}}$ (Equation (3)) is a linear combination of the Beta
variables $\theta_{T,l}$, and its distribution is not easy to infer. For this
reason, we consider the common Normal approximation of the Beta distribution
where we match the first two moments.

$\displaystyle\theta_{T,l}$
$\displaystyle\sim\mathcal{N}\left(\mu_{T,l},\left(\sigma_{T,l}\right)^{2}\right);\;\mu_{T,l}=\frac{\alpha_{T,l}}{\alpha_{T,l}+\beta_{T,l}}$
(7) $\displaystyle\left(\sigma_{T,l}\right)^{2}$
$\displaystyle=\frac{\alpha_{T,l}\beta_{T,l}}{\left(\alpha_{T,l}+\beta_{T,l}\right)^{2}\left(1+\alpha_{T,l}+\beta_{T,l}\right)}$
(8)

This makes
$\theta_{\overline{T}}=\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)\theta_{T,l}$
a linear combination of Normal random variables, and therefore:

$\displaystyle\theta_{\overline{T}}$
$\displaystyle\sim\mathcal{N}\left(\mu_{\overline{T}},\left(\sigma_{\overline{T}}\right)^{2}\right);\;\mu_{\overline{T}}=\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)\mu_{T,l}$
(9) $\displaystyle\left(\sigma_{\overline{T}}\right)^{2}$
$\displaystyle=\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)^{2}\left(\sigma_{T,l}\right)^{2}$
(10)

We recall that this posterior distribution is conditioned on the observed data
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$. To finalise the definition
of $\theta_{\overline{T}}$, we still need to define $\hat{p}\left(l\right)$.
We defer this task to Section 4.4 as we are currently lacking some key
insights from the Algorithm. For the time being, we assume having such
estimator that is completely defined by $\\{X_{i}\\}_{i=1}^{N}$ and consistent
$\hat{p}\left(l\right)\xrightarrow[N\rightarrow\infty]{\textrm{a.s}}p\left(l\right)$.

###  4.2 Estimating $\mathcal{V}^{\pi^{*}}\left(T\right)$ for an internal
Search Node $T$

Let $T$ be an internal Search Node, which is a non-terminal state. Value
Iteration updates the estimate of $\mathcal{V}^{\pi^{*}}\left(T\right)$
according to the Bellman Optimality Equation (1). Thus, we define the
posterior on $\mathcal{V}^{\pi^{*}}\left(T\right)$ given all the observed data
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$ as:

$\theta_{T}=\max_{T^{\prime}\in\textrm{Ch}\left(T\right)}\Big{\\{}-\lambda\mathds{1}\Big{\\{}T^{\prime}\neq\overline{T}\Big{\\}}+\theta_{T^{\prime}}\Big{\\}}$
(11)

What is the posterior distribution of $\theta_{T}$ given
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$?

We suppose
$\forall{T^{\prime}}\in\textrm{Ch}\left(T\right):\theta_{T^{\prime}}\sim\mathcal{N}\left(\mu_{T^{\prime}},\left(\sigma_{T^{\prime}}\right)^{2}\right)$.
This is motivated by an inductive reasoning, indeed, if we show that
$\theta_{T}$ is Normally distributed, then since the posteriors of all Search
Leaves are Normal, as defined in Section 4.1, we would recursively infer that
the posteriors of all internal Search Nodes are Normal.
Unfortunately, the maximum of Normal variables, as defined in Equation (11),
is not Normal, this observation is documented in (Clark,, 1961; Sinha et al.,,
2007). To solve this issue, a first approach is to use a Normal approximation
of the distribution of the maximum in Equation (11), this is achieved by
recursively applying Clark’s mean and variance formula for the maximum of two
Normal variables as demonstrated in (Tesauro et al.,, 2010, Section 4.1). This
leads to our first version of TSDT, we present the details of this
Backpropagation scheme in Appendix C. Nevertheless, this approximation incurs
a substantial computational cost as the number of children
$|\textrm{Ch}\left(T\right)|$ increases. Moreover, as outlined by Sinha et
al., (2007), the order in which the recursive approximations are executed may
significantly affect the quality of the overall approximation. For these
reasons, we introduce an alternative, more straightforward approach to
Backpropagating the posterior distributions $\theta_{T^{\prime}}$ to
$\theta_{T}$. Specifically, we assign to $\theta_{T}$ the posterior
distribution of the child with maximum posterior mean:

$\widetilde{T}=\textrm{Argmax}_{T^{\prime}\in\textrm{Ch}\left(T\right)}\\{\mu_{T^{\prime}}\\};\;\theta_{T}\sim\mathcal{N}\left(\mu_{\widetilde{T}},\left(\sigma_{\widetilde{T}}\right)^{2}\right)$
(12)

We call this second version of the Algorithm Fast-TSDT, it is more practical
than the first one and exhibits better computational efficiency. While in
general, the distribution in formula (12) may not serve as an accurate
approximation for the distribution of the maximum in Equation (11), it
progressively improves as $\theta_{T^{\prime}}$, for children $T^{\prime}$,
concentrate around their means. This concentration occurs as more data is
accumulated within $T^{\prime}$, as exemplified in Equations (10) and (8) for
Search Leaves. Furthermore, it is worth noting that Fast-TSDT displays a
substantial gain in computational efficiency and also (surprisingly!) in
performance compared to TSDT.

###  4.3 The Algorithm

Algorithm 1 is an abstract description of TSDT and Fast-TSDT. In the
following, we view it from the perspective of an incremental construction of
the Search Tree representation. Initially, our Search Tree representation
contains the root $R$ only, then at each iteration $t$, we follow the steps
illustrated in Figure 2.

  * •

Selection: Line 4. Starting from $R$, descend the Search Tree by choosing a
child according to the current policy $\pi_{t}$ until reaching a Search Leaf.

  * •

Simulation: Line 5. We observe new $m$ incoming data from the stream in
$T^{\left(N-1\right)}$. The objective is to use the accumulated observed data
in $T^{\left(N-1\right)}$ to, either initialise the posteriors of children
$T^{\prime}\in\textrm{Ch}\left(T^{\left(N-1\right)}\right)$ with
$\theta_{T^{\prime}}=\theta_{\overline{T^{\prime}}}$ (Line 11), or to just
update the posterior of $\theta_{T^{\left(N\right)}}$ (Line 14). These
posteriors will in turn update the posterior of $\theta_{T}$, as per Section
4.2, during Backpropagation.

  * •

Expansion: Line 7. If $T^{\left(N-1\right)}$ is visited for the first time, we
add its children Search Nodes
$T^{\prime}\in\textrm{Ch}\left(T^{\left(N-1\right)}\right)$ to our Search Tree
representation.

  * •

Backpropagation: Loop from Line 16 to 21. Recursively update the posterior of
the ancestors $\theta_{T^{\left(j\right)}}$ (Line 17), for $j=N-1$ to $0$,
with the internal Search Nodes posterior updates as per Section 4.2 (formula
(12) for Fast-TSDT, and the recursive Normal approximation of the maximum for
TSDT). At the same time, update the Thompson Sampling policy (Loop from Line
18 to 20).

In line 23, after $M$ iterations of TSDT, we define the greedy policy $\pi$
with respect to the posterior means. Then we unroll $\pi$:
$R=T^{\left(0\right)}\overset{\pi}{\rightarrow}T^{\left(1\right)}\overset{\pi}{\rightarrow}\ldots,\overset{\pi}{\rightarrow}T^{\left(N\right)}$
and return the proposed solution $T^{\left(N\right)}$ (Lines 24, 25).

To complete the description of Algorithm 1, we still need to answer the
following question: How does the Simulation step allow us to initialise the
posteriors for the children? To answer this question, we introduce some new
statistics.
Let $T$ be a Search Node that was simulated, and suppose we observe data
$\\{\left(X_{s},Y_{s}\right)\\}_{s=1}^{N}$ in $T$. Let
$l\in\mathcal{L}\left(T\right)$ be a leaf of $T$ and
$T^{\left(l,i\right)}\in\textrm{Ch}\left(T\right)$ the child that stems from
splitting $l$ with respect to attribute $X^{\left(i\right)}$. Our objective
here is to use data $\\{\left(X_{s},Y_{s}\right)\\}_{s=1}^{N}$ to initialise
$\theta_{T^{\left(l,i\right)}}=\theta_{\overline{T^{\left(l,i\right)}}}$.
According to Equations (7), (8), (9) and (10), this is achieved by calculating
$\alpha_{T^{\left(l,i\right)},l^{\prime}},\beta_{T^{\left(l,i\right)},l^{\prime}}$
for all leaves $l^{\prime}\in\mathcal{L}\left(T^{\left(l,i\right)}\right)$
(and also $\hat{p}\left(l^{\prime}\right)$ which, we remind the reader, is
deferred to Section 4.4). Let
$l^{\prime}\in\mathcal{L}\left(T^{\left(l,i\right)}\right)$, if $l^{\prime}$
is not a child of $l$, then $l^{\prime}$ is a common leaf between
$T^{\left(l,i\right)}$ and $T$, thus
$\alpha_{T^{\left(l,i\right)},l^{\prime}}=\alpha_{T,l^{\prime}}$ and
$\beta_{T^{\left(l,i\right)},l^{\prime}}=\beta_{T,l^{\prime}}$, these are
straightforwardly calculated with the observed data
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$ using Equations (4), (5) and
(6). If $l^{\prime}$ is a child of $l$, then there exists $j$ such that
$l^{\prime}=l_{ij}$ is the child of $l$ that corresponds to attribute
$X^{\left(i\right)}$ being equal to $j$. For $N^{\prime}\leq N$, we define:

$\displaystyle n_{ijk}\left(N^{\prime},l\right)$
$\displaystyle=\sum_{s=1}^{N^{\prime}}\mathds{1}\\{Y_{s}=k\\}\mathds{1}\\{X_{s}^{(i)}=j\\}\mathds{1}\\{X_{s}\in
l\\}$

On the subset $\\{\left(X_{s},Y_{s}\right)\\}_{s=1}^{N^{\prime}}$,
$n_{ijk}\left(N^{\prime},l\right)$ is the number of inputs $X_{s}\in l$ of
class $k$ satisfying $X_{s}^{\left(i\right)}=j$. Then we can track the
estimates:

$\displaystyle\hat{T}_{N^{\prime}}^{\left(l,i\right)}\left(l_{ij}\right)=\textrm{Argmax}_{k}\Bigg{\\{}\frac{n_{ijk}\left(N^{\prime},l\right)}{\sum_{k}n_{ijk}\left(N^{\prime},l\right)}\Bigg{\\}}$
$\displaystyle
m\left(l_{ij}\right)=\sum_{s=2}^{N}\mathds{1}\\{\hat{T}_{s-1}^{\left(l,i\right)}\left(X_{s}\right)=Y_{s}\\}\mathds{1}\\{X_{s}^{(i)}=j\\}\mathds{1}\\{X_{s}\in
l\\}$
$\displaystyle\alpha_{T^{\left(l,i\right)},l_{ij}}=1+m\left(l_{ij}\right);$
$\displaystyle\beta_{T^{\left(l,i\right)},l_{ij}}=1+\sum_{ijk}n_{ijk}\left(N,l\right)-m\left(l_{ij}\right)$

With this, the initialisation
$\theta_{T^{\left(l,i\right)}}=\theta_{\overline{T^{\left(l,i\right)}}}$ is
now complete. In summary, the introduced $n_{ijk}\left(N^{\prime},l\right)$
statistics at the leaves $l\in\mathcal{L}\left(T\right)$ allow us to use the
accumulated observed data $\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$ to
initialise the posterior $\theta_{T^{\prime}}=\theta_{\overline{T^{\prime}}}$
for all children $T^{\prime}\in\textrm{Ch}\left(T\right)$.

Algorithm 1 TSDT, Fast-TSDT

1:Input: $M$ number of iterations, $m$ number of observed samples per
Simulation, $\lambda\geq 0$.

2:Initialise $\pi_{0}\left(\overline{T}\Big{|}T\right)=1$ and _fully_expanded(
$T$) = False_ for all non-terminal states $T$

3:for $t=1$ to $M$ do

4: Unroll $\pi_{t}$:
$R=T^{\left(0\right)}\overset{\pi_{t}}{\rightarrow}T^{\left(1\right)}\overset{\pi_{t}}{\rightarrow}\ldots,\overset{\pi_{t}}{\rightarrow}T^{\left(N\right)}$

5:  _Simulate( $T^{\left(N-1\right)}$)_

6: if not _fully_expanded( $T^{\left(N-1\right)}$)_ then

7:  _Expand( $T^{\left(N-1\right)}$)_

8:  _fully_expanded( $T^{\left(N-1\right)}$) = True_

9: for $T^{\prime}\in\textrm{Ch}\left(T^{\left(N-1\right)}\right)$ do

10: Update the posterior of $\theta_{\overline{T^{\prime}}}$

11: Initialise $\theta_{T^{\prime}}=\theta_{\overline{T^{\prime}}}$

12: end for

13: else

14: Update the posterior of $\theta_{T^{\left(N\right)}}$

15: end if

16: for $j=N-1$ to $0$ do

17: Update the posterior of $\theta_{T^{\left(j\right)}}$

18: for $T^{\prime}\in\textrm{Ch}\left(T^{\left(j\right)}\right)$ do

19: Update the policy at $T^{\left(j\right)}\rightarrow T^{\prime}$
$\pi_{t+1}\left(T^{\prime}\Big{|}T^{\left(j\right)}\right)=\mathbb{P}\left[\theta_{T^{\prime}}=\max_{T"\in\textrm{Ch}\left(T^{\left(j\right)}\right)}\\{\theta_{T"}\\}\right]$

20: end for

21: end for

22:end for

23:Define
$\pi\left(T\right)=\textrm{Argmax}_{T^{\prime}\in\textrm{Ch}\left(T\right)}\Big{\\{}-\lambda\mathds{1}\\{T^{\prime}\neq\overline{T}\\}+\mu_{T^{\prime}}\Big{\\}}$
for all non-terminal states $T$

24:Unroll $\pi$:
$R=T^{\left(0\right)}\overset{\pi}{\rightarrow}T^{\left(1\right)}\overset{\pi}{\rightarrow}\ldots,\overset{\pi}{\rightarrow}T^{\left(N\right)}$

25:return $T^{\left(N\right)}$

In the following, we provide the optimal convergence result for both TSDT and
Fast-TSDT.

######  Theorem 1.

Let time $t$ denote the number of iterations of TSDT and Fast-TSDT, then any
Search Node $T$ satisfies the following:

$\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T\right),\left(\sigma_{T}\right)^{2}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

and any internal Search Node $T$ satisfies:

$\pi_{t}\left(\pi^{*}\left(T\right)\Big{|}T\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}1$

Theorem 1 states the concentration of $\theta_{T}$ around the optimal value
$\mathcal{V}^{\pi^{*}}\left(T\right)$ for any Search Node $T$. Additionally,
it asserts the concentration of the policy $\pi_{t}\left(.|T\right)$ around
the optimal action $\pi^{*}\left(T\right)$ for any internal Search Node $T$.
This Theorem provides an asymptotic guarantee of optimality, which is
valuable. However, it would be ideal to have some finite time guarantees in
the form of PAC-bounds or rates of convergence. Unfortunately, such guarantees
are primarily derived for simpler settings like bandit problems. In the
context of MDPs, most convergence guarantees are asymptotic, and the issue of
finite-time guarantees remains open in many cases. We believe that the tail
inequality we derive in Theorem 2 marks a first step towards achieving this
goal in a future work. The idea is that by controlling the concentration of
the posteriors at the level of Search Leaves, it may be possible to propagate
this control up the Search Tree to the root state $R$. This would allow us to
derive a time-dependent concentration probability of the posterior of
$\theta_{R}$ around the true $\mathcal{V}^{\pi^{*}}\left(R\right)$. However,
this Backpropagation reasoning is a non-trivial challenge that warrants
further exploration in future work.

######  Theorem 2.

Let $T$ be an internal Search Node with
$\textrm{Ch}\left(T\right)=\\{T_{1},\ldots,T_{w}\\}$ Search Leaves and $w\geq
2$. Let $t$ denote the number of visits of $T$ and $N_{T_{j}}\left(t\right)$
the number of visits of $T_{j}$ up to $t$. Define
$M_{w}=1+\sqrt{\frac{2}{\sqrt{3}}}\textrm{erfc}^{-1}\left(\frac{1}{w-1}\right)$,
then $\forall{T_{j}\in\textrm{Ch}\left(T\right)}$:

$\displaystyle\mathbb{P}\left[N_{T_{j}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{j}\right)|M_{w}}\right]\leq$
$\displaystyle\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\phi\left(t\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{j}\right)|M_{w}^{2}}\right)^{2}\right]$

Where $\phi\left(t\right)=\sqrt{\frac{\log t}{4}}+\sqrt{\frac{\log t}{4}+2}$

Figure 2: One iteration of TSDT. The Search Node in dashed lines is the Search
Leaf $T^{\left(N\right)}=\overline{T^{\left(N-1\right)}}$.

###  4.4 Estimator $\hat{p}\left(l\right)$

Let $T$ be a DT and $l\in\mathcal{L}\left(T\right)$ some leaf. We recall from
Equations (2) and (3) that we need an estimator $\hat{p}\left(l\right)$ of
$p\left(l\right)=\mathbb{P}\left[X\in l\right]$. Suppose we observe data
$\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$ in $T$, the most straightforward
estimator is the empirical average. However, Algorithm 1 incorporates
mechanisms that make it sample efficient. It does not copy Decision Tree
nodes, thus the $n_{ijk}\left(N,\eta\right)$, of any node $\eta$, are updated
whenever data $\left(X_{s},Y_{s}\right)$ is observed (during Simulation) with
$X_{s}\in\eta$, regardless of which Search Node was simulated. In addition,
even though $n_{ijk}\left(N,l\right)$ can be used to calculate the empirical
averages:

$\displaystyle\hat{p}\left(l\right)$
$\displaystyle=\frac{\sum_{ijk}n_{ijk}\left(N,l\right)}{\sum_{l\in\mathcal{L}\left(T\right)}\sum_{ijk}n_{ijk}\left(N,l\right)}$
$\displaystyle\hat{p}\left(l_{ij}\right)$
$\displaystyle=\frac{\sum_{k}n_{ijk}\left(N,l\right)}{\sum_{l\in\mathcal{L}\left(T\right)}\sum_{ijk}n_{ijk}\left(N,\eta\right)}$

for any leaf $l\in\mathcal{L}\left(T\right)$ and any child node $l_{ij}$ of
$l$. $n_{ijk}\left(N,l\right)$ cannot calculate the empirical average for the
children of $l_{ij}$. This limited scope, along with not copying Decision Tree
nodes, cause the observed marginal distribution of input $X$ to shift from the
true marginal distribution. We explain this phenomenon in the next paragraph
and illustrate it in Figure 3.

When expanding $R$, the observed data in $r$ update the empirical averages for
nodes $a$ and $b$, then when $A$ is selected, simulated and expanded, node $a$
in $C$ has its empirical average estimator updated using this newly observed
data (during the Simulation of $A$) accumulated with the old data (from the
Simulation of $R$). On the other hand however, for nodes $c$ and $d$, the
update only involves the newly observed data in $b$ (during the Simulation of
$A$). This leads to skewed estimators, $\hat{p}\left(a\right)$ overestimates
$p\left(a\right)$ while $\hat{p}\left(c\right)$ and $\hat{p}\left(d\right)$
underestimate $p\left(c\right)$ and $p\left(d\right)$, and the greater the
difference in depth between $a$ and $c,d$, the greater the overestimation and
underestimation effects are, we call this phenomenon “Weights Degeneracy”.
A second source of Weights Degeneracy is not copying the DT nodes, indeed
$\hat{p}\left(a\right)$ is updated not only when $A$ or $C$ are simulated but
also when $D$ is simulated, in the latter case, the sufficient statistics of
$\hat{p}\left(c\right)$ and $\hat{p}\left(d\right)$ are not updated at all,
making the overestimation/underestimation wider!

We avoid both Weights Degeneracy causes by defining a new estimator based on
the chain rule:

$\displaystyle\mathbb{P}\left[X\in l\right]=$
$\displaystyle\mathbb{P}\left[X\in
l,X\in\textrm{Parent}\left(l\right),\ldots,X\in\textrm{root}\right]$
$\displaystyle=$ $\displaystyle\mathbb{P}\left[X\in
l|X\in\textrm{Parent}\left(l\right)\right]\times\ldots\times\mathbb{P}\left[X\in\textrm{root}\right]$

We estimate each term
$\mathbb{P}\left[X\in\eta|X\in\textrm{Parent}\left(\eta\right)\right]$ with
$\hat{p}\left(\eta|\textrm{Parent}\left(\eta\right)\right)=\frac{n\left(N,\eta\right)}{\sum_{\psi\in\textrm{Sib}\left(\eta\right)}n\left(N,\psi\right)}$,
where $\textrm{Sib}\left(\eta\right)$ is the set of siblings of node $\eta$,
including $\eta$ itself, and $n\left(N,\eta\right)$ is the number of observed
samples with inputs in $\eta$. This yields the product estimator:

$\hat{p}\left(l\right)=\hat{p}\left(l|\textrm{Parent}\left(l\right)\right)\times\ldots\times
1$

Since estimates $\hat{p}\left(\eta|\textrm{Parent}\left(\eta\right)\right)$
only involve nodes at the same depth ($\eta$ and its siblings), both sources
of Weights Degeneracy are avoided, and by the Strong Law of Large numbers, we
have the consistency:

$\hat{p}\left(\eta|\textrm{Parent}\left(\eta\right)\right)\xlongrightarrow[]{\textrm{a.s}}\mathbb{P}\left[X\in\eta|X\in\textrm{Parent}\left(\eta\right)\right]$

As more and more samples are observed in $\textrm{Parent}\left(\eta\right)$,
and we deduce the consistency of our new estimator
$\hat{p}\left(l\right)\xlongrightarrow[N\rightarrow\infty]{\textrm{a.s}}p\left(l\right)$.

Figure 3: The Weights Degeneracy phenomenon.

##  5 EXPERIMENTS

Figure 4: Comparison of VFDT, EFDT, TSDT and Fast-TSDT. Left: Frequency of
perfect convergence; Right: Average running time in seconds. Figure 5: Cross-
validation test accuracy comparison between TSDT, Fast-TSDT, OSDT and DL8.5 as
a function of the number of leaves.

Our first experiment highlights an important weakness of the classic greedy DT
methods, and showcases how TSDT and Fast-TSDT circumvent this shortcoming. In
the second experiment, we compare our methods with recent optimal batch DT
algorithms DL8.5 and OSDT on standard real world benchmarks. All the
experimental details and additional results are provided in Appendix B.
Furthermore, our implemented code is available at
https://github.com/Chaoukia/Thompson-Sampling-Decision-Trees along with the
datasets we used.

We construct a challenging classification problem for greedy DT methods. In
this setting, all the attributes are uninformative, in the sense that their
true splitting gain metrics are all equal, making greedy methods VFDT and EFDT
choose an attribute arbitrarily with tie-break. Concretely, We consider a
binary classification problem with binary i.i.d. uniform attributes where
$Y=1$ if $X^{\left(1\right)}=0,X^{\left(2\right)}=0$ or
$X^{\left(1\right)}=1,X^{\left(2\right)}=1$ and $Y=0$ otherwise (Figure 6
provides a visualisation of the optimal DT). Attributes
$X^{\left(3\right)},\ldots,X^{\left(q\right)}$ are irrelevant, resulting in
uniform class distributions in both leaves, regardless of the attribute chosen
for the root split, even when selecting one of the relevant attributes
$X^{\left(1\right)}$ or $X^{\left(2\right)}$. Consequently, VFDT and EFDT
arbitrarily choose the attribute to employ for the first split, and will
continue with these arbitrary choices until attribute $X^{\left(1\right)}$ or
$X^{\left(2\right)}$ is chosen, resulting in unnecessarily deep DTs. We
compare VFDT, EFDT and TSDT on settings with different numbers of attributes
$q=5,10,20,50,100$. We perform 20 runs and report the frequency of perfect
convergence, i.e, convergence to the optimal DT that only employs
$X^{\left(1\right)}$ and $X^{\left(2\right)}$, and the average running time.
Figure 4 presents a clear trend: VFDT and EFDT rarely attain perfect
convergence, especially when $q$ is large. In contrast, both TSDT and Fast-
TSDT consistently achieve perfect convergence. Additionally, as anticipated,
Fast-TSDT demonstrates superior computational efficiency compared to TSDT.

In our second experiment, we conduct a comparison between TSDT, Fast-TSDT,
OSDT, and DL8.5, even though the latter two are batch algorithms. This choice
is due to the absence of prior research on optimal online DTs, to the best of
our knowledge. Furthermore, the source codes of both DL8.5 and OSDT are
publicly available. Unfortunately, we could not include a comparison with the
work by Nunes et al., (2018) as the authors have not made their code publicly
accessible. In this regard, we also draw attention to (Nunes et al.,, 2018,
Table 1), which demonstrates how that algorithm is prohibitively slow, taking
up to 105 hours in an instance. It is worth noting that our experiments
exclude GOSDT because our focus is on accuracy and complexity comparison, and
GOSDT is primarily an extension of OSDT to other objective functions beyond
accuracy. We follow the experimental protocol from (Hu et al.,, 2019) with its
datasets. We perform a 5-fold crossvalidation with different values of the
hyperparameters (maximum depth for DL8.5 and $\lambda$ for OSDT and TSDT), and
we report in Figure 5 the quartiles of the test accuracy and the number of
leaves. For MONK1, Hu et al., (2019) utilised a One-Hot Encoding that excludes
the last category of each attribute, which results in an optimal DT with 8
leaves. However, when the first category is dropped instead, the problem
becomes significantly more challenging, with an optimal DT having over 18
leaves (further details are available in Appendix B). On this latter problem,
Figure 5 clearly indicates that Fast-TSDT outperforms all other methods,
followed by TSDT. In fact, Fast-TSDT is the only method that achieves $100\%$
test accuracy with 19 leaves. Moreover, unlike OSDT and DL8.5, our methods do
not necessitate binary attributes. Therefore, they can be directly applied to
the original MONK1 data. In this scenario, the optimal DT representation of
$Y$ with the lowest complexity consists of 27 leaves, and it is successfully
retrieved by Fast-TSDT. TSDT, on the other hand, identifies a slightly more
complex DT with 28 leaves. For MONK2 and MONK3, Fast-TSDT demonstrates the
best accuracy to number of leaves frontier. On the remaining datasets, our
methods do not produce DTs with a large number of leaves, and OSDT performs
slightly better. In Appendix B, we provide the execution times, DL8.5 is the
fastest algorithm but also performs the least effectively, while OSDT and TSDT
frequently reach their time limit of 10 minutes. On the other hand, Fast-TSDT
strikes a good balance between speed and performance.

##  6 CONCLUSIONS, LIMITATIONS AND FUTURE WORK

We devised TSDT, a new family of MCTS algorithms for constructing optimal
online Decision Trees. We provided strong convergence results for our method
and highlighted how it circumvents the suboptimality issue of the standard
methods. Furthermore, TSDT showcases similar or better accuracy-complexity
trade-off compared to recent successful batch optimal DT algorithms, all while
being tailored to handling data streams. For now, we are still limited to
categorical attributes and our theoretical analysis only provides asymptotic
convergence results. It would be desirable to derive some finite-time
guarantees, in the form of PAC-bounds or rates of convergence, this is the aim
of our future work. To conclude, this paper opens further possibilities for
defining other MCTS algorithms with different policies, such as UCB and
$\epsilon$-greedy, in the context of optimal online DTs.

#### Acknowledgements

We thank Emilie Kaufmann for her insightful discussions, Otmane Sakhi for his
helpful comments on the writing of the paper, and the anonymous reviewers for
their valuable feedback.

## References

  * Aglin et al., (2020) Aglin, G., Nijssen, S., and Schaus, P. (2020).  Learning optimal decision trees using caching branch-and-bound search.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2):235–256.
  * Bai et al., (2013) Bai, A., Wu, F., and Chen, X. (2013).  Bayesian mixture modelling and inference based Thompson Sampling in Monte-Carlo tree search.  Advances in neural information processing systems, 26.
  * Bennett, (1994) Bennett, K. P. (1994).  Global tree optimization: A non-greedy decision tree algorithm.  Computing Science and Statistics, pages 156–156.
  * Bennett and Blue, (1996) Bennett, K. P. and Blue, J. A. (1996).  Optimal decision trees.  Rensselaer Polytechnic Institute Math Report, 214:24.
  * Bertsimas and Dunn, (2017) Bertsimas, D. and Dunn, J. (2017).  Optimal classification trees.  Machine Learning, 106(7):1039–1082.
  * Bifet and Gavalda, (2009) Bifet, A. and Gavalda, R. (2009).  Adaptive learning from evolving data streams.  In International Symposium on Intelligent Data Analysis, pages 249–260. Springer.
  * Bifet and Kirkby, (2009) Bifet, A. and Kirkby, R. (2009).  Data stream mining: a practical approach.  The university of Waikato.
  * Breiman et al., (1984) Breiman, L., Friedman, J., Stone, C. J., and Olshen, R. A. (1984).  Classification and regression trees.  CRC press.
  * Browne et al., (2012) Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. (2012).  A survey of Monte Carlo Tree Search methods.  IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43.
  * Clark, (1961) Clark, C. E. (1961).  The greatest of a finite set of random variables.  Operations Research, 9(2):145–162.
  * Domingos and Hulten, (2000) Domingos, P. and Hulten, G. (2000).  Mining high-speed data streams.  In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 71–80.
  * Dong et al., (2022) Dong, Z., Wang, C., and Ross, K. (2022).  On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs.  arXiv preprint arXiv:2209.02864.
  * Hu et al., (2019) Hu, X., Rudin, C., and Seltzer, M. (2019).  Optimal sparse decision trees.  Advances in Neural Information Processing Systems, 32.
  * Hulten et al., (2001) Hulten, G., Spencer, L., and Domingos, P. (2001).  Mining time-changing data streams.  In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 97–106.
  * Jin and Agrawal, (2003) Jin, R. and Agrawal, G. (2003).  Efficient decision tree construction on streaming data.  In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 571–576.
  * Kocsis and Szepesvári, (2006) Kocsis, L. and Szepesvári, C. (2006).  Bandit based Monte-Carlo planning.  In European conference on machine learning, pages 282–293. Springer.
  * Kschischang, (2017) Kschischang, F. R. (2017).  The complementary error function.  Online, April.
  * Laurent and Rivest, (1976) Laurent, H. and Rivest, R. L. (1976).  Constructing optimal binary decision trees is NP-complete.  Information processing letters, 5(1):15–17.
  * Lin et al., (2020) Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. (2020).  Generalized and scalable optimal sparse decision trees.  In International Conference on Machine Learning, pages 6150–6160. PMLR.
  * Manapragada et al., (2018) Manapragada, C., Webb, G. I., and Salehi, M. (2018).  Extremely fast decision tree.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1953–1962.
  * Norouzi et al., (2015) Norouzi, M., Collins, M., Johnson, M. A., Fleet, D. J., and Kohli, P. (2015).  Efficient non-greedy optimization of decision trees.  Advances in neural information processing systems, 28.
  * Nunes et al., (2018) Nunes, C., De Craene, M., Langet, H., Camara, O., and Jonsson, A. (2018).  A Monte Carlo Tree Search approach to learning decision trees.  In 2018 17th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 429–435. IEEE.
  * Quinlan, (2014) Quinlan, J. (2014).  C4. 5: programs for machine learning.  Elsevier.
  * Quinlan, (1986) Quinlan, J. R. (1986).  Induction of decision trees.  Machine learning, 1(1):81–106.
  * Rutkowski et al., (2013) Rutkowski, L., Jaworski, M., Pietruczuk, L., and Duda, P. (2013).  Decision trees for mining data streams based on the Gaussian approximation.  IEEE Transactions on Knowledge and Data Engineering, 26(1):108–119.
  * Rutkowski et al., (2012) Rutkowski, L., Pietruczuk, L., Duda, P., and Jaworski, M. (2012).  Decision trees for mining data streams based on the mcdiarmid’s bound.  IEEE Transactions on Knowledge and Data Engineering, 25(6):1272–1279.
  * Sinha et al., (2007) Sinha, D., Zhou, H., and Shenoy, N. V. (2007).  Advances in computation of the maximum of a set of Gaussian random variables.  IEEE Transactions on Computer-Aided design of integrated circuits and systems, 26(8):1522–1533.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Tesauro et al., (2010) Tesauro, G., Rajan, V. T., and Segal, R. (2010).  Bayesian Inference in Monte-Carlo Tree Search.  In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI’10, page 580–588, Arlington, Virginia, USA. AUAI Press.
  * Verwer and Zhang, (2019) Verwer, S. and Zhang, Y. (2019).  Learning optimal classification trees using a binary linear program formulation.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1625–1632.
  * Wang et al., (2020) Wang, C., Yuan, S., Shao, K., and Ross, K. (2020).  On the convergence of the Monte Carlo exploring starts algorithm for reinforcement learning.  arXiv preprint arXiv:2002.03585.

##  Appendix A Table of Notations

Table 1: Table of Notation $X$ | $=$ |  $\left(X^{\left(1\right)},\ldots,X^{\left(q\right)}\right)$, the input.
---|---|---
$Y$ | $\in$ |  $\\{1,\ldots,K\\}$, the class.
$T$ | $\triangleq$ |  State, Decision Tree, Search Node.
$\overline{T}$ | $\triangleq$ |  Terminal state that stems from taking the terminal action in $T$.
$T^{\left(l,i\right)}$ | $\triangleq$ |  child Search Node of $T$ that stems from splitting leaf $l\in\mathcal{L}\left(T\right)$ with respect to attribute $X^{\left(i\right)}$.
$R$ | $\triangleq$ |  Root Decision Tree, initial state, root of the Search Tree.
$\mathcal{L}\left(T\right)$ | $\triangleq$ |  Set of leaves of Decision Tree $T$.
$X\in l$ | $\triangleq$ |  Event, the subset described by $l$ contains $X$.
$p\left(l\right)$ | $=$ |  $\mathbb{P}\left[X\in l\right]$, probability of $X\in l$.
$p_{k}\left(l\right)$ | $=$ |  $\mathbb{P}\left[Y=k|X\in l\right]$, probability of $Y=k$ given $X\in l$.
$l\left(X\right)$ | $\triangleq$ |  Leaf $l$ such that $X\in l$.
$\mathcal{H}\left(T\right)$ | $=$ |  $\mathbb{P}\left[T\left(X\right)=Y\right]$, accuracy of Decision Tree classifier $T$.
$T\left(X\right)$ | $\triangleq$ |  $\textrm{argmax}_{k}\\{p_{k}\left(l\left(X\right)\right)\\}$, predicted class of $X$ according to DT $T$.
$\mathcal{H}_{r}\left(T\right)$ | $\triangleq$ |  Regularized Objective function of Search Node $T$.
$\mathcal{H}_{r}\left(T\right)$ | $=$ |  $\mathbb{P}\left[T\left(X\right)=Y\right]-\lambda\mathcal{S}\left(T\right)$.
$\mathcal{S}\left(T\right)$ | $\triangleq$ |  Number of splits in DT $T$.
$T\rightarrow T^{\prime}$ | $\triangleq$ |  Transition from state $T$ to state $T^{\prime}$.
$\textrm{Ch}\left(T\right)$ | $\triangleq$ |  Set of children of Search Node $T$, also set of next states from $T$.
$r\left(T,T^{\prime}\right)$ | $\triangleq$ |  Reward of transition $T\rightarrow T^{\prime}$.
$\pi$ | $\triangleq$ |  Policy, maps each state $T$ to a distribution over $\textrm{Ch}\left(T\right)$.
$\pi\left(T^{\prime}|T\right)$ | $\triangleq$ |  Probability of transition $T\rightarrow T^{\prime}$ according to policy $\pi$.
$\pi\left(T\right)$ | $\triangleq$ |  Next state from $T$ according to policy $\pi$.
$T^{\left(0\right)}\overset{\pi}{\rightarrow}\ldots,\overset{\pi}{\rightarrow}T^{\left(N\right)}$ | $\triangleq$ |  Episode that stems from following policy $\pi$ starting from state $T$.
$\mathcal{V}^{\pi}\left(T\right)$ | $\triangleq$ |  Value of following policy $\pi$ starting from state $T$.
$\pi^{*}$ | $\in$ |  $\textrm{Argmax}_{\pi}\mathcal{V}^{\pi}\left(R\right)$, optimal policy at the initial state $R$.
$T^{*}$ | $\triangleq$ |  Optimal Decision Tree with respect to $\mathcal{H}_{r}$.
$\theta_{T}$ | $\triangleq$ |  Posterior distribution on $\mathcal{V}^{\pi^{*}}\left(T\right)$.
$\theta_{T,l}$ | $\triangleq$ |  Posterior distribution on $\mathbb{E}\left[\mathds{1}\\{T\left(X\right)=Y\\}|X\in l\right]$.
$\hat{p}\left(l\right)$ | $\triangleq$ |  Estimator of $p\left(l\right)$.
$\hat{p}_{k}^{\left(i\right)}\left(l\right)$ | $=$ |  $\frac{\sum_{j=1}^{i}\mathds{1}\\{X_{j}\in l\\}\mathds{1}\\{Y_{j}=k\\}}{\sum_{j=1}^{i}\mathds{1}\\{X_{j}\in l\\}}$, estimator of $p_{k}\left(l\right)$.
$\hat{T}_{i}\left(l\right)$ | $=$ |  $\textrm{Argmax}_{k}\\{\hat{p}_{k}^{\left(i\right)}\left(l\right)\\}$, estimator of $T\left(l\right)$.
$\alpha_{T,l},\beta_{T,l}$ | $=$ |  Parameters of random variable $\theta_{T,l}$.
$\mu_{T,l},\sigma_{T,l}$ | $=$ |  Mean and standard deviation of $\theta_{T,l}$ respectively.
$\mu_{T},\sigma_{T}$ | $=$ |  Mean and standard deviation of $\theta_{T}$ respectively.
$n_{ijk}\left(N,\eta\right)$ | $\triangleq$ |  Given observed samples $\\{\left(X_{s},Y_{s}\right)\\}_{s=1}^{N}$, $n_{ijk}\left(N,\eta\right)$ is the number samples with $X_{s}\in\eta,Y_{s}=k$ satisfying $X_{s}^{\left(i\right)}=j$.

##  Appendix B Experiments

  * •

All of the experiments were run on a personal Machine (2,6 GHz 6-Core Intel
Core i7), they are easily reproducible.

  * •

The codes for DL8.5 and OSDT are available at https://pypi.org/project/dl8.5/
and https://github.com/xiyanghu/OSDT.git respectively. We provide code for
TSDT and Fast-TSDT at https://github.com/Chaoukia/Thompson-Sampling-Decision-
Trees.

  * •

In practice, the variances in Equation (10) can collapse to $0$ quickly,
undermining exploration and slowing down the algorithm. We mitigate this issue
by introducing an exponent $0<\gamma<1$ as follows:

$\left(\sigma_{\overline{T}}\right)^{2}=\left(\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)^{2}\left(\sigma_{T,l}\right)^{2}\right)^{\gamma}$

This is also discussed in (Kocsis and Szepesvári,, 2006, Section 3.1). The
authors of UCT introduce an exponent on the bias terms $c_{t,s}$ in practice.
In all our experiments, we use $\gamma=0.75$.

  * •

During the Expansion step, creating all the children of the selected Search
Node $T$ can be computationally expensive. Therefore, whenever $T$ is chosen,
we expand it with respect to only one untreated leaf. Initially, all leaves of
$T$ are marked as untreated. Upon selecting $T$, we pick the untreated leaf
$l\in\mathcal{L}\left(T\right)$ with the highest Gini impurity to prioritize
exploring promising parts of the Search Tree. We then generate the subset of
$\textrm{Ch}\left(T\right)$ by considering all possible split actions
exclusively with respect to leaf $l$, subsequently marking $l$ as treated. We
update $\pi_{t}$ at $T$ only when all leaves in $\mathcal{L}\left(T\right)$
have been treated. Only then, the children of $T$ in
$\textrm{Ch}\left(T\right)$ become eligible to be considered for future
Selection (and the subsequent) steps.

##### Synthetic Experiment:

We use the default hyperparameters for VFDT and EFDT, for TSDT and Fast-TSDT,
we set $M=400,m=100,\lambda=0.05$.

Figure 6: Equivalent representations of $Y$ as a Decision Tree for the
synthetic experiment.

##### Real World datasets:

We ran both our methods with $M=1000$ iterations for MONK1 Original and MONK1
Drop Last, and with $M=10000$ iterations on the remaining datasets. All
instances of TSDT and Fast-TSDT use $m=100$ number of samples per Simulation
step. To get our accuracy-complexity frontier figures, we run the experiments
with multiple values of $\lambda$ for TSDT, Fast-TSDT and OSDT, and different
values of the depth limit for DL8.5.

  * •

For DL8.5, the depth limits range from $1$ to $6$ exactly as reported by Lin
et al., (2020).

  * •

For TSDT, Fast-TSDT and OSDT, the set of $\lambda$ values is
$0.1,0.01,0.0025,0.0001$, which is a subset of the values used by Lin et al.,
(2020). For all algorithms, we set a time limit of $10$ minutes.

In Figure 8, OSDT reaches its time limit on all the datasets except MONK1,
where the last category is dropped by the Binary Encoding. TSDT displays a
similar behaviour but in less experiments than OSDT. On the other hand, while
it is true that DL8.5 is clearly the fastest algorithm, it is also the
algorithm that exhibits the least efficient accuracy-complexity frontier. In
fact, when comparing the training accuracies in Figure 7 and the test
accuracies in Figure 5, we notice a clear overfitting trend by DL8.5 unlike
the remaining algorithms. To conclude, we argue that Fast-TSDT displays the
best trade-off between optimality and execution time.

Figure 7: Cross-validation training accuracy of TSDT, OSDT and DL8.5 as a
function of the number of leaves. Figure 8: Cross-validation execution times
of TSDT, OSDT and DL8.5 as a function of the number of leaves.

One of the main demonstrations of OSDTwas its Decision Tree solution to MONK1
Drop Last, and depicted in (Hu et al.,, 2019, Figure 6) in the comparison
against BinOCT. Fast-TSDT consistently achieves the same solution with 8
leaves, represented in Figure 10, in much less time as documented in Figure 8.
Moreover, as stated in Section 5, Hu et al., (2019) drop the last category of
each attribute in their One-Hot Encoding of MONK1. However, without some form
of prior knowledge, such choice is just arbitrary, and other options can be
considered as well. The issue that arises from this is that these different
options lead to solutions of different complexities as we explain in the
following. In Figure 18, we aim at encoding some attribute variable $X$ that
takes three possible values (categories). One-Hot Encoding encodes $X$ using
two binary variables $X_{0}$ and $X_{1}$, if we drop the last category of $X$
then we represent $X=0$ with $X_{0}=1$, and $X=1$ with $X_{1}=1$; but to
encode $X=2$ (the excluded category), we need $X_{0}=0,X_{1}=0$, which
translates into a branch with two splits. Now, let us consider the following
classification problem with
$\mathbb{P}\left[Y=1|X=2\right]=0,\mathbb{P}\left[Y=1|X\neq 2\right]=1$, then
dropping the last category during One-Hot Encoding leads to an optimal
Decision Tree with two splits, as represented in Figure 18, while dropping any
other category instead leads to an optimal Decision Tree with only one split.
In Monk 1, a similar phenomenon occurs where the choice of binary encoding has
a significant impact on the complexity of the optimal DT. Indeed, dropping the
last category leads to a simple solution with only 8 leaves, however, dropping
the first category instead leads to a more complicated ad hard to find
solution. In this case, Figures 7 and 5 clearly demonstrate that Fast-TSDT
consistently achieves a better solution than DL8.5 and OSDT. Figure 11
illustrates a 19-leaf solution that Fast-TSDTretrieves, achieving 100%
training and test accuracies, no similar solution has been found by DL8.5 and
OSDT.

Figure 9: Fast-TSDT’s solution to Monk 1 Original, the true optimal solution
of least complexity. Figure 10: Fast-TSDT’s solution to Monk 1 Drop Last, the
true optimal solution of least complexity. Figure 11: Fast-TSDT’s solution to
Monk 1 Drop First, this solution has $19$ leaves and achieves $100\%$ training
and test accuracies; DL8.5 and OSDT were unsuccessful in retrieving such
solution. Figure 12: Fast-TSDT’s solution to Monk 2, this solution has $17$
leaves and achieves $89.6\%$ training accuracy and $73.5\%$ test accuracies.
Figure 13: Fast-TSDT’s solution to Monk 3, this solution achieves $93.8\%$
training accuracy and $92\%$ test accuracy. Figure 14: Fast-TSDT’s solution to
Tic-Tac-Toe, this solution achieves $79.8\%$ training accuracy and $81.8\%$
test accuracy. Figure 15: Fast-TSDT’s solution to Car Evaluation, this
solution achieves $89.9\%$ training accuracy and $90.8\%$ test accuracy.
Figure 16: Fast-TSDT’s solution to Compas, this solution achieves $66.4\%$
training accuracy and $66\%$ test accuracy. Figure 17: Fast-TSDT’s solution to
Fico, this solution achieves $69.4\%$ training accuracy and $71.8\%$ test
accuracy. Figure 18: How the choice of which category to drop during One-Hot
Encoding influences the resulting splits.

##  Appendix C TSDT’s Backpropagation details

In this section, we present the details of the Backpropagation step performed
by our first version of TSDT. Let $T$ be an internal Search Node, which is an
internal state, and let $\textrm{Ch}\left(T\right)=\\{T_{1},\ldots,T_{m}\\}$.
We recall from Equation (11) that we have:

$\theta_{T}=\max_{1\leq j\leq
m}\Big{\\{}-\lambda\mathds{1}\Big{\\{}T_{j}\neq\overline{T}\Big{\\}}+\theta_{T_{j}}\Big{\\}}$

Following the Inductive reasoning in Section 4.2, we suppose that
$\forall{1\leq j\leq
m}:\theta_{T_{j}}\sim\mathcal{N}\left(\mu_{T_{j}},\left(\sigma_{T_{j}}\right)^{2}\right)$.
Now, $\theta_{T}$ is a maximum over Normal variables that are conditionally
independent given the observed data $\\{\left(X_{i},Y_{i}\right)\\}_{i=1}^{N}$
in $T$. We know that $\theta_{T}$ is not Normally distributed, but we can
approximate its distribution with a Gaussian as is discussed in (Sinha et
al.,, 2007). Let us first consider the case with two independent Normal
variables
$\theta_{1}\sim\mathcal{N}\left(\mu_{1},\sigma_{1}^{2}\right),\theta_{2}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}^{2}\right)$.
Let $\theta=\max\\{\theta_{1},\theta_{2}\\}$, then the mean $\mu$ and variance
$\sigma^{2}$ of $\theta$ satisfy:

$\displaystyle\mu$
$\displaystyle=\mu_{1}\Phi\left(\alpha\right)+\mu_{2}\Phi\left(-\alpha\right)+\phi\left(\alpha\right)\sigma_{m}$
(13) $\displaystyle\sigma^{2}$
$\displaystyle=\left(\mu_{1}^{2}+\sigma_{1}^{2}\right)\Phi\left(\alpha\right)+\left(\mu_{2}^{2}+\sigma_{2}^{2}\right)\Phi\left(-\alpha\right)+\left(\mu_{1}+\mu_{2}\right)\sigma_{m}\phi\left(\alpha\right)-\mu^{2}$
(14)

Where
$\sigma_{m}=\sigma_{1}^{2}+\sigma_{2}^{2},\alpha=\frac{\mu_{1}-\mu_{2}}{\sigma_{m}}$,
and $\phi$ and $\Phi$ are respectively the probability density function and
the cumulative distribution function of $\mathcal{N}\left(0,1\right)$ (see
(Clark,, 1961), (Tesauro et al.,, 2010)). The distribution of $\theta$ can be
approximated with a Normal distribution by matching their first two moments,
for short we call it Clark’s approximation; Sinha et al., (2007) provide an
error analysis of this approximation. This motivates rewriting $\theta_{T}$ as
a nested pair-wise maximum:

$\displaystyle\theta_{T}$
$\displaystyle=\max\Big{\\{}-\lambda\mathds{1}\big{\\{}T_{1}\neq\overline{T}\big{\\}}+\theta_{T_{1}},\max\\{-\lambda\mathds{1}\big{\\{}T_{2}\neq\overline{T}\big{\\}}+\theta_{T_{2}},\ldots,\max\\{-\lambda\mathds{1}\big{\\{}T_{m-1}\neq\overline{T}\big{\\}}+\theta_{T_{m-1}},$
$\displaystyle-\lambda\mathds{1}\big{\\{}T_{m}\neq\overline{T}\big{\\}}+\theta_{T_{m}}\\}\\}\ldots\Big{\\}}$

$\max\\{-\lambda\mathds{1}\Big{\\{}T_{m-1}\neq\overline{T}\Big{\\}}+\theta_{T_{m-1}},-\lambda\mathds{1}\Big{\\{}T_{m}\neq\overline{T}\Big{\\}}+\theta_{T_{m}}\\}\\}$
is a maximum of two (conditionally) independent Normal variables, thus we
approximate its distribution as a Normal with Clark’s approximation, and we
recursively use Clark’s approximation on the unfolding maximums of pairs to
approximate the posterior distribution of $\theta_{T}$ as a Normal
$\theta_{T}\sim\mathcal{N}\left(\mu_{T},\left(\sigma_{T}\right)^{2}\right)$,
$\mu_{T}$ and $\left(\sigma_{T}\right)^{2}$ are calculated with a recursive
application of equations (13) and (14). A similar approximation was used by
Tesauro et al., (2010) in the context of MCTS with a Bayesian approach, but
the policy the authors considered is not Thompson Sampling but rather a form
of UCB that uses the quantiles of the posterior distributions to derive the
index of the UCB policy.

##  Appendix D Proofs

To prove Theorem 1, we use and inductive reasoning that starts from Search
Leaves.

######  Lemma 3.

Let $T$ be a Search Leaf and time $t$ the number of times $T$ is selected,
then we have:

$\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T\right),\left(\sigma_{T}\right)^{2}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

###### Proof of Lemma 3.

Let us start with the variance as it is a simpler result to prove. From the
definition of $\alpha_{T}\left(t\right)$ and $\beta_{T}\left(t\right)$, we
have $\alpha_{T}\left(t\right)+\beta_{T}\left(t\right)=tm+1$, where we recall
that $m$ is the number of observed samples from the stream in a single
Simulation step. Therefore we have:

$\displaystyle\left(\sigma_{T}\right)^{2}$
$\displaystyle=\frac{\alpha_{T}\left(t\right)\beta_{T}\left(t\right)}{\left(\alpha_{T}\left(t\right)+\beta_{T}\left(t\right)\right)^{2}\left(\alpha_{T}\left(t\right)+\beta_{T}\left(t\right)+1\right)}$
$\displaystyle=\frac{\alpha_{T}\left(t\right)\beta_{T}\left(t\right)}{\left(tm+1\right)^{2}\left(tm+2\right)}$
$\displaystyle\leq\frac{\left(tm+1\right)^{2}}{\left(tm+1\right)^{2}\left(tm+2\right)}$
$\displaystyle\leq\frac{1}{tm+2}$

Therefore $\left(\sigma_{T}\right)^{2}$ converges, not only almost surely, but
even surely to $0$ as $t\rightarrow\infty$.

Now, let us show the result for the mean, we have:

$\mu_{T}=\frac{\alpha_{T}\left(t\right)}{tm+1}=\frac{1}{1+tm}+\frac{1}{1+tm}\sum_{i=2}^{tm}\mathds{1}\Big{\\{}\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\Big{\\}}$

We know that, for any $l\in\mathcal{L}\left(T\right)$ such that
$p\left(l\right)>0$, which are the only leaves that can contain inputs
$X_{i}$, the number of observed samples grows to infinity almost surely as
$t\rightarrow\infty$, therefore, by the Strong Law of Large numbers we have:

$\forall{k}\in\\{1\ldots,K\\}:\hat{p}_{k}^{\left(i\right)}\left(l\right)\xlongrightarrow[i\rightarrow\infty]{\textrm{a.s}}p_{k}\left(l\right)$

Which means that:

$\mathbb{P}\left[\forall{\epsilon}>0,\exists I>0,\forall{i}\geq
I,\forall{k}\in\\{1,\ldots,K\\}:\Big{|}\hat{p}_{k}^{\left(i\right)}\left(l\right)-p_{k}\left(l\right)\Big{|}\leq\epsilon\right]=1$
(15)

Take $\epsilon=\frac{1}{2}\min_{k\neq
k^{\prime}}\Big{\\{}\Big{|}p_{k}\left(l\right)-p_{k^{\prime}}\left(l\right)\Big{|}\Big{\\}}$,
in light of Equation (15) we have:

$\displaystyle\mathbb{P}\left[\exists\tau>0,\forall{i}\geq\tau,\forall{k}\in\\{1,\ldots,K\\}:\Big{|}\hat{p}_{k}^{\left(i\right)}\left(l\right)-p_{k}\left(l\right)\Big{|}\leq\epsilon\right]=1$
$\displaystyle\implies$
$\displaystyle\mathbb{P}\left[\exists\tau>0,\forall{i}\geq\tau:\textrm{Argmax}_{k}\\{p_{k}\left(l\right)\\}=\textrm{Argmax}_{k}\\{\hat{p}_{k}^{\left(i\right)}\left(l\right)\\}\right]=1$
$\displaystyle\implies$
$\displaystyle\mathbb{P}\left[\exists\tau>0,\forall{i}\geq\tau:\hat{T}_{i}\left(l\right)=T\left(l\right)\right]=1$
(16)

Let us define $\tau>0$ the random time such that:

$\forall{i}\geq\tau:\hat{T}_{i-1}\left(X_{i}\right)=T\left(X_{i}\right)$

Since Equation (16) is satisfied for all leaves
$l\in\mathcal{L}\left(T\right)$, we have
$\mathbb{P}\left[\tau<\infty\right]=1$.
Let $0<\epsilon^{\prime}<\epsilon$, we want to show that:

$\mathbb{P}\left[\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\right]=1$

By marginalising over $\tau>0$, we have:

$\displaystyle\mathbb{P}\left[\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\right]$
(17)
$\displaystyle=\sum_{t^{\prime}>0}\mathbb{P}\left[\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\Big{|}\tau=t^{\prime}\right]\mathbb{P}\left[\tau=t^{\prime}\right]$
(18)

Note that in this marginalisation, the term
$\mathbb{P}\left[\tau=\infty\right]$ is absent because
$\mathbb{P}\left[\tau=\infty\right]=0$.
From the definition of $\tau$, we can write $\mu_{T}$ as follows:

$\forall{t}>\tau:\mu_{T}=\frac{1}{1+tm}+\frac{1}{1+tm}\sum_{i=2}^{\tau
m}\mathds{1}\Big{\\{}\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\Big{\\}}+\frac{1}{1+tm}\sum_{i=\tau
m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}$

Now, given $\tau=t^{\prime}$, then for all $t>t^{\prime}$ we have the
following:

$\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\Big{|}\frac{1}{1+tm}+\frac{1}{1+tm}\sum_{i=2}^{t^{\prime}m}\mathds{1}\Big{\\{}\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}+\Big{|}\frac{1}{1+tm}\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}$

For the first term of the RHS, we have:

$\Big{|}\frac{1}{1+tm}+\frac{1}{1+tm}\sum_{i=2}^{t^{\prime}m}\mathds{1}\Big{\\{}\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}\leq\Big{|}\frac{1}{1+tm}+\frac{t^{\prime}m-1}{1+tm}\Big{|}\underset{t\rightarrow\infty}{\longrightarrow}0$

Hence, there exists $\tau_{1}>0$ such that:

$\forall{t}>\tau_{1}:\Big{|}\frac{1}{1+tm}+\frac{1}{1+tm}\sum_{i=2}^{t^{\prime}m}\mathds{1}\Big{\\{}\hat{T}_{i-1}\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}\leq\frac{\epsilon^{\prime}}{3}$

For the second term of the RHS, we bound it first as follows:

$\displaystyle\Big{|}\frac{1}{1+tm}\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}$
$\displaystyle\leq\Big{|}\frac{1}{tm-t^{\prime}m}\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}$
$\displaystyle+\Big{|}\left(\frac{1}{1+tm}-\frac{1}{tm-t^{\prime}m}\right)\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}$

By the Strong Law of Large numbers, with probability $1$, there exists
$\tau_{2}>0$ such that:

$\forall{t}>\tau_{2}:\Big{|}\frac{1}{tm-t^{\prime}m}\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\frac{\epsilon^{\prime}}{3}$

On the other hand:

$\Big{|}\left(\frac{1}{1+tm}-\frac{1}{tm-t^{\prime}m}\right)\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}\leq\frac{t^{\prime}m+1}{1+tm}\underset{t\rightarrow\infty}{\longrightarrow}0$

Therefore, there exists $\tau_{3}>0$ such that:

$\forall{t>\tau_{3}}:\Big{|}\left(\frac{1}{1+tm}-\frac{1}{tm-t^{\prime}m}\right)\sum_{i=t^{\prime}m+1}^{tm}\mathds{1}\Big{\\{}T\left(X_{i}\right)=Y_{i}\Big{\\}}\Big{|}\leq\frac{\epsilon^{\prime}}{3}$

Now take $\tau^{\prime}=\max\\{\tau_{1},\tau_{2},\tau_{3}\\}$, then we have:

$\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\frac{\epsilon^{\prime}}{3}+\frac{\epsilon^{\prime}}{3}+\frac{\epsilon^{\prime}}{3}=\epsilon^{\prime}$

Therefore, conditionally on $\tau=t^{\prime}$, with probability $1$, there
exists $\tau^{\prime}>0$ such that
$\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}$,
i.e:

$\mathbb{P}\left[\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\Big{|}\tau=t^{\prime}\right]=1$

From Equation (18), we deduce that:

$\displaystyle\forall{0<\epsilon^{\prime}<\epsilon}:\mathbb{P}\left[\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\right]=\sum_{t^{\prime}>0}\mathbb{P}\left[\tau=t^{\prime}\right]=1$
$\displaystyle\implies$
$\displaystyle\mathbb{P}\left[\forall{0<\epsilon^{\prime}<\epsilon},\exists\tau^{\prime}>0,\forall{t}>\tau^{\prime}:\Big{|}\mu_{T}-\mathcal{V}^{\pi^{*}}\left(T\right)\Big{|}\leq\epsilon^{\prime}\right]=1$
$\displaystyle\implies$
$\displaystyle\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T\right)$

∎

######  Lemma 4.

For any Search Node $T$ with $t$ the number of visits of its parent and
$N_{T}\left(t\right)$ the number of times $T$ has been visited up to time $t$,
we have:

$N_{T}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$

###### Proof of Lemma 4.

Let $P\left(T\right)$ denote the parent of $T$, for convenience, we denote
$\textrm{Ch}\left(P\left(T\right)\right)=\\{T_{1},\ldots,T_{n}\\}$ and
$T=T_{j}$, now we want to show that
$N_{T_{j}}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$.
To do so, we want to prove the following result:
$\mathbb{P}\left[\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]<1$ at all times $t$, i.e, the probability of
choosing $T_{j}$ is always non-zero. We consider the auxiliary problem with
$\textrm{Ch}^{\prime}\left(P\left(T\right)\right)=\\{T_{j},T^{\prime}\\}$
where

$\theta_{T^{\prime}}\sim\mathcal{N}\left(\mu_{T^{\prime}},\left(\sigma_{T^{\prime}}\right)^{2}\right),\mu_{T^{\prime}}=\max_{i\neq
j}\\{\mu_{T_{i}}\\}+f_{n}\left(t\right),\sigma_{T^{\prime}}=\max_{i\neq
j}\\{\sigma_{T_{i}}\\}$

Where we will define $f_{n}\left(t\right)$ such that
$\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]\geq\frac{1}{2}$ at all times $t$. In this case,
we have the following bound: $\mathbb{P}\left[\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]\leq\mathbb{P}\left[\theta_{T_{j}}\leq\theta_{T^{\prime}}\right]$.
We use the union bound:

$\displaystyle\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]\geq 1-\sum_{i\neq
j}\mathbb{P}\left[\theta_{T^{\prime}}<\theta_{T_{i}}\right]$

Since $\forall{i}\neq
j:\theta_{T^{\prime}}-\theta_{T_{i}}\sim\mathcal{N}\left(\mu_{T^{\prime}}-\mu_{T_{i}},\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{i}}\right)^{2}\right)$,
we have:

$\displaystyle\mathbb{P}\left[\theta_{T^{\prime}}<\theta_{T_{i}}\right]$
$\displaystyle=\frac{1}{2}\textrm{erfc}\left(\frac{\max_{k\neq
j}\\{\mu_{T_{k}}\\}-\mu_{T_{i}}+f_{n}\left(t\right)}{\sqrt{2\left[\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{i}}\right)^{2}\right]}}\right)$
$\displaystyle\leq\frac{1}{2}\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)$

Hence:

$\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]\geq
1-\frac{n-1}{2}\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)$

Thus, we want $f_{n}\left(t\right)$ satisfying
$\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)\leq\frac{1}{n-1}$.
Take $f_{n}\left(t\right)=g_{n}\left(t\right)\sigma_{T^{\prime}}$, hence it
suffices to take
$g_{n}\left(t\right)=2\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$ and thus
$f_{n}\left(t\right)=2\sigma_{T^{\prime}}\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$.

On the other hand, we have the following:

$\mathbb{P}\left[\theta_{T_{j}}>\theta_{T^{\prime}}\right]=\frac{1}{\sqrt{\pi}}\bigintsss_{\frac{\mu_{T^{\prime}}-\mu_{T_{j}}}{\sqrt{2\left[\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{j}}\right)^{2}\right]}}}^{\infty}e^{-u^{2}}du>0$

Therefore we deduce that:

$\forall{t}>0:\mathbb{P}\left[\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{T_{i}}\\}\right]\leq\mathbb{P}\left[\theta_{T_{j}}\leq\theta_{T^{\prime}}\right]<1$

To show that
$N_{T_{j}}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$,
we will equivalently prove:

$\mathbb{P}\left[\exists{M}>0,\forall{t}>0:N_{T_{j}}\left(t\right)<M\right]=0$

The event $\\{\exists{M}>0,\forall{t}>0:N_{T_{j}}\left(t\right)<M\\}$ can be
rewritten as the event
$\\{\exists{\tau>0},\forall{t\geq\tau}:\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{i}\\}\\}$, which means that there exists a time $\tau>0$ such
that, from then on, $T_{j}$ will never be chosen again. Therefore:

$\displaystyle\mathbb{P}\left[\exists{M}>0,\forall{t}>0:N_{T_{j}}\left(t\right)<M\right]$
$\displaystyle=\mathbb{P}\left[\exists{\tau>0},\forall{t\geq\tau}:\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{i}\\}\right]$
$\displaystyle\leq\sum_{\tau>0}\mathbb{P}\left[\forall{t\geq\tau}:\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{i}\\}\right]$
$\displaystyle\leq\sum_{\tau>0}\prod_{t\geq\tau}\mathbb{P}\left[\theta_{T_{j}}\leq\max_{i\neq
j}\\{\theta_{i}\\}\right]$
$\displaystyle\leq\sum_{\tau>0}\prod_{t\geq\tau}\mathbb{P}\left[\theta_{T_{j}}\leq\theta_{T^{\prime}}\right]$

The third line comes from the fact that $\\{\theta_{T_{i}}\\}$ are
independent. We recall that for all $t\geq\tau$:

$\displaystyle\mathbb{P}\left[\theta_{T_{j}}\leq\theta_{T^{\prime}}\right]$
$\displaystyle=\frac{1}{\sqrt{\pi}}\bigintsss_{-\infty}^{\frac{\mu_{T^{\prime}}-\mu_{T_{j}}}{\sqrt{2\left[\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{j}}\right)^{2}\right]}}}e^{-u^{2}}du\leq\frac{1}{\sqrt{\pi}}\bigintsss_{-\infty}^{\frac{1+f_{n}\left(\tau\right)-\mu_{T_{j}}}{\sqrt{2}\sigma_{T_{j}}}}e^{-u^{2}}du<1$

This comes from the fact that $\forall{1\leq i\leq n}:0\leq\mu_{i}\leq 1$ and
$f_{n}\left(t\right)$ is a decreasing function of $t$ because
$\sigma_{T^{\prime}}$ decreases with $t$. Since $\forall{t\geq\tau}:T_{j}$ is
not chosen, then $\mu_{T_{j}}$ and $\sigma_{T_{j}}$ remain constant, and
therefore:

$\prod_{t\geq\tau}\frac{1}{\sqrt{\pi}}\bigintsss_{-\infty}^{\frac{1+f_{n}\left(\tau\right)-\mu_{T_{j}}}{\sqrt{2}\sigma_{T_{j}}}}e^{-u^{2}}du=0$

Thus we deduce that:

$\mathbb{P}\left[\exists{M}>0,\forall{t}>0:N_{T_{j}}\left(t\right)<M\right]=0$

Which concludes our proof. ∎

######  Corollary 5.

Let $t$ be the number of iterations of TSDT , then the number of visits of any
Search Node diverges almost surely to $\infty$ as $t\rightarrow\infty$.

###### Proof of Corollary 5.

Corollary 5 is straightforward to prove by Induction using Lemma 4 and the
fact that $t$ is the number of visits of the Root Search Node.

∎

In what follows, let $T$ denote an internal Search Node with
$\textrm{Ch}\left(T\right)=\\{T_{1},\ldots,T_{n}\\}$ and $T_{1}$ the optimal
child, i.e $\mathcal{V}^{\pi^{*}}\left(T_{1}\right)=\max_{1\leq j\leq
n}\\{\mathcal{V}^{\pi^{*}}\left(T_{j}\right)\\}$.

######  Lemma 6.

Let time $t$ denote the number of times that $T$ has been visited. Suppose
that
$\forall{j}\in\\{1,\ldots,n\\}:\mathcal{V}^{\pi^{*}}\left(T_{j}\right)\xlongrightarrow[N_{T_{j}}\left(t\right)\rightarrow\infty]{\textrm{a.s}}\mu_{T_{j}},\sigma_{T_{j}}\xlongrightarrow[N_{T_{j}}\left(t\right)\rightarrow\infty]{\textrm{a.s}}0$
, then we have:

$\lim_{t\rightarrow\infty}\pi_{t}\left(T_{1}|T\right)=1$

_Note that we abuse the notation a little bit here. Indeed, in the main paper
$\pi_{t}$ is the policy after $t$ iterations of TSDT, but here $\pi_{t}$
denotes the policy after choosing $T$ for $t$ times._

###### Proof of Lemma 6.

We define the following events at time $t$:

$\displaystyle\mathcal{M}\left(t,\epsilon\right)$
$\displaystyle=\bigcap_{j=1}^{n}\Bigg{\\{}\Bigg{|}\mu_{T_{j}}-\mathcal{V}^{\pi^{*}}\left(T_{j}\right)\Bigg{|}\leq\epsilon\Bigg{\\}}$
$\displaystyle\mathcal{V}\left(t,\epsilon\right)$
$\displaystyle=\bigcap_{j=1}^{n}\Bigg{\\{}\left(\sigma_{T_{j}}\right)^{2}<\frac{\epsilon}{2}\Bigg{\\}}$

and $t\left(\epsilon\right)>0$ the random time such that
$\forall{t}>t\left(\epsilon\right):$ $\mathcal{M}\left(t,\epsilon\right)$ and
$\mathcal{V}\left(t,\epsilon\right)$ happen. By Lemma 4, we have
$\forall{j}\in\\{1,\ldots,n\\}:N_{T_{j}}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$,
therefore $\mathbb{P}\left[t\left(\epsilon\right)<\infty\right]=1$. Let
$i\left(t\right)$ denote the chosen child at time $t$, we have
$\mathbb{P}\left[i\left(t\right)=T_{1}\right]=\pi_{t}\left(T_{1}|T\right)$.
The introduction of $i\left(t\right)$ is purely for convenience purposes. We
write:

$\displaystyle\mathbb{P}\left[i\left(t\right)=T_{1}\right]$
$\displaystyle=\sum_{\tau>0}\mathbb{P}\left[i\left(t\right)=T_{1}\Big{|}t\left(\epsilon\right)=\tau\right]\mathbb{P}\left[t\left(\epsilon\right)=\tau\right]$
$\displaystyle\geq\sum_{1\leq\tau\leq
t}\mathbb{P}\left[i\left(t\right)=T_{1}\Big{|}t\left(\epsilon\right)=\tau\right]\mathbb{P}\left[t\left(\epsilon\right)=\tau\right]$

Conditionally on $t\left(\epsilon\right)=\tau$, for $t\geq\tau$ we have the
following:

$\displaystyle\mathbb{P}\left[i\left(t\right)=T_{1}\Big{|}t\left(\epsilon\right)\right]$
$\displaystyle=\mathbb{P}\left[\forall{j}\neq
1:\theta_{T_{1}}>\theta_{T_{j}}\Big{|}\mathcal{M}\left(t,\epsilon\right),\mathcal{V}\left(t,\epsilon\right)\right]$
$\displaystyle\geq 1-\sum_{j\neq
1}\mathbb{P}\left[\theta_{T_{1}}\leq\theta_{T_{j}}\Big{|}\mathcal{M}\left(t,\epsilon\right),\mathcal{V}\left(t,\epsilon\right)\right]$

Before we continue, we introduce the following notation $\forall{j}\neq
1:\Delta_{j}=\mathcal{V}^{\pi^{*}}\left(T_{1}\right)-\mathcal{V}^{\pi^{*}}\left(T_{j}\right)>0,\Delta=\min_{j\neq
1}\Delta_{j}$. Let $C>0$ and define $\epsilon=\frac{\Delta}{4C}$, then for all
$j\neq 1$:

$\displaystyle\mathbb{P}\left[\theta_{T_{1}}\leq\theta_{T_{j}}\Big{|}\mathcal{M}\left(t,\epsilon\right),\mathcal{V}\left(t,\epsilon\right)\right]$
$\displaystyle\leq\mathbb{P}\left[\theta_{T_{1}}\leq\theta_{T_{j}}\Bigg{|}\Big{|}\mu_{T_{1}}-\mathcal{V}^{\pi^{*}}\left(T_{1}\right)\Big{|}<\frac{\Delta_{j}}{4C},\Big{|}\mu_{T_{j}}-\mathcal{V}^{\pi^{*}}\left(T_{j}\right)\Big{|}<\frac{\Delta_{j}}{4C},\left(\sigma_{T_{1}}\right)^{2}<\frac{\Delta_{j}}{8C},\left(\sigma_{T_{j}}\right)^{2}<\frac{\Delta_{j}}{8C}\right]$
$\displaystyle\leq\frac{1}{\sqrt{\pi}}\bigintsss_{4C}^{\infty}e^{-u^{2}}du=\frac{1}{2}\textrm{erfc}\left(4C\right)$

Hence, we deduce that:

$\mathbb{P}\left[i\left(t\right)=T_{1}\Big{|}t\left(\epsilon\right)\right]\geq
1-\frac{|\textrm{Ch}\left(T\right)|-1}{2}\textrm{erfc}\left(4C\right)$

and thus:

$\mathbb{P}\left[i\left(t\right)=T_{1}\right]\geq\left[1-\frac{|\textrm{Ch}\left(T\right)|-1}{2}\textrm{erfc}\left(4C\right)\right]\sum_{1\leq\tau\leq
t}\mathbb{P}\left[t\left(\epsilon\right)=\tau\right]$

Since $\sum_{\tau\geq 1}\mathbb{P}\left[t\left(\epsilon\right)=\tau\right]=1$
(because $\mathbb{P}\left[t\left(\epsilon\right)=\infty\right]=0$), by taking
the limit, we get:

$\lim_{t\rightarrow\infty}\mathbb{P}\left[i\left(t\right)=T_{1}\right]\geq
1-\frac{|\textrm{Ch}\left(T\right)|-1}{2}\textrm{erfc}\left(4C\right)$

Since this is satisfied for all $C>0$ and
$\lim_{C\rightarrow\infty}\textrm{erfc}\left(4C\right)=0$, we deduce that:

$\lim_{t\rightarrow\infty}\mathbb{P}\left[i\left(t\right)=T_{1}\right]=\lim_{t\rightarrow\infty}\pi_{t}\left(T_{1}|T\right)=1$

∎

######  Lemma 7.

Let time $t$ denote the number of times that the parent of $T$ has been
visited. Under the same assumptions as Lemma 6, $T$ satisfies:

$\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T\right),\left(\sigma_{T}\right)^{2}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

###### Proof of Lemma 7.

By Induction on $n=|\textrm{Ch}\left(T\right)|$, if $n=2$ we have:

$\displaystyle\mu_{T}$
$\displaystyle=\mu_{T_{1}}\Phi\left(\alpha\right)+\mu_{T_{2}}\Phi\left(-\alpha\right)+\phi\left(\alpha\right)\sigma_{m}$
$\displaystyle\left(\sigma_{T}\right)^{2}$
$\displaystyle=\left[\left(\mu_{T_{1}}\right)^{2}+\left(\sigma_{T_{1}}\right)^{2}\right]\Phi\left(\alpha\right)+\left[\left(\mu_{T_{2}}\right)^{2}+\left(\sigma_{T_{2}}\right)^{2}\right]\Phi\left(-\alpha\right)+\left(\mu_{T_{1}}+\mu_{T_{2}}\right)\sigma_{m}\phi\left(\alpha\right)-\left(\mu_{T}\right)^{2}$

Where
$\sigma_{m}=\left(\sigma_{T_{1}}\right)^{2}+\left(\sigma_{T_{2}}\right)^{2},\alpha=\frac{\mu_{1}-\mu_{2}}{\sigma_{m}}$,
and $\phi$ and $\Phi$ are respectively the probability density function and
the cumulative distribution function of $\mathcal{N}\left(0,1\right)$. Using
Lemma 4, we have
$N_{T_{1}}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$
and
$N_{T_{2}}\left(t\right)\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$,
therefore
$\mu_{T_{1}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T_{1}\right),\sigma_{T_{1}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$
and
$\mu_{T_{2}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T_{2}\right),\sigma_{T_{2}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$,
which yields $\sigma_{m}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$
and $\alpha\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\infty$, using
these results with the formulas above, we deduce that:

$\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T_{1}\right)=\max\\{\mathcal{V}^{\pi^{*}}\left(T_{1}\right),\mathcal{V}^{\pi^{*}}\left(T_{2}\right)\\},\;\sigma_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

Now suppose the result holds true for some $n\geq 2$ and now consider
$\textrm{Ch}\left(T\right)=\\{T_{1},\ldots,T_{n+1}\\}$. We define
$\theta_{T^{\prime}}\left(t\right)\sim\mathcal{N}\left(\mu_{T^{\prime}},\left(\sigma_{T^{\prime}}\right)^{2}\right)$
which approximates recursively the maximum for $\\{T_{2},\ldots,T_{n+1}\\}$.
By the Induction hypothesis, we have:

$\mu_{T^{\prime}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\max\\{\mathcal{V}^{\pi^{*}}\left(T_{2}\right),\ldots,\mathcal{V}^{\pi^{*}}\left(T_{n+1}\right)\\},\;\sigma_{T^{\prime}}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

Now we have
$\theta_{T}\left(t\right)\sim\mathcal{N}\left(\mu_{T},\left(\sigma_{T}\right)^{2}\right)$
approximating the maximum for $\\{T_{1},T^{\prime}\\}$. By the Induction
hypothesis again, we have:

$\mu_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}\mathcal{V}^{\pi^{*}}\left(T_{1}\right)=\max\\{\mathcal{V}^{\pi^{*}}\left(T_{1}\right),\mathcal{V}^{\pi^{*}}\left(T^{\prime}\right)\\},\;\sigma_{T}\xlongrightarrow[t\rightarrow\infty]{\textrm{a.s}}0$

This concludes the Induction proof. ∎

###### Proof of Theorem 1.

By backward induction starting from the Search Leaves and going up to the Root
Search Node, using Lemmas 3, 4, 7 and Corollary 5, it is straightforward to
deduce the main result.

∎

######  Lemma 8.

Let $T$ be a Search Leaf, with $t$ the number of visits of its parent and
$N_{T}\left(t\right)$ the number of visits of $T$ up to time $t$. Then we
have:

$\forall{C}>|\mathcal{L}\left(T\right)|:N_{T}\left(t\right)m\leq\frac{1}{2}\left(\frac{C}{|\mathcal{L}\left(T\right)|}\right)^{\frac{1}{2}}\implies\left(\sigma_{T}\right)^{2}\geq\frac{1}{C}$

###### Proof of Lemma 8.

We have:

$\left(\sigma_{T}\right)^{2}=\sum_{l}\left(\hat{p}\left(l\right)\right)^{2}\left(\sigma_{T,l}\right)^{2};\left(\sigma_{T,l}\right)^{2}=\frac{\alpha_{T,l}\beta_{T,l}}{\left(\alpha_{T,l}+\beta_{T,l}\right)^{2}\left(1+\alpha_{T,l}+\beta_{T,l}\right)}$

Let $n_{T,l}=\sum_{i=2}^{t}\mathds{1}\\{X_{i}\in l\\}$ the number of samples
effectively observed in leaf $l$ of $T$ up to the $t^{\textrm{th}}$ visit of
the parent of $T$. Then from Equation (5) and (6), we have the following
$\alpha_{T,l}+\beta_{T,l}=2+n_{T,l}$ and
$\alpha_{T,l}\beta_{T,l}=\alpha_{T,l}\left(2+n_{T,l}-\alpha_{T,l}\right)$
knowing that $1\leq\alpha_{T,l}\leq 1+n_{T,l}$.
Consider the function $f:x\mapsto x\left(2+n_{T,l}-x\right)$ defined on
$\left[1,1+n_{T,l}\right]$, $f$ has a minimum
$f\left(1\right)=f\left(1+n_{T,l}\right)=1+n_{T,l}$, and therefore:

$\left(\sigma_{T,l}\right)^{2}\geq\frac{1+n_{T,l}}{\left(2+n_{T,l}\right)^{2}\left(3+n_{T,l}\right)}$

Now consider the function
$g:x\mapsto\frac{1+x}{\left(2+x\right)^{2}\left(3+x\right)}$ defined for
$x\geq 0$, $g$ is differentiable on $\mathbb{R}^{*}_{+}$ and
$g^{\prime}\left(x\right)=\frac{-2-6x-2x^{2}}{\left(2+x\right)^{3}\left(3+x\right)^{2}}<0$,
hence $g$ is decreasing. Therefore, for $\mathcal{C}>n_{T,l}$ we get:

$\left(\sigma_{T,l}\right)^{2}\geq g\left(n_{T,l}\right)\geq
g\left(\mathcal{C}\right)$

Furthermore, the total number of observed samples in $T$ is obviously larger
than the number of observed samples in leaf $l\in\mathcal{L}\left(l\right)$,
thus $n_{T,l}\leq
N_{T}\left(t\right)m\leq\frac{1}{2}\sqrt{\frac{C}{|\mathcal{L}\left(T\right)|}}$.
Let us choose $\mathcal{C}>5$, this leads to:

$\displaystyle\left(\sigma_{T}\right)^{2}$ $\displaystyle\geq
g\left(\mathcal{C}\right)\sum_{l\in\mathcal{L}\left(T\right)}\hat{p}\left(l\right)$
$\displaystyle\left(\sigma_{T}\right)^{2}$
$\displaystyle\geq\frac{1}{|\mathcal{L}\left(T\right)|}\frac{1+\mathcal{C}}{\left(2+\mathcal{C}\right)^{2}\left(3+\mathcal{C}\right)}$
$\displaystyle\geq\frac{1}{|\mathcal{L}\left(T\right)|}\frac{\mathcal{C}}{\left(\sqrt{2}\mathcal{C}\right)^{2}\left(2\mathcal{C}\right)}$
$\displaystyle\geq\frac{1}{4^{|}\mathcal{L}\left(T\right)|\mathcal{C}^{2}}$

The second inequality comes from the fact that the uniform distribution
minimises the collision probability.

By taking
$\mathcal{C}=\frac{1}{2}\left(\frac{C}{|\mathcal{L}\left(T\right)|}\right)^{\frac{1}{2}}$,
we deduce the result of the Lemma.

∎

###### Proof of Theorem 2.

Let us first consider the case with $n=2$, i.e
$\textrm{Ch}\left(T\right)=\\{T_{1},T_{2}\\}$ and then we will generalise the
result for an arbitrary $n\geq 2$. We have $M_{2}=1$, thus we want to show
that:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{2}\right)|}\right]\leq\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\left(\sqrt{\frac{\log
t}{4}}+\sqrt{\frac{\log t}{4}+2}\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{2}\right)|}\right)^{2}\right]$

The result will be valid for $T_{1}$ as well without loss of generality.

At time $t$, child $T_{2}$ is chosen if $\theta_{T_{2}}\geq\theta_{T_{1}}$,
which motivates us to study
$\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\right]$:
We know that
$\theta_{T_{2}}-\theta_{T_{1}}\sim\mathcal{N}\left(\mu_{T_{2}}-\mu_{T_{1}},\left(\sigma_{T_{2}}\right)^{2}+\left(\sigma_{T_{1}}\right)^{2}\right)$,
hence:

$\displaystyle\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\right]$
$\displaystyle=\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\mu_{T_{2}}<\mu_{T_{1}}\right]\mathbb{P}\left[\mu_{T_{2}}<\mu_{T_{1}}\right]+\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\mu_{T_{2}}\geq\mu_{T_{1}}\right]\mathbb{P}\left[\mu_{T_{2}}\geq\mu_{T_{1}}\right]$

Since
$\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\mu_{T_{2}}<\mu_{T_{1}}\right]\leq\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\mu_{T_{2}}\geq\mu_{T_{1}}\right]$,
we have:

$\displaystyle\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\right]$
$\displaystyle\geq\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\mu_{T_{2}}<\mu_{T_{1}}\right]$
$\displaystyle\geq\frac{1}{\sqrt{\pi}}\bigintsss_{\frac{\mu_{T_{1}}-\mu_{T_{2}}}{\sqrt{2\left[\left(\sigma_{T_{1}}\right)^{2}+\left(\sigma_{T_{2}}\right)^{2}\right]}}}^{\infty}e^{-u^{2}}du$
$\displaystyle\geq\frac{1}{\sqrt{\pi}}\bigintsss_{\frac{\mu_{T_{1}}-\mu_{T_{2}}}{\sqrt{2\left(\sigma_{T_{2}}\right)^{2}}}}^{\infty}e^{-u^{2}}du$

In what follows, we consider
$N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T\right)|}$, and we
will define $C$ as a function of $t$ later. According to Lemma 8 we have
$\left(\sigma_{T_{2}}\right)^{2}\geq\frac{|\mu_{T_{1}}-\mu_{T_{2}}|}{C}$, thus
$\frac{\mu_{T_{1}}-\mu_{T_{2}}}{\sqrt{2\left(\sigma_{T_{2}}\right)^{2}}}\leq\sqrt{\frac{C\left(\mu_{T_{1}}-\mu_{T_{2}}\right)}{2}}\leq\sqrt{\frac{C}{2}}$
since by definition, all the means $\mu_{T_{i}}\in\left[0,1\right]$. This
leads to:

$\displaystyle\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\left(\sigma_{T_{2}}\right)^{2}\geq\frac{|\mu_{T_{1}}-\mu_{T_{2}}|}{C}\right]$
$\displaystyle\geq\frac{1}{\sqrt{\pi}}\bigintsss_{\sqrt{\frac{C}{2}}}^{\infty}e^{-u^{2}}du$
$\displaystyle\geq\frac{1}{2}\textrm{erfc}\left(\sqrt{\frac{C}{2}}\right)$

$\textrm{erfc}\left(.\right)$ denotes the complementary error function. Using
the lower bound in (Kschischang,, 2017), we deduce that:

$\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Big{|}\left(\sigma_{T_{2}}\right)^{2}\geq\frac{|\mu_{T_{1}}-\mu_{T_{2}}|}{C}\right]\geq\frac{1}{2}\textrm{erfc}\left(\sqrt{\frac{C}{2}}\right)\geq\frac{\exp\left(\frac{-C}{2}\right)}{\sqrt{\pi}\left(\sqrt{\frac{C}{2}}+\sqrt{\frac{C}{2}+2}\right)}$
(19)

Since $\forall{t^{\prime}}\leq t:N_{T_{2}}\left(t^{\prime}\right)\leq
N_{T_{2}}\left(t\right)$, we have
$N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T\right)|}\implies
N_{T_{2}}\left(t^{\prime}\right)m\leq\frac{C}{2|\mathcal{L}\left(T\right)|}\implies\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{1}}-\mu_{T_{2}}\Big{|}}{C}$,
and Inequality (19) holds for all $1\leq t^{\prime}\leq t$. Hence we write:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|}\right]$
$\displaystyle=\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|},\left(\sigma_{T_{2}}\right)^{2}\geq\frac{|\mu_{T_{2}}-\mu_{T_{1}}|}{C}\right]$
$\displaystyle=\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|},\forall{1\leq
t^{\prime}\leq
t}:\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\right]$
$\displaystyle\leq\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|}\Bigg{|}\forall{1\leq
t^{\prime}\leq
t}:\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\right]$

Given the event $\Bigg{\\{}\forall{1\leq t^{\prime}\leq
t}:\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\Bigg{\\}}$,
at each time $1\leq t^{\prime}\leq t:T_{2}$ is chosen with probability
$\mathbb{P}\left[\theta_{T_{2}}\geq\theta_{T_{1}}\Bigg{|}\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\right]$.
Let
$\mathcal{C}=\frac{\exp\left(\frac{-C}{2}\right)}{\sqrt{\pi}\left(\sqrt{\frac{C}{2}}+\sqrt{\frac{C}{2}+2}\right)}$
and define the i.i.d. random variables $Z_{1},\ldots,Z_{t}$ such that
$\forall{i}:Z_{i}\sim\textrm{Bernoulli}\left(\mathcal{C}\right)$.
Inequality (19) and Lemma 8 lead to:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|}\right]$
$\displaystyle=\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|},\forall{1\leq
t^{\prime}\leq
t}:\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\right]$
$\displaystyle\leq\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|}\Bigg{|}\forall{1\leq
t^{\prime}\leq
t}:\left(\sigma_{T_{2}}\right)^{2}\geq\frac{\Big{|}\mu_{T_{2}}-\mu_{T_{1}}\Big{|}}{C}\right]$
$\displaystyle\leq\mathbb{P}\left[\sum_{i=1}^{t}Z_{i}\leq\frac{C}{2m|\mathcal{L}\left(T_{2}\right)|}\right]$

Using Hoeffding’s inequality, for $\epsilon>0$ we have
$\mathbb{P}\left[\sum_{i=1}^{t}Z_{i}-t\mathcal{C}\leq-\epsilon\right]\leq\exp\left(-\frac{2\epsilon^{2}}{t}\right)$.
Thus, by setting
$\epsilon=t\mathcal{C}-\frac{C}{2m|\mathcal{L}\left(T_{2}\right)|}>0$, we
deduce:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{C}{2|\mathcal{L}\left(T_{2}\right)|}\right]$
$\displaystyle\leq\mathbb{P}\left[\sum_{i=1}^{t}Z_{i}\leq\frac{C}{2m|\mathcal{L}\left(T_{2}\right)|}\right]$
$\displaystyle\leq\exp\left(-\frac{2\left(t\mathcal{C}-\frac{C}{2m|\mathcal{L}\left(T_{2}\right)|}\right)^{2}}{t}\right)$

Now let us find an adequate expression of $C$ as a function of $t$, hence we
will write $\mathcal{C}\left(t\right),C\left(t\right)$.
We recall that
$\epsilon=t\mathcal{C}-\frac{C\left(t\right)}{2m|\mathcal{L}\left(T_{2}\right)|}>0$,
thus a first condition is to have
$C\left(t\right)<2m|\mathcal{L}\left(T_{2}\right)|t\mathcal{C}$, which means
that $C\left(t\right)$ has to be sublinear.
Recall that
$\mathcal{C}\left(t\right)=\frac{\exp\left(\frac{-C\left(t\right)}{2}\right)}{\sqrt{\pi}\left(\sqrt{\frac{C\left(t\right)}{2}}+\sqrt{\frac{C\left(t\right)}{2}+2}\right)}$,
thus:

$\displaystyle C\left(t\right)$
$\displaystyle<2m|\mathcal{L}\left(T_{2}\right)|t\frac{\exp\left(\frac{-C\left(t\right)}{2}\right)}{\sqrt{\pi}\left(\sqrt{\frac{C\left(t\right)}{2}}+\sqrt{\frac{C\left(t\right)}{2}+2}\right)}$
$\displaystyle\frac{\sqrt{\pi}}{2m|\mathcal{L}\left(T_{2}\right)|}C\left(t\right)\left(\sqrt{\frac{C\left(t\right)}{2}}+\sqrt{\frac{C\left(t\right)}{2}+2}\right)$
$\displaystyle<t\exp\left(-\frac{C\left(t\right)}{2}\right)$

For any $\alpha>0$, we cannot have $C\left(t\right)=t^{\alpha}$ because the
RHS would converge to $0$ as $t\rightarrow\infty$ while the LHS would diverge
to $\infty$. Hence, we consider $C\left(t\right)=a\log t$ for some $a>0$.

$\displaystyle\frac{\sqrt{\pi}}{2m|\mathcal{L}\left(T_{2}\right)|}a\log\left(t\right)\left(\sqrt{\frac{a\log
t}{2}}+\sqrt{\frac{a\log t}{2}+2}\right)$
$\displaystyle<t\exp\left(-\frac{a\log t}{2}\right)$
$\displaystyle<t^{1-\frac{a}{2}}$

Thus we must have $0<a<2$.

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{a\log
t}{2|\mathcal{L}\left(T_{2}\right)|}\right]$
$\displaystyle\leq\exp\left(-\frac{2\left(\frac{t^{1-\frac{a}{2}}}{\sqrt{\pi}\left(\sqrt{\frac{a\log
t}{2}}+\sqrt{\frac{a\log t}{2}+2}\right)}-\frac{a\log
t}{2m|\mathcal{L}\left(T_{2}\right)|}\right)^{2}}{t}\right)$

Since
$\frac{2}{t}\left(\frac{t^{1-\frac{a}{2}}}{\sqrt{\pi}\left(\sqrt{\frac{a\log
t}{2}}+\sqrt{\frac{a\log t}{2}+2}\right)}-\frac{a\log
t}{2m|\mathcal{L}\left(T_{2}\right)|}\right)^{2}=\mathcal{O}\left(t^{1-a}\right)$,
we must have $0<a<1$; by taking $a=\frac{1}{2}$, we get:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{2}\right)|}\right]\leq\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\left(\sqrt{\frac{\log
t}{4}}+\sqrt{\frac{\log t}{4}+2}\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{2}\right)|}\right)^{2}\right]$

Following the exact same steps, we can show that if
$|\mu_{T_{2}}-\mu_{T_{1}}|\leq M$ where $M>0$ some constant, we would have:

$\displaystyle\mathbb{P}\left[N_{T_{2}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{2}\right)|M}\right]\leq\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\left(\sqrt{\frac{\log
t}{4}}+\sqrt{\frac{\log t}{4}+2}\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{2}\right)|M^{2}}\right)^{2}\right]$

This result constitutes our induction hypothesis for the following
generalisation.

Let us now address the setting with
$\textrm{Ch}\left(T\right)=\\{T_{1},\ldots,T_{n}\\}$ where $n\geq 2$, and let
$i\in\\{1,\ldots,n\\}$. Our idea is to transform this problem into a problem
with two children and use the induction hypothesis.
We consider a new child $T^{\prime}$ with parameters
$\theta_{T^{\prime}}\sim\mathcal{N}\left(\mu_{T^{\prime}},\left(\sigma_{T^{\prime}}\right)^{2}\right)$
such that:

$\displaystyle\mu_{T^{\prime}}$ $\displaystyle=\max_{j\neq
i}\\{\mu_{T_{j}}\\}+f_{n}\left(t\right)$ $\displaystyle\sigma_{T^{\prime}}$
$\displaystyle=\max_{j\neq i}\\{\sigma_{T_{j}}\\}$

$f_{n}\left(t\right)$ is a function that we will derive later on.
Consider the setting with the new set of children
$\textrm{Ch}^{\prime}\left(T\right)=\\{T_{i}^{\prime},T^{\prime}\\}$ where
$\theta_{T_{i}}=\theta_{T_{i}^{\prime}}$ and
$|\mathcal{L}\left(T_{i}\right)|=|\mathcal{L}\left(T^{\prime}_{i}\right)|$.
For any $C>0$, we want $\mathbb{P}\left[N_{T_{i}}\left(t\right)m\leq
C\right]\leq\mathbb{P}\left[N_{T_{i}^{\prime}}\left(t\right)m\leq C\right]$,
to achieve this, it suffices to have
$\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{j\neq
i}\\{\theta_{T_{j}}\\}\right]\geq\frac{1}{2}$ because it means that the
probability of choosing $T_{i}^{\prime}$ in the problem with
$\textrm{Ch}^{\prime}\left(T\right)$ is lower than the probability of choosing
$T_{i}$ in the problem with $\textrm{Ch}\left(T\right)$, which leads to
$\mathbb{P}\left[N_{T_{i}}\left(t\right)m\leq
C\right]\leq\mathbb{P}\left[N_{T_{i}^{\prime}}\left(t\right)m\leq C\right]$.
Using the union bound, we have:

$\displaystyle\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{j\neq
i}\\{\theta_{T_{j}}\\}\right]\geq 1-\sum_{j\neq
i}\mathbb{P}\left[\theta_{T^{\prime}}<\theta_{T_{j}}\right]$

Since $\forall{j}\neq
i:\theta_{T^{\prime}}-\theta_{T_{j}}\sim\mathcal{N}\left(\mu_{T^{\prime}}-\mu_{T_{j}},\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{j}}\right)^{2}\right)$,
we have:

$\displaystyle\mathbb{P}\left[\theta_{T^{\prime}}<\theta_{T_{j}}\right]$
$\displaystyle=\frac{1}{2}\textrm{erfc}\left(\frac{\max_{k\neq
i}\\{\mu_{T_{k}}\\}-\mu_{T_{j}}+f_{n}\left(t\right)}{\sqrt{2\left[\left(\sigma_{T^{\prime}}\right)^{2}+\left(\sigma_{T_{j}}\right)^{2}\right]}}\right)$
$\displaystyle\leq\frac{1}{2}\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)$

Hence:

$\mathbb{P}\left[\theta_{T^{\prime}}\geq\max_{j\neq
i}\\{\theta_{T_{j}}\\}\right]\geq
1-\frac{n-1}{2}\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)$

Thus, we want $f_{n}\left(t\right)$ satisfying
$\textrm{erfc}\left(\frac{f_{n}\left(t\right)}{2\sigma_{T^{\prime}}}\right)\leq\frac{1}{n-1}$.
Take $f_{n}\left(t\right)=g_{n}\left(t\right)\sigma_{T^{\prime}}$, hence it
suffices to take
$g_{n}\left(t\right)=2\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$ and thus

$f_{n}\left(t\right)=2\sigma_{T^{\prime}}\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$

In order to use the induction hypothesis, let us bound
$\Big{|}\mu_{T^{\prime}}-\mu_{T_{j}}\Big{|}$:

$\displaystyle\Big{|}\mu_{T^{\prime}}-\mu_{T_{j}}\Big{|}$
$\displaystyle=\Big{|}\max_{j\neq
i}\\{\mu_{T_{j}}\\}+f_{n}\left(t\right)-\mu_{T_{i}}\left(t\right)\Big{|}$
$\displaystyle\leq
1+2\sigma_{T^{\prime}}\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$

For any $j\neq i$, we have
$\left(\sigma_{T_{j}}\right)^{2}\leq\sqrt{\frac{1}{12}}$, thus
$\Big{|}\mu_{T^{\prime}}-\mu_{T_{j}}\Big{|}\leq
1+\sqrt{\frac{2}{\sqrt{3}}}\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$.
By defining
$M_{n}=1+\sqrt{\frac{2}{\sqrt{3}}}\textrm{erfc}^{-1}\left(\frac{1}{n-1}\right)$,
we use the induction hypothesis to deduce that:

$\displaystyle\mathbb{P}\left[N_{T_{i}^{\prime}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{i}^{\prime}\right)|M_{n}}\right]\leq\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\left(\sqrt{\frac{\log
t}{4}}+\sqrt{\frac{\log t}{4}+2}\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{1}^{\prime}\right)|M_{n}^{2}}\right)^{2}\right]$

Since $\mathbb{P}\left[N_{T_{i}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{i}\right)|M_{n}}\right]\leq\mathbb{P}\left[N_{T_{i}^{\prime}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{i}^{\prime}\right)|M_{n}}\right]$, we deduce that:

$\displaystyle\mathbb{P}\left[N_{T_{i}}\left(t\right)m\leq\frac{\log
t}{4|\mathcal{L}\left(T_{i}\right)|M_{n}}\right]\leq\exp\left[-\frac{2}{t}\left(\frac{t^{3/4}}{\sqrt{\pi}\left(\sqrt{\frac{\log
t}{4}}+\sqrt{\frac{\log t}{4}+2}\right)}-\frac{\log
t}{4m|\mathcal{L}\left(T_{i}\right)|M_{n}^{2}}\right)^{2}\right]$

∎