First-Explore, then Exploit: Meta-Learning to Solve Hard Exploration-Exploitation Trade-Offs

Ben Norman, Jeff Clune

TL;DR

Current meta-reinforcement learning (meta-RL) algorithms often fail when exploration requires forgoing immediate rewards—a common scenario in complex, real-world tasks. First-Explore solves this by decoupling exploration and exploitation into two separate policies, allowing agents to learn sophisticated search strategies that "deceptive" reward structures would otherwise suppress.

What Problem Does This Paper Address?

In reinforcement learning, agents must balance exploration (trying new things to learn) and exploitation (using what they know to get rewards). Meta-RL aims to automate this balance by training agents that can adapt to new environments within a few episodes.

However, the authors identify a critical failure mode in state-of-the-art "cumulative-reward" meta-RL methods (like RL², VariBAD, and HyperX). These methods try to maximize the total reward across a sequence of episodes. If an environment is "deceptive"—meaning exploration is costly in the short term and only pays off if the agent already knows how to exploit the results—the agent often learns to avoid exploration entirely. It gets stuck in a local optimum: doing nothing is better than exploring and failing to exploit. This is a "chicken and egg" problem: you can't learn to explore without reliable exploitation, but you can't learn to exploit without exploring first.

Methods

The core innovation is the First-Explore framework, which breaks the single-policy paradigm. Instead of one policy doing everything, First-Explore trains two:

  1. The Exploit Policy ($\pi_{exploit}$): Trained solely to maximize reward in a single episode, given the context of what has been discovered so far.
  2. The Explore Policy ($\pi_{explore}$): Trained solely to provide the most useful information to the exploit policy. It is incentivized by how much the exploit policy's performance improves after an exploration episode.
The First-Explore framework: training separate policies and then combining them.

During training, these policies are interleaved. Because $\pi_{explore}$ isn't penalized for forgoing immediate rewards, it can freely learn complex search strategies. After training, the system enters a $k$-selection phase, where it determines the optimal number of episodes ($k$) to spend exploring before switching to pure exploitation for the remainder of the sequence. Both policies are implemented using a GPT-2 style causal transformer to handle long-term memory across episodes.

Datasets

The authors evaluated First-Explore on three domains designed to test "deceptive" exploration:

  • Bandits with One Fixed Arm: A multi-armed bandit where one arm gives a guaranteed, above-average (but sub-optimal) reward. To find the best arm, the agent must risk getting zero reward, which stymies standard meta-RL.
  • Dark Treasure Rooms: A grid-world where an agent moves blindly in the dark. Most locations contain "traps" (negative reward), and only a few have "treasures." The agent must visit traps to map the room before it can reliably hit treasures.
  • Ray Maze: A complex 3D-style navigation task using lidar observations. The agent must navigate a maze to find goal locations that have a high probability of being traps.

Key Insights and Ideas

  • Decoupling is Key: By separating the objective of exploration from the objective of exploitation during training, the agent avoids the "exploration-avoidance" trap. The explore policy becomes a dedicated "information gatherer."
  • Grounded Exploration: Unlike methods that use "intrinsic curiosity" (which might explore useless details), First-Explore's exploration is "grounded"—it only cares about information that actually helps the exploit policy get more reward.
  • Overcoming the Local Optimum: Standard methods converge to "never move" or "always take the safe arm" because early in training, their unrefined exploitation makes exploration look like a net loss. First-Explore bypasses this by ignoring the cost of exploration during the learning phase.

Key Results

First-Explore significantly outperformed SOTA meta-RL controls across all deceptive domains:

  • Bandits: It achieved roughly 2x the total reward of RL² in the deceptive case. While RL² often settled for the "safe" arm, First-Explore learned to find the optimal arm quickly.
  • Dark Treasure Rooms: First-Explore achieved 10x more total reward than controls. The controls learned to "stay still" to avoid traps, while First-Explore learned to map the room despite the initial negative rewards.
  • Ray Maze: In this high-dimensional task, First-Explore achieved a mean reward of 0.47, while most controls stayed at 0 (learning to spin in place to avoid traps).
Performance on the Bandit domain. First-Explore (green) transitions to optimal reward much faster and more reliably than RL² (fuchsia).

Limitations and Future Work

  • Myopic Exploration: Currently, $\pi_{explore}$ only tries to improve the next exploit episode. It doesn't explicitly learn to explore in a way that enables further exploration later (e.g., finding a key to open a door to a new area).
  • Safety: Because the explore policy is encouraged to ignore immediate negative rewards, it could be dangerous in real-world physical systems (e.g., a robot breaking itself to "see what happens").
  • Switching Logic: The current version uses a fixed $k$ episodes for exploration. Future work could involve a "learned classifier" to decide dynamically when enough information has been gathered to switch to exploitation.

Summary updated

Abstract

Standard reinforcement learning (RL) agents never intelligently explore like a human (i.e. taking into account complex domain priors and adapting quickly based on previous exploration). Across episodes, RL agents struggle to perform even simple exploration strategies, for example systematic search that avoids exploring the same location multiple times. This poor exploration limits performance on challenging domains. Meta-RL is a potential solution, as unlike standard RL, meta-RL can learn to explore, and potentially learn highly complex strategies far beyond those of standard RL, strategies such as experimenting in early episodes to learn new skills, or conducting experiments to learn about the current environment. Traditional meta-RL focuses on the problem of learning to optimally balance exploration and exploitation to maximize the cumulative reward of the episode sequence (e.g., aiming to maximize the total wins in a tournament -- while also improving as a player). We identify a new challenge with state-of-the-art cumulative-reward meta-RL methods. When optimal behavior requires exploration that sacrifices immediate reward to enable higher subsequent reward, existing state-of-the-art cumulative-reward meta-RL methods become stuck on the local optimum of failing to explore. Our method, First-Explore, overcomes this limitation by learning two policies: one to solely explore, and one to solely exploit. When exploring requires forgoing early-episode reward, First-Explore significantly outperforms existing cumulative meta-RL methods. By identifying and solving the previously unrecognized problem of forgoing reward in early episodes, First-Explore represents a significant step towards developing meta-RL algorithms capable of human-like exploration on a broader range of domains.
BibTeX
@inproceedings{norman2024first,
  author = {Ben Norman and Jeff Clune},
  title = {{First-Explore, then Exploit: Meta-Learning to Solve Hard Exploration-Exploitation Trade-Offs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=AhjTu2aiiW},
}
Figure