Monte Carlo Tree Search in Continuous Action Spaces with Execution Uncertainty

Timothy Yee, Viliam Lisý, Michael H. Bowling

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Curling simulator environment showing stone trajectories and 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.

Action space analysis for the final 'Hammer' shot. The heatmap shows expected value across weight and aim, while the bottom panels compare sampling density between standard UCT and KR-UCT.

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

Abstract

Real world applications of artificial intelligence often require agents to sequentially choose actions from continuous action spaces with execution uncertainty. When good actions are sparse, domain knowledge is often used to identify a discrete set of promising actions. These actions and their uncertain effects are typically evaluated using a recursive search procedure. The reduction of the problem to a discrete search problem causes severe limitations, notably, not exploiting all of the sampled outcomes when evaluating actions, and not using outcomes to help find new actions outside the original set. We propose a new Monte Carlo tree search (MCTS) algorithm specifically designed for exploiting an execution model in this setting. Using kernel regression, it generalizes the information about action quality between actions and to unexplored parts of the action space. In a high fidelity simulator of the Olympic sport of curling, we show that this approach significantly outperforms existing MCTS methods.
BibTeX
@inproceedings{yee2016monte,
  author = {Timothy Yee and Viliam Lisý and Michael H. Bowling},
  title = {{Monte Carlo Tree Search in Continuous Action Spaces with Execution Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure