Abstract
Autonomous exploration is a critical capability for reinforcement learning (RL) agents operating in environments with sparse or absent rewards. This paper introduces META-EXPLORE, a meta-algorithm designed to transform standard online RL algorithms—specifically those minimizing regret—into robust exploration tools. By treating existing algorithms as black boxes, META-EXPLORE enables an agent to navigate unknown Markov Decision Processes (MDPs) and reach all reachable states within a specified radius. We provide theoretical guarantees on sample complexity and demonstrate through simulations that improvements in the underlying RL algorithm directly translate to more efficient exploration.
Introduction
In traditional RL, agents are typically guided by extrinsic rewards. However, many real-world tasks feature "sparse" rewards or none at all, requiring agents to explore autonomously to build a map of the environment or a library of skills. The challenge lies in efficiently navigating an MDP with a potentially large state space to discover all reachable states. While specialized exploration algorithms exist, this work explores whether the extensive research in regret-minimizing RL algorithms can be generalized to solve the exploration problem.
The META-EXPLORE Framework
META-EXPLORE operates as a wrapper around any standard online RL algorithm. The process is divided into three iterative phases:
- State Discovery: Upon reaching a new state, the agent explores its immediate neighborhood by executing all possible actions multiple times to determine transition dynamics.
- Target Selection: The agent selects a "candidate" state from the frontier of discovered but unverified states.
- Target Evaluation (Induced MDP): To utilize a black-box RL algorithm (which requires rewards), the authors construct an "induced MDP." In this sub-problem, reaching the target state is the only way to avoid a penalty (loss). If the black-box algorithm successfully reaches the target within a time limit, the state is added to the "known" set.
Because the black-box algorithm is run multiple times, the framework includes a method to "stitch" these different runs together into a single, reliable navigation policy.
Experimental Evaluation
The authors evaluated META-EXPLORE using simulated tertiary tree environments. In these environments, each node has three children, and transitions are stochastic. The agent's goal is to discover all nodes within a specific depth.
Two settings were tested, differing in the degree of stochasticity in the transitions (see Figure 3). Setting 2 represents a more deterministic environment than Setting 1, allowing for a comparison of how transition dynamics affect exploration efficiency.
Results and Discussion
The theoretical analysis provides an upper bound on sample complexity that scales with the regret bound of the chosen black-box algorithm. Empirically, the algorithm was tested using UCRL2 and its improved version, UCRL2b.
As shown in Figure 1, the empirical sample complexity is significantly lower than the theoretical upper bounds, suggesting that the algorithm is highly effective in practice. Furthermore, using UCRL2b as the black box resulted in better performance than UCRL2, confirming that advancements in standard RL algorithms directly enhance exploration efficiency via the META-EXPLORE framework. This "generality" allows the exploration tool to automatically benefit from future improvements in regret-minimizing algorithms.
Conclusion
META-EXPLORE provides a generalized framework for autonomous exploration by repurposing regret-minimizing RL algorithms. While there is a slight efficiency overhead compared to hand-tuned exploration methods, its ability to leverage any black-box RL algorithm makes it a versatile tool. Future work includes extending the framework to non-stationary environments and multi-goal settings such as Stochastic Shortest Path problems.
Summary updated