Abstract: An agent that has well understood the environment should be able to apply its skills for any given goals, leading to the fundamental problem of learning the Universal Value Function Approximator (UVFA). A UVFA learns to predict the cumulative rewards between all state-goal pairs. However, empirically, the value function for long-range goals is always hard to estimate and may consequently result in failed policy. This has presented challenges to the learning process and the capability of neural networks. We propose a method to address this issue in large MDPs with sparse rewards, in which exploration and routing across remote states are both extremely challenging. Our method explicitly models the environment in a hierarchical manner, with a high-level dynamic landmark-based map abstracting the visited state space, and a low-level value network to derive precise local decisions. We use farthest point sampling to select landmark states from past experience, which has improved exploration compared with simple uniform sampling. Experimentally we showed that our method enables the agent to reach long-range goals at the early training stage, and achieve better performance than standard RL algorithms for a number of challenging tasks.
The Challenge of Long-Range Goals
In a Universal Markov Decision Process (UMDP), an agent is tasked with reaching any goal state from any starting state. The standard approach involves using a Universal Value Function Approximator (UVFA) to estimate the "distance" or cumulative reward between every possible state-goal pair. However, UVFAs suffer from a "curse of dimensionality." As environments grow, the number of state-goal pairs explodes, and neural networks often struggle to extrapolate to distant, unseen goals. This leads to wild estimations and failed policies for long-horizon tasks. The authors argue that expecting a single network to memorize the global topology of a complex environment is a daunting task that frequently results in poor performance.
Methodology: A Hierarchical Approach
The proposed framework addresses these challenges by splitting the problem into global planning and local control. This hierarchical structure relieves the neural network of the burden of global topological memorization, allowing it to specialize in local transitions.
- Local UVFA with HER: The system first trains a standard goal-conditioned policy using Hindsight Experience Replay (HER), restricted to "local" goals reachable within a few steps to ensure high accuracy in the immediate neighborhood.
- Landmark Sampling: To build a global map, landmark states are sampled from the agent’s past experience using Farthest Point Sampling (FPS). This technique selects states that are as far apart as possible, effectively pushing the boundaries of the known map and aiding exploration.
- Graph Construction: Landmarks become nodes in a graph. Edges are drawn between landmarks if the local UVFA determines they are within a reliable reach distance. Edge weights represent the estimated distance from the UVFA.
- High-Level Planning: For distant goals, the agent uses the Bellman-Ford algorithm on the landmark graph to find a sequence of subgoals. The local UVFA then navigates between these landmarks until the final goal is reached.
Key Results and Insights
The method was evaluated across diverse environments, including discrete mazes (FourRoom), continuous control tasks (MuJoCo-based), and complex navigation/locomotion tasks (AntMaze).
- Superior Sample Efficiency: In a large 24x24 AntMaze, the proposed method achieved a 0.5 success rate within 2 million steps under sparse rewards, while competing hierarchical methods like HIRO and HAC failed entirely.
- Accuracy and Robustness: In the FourRoom environment, the landmark-based approach showed significantly lower Mean Distortion Error (MDE) in distance estimation compared to standard DQN+HER, particularly in early training stages. Ablation studies confirmed robustness to the number of landmarks and connection thresholds.
- Exploration Engine: By picking landmarks at the edges of visited space, FPS naturally encourages the agent to explore the "frontier" of its environment, overcoming the overestimation issues common in standard Q-learning for distant goals.
Limitations and Future Work
While effective, the method currently requires manual tuning for parameters like the "vicinity" threshold and edge-clipping values. It also assumes the existence of a good state representation, as it does not yet incorporate components for learning complex embeddings from raw pixels. Future work may address these areas, as well as the potential for accumulated errors over very long sequences of landmarks in extremely high-dimensional or complex topologies.
Summary updated