Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search

Tuan Dam

cs.LGSep 6, 2026

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search

Authors: Tuan Dam

Organizations: Hanoi University of Science and Technology, Hanoi, Vietnam.

Abstract

Monte Carlo Tree Search (MCTS) has demonstrated success in online planning for deterministic environments, yet significant challenges remain in adapting it to stochastic Markov Decision Processes (MDPs), particularly in continuous state-action spaces. Existing methods, such as HOOT, which combines MCTS with the Hierarchical Optimistic Optimization (HOO) bandit strategy, address continuous spaces but rely on a logarithmic exploration bonus that lacks theoretical guarantees in non-stationary, stochastic settings. Recent advancements, such as POLY-HOOT, introduced a polynomial bonus term to achieve convergence in deterministic MDPs, though a similar theory for stochastic MDPs remains undeveloped. In this paper, we propose a novel MCTS algorithm, \Algname, designed for continuous, stochastic MDPs. \Algname integrates a power mean as a value backup operator, alongside a polynomial exploration bonus to address the non-stationarity inherent in continuous action spaces. Our theoretical analysis establishes that \Algname converges at a polynomial rate of $\mathcal{O}(n^{-ζ})$ , $ζ\in (0,1/2)$ , where $n$ is the number of visited trajectories, thereby extending the non-asymptotic convergence guarantees of POLY-HOOT to stochastic environments. Experimental results on stochastic tasks validate our theoretical findings, demonstrating the effectiveness of \Algname in continuous, stochastic domains.

Figures & tables

Conditions on the parameters $b_{d},\alpha_{d},\beta_{d},p$ (all must hold):
1. $b_{d}<\alpha_{d}$ and $b_{d}>2$ .
2. Either $\bigl(1\leq p\leq 2\;\;\text{and}\;\;\alpha_{d}\leq\tfrac{\beta_{d}}{2}\bigr)$ or $\bigl(p>2,\;\alpha_{d}\leq\tfrac{\beta_{d}}{2},\;\text{and}\;0<\alpha_{d}-\tfrac{\beta_{d}}{p}<1\bigr)$ .
3. $\alpha_{d}\Bigl(1-\tfrac{b_{d}}{\alpha_{d}}\Bigr)\;\leq\;b_{d}\;<\;\alpha_{d}.$
4. $\displaystyle\alpha_{d}\;=\;\frac{\,1-\tfrac{b_{d+1}}{\alpha_{d+1}}\,}{\,1+d^{\prime}+\tfrac{\beta_{d+1}}{\alpha_{d+1}}\,}\;\times\;\frac{\,b_{d+1}-3\,}{2}.$
5. $\beta_{d}\;=\;\bigl(b_{d+1}-1\bigr).$

Table 1: Summary of constraints on the algorithmic constants for

d\in\{0,1,\dots,D\}.

(

d^{\prime}

is a constant that is bigger than

d

)

	CartPole	CartPole-IG	Pendulum	MountainCar	Acrobot
Discretized-UCT	$77.85\pm 0.00$	$37.95\pm 1.60$	$1263.68\pm 37.66$	$-0.020\pm 0.004$	$70.14\pm 32.29$
PW	$77.85\pm 0.00$	$68.46\pm 6.87$	$1141.51\pm 80.93$	$-0.020\pm 0.002$	$77.85\pm 0.00$
HOOT	$77.85\pm 0.00$	$38.51\pm 0.81$	$1043.23\pm 70.79$	$-0.007\pm 0.001$	$70.05\pm 37.05$
POLY-HOOT(p=1)	$77.85\pm 0.00$	$77.85\pm 0.00$	$1205.886\pm 110.01$	$-0.055\pm 0.002$	$77.85\pm 0.00$
Stochastic-Power-HOOT	$\mathbf{77.85\pm 0.00}$	$\mathbf{77.85\pm 0.00}$	$\mathbf{1397.40\pm 95.42}$	$\mathbf{27.285\pm 0.163}$	$\mathbf{77.85\pm 0.00}$

Table 2: Performance on stochastic classic control tasks. Each environment features continuous actions and multiple noise sources. Stochastic-Power-HOOT uses

p=2

. Bold indicates best performance.

Algorithm	Humanoid-v0	Hopper-v0
	(17D action, 376D state)	(3D action)
