cs.LGMar 23, 2026

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

Authors: Zakaria Mhammedi, James Cohan

Organizations: Google Research, NYC

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 approach that explicitly decouples exploration from policy optimization and bypasses RL entirely during the exploration phase. Our method uses a tree-search strategy inspired by the Go-With-The-Winner algorithm, paired with a measure of 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 exploration benchmarks. Further, we demonstrate that the trajectories discovered during exploration can be distilled into deployable policies using existing supervised backward learning algorithms, achieving state-of-the-art performance 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.

Figures & tables

Figure 1: Schematic overview of GowU with a single group of particles. The algorithm maintains a population of particles ( p1,p2,p3p_{1},p_{2},p_{3} ) that explore the state space via multi-step rollouts. During an outer step, if a particle reaches a dead state (e.g., p2p_{2} on level one), it is pruned and its state is reset via a Reset to the winner—the alive node maximizing accumulated reward, with epistemic uncertainty used as a tie-breaker. After KK outer steps, a Group Consolidation Reset syncs all particles, including alive particles, to the current winner.
Figure 2: Fully rendered observations from the three hard-exploration Atari games used in our evaluation.
Figure 3: MuJoCo continuous-control tasks used in our evaluation. (a–c) Adroit dexterous manipulation tasks using the 24-DoF ShadowHand. (d) AntMaze navigation task (top-down view).
Figure 4: Processed visual observations as seen by the agent for each MuJoCo task. Each column shows a frame in the observation stack, from the oldest (Frame −3-3 ) to the most recent (Frame 00 ). For AntMaze, the “Frame top” column shows the global top-down view of the maze; during Phase I (exploration), only this top-down view is used. See Section 5 for an overview and Appendix E for full details on the observation processing pipeline.
GameOursGo-ExploreRNDMEMEBYOL-Hind.
Exploration (GowU)Robustification
Montezuma98,249 ±\pm 18,102196,312 ±\pm 49,67043,7918,1529,429∼14,517∗{\sim}14{,}517^{*}
Pitfall54,440 ±\pm 14,817101,972 ±\pm 2,2266,945−3-37,821∼16,211∗{\sim}16{,}211^{*}
Venture5,012 ±\pm 2,6786,436 ±\pm 1,5042,2811,8592,583∼2,328∗{\sim}2{,}328^{*}
Table 1: Comparison of GowU against baselines on hard-exploration Atari games. For GowU , we report the mean ( ±\pm standard deviation) cumulative reward along the discovered demonstrations across 100 exploration seeds after at most 600M frames per seed, and the mean ( ±\pm standard deviation) policy score across 10 Phase II runs (see Table 3 for full statistics). All results use sticky actions ( p=0.25p=0.25 ), except Go-Explore , which uses a deterministic environment during exploration. Baseline numbers are taken from the respective papers. ∗ BYOL-Hindsight values are approximate, extracted visually from Figure 19 in the original paper.
Figure 5: Phase I exploration on Atari: GowU vs. Go-Explore ( Ecoffet et al., 2021 ) . Mean cumulative reward ( ±\pm std) across 100 seeds as a function of game frames. Go-Explore curves are approximated from Extended Data Fig. 2 in ( Ecoffet et al., 2021 ) .
TaskMeanStdMedianMinMax
Hammer26,79713,98324,1424,71373,306
Door272,688200,824224,33817,086943,066
Relocate275,372839,81569,5462,1378,015,087
AntMaze10,161,2726,697,7368,517,1863,078,41248,332,904
Table 2: MuJoCo Phase I exploration efficiency: number of environment frames until a task-completing trajectory is first discovered, across 100100 GowU seeds.
GameMeanStdMedianWorst-RunBest-Run
Montezuma196,31249,670189,151130,501263,111
Pitfall101,9722,226102,29697,090105,589
Venture6,4361,5046,1774,7439,357
Table 3: Detailed Phase II robustification statistics for GowU on Atari. We conduct 10 Phase II runs per game, where each run trains on a unique set of 10 demonstrations, each from a different exploration run. Each Phase II run is repeated with 5 random seeds, and its result is averaged over the seeds. We report the mean, standard deviation, median, worst-run, and best-run policy scores across the 10 runs.
TaskMeanStdMedianWorst-RunBest-Run
Hammer1.0000.0011.0000.9971.000
Door0.9810.0060.9810.9720.992
Relocate0.9520.0170.9470.9330.973
AntMaze0.9610.0190.9640.9160.980
Table 4: Phase II success rate statistics for MuJoCo tasks. We conduct 10 Phase II runs per task, where each run trains on a unique set of 10 demonstrations and is repeated with 5 random seeds, and its result is averaged over the seeds. We report the mean, standard deviation, median, worst-run, and best-run success rates across the 10 runs.
Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

