Paper       Project Page       Datasets

Overview

Adaptive Quasimetric Mapping (AQM) learns a time-to-reach quasimetric from offline data to build a sparse topological graph for goal-conditioned navigation, enabling efficient planning and test-time replanning under topology changes.

Abstract :

Goal-Conditioned Reinforcement Learning aims to design agents that can reach specified goals, notably from previously collected trajectories in the offline setting. In this context, graph-based approaches have been proposed to mitigate compounding value-estimation errors in long-horizon navigation tasks. However, existing approaches typically rely on dense keypoint coverage of the dataset support, resulting in computationally expensive planning. Moreover, they lack explicit mechanisms to adapt to topological changes (e.g., new obstacles), hindering deployment in live applications such as video game environments. To address these two shortcomings, we introduce Adaptive Quasimetric Mapping (AQM), an offline framework leveraging a “time-to-reach” quasimetric learned from the available data. Crucially, it builds a sparse cover of the dataset support, as a greedy approximation to a dominating set problem. At test-time, the resulting graph is carefully pruned by comparing the observed edge traversal time against a time-to-reach budget derived from the quasimetric, thus enabling zero-shot replanning. Empirically, we evaluate AQM on navigation tasks ranging from a classical to a video-game-like benchmark evaluating adaptation across tasks. We show that AQM achieves competitive performance while requiring up to 100× fewer keypoints than prior approaches, hence demonstrating the relevance of topological abstraction for goal-conditioned navigation.

Learning Pipeline :

1. Getting Started

Follow these tutorials to install the library on : Linux ( Ubuntu 22.04 ).

2. Using the Library

We consider the experimental setup described in the given tutorial.

2.A. Run Training

In the single tasks an agent is trained and evaluated on the same environment.

Read the configuration file associated to the config-name (cn) to see which variables are available and can be modified.

To train :

cd ~/workspace/adaptive-quasimetric-mapping/experiments/1_run/
python train.py -cp=linux/aqm -cn=antmaze algo_cfg.aqm_repel_range=10.0 algo_cfg.train_save_epochs=[800000,900000,1000000]

2.B. Visualize Trained Agent

To visualize agent for a fixed configuration at a given gradient step (if saved) :

cd ~/workspace/adaptive-quasimetric-mapping/experiments/1_run/
python visualize.py-cp=linux/aqm -cn=antmaze algo_cfg.aqm_repel_range=10.0 algo_cfg.train_save_epochs=[800000,900000,1000000] eval_cfg.visu_at_step=1000000 eval_cfg.visu_task=0

3. Environments & Datasets

3.A. OGBench

See additional resources below for more informations.

OGBench - AntMaze Agent & Maze Configurations :

3.B. Continual NavBench

See additional resources below for more informations.

Continual NavBench - Visualization :

4. Benchmark (Main Results)

4.A. How effective is AQM on navigation tasks ? :

Dataset Type	Dataset	GCBC	GCIQL	QRL	CRL	HILP	HIQL	SAW	GAS	AQM
Locomotion	antmaze-medium-navigate	33 ± 6	75 ± 5	82 ± 8	95 ± 1	96 ± 1	95 ± 1	97 ± 1	96 ± 1	98 ± 1
	antmaze-large-navigate	24 ± 3	33 ± 5	75 ± 4	86 ± 5	87 ± 4	90 ± 2	90 ± 2	93 ± 1	94 ± 2
	antmaze-giant-navigate	0 ± 0	0 ± 0	14 ± 4	15 ± 6	53 ± 3	67 ± 6	70 ± 4	78 ± 3	88 ± 2
Stitching	antmaze-medium-stitch	43 ± 8	27 ± 7	67 ± 11	57 ± 8	96 ± 1	92 ± 3	95 ± 2	98 ± 1	98 ± 2
	antmaze-large-stitch	2 ± 4	10 ± 3	20 ± 2	14 ± 6	34 ± 3	72 ± 5	64 ± 9	97 ± 1	95 ± 2
	antmaze-giant-stitch	0 ± 0	0 ± 0	0 ± 0	0 ± 0	0 ± 0	1 ± 1	1 ± 2	88 ± 4	90 ± 3
Exploratory	antmaze-medium-explore	3 ± 3	12 ± 1	1 ± 1	1 ± 2	40 ± 7	32 ± 3	27 ± 7	98 ± 0	99 ± 1
	antmaze-large-explore	0 ± 0	1 ± 1	0 ± 1	0 ± 0	2 ± 2	3 ± 4	5 ± 4	94 ± 3	94 ± 5

Baseline results are reported from GAS (2025). Results are averaged over 4 seeds (50 rollouts per goal). Bold values indicate performance with 95% reach of the top performing method.

4.B. Does AQM solve the GAS scaling bottleneck ? :

Dataset	Method	# Nodes	Success (%)
antmaze-giant-navigate	GAS	4286	74 ± 3
	GAS	978	77 ± 3
	GAS	431	71 ± 2
	GAS	268	64 ± 2
	AQM	158	88 ± 2
	AQM	109	86 ± 2
	AQM	67	83 ± 1
antmaze-giant-stitch	GAS	12901	81 ± 3
	GAS	1966	88 ± 4
	GAS	688	80 ± 4
	GAS	375	69 ± 2
	AQM	163	90 ± 3
	AQM	113	88 ± 3
	AQM	71	82 ± 1
antmaze-large-explore	GAS	15143	98 ± 1
	GAS	2499	94 ± 3
	GAS	1126	88 ± 8
	GAS	679	90 ± 4
	AQM	177	91 ± 7
	AQM	114	94 ± 5
	AQM	68	88 ± 6

Comparison of performance/cost trade-offs between AQM and GAS (2025) methods.

4.C. To what extent does AQM handle test-time adaptation in changing environments ? :

Performances are presented as heatmaps where rows represent the training environment and columns represent the evaluation environment. The diagonal values represent standard evaluation setup (training and evaluation environments match), while off-diagonal entries quantify test-time replanning capabilities under specific environmental shifts.

5. Additional Resources

• Continual NavBench : A Continual Offline Reinforcement Learning Benchmark for Navigation Tasks
• JAX-CORL : Clean Sigle-file Implementations of Offline RL Algorithms in JAX
• OGBench : Benchmarking Offline Goal-Conditioned RL
• Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning

6. Citation

Accepted at ICML 2026. Proceedings citation will be updated once available.

@inproceedings{kobanda2026aqm,
  title     = {Adaptive Quasimetric Mapping: Principled Topological Abstraction for Robust Offline Goal-Conditioned Navigation},
  author    = {Kobanda, Anthony and Radji, Waris and Maillard, Odalric-Ambrym and Portelas, R{\'e}my},
  booktitle = {International Conference on Machine Learning (ICML)},
  year      = {2026},
  note      = {Accepted at ICML 2026}
}