Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search
Authors: Tuan Quang Dam
Venue: ICML 2025 poster (2025)
Keywords: Monte-Carlo Tree Search; Continuous Reinforcement Learning Planning
Primary area: reinforcement_learning->planning
TL;DR: We develop a theoretically-guaranteed planning algorithm that enables making optimal continuous decisions in unpredictable environments, outperforming existing methods on robotic control tasks.

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, Stochastic-Power-HOOT, designed for continuous, stochastic MDPs. Stochastic-Power-HOOT 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 Stochastic-Power-HOOT converges at a polynomial rate of $\mathcal{O}(n^{-\zeta})$, $\zeta \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 Stochastic-Power-HOOT in continuous, stochastic domains.

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Tuan Dam
Abstract
1. Introduction
Monte Carlo Tree Search (MCTS) has become corner- stone of modern decision-making and planning, yielding unprecedented successes in deterministic domains such as Go, Chess, and Shogi (Kocsis et al., 2006, Browne et al.) 2012). However, real-world applications often involve con- timoous actions and stochastic dynamics factors that sig- nificantly complicate both the theoretical convergence and practical performance of MCTS. Traditional methods typ- ically assume discrete action sets with near-stationary re- wards, making them ill-suited for continuous, noisy envi- ronments where value estimates shift over time and enu- merating possible actions is infeasible. This gap has con- strained MCTS's s applicability narrow set of problems, limiting its promise in roboties, control, and other high- dimensional tasks.
Monte Carlo Tree Search (MCTS) has demon- strated success online planning for determin- istic environments, yet significant challenges remain in adapting it to stochastic Markov Decision Processes (MDPs), particularly in con- tinuous state-action spaces. Existing methods, such as HOOT, which combines MCTS with the Hierarchical Optimistic Optimization (HOO) bandit strategy, address continuous spaces but rely logarithmic exploration bonus that lacks theoretical guarantees in non-stationary, stochastic settings. Recent advancements, such as POLY-HOOT, introduced a polyno- mial bonus term to achieve convergence in deterministic MDPs, though a similar theory for stochastic MDPs remains undeveloped. In this paper, we propose novel MCTS algorithm,
Existing efforts to adapt MCTS to continuous settings in- clude HOOT (Mansley et al. 2011), which couples MCTS with a hierarchical bandit (HOO). Yet, HOOT relies on log- arithmic exploration bonuses that fail to guarantee conver- gence when state-action values are non-stationary. POLY- HOOT (Mao al., 2020) subsequently introduced poly- nomial bonus terms and established strong results in de- terministic continuous MDPs. Unfortunately, no analo- gous guarantee exists for stochastic environments, a critical shortcoming for many real-world domains where transition and reward uncertainties are prevalent.
Stochast.c--Power-Bte designed for continuous, stochastic MDPs. integrates a power mean as a value backup operator, along- side a polynomial exploration bonus to address the non-stationarity inherent in continuous action spaces. Our theoretical analysis establishes that converges polynomial rate of O(n ç E (0, where is the number of visited trajecto- ries, thereby extending the non-asymptotic convergence guarantees of POLY-HOOT to stochastic environments. Experimental results stochastic tasks validate our theoretical findings, demonstrating the effectiveness of Crochastic-Powe--e in continuous, stochastic domains.
Stochastic-Power-Eee
In this paper, we bridge that gap by proposing stochastic-Pover-Be
novel MCTS algo- rithm designed for continuous and stochastic MDPs. -occhastt--Powe---OOOe uses power mean as its value backup operator, combining it with polynomial ex- ploration bonus to rigorously handle non-stationary value estimates across the tree. This design extends theoret- ical guarantees of POLY-HOOT beyond deterministic en- vironments, ensuring that Stochast Poo-ooeer--- HOOT converges at polynomial rate in the presence of stochas- tic transitions. Moreover, our approach avoids naive action- space discretization by focusing search adaptively where it matters most.
'Hanoi University of Science and Technol- ogy, Hanoi, Vietnam. Correspondence to: Tuan Dam soiet.hust..cu..n..
Our key contributions include:
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
power mean backup operator for stochastic, con-

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
linuous MCTS. Power-mean updates naturally handle non-stationary dynamies without the instabilities of- ten seen in simple averaging.
3. Setup and Notations
We consider infinite-horizon discounted MDPs (S T, R) with continuous state space S - R". continuous action space A
A
polynomial exploration bonus tailored to stochastic MDPs. We establish that achieves conver- gence at rate O(n Ç e (0,1/2), matching the known results of POLY-HOOT (Mao et al. 2020), but
S RT, stochastic tran- sitions T S x A + P(S), bounded rewards R: S x A - [0, Rmax], and discount factor y E (0, 1).
Stochastic-Power-
For policy π : S + A, we define value functions:
now for stochastic domains.
Comprehensive empirical validation. Experiments on robotic tasks show Stochastic-Power- outperforms prior MCTS variants (e.g., HOOT, discretized-UCTT Voronoi MCTS) in final perfor- mance and robustness, confirming both its practical viability and theoretical soundness.
(T((s) = B
Σ I==
7 R(s,, ax) 100 =
Q* = B
R(s,, az) 1800 =,,00 =
The objective is finding optimal policy n' such that V (s) (s) sup, V*(s). We assume access to a generative model providing sampled transitions and re- wards.
2. Related Works
Monte Carlo Tree Search (MCTS) has proven highly effec- tive in deterministic environments, famously demonstrated by UCT (Kocsis et al.) )006) for discrete actions. Beyond UCT, alternative exploration strategies have emerged, in- cluding entropy regularization methods like MENTS (Xiao eet al. 2019), RENTS and TENTS (Dam et al.] 2021 2024ap, and boltzmann-basser approaches (Painter al. 2023), though these rely temperature parameters that may impede convergence. However, adapting MCTS to continuous or stochastic domains remains non-trivial. Early works such as HOOT (Mansley et al.) 2011) introduced hierarchical bandit mechanisms for continuous actions, but relied on logarithmic bonus terms ill-suited for non- stationary value estimates. Recent advances in power mean estimation for MCTS include the work of Dam et al. (2020) 2024 which introduced power mean backups for discrete, deterministic environments, and Dam et al. 2024b), which extended power mean estimation to dis- crete, stochastic MDPs. Our work differs by address- ing continuous action spaces in stochastic settings. Aug- menting MCTS with progressive widening (Auger et al., 2013) can mitigate sparse sampling in continuous spaces, yet often struggles under deep planning large explo- ration demands. Meanwhile, recent methods such as POLY- HOOT MMo et al. (020) improved convergence in de- terministic tasks by adopting polynomial exploration, al- though extending to stochastic settings required further analysis. For continuous action spaces. Kim et al.] (2020) proposed Voronoi MCTS using Voronoi partitioning with regret bounds, but limited to deterministic settings. Our algorithm, Stochastic ceaiicPPowwe line of work by combining a power-mean value backup with polynomial bonuses, thereby addressing the dual chal- lenges of continuous actions and non-stationary dynam- ies while providing theoretical guarantees for stochastic MDPs.
4. Background material
In this section, first provide some background knowl- edge about Markov Decision Processes, and then we give an overview of Monte Carlo Tree Search.
Monte Carlo Tree Search (MCTS) MCTS (Browne) et al. 2012) combines Monte Carlo sampling with tree- based exploration for planning under uncertainty. The al- gorithm iteratively: (1) selects nodes based on statistical information, (2) expands the tree, (3) evaluates new nodes via rollouts, and (4) backpropagates rewards. Effectiveness depends on the value update operator and node selection strategy.
MCTS Formalization MCTS grows a planning tree by collecting trajectories from initial state Su to depth D or leaf nodes. Playout policy To estimates terminal values. Af- ter trajectories, the algorithm outputs best action estimate ãe and value estimate Vs()).
Performance is measured by convergence rate r()):
E(V* Q" @.)) & r()
or [s[V"(so) D2(55)]l < <(())
Value functions are defined inductively: v(sp) VolSD) at leaves, and for < D:
advances this
((s, r(sa + Σ ((
v(s.) max ())
2

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
where r(sá; a) represents the expected reward when taking action in state sa- Thus, we have the following approxi- mation bound:
5.1. Generic UCT-like Algorithm
For node Sd at depth d, we define value estimates (t, and Q-value estimates (1) (Sa. a) with visit counts (t) and T (t..
(s0 a) Q(50; a)l & > Vollco;
where the supremum norm is taken over states reachable within D steps from 8g. The goal of MCTS is to minimize the convergence rate r(t) by accurately estimating Q(s0, a) and V (s)). ultimately upproximating (* a) and identi- fying the optimal action a* arg max, (50, a) at the
A UCT-like algorithm follows predefined bonus functions [t, sd, a) for each state, action (sa, a) at time step t. It iteratively collects trajectories from root So until reaching a leaf or depth D. Upon reaching a leaf, playout policy To provides value estimate Vo-returning i.idd samples stochastic or fixed values if deterministic.
root node.
Trajectories {so, ro,...; Vss.)) are collected ing action selection:
Hierarchical Optimistic Optimization (HOO) HOO (Bubeck et al.] (011)) tackles continuous action spaces by organizing them into a binary partition tree. Each node represents a subset of the action space, which is split into two smaller subsets each level. In each round, HOO traverses from the root to leaf, favoring child nodes with larger upper confidence bounds (B-values) Let (h, i) index the node at depth h and position i, with ih.,i as its corresponding subset. The number of visits to all descendants of (h, i) is (m), and the empirical reward mean is (n). HOO then forms UCB-like bound (n)(n) with logarithmic bonus, and action is selected as
ad = arg max { (t) a) + B(t, sd a)} aEAr,
where 8441 ~ P(-|as, aa). After 1 simulations, the esti- mated best action is 0g arg max, Tt (50, a)..
5.2. The Stochastic-Power-Hot Algorithm
is an MCTS-based algo- rithm for continuous-action, stochastic environments. It in- troduces power mean backup operator for value estima- tion and a polynomial exploration bonus, enabling efficient planning under stochastic dynamics.
Stochastic-Power-tae
a = arg max (nanln) +
logn (m)
up"
5.2.1. ALGORITHM OVERVIEW
where C,v, h h are constants. Searching proceeds top- down, always expanding toward the child with the higher B-value, until a leaf is chosen the action. Mansley et al. (011) extends HOO in MCTS and proposes HOOT. How- ever, like|Kocsi, Kocsis and Szepesvári (2006). this algorithm uses a logarithmic bonus for exploration rather than a polyno- mial one. As noted by [Shah et al. (2020), this choice leads to unclear convergence guarantees because non-stationary rewards lack concentration. Mao et al. (2020) propose and establish non-asymptotic convergence guarantees for POLY-HOOT to enhance the HOO strategy with polyno- mial bonus term to account for the non-stationarity
(pseudocode shown in Alg. D iteratively builds search tree using four main phases: Selection, Expansion, Rollout, and Backpropaga- tion. At each step, it leverages power mean operator to compute value estimates and polynomial exploration term to balance exploration and exploitation.
Stochastic-Power-teee
5.2.2. SELECTION AND EXPANSION
the Stochastic-Pone Paweiiic-ooeeHHHOe HOOT navigates the search tree from the root to leaf node. At each depth d, it selects an action by traversing the Hierarchical Optimistic Optimization (HOO) tree, choosing child nodes based on their upper confidence bounds. If a state has not been visited before at a given depth, a new HOO agent is initialized.
During
selection
phase,
arg max Fris + Ct Th + pD
by
Fa
2d
by, Ozd, By are constant. However, Mao et al. (2000) can only provide convergence proof for deterministic settings
leaving a gap in stochastic environments. We build upon this idea in our Stochastic-Power to close this gap.
In the expansion phase, new child nodes are added the tree based the selected action. If the depth limit has not been reached, an arbitrary action is sampled within the cor- responding partition PH,I, and a new node is created.
algorithm
5. Stochastic Power-HOOT
5.2.3. ROLLOUT AND BACKPROPAGATION
In this section, we first present a generic UCT-like algorithm and then we present our Stochastic-Power- algorithm.
In the rollout phase, a default policy To is used to simulate trajectories from the expanded node to estimate the value
3

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Algorithm I: Stochast ct
with y is a discount factor. n. : is the number of rollouts. (ba (ba)a-o- {az)a=o-
{Ba)2-o are positive algorithmic constants that satisfy conditions as in Table mo is a rollout policy. C is an exploration constant.
Input:
root node state so
Output:
optimal action the root node
Rollout (8)
HOOUpdateV (d, for (h, P:
V(a) average of the call to (s)
return (s)
Th.s t Th,s +1 Fa, (1-1/Th,,)
Y/Th.
SelectAction (s, depth = d, t)
end
if state s has never been visited at depth d then Initialize HOO agent at state s and depth d:
for (h, 1) E T do
bet1 Un = Phit i + Ct Pa- T Th
T -- [(0,1))
Patl
+ vip
B1.2. B2.2 + +00
end
else
+ the HOO agent constructed state and depth d previously
T T while
end
T' + {(0, 1)} do
i) + 10.
(h, 1) < an arbitrary leaf node of T Ba. min Un. max { B,,4,,2, B141,2011 }
Mnitialize HOO path in the current round:
Pi i),
T T ((b,))
while (h, E T
end
if B141,25-1 > 1, then
(h + (h+ + 1,2i 1)
ml.0op
L=
else
for simulation round +- 1 do for depth d + 0 to D -
ih + + 1,24)
end
ad + -e=Selecttctionnaa depth =d, t)
P. + Pt ih)
8d41~ P(-las,aa)
end
r(sa, 0a)~ R(sa, ad,
(H, 1) (h
end
if H < H then Choose arbitrary arm X in PH.I
r(SD)~ V(SD) for depth d + D - to do (1) <- (1) +1) (s) + (1-1/T 1/Tsa (aaaa(t))@aa (t)) + (r(sa, ad) + +r (0) (8(+))))) (f) (1) +- (1)
An. =X
(U,,
B8+122-1; BH+1221 +- +00
return X
end
(H + 1,
return An.I
( Tagall) (I (1)) $1
HCOUpdateV sa,t, (8a))))(8a)) end end return V.((s))
of terminal states. The resulting reward is then propagated back up the tree.
5.2.4. VALUE BACKUP AND EXPLORATION STRATEGY
Unlike standard MCTS approaches that rely on simple av- eraging, Stochast i c-Power-HHOS employs power mean backup operator aggregate value estimates:
The buckpropagation phase updates the visit counts and value estimates of nodes along the traversed path. For each node (h, :), the empirical mean reward Ih.s is updated, and the upper confidence bounds UR, are adjusted using poly- nomial exploration bonus. The backpropagation step en- sures that future searches prioritize promising regions of the action space.
Vi(ea) = (E Tea.a
(Sr. a)))
(1)
Tea
This formulation provides tunable balance between mean and max-based value updates, allowing for better adapta- tion to stochastic rewards.
Additionally,
incorporates
4

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
polynomial exploration bonus:
function ʃ in 1 a polynomial rate: 11./ f1 < Ch
for some constant C > 0 and Ç (0,0.5). This limiting function, denoted as f. is the mean-payoff function and is formalized in Theorem 2.
Sa+1 od+1 Pa+1
Uh, = fr.. + Ct Tni
+ v1p
This approach ensures a more stable and theoretically grounded exploration mechanism compared to traditional logarithmic bonuses.
Given that MDP rewards are bounded by Rmax- the ban- dit payoff' at any tree node at depth d and the mean- payoff function f are also bounded by Rimx Let f suPRex f(x) represent the highest achievable payoff by any HOO agent, and let X, be the action chosen by the agent at time t. The agent aims to minimize the cumu- lative regret over the first rounds, defined Rn - nf - Y,, where Y, is the observed reward of choos- ing X, at time I, with E[Y]] (x()).
I-y
Table I: Summary of constraints on the algorithmic con- stants for d E f0.1......D D). (d' is a constant that is bigger than d)
Conditions on the parameters ha, Odd Pa,P (all must hold):
ba- < Ord
and
ba= >
Our analysis is based on two main assumptions, adapted from (Bubeck et al.] [00IT) which support the hierarchical structure of MCTS with coverings and the smoothness of the reward function.
2. Either (1
I S 2
and
Od S ) or (p
2,
Od S
Bg 2
and
< Odd
8 <)
p
3.
0dd 1
bd 0d
S ba <
ad.
Assumption 1. For each HOO agent, with parameters #1 and p E (0, and covering tree (Ph.),, we assume there exists dissimilarity function E: X x X + [0, oo] satisfy- ing:
dat1
ba-1 1 -
ad+1
Old
x
1 d'
Bo+1
ad41
5. Sa = (bu+1 - 1).
(a) There exists constant 1/2 > 0 such that for each integer h > O, the diameter of any partition Pa, shrinks geometrically as diam(Pn..) & ungh for all iE (!,...,,2),, where diam( (A) _ suPa.ee ((x
Our theoretical framework requires bounded planning hori- zon D. For analysis purposes, we consider a modified al- gorithm that generates fixed-length trajectories of depth D. applying the playout policy exclusively at terminal leaf nodes. Practical implementation could use infinite depth.
(b) Each partition Pr, contains point with smaller covering region B & B( 12p²) C Ph.s, where B(x, e) = (u E X ((x, <.}.
6. Theoretical analysis
Planning in MCTS requires a sequence of decisions along the tree, with each internal node acting as a non-stationary bandit. The empirical mean at these nodes shifts due to the action selection strategy. To address this problem, we first analyze non-stationary multi-armed bandit settings, fo- cusing on the concentration properties of the power-mean backup for each arm compared to the optimal value. We then apply these findings to MCTS.
(c) These smaller covering regions do not overlap: B n B = 0 for all 1 < < < 2
Assumption 2 (Smoothness). The limiting mean- mean-f function satisfies:
S ("- < S" (i00
X.
6.2. Non-stationary Power Mean HOO
6.1. Theoretical Analysis Framework
We begin by developing our theoretical framework through the lens of non-stationary multi-armed ban- dits, which will serve as the foundation for analyzing Stochastic-Powers
We start by defining essential notation and assumptions for our theoretical analysis. Consider a Hierarchical Optimistic Optimization (HOO) agent, where C A C [0, 1 rep- resents the continuous action (or arm) space in the current state. Each action E X has an associated stochastic re- Q-value at the current state in the MDP. We define [((x) X + R as the expected reward at time t, termed the tempo- rary mean-pay mayoff function. Since the rewards are impacted by future choices deeper in the MCTS tree, fe is non- stationary. However, we assume fi converges to a limiting
in the full MCTS setting. Each node in our search tree can be viewed as ban- dit problem where arms correspond to possible actions (HOO tree paths) and rewards evolve non non-stationarily due to changing value estimates from deeper levels.
ward distribution, representing the "cost-to-go"
Problem Formulation Consider a continuous-ane armed bandit over domain X S [0,1]] with rewards bounded in [0, Rmax]. Unlike classical bandits, our reward process
5

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
non-stationary-the expected reward [x) for I evolves as the algorithm progresses. This non-stationarity captures the changing value estimates that occur in MCTS as the tree expands and value propagation refines estimates.
time
The power mean operator (p(P) provides a flexible interpolation between conserva- tive (arithmetic mean, p 1) and optimistic (maximum, p + oc) value estimates. This tunability is crucial for bal- ancing exploration and exploitation across different levels of environmental stochasticity.
Power Mean Aggregation:
Our bandit satisfies two key structural properties:
ii) Fixed-arm convergence: The mean mean-payoff function converges polynomially:
HOO Tree Refinement: The hierarchical structure allows the algorithm to focus computational effort on promising regions of the continuous action space while maintaining theoretical coverage guarantees.
C n5'
fn fllo
Vn 1nLL.
(4)
for constants C² > 0 and 0 < <<<<> <
Theoretical Foundation The convergence analysis for this algorithm builds on the following result from Mao er al. (2020):
iii Fixed-arm concentration: Individual arm estimates concentrate at polynomial rates:
Theorem (Enhanced HOO for Non-stationary Bandits Mao et al. 2020)). For continuous-ammn bandit sat- isfying properties (4) and (5), with parameters fulfilling al1 111-b/e b/a) & b < a; b 3, and p < n n-a/0 the
P Y, s(x) 2
E & <on
(5)
enhanced HOO agent achieves:
for appropriate constants C, 0, >0
(i) Optimal-arm convergence:
LE EE 1=1 Yı] - ff
<
HOO Tree Structure and Action Space the contin- uous setting, we cannot enumerate all possible actions. Instead, use the Hierarchical Optimistic Optimization (HOO) framework to adaptively partition the action space X into a binary tree of depth H. Each root-to-leaf path in this tree represents a distinct "pseudo-action" correspond- ing to a refined region of X.
Co as
(ii Optimal-arm concentration: P Y. fl
6) & O'n C'n--
and Yg is the random 1-b/a b-3 3' b-3 where a' 1+d'-B/a reward observed at time t.
2
Let K denote the finite set of all possible paths from root to leaf in the depth-Hf HOO tree. For each path a K,
Concentration Rate Formalization To facilitate our analysis, we formalize the notion of polynomial concen- tration:
maintain:- Visit count: (n)
1= 1a a)-
Empirical reward: fa.r.(.)) = (.)
Ya,
where Ya, is the s-th reward obtained from path a.
Definition (Polynomial Concentration). A sequence of estimators (V,) (n)) concentrates at rate (a, 3) toward limit
Non-stationary Power Mean HOO Algorithm Our al- gorithm extends classical HOO to handle non-stationary re- wards through polynomial exploration bonuses and power mean aggregation. The complete algorithmic description is provided in Algorithm 2 in the appendix. The key components include: (1) hierarchical action space parti- tioning via HOO trees, (2) polynomial upper confidence bounds of the form Ctb/8T, for robust exploration in aaP
V if there exists constant c >> 0 such that:
Vn > 1, VE 0/3
P(V. V| & 88-8
We denote this as V a. V.
Assumption 3 (Stochastic Reward Concentration) For
each action æ E X, the empirical mean Jn = Σm Y: satisfies 7n 0. f(x) for the true mean f(x). where Y, is
h,i
non-stationary settings, and (3) power mean aggregation
=1-000 the I-reward follows the "psudo-action" path æ from HOO.
Pa(p)) = (Ix Ta(m) Po (m))
1/P
to flexibly balance ex-
ploration and exploitation through the tunable parameter p.
Power Mean Concentration Result Our main theoret- ical contribution for the bandit setting establishes that power mean aggregation preserves polynomial concentra- tion rates:
Key Algorithmic Components Polynomial Explo- ration Bonus: Unlike classical UCB algorithms that use /logn/Ta bonuses, we employ the polynomial term Cnb/3 Cnbl9/TT,m)) (n) This provides stronger exploration guar- antees in non-stationary settings where confidence intervals must adapt to changing reward distributions.
Theorem 2 (Power Mean Concentration). For estimators
a. Pa,n 2n fi, with f max, (fr,,), if parameters sat-
no0
isfy (1 E p 2, a & 3/2) or (p > 2, < a -- -3/p <
6

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
and (11 - bb/)) bb< a, then:
Intuition: This lemma captures the essence of Bellman backup in stochastic settings. The Q-value estimate com- bines immediate rewards (which concentrate at standard rates) with discounted future values weighted by transi- tion probabilities. Crucially, the concentration rate (a, (3) is preserved despite the stochastic transitions, enabling our inductive analysis.
(p) d' fr
where a' 1-b/a b-3 +3/0 2 8¹ b-3
This bandit-level result provides the foundation for our MCTS analysis, where each tree node corresponds to a non-stationary bandit with arms given by child nodes and rewards determined by downstream value estimates.
| enables a powerful inductive argument for tree-wide concentration:
Inductive Concentration Analysis Lemma
6.3. Monte Carlo Tree Search Analysis
(i) Base Case (Leaves); At depth D, rollout policies pro- vide value estimates V(D) with known concentration rates.
Having established the concentration properties of power mean estimation in non-stationary bandits, now extend these results to the full MCTS setting. The key insight is that each internal node in our search tree can be modeled as a non-stationary multi-armed bandit where arms corre- spond to child nodes and rewards are given by (evolving) value estimates from deeper levels.
Inductive Step: At depth d D, assume child values ((sa+1) concentrate rate (a.+1, Sa+1). Then:
By Lemma Q-values @(sa; a) concentrate at the same rate (a.+1.
By Theorem 2 the power mean aggregation (ss) concentrates at the transformed rate (Ora,
The Inductive Framework Our analysis proceeds inductively through the tree struc- ture. At the leaves (depth D), rollout policies provide di- rect value estimates with known concentration properties. Moving upward, each internal node aggregates child values using our power mean operator while selecting actions via polynomial exploration bonuses. The challenge is showing that concentration rates propagate correctly through this hi- erarchical structure.
From Bandits to Trees:
(ii) Propagation: This process continues upward, with each level's concentration rates determined by the power mean transformation of the level below.
Attribution and Technical Innovation While our over- all approach follows the inductive framework established in prior work (Shah et al. 2022), two key technical innova- tions are required for the stochastic continuous setting:
Value Concentration in Stochastic MDPs The foun- dation of our MCTS analysis rests on understanding how
Q-value estimates behave when transition dynamics are stochastic. The following result, established in Dam et al. (0044)), provides the crucial bridge between individual value estimates and their aggregated Q-values:
(i) Stochastic Q-Value Analysis: Lemma | from Dam jet al. (2024b) extends concentration analysis to stochastic MDPs, handling the additional variance in- troduced by random transitions.
Lemma (Q-Value Concentration, Lemma 1 of Dam et al. 2024b)). Consider state-action pair with M possible next states. Let (Vm,n)nzi be value estimators for next- state m satisfying Vm, anlyy V... bounded by constant T.. Let X; be i.i.d. immediate rewards with mean μs, and Sy be i..dd. next-state indices from distribution p = (PI....,PM)
(ii) Power Mean Backup: Theorem 2 establishes con- centration properties specific to power mean aggrega- tion, enabling flexible exploration- explooitttiioiiiionnn tuning beyond standard arithmetic means.
Main MCTS Convergence Result The inductive frame- work culminates in our main convergence guarantee:
Define visit counts No Hi < n S = m3 and the Q-value estimator:
Theorem 4 (Convergence of Expected Payoff). For Brnchastic-Power--e
applied to stochastic con- timuous MDPs, with optimal parameter tuning, the ex- pected value estimate at the root satisfies:
M
n N=
X1 +
No.
n
n
m=
Then, with 2a & B and B 1:
- V(so) < <((n
M
2n
0,3
| + 7 Σ
pm Vm
where Ç E (0, 1/2) depends on the algorithu parameters and tree depth.
110000
m=
7

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Sketch. The proof follows by applying Jensen's in- equality and integrating the tail probability bounds estab- lished through our inductive concentration analysis. Com- plete details are provided in Appendix F.
Sketch.
selected actions, (2) dynamics noise through random per- turbations state transitions, and (3) observation noise by adding Gaussian noise to state observations. Addition- ally, since power means require strictly positive inputs, we apply reward transformations of the form max(0.01, (r + offiett x scaling) while preserving optimal policies.
Remark 1 (Comparison with POLY-HOOT). Theorem achieves the same polynomial convergence rate Onn as POLY-HOOT (Mao et al. (020), but under significantly more general conditions. Key distinctions include:
Baseline Comparisons: We compare against four estab- lished continuous MCTS methods: discretized-UCC (Koc- sis et al. 2006), PW with progressive widening (Auger et al. 2013). HOOT (Mansley et al., 2011), and POLY- HOOT MMoo et al., 2020). We also include Voronoi MCTS (Kim et al. 2020), a recent method designed for
Stochastic vs. Deterministic: Our result handles stochastic MDPs while POLY-HOOT assumes deter- ministic dynamics
deterministic continuous spaces, to demonstrate the chal- lenges of applying deterministic methods to stochastic set- tings.
Power Mean vs. Arithmetic Mean: We provide guar- antees for for flexible power mean backups (p 2 1) rather than fixed arithmetic means 11)
7.2. Classic Control Results
Continuous Actions: Both methods handle contin- wous action spaces, but stochastic extension is novel
The results in Table Ecochastic-Powe--oOee
demonstrate
effectiveness across di- verse control challenges. While all methods solve the basic CartPole task, only Stochastic Srrochasti--Poee-HOOr Pooer--HOO han- dles the increased gravity variant (CarPPoleIGG) optimally. The algorithm shows particular strength in sparse reward settings like MountainCar, where the polynomial explo- ration bonus enables effective long-horizon planning, and in complex dynamics like Acrobot under high gravity conditions.
This demonstrates that Stochastic-Fowe---te main- tains theoretical rigor while significantly expanding the scope of domains with convergence guarantees.
Practical Implications The theoretical guarantees trans- late to several practical advantages. The polynomial concentration ensures reliable performance even un- der significant environmental noise, providing robust- ness in challenging conditions. The power parameter pp can be tuned based on domain characteristics with- out losing convergence guarantees, offering adaptabil- ity to different problem settings. Furthermore, the in- ductive structure ensures guarantees extend to arbitrary tree depths and action space dimensions, enabling scala- bility across diverse applications. These properties make Stochastie wwettiic--o-----. P----Poer--------- HOOT suitable for deployment in complex real-world domains where both theoretical relia- bility and practical flexibility are essential.
7.3. nigh-Diimensioal Robotic Environments
To evaluate scalability, we test on MuJoCo robotics tasks with significantly higher dimensionality and complexity.
Table 3 reveals several critical insights:
Dimensional
Scalability:
maintains strong per- formance the 17-dimensional Humanoid environment, achieving 3.1x improvement over UCT despite the exponential growth in action space complexity.
Stochastic-Pover--te
The optimal power param- Senrecteristis-HHumaa benefits from moderate values (p = 2) while the more stochastic Hopper environment requires higher values (p = 8) to effectively concentrate search on promising regions.
Adaptive Power Parameter:
7. Experiments
eter varies with environment
We evaluate Stochastic-Powe Powee--owrr both clas- sic control tasks and high-dimensional robotic environ- ments, all adapted to continuous-action, stochastic settings. Our experimental design addresses the key challenges of planning under uncertainty while demonstrating the scala- bility and robustness of our approach.
Stochastic Robustness: The catastrophic failure of Voronoi MCTS on Hopper (12.7x worse than UCT) versus reasonable Humanoid performance (2.8x better) demon- strates the critical importance of explicit stochasticity han- dling. This validates our core theoretical contribution.
7.1. Experimental Setup
Environment Modifications: We create stochastic ver- sions of standard benchmarks by introducing noise at mul- tiple levels: (1) action noise via Gaussian perturbations to
Our results show that Voronoi MCTS, while effective in some high-dimensional tasks, struggles in stochastic envi- ronments due to its deterministic assumptions, underscor-
8

---

Our comprehensive evaluation demonstrates that Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
CartPole
CartPole-IG
Pendulum
MountainCar
Acrobot
Discretized-UCT
77.85 0.00
37.95 +:
1263.68 +: 37.66
-0.020 0.004
70.14 32.29
PW HOOT POLY-HOOT(P=1)
77.85 0.00
68.46 + 6.87
1141.51 + 80.93
-0.020 0.002
77.85 0.00
77.85 + 0.00
38.51 + 0.81
1043.23 + 70.79
-0.007 + 0.001
70.05 + 37.05
77.85 = 0.00
77.85 = 0.00
1205.886 = 110.01
-0.055 + 0.002
77.85 0.00
Stochastic-Powor-RooT
77.85 0.00
77.85 + 0.00
1397.40 + 95.42
27 27.285 + 0.163
77. 0.00
Table Performance on stochastic classic control tasks. Each environment features continuous actions and multiple noise Bold indicates best performance.
sources. Stochastic-Powerr uses p
Algorithm
Humanoid-vD
Hopper-v0 (3D action)
(17D action, 376D state)
UCT (baseline) POLY-HOOT (p HOOT
- 136.99 + 44.84
5216.93 + 179.64
-44.40 + 3.33 (3.1x)
53230.66 + 2844.33 (2.5x)
-57.35 10.46 (2.4x)
10452.83 3885.12 (2.0x)
-89.74 24.16 (1.5x)
5218.73 73 = 1384.90 (1.0x)
Voronoi MCTS
-48.69 + 9.52 (2.8x)
411.70 + 29.03 (12.7x worse)
Stochattic-Power-HO0T (p 2)
44.12 + 6.22 (3.1x)
13303.61 3070.34 (2.5x)
Stochastic-Power-HBor (p
-44.40 + 3.33 (3.1x)
13348. + 6110.36 (2.6x)
Table 3: Performance on high-dimensional stochastic MuJoCo environments. All environments include action, dynamics, and observation noise. Performance multipliers relative UCT baseline shown parentheses. Bold indicates best perfor- mance per environment.
Power
3
6
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 CartPole-IG. Values 2 and p achieve optimal performance.
ing the need for rigorous theory in continuous MCTS. It also shows that Stochastic io-psterrr-eer Peoowr-Biie HOOT achieves more consistent performance across diverse stochastic set- tings.
settings 4. Validates theoretical predictions through em- pirical success in precisely the challenging scenarios our analysis targets
These results confirm that our theoretical extensions to stochastic continuous domains translate to practical algo- rithmic advantages in complex real-world planning scenar- ios.
7.4. Power Parameter Analysis
ro- bustness across power parameters. The optimal values (p = 2, 4) suggest that moderate power settings effectively bal- ance exploration and exploitation in stochastic environ- ments too low fails to sufficiently focus search, while too high may over-commit to early estimates.
Table 4
demonstrates Stochastic-Pooer--ee
8. Conclusion
We have introduced Stochastic- Pocsllc--we--HHOOS HOOT, a novel continuous-action MCTS algorithm designed for stochastic environments. By combining polynomial exploration bonus with power-mean value backups, St Stochastic-Pont Power- HOOT effectively balances explo- ration and exploitation in stochastic MDPs. Our theoretical results show a convergence rate of Onn Ç E (0, extending prior analyses of continuous MCTS in determin- istie to stochastie MDPs. Empirical evaluations on custom tasks validate both its robustness and versatility, highlight- ing the impact of tuning the power mean for complex ward structures.
7.5. Key Experimental Findings
1. Scales effectively to high-dimensional continuous spaces while maintaining theoretical guarantees 2. Adapts robustly to varying levels of environmental stochasticity through power parameter tuning Outperforms existing methods consistently across diverse domains, with partic- ularly strong advantages in sparse reward and high-noise

---

Tuan Dam, Odalric-Ambrym Maillard, and Emilie Kaufmann. Power mean estimation in stochas- tic carte-carlo tree search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Impact Statement
Fortieth Conference on Uncertainty in Artificial In- telligence, volume 244 of Proceedings of Machine Learning Research, pages 894-918. PMLR, 15-19 Jul 2024b. URL htttps://proceeddie mil..
Our proposed Stochastic- Poe---ooeereeee HOOT algorithm provides a new approach for planning in continuous-action, stochastic environments. By combining polynomial explo- ration with power-mean backups, it can more effectively handle complex real-world tasks where standard Monte Carlo Tree Search or deterministic models struggle. Poten- tial applications include robotics, autonomous systems, and large-seale resource tive planning under uncertain dynamies critical. We not foresee immediate negative societal effects from this research; nonetheless, with all Al advancements, respon- sible usage and careful considcration of ethical, economic, and security implications remain essential.
press/ Fress/v2444
Tuan Q Dam, Carlo D' D'Eramo, Jan Peters, and Joni Pajarinen. Convex regularization in monte-carlo tree search. In Marina Meila and Tong Zhang, editors, Pro- ceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2365-2375. PMLR, 18 24 Jul 2021. URL v139/dam21aa 1tttmammmm..mmmlmll.
domains where adap-
.lr press/
Tuan Quang Dam, Pascal Klink, Carlo D D'Eramo, Jan Pe- ters, and Joni Pajarinen. Generalized mean estimation in monte-carlo tree search. In Proceedings of the Twenty- Ninth International Joint Conference on Artificial Intelli- gence (IJCAI-20), pages 1584-1591, 2020.
Acknowledgments
This work is funded by Hanoi University of Science and Technology (HUST) under Project No. T2024-TD-022.
Beomjoon Kim, Kyungjae Lee, Sungho Lim, Leslie Pack Kaelbling, and Tomás Lozano-Péres Monte carlo tree search in continuous spaces using voronoi optimistic opti- mization with regret bounds. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 99 19249924, 2020.
References
David Auger, Adrien Couetoux, and Olivier Teytaud. Continuous upper confidence trees with polynomial In Machine Learning and Knowledge Discovery in Databases: European Con- ference, ECML. PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part 13, pages 194-209. Springer, 2013.
exploration-coonistenny
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference ma- chine learning, pages 282-293. Springer, 2006.
Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 2006.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arxiv:1606.01540. 2016.
Chris Mansley, Ari Weinstein, and Michael Littman. Sample-based planning for continuous action markov de- cision processes. In Proceedings of the International Conference on Automated Planning and Scheduling, vol- ume 21, pages 335-338, 2011.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search meth- ods. IEEE Transactions on Computational Intelligence and Al in games, 4(1): 2012.
Weichao Mao, Kaiqing Zhang, Qiaomin Xic, and Tamer Basar. Poly-hoot: Monte-carlo planning in continuous space mdps with non-asymptotic analysis. Advances in Neural Information Processing Systems, 33:4549 4559, 2020.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-rmedd bandits. Journal of Machine Learn- ing Research, 12(5), 2011.
Michael Painter, Mohamed Baioumy, Nick Hawes, and Bruno Lacerda. Monte carlo tree search with boltzmann exploration. Advances in Neural Information Processing Systems, 18:78181-78192 2023.
Tuan Dam, Carlo D' D'Eramo, Jan Peters, and Joni Pajari- nen. A unified perspective on value backup and explo- ration in monte-carlo tree search. Journal of Artificial In- telligence Research, 81:511-577, 2024a.
Devavrat Shah, Qiaomin Xie, and Zhi Xu. Non- asymptotic analysis of monte carlo tree search. In Ab- stracts of the 2020 SIGMETRICS/Peformance Joint In- ternational Conference on Measurement and Modeling of Computer Systems, pages 31-32, 2020.
10

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Devavrat Shah, Qiaomin Xie, and Zhi Xu. Nonasymptotic analysis of monte carlo tree search. Operation Research, 70(6):3334-3260, 2022.
Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. FAlché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc., 2019. URL httpsss/ppoceeeesss.nuuuu neurips.
cc//apet_fileeppppe/////////////
pdf

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
A. Outline
Notations will be described in Section B.
Psudocode of Non-stationary Power Mean HOO in Section C.
Supporting Lemmas are presented in Section D.
Technical Lemmas are shown in Section E.
Convergence of Stochastic-Power-Ho0 Non-stationary multi-armed bandits shown in Section
Convergence of Stochastic-Power-Bee in Monte-Cario Tree Search is shown in Section G.
Experimental setup and Hyperparameter selection are provided in Section H.
B. Notations
Table 5: List of all notations for Non-stationary Multi-arms bandit.
Notation
Type
Description
N
Number of arms
(1)
N
Number of visitations arm after timesteps
ff.
R
mean value of arm
a*
A
optimal action
f*
RR
mean value of an optimal arm. We assume it is unique.
(p)
power mean estimator, with a constant p E [1, +00)
Fo.m
mean estimator arm a after n visitations
C. Non-stationary Power Mean HOO
Algorithm 2: Non-stationary Power Mean HOO
Require: Parameters B, b, C,p, Mi, p: HOO tree depth H; number of rounds Power mean value estimate (p)
Ensure:
1: Initialize: T + {(0, })}, B1,,, B2, +00
2: Play each available path once to initialize
3: for = K + 1 to n do
4: a; < WWWEERMEANHOO.QUERRR
5: Observe reward Y,
6: POWERMEANHOO. LUPDATEUUP a,, Ye)
7: end for
8: Compute final power mean estimate:
9: F.(p)) + (IK Ta(n) Pa.T.(a)) return return/.(1) Tm(()
1/p
12

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Algorithm 3: PowerMeanHOO Query
Require: Round t
Ensure: Selected action X
1: (h, < 10
2: Initialize HOO path: Pt + ((b
3: while (h, E T do
4: if B1++121-12 11 then
5: (h, - (h 1, 1)
6: else
7:
(h, < (h + 1,)
8: end if
9: Pt +- Pr U ((h, i
10: end while
11: (H,1) ( ())
if H < H then
13:
Choose arbitrary arm X in PH.
14:
AH. X
15:
T T-TU((H,))
16:
B14121-11
BH+121 144.11 + t00
returnX
17:
else
(Reached maximum depth, reuse existing action)
1H, + (1 [,
returnAH,
20: end if
Algorithm 4: PowerMeanHOO-UUppac
Require: Round i, selected path a, observed reward Y,
Ensure: Updated statistics and confidence bounds Retrieve path for action a;
2: for (h, i) Pt do
3: Th,s + Th,; +1
4: fn,s+ + (1 1/Th,) Y./Th.
5: end for
6: for (1, T do
7: UNS + Fi.i + C15181100 his + pMp
8: end for
9: T' T
while T' + {(0,, 1)} do
(h,, arbitrary leaf node of T
12: BA,s minfUUn,s max Bu+ B
13: T'+T's ((h,i) i)}
14: end while
D. Supporting Lemmas
In this section, we will present all necessary supporting Lemmas for the main theoretical analysis. We start with result of the following lemma which plays important role in the analysis of our MCTS algorithm.
Lemma (Lemma Dam et al. 2024b)). For m E [M], let (Vm,adnza be a sequence of estimator satisfying Vm.. a.3
n- Vms and there exists a constant L. such that Vinn & L,, Vn 2 Let X₃ be an iid sequence with mean i and S; be an
13

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
iid sequence from distribution p (p1..... (Prr supported on f1,...,Mi M). Introducing the random variables N #li & S; 8m we define the sequence of estimator
M
N m
@
Nm
m
Then with 2a & 3,8 1,
M Pm
On a.8
+
Vm.
m=l
Lemma (Lemma 1. Then
Dam (024bb). Let consider non-negative variables I, y E R+, and constant m that 0 &
(x+ & x + +
(2)
We use Minkowski's inequality as shown below
Lemma 3. (Minkowski's inequality) Given > 1, 801.811 E R. RRii= 1,2, ...,,, then we have the following inequality
1 < E(ei))
((a + uil)")
[(ve)))
Proof. This is basic result.
E. Technical Lemmas
Lemma 4. (Lemma Bubeck et al. (2011)) Under Assumptions I and 2, for some region Ph,s An. & cuip for some constant e > 0, then all the arms in Ph,s are max (2c, c 1poopiaall.
Proof. This lemma is stated in exactly the same as way Lemma 3 in Bubeck al. (2011), and we therefore omit the proof here.
Lemma S. There exists some constan! C O, such that [hl C (12pht for all h > 0.
Proof. This result the same as the second step in the proof of Theorem in Bubeck et 2011). We, therefore, omit the proof here.
Attribution Note. The proof' of Lemmas 4-7 below follow the same high-level inductive and concentration- strat- egy as Lemmas 4-7 of Mao al. 2020), with important concentration- bound for the case Dn.i & viph which is missing in the Mao et al. (2020) paper.
For transparency we reproduce the full proofs. Lemma 6. Let Assumptions and hold. With
Uns(t) = (t) + (t, aa/0 + vrp"
(i) For every optimal node 3(, i), let n 2 1, Then for all l E (1,2,...,,,, n). there exists a constant Ci > 1, such that
Ci
P (U < f*) &
-
(ii) For all integers & n. for any suboptimal node (h, i) such that A > vip", and for all integers > An,(n)
[
2r Ah. there exists constant C2 > 1, such that
Czt
PP (Un, > fr and Th,((t) > u)
n
14

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
(iii) For all integers n, for any suboptimal node (h, such that Aus vip", and for all inlegers o' > An,(())
(
2n//0 there exists constant C2 1, such that
201ph -Bnn) (2mph-Am.s)
C2t n
PP (Uh,:(0) > I and (T, > v²) E
Proof. The proof follows the same structure as Lemma 16 in Bubeck et al. (201T) and Lemma in Mao et al. (2020).
(i) () is not played during the first rounds, then by assumption (t) oo and the inequality trivially holds. Now focus the case where (t) 2 1. From Lemma 2, we know that fx) & unp", Vo Ph. Then have E (X(,) + [ [(C,,, >
Therefore,
(U,n,((t) & f and (t) > 1)
= -P(mn.() + PIBTT, (t) -a13 + vipp & fr and (1,)())))
-I (Th,(t)) ( (t) (t) (vIp" 1*) < 1b/ (t)) and (t, > 1)
Σ (Y, f
Σ (f(,,) +upp' f*) [(M,,)))CC..)))
< 11 (1))) (1)2-111 a/8 and (1, 21
< Σ - Y.) -X) > (1) and Th, > 1
Since the HOO tree has limited depth, the total number of nodes played in C(h, 6) is upper bounded by some constant L > 1 that is independent of t. Let X denote the j-th new node played in C(h, i), denote the number of times X is played as nj, and let Y (1 & & tÿ) be the corresponding reward the s-th time arm X is played. Then, by the union bound, we have
P
(Xx))
Ys) (((r,,)))C (t) and Tt, >
Σ
P
Σ (xx)) Ya) (.)(((H)))CC)) 2 (1))
Th,(tt==1
Σ
P
MΣ(1(E) (f(x)) Y!) > (1)
Th.((t)=1
f=1==1
f + 1-a/3
Σ
Σ
P
Σ (
> L
Th.a(t) m1 j=1
C1
1-11
where C > 1 is constant depending on C' and L, and in the last inequality we applied the concentration property of the t" > is satisfied,
bandit problem (5). Notice that only use the concentration property when the requirement but when 2 < 1, the incquality also trivially holds because e > This completes the proof of IP (Un.(()) < f*) < C..
(ii)
Recall Definition
15

---

Power Mcan Estimation in Stochastic Continuous Monte Carlo Tree Search
The proof idea follows almost the same procedure as the proof of Lemma 16 in Bubeck al. (201T), and we repeat it here due to some minor differences. First, notice that the defined in the statement of the lemma satisfies n ua/0 + unp² x An.
Then we have
P (UN,,(t)) > f and (t) > u)
=P
(wn.a(t) + n -a/8 a/B +
vip" > fh.s Ana and Th.((t) > u)
(inilt)= > fhis Ah.i up
<P
and (t, >
Ans 11pp
(t) (An,(t)- - -fh,)
(t, and (t, > =u
2
An.i - u1p"
Σ (Y, - ((1,
(t) and Thys > u
2
Σ
P Σ ((YY-((X))) (x.))(x)))(
Dn. v1p
Thall))
2
(h.i(t) mu1+
where in the last step we used the union bound. Then, following similar procedure as the proof of Lemma 4 (defining X and Y and then the concentration property), we get:
1
An.i vnph Tt)((t)
Σ
P
Σ
(Y,
(h,(0)==u11
Σ
C2
(An.-u)) 9
(1,(0)==++1
(Th))tt)
Czt
n
n
(1)=()==++
where C2 is a constant independent of n, and in the second step we used the fact that Th,(1t) u > An.(n)
2/ Anp
This completes our proof of P (Un,(1) > I* and Ti,:(1) > u) <
Cat n
(ii) The proof idea follows almost the same procedure the proof of (ii), and we repeat it here due to some minor differences.
When An. S v1 define
D/.:: == 3vm An.i 2
This inflated gap Ai, is strictly bigger than vip" In particular,
A/.s unp" 201p" An.s 0.
Therefore, 2 ( 2n0 8/a We have n 5/2 /a18 + viph < Ahaturp" 2
3,,, -
Then we have
16

---

Power Mcan Estimation in Stochastic Continuous Monte Carlo Tree Search
P (UU,,(1)> I and (1) > u')
(t) + w a/a + unp" > Sh, + Ah, and (t, > v²)
unp
(n,ll)) > Shis + 2
and (() > u'
Ah, r1p"
(h,(tt) (Pns(t) - -fh >
(t,i(t) and (t,(tt) > ul
2
1
4 v1p"
Σ (Y, - [(.,))[((H..)))) >
(1) and (t)(1)) v¹)
2
1 vpp
Σ P Ev. (X.)
Tr.s(()
2
(1)=
where in the last step we used the union bound. Then, following a similar procedure as the proof of Lemma 4 (defining X and Yj', and then the concentration property), we get:
An,; - VIP"
P
E (x.))
(t,((t)
2
(t)=aa==
C2
3
(t)=a
(Tn)(())
2
C2
Cal
n2
nd
(t)=
where C2 > 1 is a constant independent of n, and the second step we used the fact that (t, > u > Al,((n) =
2/ [(
8-
This completes our proof of P (Un,(t)= f* and (h,((t) u') < St.
Lemma 7. (Lemma 14 in Bubeck et al. (2011)) Let (h be a suboptimal node. Let < k & h be the largest depth such that (ks, it) is on the path from the root (0, 1) to (h, i), ie., (k, (2) the lowest common ancestor (I.CA) of (h, i) and the optimal path. Then, for all integers u 3 0, we have
E [[Tha(n)]] & uu Su+En P P( < fr for some E [k+ 1,....t t- 1}] or [Th,(t)) u and U Un,((t) f+])
Proof. This lemma is stated in exactly the same way as Lemma 14 in Bubeck et al. (2011), and the proof follows similarly. We hence omit the proof here.
Lemma 8. For any suboptimal node (h, i) with An,i v2ph and any integer > there exist constants C1, C2 1, such that:
5/8 Dns viph
C2
E [[nn((n)] <
+1+ b-3
Proof. Let Ans(n)= =
[
2n 2/8
Then from Lemma 5, we know that
17

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
E [T)] & (n)(n)) +
Σ
(TT,,((t) > An.(n) and (n,(t)) f*) p (U)
(m)+1
By replacing the right hand side with the results from Lemma 4 and Lemma 6, we further have
Czt
t-1
Ci
E [Tn,(nn)] & An,(n)) +
Σ
+
Σ t
n
tm
An.(()++
s=l
C2
C1
< An.(n) +
pb- dl
nh
u
g
8/8
C1
+1+ C2
Ahii u2hh
b-3
This completes our proof.
Lemma 9. Let (h, i) be a suboptimal node such that An,s > v2p" Define
(
2n 2/ 6/8
(n,(
Aiit - 1/ pm)
Then for any integer n > and any integer
(n,(n),
there exist constants C1, C2 such that
Ci (u 1) 3-b
P(Th,(n) > u)
C2
+
b-2
b-3
Proof. The trivial case n < u. If n I u. then (n) is at most n, so (Th,i(n) > 4n is the empty event. Hence, ((T)..()) > u) = 0, and the inequality holds trivially.
The main case > u. We now assume n > Our goal is to bound P[Tna(n) > u.. We will do so by introducing two events and applying union bound argument.
Monotonicity of B-values. Recall that (f, is defined (in the HOO/HOOT algorithm) so that descendants of (h, i) always have a B-value at least as large as (t). Hence, along any path from the root to leaf, the B-values are non- decreasing with depth.
Defining two events: Let S le h-1 be the largest depth on the path from (0, (h, i) such that (I: it) is on the optimal path. We define:
E1 = For every E [u, n]. Bt.a(t) f or Th,((t) S An,(()) < u).
Eg {For & E n), BE41 (t)> st).
E₁ means that whenever either the local upper bound (t, is already S f* or else Th,i(t) has not exceeded (t).
Eg means that for every E (u, n), the node (A: + 1, ( on the optimal path has B-value strictly greater than f*.
18

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Key claim:
F n Eg _ (T,)()) s u).
That is, if both Ej and Eg hold, then (n) u.
Reasoning:
If at time E [u, rt] we have (t, S f* and the ancestor node (k + 1, (2+1) satisfies B,+1.1 (t) > f then by the monotonicity of B-values up the path, the algorithm would choose (A: + 1, (2+1) rather than (h, Hence, Th, does not increase.
If at time t E [u, n] we have (t) & (t,(t) < u and Bx-1 (t) > f*, still possible that the algorithm enters (h, i) and increments Th But even if so, (1) remains below u. Iterating this argument up to time n shows (n) I u.
Hence, whenever Ej O Fg true, we cannot exceed plays at node (h, i).
Completing the union bound:
(n) > m} S Ei ES
(T) > w) S I(ET) + 1(E)).
So suffices to bound P(E)) and P(E))
Bounding P(Eg). By the definition of B-values,
BRt1, (f) S {UL+I. (t) s f*} U B242. (t) S 8³}.
and iterate this argument recursively up the path. Using union bound across times [u, n), obtain
P S PC s f*)
t=
By a known concentration argument from Lemma 4 (i), we have PPU,.,;(t)) S fr] Cr. This yields a tail-sum of order f (b-b1) dl, which is proportional to (u - 1)3-b.
Bounding P(E)). Similarly, (Ba,i(t) f" and Tt,s(t) >
(t)) be bounded using the arguments from
Lemma (ii). We apply union bound over E [u, and note that ((U),((() > I" and Th,s(!) > An,(()) S Cat yields bound in terms of
Summing from
Putting all together: Combining these bounds gives
19

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
(n), > u)
+ (3 P n), (t) f and (t) > (t,,(t))
nu, 1k 8*)
< P [u,n] n|. (t) > f* and (h, > (t)
+P E [u, n|. Un 1 1 (t) < f or U242 (t) E f o.. or (t)
P (t) > f and (t) > At)(t))
P (Untlit,, (t) & f or Uk+2.14 (t) f* or or U(-1a; & 5*)
P (Uh,,(t)) > f and (t) > An,(t)) +
P (U),)(t)& <
1=
Czt
n
C1
C2n
C1
p-
n
1-1
n
t=
ua-1
Cu 1)3-b
+
h-2
b 3-3 3
This completes the proof.
refinement for 1 < S n. Finally, if S n, then one can derive slightly sharper incquality:
C2 (2
C1 (u 1)3-6
(TTh.())) > u)
n
3
by noting that _ S ( for 1 < u < n. For u > the probability is trivially zero because Tn,;(n) S < u.
Conclusion. Hence for every integer n 2 and u (n..
Ci (u - 1)3-b b b-3 3
C2
P(Th,(n) > u) 5
+
n b-2
This completes the proof.
Proof of Lemma shows one of our contributions since there could be the case where Ar,i f - -hi S 1 upp
Lemma 10. Let (h, i) be suboptimal node whose suboptimality gap satisfies
Ani - I v viph.
Define the inflated gap
S/.t = 3v1 p² - An.--
Then for any integer n 2 1, let
(n = [3>2,-00
2n0/0
)²1
67
[[(
2n b/0
2 p ph- An.
Then, exactly the same probability bound from Lemma hhold for (h, f). In particular, for every integer u 2 (n) there exist constants C1, C2 > 1 such that
from
C1 (u - 3-b
C2
(TT,(()) > u) 5
n 5-2
1- 3
20

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Proof. We begin by recalling that Lemma 9 (the "original" statement) requires An,s 11ph Its proof yields, for any (n.;
P (1) > u| <
C2 nb-
C1
uu
3-6
+
b
where
An,((n) =
[
2n4/3
Inflating the gap. Assume now that An. I vip². Despite Ar, being too small for the direct application of Lemma 9 note that (h, is still suboptimal, so Ji, 8 A standard approach Bubeck et al. (2011) is inflate the gap. We define
A 321p" Ah.
Since An,; S usp², it follows that A 2 201 p² > O.
New threshold A/,, (n). Analogously to (n) in the lemma's original statement, we define
(22 = (2
An,((n)
2n0/
-
2/a Dh.
Observe that Ar,; v1p" = 2 21p² A (which is still positive). Thus, we effectively have A/,; 11pp > 0, which is the precise condition used in Lemma
Reusing the same concentration argument. In the proof of Lemma the gap An,i - -uph > appears in several places control event probabilities of the form {U), f*} (T) > u). Now, by swapping in An, for Ar,i we 2 - An,i > 0. Hence the original union-bound arguments hold exactly as before, except that
get A/,; - p pd = the threshold (n) = n Lemma (iii) instead Lemma (ii).
6/8 / (An,s )) is replaced by [(2n// / un )^) and we use the result of
Conclusion. Therefore, even though An,s S m1ph was initially out of reach for Lemma 9 the inflated gap An.s 3v1p" An.s > pM ensures the same tail bound:
C2 b-
Ci (u (1)-1)
PP (T),, > n'1 <
Vu 2 (n)
b-3
Thus Lemma 9
extends directly to the suboptimal node (h, i) whenever An.s S 12ph
F. Convergence of Stochastic-Powez-Ban
n Non-stationary multi-armed bandits
Section Overview and Lemma/Theorem Functionality: This section establishes the theoretical foundation for power mean estimation in non-stationary continuous-armed bandits, which forms the building block for the full MCTS analysis. Lemmal| II provides a concentration bound for optimal arms by partitioning the probability space and controlling how often suboptimal arms are visited, establishing that the optimal arm's empirical mean concentrates around the true optimal value with polynomial tail bounds of the form P(JJk= "Talh"""TTTaaa Ta- f*1 8) Σ ((.,)))()))))))) (mT,,s(n) P(Th,))))))))) >
Ann) + 1) + - (K An) + 1)-a+1 Theorem 1 (from Mao et al. (2020)) serves as the foundational result for enhanced HOO in non-stationary settings, proving both convergence and concentration properties for the average reward with polynomial rates-this theorem crucial as it provides the base concentration guarantees IP() Σt= Y,
f*1 > E) & C'n-a'e 3- that our power mean analysis builds upon. Lemma 12 derives fundamental decomposition inequality for the power mean estimator, showing that the deviation from the optimal value be bounded by [f((p) l/p,, which essential for analyzing
f*1 < E(h.)) fn) (m.).T... + 2(E n how errors propagate through the power mean operator. Lemma [3 establishes concentration bounds specifically for the optimal arm within the power mean framework, demonstrating that the contribution of the optimal arm to the power mean
Tr,,(n) (f..A.T...(n))
21

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
concentrates appropriately by combining visit count bounds with the underlying concentration properties. Lemma 14 provides the most technically challenging result, analyzing concentration bounds for suboptimal arms under three different parameter regimes (depending the relationship between the power parameter and the concentration exponents a, (), showing that suboptimal arms contribute negligibly to the power mean with high probability through bounds of the form C(A(n)* n + b-3 + (concentration terms), Finally, Theorem 2 synthesizes all these components prove that the power mean estimator itself concentrates around the optimal value at polynomial rates 1- b-3
P( (Ta,(()) ([, - >
C2
K-1
(P( f with = 1+d'+ and 3' b=3 establishing the key theoretical guarantee that enables the extension R-000
2
to the full MCTS setting-this this theorem demonstrates that power mean aggregation preserves the polynomial concentration balance through the power parameter p.
properties while providing the flexibility tune
Here the details for each Lemma/Theoren with full proofs.
(
Lemma 11. Let (h denote any suboptimal node with gap Anss >> vsph. Define Anz(n)
2n
An.
(
Let (P) denote any suboptimal node with gap Awiy & unph. Define (o))
2n
and let
2010t Awa
A(n) max { (n), (n)) Assume there is a known constant R such that R 2 E n aa/3 Then, for any optimal node (10,0)) (i.e. A 0), we have:
Phess (m) - 1n1
Σ
(Tnn(n)
> A(n) +1) +
8 8 12
(K - 1 + 1) -a+1
a
((t,5))
Proof. Partitioning the event. Let
8= Σ
1) Tha(n) (K - 1) (A(n) +1)m
(h.i) (1e,))))
Observe that:
PP -T I P(E) + H( and | Tw)) -f 2 2
Σ
P ([T,,(n)) > A(n)+ +1] + D1,
(1e,)
where we used the fact that {E} C 30 (Tn,((n) > A(n) + 1), and we denoted the remaining probability
1)) Dr P Σ Tha(n) S (K-1) 1) (A(n) + 1); ( The, (n) s*1 2
Bounding D1. On the event (E (M+,))))))) Thi(n) & (K - 1)(A(n) + +1), we have
(
Th- (n) n
(na(n) 2 n 11 (K-))(A(m) +1). (h,a) o (1+,50)
Σ
Hence
D1 T (n) 2
-K (A(AA)) +1) and -
Applying the union bound in time, for
E n - (K - 1)(A(n) + +1), n).
we get
n t= (K (1((())+1
D1
22

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
By the given concentration property (namely
0. each term is at most ct g- Summing yields
D1 & CE
t
t=n (K (A(()++))
Because a > 2, this tail sum can be bounded by an integral:
(u (u-1) 1)-1) 1)
Σ
ra a
< x dx
1-1
a-1
Taking (K- (()-1(((m)) completes the bound:
D1 < c (n (K - ()((m)) +1) - 1-a
--1
Recognizing (n- (K -6) A(n) + 1) up small adjustments gives the simpler form
D1 s E 8 (n (K - 1) A(n) + 1) -a+1
Combining the pieces. Putting this together:
(m)
Σ
P[Th,(n) > A(n)+ + +1] + D1
(h,i) (h*
Σ P(Th,(n)> A(n)
+
- c g-
c
n n- (K - A()) (1)))((m)+1 -0+1
(4)
((
Hence the statement of the lemma follows.
Theorem 1. (Theorem 2 Mao et al. (2020)) Consider a non-stationary continuous-armed bandit problem satisfying prop-
erties (4) and (5). Suppose we apply the enhanced HOO agent defined in Algorithmss 2 and with parameters satisfying
a(1 8) & < a, 3, and pd <n Let the random variable Y, denote the reward obtained t. Then the
following holds:
A. Optimal-arm convergence: There exists some constant Co 0, such that
Co n2
Y
f
<
(6)
n
where < <<< 1td' B. Optimal-arm concentration: There exist constants C' > 1,8' > 0, and 1/2 & v/ < 1, such that for every 2 na/8 and every integer > 1
1 7
E C'n a''
where a'
1- b
6-3 B' (b 3)/2. and C" > 1 depends a, 3, n. and H.
1+d'+
23

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Lemma 12. Let (v) be the power mean estimator defined by
Tn,)(n) Unarinncoo"" for p 2 1.
Pa(p) =
(h,4)
Then, for all p 2 1, the following inequality holds:
(P(()) l R T
Tha(n) -nasrammol + 2
E
Thae(n)
IInsthate) - ( shis!")
(5)
"
(1.,8)
(1,,6)
Proof. Setup and Notation. Since S' = (0 we know that IhsTIas() S Shys + [InAATanto) Shall Furthermore, by definition of (P()), we have
Pn(P) = Σ (m) (nasan v
Dh.a(n)
[Shx + -
n
(h,1)
(h,3)
Bounding fn( f*. Because f 2 fiis for all (h, we write:
(x(p) 5 (p))) - Tma(n)) l /n ni/v (h.5)
Σ (n)((n) (faaTaanm)))))
Σnn
Tn,((i) (fh (Fha)") 1/0
ni/o
(h.5)
(h.i)
Applying Minkowski's inequality (together with the fact that Inn Shis 1InAAtTi..
Si,l), one obtains
1/p
(n(e)) 1
Σ
Th,( PnxtTatn Shall"
n//p
(h,s)
Bounding f - (p). Similarly, we can write:
lr Fa(p)) = [ n f.(lo)] = - n Σ
(n,( Sh,s +
E Ins(n) Sn(oo]
(h1,3)
(h,6)
Ein,o Thiiln) si.
Observe that E(ne)) Ta,(u) fhys S E(na)) Thatt)) (Fr.)P] n
1/p
since the power mean is non-decreasing in p. Also we have
Fh,s < PhaTTniln + -1.,,,Thha(m)) Shisl And
Σ Tna(n)) - Shhll S Σ This(n) (PaATh.. Shall + Imaa(n) - PnA.Ia..m) (h.a)
(h.4)
(h,
Thus, a straightforward rearrangement yields
f - Fp) I 1 Σ Tn)(()) PRATT..) - fhael +
1 Σ Tni(n) ProeTh
(h.
(h.5)
Σ Th)((n) (FusiTaneo) + | - Rhsl)
Ina(n) (Fassaat)) 1/p (h.))
//r
(h,))
Th (n) Pratthadtn) Shaal + 1 -
(hai)
(h.))
1/p
Tn,((n) [n.s.T..in) - Sh
-/v
(h..)
Σ
Tha(k) PrAIIalt) - shiel +
2
Σ
(ha(()) PPATTh - shal" 1/p
n-/p
n1
(h.3)
(hr))
24

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Combination. By combining (+) and (**), we immediately that
[((()) -M
[s Ih.sIa.im) + Σ (h,4)
Th,i(n)
[aasTha(00 - shal")
(h.4)
which establishes equation and completes the proof.
(
2n0/a
Lemma 13. Let (h, i) denote any suboptimal node with gap Ans > usph. Define Ans(n)
Anii-upph
(
Let (h, denote any suboptimal node with gap Awie & vip". Define Ao
(2 Aun and let
2n
A(n) = max { (n)( Ale (n)) Assume there is known constant R such that R 2 E 2 n 0/8 Let us define
(h","" as the optimal node. We have
Th Th-,x (m)
-
f-1)"² cP
C2(K 1)
P
<
(6)
h-2
Ci(K - -1)A(n33
(n (K ())(())(m))))))))))))))))))))))) + 1) 1
b-3
Proof.
Applying results Lemmal 11
we have
K
Th - =))<
Σ
(TTn,(n) > A(n) +1)+
5 (n - (K - 1)(((m) - 1) - 1) -a+1
a-1
(1),)))))
F12
F11
(8)
{
27
2n
From the result of Lemma and Lemma 10 with > we have with A(m) +
and A(n) +1 >
(
2/0/88 Abis
Then
- 3 A(n)-(0-1)
2cC-8 -
Fi
Σ
P (n), > A(n) +)
Σ
b
(h.0)( .2)
(h.0))(h* .P)
that concludes the proof.
b/8
Lemma 14. Let (h denote any suboptimal node with gap ANs > v.p². Define An,(n)
Ahii
Let (h',i) denote any suboptimal node with gap DNee & vip'. Define (nr,e(n) =
and let
Ayr &e Then for any e satisfying R 2 2 n a/8 there is some constant No such that for all 2 No. the following three statements hold:
A(n) -max { An,
25

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Case 1: 1 S p S 2 and S 2. n. or E) such that
For every suboptimal arm (h, there exist constants C1 C2,C (not depending on p
8
BhilThamm) - -hai > x 2²)
2
C2
AI 3-b
2c(K 1)
1 (a 2 = (A(n) + +1) 11--1a1))
n 6-2
b-3
Case 2: p > 2 and 0 < a- < 1. For every suboptimal arm (h, 1), there exist constants C1, C2 > (not depending
on n. or E) such that
C2
C1 A(n) 3-b
+ c(K - 1 - 8 (A(n) + +1) -(a-1)
[n) (hATTa, - Shall K-I 2¹)
+
a
n b-
b-3
1 (a 2) p
(10)
Case p > 2 and a
L > 1. For every suboptimal arm (h, 1). there exist constants C1, C2 > 1 (not depending on
n. or such that
p Th.(an) (PaATh.dd)) - Shil' R-T x0) 1
C2 b-2 b-3
Ci C(A(n)
c(K 1) (a 0 (A(n) + +1) - E 8
p
+
a
(a - 9)
(11)
Proof. A higgh-probability tail bound for Tn, By Lemma 9 and Lemma 10 for any suboptimal arm (h, i) and integer
ann
A(n), there exist constants C1. C2 > 1 (not depending on n or E) such that
C2
Ci (u - 1)3-
P P[Tna(m) > u] <
+
b-2
b b-3 3
Define the events E = { (n) > A(n) + 13 and = = { (n) S A(n) +1]. Hence,
P (n)
1 Ir.ATTh,(n)) - Shis 1
k-1 < F(Tha(n)= > A(n) +1
(12)
6
+ IP (h,((n) S A(n) + Ta,(m)
Fns. - -fi P
c"
(13)
K-T
From Bounding From the tail bound above, we know
C2 G = ([Tn,(n)) > A(n)+1] S b-
C1 A(n))- 3-b
+
b-3
Bounding G2. Under the event (n) S A(n) + 1}, we have (n))(n) S A(n) + 1. Thus
A(x++1
t Fruit
1
G2 <
P
fhn K - 1 c
1=1
We can see that with & A(n) + 1, we can find No such that Vn > No.
E> E n 3, Therefore,
(K-1)
A(1)+1
1
A(n)+1
-
G₂ <
Σ
P
(Pinss- - Siri >
n
<
Σ ct
t(K - 1) [[(K1]
n
E
(14)
t(K - 1)
1=1
1=
A(1)+1
Σ
c(K 1) (a- -)
(15)
26

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
We study 3 cases:
Case 1: f v 0, which can only happen if p < 2 because a < g. and actually when a < 2 we just need < p
< 2.
p
then
G2 E c(K - 1)88 nn (1 Alm)t
1 -1a-5)dt (A(n)) +1)- )
1 [a- )-1
A(x)+1
=c(K- - 1)08 nn :
+ +A(n) + 11
(ax 2 +1 +
+ C
(A(nn) + 1) 1)) +)+1
< <cK-- - ( + +)-
1
+ (A(n) +
+A(())+))-01 (a-
-(a- +1+1 +1
-(a 2) +1
Because -(ar - () + ++>> 1, we can find a constant N₂ such that Vn > No. we have
1)-E G2 & 20(K - 1) (A(m)) + +1) 2 (A(n) + 1) (a- 9-4
2c(K - 1) 8
5 (A(n) + +1)-(a-1)
-(a 8 +1 -(ax () +
Therefore, we have
(n) P
(PhnsThhto)-fff ))² > n
1 Re²)
C2 C2A(n)3~b
2c(K - -
(A(n) + 1a-11)1)) (16)
& n- +
b-3
+
-(a 3) +
E
p
that concludes for the Inequality 9
Case 2: a- > 0, which can only happen if p > 2 because a & S. We have
A(x)+1
A(n)1
{a- 11
A(n)+1
t- (a- 2)
1++
(a (a- 100== 1
+ C
(a 8 ++1
(A(n) + 1)- (a- 11+1
(a
8) p) +1 1
(a - ) +1
0
(A(n) + +1) +1)-(a-g)++
8
(a () -1
p
so that
g a
(A(n) + 1)
1)- -aa -aa-E)+ B)+1
G2 & c(K - 1
p
E pn
(a 2) 1
a
p
(A(n) + 1) (a- 1)- D)+1
2
= c(K 1)
E
(A((n) + +1)-2.
1 (a - )
(a
2
0 < a
< 1, then we can find a constant No2 such that Vn > No2, we have
G2 < c(K - 1) 2
c(K 1)
8 + ())
8 (A(n)) + +1)-(a-1)
1 1- 5)
1 1- (a )
Therefore,
p
Tha(n)
(Ihsttatns - l7,))² -Sa))²
1 x00)
<
C2 CIA()33b
+
b-3 +
c(K - 1)
(A((n) +1)-(a11) (17)
カbー
1- (a 2)
n
27

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
that concludes for the Inequality TO
Case 3: If a
1, (p > 2), find a constant No such that Vn 2 No, have
a e
(A(n) -1)-(a-())) - -1
5)+1 (A((A))) +1) c(K - 1) 6)
G2 c(K cc(K
(A(m)++)]))))
2 -1 (a
(a ( -
P
p
that concludes for the Inequality 11
(in((n) (Jasth..t) Sine
C2
CIA(n)
cK - 1) (KK-))((6
+ & (A(m) + +1) (18)
P
n
K
nd-
b-3
(a
Conclusion. Combining the estimates for G1 and G2 completes the proof in each of the three parameter regimes.
Theorem 2 (Power Mean Concentration of (x)))) For a [K], let (fan)nx1 be a sequence of estimators satisfying
fh, and let f max, (h Assume that the arms are sampled according to the strategy following Algo- rithm with parameters a, b and C. Assume that p. az 3 and satisfy one of these two conditions:
Pa
0.,3
(i) 1 <<pp? and a < _ 2
(ii) p and
2 <1 p
If (1 2 < a then the sequence of estimators (p) satisfies
Pn(p) d' f
aor 1- b-3 b-3
l+d'+ 2,,
Proof. As the results from Lemma 12 we can derive
P2(p)- -
(h)(n)
PhosTammo + Σ
Tn,((1) (h,8)
| - Shi 5
n
(h,4)
+ *P -P(ff()) -0 fr| -1+22++)))
< P
Σ In, -Pot.hnim 3E
n
(h.,)
Σ Tha(n) (h.s)
(Jhnstantn) - Shaee -fac))
> 22
B
Bounding A: with x. > 1 We have
(Lemma
O'n C'n--a a -
28

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
where a' 1+d'+
b-3
,8==
B-3
and C" 1 depends on a, 3, n, and H.
Bounding B:
The(n)
(Fansthaate -Fhe)) 20
B = P Σ
n
(h,,)
(fr - Sh 1)= 3 E
K
Th,((n)
li.e)² >
1
<
P
K - s
T
n
(Ro)) R*)
With F): According to Lemma 13 we can find constant No. such that Vn E No, we have
F (2(K-))
Ci(K - 1)A(m)3~
= (n (K (a(m)))(+))))))) 11
(19)
b-
b-3
With Pz: According to Lemma 14
we can find a constant No, such that Vn > No. we have
With < 2
we have
C2
GA(n)3-b 2c(K 1)
F2 < n b- +
8 *-((A(m) + +1)-(--1)
(20)
b-3
(a p
With p 2, and
2 < we have
p
C2
Cj(n))-b
c(K - 1
F2
n1 b-2 +
-A(m(((m) + 1a--1)
(21)
b-3
-(a - 2 +1
So that
B F1 + Fg <
C2(K 1)
+ Ci(K 1)A(n)3-b
C
E - 8n (K - 1)((n)) + +1) 1)
-+1
(22)
n-
3-3
a-
C2 C/(n)3-b
cK 1)
(A(n) + 11 (a-11)
+ b-2
b-3
-(a 9 +1
where 1 < 2,a <
2 orpp 2, and
< l.
Because b - < 1,
E R. and A(n) ((nb/a) so that find constant Np such that Vn > Np
B CK 8 A(n) (0-3)
CKR (
(23)
b-3
b-3
with C' is a constant depends on C₁, C2 C1 C₂ K. Combining the two parts 7 and 23 we have
+ (fm()) r > 2 & C'n-'' + C (00))-
b-3
1-6 b-3 8¹ -33 and C" depends on a. B, and H. So that EC > 1 depends on a, B, n. E and 1+0' 2
where a'
H such that
= p ((īn(t)) - > 2) < a'n-a'
29

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Furthermore,
Fm(p) f-11- / P ((Ent)) -f- - }5)
lim 700
B[fn(p)]- -
lim n0
n lim
ds
(o en s ds v
< lim 100
lim
1ds
lim
en 8 ds
000 1
lim én-d (5-9'++ +C) 1,- 0( we need 8 > 11>8>22
100
Therefore,
(P(P) a' fr
that concludes the proof.
Remark 2. The conditions on p. B, b, ensure that the polynomial exponents a', , ferived the union bounds remain strictly positive (with 3' > 1) and do not degenerate. In particular, requiring a > 2 ensures that one can integrate the tail probability f ee de for large E.
G. Convergence of Stochastic-Power-Bae
in Monte-Carlo Tree Search
This section extends the bandit-level concentration results to the full MCTS setting, establishing polynomial convergence guarantees for the complete tree search algorithm. Theorem serves as the central theoretical result of the paper, proving through mathematical induction that both value function estimates (sa) aa.le (sa) and Q-value estimates (n a) cha+3.00+1 ((sa, a) concentrate polynomially at every node in the search tree. The proof establishes the base case for depth = 1 by showing that leaf node estimates concen- trate via i.i.d. rollout averaging. Q-value estimates concentrate through Lemma [ (which handles stochastic transitions), and root value estimates concentrate via the power mean concentration results from the bandit analysis. The induc- tive step then demonstrates that these concentration properties propagate upward through the tree: assuming the theo- rem holds for subtrees of depth D 1, the same concentration arguments (Q-value concentration via stochastic Bell- man backups and value concentration via power mean aggregation) establish the result for the full depth-D tree. The- orem 4 (Convergence of Expected Payoff) provides the final convergence guarantee for the algorithm's expected per- formance, proving that [s)]] V(5)) < (nn where
Section Overview and Theorem Functionality:
(0, 1/2) represents the polynomial convergence rate. The proof employs Jensen's inequality to bound the expected absolute deviation by the tail probability integral Jo P((V,,
(so)l > s)ds, then uses the polynomial concentration bounds from Theorem to evaluate this inte- gral, yielding the final rate - where the exponents are determined by the algorithmic parameters. Together, these theorems establish that Stochastic Peweeicc-------eeeee HOOT achieves same polynomial convergence rates as POLY-HOOT deterministic settings, but now extended the significantly more challenging stochastic continuous-action domain.
Here details proofs for each Theorem.
Theorem 3. When
apply the Stochastic Stochastic-Power-Hoor Power--oor algorithm, with algorithmic constants
(ba) faald (Ba)2 satisfying the conditions in Table 1 the following hold:
(i) For any node sa at depth d E {0, (0.1..... D} in the tree,
(s() aa (su).
(I)
n-000
(ii) For any node sa at depth d E {0, (0,1...., D-13 in the tree,
()) Callndai1 (ss,.a), Va Aog.
(2)
Proof. We prove the theorem by induction on the depth D of the tree.
Initial step:
30

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
The root node state is sy. Let denote by r' (so, a) the intermediate reward time-step I, collected from playing (80, a). Then the system transitions $1 ~ P( so, a). We let ((5o, a) be the mean reward of (So,a).
Recall the definition of ((s0. a):
a)) = r(su. a) + 7 E P(s2 so: a) ((1)).
FLES
where (ss) the average value of the rollout policy To at state $1, and Aso is the of feasible actions so (with
cardinality M). The transition probability is P(s so,a).
Claim (7) in the statement says that for any state with depth I in the tree,
(si) -. V(s)).
Indeed, (si) is just the average i..d. calls to the playout policy To starting at 81 Hence (3) follows by straightforwaar i..d. argument.
Next, from the definition of Qn. we have
(50. 0)
as). + y (o)))
(24)
n
where Tht (1) denotes the number of times we have visited (so, a, 81) up to time I.
By applying Lemma 1 with X, r (8p, a) and probabilities p (p1. -01.-..,PM.. .MM) capturing the transition dynamics from (so, to possible next-states, conclude that
(m.
03 ((50: a), Va Aso.
(4)
This yields part (ii) of the theorem for the depth-zero node (i.e. the root).
Finally, for the value function estimate (so) depth zero, recall the polynomial concentration result from Theorem) (indeed it follows "power-mean" or similar argument), plus the definition
Va()
Σ aEAmm
(m)
[ (80
(25)
Thus,
(s0)
og: 8o ((so),
with ao, fo satisfying the conditions in Table Together with (s1)
((s) for leaf nodes, we conclude that 3
statement (i) of the theorem is correct when the tree depth is 1. Statement (ii) is correct as well by equation
Inductive step: Suppose the theorem holds for trees of depth D-1. We prove holds for tree of depth D.
Consider the root node state 8o. When select action from 8o, it transitions 81 P(( so: a). The subtree rooted 31 has depth D-1. By the induction hypothesis, for any node sa within that subtree (i.e. at depth 2 1), we have
and (ss), d d..,,,, (sa)
n-050
and
Qn(sd,a) 00-1- ass, d D 1
n
31

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
Hence, repeating the polynomial concentration argument in the base case but substituting V from deeper levels, obtain:
(S0
(sa. a), Va Aso
(5)
Then, applying again Theorem
2 (or power- argument) to the root node's value function
(n)
1/2
(s0)
Σ aE.A.0
we see that
(s0)
Gia S0
V(so),
12-+000
with op, 3o as per Table Thus statement (i) follows for the entire tree of depth Likewise, combining On results from (5) with the induction hypothesis yields statement (ii).
By induction, the statements hold for any node in any tree of depth up D.
Theorem (Convergence of Expected Payoff). We have at the root node so, with the best possible parameter tuning that
E[Vn( - < OO(
where Ç E (0,
Proof. Using the convexity of (x) |a/| and applying Jensen's inequality we have
[s0)] ((s))
< B B [so)] (so)] - ((s))]
P ([n()))
V > s) ds
20 Ag
too
1ds
+
Cym
000 g -u
Jn
80
s 86+1
+
< n
+ Con
00
30 + 1
20
Pd
C0
+ 1)n
80
Because 0 < <<<=
by 3
(Theorem 2), then the best possible rate we can estimate is
1+
(so)l - & <0(
where Ç E (0, 1/2), that concludes the proof.
32

---

Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
H. Experimental Setup and Hyperparameter Selection
We evaluate Stochastic Ceochhssic-Power-reee Power- HOOT on both classic control tasks and high-dimensions robotic environments, all adapted continuous-actinn stochastic settings. Our experimental design addresses the key challenges of planning under uncertainty while demonstrating the scalability and robustness of our approach.
Environment Modifications: We create stochastic versions of standard benchmarks by introducing noise at multiple lev- els: (1) action noise via Gaussian perturbations to selected actions, (2) dynamics noise through random perturbations to state transitions, and (3) observation noise by adding Gaussian noise to state observations. Additionally, since power means require strictly positive inputs, we apply reward transformations of the form max(0.01, (r offset) x scaling) while pre- serving optimal policies.
For classic control tasks from OpenAI Gym Brockman et al. (2016), we evaluate on CartPole, CartPole-IG (increased gravity), Pendulum, MountainCar, and Acrobot. In the standard CartPole problem, actions are discrete, taking values in {-1,1}. To enable continuous control, redefine the action space 1-1, 1]. CartPole-IG features increased gravity of 20 (up from 9.8), while Acrobot uses gravity of 30, maintaining other OpenAl Gym parameters. For high-dimensional evaluation, we test on MuJoCo robotics tasks including Humanoid-vO (1 (17-dimensional action space, 376-dimensional state space) and Hopper-vO (3-dimensional actions), both modified with comprehensive stochastic noise.
Baseline Comparisons: We compare against four established continuous MCTS methods: discretized-UU Kocsis et al. (2006), Progressive Widening (PW) Auger et al. 20133). HOOT Mansley et al. (2011). and POLY-HOOT Mao al. (2020). We also include Voronoi MCTS Kim et al. (2020), recent method designed for deterministic continuous spaces, to demonstrate the challenges of applying deterministic methods to stochastic settings.
Experimental Parameters: Across all tasks, we use a reward discount factor of ? = 0.99 and planning horizon of = 150 steps. The MCTS search depth set to = 100 with n = 100 simulations per state. In discretized-UCe actions are discretized into 10 uniformly sampled values. For HOOT and Stochastic Secchaasstc---eerrreeeeeee Power Power-HOOO,, given action space dimension m, we set p = 1 and 1/1 4m. In Stochasti cewesttic-oweeeHH-e- we configure HOO tree depth limit
1t
to H- = 10 with parameters b = 5, 20, and = 10. All algorithms use rollout policy To initialized as (ss) 0 for all states s E S.
H.1. Progressive Widening Parameter Selection
We tune environment--peecfie PW parameters (o, k, c) following:
Acrobot: a=0.6, k=2.5, c=1.2 (timeseries strategy)
MountainCar: 0=0.55, k=2.2, 1=1.3 (momentum strategy)
CanPole-IG: 0=5.5, k=2.0, c= (adaptive strategy)
Pendulum: a=0.45, k=2.5, c=1.1 (optimistic strategy)
H.2. Practical Branching Factor Analysis
Our empirical analysis shows that despite theoretical maximum branching factors of 2D, practical branching factors remain efficient:
Average branching factors: 1.86-2.17 across different power values
More than 95% of nodes have only one child
Branching concentrates at key decision points
Power mean backpropagation causes algorithm to focus on promising regions
balance, with the algorithm thoroughly exploring promising regions while limiting resources on less promising areas.
This demonstrates effective
33


Reviews:
[{"review_id": "mQr3sAZpXJ", "reviewer": "Reviewer_Excm", "summary": "In the setting of continuous state/action MCTS, this work proposes replacing the empirical mean node value estimate with a power mean-based estimate. They also propose a tree action selection bonus based on this power mean. They provide convergence proofs for this method in the setting of stochastic MDPs, and show empirical results on 5 continuous control tasks.\n\n\n## Update after rebuttal\n\nThe rebuttal addresses almost all of my significant concerns, so I have updated my recommendation.\n\nMy one reason for not choosing a weak or full accept recommendation is that I cannot say I understand the action branching behaviour, despite two author responses. I understand how the power mean focuses search, but cannot see how that affects lines 183-190 of the algorithm: a previously unselected sub-interval **must** be chosen each time the HOO tree is queried, other than when the HOO tree node is at max depth.\n\nThe node statistics are a bit difficult to understand, because the method takes an unusual approach to MCTS: **multiple** MCTS leaf nodes can be added during one trial, up to the specified max depth. In the tree structure analysis, very few nodes have a branching factor >1. This suggests to me that the algorithm may be behaving more like a flat Monte Carlo evaluation than MCTS with meaningful branching factors below the root node.\n\nI appreciate I am the only reviewer to query this, so would not push for rejection based on my not understanding this action branching factor point.\n\nRecommendation after rebuttal/discussion: weak reject.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We address each of your concerns in detail and kindly ask you to consider updating your scores after reading the rebuttal.\n\n## Experimental Design\n\n**Higher-dimensional tasks:** We added results on Humanoid (17D action, 376D state) and Hopper (3D action) with added noise to action, dynamic, and observation. For both envs, we incorporated heuristic physical knowledge of the robots during MCTS rollouts across all algorithms to improve sample efficiency:\n\n| Algorithm | Humanoid-v0 | Hopper-v0 |\n|-----------|---------------------|-------------------|\n| UCT (baseline) | -136.98 ± 44.84 (1.0x) | 5216.93 ± 179.64 (1.0x) |\n| POLY-HOOT (p=1) | -44.40 ± 3.33 (3.1x) | 13230.66 ± 2844.33 (2.5x) |\n| **Stochastic-Power-HOOT** | **-44.12 ± 6.22 (3.1x)(p=2)** | **13348.45 ± 6110.36 (2.6x)(p=8)** |\n| HOOT | -57.35 ± 10.46 (2.4x) | 10452.83 ± 3885.12 (2.0x) |\n| PUCT(PW) | -89.74 ± 24.16 (1.5x) | 5218.73 ± 1384.90 (1.0x) |\n| Voronoi MCTS | -48.69 ± 9.52 (2.8x) | 411.70 ± 29.03 (12.7x worse) |\n\n**Voronoi MCTS comparison:** We added Kim et al.'s Voronoi MCTS (AAAI 2020) to our experiments as you suggested. This recent algorithm uses Voronoi partitioning for continuous action spaces. Interestingly, it performs well on Humanoid (2.8x better than UCT) but poorly on Hopper, highlighting complementary strengths of different approaches.\n\n**MountainCar dimensionality:** We will correct this to \"low-dimensional\" (2D state, 1D action).\n\n**PW parameters:** We tune environment-specific PW parameters (α, k, c) following Sunberg et al. (2018). Each environment has tailored values and action selection strategies based on its dynamics:\n\n- Acrobot: α=0.6, k=2.5, c=1.2 (timeseries strategy) > (77.86±0.00)\n- MountainCar: α=0.55, k=2.2, c=1.3 (momentum strategy) > (-0.025 ± 0.004)\n- CartPole-IG: α=0.5, k=2.0, c=1.0 (adaptive strategy) > (75.80±11.84)\n- Pendulum: α=0.45, k=2.5, c=1.1 (optimistic strategy) > (1315.89±85.43)\n\nWe will add to the revised paper.\n\n**HOO tree depth:** We will add an investigation varying H from 1-20 and report performance.\n\n**Reward scaling:** Power means require positive inputs. Our reward transformation `max(0.01, (r + offset) * scaling_factor)` preserves positive and ensures fair comparisons by applying same scaling to all methods evaluated.\n\n**MountainCar reward:** We clarify that scaling transforms negative rewards to positive while preserving optimal policy.\n\n## Claimed Contributions\n\n**Stochastic MDPs:** We will revise to clarify our contribution is extending POLY-HOOT (limited to deterministic MDPs) to stochastic settings, not introducing MCTS for stochastic MDPs broadly.\n\n**Adaptive search:** We will rephrase to acknowledge building on POLY-HOOT's approach, emphasizing our novel power mean application to stochastic envs.\n\n## Notation and Clarity\n\nWe will improve clarity by fixing all the mentioned notions.\n\n## HOO-Based Action Selection in POLY-HOOT\n\nTo Clarify\n\n**HOO Tree**\n\nA different action isn't returned every time until max depth; here's how HOO-based action selection works:\n\n - HOO (Hierarchical Optimistic Optimization) uses a binary tree structure to adaptively partition the continuous action space. Each node in this HOO tree represents a subset of the action space, with child nodes representing further subdivisions. \n\n - When selecting an action, HOO follows a path from the root to a leaf by choosing at each level the child with the larger upper confidence bound (B-value). This doesn't necessarily mean creating a new unique action each time.\n\nThe key insight is that HOO strategically explores promising regions of the continuous action space rather than uniformly creating new actions. The algorithm uses upper confidence bounds to balance exploration and exploitation within the action space.\n\n**Bounded-Depth HOO Tree**\n\nPOLY-HOOT introduces a bounded-depth parameter H̄ for the HOO tree, which serves an important purpose: Once a HOO tree path reaches depth H̄, it will repeat the action rather than creating a new one. This mechanism helps prevent the excessive branching you're concerned about.\n\n**Practical Branching Factor**\n\nIn practice, the effective branching factor is much smaller than the theoretical maximum of 2^H̄ because:\n\n1. HOO concentrates exploration on promising regions of the action space\n2. The power parameter (p) further controls exploration vs. exploitation balance\n3. The algorithm uses polynomial upper confidence bounds to focus on high-reward actions\n4. The bounded-depth mechanism encourages exploitation of good actions already found\n\n## Academic Integrity\n\nWe acknowledge the reviewer's concern about proof attribution. Due to the foundational nature of POLY-HOOT to our work and the necessary parameter renaming ($b,\\alpha,\\beta$ in our work versus $\\eta,\\alpha,\\xi$ in Mao et al.), we included detailed proofs to ensure consistency and correctness. However, we recognize that proper attribution is crucial. \n\nWe will make explicitly clear in our revision.", "claims_and_evidence": "The theoretical claims seem well-supported by proofs. There are shortcomings with claimed contributions and the experiment scope, as discussed below.", "methods_and_evaluation_criteria": "The key novel change compared to POLY-HOOT (Mao et al 2020), i.e. the use of power means, is well-motivated to better track non-stationary rewards. It would have been nice to have more discussion of why the power mean in particular was chosen, instead of other estimators that can be shown to be consistent in the non-stationary setting.\n\nThe evaluation criteria are standard for MCTS methods with MDPs.", "theoretical_claims": "I checked the convergence proofs at a high level and they seem to be correct.", "experimental_designs_or_analyses": "I have some concerns about the experiments, which I list below.\n\n- The experiments are limited to 5 low-dimensional continuous control tasks without much long-horizon planning needed. It would be nice to see results in higher-dimensional longer-horizon tasks, for example as in (Kim et al., \"Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds\", AAAI 2020).\n    - Line 435 describes MountainCar as \"high-dimensional\", but it is only 2D.\n- More detail/justification should be given on the progressive widening parameters chosen. The optimal parameter values generally vary by task (Sunberg et al., \"Online algorithms for POMDPs with continuous state, action, and observation spaces\", ICAPS 2018).\n- Similarly, it would be nice to investigate the effect of changing the max HOO tree depth parameter rather than arbitrarily fixing it at 10.\n- Insufficient justification is given for scaling the rewards of the continuous control tasks. It is well-known that shifting rewards (especially changing the sign of rewards) can significantly change the optimal policy behaviour and returns.\n    - Conflictingly, the description of the MountainCar domain seems to suggest that it still has negative rewards most of the time (l405-406).\n    - Additionally: \"Details of the experimental setup, including noise levels and reward-scaling techniques, are provided in Appendix G.\" (l424-426), however appendix G has no discussion of reward scaling.", "relation_to_broader_scientific_literature": "In my view the claimed contributions of the paper over the current literature are overstated in places:\n\n1. Applicability to stochastic MDPs. It is true that POLY-HOOT (Mao et al. 2020) did not apply to stochastic MDPs. Howevever, I don’t agree that there are general “significant challenges… in adapting [MCTS] to stochastic MDPs” (l12-14), and that \"adapting MCTS to... stochastic domains remains non-trivial\" (l67-68). UCT (Kocsis et al. \"Bandit based Monte-Carlo Planning\", ECML 2006.) and many other MCTS-based algorithms are straightforwardly applicable to stochastic MDPs.\n2. “Our approach avoids naive action-space discretisation by focusing search adaptively on where it matters most” (l39-41, RHS) -- this is true of many existing works, including the one that this work is most closely related to, POLY-HOOT.\n\nHowever, results show this work's method outperforming common approaches to continuous state/action MCTS. Novel methods to continuous MCTS are relatively rare, so this is a good contribution and the method may be practically useful to the community.\n\nIt would have been nice to mention and potentially experimentally compare to a similar recent work that addresses continuous action sampling: (Kim et al., \"Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds\", AAAI 2020). That work only applies to deterministic MDPs, but the same is true of POLY-HOOT which is compared to in this work.", "essential_references_not_discussed": "I do not know of any missing essential references.", "other_strengths_and_weaknesses": "1. Notation is not the best:\n    - Clarity would be improved by consistently using MCTS depth d = 0..D, rather than using h/H in the text formalisation of MCTS and d/D in Algorithm 1. The POLY-HOOT paper used d=0..D for MCTS trees and h=0..H for HOO trees, which is clearer.\n    - $H$ in Algorithm 1 is also used for both MCTS horizon and the chosen $h$ node value in Algorithm 1 (Line 190).\n    - $\\hat{H}$ seems to be the maximum depth of a HOO tree but is not defined anywhere. It may be a typo of $\\bar{H}$, defined later on line 290 RHS.\n1. A few improvements to clarity could be made:\n    - Referring to “non-stationary settings” in the abstract is confusing, as it makes it seem that the work applies to non-stationary MDPs instead of non-stationary value estimation in the MCTS tree.\n    - In my view calling the optimism term in arm selection an “exploration bonus” is confusing. The term “exploration bonus” is most commonly used to refer to additional reward added to the ground-truth reward in order to encourage exploration by RL (Taiga et al, “On bonus-based exploration methods in the arcade learning environment”, 2021) (Kolter et al., \"Near-Bayesian exploration in polynomial time\", ICML 2009). Here, the bonus term affects only action selection, not the real incurred reward during the trajectory. Mao et al. (2020) call it a “bonus” without calling it an “exploration bonus”, likely to avoid confusion.\n    - \"If s_{l_t} is a new leaf with l_t < H, new Q-value nodes (s_{l_t} , a) for all actions in Aslt are added.\" (l134-135 RHS) -- this only applies for the discrete action case, not the continuous action case.\n    - As the algorithm is largely a modification of POLY-HOOT, it would be helpful to use highlighting in Algorithm 1 to show the novel parts of the algorithm.", "other_comments_or_suggestions": "### Minor points\n\n- Line 122-124 RHS: \"If $\\pi_0$ is deterministic, it provides a fixed value\" -- this is not true for stochastic MDPs, a deterministic policy will give a distribution over returns.\n- Equation 1 seems to be missing magnitude bars around the expectation operator\n- Line 118 A_s not defined, and surely the sum should be over outcomes not actions?\n- Appendix section headers E and F say “n” instead of “in”\n- Line 155 “UCT like” should be “UCT-like”\n- Line 179 overrun of line into RH column\n- Line 207 awkward spacing", "questions_for_authors": "1. I have one key question about HOO-based action selection, which I may be misunderstanding.\n    - From the description of the HOO action selection process here and in the original POLY-HOOT paper, it seems that a different action will be returned every time until the tree is fully expanded to max depth, down at least one path. Only max-depth actions may be repeated, otherwise a new action is selected and a new node created (lines 217-219).\n    - This means the MCTS tree action branching factor must be somewhere between $H$ and $2^H$, which may be very high. H=10 in your experiments, so the branching factor could be up to 1024. This seems very high for a continuous action space, and would make the tree very wide and shallow. In progressive widening, the branching factor dynamically changes over time to balance the tree width/depth, but I don't see how this could happen here.\n    - Given that your max MCTS horizon is $T=150$, surely my interpretation cannot be correct. Please can you explain?\n1. Please explain the justification behind the reward scaling in the experiments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Research Integrity Issues (e.g., plagiarism)"]}}, {"review_id": "eFRNXllhON", "reviewer": "Reviewer_hTDe", "summary": "This paper introduces Stochastic-Power-HOOT, an extension of HOOT designed to handle stochastic and continuous-action Markov Decision Processes (MDPs), where prior methods primarily focused on deterministic settings. The core contributions include:\n - Power mean backup operator to mitigate non-stationary reward estimation issues in stochastic environments.\n - Polynomial exploration bonus to ensure convergence at a polynomial rate in stochastic settings.\n - The paper evaluate Stochastic-Power-HOOT on four modified OpenAI Gym tasks (CartPole, Pendulum, MountainCar, and Acrobot), demonstrating that it outperforms existing baselines such as HOOT, PUCT, and discretized-UCT.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "| Algorithm | Humanoid-v0 | Hopper-v0 |\n|-----------|---------------------|-------------------|\n| UCT (baseline) | -136.98 ± 44.84 (1.0x) | 5216.93 ± 179.64 (1.0x) |\n| POLY-HOOT (p=1) | -44.40 ± 3.33 (3.1x) | 13230.66 ± 2844.33 (2.5x) |\n| **Stochastic-Power-HOOT** | **-44.12 ± 6.22 (3.1x)(p=2)** | **13348.45 ± 6110.36 (2.6x)(p=8)** |\n| HOOT | -57.35 ± 10.46 (2.4x) | 10452.83 ± 3885.12 (2.0x) |\n| PUCT(PW) | -89.74 ± 24.16 (1.5x) | 5218.73 ± 1384.90 (1.0x) |\n| Voronoi MCTS | -48.69 ± 9.52 (2.8x) | 411.70 ± 29.03 (12.7x worse) |\n\nThank you for your review and recognizing the theoretical contributions of our work. We appreciate your suggestions for improvement, particularly regarding empirical evaluation. We address each of your concerns in detail and kindly ask you to consider updating your scores after reading the rebuttal.\n\n### Addressing Limited Experimental Evaluation\n\nWe expanded our experiments to include more complex environments. Specifically, we tested our approach on MuJoCo tasks with higher-dimensional action spaces:\n\n1. **Humanoid-v0** (17D action space):\n   - Stochastic-Power-HOOT achieved 3.1x better performance than baseline UCT\n   - Stochastic-Power-HOOT (-44.12 ± 6.22) significantly outperformed HOOT (-57.35 ± 10.46)\n\n2. **Hopper-v0**:\n   - Stochastic-Power-HOOT achieved 2.6x better performance than baseline UCT\n   - Performance ranking: POLY-HOOT = POLY_HOOT > HOOT > PUCT (Progressing Widening) > UCT >> Voronoi MCTS\n\nThese results demonstrate that our theoretical advantages translate to practical improvements in more complex domains with higher-dimensional action spaces.\n\nWe agree that comparing against newer state-of-the-art approaches would strengthen our evaluation. We added Kim et al.'s Voronoi MCTS (AAAI 2020) to our experiments as you suggested. This recent algorithm uses Voronoi partitioning for continuous action spaces. Interestingly, it performs well on Humanoid (2.8x better than UCT) but poorly on Hopper, highlighting complementary strengths of different approaches.\n\nWe will update our revised paper and discuss connections with recent deep RL + MCTS methods.", "claims_and_evidence": "The paper provides strong theoretical justification for its proposed modifications, particularly the use of power mean backups and polynomial exploration bonuses, along with a clear convergence rate analysis. However, the empirical evaluation is somewhat limited:\n - The experiments are conducted on toy domains with relatively simple dynamics. The applicability of the method to more complex, real-world tasks (e.g., MUJOCO environments or robotics control benchmarks) remains uncertain.\n - The baselines used for comparison are dated, with the most recent one being from 2013. It is unclear whether the observed improvements would hold against state-of-the-art approaches.\n\nWhile the theoretical contributions are compelling, the experimental validation does not fully justify the practical impact of the proposed method.", "methods_and_evaluation_criteria": "The evaluation benchmarks are too simple to meaningfully assess the advantages of Stochastic-Power-HOOT in complex stochastic environments. More challenging and widely-used benchmarks (e.g., MUJOCO or real-world robotic control tasks) would have provided a stronger demonstration of the algorithm’s scalability and practical relevance.", "theoretical_claims": "The theoretical results appear correct and well-structured. The proofs provide clear convergence guarantees, and I did not find any obvious flaws in the derivations.", "experimental_designs_or_analyses": "See issues listed in 'Methods And Evaluation Criteria' section.", "relation_to_broader_scientific_literature": "The paper extends prior work in Monte-Carlo Tree Search (MCTS) for continuous action spaces and stochastic domains, which is relevant for broader AI research community.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "N.A.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "See issues listed in 'Claims And Evidence' section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4GUUj1568g", "reviewer": "Reviewer_aKY5", "summary": "This paper introduces Stochastic-Power-HOOT, a novel Monte-Carlo Tree Search (MCTS) algorithm designed for continuous, stochastic MDPs. The authors propose integrating a power mean as a value backup operator along with a polynomial exploration bonus to address the related challenges. The paper provide theoretical analysis that Stochastic-Power-HOOT converges at a polynomial rate, extending the theoretical guarantees of POLY-HOOT to stochastic environments. And the authors also conduct experiments on stochastic tasks adapted from OpenAI Gym to support their claims.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and recognition of our theoretical contributions. We address each of your concerns in detail and kindly invite you to consider updating your scores\n\n### Complex Environments\n\nWe've expanded our experiments to include high dimensional MuJoCo environments with added noise to action, dynamic, and observation:\n\n1. **Humanoid-v0** (17D action space):\n   - Stochastic-Power-HOOT achieved 3.1x better results than baseline UCT\n   - Even in this complex environment, our method maintained consistent improvement\n\n2. **Hopper-v0**:\n   - Stochastic-Power-HOOT achieved 2.5x better results than baseline UCT\n   - Stochastic-Power-HOOT (p=8) showed further improvements (2.6x)\n\n| Algorithm | Humanoid-v0 | Hopper-v0 |\n|-----------|---------------------|-------------------|\n| UCT (baseline) | -136.98 ± 44.84 (1.0x) | 5216.93 ± 179.64 (1.0x) |\n| POLY-HOOT (p=1) | -44.40 ± 3.33 (3.1x) | 13230.66 ± 2844.33 (2.5x) |\n| **Stochastic-Power-HOOT** | **-44.12 ± 6.22 (3.1x)(p=2)** | **13303.61 ± 3070.34 (2.5x)(p=8)** |\n| HOOT | -57.35 ± 10.46 (2.4x) | 10452.83 ± 3885.12 (2.0x) |\n| PW-UCT | -89.74 ± 24.16 (1.5x) | 5218.73 ± 1384.90 (1.0x) |\n| Voronoi MCTS | -48.69 ± 9.52 (2.8x) | 411.70 ± 29.03 (12.7x worse) |\n\n**Voronoi MCTS comparison:** We added Kim et al.'s Voronoi MCTS (AAAI 2020) to our experiments. This recent algorithm uses Voronoi partitioning for continuous action spaces. Interestingly, it performs well on Humanoid but poorly on Hopper, highlighting complementary strengths of different approaches.\n\n### Ablation Study on Power Parameter\n\nWe conducted additional experiments varying the power parameter p (1, 2, 4, 8) and found:\n- For Humanoid-v0, p=2 performs best (-44.12 ± 3.11)\n- For Hopper-v0, p=8 shows highest returns (13303.61 ± 3070.34)\n- Higher p values generally help in more stochastic environments\n\n## Power Mean Justification\n\n- The power mean effectively balances between underestimation and overestimation of optimal values in MCTS. As planning progresses, we need a backup operator that captures the potential of promising actions without being overly optimistic. \n\n- Standard arithmetic means (p=1) tend to underestimate optimal values by averaging across all samples, including suboptimal early explorations. Conversely, max operators (p→∞) overestimate true values by focusing solely on the best sample, which may be an outlier.\n\n- Power means with p>1 provides an elegant trade-off: it gives more weight to higher values without fully committing to the maximum. As p increases above 1, the power mean moves smoothly from the arithmetic mean toward the max operator. This creates a controlled optimistic bias that encourages exploration of promising regions while maintaining some robustness to outliers.\n\n### References  to Deep RL + MCTS Methods\n\nIn our revised paper, we'll include a discussion of connections to and contrasting our approach with Deep RL + MCTS Methods for continuous spaces\n\n### Addressing Your Specific Questions\n\n1. **Theoretical assumptions in general settings**: \n\nTo clarify\n\n*. Concentration Properties (Assumption 3)\nThis assumption is actually **automatically satisfied by construction** in our algorithm:\n- As proven in Section 6, the concentration property is established by induction through the MCTS tree structure\n- The power mean backup operator inherently preserves and strengthens this property\n- Unlike alternative approaches requiring external assumptions, our concentration guarantees emerge directly from the algorithm design\n\n*. Smoothness (Assumption 2)\nThe smoothness assumption is both theoretically sound and practically validated:\n- It is a standard requirement across all HOO-based algorithms (HOO, HOOT, POLY-HOOT)\n- For robotic control tasks (Hopper, Humanoid, etc.), smoothness naturally emerges from:\n  * Physics-based dynamics (governed by differential equations)\n  * Continuous control inputs and their effects on system states\n  * Reward functions based on physical quantities (distance, energy, etc.)\n\n*. Empirical Validation\n\nOur extensive experiments confirm these assumptions hold in practice:\n- Across 5 standard benchmarks (CartPole, Pendulum, etc.)\n- In higher-dimensional MuJoCo environments (17D Humanoid, 3D Hopper)\n- Under various stochasticity conditions (dynamics noise, observation noise)\n\nThe superior performance of Stochastic-Power-HOOT over alternatives (UCT, HOOT, Voronoi MCTS) provides strong empirical evidence that our theoretical assumptions align well with practical settings.\n\n2. **Sparse-reward tasks**: For MountainCar, our reward transformation preserves the sparse nature while ensuring numerical stability. Our results show robust performance even with the original reward structure.\n\n3. **Handling varying stochasticity**: The power mean parameter (p) + the polynomial bonus allows adaptation to different noise levels. Our ablation studies show p=2 works well for Humanoi, while p=8 works well with Hopper.", "claims_and_evidence": "The paper makes several strong claims, most of which are mainly supported by theoretical analysis, and the empirical experiments is a bit weak:\n- Stochastic-Power-HOOT converges at a polynomial rate in stochastic environments. The authors provide a theoretical analysis in Section 6, showing that the algorithm achieves convergence at the mentioned rate. This is supported by Lemma 1, Theorem 1, and Theorem 3, which establish the polynomial concentration of the power mean estimator and the convergence of the expected payoff. However,  I dont find this paper has discussed the computational complexity of Stochastic-Power-HOOT compared to other methods, which could be a limitation in practical applications.\n- The power mean backup operator effectively handles non-stationary dynamics. The theoretical analysis in Section 5.2.4 and the experimental results in Section 7 support this claim. The power mean operator is shown to balance exploration and exploitation better than simple averaging, especially in stochastic environments.\n- Stochastic-Power-HOOT outperforms existing methods in continuous, stochastic domains. The experimental results in Section 7 demonstrate that Stochastic-Power-HOOT achieves higher average returns compared to HOOT, discretized-UCT, and PUCT across several modified OpenAI Gym tasks. The results are presented with standard deviations, showing consistent performance improvements. However,  these experiments are limited to simple or modified OpenAI Gym tasks. The dimension of the continuous space and the complexity of stochasticity are far from environments often used in academic community and real-world decision-making scenarios.", "methods_and_evaluation_criteria": "The proposed method, Stochastic-Power-HOOT, is well-suited for the problem of continuous, stochastic MDPs. The use of a power mean backup operator and polynomial exploration bonus addresses the limitations of existing methods like HOOT, which rely on logarithmic bonuses that lack theoretical guarantees in non-stationary settings. \n\nThe authors compare Stochastic-Power-HOOT against several established MCTS variants (e.g., HOOT, discretized-UCT, PUCT). And the evaluation criteria, including average returns and standard deviations over multiple runs, are standard and suitable for assessing the performance of planning algorithms.", "theoretical_claims": "The theoretical claims in the paper are well-supported by rigorous proofs. The authors provide detailed proofs for the polynomial concentration of the power mean estimator (Theorem 1) and the convergence of the expected payoff (Theorem 3). The proofs rely on assumptions about the smoothness of the reward function and the hierarchical structure of the MCTS tree, which are reasonable for the problem at hand.\n\nThe proof of Theorem 1 relies on the assumption that the reward sequence satisfies certain concentration properties (Assumption 3). While this assumption is standard in bandit literature, it would be helpful to discuss its implications in the context of MCTS. The paper could benefit from a more detailed discussion of the conditions under which the theoretical guarantees hold, especially in relation to the choice of hyper-parameters.", "experimental_designs_or_analyses": "The experimental design is sound, with the authors testing Stochastic-Power-HOOT on modified versions of classic control tasks. The modifications introduce stochasticity in actions, transitions, and observations, making the tasks more challenging and suitable for evaluating the algorithm's robustness. But totally, the experiments are limited to relatively simple tasks. While the results are promising, they may not generalize to more complex or high-dimensional environments.", "relation_to_broader_scientific_literature": "This paper extends the theoretical guarantees of POLY-HOOT to stochastic environments", "essential_references_not_discussed": "The cited references cover some classical works in the MCTS field, but show little discussion about recent deep RL + MCTS methods, such as AlphaZero/MuZero, and their variants designed for continuous action space and stochastic environments—Sampled MuZero and Stochastic MuZero.", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper addresses an important gap in the literature by extending MCTS to continuous, stochastic environments with theoretical guarantees.\n- The use of a power mean backup operator is novel and well-motivated, providing a flexible mechanism for value estimation.\n\nWeaknesses:\n\n- The empirical validation is limited to relatively simple tasks. Testing on more complex or real-world environments would strengthen the paper.\n- The theoretical analysis, while rigorous, relies on assumptions that may not hold in all practical scenarios.", "other_comments_or_suggestions": "- The paper could benefit from a more detailed ablation study to isolate the impact of the power mean backup operator versus the polynomial exploration bonus.\n- The paper could benefit from a clearer explanation of the intuition behind the power mean backup operator and how it helps handle non-stationarity in stochastic environments.", "questions_for_authors": "- How do the assumptions made in the theoretical analysis impact the applicability of Stochastic-Power-HOOT in more general settings? Are there any limitations or potential extensions to address these concerns?\n- For sparse-reward tasks like MountainCar, does explicit reward engineering obscure the algorithm’s performance in raw sparse-reward settings?\n- How do you address the trade-off between exploration and exploitation when the stochasticity of the environment varies significantly over time or across different regions of the state space?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tHAGx6qfDk", "reviewer": "Reviewer_KtK7", "summary": "The paper considers MCTS for continuous action space and non-stochastic environments. The authors propose to use a power mean operator for value estimates. They also propose a polynomial exploration bonus. They show convergence results for stochastic environments that matches previous results on deterministic environments. Finally they perform experiments that show improvement over previous methods.\n\n######\nPost rebuttal\n#######\n\nI'm raising my score to 2 as my concerns were answered. I think it would benefit the paper to better discuss the theoretical results that allow obtaining guarantees on stochastic environments.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our submission. We appreciate your recognition of our theoretical contributions and have addressed your concerns with additional justification and expanded experiments.\n\n## Power Mean Estimation: Detailed Justification\n\n- The power mean effectively balances between underestimation and overestimation of optimal values in MCTS. As planning progresses, we need a backup operator that captures the potential of promising actions without being overly optimistic. \n\n- Standard arithmetic means (p=1) tend to underestimate optimal values by averaging across all samples, including suboptimal early explorations. Conversely, max operators (p→∞) overestimate true values by focusing solely on the best sample, which may be an outlier.\n\n- Power means with p>1 provide an elegant trade-off: they give more weight to higher values without fully committing to the maximum. As p increases above 1, the power mean moves smoothly from the arithmetic mean toward the max operator. This creates a controlled optimistic bias that encourages exploration of promising regions while maintaining some robustness to outliers.\n\n- Our experiments confirm this advantage—Stochastic-Power-HOOT with appropriate p values consistently outperforms both UCT (which uses arithmetic means) and other approaches, particularly in stochastic environments where balancing optimism and realism is critical.\n\n## Polynomial Bonus for Stochastic Environments\n\nOur approach addresses a critical gap in the POLY-HOOT paper: convergence in stochastic MDPs. While POLY-HOOT proved convergence for deterministic environments, our contribution extends these guarantees to settings with stochastic transitions.\n\nThe key factors:\n\n- Our polynomial bonus separates local action exploration from global uncertainty adjustment, creating an adaptive mechanism that responds to varying levels of stochasticity in the environment.\n\n- In stochastic environments, value estimates have higher variance from both transition randomness and downstream policy changes. Our approach maintains sufficient exploration even as planning progresses, unlike logarithmic bonuses that decrease too rapidly.\n\n- The combination with power mean backups creates a robust mechanism for stochastic settings - the power mean controls the trade off underestimation/overestimation in value estimates, while the polynomial bonus guides exploration appropriately.\n\nStochastic-Power-HOOT's superior performance demonstrates the effectiveness of our approach in bridging this important theoretical gap.\n\n## Experimental concerns\n\nFor responding to the reviewer's concern about the relevancy of stochastic environments:\n\n- While our experiments use simulated environments, they reflect fundamental challenges present in real-world applications which are inherently stochastic. Robotics, autonomous vehicles, healthcare, and resource management all operate under multiple sources of uncertainty (Action, Dynamics, Observation uncertainty )\n\n- The growing deployment of autonomous systems in unstructured environments makes planning under stochasticity increasingly critical. Current methods often rely on deterministic approximations that fail when uncertainty accumulates. Our approach addresses this gap, demonstrating how planning can be made robust to the types of stochasticity that practitioners face daily.\n\n- The contribution is not creating artificial noise, but rather developing theoretical guarantees for continuous planners in settings where stochasticity cannot be ignored - a limitation of prior work that restricts real-world applicability.\n\n| Algorithm | Humanoid-v0 | Hopper-v0 |\n|-----------|---------------------|-------------------|\n| UCT (baseline) | -136.98 ± 44.84 (1.0x) | 5216.93 ± 179.64 (1.0x) |\n| POLY-HOOT (p=1) | -44.40 ± 3.33 (3.1x) | 13230.66 ± 2844.33 (2.5x) |\n| **Stochastic-Power-HOOT** | **-44.12 ± 6.22 (3.1x)(p=2)** | **13303.61 ± 3070.34 (2.5x)(p=8)** |\n| HOOT | -57.35 ± 10.46 (2.4x) | 10452.83 ± 3885.12 (2.0x) |\n| PW-UCT | -89.74 ± 24.16 (1.5x) | 5218.73 ± 1384.90 (1.0x) |\n| Voronoi MCTS | -48.69 ± 9.52 (2.8x) | 411.70 ± 29.03 (12.7x worse) |\n\nWe run further experiments in Humanoid and Hopper with noise introduced in Action, Dynamics, Observation.  Our approach significantly outperforms existing methods on higher-dimensional robotics tasks with multiple sources of stochasticity. On Humanoid-v0 (17D action space), Stochastic-Power-HOOT achieves a 3.1x improvement over UCT, while on Hopper-v0, it shows a 2.5x improvement. Interestingly, power mean tuning matters - p=2 works best for Humanoid while p=8 excels for Hopper. \n\nThe performance (catastrophic in Hopper) of Voronoi MCTS (which is only for deterministic settings) further shows the challenge of designing robust planners for stochastic settings and validates our theoretical contribution.\n\n After reading the rebuttal, we kindly invite you to consider updating your scores.", "claims_and_evidence": "The theoretical claims looks sound (even though I didn't read the proofs).\n\nThe experimental results seem a bit lacking - the environments and rewards were modified to fit the claims. I'm not sure if these changes are reasonable and would have preferred some benchmark environment that wasn't tempered with.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, but the theoretical claims are reasonable.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The paper improves on previous algorithms empirically (e.g. HOOT) and extends previous convergence rates to stochastic environments.", "essential_references_not_discussed": "No to the best of my knowledge.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Solid theoretical result.\n\n2. Paper is written clearly. \n\n3. Experiments show improvements of the current method over previous similar works.\n\nWeaknesses:\n\n1. The power mean estimation method seems to be the main technical novelty, but why it's any good is not really discussed. I understand that it's closer to the max function than the average function, but also is softmax. This choice seems arbitrary and unclear, perhaps the theory still works, but a complex averaging is not a strong novelty in my opinion. Also it obviously puts some practical limitations on negative or zero rewards which adds unnecessary complications.\n\n2. The polynomial bonus was mentioned to also exist in Poly HOOT, how do the two compare? You mention in the introduction its tailored to stohcastic MDP, but this tailoring is not explained in the text.\n\n3. The environments in the experiment were tailored to show the solution's benefits. But if stochastic benchmarks couldn't be found, maybe the problem is not that interesting..", "other_comments_or_suggestions": "If there is a benchmark which is stochastic with continuous action space it would make a more convincing case.", "questions_for_authors": "Following my previous comments:\n\n1. Can you give a strong justification for mean power estimation?\n\n2. Can you provide better explanation on the polynomial bonus and why it works for stochastic environments unlike the previous polynomial bonus?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u6wYlOyVUG", "reviewer": "Reviewer_VkU4", "summary": "The submission introduces a new MCTS algorithm for continuous and stochastic MDPS. The method combines power mean backups (known to be more stable than simple averaging) with polynomial exploration bonuses (known to lead to improved converged compared to logarithmic exploration) and an HOO-like partitioning scheme for the continues domain. The convergence rate of the method in continuous and stochastic MDPS  is analyzed and found to match the one of POLY-HOOT in for continuous and deterministic MDPS. In the presence of stochasticity, the method empirically performs better than its deterministic counterpart.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and for suggesting additional related work we hadn't cited. We appreciate your thorough analysis of our theoretical claims. We address each of your concerns in detail and kindly ask you to consider updating your scores after reading the rebuttal.\n\n### Including Additional Baselines\n\n| Algorithm | Humanoid-v0 | Hopper-v0 |\n|-----------|---------------------|-------------------|\n| UCT (baseline) | -136.98 ± 44.84 (1.0x) | 5216.93 ± 179.64 (1.0x) |\n| POLY-HOOT (p=1) | -44.40 ± 3.33 (3.1x) | 13230.66 ± 2844.33 (2.5x) |\n| **Stochastic-Power-HOOT** | **-44.12 ± 6.22 (3.1x)(p=2)** | **13303.61 ± 3070.34 (2.5x)(p=8)** |\n| HOOT | -57.35 ± 10.46 (2.4x) | 10452.83 ± 3885.12 (2.0x) |\n| PW-UCT | -89.74 ± 24.16 (1.5x) | 5218.73 ± 1384.90 (1.0x) |\n| Voronoi MCTS | -48.69 ± 9.52 (2.8x) | 411.70 ± 29.03 (12.7x worse) |\n\nFollowing your suggestion, We added Kim et al.'s Voronoi MCTS (AAAI 2020) to our experiments. This recent algorithm uses Voronoi partitioning for continuous action spaces but for deterministic settings only:\n\n1. **Voronoi MCTS comparison**:\n   - Performs well on Humanoid (3nd best performer after our method)\n   - But shows inconsistent results on Hopper (worst performer)\n   - This highlights the need for methods specifically designed for stochasticity\n\n### Missing Citations\n\nThank you for pointing out the important related work. We'll add these citations in our revised paper:\n\n1. \"Generalized Mean Estimation in Monte-Carlo Tree Search\" (Dam et al., 2020)\n2. \"Power Mean Estimation in Stochastic Monte-Carlo Tree Search\" (Dam et al., 2024)\n\nThese works complement our approach and help position our contribution in the broader literature on power means in MCTS.\n\n### Additional Changes\n\nWe'll implement your suggested edits:\n- Bold formatting for best results in Table 2\n- Fix typos in Appendix headings\n- Properly name PUCT in the related work section\n\nKim, B., Lee, K., Lim, S., Kaelbling, L., & Lozano-Perez, T. (2020). Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9916-9924.", "claims_and_evidence": "I did not find any problematic claims.", "methods_and_evaluation_criteria": "* Analyzing the convergence rate makes sense for an optimization method.\n* The method is empirically evaluated on classic RL benchmarks, which seem appropriate to me. A small caveat is that the benchmarks are originally deterministic and only made stochastic in the aftermath by adding noise. In order to support the practical relevance of extending this class of algorithms to stochastic environments, I think it would have been a bit nicer to actually find an inherently stochastic application.", "theoretical_claims": "I checked the proofs in Appendix F and did not find an issue with them.", "experimental_designs_or_analyses": "If I understand correctly, POLY-HOOT and discretized-POWER UCT are as closely related to the method as the current baselines discretized-UCT and HOOT. Therefore, including them as baselines could provide an interesting additional layer of ablation.", "relation_to_broader_scientific_literature": "The suggested method is most closely related to POLY-HOOT:\nBoth methods adopt polynomial exploration and both methods achieve the same convergence rate. The difference is that POLY-HOOT is designed for deterministic settings, while the proposed method works for stochastic settings.\n\nSince POLY-HOOT is related to HOOT and PUCT (by replacing the logarithmic exploration bonus in HOOT with the polynomial one from PUCT) and to HOO (by using it for action selection), the proposed method is also related to these two pieces of work.", "essential_references_not_discussed": "**Generalized Mean Estimation in Monte-Carlo Tree Search** Dam, Klink, D’Eramo, Peters, Pajarinen. Published in IJCAI 2020.\n\nThis paper introduces „POWER-UCT“, which is related to the proposed method in the sense that it is also a  MCTS with power mean backups (e.g. Section 4, Eq. 11). The difference to the proposed method is that POWER-UCT is designed for discrete and deterministic environments.\n\n**Power Mean Estimation in Stochastic Monte-Carlo Tree Search** Dam, Maillard, Kaufmann. Published in UAI 2024. \n\nThis is another very similar power mean MCTS version. The difference is that the newly proposed version is for discrete, stochastic MDPs, wheres this citation is for continuous, stochastic MDPs.", "other_strengths_and_weaknesses": "I think this work nicely complements and fits into the existing line of work by extending this class of algorithms to continuous and stochastic settings.", "other_comments_or_suggestions": "* I would mention PUCT *with its name* in the related work section. I know it’s mentioned later on, but I was slightly confused. \n* One could highlight the best performing method in Table 2 by using bold font for it.\n* Typo in the headlines in the Appendix: „Convergence of Stochastic-Power-HOOT [i]n Monte-Carlo Tree Search“.\n* In the outline in Appendix A, the third bullet point should be „Technical Lemmas“.", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers MCTS in stochastic environments with continuous action and state spaces, and proposes Stochastic-Power-HOOT, which integrates a power mean as a value backup operator and polynomial exploration bonus. 

The paper has mixed reviews. Generally speaking, reviewers think the paper is promising, but detected several issues:

* For a paper that builds heavily upon previous work, there is a worrying lack of proper references and attribution of results to the correct work. This makes aspects regarding novelty and framing of the paper not as crisp as they should be;

* Experiments are limited;

*  Even though most reviewers praise the theoretical analysis provided, there are some doubts regarding justification of a few design choices and clarity regarding the action branching behaviour.

The authors acknowledge these issues and promise to address them in a final version. However, the gap between the current version of the paper and where in it needs to be is wider than other papers I have overseen.
Decision: Accept (poster)