{'fraction_non_alphanumeric': 0.04750858520388438, 'fraction_numerical': 0.011075481567396694, 'mean_word_length': 4.223568543597054, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Optimal Computing Budget Allocation Tree Policy for Monte Carlo Tree Search

We analyze a tree search problem with an underlying Markov decision process, in which the goal is to identify the best action at the root that achieves the highest cumulative reward. We present a new tree policy that optimally allocates a limited computing budget to maximize a lower bound on the probability of correctly selecting the best action at each node. Compared to widely used Upper Confidence Bound (UCB) tree policies, the new tree policy presents a more balanced approach to manage the exploration and exploitation trade-off when the sampling budget is limited. Furthermore, UCB assumes that the support of reward distribution is known, whereas our algorithm relaxes this assumption. Numerical experiments demonstrate the efficiency of our algorithm in selecting the best action at the root.


I. INTRODUCTION
We consider a reinforcement learning problem where an agent interacts with an underlying environment. A Markov Decision Process (MDP) with finite horizon is used to model the environment. In each move, the agent will take an action, receive a reward and land in a new state. The reward is usually random, and its distribution depends on both the state of the agent and the action taken. The distribution of the next state is also determined by the agent's current state and action. Our goal is to determine the optimal sequence of actions that leads to the highest expected reward. The optimality of the decision policy will be evaluated by the probability of correctly selecting the best action in the first stage of the underlying MDP.
If the distributions and the dynamics of the environment are known, the optimal set of actions can be computed through dynamic programming [2]. Under more general settings where the agent does not have perfect information regarding the environment, [3] proposed an adaptive algorithm based on  [4]. [5] and [6] applied UCB to tree search, and [6] invented the term Monte Carlo Tree Search (MCTS) and used it in a Go-playing program for the first time. Since then, MCTS has been developed extensively and applied to various games such as Othello [7] and Go [8]. To deal with different types of problems, several variations of MCTS have been introduced, e.g., Flat UCB (and its extension Bandit Algorithm for Smooth Trees) [9] and Single-Player MCTS (for single-player games) [10].
However, most bandit-based MCTS algorithms are designed to minimize regret (or maximize the cumulative reward of the agent), whereas in many situations, the goal of the agent may be to efficiently determine the optimal set of actions within a limited sampling budget. To the best of our knowledge, there is limited effort in the literature that aims at addressing the latter problem. [11] first incorporated Best Arm Identification (BAI) into MCTS for a MIN-MAX game tree, and provided upper bounds of play-outs under different settings. [12] had an objective similar to [11], but with a tighter bound. Their tree selection policy selects the node with largest confidence interval, which can be seen as choosing the node with the highest variance. In some sense, this is a pure exploration policy and would not efficiently use the limited sampling budget. In our work, we are motivated to establish a tree policy that intelligently balances exploration and exploitation (analogous to the objective of UCB). The algorithms developed in [11] and [12] are only for MIN-MAX game trees, whereas our new tree policy can be applied to more general types of tree search problems. The MCTS algorithm in [13] is more general than [11] and [12], but its goal is to estimate the maximum expected cumulative reward at the root node, whereas we focus on identifying the optimal action.
Algorithms that focus on minimizing regret tend to discourage exploration. This tendency can be seen in two ways. Suppose at some point an action was performed and received a small reward. To minimize regret, the algorithm would be discouraged from taking this action again. However, the small reward could be due to the randomness in the reward distribution. Mathematically, [14] showed that for MAB algorithms, the number of times the optimal action is taken is exponentially more than sub-optimal ones, which makes sense when the objective is to maximize the cumulative reward, since the exploration of other actions is highly discouraged. This leads to our second motivation: is there a tree policy that explores sub-optimal actions more to ensure the optimal action is found?
Apart from the lack of exploration as a result of the underlying MAB model's objective to minimize regret or arXiv:2009.12407v1 [eess.SY] 25 Sep 2020 maximize cumulative reward, most MCTS algorithms assume that the support of the reward distribution is bounded and known (typically assumed to be [0, 1]). With the support of reward distribution being known, the parameter in the upper confidence term in UCB is tuned or the reward is normalized. However, a general tree search problem may likely have an unknown and practically unbounded range of rewards. In such case, assuming a range can lead to very poor performance. Therefore, the third motivation of our research is to relax the known reward support assumption.
To tackle the challenge in balancing exploration and exploitation with a limited sampling budget for a tree policy, we model the tree selection problem at each stage as a statistical Ranking & Selection (R&S) problem and propose a new tree policy for MCTS based on an adaptive algorithm from the R&S community. Similar to the MAB problem, R&S assumes that we are given a set of bandit machines (often referred to as alternatives in the R&S literature) with unknown reward distributions, and the goal is to select the machine with the highest mean reward. Specifically, we will develop an MCTS tree policy based on the Optimal Computing Budget Allocation (OCBA) framework [15]. OCBA was first proposed in [16], and aims at maximizing the probability of correctly selecting the action with highest mean reward using limited sampling budget. More recent developments of OCBA include addressing multiple objectives [17] and subset selection [18], [19].
The objective of the proposed OCBA tree policy is to maximize the Approximate Probability of Correct Selection (APCS), which is a lower bound on the probability of correctly selecting the optimal action at each node. Intuitively, the objective function of the new OCBA tree selection policy would lead to an optimal balance between exploration and exploitation with a limited sampling budget, and thus help address the drawbacks of existing work that either pursues pure exploration [11], [12] or exponentially discourages exploration [14]. Our new OCBA tree policy also removes the known and bounded support assumption for the reward distribution, because the new OCBA policy determines the sampling allocation based on the posterior distribution of each action, which is updated adaptively according to samples.
To summarize, contributions of this paper include the following: 1) We propose a new tree policy for MCTS with an objective to maximize APCS with a limited sampling budget. The new tree policy optimally balances exploration and exploitation to efficiently select the optimal action. The new OCBA tree selection policy also relaxes the assumption of known bounded support on the reward distribution. 2) We present a sequential algorithm to implement the new OCBA tree policy that maximizes the APCS at each sampling stage and prove that our algorithm converges to the optimal action. 3) We provide theoretical analyses, such as convergence guarantee, proof of optimality of the proposed algorithm, and the exploration-exploitation trade-off of the proposed algorithm, which works differently than bandit-based algorithms, and is more suitable for identifying the best action. 4) We demonstrate the efficiency of our algorithm through numerical experiments.

