Abstract
In this work, we consider the popular treebased search strategy within theframework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in thecontext of infinitehorizon discounted cost Markov Decision Process (MDP).While MCTS is believed to provide an approximate value function for a givenstate with enough simulations, the claimed proof in the seminal works isincomplete. This is due to the fact that the variant, the Upper ConfidenceBound for Trees (UCT), analyzed in prior works utilizes "logarithmic" bonusterm for balancing exploration and exploitation within the treebased search,following the insights from stochastic multiarm bandit (MAB) literature. Ineffect, such an approach assumes that the regret of the underlying recursivelydependent nonstationary MABs concentrates around their mean exponentially inthe number of steps, which is unlikely to hold as pointed out in literature,even for stationary MABs. As the key contribution of this work, we establishpolynomial concentration property of regret for a class of nonstationary MAB.This in turn establishes that the MCTS with appropriate polynomial rather thanlogarithmic bonus term in UCB has the claimed property. Using this as abuilding block, we argue that MCTS, combined with nearest neighbor supervisedlearning, acts as a "policy improvement" operator: it iteratively improvesvalue function approximation for all states, due to combining with supervisedlearning, despite evaluating at only finitely many states. In effect, weestablish that to learn an $\varepsilon$ approximation of the value functionwith respect to $\ell_\infty$ norm, MCTS combined with nearest neighborrequires a sample size scaling as$\widetilde{O}\big(\varepsilon^{(d+4)}\big)$, where $d$ is the dimension ofthe state space. This is nearly optimal due to a minimax lower bound of$\widetilde{\Omega}\big(\varepsilon^{(d+2)}\big)$.
Quick Read (beta)
[10pt]
NonAsymptotic Analysis of Monte Carlo Tree Search
Devavrat Shah
LIDS, Massachusetts Institute of Technology, Cambridge, MA 02139, [email protected]u
Qiaomin Xie
ORIE, Cornell University, Ithaca, NY 14853, [email protected]
Zhi Xu
LIDS, Massachusetts Institute of Technology, Cambridge, MA 02139, [email protected]
In this work, we consider the popular treebased search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of infinitehorizon discounted cost Markov Decision Process (MDP). While MCTS is believed to provide an approximate value function for a given state with enough simulations, cf. Kocsis and Szepesvári (2006), Kocsis et al. (2006), the claimed proof of this property is incomplete. This is due to the fact that the variant of MCTS, the Upper Confidence Bound for Trees (UCT), analyzed in prior works utilizes “logarithmic” bonus term for balancing exploration and exploitation within the treebased search, following the insights from stochastic multiarm bandit (MAB) literature, cf. Agrawal (1995), Auer et al. (2002). In effect, such an approach assumes that the regret of the underlying recursively dependent nonstationary MABs concentrates around their mean exponentially in the number of steps, which is unlikely to hold as pointed out in Audibert et al. (2009), even for stationary MABs.
As the key contribution of this work, we establish polynomial concentration property of regret for a class of nonstationary MultiArm Bandits (MAB). This in turn establishes that the MCTS with appropriate polynomial rather than logarithmic bonus term in UCB has the claimed property of Kocsis and Szepesvári (2006), Kocsis et al. (2006). Interestingly enough, empirically successful approaches (cf. Silver et al. (2017b)) utilize a similar polynomial form of MCTS as suggested by our result. Using this as a building block, we argue that MCTS, combined with nearest neighbor supervised learning, acts as a “policy improvement” operator, i.e., it iteratively improves value function approximation for all states, due to combining with supervised learning, despite evaluating at only finitely many states. In effect, we establish that to learn an $\epsilon $ approximation of the value function with respect to ${\mathrm{\ell}}_{\mathrm{\infty}}$ norm, MCTS combined with nearest neighbor requires a sample size scaling as $\stackrel{~}{O}\left({\epsilon}^{(d+4)}\right)$, where $d$ is the dimension of the state space. This is nearly optimal due to a minimax lower bound of $\stackrel{~}{\mathrm{\Omega}}\left({\epsilon}^{(d+2)}\right)$, suggesting the strength of the variant of MCTS we propose here and our resulting analysis.^{†}^{†}thanks: An extended abstract of this paper is accepted for presentation at ACM SIGMETRICS 2020.
Key words: Monte Carlo Tree Search, Non Stationary MultiArm Bandit, Reinforcement Learning
Monte Carlo Tree Search (MCTS) is a search framework for finding optimal decisions, based on the search tree built by random sampling of the decision space (Browne et al. 2012). MCTS has been widely used in sequential decision makings that have a tree representation, exemplified by games and planning problems. Since MCTS was first introduced, many variations and enhancements have been proposed. Recently, MCTS has been combined with deep neural networks for reinforcement learning, achieving remarkable success for games of Go (Silver et al. 2016, 2017b), chess and shogi (Silver et al. 2017a). In particular, AlphaGo Zero (AGZ) (Silver et al. 2017b) employs supervised learning to learn a policy/value function (represented by a neural network) based on samples generated via MCTS; the neural network is recursively used to estimate the value of leaf nodes in the next iteration of MCTS for simulation guidance.
Despite the wide application and empirical success of MCTS, there is only limited work on theoretical guarantees of MCTS and its variants. One exception is the work of Kocsis and Szepesvári (2006) and Kocsis et al. (2006), which propose running tree search by applying the Upper Confidence Bound algorithm — originally designed for stochastic multiarm bandit (MAB) problems (Agrawal 1995, Auer et al. 2002) — to each node of the tree. This leads to the socalled UCT (Upper Confidence Bounds for Trees) algorithm, which is one of the popular forms of MCTS. In Kocsis and Szepesvári (2006), certain asymptotic optimality property of UCT is claimed. The proof therein is, however, incomplete, as we discuss in greater details in Section id1. More importantly, UCT as suggested in Kocsis and Szepesvári (2006) requires exponential concentration of regret for the underlying nonstationary MAB, which is unlikely to hold in general even for stationary MAB as pointed out in Audibert et al. (2009).
Indeed, rigorous analysis of MCTS is subtle, even though its asymptotic convergence may seem natural. A key challenge is that the tree policy (e.g., UCT) for selecting actions typically needs to balance exploration and exploitation, so the random sampling process at each node is nonstationary (nonuniform) across multiple simulations. A more severe difficulty arises due to the hierarchical/iterative structure of tree search, which induces complicated probabilistic dependency between a node and the nodes within its subtree. Specifically, as part of simulation within MCTS, at each intermediate node (or state), the action is chosen based on the outcomes of the past simulation steps within the subtree of the node in consideration. Such strong dependencies across time (i.e., depending on the history) and space (i.e., depending on the subtrees downstream) among nodes makes the analysis nontrivial.
The goal of this paper is to provide a rigorous theoretical foundation for MCTS. In particular, we are interested in the following:
 •

•
Can we rigorously establish the “strong policy improvement” property of MCTS when combined with supervised learning as observed in the literature (e.g., in Silver et al. (2017b))? If yes, what is the quantitative form of it?