ParameterMontezumaPitfallVentureMuJoCo
Groups ( MM )44416
Particles per group ( NN )3232328
outer steps range ( [Kmin⁡,Kmax⁡][K_{\min},K_{\max}] )[10,20][10,20][10,20][10,20][6,16][6,16][20,40][20,40]
inner steps range ( [Tmin⁡,Tmax⁡][T_{\min},T_{\max}] )[5,15][5,15][10,20][10,20][10,20][10,20][3,4][3,4]
rollback range [kmin⁡,kmax⁡][k_{\min},k_{\max}][1, 3][1, 4][1, 12][1,20]
Appendix
Table 5: Population management hyperparameters for GowU . The MuJoCo column applies to all continuous-control tasks (AntMaze and Adroit).
Metric100M frames200M frames300M frames400M frames
Clock runtime (hours)4.53±1.844.53\pm 1.846.98±1.926.98\pm 1.929.01±2.589.01\pm 2.5810.71±3.3510.71\pm 3.35
Mean score48,444±14,41748{,}444\pm 14{,}41776,014±16,62676{,}014\pm 16{,}62689,485±18,76089{,}485\pm 18{,}76098,249±18,10298{,}249\pm 18{,}102
RND SGD steps0.77M±0.28M0.77\text{M}\pm 0.28\text{M}1.38M±0.39M1.38\text{M}\pm 0.39\text{M}1.86M±0.57M1.86\text{M}\pm 0.57\text{M}2.28M±0.81M2.28\text{M}\pm 0.81\text{M}
Appendix
Table 6: Computational cost of GowU Phase I on Montezuma’s Revenge , averaged over 100 seeds.
ParameterValue
OptimizerAdam
Learning Rate1×10−41\times 10^{-4}
Discount Factor ( γ\gamma )0.999
GAE Lambda ( λ\lambda )0.95
Unroll Length128
Batch Size128 (64 for AntMaze)
Appendix
Table 7: PPO Hyperparameters (defaults; see Section B.3 for environment-specific overrides).
ParameterValue
Required Success Rate ( SreqS_{\text{req}} )0.2
Completion Threshold ( Sreq,beginS_{\text{req,begin}} )0.95
Start delta window ( Δ\Delta )25 (3 for Adroit)
Min Rollouts for Update ( NupdateN_{\text{update}} )32
Decrease Multipliers ( αdec,βdec\alpha_{\text{dec}},\beta_{\text{dec}} )0.25, 0.75 ( 13\tfrac{1}{3} , 13\tfrac{1}{3} for Adroit)
Increase Multipliers ( αinc,βinc\alpha_{\text{inc}},\beta_{\text{inc}} )0.5, 1.0 ( 13\tfrac{1}{3} , 13\tfrac{1}{3} for Adroit)
Appendix
Table 8: Backward Algorithm Configuration (defaults; see Section B.3 for environment-specific overrides).
TaskMedianStdMax
Hammer9,876,8092,340,95219,878,384
Door27,629,35914,928,47854,589,532
Relocate221,653,220146,455,143827,483,942
AntMaze119,160,55784,845,527667,819,039
Appendix
Table 9: MuJoCo Phase II training budget: total environment frames consumed per task, across 10 runs (each averaged over 5 seeds).
Figure 6: Processed visual observations as seen by the agent for each MuJoCo task. Each column shows a frame in the observation stack, from the oldest (Frame −3-3 ) to the most recent (Frame 00 ). For AntMaze, the “Frame top” column shows the global top-down view of the maze; during Phase I (exploration), only this top-down view is used. See Section 5 for an overview and Appendix E for full details on the observation processing pipeline.
Figure 7: Ablation studies on Montezuma’s Revenge . Mean cumulative reward ( ±\pm std) across seeds. (a) Disabling uncertainty-based winner selection causes exploration to fail; disabling group consolidation degrades performance. (b) 22 and 44 groups perform similarly; 11 group is worst; 88 groups improve over 11 but underperform 22 and 44 . (c) Per-iteration hyperparameter randomization yields robust performance without tuning.
Figure 8: Frame-by-frame illustration of the middle room bug in Montezuma’s Revenge . The agent starts on the rope (Frame −4-4 ), jumps left, and hits the skull platform (Frame 00 ), losing a key and collecting an unintended reward.
More in this topic

Uncertainty-Aware Exploration

See all 23 papers

Explore similar work

CardsList

  1. Look Before You Leap: Autonomous Exploration for LLM Agents

    May 15, 2026Ziang Ye, Wentao Shi, Yuxin Liu +6RL ExplorationLLM Agents

    University of Science and Technology of China · Meituan

  2. Improved Bounds for Reward-Agnostic and Reward-Free Exploration

    Feb 18, 2026Oran Ridel, Alon CohenRL ExplorationReward-Free RL

    Department of Engineering, Tel Aviv University, Tel Aviv, Israel. · Google Research, Tel Aviv, Israel.

  3. Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments

    Aug 22, 2026Khang Luong, Nam Nguyen, Hoang Ta +2Uncertainty-Aware ExplorationRL Exploration

    Hanoi University of Science and Technology, Hanoi, Vietnam · Quantum AI & Cyber Security Institute, FPT Corporation, Vietnam.