Remark 1.
In much of the computer science/artificial intelligence literature, an algorithm that focuses on determining the optimal set of actions under a limited budget is defined as a pure exploration algorithm (see, e.g., [20], [21], [22]), whereas we view such algorithms as retaining a balance between exploration and exploitation, as the analysis in Section III shows. In statistical R&S, pure exploration algorithms generally implies sampling based primarily on the variance of each action, which often leads to sampling suboptimal actions more. It will be clearer in the Section V where we show that OCBA-MCTS actually samples less those highly suboptimal actions and "exploits" those potential actions more.
The rest of the paper is organized as follows. We present the problem formulation in Section II, and review the proposed OCBA-MCTS algorithm in Section III. Theoretical analyses, including convergence theorems and exploration-exploitation analysis, are carried out in Section IV. Proofs are given in the Appendix. Numerical examples are presented in Section V to evaluate the performance of our algorithm. Section VI concludes the paper and points to future research directions.
A preliminary version of this work was presented in [1], where a simpler tree policy (not employing the node representation adopted in the current work) was used. In addition to improving the efficiency of the MCTS algorithm, here we prove that our proposed algorithm converges asymptotically to the optimal action, and provide an exploration-exploitation trade-off analysis, both analytically and through a more comprehensive set of numerical experiments.

