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

View PDF

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.

Subjects:

Machine Learning (cs.LG)

Cite as: arXiv:2603.22273 [cs.LG]

(or arXiv:2603.22273v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.22273

arXiv-issued DOI via DataCite

Submission history

From: Zakaria Mhammedi [view email] [v1] Mon, 23 Mar 2026 17:56:52 UTC (3,793 KB) [v2] Fri, 27 Mar 2026 17:44:46 UTC (3,796 KB) [v3] Mon, 30 Mar 2026 17:14:06 UTC (3,796 KB)