Abstract
Reinforcement learning (RL) agents based on the AlphaZero and MuZero architectures have achieved superhuman performance in games like Chess and Go. However, these agents often struggle in environments with sparse rewards, where they may take thousands of actions before receiving any feedback. This paper introduces Epistemic Monte Carlo Tree Search (EMCTS), a method that integrates epistemic uncertainty—the measure of what a model does not know—directly into the search process. By propagating uncertainty through the search tree, EMCTS enables "deep exploration," allowing agents to purposefully navigate toward information-rich states. We demonstrate that EMCTS significantly outperforms standard AlphaZero in complex tasks, including writing Assembly code and solving large-scale grid-world challenges.
Introduction
The success of the AlphaZero (AZ) and MuZero (MZ) family of algorithms stems from their ability to combine deep learning with Monte Carlo Tree Search (MCTS). Despite these successes, these agents possess a critical "blind spot": they rely on learned models that are often inaccurate in regions of the state space that have been infrequently visited. This inaccuracy, known as epistemic uncertainty, can lead agents to exploit errors in their own models rather than exploring the environment effectively.
In environments characterized by sparse rewards, standard MCTS tends to stall. Without a clear reward signal, the agent has no incentive to move toward distant, unknown states. To overcome this, agents require "deep exploration"—the ability to plan multi-step trajectories toward novel areas. This paper addresses the limitation by treating the learned model not as an absolute truth, but as a random variable with associated variance, allowing the search process to account for its own ignorance.
Methodology: Epistemic Monte Carlo Tree Search
The core innovation of this work is the introduction of Epistemic MCTS (EMCTS). Unlike standard MCTS, which only backs up expected reward values, EMCTS propagates uncertainty estimates from the leaf nodes back to the root.
1. Uncertainty Propagation
EMCTS treats the value of a node as a distribution rather than a point estimate. The authors derive a theoretically motivated framework to calculate the variance of a node's value based on the rewards and values of its descendants. This ensures that the uncertainty of a distant leaf node is correctly reflected in the decision-making process at the root.
2. Epistemic Search Policies (EUCT/EPUCT)
The standard selection rules used in MCTS (UCT and PUCT) are modified to incorporate an exploration term: $\beta \cdot \sigma$. Here, $\sigma$ represents the propagated uncertainty, and $\beta$ is a hyperparameter controlling the weight of exploration. This modification incentivizes the agent to visit branches where the model is most uncertain, effectively turning "curiosity" into a plannable objective.
3. Implementation and Estimators
The system is implemented in JAX, facilitating high-performance parallelized search. To provide the raw local uncertainty scores that EMCTS propagates, the authors utilize techniques such as Random Network Distillation (RND) and Uncertainty Bellman Equations (UBE).
Experimental Benchmarks
The efficacy of EMCTS was evaluated across three distinct environments designed to test exploration capabilities:
subleq: An extremely challenging benchmark involving a "one-instruction" Assembly language. The agent must generate a sequence of memory addresses to solve tasks like "Identity Function" or "Negate Positives." Reward is binary: given only if the entire program executes perfectly. This represents a classic "needle-in-a-haystack" problem.- Deep Sea: A standard hard-exploration grid-world. The probability of reaching the goal through random actions decreases exponentially with the size of the grid, making it a benchmark for deep exploration.
- MinAtar: A simplified version of Atari games used to ensure that the method maintains general performance in standard RL settings without sacrificing stability.
Key Results and Insights
Solving the Unsolvable
In the subleq Identity task, standard AlphaZero failed to find a solution within the allocated training budget. In contrast, EMCTS (referred to as E-AZ) found correct programs significantly faster and demonstrated much higher sample efficiency. This suggests that propagating uncertainty is vital for tasks where the solution space is vast and rewards are non-existent until the final step.
Scaling Deep Exploration
EMCTS successfully solved the 50x50 Deep Sea environment, a feat that baseline MuZero and AlphaZero were unable to achieve even in smaller versions. In a 40x40 Deep Sea configuration, E-AZ found the goal in approximately 10,539 steps, compared to 22,801 steps for an agent that possessed uncertainty estimates but did not use them inside the search (AZ+UBE). This result highlights that search is a critical component for refining and utilizing uncertainty estimates effectively.
Search as an Uncertainty Refiner
A major insight from this research is that search does more than just improve value estimates; it improves uncertainty estimates. By looking ahead, the agent can recognize that a seemingly safe move leads to a total unknown, making that trajectory more attractive for exploration. To maintain stability, the authors found that alternating between exploratory episodes (using uncertainty-aware search) and exploitatory episodes (using standard search) helped the agent learn a robust policy from the highly off-policy data generated during exploration.
Conclusion and Future Work
EMCTS provides a powerful framework for deep exploration in model-based RL. By integrating epistemic uncertainty into the MCTS backup process, agents can plan their way out of local minima and toward information-rich states.
While the results are promising, challenges remain. Propagating uncertainty through the latent spaces of MuZero-style models is theoretically complex, and the current implementation uses optimistic shortcuts that could be further refined. Additionally, the sensitivity of the $\beta$ exploration parameter suggests a need for automated tuning methods. Future work will focus on extending these principles to more complex, continuous environments and refining the interaction between learned transition models and uncertainty propagation.
Summary updated