II. PROBLEM FORMULATION
Consider a finite horizon MDP M = (X, A, P, R) with horizon length H, finite state space X, finite action space A with |A| > 1, bounded reward function R = {R t ,t = 0, 1, . . . H} such that R t maps a state-action pair to a random variable (r.v.), and transition function P = {P t ,t = 0, 1, . . . H} such that P t maps a state-action pair to a probability distribution over X. We assume that P t is unknown and/or |X| and |A| are very large, and hence it is not feasible to solve the problem by dynamic programming. Further define X a and A x as the available child states when taking action a and available actions at state x, respectively. Denote by P t (x, a)(y) the probability of transitioning to state y ∈ X a from state x ∈ X when taking action a ∈ A x in stage t, and R t (x, a) the reward in stage t by taking action a in state x. Let Π be the set of all possible nonstationary Markovian policies π = {π i |π i : X → A, i ≥ 0}.
Bandit-based algorithms for MDPs seek to minimize the expected cumulative regret, whereas our objective is to identify the best action that leads to maximum total expected reward given by E ∑ H−1 t=0 R t (x t , π t (x t )) for given x 0 ∈ X. We first define the optimal reward-to-go value function for state x in stage i by with Q H (x, a) = 0. It is well known [2] that eq. (1) can be written via the standard Bellman optimality equation: where Y ∼ P i (x, a)(·) represents the random next state.
Since we are considering a tree search problem, some additional notation and definitions beyond MDP settings are needed. Define a state node by a tuple that contains the state and the stage number: where X is the set of state nodes. Similarly, we define a stateaction node by a tuple of state, stage number and action (i.e., a state node followed by an action): Now, we can rewrite the immediate reward function, value function for state, state-action pair with state node and stateaction node and state transition distribution, respectively, by Similarly, V * (x) and Q(x, a) are assumed to be zero for all terminal state nodes x. To make our presentation clearer, we adopt the following definitions based on nodes: define N(x) and N(x, a) the number of visits to node x and (x, a), respectively, X a the set of child state nodes given parent nodes, and A x the set of available child actions at node x, respectively.
Traditionally, MCTS algorithms aim at estimating V * (x) and model the selection process in each stage as an MAB problem, i.e., view Q(x, a) as a set of bandit machines where (x, a) are child state-action nodes of x ([3], [5]), and minimize the regret, namely, for x in stage 1, 2, . . . H, where N and a k are the number of rollouts/simulations (also known as total sampling budget in much of Ranking & Selection literature) and the k-th action sampled at state node x by the tree policy, respectively. The meaning of rollout will be clearer in Section III. In this paper, our goal is to identify the optimal action that achieves the highest cumulative reward at the root with initial state x, that is, find where the root state node x 0 = (x, 0). LetQ(x, a) = R(x, a) + V * (y) be the random cumulative reward by taking action a at state node x, where y is the random state node reached. Clearly,Q(x, a) is a random variable. We assumeQ(x, a) is normally distributed with known variance, and its mean µ(x, a) has a conjugate normal prior with a mean equals Q(x, a).
Hence we have Remark 2. For our derivations, we assume the variance of the sampling distribution ofQ(x, a) is known; however, in practice, the prior variance may be unknown, in which case estimates such as the sample variance are used [23].
Consider the non-informative case, i.e., the prior mean Q(x, a) is unknown, it can be shown that [24] the posterior of µ(x, a) given observations (i.e., samples) is also normal. For convenience, define the t-th sample byQ t (x, a). Then the conditional distribution of µ(x, a) given the set of samples (Q 1 (x, a),Q 2 (x, a), . . . ,Q N(x,a) (x, a)) is wherē Q(x, a) = µ(x, a)|(Q 1 (x, a),Q 2 (x, a), . . . ,Q N(x,a) (x, a)), and σ 2 (x, a) is the variance ofQ(x, a) and can be approximated by the sample variance: Remark 3. If the samples of Q(x, a) are not normally distributed, the normal assumption can be justified by batch sampling and the central limit theorem.
Under these settings, our objective is to maximize the Probability of Correct Selection (PCS) defined by for a state node x, whereâ * x is the action that achieves the highest mean sample Q-value at such node, i.e.,â * x = arg max a∈A xQ (x, a).
PCS is hard to compute because of the intersections in the (joint) probability. We seek to simplify the joint probability by changing the intersections to sums using the Bonferroni inequality to make the problem tractable. By the Bonferroni inequality, PCS is lower bounded by the Approximate Probability of Correct Selection (APCS), that is, The objective of our new tree policy is to maximize APCS as given in Equation (4). Compared to MAB's objective of minimizing the expected cumulative regret, this objective function will result in an allocation of sampling budget to alternative actions in a way that optimally balances exploration and exploitation. This objective function is motivated by the OCBA algorithm [15] in the R&S literature. We will present and analyze our OCBA tree policy in the following sections.

III. ALGORITHM DESCRIPTION
In this section, we first briefly describe the main four phases, i.e., selection, expansion, simulation and backpropagation, in an MCTS algorithm. Then, we propose a novel tree policy in the selection stage that aims at finding the optimal action at each state node.

A. Canonical MCTS algorithm
Here we briefly summarize the four phases in a typical MCTS algorithm. We refer readers to [25] for a complete illustration of these phases. Algorithm 1 represents a canonical MCTS, with detailed descriptions of the main phases below.
1) Selection: In this phase, the algorithm will navigate down the tree from the root state node to an expandable node, i.e., a node with unvisited child nodes. We assume that expansion is automatically followed when a state-action is encountered. Therefore, when determining the path down, there are three possible situations: (i) If a state-action node is encountered (denoted by (x, a)), we will land into a new state node y which is obtained by calling the expansion function. Then, we continue with the selection algorithm. (ii) If an expandable state node (which could be a leaf node) is encountered, we call the expansion function to add a new child state-action node and a state node (by automatically expanding the state-action node) to the path. Then, we stop the selection phase and return the path from the root to this state node. Finally, we proceed with the simulation and backpropagation phase (iii) If an unexpandable state node is encountered (denoted by x), we employ a tree policy to determine which child action to sample. Then we enter the new state-action node (x, a) and continue the selection algorithm with this stateaction node. The tree policies can be briefly categorized into two types: deterministic, such as UCB1 and several of its variants (e.g., UCB-tuned, UCB-E), and stochastic, such as ε-greedy and EXP3; see [25] for a review.
2) Expansion: In this phase, a random child state or stateaction node of the given node is added. If the incoming node is a state node x, the next node is selected randomly (usually uniform) from those unvisited child state-action nodes. If the incoming node is a state-action node (x, a), the subsequent state node is found by simply sampling from distribution P(x, a)(·).
3) Simulation: In some literature, this phase is also known as "rollout". The simulation phase starts with a state node. The purpose of this step is to simulate a path from this node to a terminal node and produce a sample of cumulative reward by taking this path (which is a sample of the value for this node). The simulated path is taken by a default policy, which is usually sample the feasible child sate-action nodes uniformly. With this node's value sample, we may proceed to the backpropagation phase.

