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
May 15, 2026

Look Before You Leap: Autonomous Exploration for LLM Agents

Large language model based agents often fail in unfamiliar environments due to premature exploitation: a tendency to act on prior knowledge before acquiring sufficient environment-specific information. We identify autonomous exploration as a critical yet underexplored capability for building adaptive agents. To formalize and quantify this capability, we introduce Exploration Checkpoint Coverage, a verifiable metric that measures how broadly an agent discovers key states, objects, and affordances. Our systematic evaluation reveals that agents trained with standard task-oriented reinforcement learning consistently exhibit narrow and repetitive behaviors that impede downstream performance. To address this limitation, we develop a training strategy that interleaves task-execution rollouts and exploration rollouts, with each type of rollout optimized by its corresponding verifiable reward. Building on this training strategy, we propose the Explore-then-Act paradigm, which decouples information-gathering from task execution: agents first utilize an interaction budget to acquire grounded environmental knowledge, then leverage it for task resolution. Our results demonstrate that learning to systematically explore is imperative for building generalizable and real-world-ready agents.

Ziang Ye, Wentao Shi, Yuxin Liu +6

University of Science and Technology of China · Meituan

RL ExplorationLLM AgentsLLM Agent TrainingRL for LLM Agents
AskPDF
Feb 18, 2026

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration aims to enable εε-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets εε-optimality for rewards drawn from a small finite class. In the reward-agnostic setting, Li, Yan, Chen, and Fan achieve minimax sample complexity, but only for restrictively small accuracy parameter εε. We propose a new algorithm that significantly relaxes the requirement on εε. Our approach is novel and of technical interest by itself. Our algorithm employs an online learning procedure with carefully designed rewards to construct an exploration policy, which is used to gather data sufficient for accurate dynamics estimation and subsequent computation of an εε-optimal policy once the reward is revealed. Finally, we establish a tight lower bound for reward-free exploration, closing the gap between known upper and lower bounds.

Oran Ridel, Alon Cohen

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

RL ExplorationReward-Free RLSample-Efficient RL
AskPDF
Aug 22, 2026

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

We propose Variance Driven Exploration (VarDE), a principled approach for pure exploration in highly stochastic environments, where the exploration process is dominated by stochastic variance. VarDE is built on a fundamental principle: sampling effort should be allocated to minimize the uncertainty of the final decision. We formalize the uncertainty of the final decision through a smooth decision function and derive allocation rules that explicitly capture how stochastic noise in individual components affects the reliability of the final output. We apply this methodology to three core problems of pure exploration -- Best Arm Identification (BAI), Monte Carlo Tree Search (MCTS), and Best-Policy Identification (BPI) -- with theoretical guarantees on variance decay and simple regret. Empirically, we demonstrate consistent and significant improvements of VarDE over existing methods, with especially strong gains in highly stochastic environments.

Khang Luong, Nam Nguyen, Hoang Ta +2

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

Uncertainty-Aware ExplorationRL ExplorationBest-Arm IdentificationMonte Carlo Tree Search
AskPDF