Technical Summary: Gaussian Process Aggregation for Root-Parallel Monte Carlo Tree Search with Continuous Actions

Problem Statement

Monte Carlo Tree Search (MCTS) is a cornerstone algorithm for online planning, particularly in domains with large state and action spaces. While the root-parallel variant of MCTS is widely used to maximize performance under limited wall-clock time by running multiple independent search threads, a critical challenge remains in continuous action spaces: how to effectively aggregate statistics from these parallel threads.

In discrete action domains, standard aggregation strategies like Majority Voting are applicable. However, in continuous domains, every sampled action is unique, rendering voting inapplicable. Existing baselines, such as selecting the action with the highest return (Max) or highest visit count (Most Visited), fail to leverage the structural relationships between actions. State-of-the-art methods (e.g., Kurzer et al., 2020) attempt to exploit action similarity but do so in an ad-hoc manner and are restricted to selecting only actions that have already been sampled in the environment. They lack a principled mechanism to interpolate between sampled actions or to identify promising actions that were never trialed, a significant limitation when high-quality actions are difficult to sample or when computational budgets are tight.

Methodology

The authors propose Gaussian Process Regression for Root Parallel MCTS (GPR2P), a method that constructs a principled probabilistic model of the return over the entire continuous action space using data from all parallel search trees.

Core Mechanism

1. Data Collection: Multiple independent MCTS threads (using UCT with Progressive Widening or Double Progressive Widening) are executed from the same root state.
2. Filtering: A visit-count threshold ($\tau$) is applied to retain only actions with sufficient exploration, serving as a reliability filter.
3. Gaussian Process Modeling:
   • The retained actions and their estimated values ($Q(s_0, a)$) serve as training data.
   • A Radial Basis Function (RBF) kernel is used to model the covariance between actions based on their Euclidean distance. This encodes the assumption that similar actions yield similar returns.
   • The model infers a predictive mean and variance for the return function across the entire action space, not just the sampled points.
4. Action Selection: The final action is selected by maximizing the estimated mean return ($\mu(a)$) over the continuous action space. Unlike previous methods, this allows the selection of actions that were never sampled in any of the parallel trees.

Complexity

While Gaussian Process Regression typically incurs $O(M^3)$ complexity (where $M$ is the number of data points), the filtering mechanism ensures $M$ remains small (e.g., $\approx 400$ in experiments). This results in a modest increase in inference time relative to the total MCTS runtime, offering a scalable solution even for higher-dimensional action spaces compared to dense discretization.

Key Contributions

1. GPR2P Algorithm: The introduction of a statistically principled method for aggregating root-parallel MCTS results in continuous domains. It moves beyond ad-hoc similarity measures to a full probabilistic model that enables interpolation and optimization over untried actions.
2. Comprehensive Empirical Evaluation: The paper presents the most extensive evaluation to date of root-parallel aggregation strategies in continuous domains. The study covers six distinct environments (including standard Gymnasium tasks and self-designed stochastic tasks) and compares GPR2P against:
   • Simple baselines (Max, Most Visited).
   • State-of-the-art similarity-based methods (Similarity Vote, Similarity Merge).
   • Single-thread MCTS baselines (standard and 8x budget).
   • A variant of the proposed method (GPR2P-EA) that restricts selection to sampled actions, isolating the benefit of untried action selection.

Results

The evaluation demonstrates that GPR2P consistently outperforms existing aggregation strategies across the majority of environments and trial budgets.

• Performance: GPR2P achieves the highest Mean Reciprocal Rank (MRR) across all six tasks. In environments with limited rewarding regions (e.g., Narrow Corridor), GPR2P avoids the performance bottlenecks seen in methods restricted to sampled actions.
• Comparison to Baselines:
  • GPR2P vs. GPR2P-EA: In 4 out of 6 environments, the ability to select untried actions directly improved performance, validating the value of the GP interpolation.
  • GPR2P vs. Similarity Merge: GPR2P generally outperforms Similarity Merge, the strongest existing baseline.
  • GPR2P vs. Single Thread (8x): The performance gains of GPR2P are not merely due to increased computational resources; the aggregation strategy itself provides a distinct advantage over simply running a single thread with a larger budget.
• Efficiency: While GPR2P requires more inference time than simple baselines, this overhead is modest compared to the total time spent on data collection. Experiments allocating the GPR2P inference time to run additional trials (instead of aggregation) showed that the aggregation strategy itself remains the primary source of performance gain.
• Anomalies: In the Pendulum task, GPR2P's advantage diminishes as trial counts increase. The authors attribute this to the agent discovering a complex, gravity-assisted strategy involving extra swings; once sufficient samples exist, the GP model's advantage over direct sampling decreases.

Significance and Claims

The paper claims that GPR2P addresses the fundamental limitations of current root-parallel MCTS aggregation in continuous spaces:

1. Principled Interpolation: It provides a rigorous statistical framework for estimating values of untried actions, rather than relying on fixed, manually designed ranking schemes.
2. Generalization: The method demonstrates robust performance across both deterministic and stochastic transition domains, suggesting broad applicability to real-world planning problems (e.g., search-and-rescue, underwater gliders) where transitions are uncertain.
3. Efficiency: It achieves superior planning performance with only a modest computational cost, making it a viable alternative for time-constrained online planning.

The authors conclude that while GPR2P introduces additional hyperparameters (kernel parameters, threshold $\tau$), these can be tuned offline. They also note that the method relies on the assumption that similar actions have similar values, which may be less suitable for highly non-linear or discontinuous value landscapes, and suggest future work could integrate GP models to guide action selection within individual MCTS threads.