4) Backpropagation:
This phase simply takes the simulated node value and update the values of the nodes in the path (obtained in selection step) backward.
In the next section, we will propose our tree policy based on OCBA and illustrate the detailed implementations of the four phases.

B. OCBA selection algorithm
We now present an efficient tree policy to estimate the optimal actions in every state node by estimating V * (x) and Q(x, a) for all possible a ∈ A x at the state node. Denote the estimates of V * (x) at node x byV * (x), which is initialized to 0 for all state nodes. Our algorithm estimates Q(x, a) for each action a by its sample mean, and selects the action that maximizes the sample mean asâ * x . During the process, the estimate of Q(x, a) is given by Equation (2) and the proposed new OCBA tree policy is applied. Our algorithm follows the algorithmic framework described in Section III-A, with the tree policy changed to OCBA and other mild modifications.
The structure of the proposed OCBA-MCTS algorithm is shown in Algorithms 1 to 6. There are two major characteristics: the first is to use the proposed OCBA algorithm for the tree policy. The second is to require each state-action node to be expanded n 0 > 1 times, because we need a sample variance for each state-action node, which will become clearer after the tree policy illustration. The process is run for a prespecified N times (which will be later referred to as number of rollouts or sampling budget) from the root state node x 0 , after which a partially expanded tree is obtained and the optimal actionâ * x 0 can be derived.
When steering down the tree and a state node x is visited, the selection phase, which is illustrated in Algorithm 2, will first determine if there is a child state-action node that was visited for less than n 0 times at the given state node. If there is, then the state-action node will be sampled and added to the path. In other words, we try to expand each state node when it is visited, and require each node to be expanded n 0 times. If all the state-action nodes are well-expanded, Algorithm 2 will call Algorithm 3 (OCBASelection), which calculates the allocation of samples to child state-action nodes of the current state node for a total sampling budget ∑ a∈A N(x, a) + 1. To determine the number of samples allocated to each state-action node, denoted by (Ñ(x, a 1 ),Ñ(x, a 2 ), . . . ,Ñ(x, a |A x | )) (where a i ∈ A x , i = 1, . . . , |A x |), the OCBA tree policy first identifies the child state-action node with the largest sample mean (sample optimal) and finds the difference between the sample means of the sample optimum and all other nodes: a 2 ), . . . ,Ñ(x, a |A| )) that maximizes APCS can be obtained by solving the following set of equations: The derivations of Equations (5) to (7) are illustrated in the appendix.
After the new budget allocation is computed, the algorithm will select the "most starving" action to sample [23], i.e., sampleâ We highlight some major modifications to the canonical MCTS in the proposed algorithm. First, in the selection phase, we will try to expand all "expandable" nodes visited when obtaining a path to leaf. Since the variances of the values of a state node's child nodes are required in the proposed tree policy, we define a state node as expandable if it has child nodes that are visited less than n 0 > 1 times. State-action nodes are always expandable.
At the expansion phase as shown in Algorithm 4, a stateaction node is expanded by simply sampling the transition distribution P(x, a)(·), and the resulting state node is subsequently added to the path. The reward by taking the action in the state node is also recorded and will be used in the backpropagation stage.
In the simulation and backpropagation phases illustrated in Algorithm 5 and 6, a leaf-to-terminal path is simulated, and its reward is used to update the value for the leaf node. If we denote the leaf node and the reward from the simulated path by x l and r, respectively, the leaf node value estimate is updated byV After updating the leaf state node, we update the nodes in the path collected in selection stage in reversed order. Suppose we have a path and the node values of x i+1 , . . . , x l have been updated, the preceding nodes x i and (x i , a i ) are updated througĥ whereV (·) is an intermediate variable that records the average value of the node through the root-to-leaf path, and α N(x i ) ∈ [0, 1] is a smoothing parameter. The updates are performed backwards to the root node. Details of the OCBA tree policy are shown in Algorithm 1 to 6.
There are a few points worth emphasizing in Algorithm 3. First,Ñ(x, a i ) is the total number of samples for each action i after the allocation. Given present information, i.e., all samples state node x, OCBA-MCTS assumes now a total number of ∑ a∈A N(x, a) + 1 samples available. By solving Equations (5) to (7), the new budget allocation (Ñ(x, a 1 ),Ñ(x, a 2 ), . . . ,Ñ(x, a |A| )) that maximizes APCS is calculated. Afterwards, one action based on Equation (8) is selected to sample and move to the next stage. This "moststarving" implementation of the OCBA policy as given in Algorithm 3 is fully sequential, as each iteration allocates only one sample to an action before the allocation decision is recomputed. It is also possible to allocate the sampling budget in a batch of size ∆ > 1. We use the "most-starving" scheme, because it has been shown to be more efficient than the batch sampling scheme [26]. However, the benefit of sampling in batches for MCTS is that in one iteration, multiple root-toleaf paths can be examined, enabling parallelization of the algorithm. We will consider this in future research.
Second, updatingV (x i ) involves two stages: updating the value estimate along the path (Equation (12)) and taking the maximum over the values of the child state-action nodes (canonical way to update). Then the two values are mixed through α N(x i ) to updateV (x i ), as prior research (e.g., [27], Input: root state node x 0 Sample a root-to-leaf path. Append state-action node (x,â) and leaf state node y to path a 2 ), . . . ,Ñ(x, a |A| )) by solving Equations (5) to (7) a ← arg max a∈A (Ñ(x, a) − N(x, a)) returnâ Algorithm 4: expand(x or (x, a)) Input: a state node x or a state-action node (x, a) Output: child node to be added to the tree if the input node is a state node x then S ← {feasible actions of state x that has been sampled less than n 0 times} a ← random choice of S Add (x,â) to the tree if it is unvisited returnâ else Sample node (x, a) at state node x and obtain the child state node y ∼ P(x, a)(·) Add y to the tree if it is unvisited return y. end Algorithm 5: simulate(x) Input: state node x r ← 0 while True do if x is not terminal then find a random child state-action node (x, a) of x r ← r + R(x, a) sample a and obtain the child state node y ∼ P(x, a)(·) x ← y else return r end end Algorithm 6: backpropagate(path, reward) Input: path to a leaf node path, simulated reward reward for node in reversed(path) do Update node values through Equations (9) to (13). end [6]) suggests mixing with α N(x i ) → 1 (i.e., asymptotically achieves Bellman update) ensures more stable updates.
Finally, although we present our algorithm in the context of solving an MDP, it can be applied to other tree structures such as MIN-MAX game trees or more general game trees, by setting the reward function and the max and min operators accordingly.

