Abstract
Reinforcement learning in sparse-reward navigation environments with expensive and limited interactions is challenging and poses a need for effective exploration. Motivated by complex navigation tasks that require real-world training (when cheap simulators are not available), we consider an agent that faces an unknown distribution of environments and must decide on an exploration strategy. It may leverage a series of training environments to improve its policy before it is evaluated in a test environment drawn from the same environment distribution. Most existing approaches focus on fixed exploration strategies, while the few that view exploration as a meta-optimization problem tend to ignore the need for cost-efficient exploration. We propose a cost-aware Bayesian optimization approach that efficiently searches over a class of dynamic subgoal-based exploration strategies. The algorithm adjusts a variety of levers -- the locations of the subgoals, the length of each episode, and the number of replications per trial -- in order to overcome the challenges of sparse rewards, expensive interactions, and noise. An experimental evaluation demonstrates that the new approach outperforms existing baselines across a number of problem domains. We also provide a theoretical foundation and prove that the method asymptotically identifies a near-optimal subgoal design.
Introduction
Reinforcement Learning (RL) typically struggles in "sparse-reward" environments—scenarios where an agent only receives a signal after completing a long sequence of correct actions. Standard exploration techniques, such as random walks, are often too slow to discover these rewards. While subgoals can guide an agent, identifying the optimal set of subgoals is a non-trivial task.
Existing meta-learning methods for exploration often assume access to cheap simulators. However, in real-world robotics, every interaction is costly in terms of time, energy, and hardware wear. This research introduces Bayesian Exploratory Subgoal Design (BESD), a framework designed for cost-efficient meta-learning that finds optimal exploration strategies while minimizing environmental interactions.
Bayesian Exploratory Subgoal Design (BESD)
BESD treats the search for subgoals as a Bayesian Optimization (BO) problem. The framework operates by augmenting the Markov Decision Process (MDP) with sequential subgoals. The agent receives intrinsic rewards for reaching these subgoals in a specific order, effectively "stitching" together a path through the sparse-reward space.
Optimization Levers
Unlike standard BO, which typically only tunes design parameters, BESD controls the training process itself through three primary levers:
- Subgoal Locations ($\theta$): The spatial coordinates of the targets.
- Episode Length ($\tau$): The number of steps allowed per training trial.
- Replications ($q$): The number of times a trial is repeated to mitigate environmental noise.
Cost-Aware Acquisition
The core innovation is a modified Knowledge Gradient acquisition function. Instead of merely seeking the most informative next trial, BESD evaluates the information gain per unit of interaction cost. This allows the algorithm to dynamically decide whether to run many short, inexpensive trials or a single long, expensive one, optimizing the use of the interaction budget.
Experimental Evaluation
The authors evaluated BESD across several challenging domains, including Windy Gridworlds, Treasure-in-Room, Mountain Car, and Key-Door environments. These tasks require complex sequences of actions, such as picking up a key to unlock a door, where the key's location varies significantly between instances.
Key Results
- Efficiency: BESD consistently outperformed baselines like Hyperband and standard BO (Expected Improvement, LCB), achieving higher performance with lower total interaction costs.
- Test-Time Speedup: Agents trained with BESD-discovered subgoals solved test environments 3x to 20x faster than agents learning from scratch.
- Bottleneck Discovery: The algorithm naturally learned to place subgoals at critical "bottlenecks," such as doorways or near essential items, facilitating efficient navigation.
Discussion and Future Work
While BESD significantly reduces environmental interaction costs, it introduces computational overhead due to the complexity of the Knowledge Gradient calculation. Future work aims to address this by optimizing the acquisition function's performance. Additionally, extending the framework to be "task-aware"—where subgoals are conditioned on specific sensor readings of the current environment instance—could further enhance its versatility.
In conclusion, BESD provides a theoretically grounded and practically efficient method for discovering exploration strategies in sparse-reward settings, making RL more viable for real-world applications where interaction is at a premium.
Summary updated