Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search

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.

Including Additional Baselines

Following 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:

1. Voronoi MCTS comparison:
   • Performs well on Humanoid (3nd best performer after our method)
   • But shows inconsistent results on Hopper (worst performer)
   • This highlights the need for methods specifically designed for stochasticity

Missing Citations

Thank you for pointing out the important related work. We'll add these citations in our revised paper:

1. "Generalized Mean Estimation in Monte-Carlo Tree Search" (Dam et al., 2020)
2. "Power Mean Estimation in Stochastic Monte-Carlo Tree Search" (Dam et al., 2024)

These works complement our approach and help position our contribution in the broader literature on power means in MCTS.

Additional Changes

We'll implement your suggested edits:

• Bold formatting for best results in Table 2
• Fix typos in Appendix headings
• Properly name PUCT in the related work section

Kim, 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.

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.

Power Mean Estimation: Detailed Justification

• 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.

• 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.

• 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.

• 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.

Polynomial Bonus for Stochastic Environments

Our 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.

The key factors:

• 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.

• 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.

• 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.

Stochastic-Power-HOOT's superior performance demonstrates the effectiveness of our approach in bridging this important theoretical gap.

Experimental concerns

For responding to the reviewer's concern about the relevancy of stochastic environments:

• 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 )

• 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.

• 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.

We 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.

The 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.

After reading the rebuttal, we kindly invite you to consider updating your scores.

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

Complex Environments

We've expanded our experiments to include high dimensional MuJoCo environments with added noise to action, dynamic, and observation:

1. Humanoid-v0 (17D action space):

   • Stochastic-Power-HOOT achieved 3.1x better results than baseline UCT
   • Even in this complex environment, our method maintained consistent improvement

2. Hopper-v0:

   • Stochastic-Power-HOOT achieved 2.5x better results than baseline UCT
   • Stochastic-Power-HOOT (p=8) showed further improvements (2.6x)

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.

Ablation Study on Power Parameter

We conducted additional experiments varying the power parameter p (1, 2, 4, 8) and found:

• For Humanoid-v0, p=2 performs best (-44.12 ± 3.11)
• For Hopper-v0, p=8 shows highest returns (13303.61 ± 3070.34)
• Higher p values generally help in more stochastic environments

Power Mean Justification

• 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.

• 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.

• 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.

References to Deep RL + MCTS Methods

In our revised paper, we'll include a discussion of connections to and contrasting our approach with Deep RL + MCTS Methods for continuous spaces

Addressing Your Specific Questions

1. Theoretical assumptions in general settings:

To clarify

*. Concentration Properties (Assumption 3) This assumption is actually automatically satisfied by construction in our algorithm:

• As proven in Section 6, the concentration property is established by induction through the MCTS tree structure
• The power mean backup operator inherently preserves and strengthens this property
• Unlike alternative approaches requiring external assumptions, our concentration guarantees emerge directly from the algorithm design

*. Smoothness (Assumption 2) The smoothness assumption is both theoretically sound and practically validated:

• It is a standard requirement across all HOO-based algorithms (HOO, HOOT, POLY-HOOT)
• For robotic control tasks (Hopper, Humanoid, etc.), smoothness naturally emerges from:
  • Physics-based dynamics (governed by differential equations)
  • Continuous control inputs and their effects on system states
  • Reward functions based on physical quantities (distance, energy, etc.)

*. Empirical Validation

Our extensive experiments confirm these assumptions hold in practice:

• Across 5 standard benchmarks (CartPole, Pendulum, etc.)
• In higher-dimensional MuJoCo environments (17D Humanoid, 3D Hopper)
• Under various stochasticity conditions (dynamics noise, observation noise)

The 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.

2. 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.

3. 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.

Thank 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.

Addressing Limited Experimental Evaluation

We expanded our experiments to include more complex environments. Specifically, we tested our approach on MuJoCo tasks with higher-dimensional action spaces:

1. Humanoid-v0 (17D action space):

   • Stochastic-Power-HOOT achieved 3.1x better performance than baseline UCT
   • Stochastic-Power-HOOT (-44.12 ± 6.22) significantly outperformed HOOT (-57.35 ± 10.46)

2. Hopper-v0:

   • Stochastic-Power-HOOT achieved 2.6x better performance than baseline UCT
   • Performance ranking: POLY-HOOT = POLY_HOOT > HOOT > PUCT (Progressing Widening) > UCT >> Voronoi MCTS

These results demonstrate that our theoretical advantages translate to practical improvements in more complex domains with higher-dimensional action spaces.

We 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.

We will update our revised paper and discuss connections with recent deep RL + MCTS methods.

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.

Experimental Design

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:

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.

MountainCar dimensionality: We will correct this to "low-dimensional" (2D state, 1D action).

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:

• Acrobot: α=0.6, k=2.5, c=1.2 (timeseries strategy) > (77.86±0.00)
• MountainCar: α=0.55, k=2.2, c=1.3 (momentum strategy) > (-0.025 ± 0.004)
• CartPole-IG: α=0.5, k=2.0, c=1.0 (adaptive strategy) > (75.80±11.84)
• Pendulum: α=0.45, k=2.5, c=1.1 (optimistic strategy) > (1315.89±85.43)

We will add to the revised paper.

HOO tree depth: We will add an investigation varying H from 1-20 and report performance.

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.

MountainCar reward: We clarify that scaling transforms negative rewards to positive while preserving optimal policy.

Claimed Contributions

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.

Adaptive search: We will rephrase to acknowledge building on POLY-HOOT's approach, emphasizing our novel power mean application to stochastic envs.

Notation and Clarity

We will improve clarity by fixing all the mentioned notions.

HOO-Based Action Selection in POLY-HOOT

To Clarify

HOO Tree

A different action isn't returned every time until max depth; here's how HOO-based action selection works:

• 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.

• 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.

The 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.

Bounded-Depth HOO Tree

POLY-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.

Practical Branching Factor

In practice, the effective branching factor is much smaller than the theoretical maximum of 2^H̄ because:

1. HOO concentrates exploration on promising regions of the action space
2. The power parameter (p) further controls exploration vs. exploitation balance
3. The algorithm uses polynomial upper confidence bounds to focus on high-reward actions
4. The bounded-depth mechanism encourages exploitation of good actions already found

Academic Integrity

We 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.

We will make explicitly clear in our revision.