IV. ANALYSIS OF OCBA-MCTS
In this section, we first analyze how the OCBA tree policy in OCBA-MCTS balances exploration and exploitation mathematically. Then, we present several theoretical results regarding OCBA-MCTS. The proofs are given in the appendix.

A. Exploration-exploitation balance
Equations (5) to (7) determine the new sampling budget allocation. First, Eq. (5) shows that the sub-optimal stateaction nodes should be sampled proportional to their variances and inversely proportional to the squared differences between their sample means and that of the optimal state-action node. This represents a different type of trade off between exploration (sampling actions with high variances) and exploitation (sampling actions with higher sample means) compared to bandit-based algorithms.

B. Convergence analysis
In this part, we present three theorems regarding OCBA-MCTS. The first theorem ensures the estimate of the value-togo function converges to the true value. The second theorem proves that OCBA-MCTS will select the correct action, i.e., the PCS converges to 1. The last theorem guarantees that the APCS, which is a lower bound of PCS, is maximized by solving Equations (5) and (6) in each step. It is shown that at each point of the tree policy when a decision needs to be made, the action that maximizes the APCS will be selected and sampled. Therefore, the OCBA tree policy gradually maximizes the overall APCS at the root, which is a lower bound for PCS.
Theorem 1 (Asymptotic consistency). Assume the expected cumulative reward at state-action node (x, a) is a normal random variable with mean µ(x, a) and variance σ 2 (x, a) < ∞, i.e.,Q(x, a) ∼ N(µ(x, a), σ 2 (x, a)) for 0 ≤ i < H. Further assume µ(x, a) is also normally distributed with unknown mean and known variance. Suppose the proposed OCBA-MCTS algorithm is run with a sampling budget N at root state node x 0 . Then at any subsequent nodes x, Theorem 2 (Asymptotic correctness). Under the same assumptions of Theorem 1, the PCS converges to 1 for any state node x ∈ X, i.e., whereâ * x = arg max a∈A xQ (x, a). Theorem 3. Under the same assumptions of Theorem 1, the APCS defined in Equation (4) is maximized asymptotically with simulation budget allocation (Ñ(x, a 1 ),Ñ(x, a 2 ), . . . ,Ñ(x, a |A| )) by solving Equations (5) and (6) with total budget N, i.e., ∑ a∈A xÑ (x, a) = N.
Theorem 3, which follows from the result originally derived in [15], shows that at each point of the algorithm when a decision needs to be made, the action that maximizes the APCS will be selected and sampled. Therefore, the OCBA tree policy gradually maximizes the overall APCS at the root, which is a lower bound for PCS.

C. Performance lower bound
We take advantage of the normal distribution assumptions on the Q functions and provide a lower bound on PCS.
Theorem 4 (Lower bound on the probability of correct selection). Under the same assumptions of Theorem 1, the PCS at each stage and state is lower bounded by where Φ(·) is the cdf of standard normal distribution and .

V. NUMERICAL EXAMPLES
In this section, we evaluate our proposed OCBA-MCTS on two tree search problems against the well-known UCT [5]. The effectiveness is measured by PCS, which is estimated by the fraction of times the algorithm chooses the true optimal action. We first evaluate our algorithm on an inventory control problem with random non-normal reward. Then we apply our algorithm to the game of tic-tac-toe.
For convenience, we restate the UCT tree policy here. At a state node x, the UCT policy will select the child state-action node with the highest upper confidence bound, i.e., where w e is the "exploration weight". The original UCT algorithm assumes the value function in each stage is bounded in [0, 1] because it sets w e = 1, whereas the support is unknown in many practical problems. Therefore, in general, w e needs to be tuned to encourage exploration.
For all experiments, we set the smoothing parameter in Equation (13) in the backpropagation phase to α N(x) = 1 − 1 5N(x) . Since initial estimates of sample variance can be less accurate with small n 0 , we add an initial variance σ 2 0 > 0, which decays as the number of visits grows, to the sample variance to encourage exploration. Specifically, we set where the first term is the sample variance, and second term vanishes as N(x, a) grows.

A. Inventory control problem
We now evaluate the performance of OCBA-MCTS using the inventory control problem in [3]. The objective is to find the initial order quantity that minimizes the total cost over a finite horizon. At decision period i, we denote by D i the random demand in period i, x i = (x i , i) the state node, where x i is the inventory level at the end of period i (which is also the inventory at the beginning of period i + 1), (x i , a i ) the corresponding child state-action node with a i being the order amount in period i, p the per period per unit demand lost penalty cost, h the per period per unit inventory holding cost, K the fixed (set-up) cost per order, M the maximum inventory level (storage capacity) and H the number of simulation stages. We set M = 20, initial state x 0 = 5, h = 1, H = 3, D i ∼ DU(0, 9) (discrete uniform, inclusive), and consider two different settings for p and K: 1) Experiment 1: p = 10 and K = 0; 2) Experiment 2: p = 1 and K = 5. The reward function, which in this case is the negative of the inventory cost in stage i, is defined by where 1 is the indicator function, and the state transition follows For UCT, to accommodate the reward support not being [0, 1], we adjust the exploration weight when updating a state-action node, i.e., set w e initially to 1, then in the backpropagation step, update w e by w e = max(w e , |Q N(x,a) (x, a)|), whereQ N(x,a) (x, a) is obtained in Equation (10). The initial variance σ 2 0 is set to 100. For both OCBA-MCTS and UCT, we set the number of expansions (n 0 ) to 4 for depth 1 stateaction nodes (i.e., the child nodes of the root) and to 2 for all other state action nodes in Experiment 1, and set n 0 to 2 for all nodes in Experiment 2. The different values of n 0 are due to the variance decreasing with the depth of a node, and Experiment 2 is a relatively easier problem.
For both experiment settings, each algorithm is repeated 1, 000 times at each simulation budget level N to estimate PCS. Since Experiment 1 is a much harder problem compared to Experiment 2, more rollouts (budget) are required. Therefore, N ranges from 10, 000 to 20, 000 and from 50 to 170 for Experiments 1 and 2, respectively.
The estimated PCS curves for both experiments are illustrated in Figure 1, where the standard error (= PCS(1 − PCS)/N) is small and thus omitted for clarity. OCBA-MCTS achieves better PCS for both experiment setups. For Experiment 1 (optimal action a * 0 = 4), as shown in Figure 1a, OCBA-MCTS achieves a 10% higher PCS (absolute) compared to UCT. For Experiment 2 (optimal action a * 0 = 0), we see a 20% performance gap between UCT and OCBA-MCTS when the number of samples is less than 100, after which UCT gradually closes the gap as expected.
It is also beneficial to compare the distribution of budget allocation of OCBA-MCTS and UCT to show the explorationexploitation balance of OCBA-MCTS. For convenience, we label the child actions of the root node from 0 to 15, where action i denotes ordering i units. Figures 2 and 3 illustrate the average number of visits, average estimated value function, and average estimated standard deviation of all child stateaction nodes of the root node over 1,000 repeated runs with 20,000 and 170 rollouts for Experiment 1 and Experiment 2, respectively. Note that although the estimated standard deviation does not play a role in determining the allocation for UCT, we still plot it for reference. Both figures show that the number of visits to children nodes is, to some extent, proportional to the estimated value of the node for UCT. On the other hand, OCBA-MCTS puts more effort on the estimated optimal and second optimal actions (actions 4 and 3 for Experiment 1 and actions 0 and 1 for Experiment 2, respectively), as illustrated in Figures 2b and 3b.
In Experiment 1 where there are two competing actions with similar estimated values (actions 3 and 4, with action 4 being the optimal), OCBA-MCTS will spend most of its sampling budget on those two potential actions and put much lesser effort on clearly inferior actions, such as actions 6 to 14, compared to UCT. This strategy makes more sense when the objective is to identify the best action, and thus is more suitable for MCTS problems, as the ultimate goal is to make a decision. It is also interesting to note that OCBA-MCTS actually allocates slightly more visits to the competing suboptimal action than the optimal one (mean 8486 and 8468 for actions 3 and 4, respectively), which will not happen in bandit-based policies, as their goal is to minimize regret, and thus will put more effort on exploiting the estimated optimal action. In Experiment 2 where the optimum is slightly easier to find, although OCBA-MCTS allocates a larger fraction of samples to suboptimal actions compared to that in Experiment 1, most of the samples are still allocated to the top 2 actions as shown in Figure 3b, whereas UCT performs similar to that in Experiment 1.

