  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.