•
Does supervised learning combined with MCTS lead to the optimal policy, asymptotically? If so, what is its finitesample (nonasymptotic) performance?
As the main contribution of this work, we provide affirmative answers to all of the above questions. In what follows, we provide a brief overview of our contributions and results.
Nonstationary MAB and recursive polynomial concentration. In stochastic Multi Arm Bandit (MAB), the goal is to discover amongst finitely many actions (or arms), the one with the best average reward while choosing as few nonoptimal actions as possible in the process. The rewards for any given arm are assumed to be independent and identically distributed (i.i.d.). The usual exponential concentration for such i.i.d. and hence stationary processes leads to UCB algorithm with a logarithmic bonus term: at each time, choose action with maximal index (ties broken arbitrarily), where the index of an arm is defined as the empirical mean reward plus constant times $\sqrt{\mathrm{log}t/s}$, where $t$ is the total number of trials so far and $s\le t$ is the number of times the particular action is chosen in these $t$ trials.
The goal in the Monte Carlo Tree Search (MCTS) is very similar to the MAB setup described above – choose an action at a given query state that gives the best average reward. However, the reward depends on the future actions. Therefore, to determine the best action for the given state, one has to take future actions into account and MCTS does this by simulating future via effectively expanding all possible future actions recursively in the form of (decisionlike) trees. In essence, the optimal action at the root of such a tree is determined by finding optimal path in the tree. And determining this optimal path requires solving multiple MABs, one per each intermediate node within the tree. Apart from the MABs associated with the lowest layer of the tree, all the MABs associated with the intermediate nodes turn out to have rewards that are the rewards generated by MAB algorithms for nodes downstream. This creates complicated, hierarchically interdependent MABs.
To determine the appropriate, UCBlike index algorithm for each node of the MCTS tree, it is essential to understand the concentration property of the rewards, i.e., concentration of regret for MABs associated with nodes downstream. While the rewards at leaf level may enjoy exponential concentration due to independence, the regret of any algorithm even for such an MAB is unlikely to have exponential concentration in general, cf. Audibert et al. (2009), Salomon and Audibert (2011). Further, the MAB of our interest has nonstationary rewards due to strong dependence across hierarchy. Indeed, an oversight of this complication led Kocsis and Szepesvári (2006), Kocsis et al. (2006) to suggest UCT inspired by the standard UCB algorithm for MABs with stationary, independent rewards.
As an important contribution of this work, we formulate an appropriate form of nonstationary MAB which correctly models the MAB at each of the node in the MCTS tree. For such a nonstationary MAB, we define UCB algorithm with appropriate index and under which we establish appropriate concentration of the induced regret. This, in turn, allows us to recursively define the UCT algorithm for MCTS by appropriately defining index for each of the nodeaction within the MCTS tree. Here we provide a brief summary.
Given $[K]=\{1,\mathrm{\dots},K\}$ actions or arms, let ${X}_{i,t}$ denote the reward generated by playing arm $i\in [K]$ for the $t$th time. Let empirical mean over $n$ trials for arm $i$ be ${\overline{X}}_{i,n}=\frac{1}{n}{\sum}_{t=1}^{n}{X}_{i,t}$, and let ${\mu}_{i,n}=\mathbb{E}[{\overline{X}}_{i,n}]$ be its expectation. Suppose ${\mu}_{i,n}\to {\mu}_{i}$ as $n\to \mathrm{\infty}$ for all $i\in [K]$ and let there exist constants, $\beta >1$, $\xi >0$, and $$ such that for every $z\ge 1$ and every integer $n\ge 1$,
$\mathbb{P}(n{\overline{X}}_{i,n}n{\mu}_{i}\ge {n}^{\eta}z)$  $\le {\displaystyle \frac{\beta}{{z}^{\xi}}}.$ 
Note that for i.i.d. bounded rewards, above holds for $\eta =1/2$ for any finite $\xi $ due to exponential concentration. We propose to utilize the UCB algorithm where at time $t$, the arm ${I}_{t}$ is chosen according to
$${I}_{t}\in \mathrm{arg}\underset{i\in [K]}{\mathrm{max}}\left\{{\overline{X}}_{i,{T}_{i}(t1)}+{B}_{t1,{T}_{i}(t1)}\right\},$$  (1) 
where ${T}_{i}(t)={\sum}_{l=1}^{t}\mathbb{I}\{{I}_{l}=i\}$ is the number of times arm $i$ has been played, up to (including) time $t$, and the bias or bonus term ${B}_{t,s}$ is defined as
$${B}_{t,s}=\frac{{\beta}^{1/\xi}\cdot {t}^{\eta (1\eta )}}{{s}^{1\eta}}.$$ 
Let ${\mu}_{*}={\mathrm{max}}_{i\in [K]}{\mu}_{i}$ and let ${\overline{X}}_{n}$ denote the empirical average of the rewards collected. Then, we establish that $\mathbb{E}[{\overline{X}}_{n}]$ converges to ${\mu}_{*}$, and that for every $n\ge 1$ and every $z\ge 1$, a similar polynomial concentration holds:
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {n}^{\eta}z)$  $\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ 
where ${\xi}^{\prime}=\xi \eta (1\eta )1$, and ${\beta}^{\prime}>1$ is a large enough constant. The precise statement can be found as Theorem 3 in Section id1.
Corrected UCT for MCTS and nonasymptotic analysis. For MCTS, as discussed above, the leaf nodes have rewards that can be viewed as generated per standard stationary MAB. Therefore, the rewards for each arm (or action) at the leaf level in MCTS satisfy the required concentration property with $\eta =1/2$ due to independence. Hence, from our result for nonstationary MAB, we immediately obtain that we can recursively apply the UCB algorithm per (1) at each level in the MCTS with $\eta =1/2$ and appropriately adjusted constants $\beta $ and $\xi $. In effect, we obtain modified UCT where the bias or bonus term ${B}_{t,s}$ scales as ${t}^{1/4}/{s}^{1/2}$. This is in constrast to ${B}_{t,s}$ scaling as $\sqrt{\mathrm{log}t/s}$ in the standard UCB as well as UCT suggested in the literature, cf. Kocsis and Szepesvári (2006), Kocsis et al. (2006).
By recursively applying the convergence and concentration property of the nonstationary MAB for the resulting algorithm for MCTS, we establish that for any query state $s$ of the MDP, using $n$ simulations of the MCTS, we can obtain a value function estimation within error $\delta {\epsilon}_{0}+O\left({n}^{1/2}\right)$, if we start with a value function estimation for all the leaf nodes within error ${\epsilon}_{0}$ for some $$ (independent of $n$, dependent on depth of MCTS tree). That is, MCTS is indeed asymptotically correct as was conjectured in the prior literature. For details, see Theorem 1 in Section id1.
MCTS with supervised learning, strong policy improvement, and near optimality. The result stated above for MCTS implies its “bootstrapping” property – if we start with a value function estimation for all state within error $\epsilon $, then MCTS can produce estimation of value function for a given query state within error less than $\epsilon $ with enough simulations. By coupling such improved estimations of value function for a number of query states, combined with expressive enough supervised learning, one can hope to generalize such improved estimations of value function for all states. That is, MCTS coupled with supervised learning can be “strong policy improvement operator”.
Indeed, this is precisely what we establish by utilizing nearest neighbor supervised learning. Specifically, we establish that with $\stackrel{~}{O}\left(\frac{1}{{\epsilon}^{4+d}}\right)$ number of samples, MCTS with nearest neighbor finds an $\epsilon $ approximation of the optimal value function with respect to ${\mathrm{\ell}}_{\mathrm{\infty}}$norm; here $d$ is the dimension of the state space. This is nearly optimal in view of a minimax lower bound of $\stackrel{~}{\mathrm{\Omega}}\left(\frac{1}{{\epsilon}^{2+d}}\right)$ (Shah and Xie 2018). For details, see Theorem 2 in Section id1.
An Implication. As mentioned earlier, the modified UCT policy per our result suggests using bias or bonus term ${B}_{t,s}$ that scales as ${t}^{1/4}/{s}^{1/2}$ at each node within the MCTS. Interestingly enough, the empirical results of AGZ are obtained by utilizing ${B}_{t,s}$ that scales as ${t}^{1/2}/s$. This is qualitatively similar to what our results suggests and in contrast to the classical UCT.
Reinforcement learning aims to approximate the optimal value function and policy directly from experimental data. A variety of algorithms have been developed, including modelbased approaches, modelfree approaches like tabular Qlearning (Watkins and Dayan 1992), and parametric approximation such as linear architectures (Sutton 1988). More recent work approximates the value function/policy by deep neural networks (Mnih et al. 2015, Schulman et al. 2015, 2017, Silver et al. 2017b, Yang et al. 2019), which can be trained using temporaldifference learning or Qlearning (Van Hasselt et al. 2016, Mnih et al. 2016, 2013).
MCTS is an alternative approach, which as discussed, estimates the (optimal) value of states by building a search tree from MonteCarlo simulations (Kocsis and Szepesvári 2006, Chang et al. 2005, Coulom 2006, Browne et al. 2012). Kocsis and Szepesvári (2006) and Kocsis et al. (2006) argue for the asymptotic convergence of MCTS with standard UCT. However, the proof is incomplete (Szepesvári 2019). A key step towards proving the claimed result is to show the convergence and concentration properties of the regret for UCB under nonstationary reward distributions. In particular, to establish an exponential concentration of regret (Theorem 5, (Kocsis et al. 2006)), Lemma 14 is applied. However, it requires conditional independence of $\{{Z}_{i}\}$ sequence, which does not hold, hence making the conclusion of exponential concentration questionable. Therefore, the proof of the main result (Theorem 7, (Kocsis et al. 2006)), which applies Theorem 5 with an inductive argument, is incorrect as stated.
In fact, it may be infeasible to prove Theorem 5 in (Kocsis et al. 2006) as it was stated. For example, the work of Audibert et al. (2009) shows that for bandit problems, the regret under UCB concentrates around its expectation polynomially and not exponentially as desired in Kocsis et al. (2006). Further, Salomon and Audibert (2011) prove that for any strategy that does not use the knowledge of time horizon, it is infeasible to improve this polynomial concentration and establish exponential concentration. Our result is consistent with these fundamental bound of stationary MAB — we establish polynomial concentration of regret for nonstationary MAB, which plays a crucial role in our analysis of MCTS. Also see the work Munos et al. (2014) for a discussion of the issues with logarithmic bonus terms for tree search.
While we focus on UCT in this paper, we note that there are other variants of MCTS developed for a diverse range of applications. The work of Coquelin and Munos (2007) introduces flat UCB in order to improve the worst case regret bounds of UCT. Schadd et al. (2008) modifies MCTS for singleplayer games by adding to the standard UCB formula a term that captures the possible deviation of the node. In the work by Sturtevant (2008), a variant of MCTS is introduced for multiplayer games by adopting the max${}^{n}$ idea. In addition to turnbased games like Go and Chess, MCTS has also been applied to realtime games (e.g., Ms. PacMan, Tron and Starcraft) and nondeterministic games with imperfect information. The applications of MCTS go beyond games, and appear in areas such as optimization, scheduling and other decisionmaking problems. We refer to the survey on MCTS by Browne et al. (2012) for other variations and applications.
It has become popular recently to combine MCTS with deep neural networks, which serve to approximate the value function and/or policy (Silver et al. 2016, 2017b, 2017a). For instance, in AlphaGo Zero, MCTS uses the neural network to query the value of leaf nodes for simulation guidance; the neural network is then updated with sample data generated by MCTSbased policy and used in tree search in the next iteration. Azizzadenesheli et al. (2018) develop generative adversarial tree search that generates rollouts with a learned GANbased dynamic model and reward predictor, while using MCTS for planning over the simulated samples and a deep Qnetwork to query the Qvalue of leaf nodes.
In terms of theoretical results, the closest work to our paper is Jiang et al. (2018), where they also consider a batch, MCTSbased reinforcement learning algorithm, which is a variant of AlphaGo Zero algorithm. The key algorithmic difference from ours lies in the leafnode evaluator of the search tree: they use a combination of an estimated value function and an estimated policy. The latest observations at the root node are then used to update the value and policy functions (leafnode evaluator) for the next iteration. They also give a finite sample analysis. However, their result and ours are quite different: in their analysis, the sample complexity of MCTS, as well as the approximation power of value/policy architectures, are imposed as an assumption; here we prove an explicit finitesample bound for MCTS and characterize the nonasymptotic error prorogation under MCTS with nonparametric regression for leafnode evaluation. Therefore, they do not establish “strong policy improvement” property of the MCTS.
Two other closely related papers are Teraoka et al. (2014) and Kaufmann and Koolen (2017), which study a simplified MCTS for twoplayer zerosum games. There, the goal is to identify the best action of the root in a given game tree. For each leaf node, a stochastic oracle is provided to generate i.i.d. samples for the true reward. Teraoka et al. (2014) give a high probability bound on the number of oracle calls needed for obtaining $\epsilon $accurate score at the root. The more recent paper Kaufmann and Koolen (2017) develops refined, instancedependent sample complexity bounds. Compared to classical MCTS (e.g., UCT), both the setting and the algorithms in the above papers are simpler: the game tree is given in advance, rather than being built gradually through samples; the algorithm proposed in Teraoka et al. (2014) operates on the tree in a bottomup fashion with uniform sampling at the leaf nodes. As a result, the analysis is significantly simpler and it is unclear whether the techniques can be extended to analyze other variants of MCTS.
It is important to mention the work of Chang et al. (2005) that explores the idea of using UCB for adaptive sampling in MDPs. The approximate value computed by the algorithm is shown to converge to the optimal value. We remark that their algorithm is different from the algorithm we analyze in this paper. In particular, their algorithm proceeds in a depthfirst, recursive manner, and hence involves using UCB for a stationary MAB at each node. In contrast, the UCT algorithm we study involves nonstationary MABs, hence our analysis is significantly different from theirs. We refer the readers to the work by Kocsis and Szepesvári (2006) and Coulom (2006) for further discussion of this difference. Another related work by Kearns et al. (2002) studies a sparse sampling algorithm for large MDPs. This algorithm is also different from the MCTS family we analyze in this paper. Recently, Efroni et al. (2018) study multiplestep lookahead policies in reinforcement learning, which can be implemented via MCTS.
Section id1 describes the setting of Markov Decision Process considered in this work. Section id1 describes the Monte Carlo Tree Search algorithm and the main result about its nonasymptotic analysis. Section id1 describes a reinforcement learning method that combines the Monte Carlo Tree Search with nearest neighbor supervised learning. It describes the finitesample analysis of the method for finding $\epsilon $ approximate value function with respect to ${\mathrm{\ell}}_{\mathrm{\infty}}$ norm. Section id1 introduces a form of nonstationary multiarm bandit and an upper confidence bound policy for it. For this setting, we present the concentration of induced regret which serves as a key result for establishing the property of MCTS. The proofs of all the technical results are delegated to Sections id1  id1 and Appendices.
We consider the setup of discretetime discounted Markov decision process (MDP). An MDP is described by a fivetuple $(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma )$, where $\mathcal{S}$ is the set of states, $\mathcal{A}$ is the set of actions, $\mathcal{P}\equiv \mathcal{P}({s}^{\prime}s,a)$ is the Markovian transition kernel, $\mathcal{R}\equiv \mathcal{R}(s,a)$ is a random reward function, and $\gamma \in (0,1)$ is a discount factor. At each time step, the system is in some state $s\in \mathcal{S}$. When an action $a\in \mathcal{A}$ is taken, the state transits to a next state ${s}^{\prime}\in \mathcal{S}$ according to the transition kernel $\mathcal{P}$ and an immediate reward is generated according to $\mathcal{R}(s,a)$.
A stationary policy $\pi (as)$ gives the probability of performing action $a\in \mathcal{A}$ given the current state $s\in \mathcal{S}.$ The value function for each state $s\in \mathcal{S}$ under policy $\pi $, denoted by ${V}^{\pi}(s)$, is defined as the expected discounted sum of rewards received following the policy $\pi $ from initial state $s$, i.e.,
${V}^{\pi}(s)={\mathbb{E}}_{\pi}[{\displaystyle \sum _{t=0}^{\mathrm{\infty}}}{\gamma}^{t}\mathcal{R}({s}_{t},{a}_{t}){s}_{0}=s].$ 
The goal is to find an optimal policy ${\pi}^{*}$ that maximizes the value from each initial state. The optimal value function ${V}^{*}$ is defined as ${V}^{*}(s)={V}^{{\pi}^{*}}(s)={sup}_{\pi}{V}^{\pi}(s)$, $\forall s\in \mathcal{S}.$ It is well understood that such an optimal policy exists in reasonable generality. In this paper, we restrict our attention to the MDPs with the following assumptions:
Assumption 1 (MDP Regularity)
(A1.) The action space $\mathrm{A}$ is a finite set and the state space $\mathrm{S}$ is a compact subset of $d$ dimensional set; without loss of generality, let $\mathrm{S}\mathrm{=}{\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}}^{d}$; (A2.) The immediate rewards are random variables, uniformly bounded such that $\mathrm{R}\mathit{}\mathrm{(}s\mathrm{,}a\mathrm{)}\mathrm{\in}\mathrm{[}\mathrm{}{R}_{\mathrm{max}}\mathrm{,}{R}_{\mathrm{max}}\mathrm{]}\mathrm{,}\mathrm{\forall}s\mathrm{\in}\mathrm{S}\mathrm{,}a\mathrm{\in}\mathrm{A}$ for some ${R}_{\mathrm{max}}\mathrm{>}\mathrm{0}$; (A3.) The state transitions are deterministic, i.e. $\mathrm{P}\mathrm{\equiv}\mathrm{P}\mathit{}\mathrm{(}{s}^{\mathrm{\prime}}\mathrm{}s\mathrm{,}a\mathrm{)}\mathrm{\in}\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{\}}$ for all $s\mathrm{,}{s}^{\mathrm{\prime}}\mathrm{\in}\mathrm{S}\mathrm{,}a\mathrm{\in}\mathrm{A}$.
Define $\beta \triangleq 1/(1\gamma )$ and ${V}_{\mathrm{max}}\triangleq \beta {R}_{\mathrm{max}}.$ Since all the rewards are bounded by ${R}_{\mathrm{max}}$, it is easy to see that the absolute value of the value function for any state under any policy is bounded by ${V}_{\mathrm{max}}$ (EvenDar and Mansour 2004, Strehl et al. 2006).
On Deterministic Transition. We note that the deterministic transition in MDP should not be viewed as restriction or assumption. Traditional AI game research has been focused on deterministic games with a tree representation. It is this context within which historically MCTS was introduced, has been extensively studied and utilized in practice (Browne et al. 2012). This includes the recent successes of MCTS in Go (Silver et al. 2017b), Chess (Silver et al. 2017a) and Atari games (Guo et al. 2014). There is a long theoretical literature on the analysis of MCTS and related methods (Browne et al. 2012, Hren and Munos 2008, Munos et al. 2014, Bartlett et al. 2019) that considers deterministic transition. The principled extension of MCTS algorithm itself as well as theoretical results similar to ours for the stochastic setting are important future work.
A classical approach to find optimal value function, ${V}^{*}$, is an iterative approach called value function iteration. The Bellman equation characterizes the optimal value function as
${V}^{*}(s)$  $=\underset{a\in \mathcal{A}}{\mathrm{max}}\left(\mathbb{E}[\mathcal{R}(s,a)]+\gamma {V}^{*}(s\circ a)\right),$  (2) 
where $s\circ a\in \mathcal{S}$ is the notation to denote the state reached by applying action $a$ on state $s$. Under Assumption 1, the transitions are deterministic and hence $s\circ a$ represents a single, deterministic state rather than a random state.
The value function iteration effectively views (2) as a fixed point equation and tries to find a solution to it through a natural iteration. Precisely, let ${V}^{(t)}(\cdot )$ be the value function estimation in iteration $t$ with ${V}^{(0)}$ being arbitrarily initialized. Then, for $t\ge 0$, for all $s\in \mathcal{S}$,
${V}^{(t+1)}(s)$  $=\underset{a\in \mathcal{A}}{\mathrm{max}}\left(\mathbb{E}[\mathcal{R}(s,a)]+\gamma {V}^{(t)}(s\circ a)\right).$  (3) 
It is well known (cf. Bertsekas (2017)) that value iteration is contractive with respect to $\parallel \cdot {\parallel}_{\mathrm{\infty}}$ norm for all $$. Specifically, for $t\ge 0$, we have
${\parallel {V}^{(t+1)}{V}^{*}\parallel}_{\mathrm{\infty}}$  $\le \gamma {\parallel {V}^{(t)}{V}^{*}\parallel}_{\mathrm{\infty}}.$  (4) 
Monte Carlo Tree Search (MCTS) has been quite popular recently in many of the reinforcement learning tasks. In effect, given a state $s\in \mathcal{S}$ and a value function estimate $\widehat{V}$, it attempts to run the value function iteration for a fixed number of steps, say $H$, to evaluate ${V}^{(H)}(s)$ starting with ${V}^{(0)}=\widehat{V}$ per (3). This, according to (4), would provide an estimate within error ${\gamma}^{H}{\parallel \widehat{V}{V}^{*}\parallel}_{\mathrm{\infty}}$ – an excellent estimate of ${V}^{*}(s)$ if $H$ is large enough. The goal is to perform computation for value function iteration necessary to evaluate ${V}^{(H)}$ for state $s$ only and not necessarily for all states as required by traditional value function iteration. MCTS achieves this by simply ‘unrolling’ the associated ‘computation tree’. Another challenge that MCTS overcomes is the fact that value function iteration as in (3) assumes knowledge of model so that it can compute $\mathbb{E}[\mathcal{R}(\cdot ,\cdot )]$ for any stateaction pair. But in reality, rewards are observed through samples, not a direct access to $\mathbb{E}[\mathcal{R}(\cdot ,\cdot )]$. MCTS tries to utilize the samples in a careful manner to obtain accurate estimation for ${V}^{(H)}(s)$ over the computation tree suggested by the value function iteration as discussed above. The concern of careful use of samples naturally connects it to multiarm bandit like setting.
Next, we present a detailed description of the MCTS algorithm in Section id1. This can be viewed as a correction of the algorithm presented in Kocsis and Szepesvári (2006), Kocsis et al. (2006). We state its theoretical property in Section id1.
We provide details of a specific form of MCTS, which replaces the logarithmic bonus term of UCT with a polynomial one. Overall, we fix the search tree to be of depth $H$. Similar to most literature on this topic, it uses a variant of the Upper Confidence Bound (UCB) algorithm to select an action at each stage. At a leaf node (i.e., a state at depth $H$), we use the current value oracle $\widehat{V}$ to evaluate its value. Note that since we consider deterministic transitions, consequently, the tree is fixed once the root node (state) is chosen, and we use the notation $s\circ a$ to denote the next state after taking action $a$ at state $s$. Each edge represents a stateaction pair, while each node represents a state. For clarity, we use superscript to distinguish quantities related to different depth. The pseudocode for the MCTS procedure is given in Algorithm 1, and Figure 1 shows the structure of the search tree and related notation.
[!ht]
\[email protected]@algorithmic[1]
\STATEInput: (1) current value oracle $\widehat{V}$, root node ${s}^{(0)}$ and search depth $H$;
$$(2) number of MCTS simulations $n$;
$$(3) algorithmic constants,
${\{{\alpha}^{(i)}\}}_{i=1}^{H},$ ${\{{\beta}^{(i)}\}}_{i=1}^{H},$ ${\{{\xi}^{(i)}\}}_{i=1}^{H}$ and ${\{{\eta}^{(i)}\}}_{i=1}^{H}.$
\STATEInitialization: for each depth $h$, initialize the cumulative node value ${\stackrel{~}{v}}^{(h)}(s)=0$ and visit count ${N}^{(h)}(s)=0$ for every node $s$ and initialize the cumulative edge value ${q}^{(h)}(s,a)=0$.
\FOReach MCTS simulation $t=1,2,\mathrm{\dots},n$
\STATE/* Simulation: select actions until reaching depth $\mathrm{H}$*/
\FORdepth $h=0,1,2,\mathrm{\dots},H1$
\STATEat state ${s}^{(h)}$ of depth $h$, select an action (edge) according to
$${a}^{(h+1)}=\mathrm{arg}\underset{a\in \mathcal{A}}{\mathrm{max}}\frac{{q}^{(h+1)}({s}^{(h)},a)+\gamma {\stackrel{~}{v}}^{(h+1)}({s}^{(h)}\circ a)}{{N}^{(h+1)}({s}^{(h)}\circ a)}+\frac{{\left({\beta}^{(h+1)}\right)}^{1/{\xi}^{(h+1)}}\cdot {\left({N}^{(h)}({s}^{(h)})\right)}^{{\alpha}^{(h+1)}/{\xi}^{(h+1)}}}{{\left({N}^{(h+1)}({s}^{(h)}\circ a)\right)}^{1{\eta}^{(h+1)}}},$$  (5) 
where dividing by zero is assumed to be $+\mathrm{\infty}$. \STATEupon taking the action ${a}^{(h+1)}$, receive a random reward ${r}^{(h+1)}\triangleq \mathcal{R}({s}^{(h)},{a}^{(h+1)})$ and transit to a new state ${s}^{(h+1)}$ at depth $h+1$. \ENDFOR\STATE/* Evaluation: call value oracle for leaf nodes*/ \STATEreach ${s}^{(H)}$ at depth $H$, call the current value oracle and let ${\stackrel{~}{v}}^{(H)}({s}^{(H)})=\widehat{V}({s}^{(H)})$. \STATE/* Update Statistics: quantities on the search path*/ \FORdepth $h=0,1,2,\mathrm{\dots},H1$ \STATEupdate statistics of nodes and edges that are on the search path of current simulation:
visit count:  ${N}^{(h+1)}({s}^{(h+1)})={N}^{(h+1)}({s}^{(h+1)})+1$  
edge value:  ${q}^{(h+1)}({s}^{(h)},{a}^{(h+1)})={q}^{(h+1)}({s}^{(h)},{a}^{(h+1)})+{r}^{(h+1)}$  
node value:  ${\stackrel{~}{v}}^{(h)}({s}^{(h)})={\stackrel{~}{v}}^{(h)}({s}^{(h)})+{r}^{(h+1)}+\gamma {r}^{(h+2)}+\mathrm{\cdots}+{\gamma}^{H1h}{r}^{(H)}+{\gamma}^{Hh}{\stackrel{~}{v}}^{(H)}({s}^{(H)})$ 
Output: average of the value for the root node ${\stackrel{~}{v}}^{(0)}({s}^{(0)})/n$.
In Algorithm 1, there are certain sequences of algorithmic parameters required, namely, $\alpha $, $\beta $, $\xi $ and $\eta $. The choices for these constants will become clear in our nonasymptotic analysis. At a higher level, the constants for the last layer (i.e., depth $H$), ${\alpha}^{(H)}$, ${\beta}^{(H)}$, ${\xi}^{(H)}$ and ${\eta}^{(H)}$ depend on the properties of the leaf nodes, while the rest are recursively determined by the constants one layer below.
We note that in selecting action ${a}^{(h+1)}$ at each depth $h$ (i.e., Line 6 of Algorithm 1), the upper confidence term is polynomial in $n$ while a typical UCB algorithm would be logarithmic in $n$, where $n$ is the number of visits to the corresponding state thus far. The logarithmic factor in the original UCB algorithm was motivated by the exponential tail probability bounds. In our case, it turns out that exponential tail bounds for each layer seems to be infeasible without further structural assumptions. As mentioned in Section id1, prior work (Audibert et al. 2009, Salomon and Audibert 2011) has justified the polynomial concentration of the regret for the classical UCB in stochastic (independent rewards) multiarm bandit setting. This implies that the concentration at intermediate depth (i.e., depth less than $H$) is at most polynomial. Indeed, we will prove these polynomial concentration bounds even for nonstationary (dependent, nonstationary rewards) multiarm bandit that show up in MCTS and discuss separately in Section id1.
Now, we state the following result on the nonasymptotic performance of the MCTS as described above.
Theorem 1
Consider an MDP satisfying Assumption 1. Let $H\mathrm{\ge}\mathrm{1}$, and for $$, let
${\eta}^{(h)}$  $={\eta}^{(H)}\equiv \eta ,\forall h\in [H],$  (6)  
${\alpha}^{(h)}$  $=\eta (1\eta )\left({\alpha}^{(h+1)}1\right),\forall h\in [H1],$  (7)  
${\xi}^{(h)}$  $={\alpha}^{(h+1)}1,\forall h\in [H1].$  (8) 
Suppose that a large enough ${\xi}^{\mathrm{(}H\mathrm{)}}$ is chosen such that ${\alpha}^{\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{>}\mathrm{2}$. Then, there exist corresponding constants ${\mathrm{\{}{\beta}^{\mathrm{(}i\mathrm{)}}\mathrm{\}}}_{i\mathrm{=}\mathrm{1}}^{H}$ such that for each query state $s\mathrm{\in}\mathrm{S}\mathrm{,}$ the following claim holds for the output ${\widehat{V}}_{n}\mathit{}\mathrm{(}s\mathrm{)}$ of MCTS with $n$ simulations:
$$\left\mathbb{E}\left[{\widehat{V}}_{n}(s)\right]{V}^{*}(s)\right\le {\gamma}^{H}{\epsilon}_{0}+O\left({n}^{\eta 1}\right),$$ 
where ${\epsilon}_{\mathrm{0}}\mathrm{=}{\mathrm{\parallel}\widehat{V}\mathrm{}{V}^{\mathrm{*}}\mathrm{\parallel}}_{\mathrm{\infty}}$ with $\widehat{V}$ being the estimate of ${V}^{\mathrm{*}}$ utilized by the MCTS algorithm for leaf nodes.
Since $\eta \in [1/2,1)$, Theorem 1 implies a best case convergence rate of $O({n}^{1/2})$ by setting $\eta =1/2$. With these parameter choices, the bias term in the upper confidence bound (line 6 of Algorithm 1) scales as ${\left({N}^{(h)}({s}^{(h)})\right)}^{1/4}/\sqrt{{N}^{(h+1)}({s}^{(h)}\circ a)}$, that is, in the form of ${t}^{1/4}/\sqrt{S}$ as mentioned in the introduction, where $t\equiv {N}^{(h)}({s}^{(h)})$ is the number of times that state ${s}^{(h)}$ at depth $h$ has been visited, and $S\equiv {N}^{(h+1)}({s}^{(h)}\circ a)$ is the number of times action $a$ has been selected at state ${s}^{(h)}$.
Recently, MCTS has been utilized prominently in various empirical successes of reinforcement learning including AlphaGo Zero (AGZ). Here, MCTS is combined with expressive supervised learning method to iteratively improve the policy as well as the value function estimation. In effect, MCTS combined with supervised learning acts as a “policy improvement” operator.
Intuitively, MCTS produces an improved estimation of value function for a given state of interest, starting with a given estimation of value function by “unrolling” the “computation tree” associated with value function iteration. And MCTS achieves this using observations obtained through simulations. Establishing this improvement property rigorously was the primary goal of Section id1. Now, given such improved estimation of value function for finitely many states, a good supervised learning method can learn to generalize such an improvement to all states. If so, this is like performing value function iteration, but using simulations. Presenting such a policy and establishing such guarantees is the crux of this section.
To that end, we present a reinforcement learning method that combines MCTS with nearest neighbor supervised learning. For this method, we establish that indeed, with sufficient number of samples, the resulting policy improves the value function estimation just like value function iteration. Using this, we provide a finitesample analysis for learning the optimal value function within a given tolerance. We find it nearly matching a minimax lower bound in Shah and Xie (2018) which we recall in Section 2, and thus establishes near minimax optimality of such a reinforcement learning method.
Here we describe the policy to produce estimation of optimal value function ${V}^{*}$. Similar approach can be applied to obtain estimation of policy as well. Let ${V}^{(0)}$ be the initial estimation of ${V}^{*}$, and for simplicity, let ${V}^{(0)}(\cdot )=0$. We describe a policy that iterates between use of MCTS and supervised learning to iteratively obtain estimation ${V}^{(\mathrm{\ell})}$ for $\mathrm{\ell}\ge 1$, so that iteratively better estimation of ${V}^{*}$ is produced as $\mathrm{\ell}$ increases. To that end, for $\mathrm{\ell}\ge 1$,

$\circ $
For appropriately sampled states ${S}^{\mathrm{\ell}}={\{{s}_{i}\}}_{i=1}^{{m}_{\mathrm{\ell}}}$, apply MCTS to obtain improved estimations of value function ${\{{\widehat{V}}^{(\mathrm{\ell})}({s}_{i})\}}_{i=1}^{{m}_{\mathrm{\ell}}}$ using ${V}^{(\mathrm{\ell}1)}$ to evaluate leaf nodes during simulations.

$\circ $
Using $\{{({s}_{i},{\widehat{V}}^{(\mathrm{\ell})}({s}_{i})\}}_{i=1}^{{m}_{\mathrm{\ell}}}$ with a variant of nearest neighbor supervised learning with parameter ${\delta}_{\mathrm{\ell}}\in (0,1)$, produce estimation ${V}^{(\mathrm{\ell})}$ of the optimal value function.
For completeness, the pseudocode is provided in Algorithm 1. {algorithm}[htp] \[email protected]@algorithmic[1] \STATEInput: initial value function oracle ${V}^{(0)}(s)=0$, $\forall s\in \mathcal{S}$ \FOR$l=1,2,\mathrm{\dots},L$ \STATE/* improvement via MCTS */ \STATEuniformly and independently sample states ${S}^{\mathrm{\ell}}={\{{s}_{i}\}}_{i=1}^{{m}_{\mathrm{\ell}}}$. \FOReach sampled state ${s}_{i}$ \STATEapply the MCTS algorithm, which takes as inputs the current value oracle ${V}^{(l1)}$, the depth ${H}^{(l)}$, the number of simulation ${n}_{l}$, and the root node ${s}_{i}$, and outputs an improved estimate for ${V}^{*}({s}_{i})$:
$${\widehat{V}}^{(l)}({s}_{i})=\text{MCTS}({V}^{(l1)},{H}^{(l)},{n}_{l},{s}_{i})$$  (9) 
/* supervised learning */ \STATEwith the collected data ${\mathcal{D}}^{(l)}={\{({s}_{i},{\widehat{V}}^{(l)}({s}_{i}))\}}_{i=1}^{{m}_{l}}$, build a new value oracle ${V}^{(l)}$ via a nearest neighbor regression with parameter ${\delta}_{l}$ :
$${V}^{(l)}(s)=\text{Nearest Neigbhor}({\mathcal{D}}^{(l)},{\delta}_{l},s),\forall s\in \mathcal{S}.$$  (10) 
Output: final value oracle ${V}^{(L)}$.
For simplicity, we shall utilize the following variant of the nearest neighbor supervised learning parametrized by $\delta \in (0,1)$. Given state space $\mathcal{S}={[0,1]}^{d}$, we wish to cover it with minimal (up to scaling) number of balls of radius $\delta $ (with respect to ${\mathrm{\ell}}_{2}$norm). To that end, since $\mathcal{S}={[0,1]}^{d}$, one such construction is where we have balls of radius $\delta $ with centers being $\{({\theta}_{1},{\theta}_{2},\mathrm{\dots},{\theta}_{d}):{\theta}_{1},\mathrm{\dots},{\theta}_{d}\in \mathcal{Q}(\delta )\}$ where
$$\mathcal{Q}(\delta )=\{\frac{1}{2}\delta i:i\in \mathbb{Z},0\le i\le \lfloor \frac{2}{\delta}\rfloor \}\cup \{1\frac{1}{2}\delta i:i\in \mathbb{Z},0\le i\le \lfloor \frac{2}{\delta}\rfloor \}.$$ 
Let the collection of these balls be denoted by ${c}_{1},\mathrm{\dots},{c}_{K(\delta ,d)}$ with $K(\delta ,d)=\mathcal{Q}(\delta )$. It is easy to verify that $\mathcal{S}\subset {\cup}_{i\in [K(\delta ,d)]}{c}_{i}$, $K(\delta ,d)=\mathrm{\Theta}({\delta}^{d})$ and ${C}_{d}{\delta}^{d}\le \U0001d5cfolume({c}_{i}\cap \mathcal{S})\le {C}_{d}^{\prime}{\delta}^{d}$ for strictly positive constants ${C}_{d},{C}_{d}^{\prime}$ that depends on $d$ but not $\delta $. For any $s\in \mathcal{S}$, let $j(s)=\mathrm{min}\{j:s\in {c}_{j}\}$. Given observations $\{{({s}_{i},{\widehat{V}}^{(\mathrm{\ell})}({s}_{i})\}}_{i=1}^{{m}_{\mathrm{\ell}}}$, we produce an estimate ${V}^{(\mathrm{\ell})}(s)$ for all $s\in \mathcal{S}$ as follows:
${V}^{(\mathrm{\ell})}(s)$  $=\{\begin{array}{cc}\frac{{\sum}_{i:{s}_{i}\in {c}_{j(s)}}{\widehat{V}}^{(\mathrm{\ell})}({s}_{i})}{\{i:{s}_{i}\in {c}_{j(s)}\}},\hfill & \text{if}\{i:{s}_{i}\in {c}_{j(s)}\}\ne 0,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$  (11) 
For finitesample analysis of the proposed reinforcement learning policy, we make the following structural assumption about the MDP. Specifically, we assume that the optimal value function (i.e., true regression function) is smooth in some sense. We note that some form of smoothness assumption for MDPs with continuous state/action space is typical for ${\mathrm{\ell}}_{\mathrm{\infty}}$ guarantee. The Lipschitz continuous assumption stated below is natural and representative in the literature on MDPs with continuous state spaces, cf. Munos et al. (2014), Dufour and PrietoRumeau (2012, 2013) and Bertsekas (1975).
Assumption 2 (Smoothness)
The optimal value function ${V}^{\mathrm{*}}\mathrm{:}\mathrm{S}\mathrm{\to}\mathrm{R}$ satisfies Lipschitz continuity with parameter $C$, i.e., $\mathrm{\forall}s\mathrm{,}{s}^{\mathrm{\prime}}\mathrm{\in}\mathrm{S}\mathrm{=}{\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}}^{d}\mathrm{,}$ $\mathrm{}{V}^{\mathrm{*}}\mathit{}\mathrm{(}s\mathrm{)}\mathrm{}{V}^{\mathrm{*}}\mathit{}\mathrm{(}{s}^{\mathrm{\prime}}\mathrm{)}\mathrm{}\mathrm{\le}C\mathit{}{\mathrm{\parallel}s\mathrm{}{s}^{\mathrm{\prime}}\mathrm{\parallel}}_{\mathrm{2}}\mathrm{.}$
Now we state the result characterizing the performance of the reinforcement learning policy described above.
Theorem 2
Let Assumptions 1 and 2 hold. Let $\epsilon \mathrm{>}\mathrm{0}$ be a given error tolerance. Then, for $L\mathrm{=}\mathrm{\Theta}\mathit{}\mathrm{\left(}\mathrm{log}\mathit{}\frac{\epsilon}{{V}_{\mathrm{max}}}\mathrm{\right)}$, with appropriately chosen ${m}_{\mathrm{\ell}}\mathrm{,}{\delta}_{\mathrm{\ell}}$ for $\mathrm{\ell}\mathrm{\in}\mathrm{[}L\mathrm{]}$ as well as parameters in MCTS, the reinforcement learning algorithm produces estimation of value function ${V}^{\mathrm{(}L\mathrm{)}}$ such that
$\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}{V}^{(L)}(s){V}^{*}(s)\right]\le \epsilon ,$ 
by selecting ${m}_{\mathrm{\ell}}$ states uniformly at random in $\mathrm{S}$ within iteration $\mathrm{\ell}$. This, in total, requires T number of state transitions (or samples), where
$T$  $=O\left({\epsilon}^{\left(4+d\right)}\cdot {\left(\mathrm{log}{\displaystyle \frac{1}{\epsilon}}\right)}^{5}\right).$ 
Leveraging the the minimax lower bound for the problem of nonparametric regression (Tsybakov 2009, Stone 1982), recent work Shah and Xie (2018) establishes a lower bound on the sample complexity for reinforcement learning algorithms for general MDPs without additional structural assumptions. Indeed the lower bound also holds for MDPs with deterministic transitions (the proof is provided in Appendix id1), which is stated in the following proposition.
Proposition 1
Given an algorithm, let ${V}_{T}$ be the estimation of ${V}^{\mathrm{*}}$ after $T$ samples of state transitions for the given MDP. Then, for each $\epsilon \mathrm{\in}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$, there exists an instance of deterministic MDP such that in order to achieve $$ it must be that
$$T\ge {C}^{\prime}d\cdot {\epsilon}^{(d+2)}\cdot \mathrm{log}({\epsilon}^{1}),$$ 
where ${C}^{\mathrm{\prime}}\mathrm{>}\mathrm{0}$ is a constant independent of the algorithm.
Proposition 1 states that for any policy to learn the optimal value function within $\epsilon $ approximation error, the number of samples required must scale as $\stackrel{~}{\mathrm{\Omega}}\left({\epsilon}^{(2+d)}\right)$. Theorem 2 implies that the sample complexity of the proposed algorithm scales as $\stackrel{~}{O}\left({\epsilon}^{(4+d)}\right)$ (omitting the logarithmic factor). Hence, in terms of the dependence on the dimension, the proposed algorithm is nearly optimal. Optimizing the dependence of the sample complexity on other parameters is an important direction for future work.
We introduce a class of nonstationary multiarm bandit (MAB) problems, which will play a crucial role in analyzing the MCTS algorithm. To that end, let there be $K\ge 1$ arms or actions of interest. Let ${X}_{i,t}$ denote the random reward obtained by playing the arm $i\in [K]$ for the $t$th time with $t\ge 1$. Let ${\overline{X}}_{i,n}=\frac{1}{n}{\sum}_{t=1}^{n}{X}_{i,t}$ denote the empirical average of playing arm $i$ for $n$ times, and let ${\mu}_{i,n}=\mathbb{E}[{\overline{X}}_{i,n}]$ be its expectation. For each arm $i\in [K]$, the reward ${X}_{i,t}$ is bounded in $[R,R]$ for some $R>0$, and we assume that the reward sequence, $\{{X}_{i,t}:t\ge 1\}$, is a nonstationary process satisfying the following convergence and concentration properties:

A.
(Convergence) the expectation ${\mu}_{i,n}$ converges to a value ${\mu}_{i}$, i.e.,
${\mu}_{i}=\underset{n\to \mathrm{\infty}}{lim}\mathbb{E}[{\overline{X}}_{i,n}].$ (12) 
B.
(Concentration) there exist three constants, $\beta >1$, $\xi >0$, and $$ such that for every $z\ge 1$ and every integer $n\ge 1$,
$\mathbb{P}(n{\overline{X}}_{i,n}n{\mu}_{i}$ $\ge {n}^{\eta}z)\le {\displaystyle \frac{\beta}{{z}^{\xi}}},\mathbb{P}(n{\overline{X}}_{i,n}n{\mu}_{i}\le {n}^{\eta}z)\le {\displaystyle \frac{\beta}{{z}^{\xi}}}.$ (13)
Consider applying the following variant of Upper Confidence Bound (UCB) algorithm to the above nonstationary MAB. Define upper confidence bound for arm or action $i$ when it is played $s$ times in total of $t\ge s$ time steps as
${U}_{i,s,t}$  $={\overline{X}}_{i,s}+{B}_{t,s},$  (14) 
where ${B}_{t,s}$ is the “bonus term”. Denote by ${I}_{t}$ the arm played at time $t\ge 1$. Then,
$${I}_{t}\in \mathrm{arg}\underset{i\in [K]}{\mathrm{max}}\left\{{\overline{X}}_{i,{T}_{i}(t1)}+{B}_{t1,{T}_{i}(t1)}\right\},$$  (15) 
where ${T}_{i}(t)={\sum}_{l=1}^{t}\mathbb{I}\{{I}_{l}=i\}$ is the number of times arm $i$ has been played, up to (including) time $t$. We shall make specific selection of the bonus or bias term ${B}_{t,s}$ as
${B}_{t,s}={\displaystyle \frac{{\beta}^{1/\xi}\cdot {t}^{\alpha /\xi}}{{s}^{1\eta}}}.$  (16) 
A tie is broken arbitrarily when selecting an arm. In the above, $\alpha >0$ is a tuning parameter that controls the exploration and exploitation tradeoff. Let ${\mu}_{*}={\mathrm{max}}_{i\in [K]}{\mu}_{i}$ be the optimal value with respect to the converged expectation, and ${i}_{*}\in \mathrm{arg}{\mathrm{max}}_{i\in [K]}{\mu}_{i}$ be the corresponding optimal arm. We assume that the optimal arm is unique. Let ${\delta}_{i*,n}={\mu}_{{i}_{*},n}{\mu}_{{i}_{*}}$, which measures how fast the mean of the optimal nonstationary arm converges. For simplicity, quantities related to the optimal arm ${i}_{*}$ will be simply denoted with subscript $*$, e.g., ${\delta}_{*},n={\delta}_{{i}_{*},n}$. Finally, denote by ${\mathrm{\Delta}}_{\mathrm{min}}={\mathrm{min}}_{i\in [K],i\ne {i}_{*}}{\mathrm{\Delta}}_{i}$ the gap between the optimal arm and the second optimal arm with notation ${\mathrm{\Delta}}_{i}={\mu}_{*}{\mu}_{i}$.
Let ${\overline{X}}_{n}\triangleq \frac{1}{n}{\sum}_{i=1}^{K}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}$ denote the empirical average under the UCB algorithm (15). Then, ${\overline{X}}_{n}$ satisfies the following convergence and concentration properties.
Theorem 3
Consider a nonstationary MAB satisfying (12) and (13). Suppose that algorithm (15) is applied with parameter $\alpha $ such that $$ and $\alpha \mathrm{>}\mathrm{2}$. Then, the following holds:

A.
Convergence:
$\left\mathbb{E}[{\overline{X}}_{n}]{\mu}_{*}\right$ $\le {\delta}_{*,n}+{\displaystyle \frac{2R(K1)\cdot \left({\left(\frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {n}^{\frac{\alpha}{\xi (1\eta )}}+\frac{2}{\alpha 2}+1\right)}{n}}.$ 
B.
Concentration: there exist constants, ${\beta}^{\prime}>1$ and ${\xi}^{\prime}>0$ and $$ such that for every $n\ge 1$ and every $z\ge 1$,
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}$ $\ge {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\le {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ where ${\eta}^{\prime}=\frac{\alpha}{\xi (1\eta )}$, ${\xi}^{\prime}=\alpha 1$, ${\beta}^{\prime}$ depends on $R,K,{\mathrm{\Delta}}_{\mathrm{min}},\beta ,$ $\xi ,\alpha ,\eta $.
We establish the convergence and concentration properties of the variant of the Upper Confidence Bound algorithm described in Section id1 and specified through (14), (15) and (16).
Establishing the Convergence Property. We define a useful notation
$$\mathrm{\Phi}(n,\delta )={n}^{\eta}{\left(\frac{\beta}{\delta}\right)}^{1/\xi}.$$  (17) 
We begin with a useful lemma, which shows that the probability that a nonoptimal arm or action has a large upper confidence is polynomially small. Proof is provided in Section id1.
Lemma 1
Let $i\mathrm{\in}\mathrm{[}K\mathrm{]}\mathrm{,}i\mathrm{\ne}{i}_{\mathrm{*}}$ be a suboptimal arm and define
${A}_{i}(t)$  $\triangleq \underset{u\in \mathbb{N}}{\mathrm{min}}\left\{{\displaystyle \frac{\mathrm{\Phi}(u,{t}^{\alpha})}{u}}\le {\displaystyle \frac{{\mathrm{\Delta}}_{i}}{2}}\right\}=\lceil {\left({\displaystyle \frac{2}{{\mathrm{\Delta}}_{i}}}\cdot {\beta}^{1/\xi}\cdot {t}^{\alpha /\xi}\right)}^{\frac{1}{1\eta}}\rceil .$  (18) 
For each $s$ and $t$ such that, ${A}_{i}\mathit{}\mathrm{(}t\mathrm{)}\mathrm{\le}s\mathrm{\le}t$, we have
$$\mathbb{P}({U}_{i,s,t}>{\mu}_{*})\le {t}^{\alpha}.$$ 
Lemma 1 implies that as long as each arm is played enough, the suboptimal ones become less likely to be selected. This allows us to upper bound the expected number of suboptimal plays as follows.
Lemma 2
Let $i\mathrm{\in}\mathrm{[}K\mathrm{]}\mathrm{,}i\mathrm{\ne}{i}_{\mathrm{*}}$, then
$$\mathbb{E}[{T}_{i}(n)]\le {\left(\frac{2}{{\mathrm{\Delta}}_{i}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {n}^{\frac{\alpha}{\xi (1\eta )}}+\frac{2}{\alpha 2}+1.$$ 
Proof of Lemma 2 is deferred to Section id1.
Completing Proof of Convergence. By the triangle inequality,
$$\left{\mu}_{*}\mathbb{E}[{\overline{X}}_{n}]\right=\left{\mu}_{*}{\mu}_{*,n}\right+\left{\mu}_{*,n}\mathbb{E}[{\overline{X}}_{n}]\right=\left{\delta}_{*,n}\right+\left{\mu}_{*,n}\mathbb{E}[{\overline{X}}_{n}]\right.$$ 
The second term can be bounded as follows:
$n\left{\mu}_{*,n}\mathbb{E}[{\overline{X}}_{n}]\right$  
$=\left\mathbb{E}\left[{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}\right]\mathbb{E}\left[{\displaystyle \sum _{i=1}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}\right]\right$  
$\le \left\mathbb{E}\left[{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}\right]\mathbb{E}\left[{T}_{*}(n){\overline{X}}_{{i}_{*},{T}_{*}(n)}\right]\right+\left\mathbb{E}\left[{\displaystyle \sum _{i=1,i\ne {i}_{*}}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}\right]\right$  
$=\left\mathbb{E}\left[{\displaystyle \sum _{t={T}_{*}(n)+1}^{n}}{X}_{{i}_{*},t}\right]\right+\left\mathbb{E}\left[{\displaystyle \sum _{i=1,i\ne {i}_{*}}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}\right]\right.$  (19) 
Recall that the reward sequences are assumed to be bounded in $[R,R]$. Therefore, the first term of (19) can be bounded as follows:
$$\left\mathbb{E}\left[\sum _{t={T}_{*}(n)+1}^{n}{X}_{{i}_{*},t}\right]\right\le \mathbb{E}\left[\sum _{t={T}_{*}(n)+1}^{n}{X}_{{i}_{*},t}\right]\le R\cdot \mathbb{E}\left[\sum _{i=1,i\ne {i}_{*}}^{K}{T}_{i}(n)\right].$$ 
The second term can also be bounded as:
$\left\mathbb{E}\left[{\displaystyle \sum _{i=1,i\ne {i}_{*}}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}\right]\right$  $\le R\cdot \mathbb{E}\left[{\displaystyle \sum _{i=1,i\ne {i}_{*}}^{K}}{T}_{i}(n)\right].$ 
Hence, we obtain that
$$\left{\mu}_{*}\mathbb{E}[{\overline{X}}_{n}]\right=\left{\delta}_{*,n}\right+\left{\mu}_{*,n}\mathbb{E}[{\overline{X}}_{n}]\right\le \left{\delta}_{*,n}\right+\frac{2R\cdot \mathbb{E}\left[{\sum}_{i=1,i\ne {i}_{*}}^{K}{T}_{i}(n)\right]}{n}.$$ 
Combining the above bounds and Lemma 2 yields the desired convergence result in Theorem 3.
Establishing the Concentration Property. Having proved the convergence property, the next step is to show that a similar concentration property (cf. (13)) also holds for ${\overline{X}}_{n}$. We aim to precisely capture the relationship between the original constants assumed in the assumption and the new constants obtained for ${\overline{X}}_{n}$. To begin with, recall the definition of ${A}_{i}(t)$ in Lemma 1 and define
$A(t)$  $=\underset{i\in [K]}{\mathrm{max}}{A}_{i}(t)=\lceil {\left({\displaystyle \frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {t}^{\frac{\alpha}{\xi (1\eta )}}\rceil .$  (20) 
It can be checked that replacing $\beta $ with any larger number still makes the concentration inequalities (13) hold. Without loss of generality, we hence let $\beta $ be large enough so that $\frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}\cdot {\beta}^{1/\xi}>1$. We further denote by ${N}_{p}$ the first time such that $t\ge A(t)$, i.e.,
${N}_{p}$  $=\mathrm{min}\{t\ge 1:t\ge A(t)\}=\mathrm{\Theta}\left({\left({\displaystyle \frac{{2}^{\xi}\beta}{{\mathrm{\Delta}}_{\mathrm{min}}^{\xi}}}\right)}^{\frac{1}{\xi (1\eta )\alpha}}\right).$  (21) 
We first state the following concentration property, which will be further refined to match the desired form in Theorem 3. We defer the proof to Section id1.
Lemma 3
For any $n\mathrm{\ge}{N}_{p}$ and $x\mathrm{\ge}\mathrm{1}$, let ${r}_{\mathrm{0}}\mathrm{=}{n}^{\eta}\mathrm{+}\mathrm{2}\mathit{}R\mathit{}\mathrm{(}K\mathrm{}\mathrm{1}\mathrm{)}\mathit{}\mathrm{\left(}\mathrm{3}\mathrm{+}A\mathit{}\mathrm{(}n\mathrm{)}\mathrm{\right)}\mathrm{.}$ Then,
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {r}_{0}x)\le {\displaystyle \frac{\beta}{{x}^{\xi}}}+{\displaystyle \frac{2(K1)}{(\alpha 1){\left((1+A(n))x\right)}^{\alpha 1}}},$  
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\le {r}_{0}x)\le {\displaystyle \frac{\beta}{{x}^{\xi}}}+{\displaystyle \frac{2(K1)}{(\alpha 1){\left((1+A(n))x\right)}^{\alpha 1}}}.$ 
Lemma 3 confirms that indeed, as $n$ becomes large, the average ${\overline{X}}_{n}$ also satisfies certain concentration inequalities. However, the particular form of concentration in Theorem 3 does not quite match the form of concentration in Theorem 3 which we conclude next.
Completing Proof of Concentration Property. Let ${N}_{p}^{\prime}$ be a constant defined as follows:
$${N}_{p}^{\prime}=\mathrm{min}\{t\ge 1:t\ge A(t)\text{and}2RA(t)\ge {t}^{\eta}+2R(4K3)\}.$$ 
Recall the definition of $A(t)$ and that $\alpha \ge \xi \eta (1\eta )$ and $$. Hence, ${N}_{p}^{\prime}$ is guaranteed to exist. In addition, note that by definition, ${N}_{p}^{\prime}\ge {N}_{p}$. For each $n\ge {N}_{p}^{\prime}$,
$2RK{\left({\displaystyle \frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {n}^{\frac{\alpha}{\xi (1\eta )}}$  $=2RK\left[{\left({\displaystyle \frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {n}^{\frac{\alpha}{\xi (1\eta )}}+11\right]$  
$\ge 2RKA(n)2RK$  
$=2R(K1)A(n)+2RA(n)2RK$  
$\ge 2R(K1)A(n)+{n}^{\eta}+2R(4K3)2RK$  
$=2R(K1)(A(n)+3)+{n}^{\eta}={r}_{0}$ 
Now, let us apply Lemma 3: for every $n\ge {N}_{p}^{\prime}$ and $x\ge 1$, we have
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {n}^{\frac{\alpha}{\xi (1\eta )}}\left[2RK{({\displaystyle \frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}}\cdot {\beta}^{1/\xi})}^{\frac{1}{1\eta}}\right]x)$  $\le \mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {r}_{0}x)$  
$\le {\displaystyle \frac{\beta}{{x}^{\xi}}}+{\displaystyle \frac{2(K1)}{(\alpha 1){\left((1+A(n))x\right)}^{\alpha 1}}}$  
$\le {\displaystyle \frac{2\mathrm{max}(\beta ,\frac{2(K1)}{(\alpha 1){(1+A({N}_{p}^{\prime}))}^{\alpha 1}})}{{x}^{\alpha 1}}},$  (22) 
where the last inequality follows because $n\ge {N}_{p}^{\prime}$ and $A(n)$ is a nondecreasing function. In addition, since $$, we have $$. For convenience, we define a constant
$${c}_{1}\triangleq 2RK{\left(\frac{2}{{\mathrm{\Delta}}_{\mathrm{min}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}.$$  (23) 
Equivalently, by a change of variable, i.e., letting $z={c}_{1}x$, then for every $n\ge {N}_{p}^{\prime}$ and $z\ge 1$, we obtain that
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {n}^{\frac{\alpha}{\xi (1\eta )}}z)$  $\le {\displaystyle \frac{2{c}_{1}^{\alpha 1}\cdot \mathrm{max}(\beta ,\frac{2(K1)}{(\alpha 1){(1+A({N}_{p}^{\prime}))}^{\alpha 1}})}{{z}^{\alpha 1}}}.$  (24) 
The above inequality holds because: (1) if $z\ge {c}_{1}$, then (24) directly follows from (22); (2) if $1\le z\le {c}_{1}$, then the R.H.S. of (24) is at least 1 (by assumption, $\beta >1$) and the inequality trivially holds. The concentration inequality, i.e., Eq. (24), is now almost the same as the desired form in Theorem 3. The only difference is that it only holds for $n\ge {N}_{p}^{\prime}$. This is not hard to resolve. The easiest approach, which we show in the following, is to refine the constants to ensure that when $$, Eq. (24) is trivially true. To this end, we note that $n{\overline{X}}_{n}n{\mu}_{*}\le 2Rn$. For each $$, there is a corresponding $\overline{z}(n)$ such that ${n}^{\frac{\alpha}{\xi (1\eta )}}\overline{z}(n)=2Rn$. That is,
$$ 
This then implies that for each $$, the following inequality trivially holds:
$$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {n}^{\frac{\alpha}{\xi (1\eta )}}z)\le \frac{\overline{z}{(n)}^{\alpha 1}}{{z}^{\alpha 1}},\forall z\ge 1.$$ 
To see why, note that for each $$: (1) if $z\ge \overline{z}(n)$, then ${n}^{\frac{\alpha}{\xi (1\eta )}}z\ge 2Rn$ and the above probability should be $0$. Hence, any positive number on the R.H.S. makes the inequality trivially true; (2) if $$, the R.H.S. is at least 1, which again makes the inequality hold. For convenience, define
$$  (25) 
Then, it is easy to see that for every $n\ge 1$ and every $z\ge 1$, we have
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ 
where the constants are given by
${\eta}^{\prime}$  $={\displaystyle \frac{\alpha}{\xi (1\eta )}},$  (26)  
${\xi}^{\prime}$  $=\alpha 1,$  (27)  
${\beta}^{\prime}$  $=\mathrm{max}\{{c}_{2},\mathrm{\hspace{0.25em}2}{c}_{1}^{\alpha 1}\cdot \mathrm{max}(\beta ,{\displaystyle \frac{2(K1)}{(\alpha 1){(1+A({N}_{p}^{\prime}))}^{\alpha 1}}})\}.$  (28) 
Finally, notice that since $\alpha \ge \xi \eta (1\eta )$ and $$, we have $$. Note that per (23), ${c}_{1}$ depends on $R,K,{\mathrm{\Delta}}_{\mathrm{min}},\beta ,\xi $ and $\eta $. In addition, ${c}_{2}$ depends on $R,K,{\mathrm{\Delta}}_{\mathrm{min}},\beta ,\xi ,\alpha ,\eta $ and ${N}_{p}^{\prime}$ depends on $R,K,{\mathrm{\Delta}}_{\mathrm{min}},\beta ,\xi ,\alpha ,\eta $. Therefore, ${\beta}^{\prime}$ depends on $R,K,{\mathrm{\Delta}}_{\mathrm{min}},\beta ,$ $\xi ,\alpha ,\eta $. The other direction follows exactly the same reasoning, and this completes the proof of Theorem 3.
By the choice of ${A}_{i}(t)$, $s$ and $t$, we have ${B}_{t,s}=\frac{\mathrm{\Phi}(s,{t}^{\alpha})}{s}\le \frac{\mathrm{\Phi}({A}_{i}(t),{t}^{\alpha})}{{A}_{i}(t)}\le \frac{{\mathrm{\Delta}}_{i}}{2}$. Therefore,
$\mathbb{P}({U}_{i,s,t}>{\mu}_{*})$  $=\mathbb{P}({\overline{X}}_{i,s}+{B}_{t,s}>{\mu}_{*})$  
$=\mathbb{P}({\overline{X}}_{i,s}{\mu}_{i}>{\mathrm{\Delta}}_{i}{B}_{t,s})$  
$\le \mathbb{P}({\overline{X}}_{i,s}{\mu}_{i}>{B}_{t,s})$  ${\mathrm{\Delta}}_{i}\ge 2{B}_{t,s}$  
$\le {t}^{\alpha}.$  $\text{by concentration (}\text{13}\text{)}.$ 
If a suboptimal arm $i$ is chosen at time $t+1$, i.e., ${I}_{t+1}=i$, then at least one of the following two equations must be true: with notation ${T}_{*}(\cdot )={T}_{{i}_{*}}(\cdot $),
${U}_{{i}_{*},{T}_{*}(t),t}$  $\le {\mu}_{*},$  (29)  
${U}_{i,{T}_{i}(t),t}$  $>{\mu}_{*}.$  (30) 
Indeed, if both inequalities are false, we have ${U}_{{i}_{*},{T}_{*}(t),t}>{\mu}_{*}\ge {U}_{i,{T}_{i}(t),t}$, which is a contradiction to ${I}_{t+1}=i$. We now use this fact to prove Lemma 2.
Case 1: $n>{A}_{i}(n)$. Note that such $n$ exists because ${A}_{i}(n)$ grows with a polynomial order $O\left({n}^{\frac{\alpha}{\xi (1\eta )}}\right)$ and $$, i.e., ${A}_{i}(n)=o(n)$. Then,
${T}_{i}(n)$  $={\displaystyle \sum _{t=0}^{n1}}\mathbb{I}\{{I}_{t+1}=i\}\stackrel{(a)}{=}1+{\displaystyle \sum _{t=K}^{n1}}\mathbb{I}\{{I}_{t+1}=i\}$  
$$  
$\le {A}_{i}(n)+{\displaystyle \sum _{t=K}^{n1}}\mathbb{I}\{{I}_{t+1}=i,{T}_{i}(t)\ge {A}_{i}(n)\},$ 
where equality (a) follows from the fact that ${B}_{t,s}=\mathrm{\infty}$ if $s=0$.
To analyze the above summation, we note that from (29) and (30),
$\mathbb{I}\{{I}_{t+1}=i,{T}_{i}(t)\ge {A}_{i}(n)\}$  $\le \mathbb{I}\{{U}_{{i}_{*},{T}_{*}(t),t}\le {\mu}_{*}\text{or}{U}_{i,{T}_{i}(t),t}{\mu}_{*},{T}_{i}(t)\ge {A}_{i}(n)\}$  
$\le \mathbb{I}\{{U}_{i,{T}_{i}(t),t}>{\mu}_{*},{T}_{i}(t)\ge {A}_{i}(n)\}+\mathbb{I}\{{U}_{{i}_{*},{T}_{*}(t),t}\le {\mu}_{*},{T}_{i}(t)\ge {A}_{i}(n)\}$  
$\le \mathbb{I}\{{U}_{i,{T}_{i}(t),t}>{\mu}_{*},{T}_{i}(t)\ge {A}_{i}(n)\}+\mathbb{I}\{{U}_{{i}_{*},{T}_{*}(t),t}\le {\mu}_{*}\}$  
$=\mathbb{I}\{\exists s:{A}_{i}(n)\le s\le t,\text{s.t.}{U}_{i,s,t}{\mu}_{*}\}+\mathbb{I}\{\exists {s}_{*}:1\le {s}_{*}\le t,\text{s.t.}{U}_{{i}_{*},{s}_{*},t}\le {\mu}_{*}\}.$ 
To summarize, we have proved that
$\mathbb{E}[{T}_{i}(n)]$  $\le {A}_{i}(n)+{\displaystyle \sum _{t={A}_{i}(n)}^{n1}}\mathbb{P}((\mathit{\text{29}})\text{or}(\mathit{\text{30}})\text{is true, and}{T}_{i}(t)\ge {A}_{i}(n))$  
$\le {A}_{i}(n)+{\displaystyle \sum _{t={A}_{i}(n)}^{n1}}\left[\mathbb{P}\left(\underset{{E}_{1}}{\underset{\u23df}{\exists s:{A}_{i}(n)\le s\le t,\text{s.t.}{U}_{i,s,t}{\mu}_{*}}}\right)+\mathbb{P}\left(\underset{{E}_{2}}{\underset{\u23df}{\exists {s}_{*}:1\le {s}_{*}\le t,\text{s.t.}{U}_{{i}_{*},{s}_{*},t}\le {\mu}_{*}}}\right)\right].$  (31) 
To complete the proof of Lemma 2, it suffices to bound the probabilities of the two events ${E}_{1}$ and ${E}_{2}$. To this end, we use a union bound:
$\mathbb{P}\left({E}_{1}\right)$  $\le {\displaystyle \sum _{s={A}_{i}(n)}^{t}}\mathbb{P}({U}_{i,s,t}>{\mu}_{*})\stackrel{(a)}{\le}{\displaystyle \sum _{s={A}_{i}(n)}^{t}}{t}^{\alpha}\le t\cdot {t}^{\alpha}={t}^{1\alpha},$ 
where the step $(a)$ follows from ${A}_{i}(n)\ge {A}_{i}(t)$ and Lemma 1. We bound $\mathbb{P}({E}_{2})$ in a similar way:
$\mathbb{P}({E}_{2})$  $\le {\displaystyle \sum _{{s}_{*}=1}^{t}}\mathbb{P}({U}_{{i}_{*},{s}_{*},t}\le {\mu}_{*})={\displaystyle \sum _{{s}_{*}=1}^{t}}\mathbb{P}({\overline{X}}_{{i}_{*},{s}_{*}}+{B}_{t,{s}_{*}}\le {\mu}_{*})\stackrel{(a)}{\le}{\displaystyle \sum _{{s}_{*}=1}^{t}}{t}^{\alpha}\le {t}^{1\alpha},$ 
where step $(a)$ follows from concentration (cf. (13)). By substituting the bounds of $\mathbb{P}({E}_{1})$ and $\mathbb{P}({E}_{2})$ into (31), we have:
$\mathbb{E}[{T}_{i}(n)]$  $\le {A}_{i}(n)+{\displaystyle \sum _{t={A}_{i}(n)}^{n1}}2{t}^{1\alpha}$  
$\le {A}_{i}(n)+{\displaystyle {\int}_{{A}_{i}(n)1}^{\mathrm{\infty}}}2{t}^{1\alpha}\mathit{d}t$  $\alpha >2$  
$={A}_{i}(n)+{\displaystyle \frac{2{\left({A}_{i}(n)1\right)}^{2\alpha}}{\alpha 2}}$  
$\le {A}_{i}(n)+{\displaystyle \frac{2}{\alpha 2}}$  
$\le {\left({\displaystyle \frac{2}{{\mathrm{\Delta}}_{i}}}\cdot {\beta}^{1/\xi}\right)}^{\frac{1}{1\eta}}\cdot {n}^{\frac{\alpha}{\xi (1\eta )}}+{\displaystyle \frac{2}{\alpha 2}}+1.$ 
Case 2: $n\le {A}_{i}(n)$. Note that if $n$ is such that $n\le {A}_{i}(n)$, then the above bound trivially holds because ${T}_{i}(n)\le n\le {A}_{i}(n)$. This completes the proof of Lemma 2.
We first prove one direction, namely, $\mathbb{P}(n{\mu}_{*}n{\overline{X}}_{n}\ge {r}_{0}x)$. The other direction follows the similar steps, and we will comment on that at the end of this proof. The general idea underlying the proof is to rewrite the quantity $n{\mu}_{*}n{\overline{X}}_{n}$ as sums of terms that can be bounded using previous lemmas or assumptions. To begin with, note that
$n{\mu}_{*}n{\overline{X}}_{n}$  $=n{\mu}_{*}{\displaystyle \sum _{i=1}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}$  
$=n{\mu}_{*}{\displaystyle \sum _{t=1}^{{T}_{*}(n)}}{X}_{{i}_{*},t}{\displaystyle \sum _{i\ne {i}_{*}}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}$  
$=n{\mu}_{*}{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}+{\displaystyle \sum _{t={T}_{*}(n)+1}^{n}}{X}_{{i}_{*},t}{\displaystyle \sum _{i\ne {i}_{*}}}{\displaystyle \sum _{t=1}^{{T}_{i}(n)}}{X}_{i,t}$  
$\le n{\mu}_{*}{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}+2R{\displaystyle \sum _{i\ne {i}_{*}}}{T}_{i}(n),$ 
because ${X}_{i,t}\in [R,R]$ for all $i,t$. Therefore, we have
$\mathbb{P}(n{\mu}_{*}n{\overline{X}}_{n}\ge {r}_{0}x)$  $\le \mathbb{P}(n{\mu}_{*}{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}+2R{\displaystyle \sum _{i\ne {i}_{*}}}{T}_{i}(n)\ge {r}_{0}x)$  
$\le \mathbb{P}(n{\mu}_{*}{\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}\ge {n}^{\eta}x)+{\displaystyle \sum _{i\ne {i}_{*}}}\mathbb{P}({T}_{i}(n)\ge (3+A(n))x),$  (32) 
where the last inequality follows from the union bound.
To prove the theorem, we now bound the two terms in (32). By our concentration assumption, we can upper bound the first term as follows:
$$\mathbb{P}(n{\mu}_{*}\sum _{t=1}^{n}{X}_{{i}_{*},t}\ge {n}^{\eta}x)\le \frac{\beta}{{x}^{\xi}}.$$  (33) 
Next, we bound each term in the summation of (32). Fix $n$ and a suboptimal edge $i$. Let $u$ be an integer satisfying $u\ge A(n).$ For any $\tau \in \mathbb{R}$, consider the following two events:
${E}_{1}$  $=\{\text{For each integer}t\in [u,n],\text{we have}{U}_{i,u,t}\le \tau \},$  
${E}_{2}$  $=\{\text{For each integer}s\in [1,nu],\text{we have}{U}_{{i}_{*},s,u+s}\tau \}.$ 
As a first step, we want to show that
$${E}_{1}\cap {E}_{2}\Rightarrow {T}_{i}(n)\le u.$$  (34) 
To this end, let us condition on both events ${E}_{1}$ and ${E}_{2}$. Recall that ${B}_{t,s}$ is nondecreasing with respect to $t$. Then, for each $s$ such that $1\le s\le nu,$ and each $t$ such that $u+s\le t\le n$, it holds that
$${U}_{{i}_{*},s,t}={\overline{X}}_{{i}_{*},s}+{B}_{t,s}\ge {\overline{X}}_{{i}_{*},s}+{B}_{u+s,s}={U}_{{i}_{*},s,u+s}>\tau \ge {U}_{i,u,t}.$$ 
This implies that ${T}_{i}(n)\le u$. To see why, suppose that ${T}_{i}(n)>u$ and denote by ${t}^{\prime}$ the first time that arm $i$ has been played $u$ times, i.e., ${t}^{\prime}=\mathrm{min}\{t:t\le n,{T}_{i}(t)=u\}$. Note that by definition ${t}^{\prime}\ge u+{T}_{*}({t}^{\prime})$. Hence, for any time t such that $$, the above inequality implies that ${U}_{{i}_{*},{T}_{*}(t),t}>{U}_{i,u,t}$. That is, ${i}^{*}$ always has a higher upper confidence bound than $i$, and arm $i$ will not be selected, i.e., arm $i$ will not be played the $(u+1)$th time. This contradicts our assumption that ${T}_{i}(n)>u$, and hence we have the inequality ${T}_{i}(n)\le u$.
To summarize, we have established the fact that ${E}_{1}\cap {E}_{2}\Rightarrow {T}_{i}(n)\le u.$ As a result, we have:
$\mathrm{\{}{T}_{i}(n)>u\}$  $\subset \left({E}_{1}^{c}\cup {E}_{2}^{c}\right)=\left(\{\exists t:u\le t\le n\text{s.t.}{U}_{i,u,t}\tau \}\cup \{\exists s:1\le s\le nu,\text{s.t.}{U}_{{i}_{*},s,u+s}\le \tau \}\right).$ 
Using union bound, we obtain that
$$\mathbb{P}({T}_{i}(n)>u)\le \sum _{t=u}^{n}\mathbb{P}({U}_{i,u,t}>\tau )+\sum _{s=1}^{nu}\mathbb{P}({U}_{{i}_{*},s,u+s}\le \tau ).$$  (35) 
Note that for the above bound, we are free to choose $u$ and $\tau $ as long as $u\ge A(n)$. To connect with our goal (cf. (32)), in the following, we set $u=\lfloor (1+A(n))x\rfloor +1$ (recall that $x\ge 1$) and $\tau ={\mu}_{*}$ to bound $\mathbb{P}({T}_{i}(n)>u).$ Since $u\ge A(n)\ge {A}_{i}(n)$, by Lemma 1, we have
$\sum _{t=u}^{n}}\mathbb{P}({U}_{i,u,t}>{\mu}_{*})\le {\displaystyle \sum _{t=u}^{n}}{t}^{\alpha}\le {\displaystyle {\int}_{u1}^{\mathrm{\infty}}}{t}^{\alpha}dt$  $={\displaystyle \frac{{(u1)}^{1\alpha}}{\alpha 1}}$  
$={\displaystyle \frac{{(\lfloor (1+A(n))x\rfloor )}^{1\alpha}}{\alpha 1}}\le {\displaystyle \frac{{\left((1+A(n))x\right)}^{1\alpha}}{\alpha 1}}.$ 
As for the second summation in the R.H.S. of (35), we have that
$\sum _{s=1}^{nu}}\mathbb{P}({U}_{{i}_{*},s,u+s}\le \tau )$  $={\displaystyle \sum _{s=1}^{nu}}\mathbb{P}({U}_{{i}_{*},s,u+s}\le {\mu}_{*})$  
$={\displaystyle \sum _{s=1}^{nu}}\mathbb{P}({\overline{X}}_{{i}_{*},s}+{B}_{u+s,s}\le {\mu}_{*})$  
$\le {\displaystyle \sum _{s=1}^{nu}}{(s+u)}^{\alpha}={\displaystyle \sum _{t=1+u}^{n}}{t}^{\alpha}$  
$\le {\displaystyle {\int}_{u1}^{\mathrm{\infty}}}{t}^{\alpha}\mathit{d}t={\displaystyle \frac{{(u1)}^{1\alpha}}{\alpha 1}}\le {\displaystyle \frac{{\left((1+A(n))x\right)}^{1\alpha}}{\alpha 1}},$ 
where the first inequality follows from the concentration property, cf. (13). Combining the above inequalities and note that $(3+A(n))x>\lfloor (1+A(n))x\rfloor +1$:
$$\mathbb{P}({T}_{i}(n)\ge (3+A(n))x)\le \mathbb{P}({T}_{i}(n)>u)\le \frac{2{\left(\left(1+A(n)\right)x\right)}^{1\alpha}}{\alpha 1}.$$  (36) 
Substituting (33) and (36) into (32), we obtain
$$\mathbb{P}(n{\mu}_{*}n{\overline{X}}_{n}\ge {r}_{0}x)\le \frac{\beta}{{x}^{\xi}}+\sum _{i\ne {i}_{*}}\frac{2{\left(\left(1+A(n)\right)x\right)}^{1\alpha}}{\alpha 1},$$ 
which is the desired inequality in Lemma 3.
To complete the proof, we need to consider the other direction, i.e., $\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {r}_{0}x)$. The proof is almost identical. Note that
$n{\overline{X}}_{n}n{\mu}_{*}$  $={\displaystyle \sum _{i=1}^{K}}{T}_{i}(n){\overline{X}}_{i,{T}_{i}(n)}n{\mu}_{*}$  
$={\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}n{\mu}_{*}{\displaystyle \sum _{t={T}_{*}(n)+1}^{n}}{X}_{{i}_{*},t}+{\displaystyle \sum _{i\ne {i}_{*}}}{\displaystyle \sum _{t=1}^{{T}_{i}(n)}}{X}_{i,t}$  
$\le {\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}n{\mu}_{*}+2R{\displaystyle \sum _{i\ne {i}_{*}}}{T}_{i}(n),$ 
because ${X}_{i,t}\in [R,R]$ for all $i,t$. Therefore,
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{*}\ge {r}_{0}x)$  $\le \mathbb{P}({\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}n{\mu}_{*}+2R{\displaystyle \sum _{i\ne {i}_{*}}}{T}_{i}(n)\ge {r}_{0}x)$  
$\le \mathbb{P}({\displaystyle \sum _{t=1}^{n}}{X}_{{i}_{*},t}n{\mu}_{*}\ge {n}^{\eta}x)+{\displaystyle \sum _{i\ne {i}_{*}}}\mathbb{P}({T}_{i}(n)\ge (3+{A}_{i}(n))x).$ 
The desired inequality then follows exactly from the same reasoning of our previous proof.
In this section, we give a complete analysis for the fixeddepth Monte Carlo Tree Search (MCTS) algorithm illustrated in Algorithm 1 and prove Theorem 1. In effect, as discussed in Section id1, one can view a depth$H$ MCTS as a simulated version of $H$ steps value function iterations. Given the current value function proxy $\widehat{V}$, let ${V}^{(H)}(\cdot )$ be the value function estimation after $H$ steps of value function iteration starting with the proxy $\widehat{V}$. Then, we prove the result in two parts. First, we argue that due to the MCTS sampling process, the mean of the empirical estimation of value function at the query node $s$, or the root node of MCTS tree, is within $O({n}^{\eta 1})$ of ${V}^{(H)}(s)$ after $n$ simulations, with the given proxy $\widehat{V}$ being the input to the MCTS algorithm. Second, we argue that ${V}^{(H)}(s)$ is within ${\gamma}^{H}{\parallel \widehat{V}{V}^{*}\parallel}_{\mathrm{\infty}}\le {\gamma}^{H}{\epsilon}_{0}$ of the optimal value function. Putting this together leads to Theorem 1.
We start by a preliminary probabilistic lemma in Section id1 that will be useful throughout. Sections 4 and id1 argue the first part of the proof as explained above. Section id1 provides proof of the second part. And Section id1 concludes the proof of Theorem 1.
We state the following probabilistic lemma that is useful throughout. Proof can be found in Section id1.
Lemma 4
Consider realvalued random variables ${X}_{i}\mathrm{,}{Y}_{i}$ for $i\mathrm{\ge}\mathrm{1}$ such that $X$s are independent and identically distributed taking values in $\mathrm{[}\mathrm{}B\mathrm{,}B\mathrm{]}$ for some $B\mathrm{>}\mathrm{0}$, $X$s are independent of $Y$s, and $Y$s satisfy

A.
Convergence: for $n\ge 1$, with notation ${\overline{Y}}_{n}=\frac{1}{n}\left({\sum}_{i=1}^{n}{Y}_{i}\right)$,
$\underset{n\to \mathrm{\infty}}{lim}\mathbb{E}[{\overline{Y}}_{n}]$ $={\mu}_{Y}.$ 
B.
Concentration: there exist constants, $\beta >1$, $\xi >0$, $$ such that for $n\ge 1$ and $z\ge 1$,
$\mathbb{P}(n{\overline{Y}}_{n}n{\mu}_{Y}\ge {n}^{\eta}z)\le {\displaystyle \frac{\beta}{{z}^{\xi}}},\mathbb{P}(n{\overline{Y}}_{n}n{\mu}_{Y}\le {n}^{\eta}z)\le {\displaystyle \frac{\beta}{{z}^{\xi}}}.$
Let ${Z}_{i}\mathrm{=}{X}_{i}\mathrm{+}\rho \mathit{}{Y}_{i}$ for some $\rho \mathrm{>}\mathrm{0}$. Then, $Z$s satisfy

A.
Convergence: for $n\ge 1$, with notation ${\overline{Z}}_{n}=\frac{1}{n}\left({\sum}_{i=1}^{n}{Z}_{i}\right)$, and ${\mu}_{X}=\mathbb{E}[{X}_{1}]$,
$\underset{n\to \mathrm{\infty}}{lim}\mathbb{E}[{\overline{Z}}_{n}]$ $={\mu}_{X}+\rho {\mu}_{Y}.$ 
B.
Concentration: there exist constant ${\beta}^{\prime}>1$ depending upon $\rho ,\xi ,\beta $ and $B$, such that for $n\ge 1$ and $z\ge 1$,
$\mathbb{P}(n{\overline{Z}}_{n}n({\mu}_{X}+\rho {\mu}_{Y})\ge {n}^{\eta}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{\xi}}},\mathbb{P}(n{\overline{Z}}_{n}n({\mu}_{X}+\rho {\mu}_{Y})\le {n}^{\eta}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{\xi}}}.$
The goal is to understand the empirical reward observed at the query node for MCTS or the root node of the MCTS tree. In particular, we argue that the mean of the empirical reward at the root node of the MCTS tree is within $O({n}^{\eta 1})$ of the mean reward obtained at it assuming access to infinitely many samples. We start by analyzing the reward collected at the nodes that are at leaf level $H$ and level $H1$.
The nodes at leaf level, i.e., level $H$, are children of nodes at level $H1$ in the MCTS tree. Let there be ${n}_{H1}$ nodes at level $H1$ corresponding to states ${s}_{1,H1},\mathrm{\dots},{s}_{{n}_{H1},H1}\in \mathcal{S}$. Consider node $i\in [{n}_{H1}]$ at level $H1$, corresponding to state ${s}_{i,H1}$. As part of the algorithm, whenever this node is visited, one of the $K$ feasible actions is taken. When an action $a\in [K]$ is taken, the node ${s}_{H}^{\prime}={s}_{i,H1}\circ a$, at the leaf level $H$ is reached. This results in reward at node ${s}_{i,H1}$ (at level $H1$) being equal to $\mathcal{R}({s}_{i,H1},a)+\gamma {\stackrel{~}{v}}^{(H)}({s}_{H}^{\prime})$. Here, for each $s\in \mathcal{S}$ and $a\in [K]$, the reward $\mathcal{R}(s,a)$ is an independent, bounded random variable taking value in $[{R}_{\mathrm{max}},{R}_{\mathrm{max}}]$ with distribution dependent on $s,a$; ${\stackrel{~}{v}}^{(H)}(\cdot )$ is the input of value function proxy to the MCTS algorithm denoted as $\widehat{V}(\cdot )$, and $\gamma \in [0,1)$ is the discount factor. Recall that ${\epsilon}_{0}={\parallel \widehat{V}{V}^{*}\parallel}_{\mathrm{\infty}}$ and ${\parallel {V}^{*}\parallel}_{\mathrm{\infty}}\le {V}_{\mathrm{max}}$. Therefore, ${\parallel {\stackrel{~}{v}}^{(H)}\parallel}_{\mathrm{\infty}}={\parallel \widehat{V}\parallel}_{\mathrm{\infty}}\le {V}_{\mathrm{max}}+{\epsilon}_{0}$, and the reward collected at node ${s}_{i,H1}$ by following any action is bounded, in absolute value, by ${\stackrel{~}{R}}_{\mathrm{max}}^{(H1)}={R}_{\mathrm{max}}+\gamma ({V}_{\mathrm{max}}+{\epsilon}_{0})$.
As part of the MCTS algorithm as described in (5), when node ${s}_{i,H1}$ is visited for the $t+1$ time with $t\ge 0$, the action taken is
$\mathrm{arg}\underset{a\in \mathcal{A}}{\mathrm{max}}$  $\left\{{\displaystyle \frac{1}{{u}_{a}}}{\displaystyle \sum _{j=1}^{{u}_{a}}}\left(r({s}_{i,H1},a)(j)+\gamma {\stackrel{~}{v}}^{(H)}({s}_{i,H1}\circ a)(j)\right)+{\displaystyle \frac{{\left({\beta}^{(H)}\right)}^{1/{\xi}^{(H)}}\cdot {\left(t\right)}^{{\alpha}^{(H)}/{\xi}^{(H)}}}{{\left({u}_{a}\right)}^{1{\eta}^{(H)}}}}\right\},$ 
where ${u}_{a}\le t$ is the number of times action $a$ has been chosen thus far at state ${s}_{i,H1}$ in the $t$ visits so far, $r({s}_{i,H1},a)(j)$ is the $j$th sample of random variable per distribution $\mathcal{R}({s}_{i,H1},a)$, and ${\stackrel{~}{v}}^{(H)}({s}_{i,H1}\circ a)(j)$ is the reward evaluated at leaf node ${s}_{i,H1}\circ a$ for the $j$th time. Note that for all $j$, the reward evaluated at leaf node ${s}_{i,H1}\circ a$ is the same and equals to ${\stackrel{~}{v}}^{(H)}(\cdot )$, the input value function proxy for the algorithm. When ${u}_{a}=0$, we use notation $\mathrm{\infty}$ to represent quantity inside the $\mathrm{arg}\mathrm{max}$. The net discounted reward collected by node ${s}_{i,H1}$ during its total of $t\ge 1$ visits is simply the sum of rewards obtained by selecting the actions per the policy – which includes the reward associated with taking an action and the evaluation of ${\stackrel{~}{v}}^{(H)}(\cdot )$ for appropriate leaf node, discounted by $\gamma $. In effect, at each node ${s}_{i,H1}$, we are using the UCB policy described in Section id1 with parameters ${\alpha}^{(H)},{\beta}^{(H)},{\xi}^{(H)},{\eta}^{(H)}$ with $K$ possible actions, where the rewards collected by playing any of these $K$ actions each time is simply the summation of bounded independent and identical (for a given action) random variable and a deterministic evaluation. By applying Lemma 4, where $X$s correspond to independent rewards, $\rho =\gamma $, and $Y$s correspond to deterministic evaluations of ${\stackrel{~}{v}}^{(H)}(\cdot )$, we obtain that for given ${\xi}^{(H)}>0$ and ${\eta}^{(H)}\in [\frac{1}{2},1)$, there exists ${\beta}^{(H)}$ such that the collected rewards at ${s}_{i,H1}$ (i.e., sum of i.i.d. reward and deterministic evaluations) satisfy the convergence property cf. (12) and concentration property cf. (13) stated in Section id1. Therefore, by an application of Theorem 3, we conclude Lemma 5 stated below. We define some notations first:
${\mu}_{a}^{(H1)}({s}_{i,H1})$  $=\mathbb{E}[\mathcal{R}({s}_{i,H1},a)]+\gamma {\stackrel{~}{v}}^{(H)}({s}_{i,H1}\circ a),$  
${\mu}_{*}^{(H1)}({s}_{i,H1})$  $=\underset{a\in [K]}{\mathrm{max}}{\mu}_{a}^{(H1)}({s}_{i,H1})$  
${a}_{*}^{(H1)}({s}_{i,H1})$  $\in \mathrm{arg}\underset{a\in [K]}{\mathrm{max}}{\mu}_{a}^{(H1)}({s}_{i,H1})$  (37)  
${\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}({s}_{i,H1})$  $={\mu}_{*}^{(H1)}({s}_{i,H1})\underset{a\ne {a}_{*}^{(H1)}({s}_{i,H1})}{\mathrm{max}}{\mu}_{a}^{(H1)}({s}_{i,H1}).$ 
We shall assume that the maximizer in the set $\mathrm{arg}{\mathrm{max}}_{a\in [K]}{\mu}_{a}^{(H1)}({s}_{i,H1})$ is unique, i.e. ${\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}({s}_{i,H1})>0$. And further note that all rewards belong to $[{\stackrel{~}{R}}_{\mathrm{max}}^{(H1)},{\stackrel{~}{R}}_{\mathrm{max}}^{(H1)}]$.
Lemma 5
Consider a node corresponding to state ${s}_{i\mathrm{,}H\mathrm{}\mathrm{1}}$ at level $H\mathrm{}\mathrm{1}$ within the MCTS for $i\mathrm{\in}\mathrm{[}{n}_{H\mathrm{}\mathrm{1}}\mathrm{]}$. Let ${\stackrel{\mathrm{~}}{v}}^{\mathrm{(}H\mathrm{}\mathrm{1}\mathrm{)}}\mathit{}{\mathrm{(}{s}_{i\mathrm{,}H\mathrm{}\mathrm{1}}\mathrm{)}}_{n}$ be the total discounted reward collected at ${s}_{i\mathrm{,}H\mathrm{}\mathrm{1}}$ during $n\mathrm{\ge}\mathrm{1}$ visits of it, to one of its $K$ leaf nodes under the UCB policy. Then, for the choice of appropriately large ${\beta}^{\mathrm{(}H\mathrm{)}}\mathrm{>}\mathrm{0}$, for a given ${\xi}^{\mathrm{(}H\mathrm{)}}\mathrm{>}\mathrm{0}$, ${\eta}^{\mathrm{(}H\mathrm{)}}\mathrm{\in}\mathrm{[}\frac{\mathrm{1}}{\mathrm{2}}\mathrm{,}\mathrm{1}\mathrm{)}$ and ${\alpha}^{\mathrm{(}H\mathrm{)}}\mathrm{>}\mathrm{2}$, we have

A.
Convergence:
$\left\mathbb{E}\left[{\displaystyle \frac{1}{n}}{\stackrel{~}{v}}^{(H1)}{({s}_{i,H1})}_{n}\right]{\mu}_{*}^{(H1)}({s}_{i,H1})\right$ $\le {\displaystyle \frac{2{\stackrel{~}{R}}_{\mathrm{max}}^{(H1)}(K1)\cdot \left({\left(\frac{2{({\beta}^{(H)})}^{\frac{1}{{\xi}^{(H)}}}}{{\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}({s}_{i,H1})}\right)}^{\frac{1}{1{\eta}^{(H)}}}\cdot {n}^{\frac{{\alpha}^{(H)}}{{\xi}^{(H)}(1{\eta}^{(H)})}}+\frac{2}{{\alpha}^{(H)}2}+1\right)}{n}}.$ 
B.
Concentration: there exist constants, ${\beta}^{\prime}>1$ and ${\xi}^{\prime}>0$ and $$ such that for every $n\ge 1$ and every $z\ge 1$,
$\mathbb{P}({\stackrel{~}{v}}^{(H1)}{({s}_{i,H1})}_{n}n{\mu}_{*}^{(H1)}({s}_{i,H1})\ge {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ $\mathbb{P}({\stackrel{~}{v}}^{(H1)}{({s}_{i,H1})}_{n}n{\mu}_{*}^{(H1)}({s}_{i,H1})\le {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ where ${\eta}^{\prime}=\frac{{\alpha}^{(H)}}{{\xi}^{(H)}(1{\eta}^{(H)})}$, ${\xi}^{\prime}={\alpha}^{(H)}1$, and ${\beta}^{\prime}$ is a large enough constant that is function of parameters ${\alpha}^{(H)},{\beta}^{(H)},{\xi}^{(H)},$ ${\eta}^{(H)},{\stackrel{~}{R}}_{\mathrm{max}}^{(H1)},K,{\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}({s}_{i,H1})$.
Let ${\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}={\mathrm{min}}_{i\in [{n}_{H1}]}{\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}({s}_{i,H1})$. Then, the rate of convergence for each node ${s}_{i,H1}$, $i\in [{n}_{H1}]$ can be uniformly simplified as
${\delta}_{n}^{(H1)}=$  $\frac{2{\stackrel{~}{R}}_{\mathrm{max}}^{(H1)}(K1)\cdot \left({\left(\frac{2{({\beta}^{(H)})}^{\frac{1}{{\xi}^{(H)}}}}{{\mathrm{\Delta}}_{\mathrm{min}}^{(H1)}}\right)}^{\frac{1}{1{\eta}^{(H)}}}\cdot {n}^{\frac{{\alpha}^{(H)}}{{\xi}^{(H)}(1{\eta}^{(H)})}}+\frac{2}{{\alpha}^{(H)}2}+1\right)}{n}$  
$=$  $\mathrm{}\mathrm{\Theta}\left({n}^{\frac{{\alpha}^{(H)}}{{\xi}^{(H)}(1{\eta}^{(H)})}1}\right)$  
$\stackrel{(a)}{=}$  $\mathrm{}O\left({n}^{\eta 1}\right),$ 
where (a) holds since ${\alpha}^{(H)}={\xi}^{(H)}(1{\eta}^{(H)}){\eta}^{(H)},{\eta}^{(H)}=\eta $. It is worth remarking that ${\mu}_{*}^{(H1)}({s}_{i,H1})$, as defined in (37), is precisely the value function estimation for ${s}_{i,H1}$ at the end of one step of value iteration starting with $\widehat{V}$.
Lemma 5 suggests that the necessary assumption of Theorem 3, i.e. (12) and (13), are satisfied by ${\stackrel{~}{v}}_{n}^{(H1)}$ for each node or state at level $H1$, with ${\alpha}^{(H1)},{\xi}^{(H1)},{\eta}^{(H1)}$ as defined per relationship (6)  (8) and with appropriately defined large enough constant ${\beta}^{(H1)}$. We shall argue that result similar to Lemma 5, but for node at level $H2$, continues to hold with parameters ${\alpha}^{(H2)},{\xi}^{(H2)},{\eta}^{(H2)}$ as defined per relationship (6)  (8) and with appropriately defined large enough constant ${\beta}^{(H2)}$. And similar argument will continue to apply going from level $h$ to $h1$ for all $h\le H1$. That is, we shall assume that the necessary assumption of Theorem 3, i.e. (12) and (13), holds for ${\stackrel{~}{v}}^{(h)}(\cdot )$, for all nodes at level $h$ with ${\alpha}^{(h)},{\xi}^{(h)},{\eta}^{(h)}$ as defined per relationship (6)  (8) and with appropriately defined large enough constant ${\beta}^{(h)}$, and then argue that such holds for nodes at level $h1$ as well. This will, using mathematical induction, allow us to prove the results for all $h\ge 1$.
To that end, consider any node at level $h1$. Let there be ${n}_{h1}$ nodes at level $h1$ corresponding to states ${s}_{1,h1},\mathrm{\dots},{s}_{{n}_{h1},h1}\in \mathcal{S}$. Consider a node corresponding to state ${s}_{i,h1}$ at level $h1$ within the MCTS for $i\in [{n}_{h1}].$ As part of the algorithm, whenever this node is visited, one of the $K$ feasible action is taken. When an action $a\in [K]$ is taken, the node ${s}_{h}^{\prime}={s}_{i,h1}\circ a$, at the level $h$ is reached. This results in reward at node ${s}_{i,h1}$ at level $h1$ being equal to $\mathcal{R}({s}_{i,h1},a)+\gamma {\stackrel{~}{v}}^{(h)}({s}_{h}^{\prime})$. As noted before, $\mathcal{R}(s,a)$ is an independent, bounded valued random variable while ${\stackrel{~}{v}}^{(h)}(\cdot )$ is effectively collected by following a path all the way to the leaf level. Inductively, we assume that ${\stackrel{~}{v}}^{(h)}(\cdot )$ satisfies the convergence and concentration property for each node or state at level $h$, with ${\alpha}^{(h)},{\xi}^{(h)},{\eta}^{(h)}$ as defined per relationship (6)  (8) and with appropriately defined large enough constant ${\beta}^{(h)}$. Therefore, by an application of Lemma 4, it follows that this combined reward continues to satisfy (12) and (13), with ${\alpha}^{(h)},{\xi}^{(h)},{\eta}^{(h)}$ as defined per relationship (6)  (8) and with a large enough constant which we shall denote as ${\beta}^{(h)}$. These constants are used by the MCTS policy. By an application of Theorem 3, we can obtain the following Lemma 6 regarding the convergence and concentration properties for the reward sequence collected at node ${s}_{i,h1}$ at level $h1.$ Similar to the notation in Eq. (37), let
${\mu}_{a}^{(h1)}({s}_{i,h1})$  $=\mathbb{E}[\mathcal{R}({s}_{i,h1},a)]+\gamma {\mu}_{*}^{(h)}({s}_{i,h1}\circ a)$  
${\mu}_{*}^{(h1)}({s}_{i,h1})$  $=\underset{a\in [K]}{\mathrm{max}}{\mu}_{a}^{(h1)}({s}_{i,h1})$  
${a}_{*}^{(h1)}({s}_{i,h1})$  $\in \mathrm{arg}\underset{a\in [K]}{\mathrm{max}}{\mu}_{a}^{(h1)}({s}_{i,h1})$  (38)  
${\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}({s}_{i,h1})$  $={\mu}_{*}^{(h1)}({s}_{i,h1})\underset{a\ne {a}_{*}^{(h1)}({s}_{i,h1})}{\mathrm{max}}{\mu}_{a}^{(h1)}({s}_{i,h1}).$ 
Again, we shall assume that the maximizer in the set $\mathrm{arg}{\mathrm{max}}_{a\in [K]}{\mu}_{a}^{(h1)}({s}_{i,h1})$ is unique, i.e. ${\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}({s}_{i,h1})>0$. Define ${\stackrel{~}{R}}_{\mathrm{max}}^{(h1)}={R}_{\mathrm{max}}+\gamma {\stackrel{~}{R}}_{\mathrm{max}}^{(h)},$ where ${\stackrel{~}{R}}^{(H)}={V}_{\mathrm{max}}+{\epsilon}_{0}.$ Note that all rewards collected at level $h1$ belong to $[{\stackrel{~}{R}}_{\mathrm{max}}^{(h1)},{\stackrel{~}{R}}_{\mathrm{max}}^{(h1)}]$.
Lemma 6
Consider a node corresponding to state ${s}_{i\mathrm{,}h\mathrm{}\mathrm{1}}$ at level $h\mathrm{}\mathrm{1}$ within the MCTS for $i\mathrm{\in}\mathrm{[}{n}_{h\mathrm{}\mathrm{1}}\mathrm{]}$. Let ${\stackrel{\mathrm{~}}{v}}^{\mathrm{(}h\mathrm{}\mathrm{1}\mathrm{)}}\mathit{}{\mathrm{(}{s}_{i\mathrm{,}h\mathrm{}\mathrm{1}}\mathrm{)}}_{n}$ be the total discounted reward collected at ${s}_{i\mathrm{,}h\mathrm{}\mathrm{1}}$ during $n\mathrm{\ge}\mathrm{1}$ visits. Then, for the choice of appropriately large ${\beta}^{\mathrm{(}h\mathrm{)}}\mathrm{>}\mathrm{0}$, for a given ${\xi}^{\mathrm{(}h\mathrm{)}}\mathrm{>}\mathrm{0}$, ${\eta}^{\mathrm{(}h\mathrm{)}}\mathrm{\in}\mathrm{[}\frac{\mathrm{1}}{\mathrm{2}}\mathrm{,}\mathrm{1}\mathrm{)}$ and ${\alpha}^{\mathrm{(}h\mathrm{)}}\mathrm{>}\mathrm{2}$, we have

A.
Convergence:
$\left\mathbb{E}\left[{\displaystyle \frac{1}{n}}{\stackrel{~}{v}}^{(h1)}{({s}_{i,h1})}_{n}\right]{\mu}_{*}^{(h1)}({s}_{i,h1})\right$ $\le {\displaystyle \frac{2{\stackrel{~}{R}}_{\mathrm{max}}^{(h1)}(K1)\cdot \left({\left(\frac{2{({\beta}^{(h)})}^{\frac{1}{{\xi}^{(h)}}}}{{\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}({s}_{i,h1})}\right)}^{\frac{1}{1{\eta}^{(h)}}}\cdot {n}^{\frac{{\alpha}^{(h)}}{{\xi}^{(h)}(1{\eta}^{(h)})}}+\frac{2}{{\alpha}^{(h)}2}+1\right)}{n}}.$ 
B.
Concentration: there exist constants, ${\beta}^{\prime}>1$ and ${\xi}^{\prime}>0$ and $$ such that for $n\ge 1$, $z\ge 1$,
$\mathbb{P}({\stackrel{~}{v}}^{(h1)}{({s}_{i,h1})}_{n}n{\mu}_{*}^{(h1)}({s}_{i,h1})\ge {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ $\mathbb{P}({\stackrel{~}{v}}^{(h1)}{({s}_{i,h1})}_{n}n{\mu}_{*}^{(h1)}({s}_{i,h1})\le {n}^{{\eta}^{\prime}}z)\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{{\xi}^{\prime}}}},$ where ${\eta}^{\prime}=\frac{{\alpha}^{(h)}}{{\xi}^{(h)}(1{\eta}^{(h)})}$, ${\xi}^{\prime}={\alpha}^{(h)}1$, and ${\beta}^{\prime}$ is a large enough constant that is function of parameters ${\alpha}^{(h)},{\beta}^{(h)},{\xi}^{(h)},$ ${\eta}^{(h)},{\stackrel{~}{R}}_{\mathrm{max}}^{(h1)},K,{\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}({s}_{i,h1})$.
As before, let us define ${\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}={\mathrm{min}}_{i\in [{n}_{h1}]}{\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}({s}_{i,h1})$. Similarly, we can show that for every node ${s}_{i,h1}$, $i\in [{n}_{h1}]$, the rate of convergence in Lemma 6 can be uniformly simplified as
${\delta}_{n}^{(h1)}$  $={\displaystyle \frac{2{\stackrel{~}{R}}_{\mathrm{max}}^{(h1)}(K1)\cdot \left({\left(\frac{2{({\beta}^{(h)})}^{\frac{1}{{\xi}^{(h)}}}}{{\mathrm{\Delta}}_{\mathrm{min}}^{(h1)}}\right)}^{\frac{1}{1{\eta}^{(h)}}}\cdot {n}^{\frac{{\alpha}^{(h)}}{{\xi}^{(h)}(1{\eta}^{(h)})}}+\frac{2}{{\alpha}^{(h)}2}+1\right)}{n}}$  
$\mathrm{}=\mathrm{\Theta}\left({n}^{\frac{{\alpha}^{(h)}}{{\xi}^{(h)}(1{\eta}^{(h)})}1}\right)=O\left({n}^{\eta 1}\right),$ 
where the last equality holds as ${\alpha}^{(h)}={\xi}^{(h)}(1{\eta}^{(h)}){\eta}^{(h)}$ and ${\eta}^{(h)}=\eta .$ Again, it is worth remarking, inductively, that ${\mu}_{*}^{(h1)}({s}_{i,h1})$ is precisely the value function estimation for ${s}_{i,h1}$ at the end of $Hh+1$ steps of value iteration starting with $\widehat{V}$.
Remark (Recursive Relation among Parameters). With the above development, we are ready to elaborate our choice of parameters in Theorem 1, defined recursively via Eqs. (6)(8). In essence, those parameter requirements originate from our analysis of the nonstationary MAB, i.e., Theorem 3. Recall that from our previous analysis, the key to establish the MCTS guarantee is to recursively argue the convergence and the polynomial concentration properties at each level; that is, we recursively solve the nonstationary MAB problem at each level. In order to do so, we apply our result on the nonstationary MAB (Theorem 3) recursively at each level. Importantly, recall that Theorem 3 only holds when $$ and $\alpha >2$, under which it leads to the recursive conclusions ${\eta}^{\prime}=\frac{\alpha}{\xi (1\eta )}$ and ${\xi}^{\prime}=\alpha 1$. Using our notation with superscript indicating the levels, this means that apart from the parameters at the leaf level (level $H$) which could be freely chosen, we must choose parameters of other levels recursively so that the following conditions hold:
$$  
${\xi}^{(h)}={\alpha}^{(h+1)}1\text{and}{\eta}^{(h)}={\displaystyle \frac{{\alpha}^{(h+1)}}{{\xi}^{(h+1)}(1{\eta}^{(h+1)})}}.$ 
It is not hard to see that the conditions in Theorem 1 guarantee the above. There might be other sequences of parameters satisfying the requirements, but our particular choice gives cleaner analysis as presented in this paper.
We now move to the second part of the proof. The value function iteration improves the estimation of optimal value function by iterating Bellman equation. In effect, the MCTS tree is “unrolling” $H$ steps of such an iteration. Precisely, let ${V}^{(h)}(\cdot )$ denote the value function after $h$ iterations starting with ${V}^{(0)}=\widehat{V}$. By definition, for any $h\ge 0$ and $s\in \mathcal{S}$,
${V}^{(h+1)}(s)$  $=\underset{a\in [K]}{\mathrm{max}}\left(\mathbb{E}[\mathcal{R}(s,a)]+\gamma {V}^{(h)}(s\circ a)\right).$  (39) 
Recall that value iteration is contractive with respect to $\parallel \cdot {\parallel}_{\mathrm{\infty}}$ norm (cf. Bertsekas (2017)). That is, for any $h\ge 0$,
${\parallel {V}^{(h+1)}{V}^{*}\parallel}_{\mathrm{\infty}}$  $\le \gamma {\parallel {V}^{(h)}{V}^{*}\parallel}_{\mathrm{\infty}}.$  (40) 
As remarked earlier, ${\mu}_{*}^{(h1)}({s}_{i,h1})$, the mean reward collected at node ${s}_{i,h1}$ for $i\in [{n}_{h1}]$ for any $h\ge 1$, is precisely ${V}^{(Hh+1)}({s}_{i,h1})$ starting with ${V}^{(0)}=\widehat{V}$, the input to MCTS policy. Therefore, the mean reward collected at root node ${s}^{(0)}$ of the MCTS tree satisfies ${\mu}_{*}^{(0)}({s}^{(0)})={V}^{(H)}({s}^{(0)})$. Using (40), we obtain the following Lemma.
Lemma 7
The mean reward collected under the MCTS policy at root note ${s}^{\mathrm{(}\mathrm{0}\mathrm{)}}$, ${\mu}_{\mathrm{*}}^{\mathrm{(}\mathrm{0}\mathrm{)}}\mathit{}\mathrm{(}{s}^{\mathrm{(}\mathrm{0}\mathrm{)}}\mathrm{)}$, starting with input value function proxy $\widehat{V}$ is such that
${\mu}_{*}^{(0)}({s}^{(0)}){V}^{*}({s}^{(0)})$  $\le {\gamma}^{H}{\parallel \widehat{V}{V}^{*}\parallel}_{\mathrm{\infty}}.$  (41) 
In summary, using Lemma 6, we conclude that the recursive relationship going from level $h$ to $h1$ holds for all $h\ge 1$ with level $0$ being the root. At root ${s}^{(0)}$, the query state that is input to the MCTS policy, we have that after $n$ total simulations of MCTS, the empirical average of the rewards over these $n$ trial, $\frac{1}{n}{\stackrel{~}{v}}^{(0)}{({s}_{0})}_{n}$ is such that (using the fact that ${\alpha}^{(0)}={\xi}^{(0)}(1{\eta}^{(0)}){\eta}^{(0)}$)
$\left\mathbb{E}\left[{\displaystyle \frac{1}{n}}{\stackrel{~}{v}}^{(0)}{({s}_{0})}_{n}\right]{\mu}_{*}^{(0)}\right$  $=O\left({n}^{\frac{{\alpha}^{(0)}}{{\xi}^{(0)}(1{\eta}^{(0)})}1}\right)=O\left({n}^{\eta 1}\right),$  (42) 
where ${\mu}_{*}^{(0)}$ is the value function estimation for ${s}^{(0)}$ after $H$ iterations of value function iteration starting with $\widehat{V}$. By Lemma 7, we have
${\mu}_{*}^{(0)}{V}^{*}({s}^{(0)})$  $\le {\gamma}^{H}{\epsilon}_{0},$  (43) 
since ${\epsilon}_{0}={\parallel \widehat{V}{V}^{*}\parallel}_{\mathrm{\infty}}$. Combining (42) and (43),
$\left\mathbb{E}\left[{\displaystyle \frac{1}{n}}{\stackrel{~}{v}}^{(0)}{({s}_{0})}_{n}\right]{V}^{*}({s}^{(0)})\right$  $\le {\gamma}^{H}{\epsilon}_{0}+O\left({n}^{\eta 1}\right).$  (44) 
This concludes the proof of Theorem 1.
The convergence property, ${lim}_{n\to \mathrm{\infty}}\mathbb{E}[{\overline{Z}}_{n}]={\mu}_{X}+\rho {\mu}_{Y}$, follows simply by linearity of expectation. For concentration, consider the following: since $X$s are i.i.d. bounded random variables taking value in $[B,B]$, by Hoeffding’s inequality (Hoeffding 1963), we have that for $t\ge 0$,
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{X}\ge nt)\le \mathrm{exp}({\displaystyle \frac{{t}^{2}n}{2{B}^{2}}}),$  (45)  
$\mathbb{P}(n{\overline{X}}_{n}n{\mu}_{X}\le nt)\le \mathrm{exp}({\displaystyle \frac{{t}^{2}n}{2{B}^{2}}}).$ 
Therefore,
$\mathbb{P}(n{\overline{Z}}_{n}n({\mu}_{X}+\rho {\mu}_{Y})\ge {n}^{\eta}z)$  $\le \mathbb{P}(n{\overline{X}}_{n}n{\mu}_{X}\ge {\displaystyle \frac{{n}^{\eta}z}{2}})+\mathbb{P}(n{\overline{Y}}_{n}n{\mu}_{Y}\ge {\displaystyle \frac{{n}^{\eta}z}{2\rho}})$  
$\le \mathrm{exp}\left({\displaystyle \frac{{z}^{2}{n}^{2\eta 1}}{8{B}^{2}}}\right)+{\displaystyle \frac{\beta {2}^{\xi}{\rho}^{\xi}}{{z}^{\xi}}}$  
$\le {\displaystyle \frac{{\beta}^{\prime}}{{z}^{\xi}}},$  (46) 
where ${\beta}^{\prime}$ is a large enough constant depending upon $\rho ,\xi ,\beta $ and $B$. The otherside of the inequality follows similarly. This completes the proof.
First, we establish a useful property of nearest neighbor supervised learning presented in Section id1. This is stated in Section id1. We will use it, along with the guarantees obtained for MCTS in Theorem 1 to establish Theorem 2 in Section id1. Throughout, we shall assume the setup of Theorem 2.
Let $\delta \in (0,1)$ be given. As stated in Section id1, let $K(\delta ,d)=\mathrm{\Theta}({\delta}^{d})$ be the collection of balls of radius $\delta $, say ${c}_{i},i\in [K(\delta ,d)]$, so that they cover $\mathcal{S}$, i.e. $\mathcal{S}\subset {\cup}_{i\in [K(\epsilon ,d)]}{c}_{i}$. Also, by construction, each of these balls have intersection with $\mathcal{S}$ whose volume is at least ${C}_{d}{\delta}^{d}$. Let $S=\{{s}_{i}:i\in [N]\}$ denote $N$ state samples from $\mathcal{S}$ uniformly at random and independent of each other. For each state $s\in \mathcal{S}$, let $V:\mathcal{S}\to [{V}_{\mathrm{max}},{V}_{\mathrm{max}}]$ be such that $\mathbb{E}[V(s)]{V}^{*}(s)\le \mathrm{\Delta}$. Let the nearest neighbor supervised learning described in Section id1 produce estimate $\widehat{V}:\mathcal{S}\to \mathbb{R}$ using labeled data points ${({s}_{i},V({s}_{i}))}_{i\in [N]}$. Then, we claim the following guarantee. Proof can be found in Section id1.
Lemma 8
Under the above described setup, as long as $N\mathrm{\ge}\mathrm{32}\mathit{}\mathrm{max}\mathit{}\mathrm{(}\mathrm{1}\mathrm{,}{\delta}^{\mathrm{}\mathrm{2}}\mathit{}{V}_{\mathrm{max}}^{\mathrm{2}}\mathrm{)}\mathit{}{C}_{d}^{\mathrm{}\mathrm{1}}\mathit{}{\delta}^{\mathrm{}d}\mathit{}\mathrm{log}\mathit{}\frac{K\mathit{}\mathrm{(}\delta \mathrm{,}d\mathrm{)}}{\delta}$, i.e., $N\mathrm{=}\mathrm{\Omega}\mathit{}\mathrm{(}d\mathit{}{\delta}^{\mathrm{}d\mathrm{}\mathrm{2}}\mathit{}\mathrm{log}\mathit{}{\delta}^{\mathrm{}\mathrm{1}}\mathrm{)}$,
$\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\widehat{V}(s){V}^{*}(s)\right]$  $\le \mathrm{\Delta}+(C+1)\delta +{\displaystyle \frac{4{V}_{\mathrm{max}}{\delta}^{2}}{K(\delta ,d)}}.$  (47) 
Using Theorem 1 and Lemma 8, we complete the proof of Theorem 2 under appropriate choice of algorithmic parameters. We start by setting some notation.
To that end, the algorithm as described in Section id1 iterates between MCTS and supervised learning. In particular, let $\mathrm{\ell}\ge 1$ denote the iteration index. Let ${m}_{\mathrm{\ell}}$ be the number of states that are sampled uniformly at random, independently, over $\mathcal{S}$ in this iteration, denoted as ${S}^{(\mathrm{\ell})}=\{{s}_{i}^{(\mathrm{\ell})}:i\in [{m}_{\mathrm{\ell}}]\}$. Let ${V}^{(\mathrm{\ell}1)}$ be the input of value function from prior iteration, using which the MCTS algorithm with ${n}_{\mathrm{\ell}}$ simulations obtains improved estimates of value function for states in ${S}^{(\mathrm{\ell})}$ denoted as ${\widehat{V}}^{(\mathrm{\ell})}({s}_{i}^{(\mathrm{\ell})}),i\in [{m}_{\mathrm{\ell}}]$. Using ${({s}_{i}^{(\mathrm{\ell})},{\widehat{V}}^{(\mathrm{\ell})}({s}_{i}^{(\mathrm{\ell})}))}_{i\in [{m}_{\mathrm{\ell}}]}$, the nearest neighbor supervised learning as described above with balls of appropriate radius ${\delta}_{\mathrm{\ell}}\in (0,1)$ produces estimate ${V}^{(\mathrm{\ell})}$ for all states in $\mathcal{S}$. Let ${\mathcal{F}}^{(\mathrm{\ell})}$ denote the smallest $\sigma $algebra containing all information pertaining to the algorithm (both MCTS and supervised learning). Define the error under MCTS in iteration $\mathrm{\ell}$ as
${\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}$  $=\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\right\mathbb{E}\left[{\widehat{V}}^{(\mathrm{\ell})}(s)\right{\mathcal{F}}^{(\mathrm{\ell}1)}]{V}^{*}(s)\left\right].$  (48) 
And, the error for supervised learning in iteration $\mathrm{\ell}$ as
${\theta}_{\text{sl}}^{(\mathrm{\ell})}$  $=\underset{s\in \mathcal{S}}{sup}\left{V}^{(\mathrm{\ell})}(s){V}^{*}(s)\right,\text{and}{\epsilon}_{\text{sl}}^{(\mathrm{\ell})}=\mathbb{E}\left[{\theta}_{\text{sl}}^{(\mathrm{\ell})}\right].$  (49) 
Recall that in the beginning, we set ${V}^{(0)}(s)=0$ for all $s\in \mathcal{S}$. Since ${V}^{*}(\cdot )\in [{V}_{\mathrm{max}},{V}_{\mathrm{max}}]$, we have that ${\epsilon}_{\text{sl}}^{(0)}\le {V}_{\mathrm{max}}$. Further, it is easy to see that if the leaf estimates (i.e., the output of the supervised learning from the previous iteration) is bounded in $[{V}_{\mathrm{max}},{V}_{\mathrm{max}}]$, then the output of the MCTS algorithm is always bounded in $[{V}_{\mathrm{max}},{V}_{\mathrm{max}}]$. That is, since ${V}^{(0)}(s)=0$ and the nearest neighbor supervised learning produces estimate ${V}^{(l)}$ via simple averaging, inductively, the output of the MCTS algorithm is always bounded in $[{V}_{\mathrm{max}},{V}_{\mathrm{max}}]$ throughout every iteration.
With the notation as set up above, it follows that for a given ${\delta}_{\mathrm{\ell}}\in (0,1)$ with ${m}_{\mathrm{\ell}}$ satisfying condition of Lemma 8, i.e. ${m}_{\mathrm{\ell}}=\mathrm{\Omega}(d{\delta}_{\mathrm{\ell}}^{d2}\mathrm{log}{\delta}_{\mathrm{\ell}}^{1})$, and with the nearest neighbor supervised learning using ${\delta}_{\mathrm{\ell}}$ radius balls for estimation, we have the following recursion:
${\epsilon}_{\text{sl}}^{(\mathrm{\ell})}$  $\le {\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}+(C+1){\delta}_{\mathrm{\ell}}+{\displaystyle \frac{4{V}_{\mathrm{max}}{\delta}_{\mathrm{\ell}}^{2}}{K({\delta}_{\mathrm{\ell}},d)}}\le {\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}+{C}^{\prime}{\delta}_{\mathrm{\ell}},$  (50) 
where ${C}^{\prime}$ is a large enough constant, since $\frac{{\delta}_{\mathrm{\ell}}^{2}}{K({\delta}_{\mathrm{\ell}},d)}=\mathrm{\Theta}(d{\delta}_{\mathrm{\ell}}^{d+2})$ which is $O({\delta}_{\mathrm{\ell}})$ for all ${\delta}_{\mathrm{\ell}}\in (0,1)$. By Theorem 1, for iteration $\mathrm{\ell}+1$ that uses the output of supervised learning estimate, ${V}^{(\mathrm{\ell})}$, as the input to the MCTS algorithm, we obtain
$\mathbb{E}\left[{\widehat{V}}^{(\mathrm{\ell}+1)}(s)\right{\mathcal{F}}^{(\mathrm{\ell})}]{V}^{*}(s)\le {\gamma}^{{H}^{(\mathrm{\ell}+1)}}\mathbb{E}\left[{\theta}_{\text{sl}}^{(\mathrm{\ell})}\right{\mathcal{F}}^{(\mathrm{\ell})}]+O\left({n}_{\mathrm{\ell}+1}^{\eta 1}\right),\forall s\in \mathcal{S},$  (51) 
where $\eta \in [1/2,1)$ is the constant utilized by MCTS with fixed height of tree being ${H}^{(\mathrm{\ell}+1)}$. This then implies that
${\epsilon}_{\text{mcts}}^{(\mathrm{\ell}+1)}$  $=\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\right\mathbb{E}\left[{\widehat{V}}^{(\mathrm{\ell}+1)}(s)\right{\mathcal{F}}^{(\mathrm{\ell})}]{V}^{*}(s)\left\right]$  
$\le {\gamma}^{{H}^{(\mathrm{\ell}+1)}}\mathbb{E}\left[\mathbb{E}\left[{\theta}_{\text{sl}}^{(\mathrm{\ell})}{\mathcal{F}}^{(\mathrm{\ell})}\right]\right]+O\left({n}_{\mathrm{\ell}+1}^{\eta 1}\right)$  
$\le {\gamma}^{{H}^{(\mathrm{\ell}+1)}}\left({\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}+{C}^{\prime}{\delta}_{\mathrm{\ell}}\right)+O\left({n}_{\mathrm{\ell}+1}^{\eta 1}\right).$  (52) 
Denote by $\lambda \triangleq {(\frac{\epsilon}{{V}_{\mathrm{max}}})}^{1/L}$. Note that since the final desired error $\epsilon $ should be less than ${V}_{\mathrm{max}}$ (otherwise, the problem is trivial by just outputing $0$ as the final estimates for all the states), we have $$. Let us set the algorithmic parameters for MCTS and nearest neighbor supervised learning as follows: for each $\mathrm{\ell}\ge 1$,
${H}^{(\mathrm{\ell})}=\lceil {\mathrm{log}}_{\gamma}{\displaystyle \frac{\lambda}{8}}\rceil ,{\delta}_{\mathrm{\ell}}={\displaystyle \frac{3{V}_{\mathrm{max}}}{4{C}^{\prime}}}{\lambda}^{\mathrm{\ell}},{n}_{\mathrm{\ell}}={\kappa}_{l}{\left({\displaystyle \frac{8}{{V}_{\mathrm{max}}{\lambda}^{\mathrm{\ell}}}}\right)}^{\frac{1}{1\eta}},$  (53) 
where ${\kappa}_{l}>0$ is a sufficiently large constant such that $O\left({n}_{\mathrm{\ell}}^{\eta 1}\right)=\frac{{V}_{\mathrm{max}}}{8}{\lambda}^{\mathrm{\ell}}$. Substituting these values into Eq. (52) yields
$${\epsilon}_{\text{mcts}}^{(\mathrm{\ell}+1)}=\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\right\mathbb{E}[{\widehat{V}}^{(\mathrm{\ell}+1)}(s){\mathcal{F}}^{(\mathrm{\ell})}]{V}^{*}(s)\left\right]\le \frac{\lambda}{8}{\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}+\frac{7{V}_{\mathrm{max}}}{32}{\lambda}^{\mathrm{\ell}+1}.$$ 
Note that by (51) and (53), and the fact that ${\epsilon}_{\text{sl}}^{(0)}\le {V}_{\mathrm{max}}$, we have
$${\epsilon}_{\text{mcts}}^{(1)}\le \frac{\lambda}{8}{\epsilon}_{\text{sl}}^{(0)}+\frac{\lambda}{8}{V}_{\mathrm{max}}\le \frac{\lambda}{4}{V}_{\mathrm{max}}.$$ 
It then follows inductively that
${\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}$  $\le {\lambda}^{\mathrm{\ell}1}{\epsilon}_{\text{mcts}}^{(1)}={\displaystyle \frac{{V}_{\mathrm{max}}}{4}}{\lambda}^{\mathrm{\ell}}.$ 
As for the supervised learning oracle, $\forall s\in \mathcal{S},$ Eq. (50) implies
$\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\left{V}^{(\mathrm{\ell})}(s){V}^{*}(s)\right\right]\le {\epsilon}_{\text{mcts}}^{(\mathrm{\ell})}+{\displaystyle \frac{3{V}_{\mathrm{max}}}{4}}{\lambda}^{\mathrm{\ell}}\le {V}_{\mathrm{max}}{\lambda}^{\mathrm{\ell}}.$ 
This implies that
$\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\left{V}^{(L)}(s){V}^{*}(s)\right\right]\le {V}_{\mathrm{max}}{\lambda}^{L}=\epsilon .$ 
We now calculate the sample complexity, i.e., the total number of state transitions required for the algorithm. During the $\mathrm{\ell}$th iteration, each query of MCTS oracle requires ${n}_{\mathrm{\ell}}$ simulations. Recall that the number of querying MCTS oracle, i.e., the size of training set ${\mathcal{S}}^{(\mathrm{\ell})}$ for the nearest neighbor supervised step, should satisfy ${m}_{\mathrm{\ell}}=\mathrm{\Omega}(d{\delta}_{\mathrm{\ell}}^{d2}\mathrm{log}{\delta}_{\mathrm{\ell}}^{1})$ (cf. Lemma 8). From Eq. (53), we have
$${H}^{(\mathrm{\ell})}={c}_{0}^{\prime}\mathrm{log}{\lambda}^{1},{\delta}^{(\mathrm{\ell})}={c}_{1}{\lambda}^{\mathrm{\ell}},\text{and}\mathit{\hspace{1em}}{n}_{\mathrm{\ell}}={c}_{2}^{\prime}{\lambda}^{\mathrm{\ell}/(1\eta )},$$ 
where ${c}_{0}^{\prime},{c}_{1},{c}_{2}^{\prime},$ are constants independent of $\lambda $ and $\mathrm{\ell}.$ Note that each simulation of MCTS samples ${H}^{(\mathrm{\ell})}$ state transitions. Hence, the number of state transitions at the $\mathrm{\ell}$th iteration is given by
${M}^{(\mathrm{\ell})}$  $={m}_{\mathrm{\ell}}{n}_{\mathrm{\ell}}{H}^{(\mathrm{\ell})}.$ 
Therefore, the total number of state transitions after $L$ iterations is
$\sum _{l=1}^{L}}{M}^{(\mathrm{\ell})$  $={\displaystyle \sum _{\mathrm{\ell}=1}^{L}}{m}_{\mathrm{\ell}}\cdot {n}_{\mathrm{\ell}}\cdot {H}^{(\mathrm{\ell})}=O\left({\epsilon}^{\left(2+1/(1\eta )+d\right)}\cdot {\left(\mathrm{log}{\displaystyle \frac{1}{\epsilon}}\right)}^{5}\right).$ 
That is, for optimal choice of $\eta =1/2$, the total number of state transitions is $O\left({\epsilon}^{(4+d)}\cdot {\left(\mathrm{log}\frac{1}{\epsilon}\right)}^{5}\right).$
Given $N$ samples ${s}_{i},i\in [N]$ that are sampled independently and uniformly at random over $\mathcal{S}$, and given the fact that each ball ${c}_{i},i\in [K(\delta ,d)]$ has at least ${C}_{d}{\delta}^{d}$ volume shared with $\mathcal{S}$, each of the sample falls within a given ball with probability at least ${C}_{d}{\delta}^{d}$. Let ${N}_{i},i\in [K(\delta ,d)]$ denote the number of samples amongst $N$ samples in ball ${c}_{i}$.
Now the number of samples falling in any given ball is lower bounded by a Binomial random variable with parameter $N,{C}_{d}{\delta}^{d}$. By Chernoff bound for Binomial variable with parameter $n,p$, we have that
$\mathbb{P}(B(n,p)\le np/2)$  $\le \mathrm{exp}\left({\displaystyle \frac{np}{8}}\right).$ 
Therefore, with an application of union bound, each ball has at least $0.5{C}_{d}{\delta}^{d}N$ samples with probability at least $1K(\delta ,d)\mathrm{exp}\left({C}_{d}{\delta}^{d}N/8\right)$. That is, for $N=32\mathrm{max}(1,{\delta}^{2}{V}_{\mathrm{max}}^{2}){C}_{d}^{1}{\delta}^{d}[\mathrm{log}(K(\delta ,d)+\mathrm{log}{\delta}^{1}]$, each ball has at least $\mathrm{\Gamma}=16\mathrm{max}(1,{\delta}^{2}{V}_{\mathrm{max}}^{2})(\mathrm{log}K(\delta ,d)+\mathrm{log}{\delta}^{1})$ samples with probability at least $1\frac{{\delta}^{2}}{K(\delta ,d)}$. Define event
${\mathcal{E}}_{1}$  $=\{{N}_{i}\ge 16\mathrm{max}(1,{\delta}^{2}{V}_{\mathrm{max}}^{2})(\mathrm{log}K(\delta ,d)+\mathrm{log}{\delta}^{1}),\forall i\in [K(\delta ,d)]\}.$ 
Then
$\mathbb{P}({\mathcal{E}}_{1}^{c})\le {\displaystyle \frac{{\delta}^{2}}{K(\delta ,d)}}.$ 
Now, for any $s\in \mathcal{S}$, the nearest neighbor supervised learning described in Section id1 produces estimate $\widehat{V}(s)$ equal to the average value of observations for samples falling in ball ${c}_{j(s)}$. Let ${N}_{j(s)}$ denote the number of samples in ball ${c}_{j(s)}.$ To that end,
$\left\widehat{V}(s){V}^{*}(s)\right$  $=\left{\displaystyle \frac{1}{{N}_{j(s)}}}\left({\displaystyle \sum _{i:{s}_{i}\in {c}_{j(s)}}}V({s}_{i}){V}^{*}(s)\right)\right$  
$=\left{\displaystyle \frac{1}{{N}_{j(s)}}}\left({\displaystyle \sum _{i:{s}_{i}\in {c}_{j(s)}}}V({s}_{i})\mathbb{E}[V({s}_{i})]\right)\right+\left{\displaystyle \frac{1}{{N}_{j(s)}}}\left({\displaystyle \sum _{i:{s}_{i}\in {c}_{j(s)}}}\mathbb{E}[V({s}_{i})]{V}^{*}({s}_{i})\right)\right$  
$\mathrm{\hspace{1em}\hspace{1em}}+\left{\displaystyle \frac{1}{{N}_{j(s)}}}\left({\displaystyle \sum _{i:{s}_{i}\in {c}_{j(s)}}}{V}^{*}({s}_{i}){V}^{*}(s)\right)\right.$ 
For the first term, since for each ${s}_{i}\in {c}_{j(s)}$, $V({s}_{i})$ is produced using independent randomness via MCTS, and since the output $V({s}_{i})$ is a bounded random variable, using Hoeffding’s inequality, it follows that
$\mathbb{P}\left(\right{\displaystyle \frac{1}{{N}_{j(s)}}}({\displaystyle \sum _{i:{s}_{i}\in {c}_{j(s)}}}V({s}_{i})\mathbb{E}[V({s}_{i})])\ge {\mathrm{\Delta}}_{1})$  $\le 2\mathrm{exp}\left({\displaystyle \frac{{N}_{j(s)}{\mathrm{\Delta}}_{1}^{2}}{8{V}_{\mathrm{max}}^{2}}}\right).$ 
The second term is no more than $\mathrm{\Delta}$ due to the guarantee given by MCTS as assumed in the setup. And finally, the third term is no more than $C\delta $ due to Lipschitzness of ${V}^{*}$. To summarize, with probability at least $12\mathrm{exp}\left(\frac{{N}_{j(s)}{\mathrm{\Delta}}_{1}^{2}}{8{V}_{\mathrm{max}}^{2}}\right)$, we have that
$\left\widehat{V}(s){V}^{*}(s)\right$  $\le {\mathrm{\Delta}}_{1}+\mathrm{\Delta}+C\delta .$ 
As can be noticed, the algorithm produces the same estimate for all $s\in \mathcal{S}$ such that they map to the same ball. And there are $K(\delta ,d)$ such balls. Therefore, using union bound, it follows that with probability at least $12K(\delta ,d)\mathrm{exp}\left(\frac{({\mathrm{min}}_{i\in [K(\delta ,d)]}{N}_{i}){\mathrm{\Delta}}_{1}^{2}}{8{V}_{\mathrm{max}}^{2}}\right)$,
$\underset{s\in \mathcal{S}}{sup}\left\widehat{V}(s){V}^{*}(s)\right$  $\le {\mathrm{\Delta}}_{1}+\mathrm{\Delta}+C\delta .$ 
Under event ${\mathcal{E}}_{1}$, ${\mathrm{min}}_{i\in [K(\delta ,d)]}{N}_{i}\ge 16\mathrm{max}(1,{\delta}^{2}{V}_{\mathrm{max}}^{2})(\mathrm{log}K(\delta ,d)+\mathrm{log}{\delta}^{1})$. Therefore, under event ${\mathcal{E}}_{1}$, by choosing ${\mathrm{\Delta}}_{1}=\delta $, we have
$\underset{s\in \mathcal{S}}{sup}\left\widehat{V}(s){V}^{*}(s)\right$  $\le \mathrm{\Delta}+(C+1)\delta ,$ 
with probability at least $1\frac{2{\delta}^{2}}{K(\delta ,d)}$. When event ${\mathcal{E}}_{1}$ does not hold or the above does not hold, we have trivial error bound of $2{V}_{\mathrm{max}}$ on the error. Therefore, we conclude that
$\mathbb{E}\left[\underset{s\in \mathcal{S}}{sup}\left\widehat{V}(s){V}^{*}(s)\right\right]$  $\le \mathrm{\Delta}+(C+1)\delta +{\displaystyle \frac{4{V}_{\mathrm{max}}{\delta}^{2}}{K(\delta ,d)}}.$ 
In this paper, we introduce a correction of the popular Monte Carlo Tree Search (MCTS) policy for improved value function estimation for a given state, using an existing value function estimation for the entire state space. This correction was obtained through careful, rigorous analysis of a nonstationary MultiArm Bandit where rewards are dependent and nonstationary. In particular, we analyzed a variant of the classical Upper Confidence Bound policy for such an MAB. Using this as a building block, we establish rigorous performance guarantees for the corrected version of MCTS proposed in this work. This, to the best of our knowledge, is the first mathematically correct analysis of the UCT policy despite its popularity since it has been proposed in literature (Kocsis and Szepesvári 2006, Kocsis et al. 2006). We further establish that the proposed MCTS policy, when combined with nearest neighbor supervised learning, leads to near optimal sample complexity for obtaining estimation of value function within a given tolerance, where the optimality is in the minimax sense. This suggests the tightness of our analysis as well as the utility of the MCTS policy.
We take a note that much of this work was inspired by the success of AlphaGo Zero (AGZ) which utilizes MCTS combined with supervised learning. Interestingly enough, the correction of MCTS suggested by our analysis is qualitatively similar to the version of MCTS utilized by AGZ as reported in practice. This seeming coincidence may suggest further avenue for practical utility of versions of the MCTS proposed in this work and is an interesting direction for future work.
References
 Agrawal (1995) Agrawal R (1995) Sample mean based index policies by o (log n) regret for the multiarmed bandit problem. Advances in Applied Probability 27(4):1054–1078.
 Audibert et al. (2009) Audibert JY, Munos R, Szepesvári C (2009) Exploration–exploitation tradeoff using variance estimates in multiarmed bandits. Theoretical Computer Science 410(19):1876–1902.
 Auer et al. (2002) Auer P, CesaBianchi N, Fischer P (2002) Finitetime analysis of the multiarmed bandit problem. Machine learning 47(23):235–256.
 Azizzadenesheli et al. (2018) Azizzadenesheli K, Yang B, Liu W, Brunskill E, Lipton ZC, Anandkumar A (2018) Sampleefficient deep RL with generative adversarial tree search. CoRR abs/1806.05780.
 Bartlett et al. (2019) Bartlett P, Gabillon V, Healey J, Valko M (2019) Scalefree adaptive planning for deterministic dynamics & discounted rewards. International Conference on Machine Learning, 495–504.
 Bertsekas (1975) Bertsekas D (1975) Convergence of discretization procedures in dynamic programming. IEEE Transactions on Automatic Control 20(3):415–419.
 Bertsekas (2017) Bertsekas D (2017) Dynamic Programming and Optimal Control (Athena Scientific).
 Browne et al. (2012) Browne CB, Powley E, Whitehouse D, Lucas SM, Cowling PI, Rohlfshagen P, Tavener S, Perez D, Samothrakis S, Colton S (2012) A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4(1):1–43.
 Chang et al. (2005) Chang HS, Fu MC, Hu J, Marcus SI (2005) An adaptive sampling algorithm for solving markov decision processes. Operations Research 53(1):126–139.
 Coquelin and Munos (2007) Coquelin PA, Munos R (2007) Bandit algorithms for tree search. arXiv preprint cs/0703062 .
 Coulom (2006) Coulom R (2006) Efficient selectivity and backup operators in montecarlo tree search. International conference on computers and games, 72–83 (Springer).
 Dufour and PrietoRumeau (2012) Dufour F, PrietoRumeau T (2012) Approximation of Markov decision processes with general state space. Journal of Mathematical Analysis and applications 388(2):1254–1267.
 Dufour and PrietoRumeau (2013) Dufour F, PrietoRumeau T (2013) Finite linear programming approximations of constrained discounted Markov decision processes. SIAM Journal on Control and Optimization 51(2):1298–1324.
 Efroni et al. (2018) Efroni Y, Dalal G, Scherrer B, Mannor S (2018) Multiplestep greedy policies in approximate and online reinforcement learning. Advances in Neural Information Processing Systems, 5244–5253.
 EvenDar and Mansour (2004) EvenDar E, Mansour Y (2004) Learning rates for Qlearning. JMLR 5.
 Guo et al. (2014) Guo X, Singh S, Lee H, Lewis RL, Wang X (2014) Deep learning for realtime atari game play using offline montecarlo tree search planning. Advances in neural information processing systems, 3338–3346.
 Hoeffding (1963) Hoeffding W (1963) Probability inequalities for sums of bounded random variables. Journal of Americal Statistics Association 58.
 Hren and Munos (2008) Hren JF, Munos R (2008) Optimistic planning of deterministic systems. European Workshop on Reinforcement Learning, 151–164 (Springer).
 Jiang et al. (2018) Jiang DR, Ekwedike E, Liu H (2018) Feedbackbased tree search for reinforcement learning. International conference on machine learning.
 Kaufmann and Koolen (2017) Kaufmann E, Koolen WM (2017) Montecarlo tree search by best arm identification. Advances in Neural Information Processing Systems, 4897–4906.
 Kearns et al. (2002) Kearns M, Mansour Y, Ng AY (2002) A sparse sampling algorithm for nearoptimal planning in large markov decision processes. Machine learning 49(23):193–208.
 Kocsis and Szepesvári (2006) Kocsis L, Szepesvári C (2006) Bandit based montecarlo planning. European conference on machine learning, 282–293 (Springer).
 Kocsis et al. (2006) Kocsis L, Szepesvári C, Willemson J (2006) Improved montecarlo search. Univ. Tartu, Estonia, Tech. Rep .
 Mnih et al. (2016) Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K (2016) Asynchronous methods for deep reinforcement learning. International conference on machine learning, 1928–1937.
 Mnih et al. (2013) Mnih V, Kavukcuoglu K, Silver D, Graves A, Antonoglou I, Wierstra D, Riedmiller M (2013) Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 .
 Mnih et al. (2015) Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, et al. (2015) Humanlevel control through deep reinforcement learning. Nature 518(7540):529.
 Munos et al. (2014) Munos R, et al. (2014) From bandits to montecarlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends® in Machine Learning 7(1):1–129.
 Salomon and Audibert (2011) Salomon A, Audibert JY (2011) Deviations of stochastic bandit regret. International Conference on Algorithmic Learning Theory, 159–173 (Springer).
 Schadd et al. (2008) Schadd MPD, Winands MHM, van den Herik HJ, Chaslot GMJB, Uiterwijk JWHM (2008) Singleplayer montecarlo tree search. van den Herik HJ, Xu X, Ma Z, Winands MHM, eds., Computers and Games, 1–12 (Berlin, Heidelberg: Springer Berlin Heidelberg).
 Schulman et al. (2015) Schulman J, Levine S, Abbeel P, Jordan M, Moritz P (2015) Trust region policy optimization. International Conference on Machine Learning, 1889–1897.
 Schulman et al. (2017) Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 .
 Shah and Xie (2018) Shah D, Xie Q (2018) Qlearning with nearest neighbors. Bengio S, Wallach H, Larochelle H, Grauman K, CesaBianchi N, Garnett R, eds., Advances in Neural Information Processing Systems 31, 3115–3125 (Curran Associates, Inc.).
 Silver et al. (2016) Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, Antonoglou I, Panneershelvam V, Lanctot M, et al. (2016) Mastering the game of go with deep neural networks and tree search. nature 529(7587):484–489.
 Silver et al. (2017a) Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, Lanctot M, Sifre L, Kumaran D, Graepel T, et al. (2017a) Mastering chess and shogi by selfplay with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815 .
 Silver et al. (2017b) Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, Baker L, Lai M, Bolton A, et al. (2017b) Mastering the game of go without human knowledge. Nature 550(7676):354.
 Stone (1982) Stone CJ (1982) Optimal global rates of convergence for nonparametric regression. The Annals of Statistics 1040–1053.
 Strehl et al. (2006) Strehl AL, Li L, Wiewiora E, Langford J, Littman ML (2006) Pac modelfree reinforcement learning. Proceedings of the 23rd international conference on Machine learning, 881–888 (ACM).
 Sturtevant (2008) Sturtevant NR (2008) An analysis of uct in multiplayer games. van den Herik HJ, Xu X, Ma Z, Winands MHM, eds., Computers and Games, 37–49 (Berlin, Heidelberg: Springer Berlin Heidelberg).
 Sutton (1988) Sutton RS (1988) Learning to predict by the methods of temporal differences. Machine learning 3(1):9–44.
 Szepesvári (2019) Szepesvári C (2019) Personal communication.
 Teraoka et al. (2014) Teraoka K, Hatano K, Takimoto E (2014) Efficient sampling method for monte carlo tree search problem. IEICE TRANSACTIONS on Information and Systems 97(3):392–398.
 Tsybakov (2009) Tsybakov AB (2009) Introduction to Nonparametric Estimation. Springer Series in Statistics (Springer).
 Van Hasselt et al. (2016) Van Hasselt H, Guez A, Silver D (2016) Deep reinforcement learning with double qlearning. AAAI, volume 2, 5 (Phoenix, AZ).
 Watkins and Dayan (1992) Watkins CJ, Dayan P (1992) Qlearning. Machine learning 8(34):279–292.
 Yang et al. (2019) Yang Y, Zhang G, Xu Z, Katabi D (2019) Harnessing structures for valuebased planning and reinforcement learning. arXiv preprint arXiv:1909.12255 .
The recent work Shah and Xie (2018) establishes a lower bound on the sample complexity for reinforcement learning algorithms on MDPs. We follow a similar argument to establish a lower bound on the sample complexity for MDPs with deterministic transitions. We provide the proof for completeness. The key idea is to connect the problem of estimating the value function to the problem of nonparametric regression, and then leveraging known minimax lower bound for the latter. In particular, we show that a class of nonparametric regression problem can be embedded in an MDP with deterministic transitions, so any algorithm for the latter can be used to solve the former. Prior work on nonparametric regression (Tsybakov 2009, Stone 1982) establishes that a certain number of observations is necessary to achieve a given accuracy using any algorithms, hence leading to a corresponding necessary condition for the sample size of estimating the value function in an MDP problem. We now provide the details.
Step 1. Nonparametric regression. Consider the following nonparametric regression problem: Let $\mathcal{S}:={[0,1]}^{d}$ and assume that we have $T$ data pairs $({x}_{1},{y}_{1}),\mathrm{\dots},({x}_{T},{y}_{T})$ such that conditioned on ${x}_{1},\mathrm{\dots},{x}_{n},$ the random variables ${y}_{1},\mathrm{\dots},{y}_{n}$ are independent and satisfy
$$\mathbb{E}\left[{y}_{t}{x}_{t}\right]=f({x}_{t}),{x}_{t}\in \mathcal{S}$$  (54) 
where $f:\mathcal{S}\to \mathbb{R}$ is the unknown regression function. Suppose that the conditional distribution of ${y}_{t}$ given ${x}_{t}=x$ is a Bernoulli distribution with mean $f(x)$. We also assume that $f$ is $1$Lipschitz continuous with respect to the Euclidean norm, i.e.,
$$f(x)f({x}_{0})\le x{x}_{0},\forall x,{x}_{0}\in \mathcal{S}.$$ 
Let $\mathcal{F}$ be the collection of all $1$Lipschitz continuous function on $\mathcal{X}$, i.e.,
$$\mathcal{F}=\{hh\text{is a 1Lipschitz function on}\mathcal{S}\},$$ 
The goal is to estimate $f$ given the observations $({x}_{1},{y}_{1}),\mathrm{\dots},({x}_{T},{y}_{T})$ and the prior knowledge that $f\in \mathcal{F}$.
It is easy to verify that the above problem is a special case of the nonparametric regression problem considered in the work by Stone (1982) (in particular, Example 2 therein). Let ${\widehat{f}}_{T}$ denote an arbitrary (measurable) estimator of $f$ based on the training samples $({x}_{1},{y}_{1}),\mathrm{\dots},({x}_{T},{y}_{T})$. By Theorem 1 in Stone (1982), we have the following result: there exists a $c>0$ such that
$\underset{T\to \mathrm{\infty}}{lim}\underset{{\widehat{f}}_{T}}{inf}\underset{f\in \mathcal{F}}{sup}\mathbb{P}(\parallel {\widehat{f}}_{T}f{\parallel}_{\mathrm{\infty}}\ge c{\left({\displaystyle \frac{\mathrm{log}T}{T}}\right)}^{\frac{1}{2+d}})=1,$  (55) 
where infimum is over all possible estimators ${\widehat{f}}_{T}$. Translating this result to the nonasymptotic regime, we obtain the following theorem.
Theorem 4
Under the above stated assumptions, for any number $\delta \mathrm{\in}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$, there exits $c\mathrm{>}\mathrm{0}$ and ${T}_{\delta}$ such that
$$\underset{{\widehat{f}}_{T}}{inf}\underset{f\in \mathcal{F}}{sup}\mathbb{P}(\parallel {\widehat{f}}_{T}f{\parallel}_{\mathrm{\infty}}\ge c{\left(\frac{\mathrm{log}T}{T}\right)}^{\frac{1}{2+d}})\ge \delta ,\mathit{\text{for all}}T\ge {T}_{\delta}.$$ 
Step 2. MDP with deterministic transitions. Consider a class of discretetime discounted MDPs $(\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma )$, where
$\mathcal{S}={[0,1]}^{d},$  
$\mathcal{A}\text{is finite},$  
$\text{for each}(x,a),\text{there exists a unique}{x}^{\prime}\in \mathcal{S}\text{such that}\mathcal{P}({x}^{\prime}x,a)=1,$  
$r(x,a)=r(x)\text{for all}a,$  
$\gamma =0.$ 
In words, the transition is deterministic, the expected reward is independent of the action taken and the current state, and only immediate reward matters.
Let ${R}_{t}$ be the observed reward at step $t$. We assume that given ${x}_{t},$ the random variable ${R}_{t}$ is independent of $({x}_{1},\mathrm{\dots},{x}_{t1})$, and follows a Bernoulli distribution $\text{Bernoulli}\left(r({x}_{t})\right).$ The expected reward function $r(\cdot )$ is assumed to be $1$Lipschitz and bounded. It is easy to see that for all $x\in \mathcal{S}$, $a\in \mathcal{A}$,
${V}^{*}(x)$  $=r(x).$  (56) 
Step 3. Reduction from regression to MDP. Given a nonparametric regression problem as described in Step $1$, we may reduce it to the problem of estimating the value function ${V}^{*}$ of the MDP described in Step $2$. To do this, we set
$r(x)$  $=f(x),\forall x\in \mathcal{S}$ 
and
${R}_{t}$  $={y}_{t},t=1,2,\mathrm{\dots},T.$ 
In this case, it follows from equations (56) that the value function is given by ${V}^{*}=f$. Moreover, the expected reward function $r(\cdot )$ is $1$Lipschitz, so the assumptions of the MDP in Step $2$ are satisfied. This reduction shows that the MDP problem is at least as hard as the nonparametric regression problem, so a lower bound for the latter is also a lower bound for the former.
Applying Theorem 4 yields the following result: for any number $\delta \in (0,1)$, there exist some numbers $c>0$ and ${T}_{\delta}>0$, such that
$$\underset{{\widehat{V}}_{T}}{inf}\underset{{V}^{*}\in \mathcal{F}}{sup}\mathbb{P}[\parallel {\widehat{V}}_{T}{V}^{*}{\parallel}_{\mathrm{\infty}}\ge c{\left(\frac{\mathrm{log}T}{T}\right)}^{\frac{1}{2+d}}]\ge \delta ,\text{for all}T\ge {T}_{\delta}.$$ 
Consequently, for any reinforcement learning algorithm ${\widehat{V}}_{T}$ and any sufficiently small $\epsilon >0$, there exists an MDP problem with deterministic transitions such that in order to achieve
$$ 
one must have
$$T\ge {C}^{\prime}d{\left(\frac{1}{\epsilon}\right)}^{2+d}\mathrm{log}\left(\frac{1}{\epsilon}\right),$$ 
where ${C}^{\prime}>0$ is a constant. The statement of Proposition 1 follows by selecting $\delta =\frac{1}{2}$.