B. Tic-tac-toe
In this section, we apply OCBA-MCTS and UCT to the game of tic-tac-toe to identify the optimal move. Tic-tac-toe is a game for two players who take turns marking 'X' (Player 1) and 'O' (Player 2) on a 3 × 3 board. The objective for Player 1 (Player 2) is to mark 3 consecutive 'X' ('O') in a row, column or diagonal. If both players act optimally, the game will always end in a draw.
For ease of presentation, we number the spaces sequentially as shown in Figure 4a. We use OCBA-MCTS and UCT to represent Player 2, with Player 1 marked 'X' on space 0 as shown in Figure 4b. In this situation, the optimal move for Player 2 will be marking space 4 (shown in Figure 4c), as taking any other space will end up in losing the game if Player 1 plays optimally. In this game, Player 2 (MCTS algorithm) makes decisions at even stages (0, 2, 4, . . . ) and Player 1 makes decisions at odd stages (1, 3, . . . ). The state transitioning is deterministic and Player 1's move is modeled using a randomized policy. We consider two different policies for Player 1: 1) Experiment 3: Player 1 plays randomly, i.e., with equal probability to mark any feasible space; 2) Experiment 4: Player 1 plays UCT.
We compare the performance of OCBA-MCTS and UCT on Player 2 in both experiments. At state node x, the reward function for taking action a is defined according to the following rules: immediately after taking the action, if Player 2 wins the game, R(x, a) = 1, if it leads to a draw, R(x, a) = 0.5; otherwise (Player 2 loses or in any non-terminating state), R(x, a) = 0. n 0 is set to 2 across all nodes for both UCT and OCBA-MCTS. Since the value function for all state-action nodes is now bounded in [0, 1], we set w e = 1 throughout the entire experiment for UCT policies. The initial variance σ 2 0 is set to 10. For Experiment 4 where Player 1 plays UCT, its goal is to minimize the reward, therefore, Player 1 will select the action that minimizes the lower confidence bound, i.e., a = arg min Similar to the previous section, we plot the PCS of the two algorithms as a function of the number of rollouts, which ranges from 300 to 700 for both experiments and the PCS is estimated over 2000 independent experiments at each rollout level. The results are shown in Figure 5, which indicates that the proposed OCBA-MCTS produces a more accurate estimate of the optimal action compared to UCT. Both experiments  show that OCBA-MCTS is better at finding the optimal move when the sampling budget is relatively low. The performance of UCT and OCBA-MCTS become comparable when more samples become available. We also note that there is a greater performance gap between UCT and OCBA-MCTS in Experiment 3 than in Experiment 4: in Experiment 3, OCBA-MCTS achieves 10% better PCS, whereas in Experiment 4, the difference is around 5% when N < 500 and soon catches up as N increases. This is expected, as it becomes easier to determine the optimal action when the opponent applies an AI algorithm (i.e., Player 1 has a better chance to take its optimal action). In this case, space 4 becomes a clear optimum and therefore Player 2's UCT algorithm tends to exploit it more, which leads to better performance. The sampling distributions for OCBA-MCTS and UCT with N = 700 for both experiments are shown in Figures 6 and 7. In this game, since a relatively clear optimum is available, OCBA-MCTS and UCT behaved differently compared to that in the inventory control problem. As shown in Figures 6a and  7a, UCT spends most of the sampling budget exploiting this action, whereas OCBA will still try to explore other suboptimal actions due to its tendency to better balance exploration and exploitation. In summary, the proposed OCBA-MCTS outperforms UCT in both experiments in finding the optimal action at the root. Since the objective of the proposed OCBA tree policy is to maximize PCS, it leads to different budget allocation and better PCS.

VI. CONCLUSION AND FUTURE RESEARCH
In this paper, we present a new OCBA tree policy for MCTS. Unlike bandit-based tree policies (e.g., UCT), the new policy maximizes PCS at the root node, and in doing so, balances the exploration and exploitation trade-off differently. Furthermore, the new OCBA tree policy relaxes the assumption of known bounded support on the reward distribution, and thus makes MCTS more generally applicable.
For future research, we intend to explore the use of a batch sampling scheme in Algorithm 2, which allocates a batch of ∆ > 1 samples at each node. With batch sampling and updating, we may exploit the power of parallel computing to more quickly identify the optimal action. Furthermore, the proposed OCBA-MCTS algorithm aims at selecting only the optimal action at the root. It may be of interest to show that our algorithm is ε − δ -correct and establish an upper bound on the sample complexity.

