Overview
An agent that truly understands its environment should be able to apply its skills to reach any given goal. In Reinforcement Learning (RL), this is the fundamental problem of learning a Universal Value Function Approximator (UVFA), which predicts the cumulative rewards between all possible state-goal pairs.
However, standard UVFAs struggle significantly with "long-horizon" tasks. When a goal is very far from the starting point, the value function is notoriously hard to estimate, often resulting in a failed policy. This paper introduces a hierarchical approach to Universal Goal Reaching that overcomes this limitation by combining a high-level landmark-based map with a low-level RL policy.
The Challenge of Long-Range Goals
While techniques like Hindsight Experience Replay (HER) help agents learn from failure by pretending a failed state was the intended goal, they still falter across vast distances. The core challenge is that neural networks are poor at extrapolating distances to distant, unseen goals.
As the distance between states increases, the number of possible state-goal pairs grows polynomially. It becomes nearly impossible for a single network to memorize the entire value landscape. Essentially, the network gets "lost" when trying to plan across a large environment because its global estimates become noisy and unreliable.
The Proposed Method: Hierarchical Landmark Mapping
To address the vanishing gradient and extrapolation issues of deep RL, the authors propose a hybrid system. It treats the environment as a low-dimensional manifold and builds a topological map of it, offloading global navigation to a graph-based planner.
The system operates through four key steps:
- Local UVFA with HER: The system first trains a standard goal-conditioned RL agent (using DQN or DDPG with HER). Crucially, this agent is only expected to be accurate for local goals (nearby states), acting as a reliable local compass rather than a global map.
- Landmark Sampling: To build a map, the system samples states from the agent's experience replay buffer. It uses Farthest Point Sampling (FPS), a technique that selects points as far away from each other as possible. This actively pushes landmarks toward the boundaries of the explored space, naturally driving exploration.
- Graph Construction: These sampled landmarks become nodes in a graph. An edge is created between two landmarks if the local UVFA predicts the distance between them is below a certain threshold ($\tau$). The edge weight is the predicted distance.
- Hierarchical Planning: When given a distant goal, the agent uses the graph to find the shortest path of landmarks to the goal (using algorithms like Bellman-Ford). It selects the next landmark in the path as a "subgoal," uses the low-level policy to reach that subgoal, and repeats the process until the final goal is reached.
Key Results and Performance
The researchers evaluated their method on several challenging continuous control and navigation environments, including classic discrete navigation (FourRoom), robotic manipulation (FetchPush), and complex locomotion (AntMaze).
- Superiority in Long-Range Tasks: On complex tasks like the AntMaze (where a quadruped "ant" must navigate a U-shaped maze), standard HER fails to reach the goal almost entirely. In contrast, the landmark-based method achieves a high success rate early in training.
- Sample Efficiency: The agent reaches long-range goals much earlier in the training process because it can "stitch together" local successes into a cohesive global plan.
- Accurate Distance Estimation: The landmark-based planner provides much more accurate distance-to-goal estimates. As seen in the FourRoom evaluations, it yields a significantly lower Mean Distortion Error compared to a pure DQN/HER approach, which consistently underestimates distances to far-off goals.
- Robustness: The method proved robust to the choice of hyperparameters, such as the number of landmarks and the distance threshold ($\tau$), provided the underlying graph remained connected.
Limitations and Future Work
While highly effective, the approach does have limitations. The distance threshold ($\tau$) used to connect landmarks currently requires manual tuning; if it's too small, the graph disconnects, but if it's too large, the edges rely on unreliable long-range UVFA estimates. Additionally, because the agent moves from landmark to landmark, small errors in the low-level policy can accumulate, potentially causing the agent to miss narrow passages.
Finally, the method relies on having a decent state representation. In environments with purely visual inputs or extremely complex topological structures, learning a useful embedding for landmarks remains an open challenge for future research.
Summary updated