Monte-Carlo Tree Search (MCTS) is a widely-used strategy for online planning
that combines Monte-Carlo sampling with forward tree search. Its success relies
on the Upper Confidence bound for Trees (UCT) algorithm, an extension of the
UCB method for multi-arm bandits. However, the theoretical foundation of UCT is
incomplete due to an error in the logarithmic bonus term for action selection,
leading to the development of Fixed-Depth-MCTS with a polynomial exploration
bonus to balance exploration and exploitation~\citep{shah2022journal}. Both UCT
and Fixed-Depth-MCTS suffer from biased value estimation: the weighted sum
underestimates the optimal value, while the maximum valuation overestimates
it~\citep{coulom2006efficient}. The power mean estimator offers a balanced
solution, lying between the average and maximum values.
Power-UCT~\citep{dam2019generalized} incorporates this estimator for more
accurate value estimates but its theoretical analysis remains incomplete. This
paper introduces Stochastic-Power-UCT, an MCTS algorithm using the power mean
estimator and tailored for stochastic MDPs. We analyze its polynomial
convergence in estimating root node values and show that it shares the same
convergence rate of $\mathcal{O}(n^{-1/2})$, with $n$ is the number of visited
trajectories, as Fixed-Depth-MCTS, with the latter being a special case of the
former. Our theoretical results are validated with empirical tests across
various stochastic MDP environments.

通过引入随机 功值平 均估计器的随机功 - UCT 算法，实现在随 机马尔可夫 决策过程中更准确的价值估计，研究其多项式收 敛性和与 Fixed-Depth-MCTS 相同的收 敛速率。