UCT (baseline)	$-136.98\pm 44.84$	$5216.93\pm 179.64$
POLY-HOOT ( $p=1$ )	$-44.40\pm 3.33$ (3.1×)	$13230.66\pm 2844.33$ (2.5×)
HOOT	$-57.35\pm 10.46$ (2.4×)	$10452.83\pm 3885.12$ (2.0×)
PW	$-89.74\pm 24.16$ (1.5×)	$5218.73\pm 1384.90$ (1.0×)
Voronoi MCTS	$-48.69\pm 9.52$ (2.8×)	$411.70\pm 29.03$ (12.7× worse)

Table 3: Performance on high-dimensional stochastic MuJoCo environments. All environments include action, dynamics, and observation noise. Performance multipliers relative to UCT baseline shown in parentheses. Bold indicates best performance per environment.

Power $p$	1	2	3	4	5	6	7	8	9	10
Reward	76.91	77.85	76.80	77.77	76.81	75.85	75.75	76.74	75.82	75.89

Table 4: Power parameter sensitivity analysis on CartPole-IG. Values

p=2

and

p=4

achieve optimal performance.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Notation	Type	Description
$K$	$\mathbb{N}$	Number of arms
$T_{a}(t)$	$\mathbb{N}$	Number of visitations at arm $a$ after $t$ timesteps
$f^{*}_{h,i}$	$\mathbb{R}$	mean value of arm $a$
$a^{\star}$	$\mathcal{A}$	optimal action
$f^{\star}$	$\mathbb{R}$	mean value of an optimal arm. We assume it is unique.
$\widehat{f}_{n}(p)$	$\mathbb{R}$	power mean estimator, with a constant $p\in[1,+\infty)$

Appendix

Table 5: List of all notations for Non-stationary Multi-arms bandit.

Explore similar work

Finite-Time Analysis of MCTS in Continuous POMDP Planning
May 8, 2026Da Kong, Vadim IndelmanMonte Carlo Tree Search Partially Observable Markov Decision Processes
Technion Autonomous Systems Program (TASP) · Technion – Israel Institute of Technology · Stephen B. Klein Faculty of Aerospace Engineering +1
Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation
Sep 17, 2026Tung Tran, Viet Bao Mai, Hoang Ta +1Markov Decision Processes Monte Carlo Tree Search
School of ICT Hanoi University of Science and Technology Hanoi, Vietnam
Online Robust Reinforcement Learning Through Monte-Carlo Planning
Sep 16, 2026Tuan Dam, Kishan Panaganti, Brahim Driss +1Monte Carlo Tree Search Distributionally Robust RL
Hanoi University of Science and Technology, Hanoi, Vietnam · Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL

May 8, 2026J/K move · Enter open · S save

Finite-Time Analysis of MCTS in Continuous POMDP Planning

Da Kong, Vadim Indelman

Technion Autonomous Systems Program (TASP) · Technion – Israel Institute of Technology · Stephen B. Klein Faculty of Aerospace Engineering+1

Monte Carlo Tree Search Partially Observable Markov Decision Processes UCB Algorithms

Open paper AskPDF arXiv

This paper presents a finite-time analysis for Monte Carlo Tree Search (MCTS) in Partially Observable Markov Decision Processes (POMDPs), with probabilistic concentration bounds in both discrete and continuous observation spaces. While MCTS-style solvers such as POMCP achieve empirical success in many applications, rigorous finite-time guarantees remain an open problem due to the nonstationarity and the interdependencies induced by heuristic action selection (e.g., UCB). In the discrete setting, we address these challenges by extending the polynomial exploration bonus to UCB in POMDP setting, yielding polynomial concentration bounds for the empirical value estimation at the root node. For continuous observation spaces, we introduce an abstract partitioning framework and propose a finite-time bound on partitioning loss. Under mild conditions, we prove highprobability bound on value estimates in POMDPs with continuous observation space. Specifically, we propose Voro-POMCPOW, a variant of POMCPOW with f inite-time guarantees that adaptively partitions the continuous observation space using Voronoi cells. This approach maintains a finite branching factor while preserving the original observation generator. Empirical validation demonstrates that the proposed Voro-POMCPOW shows competitive performance while providing theoretical guarantees. Although our analysis focuses on continuous POMDPs, the techniques developed herein are also applicable to continuous MDPs, closing another gap on the MDP side.

Abstract

Explore similar work

Finite-Time Analysis of MCTS in Continuous POMDP Planning

Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

Online Robust Reinforcement Learning Through Monte-Carlo Planning