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 相同的收 敛速率。

随机蒙特卡洛树搜索中的功率均值估计

Power Mean Estimation in Stochastic Monte-Carlo Tree_Search

The design of neural network architectures for a new data set is a laborious
task which requires human deep learning expertise. In order to make deep
learning available for a broader audience, automated methods for finding a
neural network architecture are vital. Recently proposed methods can already
achieve human expert level performances. However, these methods have run times
of months or even years of GPU computing time, ignoring hardware constraints as
faced by many researchers and companies. We propose the use of Monte Carlo
planning in combination with two different UCT (upper confidence bound applied
to trees) derivations to search for network architectures. We adapt the UCT
algorithm to the needs of network architecture search by proposing two ways of
sharing information between different branches of the search tree. In an
empirical study we are able to demonstrate that this method is able to find
competitive networks for MNIST, SVHN and CIFAR-10 in just a single GPU day.
Extending the search time to five GPU days, we are able to outperform human
architectures and our competitors which consider the same types of layers.

本论文提出了使用蒙特卡罗规划结合两种不同的 UCT（基于树的上限置信度）推导来搜索网络架构，并在一天内找到了 MNIST、SVHN 和 CIFAR-10 的一个具有竞争力的网络，将搜索时间扩展到五天，能够超越人类架构及其同类层次的竞争者。