Abstract
This paper introduces KR-UCT (Kernel Regression UCT), a novel variant of Monte Carlo Tree Search (MCTS) designed for continuous action spaces characterized by execution uncertainty. Unlike standard MCTS, which treats actions as discrete and independent, KR-UCT utilizes kernel regression—with a kernel derived from the system's noise model—to share information across the action space. Evaluated in a high-fidelity curling simulator, KR-UCT demonstrates superior performance over standard UCT and domain-specific heuristics, effectively discovering high-value moves in complex, noisy environments.
Introduction
Many real-world planning problems, such as robotic navigation or precision sports, require selecting actions from a continuous space (e.g., specific angles and velocities). A significant challenge in these domains is execution uncertainty: an agent may aim for a specific target, but the actual outcome will vary due to inherent system noise.
Standard MCTS algorithms like UCT are typically optimized for discrete decision trees (e.g., Chess or Go). When applied to continuous domains, they often rely on "Progressive Widening" or human-designed heuristics to discretize the space. However, these methods often fail to exploit a critical insight: an outcome from one action provides information about any other action that could have produced that same outcome. KR-UCT addresses this by treating the action space as a continuum where every sample helps refine a global value surface.
Methods: Kernel Regression UCT
KR-UCT replaces the simple averages and discrete visit counts of standard UCT with kernel-based estimates to enable information sharing between similar actions.
- Value Estimation via Kernel Regression: Instead of averaging rewards for a single discrete action, KR-UCT uses kernel regression to estimate the value of any point in the continuous action space based on nearby samples.
- Kernel Density for Exploration: The standard exploration bonus, which depends on discrete visit counts ($n_a$), is replaced by a "kernel density" estimate ($W(a)$). This measures the total "information weight" gathered in the neighborhood of an action.
- The Uncertainty Kernel: The kernel function $K(x, x')$ is defined as the probability density function of the execution noise model. This ensures that the degree of information sharing is physically grounded in the system's actual uncertainty profile.
- Information-Gap Expansion: When expanding the tree, the algorithm searches for new actions that minimize current kernel density, effectively targeting "information gaps" to ensure broad coverage of the action space.
Experimental Setup
The algorithm was evaluated using a high-fidelity curling simulator built on the Chipmunk 2D physics library. The simulator models complex stone trajectories, friction, and multi-stone collisions.
To ensure realism, the authors used a heavy-tailed Student-t distribution to model execution noise, calibrated against Olympic-level player statistics from the 2010 and 2014 Winter Games. KR-UCT was compared against standard UCT, Rapid Action Value Estimation (RAVE), and a "Domain Knowledge" baseline using a hand-coded shot generator suggesting 7 to 30 strategic candidate shots.
Key Results
In a round-robin tournament of 16,000 games, KR-UCT achieved a positive expected point differential against all competitors. Notably, against standard UCT, KR-UCT gained an average of 0.11 points per end. In a professional 10-end match, this represents a 1.1-point advantage—a decisive margin given that nearly 30% of Olympic games are decided by a single point.
Hammer Shot Analysis
The advantage of KR-UCT is most evident in the "Hammer" (the final shot of an end). While discrete shot generators often suggest moves on the periphery of high-value zones, KR-UCT can "drift" toward the true global optimum during the search process.
As shown in the figure above, standard UCT often fails to fully exploit high-value regions because it is restricted to its initial discrete samples. In contrast, KR-UCT's kernel-based approach allows it to sample more densely in high-reward areas, effectively refining the final shot selection toward the center of the "sweet spot."
Conclusion
KR-UCT demonstrates that incorporating execution uncertainty directly into the MCTS framework via kernel regression significantly improves planning in continuous spaces. By treating actions as interrelated rather than isolated, the algorithm escapes the limitations of fixed candidate sets. Future work will focus on reducing the computational overhead of kernel density calculations and investigating the interaction between lookahead depth and continuous action selection.
Summary updated