Mapping State Space using Landmarks for Universal Goal Reaching

Zhiao Huang, Fangchen Liu, Hao Su

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.

Hierarchical planning using a landmark-based graph

The system operates through four key steps:

  1. 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.
  2. 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.
  3. 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.
  4. 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).

Performance metrics and graph visualization in the FourRoom environment
  • 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

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.
BibTeX
@inproceedings{huang2019mapping,
  author = {Zhiao Huang and Fangchen Liu and Hao Su},
  title = {{Mapping State Space using Landmarks for Universal Goal Reaching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=IWpKhE7Dtj},
}
Figure