Epistemic Monte Carlo Tree Search
This work improves exploration for reinforcement learning algorithms in sparse-reward tasks, such as code generation and hard-exploration benchmarks, by integrating uncertainty estimation into search, though it is incremental as it builds on existing AlphaZero/MuZero frameworks.
The paper tackles the problem of Monte Carlo Tree Search (MCTS) not accounting for epistemic uncertainty in learned models, which limits exploration in sparse-reward environments, and introduces Epistemic MCTS (EMCTS) to address this, resulting in significantly higher sample efficiency in Assembly code writing and faster solving of hard-exploration benchmarks like Deep Sea compared to baseline methods.
The AlphaZero/MuZero (A/MZ) family of algorithms has achieved remarkable success across various challenging domains by integrating Monte Carlo Tree Search (MCTS) with learned models. Learned models introduce epistemic uncertainty, which is caused by learning from limited data and is useful for exploration in sparse reward environments. MCTS does not account for the propagation of this uncertainty however. To address this, we introduce Epistemic MCTS (EMCTS): a theoretically motivated approach to account for the epistemic uncertainty in search and harness the search for deep exploration. In the challenging sparse-reward task of writing code in the Assembly language {\sc subleq}, AZ paired with our method achieves significantly higher sample efficiency over baseline AZ. Search with EMCTS solves variations of the commonly used hard-exploration benchmark Deep Sea - which baseline A/MZ are practically unable to solve - much faster than an otherwise equivalent method that does not use search for uncertainty estimation, demonstrating significant benefits from search for epistemic uncertainty estimation.