APPENDIX A CONVERGENCE ANALYSIS
To prove that our algorithm correctly selects the optimal action as the sampling budget goes to infinity, we first prove that at each stage, the PCS converges to 1. The process of our algorithm at each single stage is OCBA adapted from [15]. OCBA tries to identify the alternative with highest mean from a set of normal random variables (alternatives) with means J i and known variances σ 2 i , i = 1, 2, . . . , k by efficiently allocating samples that maximizes APCS. OCBA assumes that J i is also normally distributed. Here we present OCBA again in Algorithm 7 for convenience. The budget allocation process is similar to Equations (5) to (7). First definē where l i is the number of samples for alternative i,Ĵ m i is the m-th sample of J i for 1 ≤ i ≤ k, 1 ≤ m ≤ l i . The new allocations (l 1 ,l 2 , . . . ,l k ) with budget T > ∑ i l i can be obtained by solving the set of equations: where σ i is the standard deviation of the i−th reward distribution. As in Remark 2, σ i is assumed to be known, but in practice can be unknown and approximated by sample standard Proof. The PCS can be lower bounded by APCS, i.e., by the Bonferroni inequality Thus, to prove that PCS → 1, it suffices to prove APCS → 1, i.e., Based on the normality assumption, the posterior distribution is also normal, i.e., (18) where Φ is the cdf of the standard normal distribution. Since then when T → ∞, at least one of the actions will be sampled infinitely many times, i.e., there exists an index i such that l i → ∞. Then there are two possible cases: i = b and i = b. Case 1: i = b According to eq. (15), Since σ i and δ (b, i) are bounded for all i, l j → ∞, ∀ j = b. Therefore, by eq. (16), l b → ∞. Thus, l i → ∞ for all i = 1, 2, . . . , k. Case 2: i = b According to (16), Thus there exists an index i = b such that l i → ∞. By a similar argument in Case 1, we can conclude that l i → ∞ for all i = 1, 2, . . . , k.
In either case, we have l i → ∞ for all i = 1, 2, . . . , k. Additionally, sinceJ b is defined to be the maximum of allJ i , i.e., A corollary follows directly from the lemma.
Corollary 5. Suppose one-stage OCBA is run with budget T . ThenJ The proof is a simple application of the strong law of large numbers, since l b → ∞. With this key lemma, we are ready to prove the first two theorems proposed in Section IV. We start with Theorem 1.
Proof of Theorem 1. The result can be proved by induction.
First observe that since N → ∞, each path is explored infinitely many times. Thus the number of samples in each stage also goes to infinity as N → ∞.
Suppose at some point of the algorithm, all nodes are expanded. If the current state node x is at stage H − 1 (i.e., it will transit into a terminal node in the next transition), running Algorithm 3 reduces to a single-stage problem, which is the same as OCBA in Algorithm 7.Q(x, a) can be viewed as a set of alternatives for a ∈ A. From Corollary 5, it is straightforward that lim N→∞Q (x, a) = Q(x, a).
Therefore, since the reward function is bounded Now suppose that the statement is true for all child state nodes y of a state x, i.e.,V (y) → V * (y) and y could be achieved from x. Then for x, the algorithm also reduces to OCBA. Thus from Corollary 5 again for all child state-action pair (x, a). It follows that Theorem 2 is a direct result of Lemma 1.
Proof of Theorem 2. Since we assumeQ(x, a) is normally distributed with known variance, the posterior distribution of Q(x, a), i.e.,Q(x, a), is also a normal random variable. Then, it follows directly from Lemma 1 that APPENDIX B ALLOCATION STRATEGY Proof of Theorem 3. The problem of maximizing APCS with budget constraint can be formulated as With Lagrange multiplier λ , the Lagrangian can be written as Apply Karush-Kuhn-Tucker (KKT) conditions [28]: • stationarity . .

APPENDIX C PERFORMANCE BOUND ANALYSIS
Proof of Theorem 4. When the number of samples at node x is large, we assume that N(x, a) satisfies Equations (5) to (6).
In this way, we can express the budget allocation to any suboptimal actionã as the product of the budget allocation to a particular suboptimal action a and the factor r x (ã, a) = σ (x,ã)δ x (â * x , a) σ (x, a)δ x (â * x ,ã) 2 .
Apply inequality ∑ n i=1 c 2 i ≤ ∑ n i=1 c 2 i = ∑ n i=1 c i for positive numbers c i 's yields σ (x,ã) .
Since APCS is decreasing in σ 2 x (a,â * x ), we have