Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration

Zakaria Mhammedi, James Cohan · 2026

Read Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration by Zakaria Mhammedi, James Cohan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22273.txt.

Introduction

Mhammedi and Cohan split exploration away from policy training in reinforcement learning. Standard agents mix the two, using policy machinery just to widen state coverage. The authors argue that this overhead is wasteful. Their method explores with tree search, guided by an uncertainty measure. No reinforcement learning runs during the search phase. They report about ten times wider coverage than intrinsic motivation baselines. The found paths can then be distilled into working policies. Those policies set strong scores on Montezuma's Revenge, Pitfall, and Venture.

Catalog record

CREATORZakaria Mhammedi, James Cohan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106781
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22273

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration Zakaria Mhammedi, James Cohan Abstract The process of discovery requires active exploration—the act of collecting new and informative data. However, efficient autonomous exploration remains a major unsolved problem. The dominant paradigm addresses this challenge by using Reinforcement Learning (RL) to train agents with intrinsic motivation, maximizing a composite objective of extrinsic and intrinsic rewards. We suggest that this approach incurs unnecessary overhead: while policy optimization is necessary for precise task execution, employing such machinery solely to expand state coverage may be inefficient. In this paper, we propose a new paradigm that explicitly separates exploration from exploitation and bypasses RL during the exploration phase. Our method uses a tree-search strategy inspired by the Go-With-The-Winner algorithm, paired with a measure of epistemic uncertainty to systematically drive exploration. By removing the overhead of policy optimization, our approach explores an order of magnitude more efficiently than standard intrinsic motivation baselines on hard Atari benchmarks. Further, we demonstrate that the discovered trajectories can be distilled into deployable policies using existing supervised backward learning algorithms, achieving state-of-the-art scores by a wide margin on Montezuma’s Revenge , Pitfall! , and Venture without relying on domain-specific knowledge. Finally, we demonstrate the generality of our framework in high-dimensional continuous action spaces by solving the MuJoCo Adroit dexterous manipulation and AntMaze tasks in a sparse-reward setting, directly from image observations and without expert demonstrations or offline datasets. To the best of our knowledge, this has not been achieved before for the Adroit tasks. 1 Introduction Reinforcement learning (RL) is a cornerstone of modern artificial intelligence, enabling breakthroughs in complex autonomous systems and, more recently, the post-training and alignment of Large Language Models (LLMs) ( Mnih et al. 2015 ; Silver et al. 2016 ; Silver et al. 2018 ; Ouyang et al. 2022 ; Rafailov et al. 2023 ) . However, these successes often rely on rich feedback, such as expert demonstrations in robotics or preference labels in language model alignment ( Christiano et al. 2017 ; Hester et al. 2018 ; Brohan et al. 2022 ) . In the settings we study, where guidance is scarce, rewards sparse, or the goal is surpassing human performance, learning must go beyond imitation to autonomously generate quality data ( Silver et al. 2016 ; Ecoffet et al. 2021 ) . This requires active exploration : an algorithmic process that deliberately collects informative experience ( Shyam et al. 2019 ; Sekar et al. 2020 ; Eysenbach et al. 2018 ) . In the hardest cases, this amounts to “finding a needle in a haystack,” where a single rare trajectory is the key that unlocks learning. In structured settings like two-player games, self-play facilitates exploration ( Silver et al. 2016 ) . As the agent improves, it probes the boundary of its current policy, gradually expanding its coverage of relevant strategies. Outside of this self-play regime, driving exploration is significantly harder. Even in simple 2D environments, current methods often fail to explore efficiently without domain engineering; Montezuma’s Revenge and Pitfall! remain standard benchmarks that stress-test systematic exploration ( Ecoffet et al. 2019 ; Badia et al. 2020a ; Badia et al. 2020b ; Guo et al. 2022 ) . These failures suggest that we still lack a robust understanding of systematic exploration in data-sparse domains. Progress in this area has implications well beyond games; efficient exploration is a prerequisite for discovery in complex scientific domains. Historically, the primary approach to exploration relies on training agents with intrinsic motivation ( Schmidhuber 1991 ; Oudeyer et al. 2007 ; Barto 2012 ; Houthooft et al. 2016 ; Stadie et al. 2015 ) . In this paradigm, the agent is trained to maximize a composite objective consisting of the extrinsic reward and an intrinsic bonus designed to encourage visiting novel states. In high-dimensional spaces, these bonuses typically use proxies for “visitation frequency,” such as the error of Random Network Distillation ( RND ) or the prediction error of a dynamics model ( Burda et al. 2018 ; Pathak et al. 2017 ; Pathak et al. 2019 ) . While accurate uncertainty estimation is crucial, we argue that driving exploration by maximizing these signals via RL incurs unnecessary complexity; iteratively updating a policy to reach novel states is inherently sample-inefficient, as it requires constantly tracking a non-stationary intrinsic reward signal. Contributions • We propose a new paradigm for autonomous exploration in sparse-reward settings that bypasses intrinsic-reward policy optimization. Our framework pairs a tree-search strategy, inspired by the Go-With-The-Winner ( GWTW ) algorithm ( Aldous and Vazirani 1994 ) , with epistemic uncertainty ( Depeweg et al. 2018 ) to drive exploration; the approach is modular and agnostic to the specific uncertainty metric. The method relies on the ability to reset the environment to previously visited states in order to redistribute computational effort toward the most promising frontiers. By replacing intrinsic-reward policy optimization with uncertainty-guided tree search, our method discovers high-reward trajectories using an order of magnitude fewer environment interactions than standard intrinsic motivation baselines on hard-exploration benchmarks. • We show that supervised backward learning algorithms (e.g., Salimans and Chen 2018 ) can distill the generated trajectories into robust, high-scoring policies. In particular, we achieve state-of-the-art results by a wide margin on Montezuma’s Revenge , Pitfall! , and Venture when not relying on domain-specific knowledge. • We demonstrate the generality of our framework by applying it to high-dimensional continuous action spaces, solving the MuJoCo Adroit dexterous manipulation and AntMaze navigation tasks from pixel observations in a sparse-reward setting without relying on expert demonstrations or offline datasets. To the best of our knowledge, this has not been previously achieved for the Adroit tasks. In both cases, the final distilled policies operate directly from image observations, without accessing privileged state information. Outline The remainder of this paper is organized as follows. Section 2 presents the related work and contextualizes our approach within the literature on separating exploration from exploitation and the usage of environment resets. Section 3 formalizes the problem setting and introduces core components, including the uncertainty estimator and the reset mechanism. Section 4 details our uncertainty-driven tree-search algorithm for exploration, Go-With-Uncertainty ( GowU ). Section 5 presents implementation details, including a distributed architecture for scalable exploration and the specific instantiations of the uncertainty estimator and particle policies. Finally, Section 6 evaluates the method on hard-exploration Atari games and challenging MuJoCo continuous-control tasks, showing efficient exploration and successful policy distillation across all environments. 2 Related Work Efficient exploration remains a central challenge in reinforcement learning. Below we situate our approach within the broader landscape of exploration methods. Intrinsic motivation and latent predictive models A dominant approach to exploration in deep RL is to train a policy to maximize an intrinsic motivation signal that encourages the agent to visit novel states ( Stadie et al. 2015 ; Bellemare et al. 2016 ; Pathak et al. 2019 ; Badia et al. 2020a ) . In high-dimensional settings, these signals are often defined using proxies for novelty such as prediction error ( Pathak et al. 2017 ) , pseudo-counts ( Bellemare et al. 2016 ) , Random Network Distillation ( Burda et al. 2018 ) , or information gain over a

Read the complete text