Robots that navigate without a prebuilt map increasingly learn from logs: people driving, walking, or teleoperating along routes that wander, backtrack, and jitter. The most promising way to turn such logs into good behavior without hand-designed rewards is to learn a quasimetric. A quasimetric is a learned "time-to-reach" distance between observations that may be asymmetric (uphill differs from downhill) but obeys the triangle inequality. The robot then follows the direction in which this distance shrinks. These methods stitch pieces of mediocre trajectories into shortest paths. They have so far been shown on deterministic mazes and tabletop arms, and they break when the world is noisy. Projective quasimetric planning explicitly fails on OGBench's stochastic "Teleport" maze, and the original quasimetric RL guarantees assume deterministic dynamics. Real navigation is stochastic everywhere: wheels slip, people block corridors, actuation is imprecise.
This note argues that the failure has a specific cause that can be fixed. The shape of the quasimetric is still correct under stochastic dynamics. What goes wrong is the training rule: current rules take a minimum or a tightening over individual sampled transitions, so they credit lucky outcomes as if the agent could control them. We propose a backup that takes an expectation first and a maximum second, across several look-ahead horizons. This backup is a provable contraction, meaning repeated application shrinks the error by a fixed factor each round and converges to one answer. Its unique fixed point is the true optimal goal-reaching value even under stochastic dynamics. It keeps the fast long-horizon propagation that makes multistep quasimetric methods work. The intended payoff is offline, reward-free, mapless visual navigation trained on uncurated demonstrations in environments where outcomes are random.
Core Claim
Let $V^*(s,g)=\max_\pi \mathbb{E}_\pi[\gamma^{\tau_g}]$ be the optimal discounted probability-like value of reaching goal $g$ from observation $s$. Here $\tau_g$ is the hitting time of $g$ and $\gamma\in(0,1)$ is the discount. Define the distance $d^*=-\log_\gamma V^*$.
The first observation is that $d^*$ satisfies the triangle inequality even when transitions are stochastic. One valid policy from $s$ to $g$ is "reach $w$ optimally, then continue optimally to $g$." By the strong Markov property its value is $V^*(s,w)\,V^*(w,g)$, so $V^*(s,g)\ge V^*(s,w)V^*(w,g)$. The asymmetric quasimetric architectures used by Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning (QRL) and Offline Goal-conditioned Reinforcement Learning with Quasimetric Representations (TMD) are therefore still the right inductive bias in stochastic worlds. The problem lies in how those methods fit the architecture to data.
QRL's local constraint $d(s,s')\le 1$ is imposed on every sampled successor. It treats a lucky teleport as a controllable step. Hindsight waypoint sampling, as in Scaling Goal-conditioned Reinforcement Learning with Multistep Quasimetric Distances (MQE), conditions on the waypoint having been reached. Both rules are optimistic in a noisy world.
We replace them with the following backup over a set of horizons $K=\{1,2,4,\dots,k_{\max}\}$, where $\beta$ is whatever policy produced the data:
$$(\mathcal{T}Q)(s,a,g)=\max_{k\in K}\ \mathbb{E}_{\beta}\Big[\gamma^{\tau_g}\mathbb{1}[\tau_g\le k]+\gamma^{k}\,\mathbb{1}[\tau_g>k]\max_{a'}Q(s_k,a',g)\ \Big|\ s_0=s,a_0=a\Big].$$
Each term follows the logged behavior for $k-1$ steps and then hands off to the current estimate. Each term is a $\gamma^k$-contraction in the sup norm. A maximum of contractions with modulus at most $\gamma$ is itself a $\gamma$-contraction. The $k=1$ term is the ordinary optimality backup, so $\mathcal{T}Q^*\ge Q^*$. Every $k>1$ term evaluated at $Q^*$ is the value of a legitimate non-anticipating policy (behave like the data, then act optimally), so $\mathcal{T}Q^*\le Q^*$. Hence $Q^*$ is the unique fixed point.
The goal $g$ only enters through the indicator and the hand-off value. The expectation is over behavior that never "knew" about $g$, so relabeling goals introduces no hindsight bias. Where the demonstrations are good, the long-horizon terms dominate and information propagates $k$ steps per backup. Where demonstrations are poor, the one-step term takes over. The backup therefore exploits imperfect experts without trusting them.
Research Program
The work has three parts.
The first is analytical. We will state and prove the contraction and fixed-point result above, including the case of history-dependent human behavior. We will then characterize what goes wrong when the expectation is replaced by a sample maximum. On a family of stochastic gridworlds where $Q^*$ can be computed exactly, we will show the size of the optimism gap that sampled-minimum rules converge to.
This part sits in a tradition that both motivates and constrains it. An Alternative Softmax Operator for Reinforcement Learning showed that an innocent-looking change of operator (Boltzmann softmax) destroys non-expansion and causes divergence. That is a warning that "min over samples" deserves the same scrutiny. Emphatic TD Bellman Operator is a Contraction restored contraction for off-policy projected updates at the cost of looser moduli. Our operator stays in the plain sup norm and needs no importance weights, because each $k$-term evaluates the logged behavior itself. That is the same design choice that lets Exponentially Weighted Imitation Learning for Batched Historical Data (MARWIL) avoid importance sampling, though MARWIL requires scalar rewards and we do not.
We deliberately stay with expected values rather than return distributions. A Distributional Perspective on Reinforcement Learning proved that the distributional optimality operator is not a contraction. A risk-sensitive version is therefore a separate problem that we flag but do not attempt.
The second part is algorithmic. Each $k$-term is a conditional expectation, so it can be estimated by ordinary squared-error regression. We train one head $h_k(s,a,g)$ per horizon to regress the bracketed target, using a slowly updated target network for the hand-off value. We then fit the quasimetric critic to $\max_k h_k$. The critic uses the architecture and action-invariance constraint of TMD: the distance from a state to the state-action pair that starts there is zero. Regression before the maximum is the essential ingredient.
A maximum over noisy regressors is itself biased upward, the same way Q-learning's maximum overestimates. We will control this by fitting the heads on disjoint data halves and taking the maximum of one half's heads evaluated with the other half's targets. We will report how much residual bias remains. Policies are extracted with goal-conditioned advantage-weighted regression, as in ProQ.
The third part is the application: mapless navigation from egocentric images, trained offline on demonstrations that are deliberately imperfect. The motivation is twofold. HD maps fail when scenes change, as the Zeus system report documents (Building a Winning Self-Driving Car in Six Months). And current RGB-only skills such as PixNav are trained by imitation on 100,000 shortest-path trajectories, which is exactly the expert-optimality assumption real logs violate. Reinforced Imitation similarly relies on optimal planner demonstrations plus online RL.
Rewards come only from reaching relabeled goals, so no progress or collision penalties are designed by hand. That addresses the shaping fragility documented in Adaptive Reward Design for Reinforcement Learning and the reward hacking discussed in Active Reward Learning.
Positioning Against the Closest Work
QRL, TMD, and MQE all learn quasimetrics from suboptimal offline data without rewards. QRL does so by chain-tightening on sampled transitions, with guarantees only for deterministic dynamics. TMD uses a Bregman-divergence temporal-consistency loss that is empirical rather than a proven contraction. MQE uses multistep waypoints with an action-invariance loss and is not framed as an operator.
ProQ builds a landmark graph on top of a quasimetric and fails on Teleport. QuasiNav brings quasimetrics to physical navigation but learns online from simulation rollouts.
Our proposal differs in one precise place: the target. We use a max over horizons of conditional expectations under the logged behavior. With this target the fixed point is exact under stochasticity, and multistep speed is retained. We keep their architectures and policy extraction, so any gain can be attributed to the backup.
Baselines
The naive reference is goal-conditioned behavioral cloning (GCBC), run exactly as packaged in OGBench. It shows how much is gained by doing any value learning at all on imperfect data. For visual navigation, the corresponding naive reference is a PixNav-style imitation policy trained on our imperfect Habitat demonstrations instead of shortest paths. PixNav reports a 37.9% open-set ObjectNav success rate and above 80% for the local pixel-goal skill when trained on expert data. The gap between that expert-trained figure and the same architecture on noisy data measures the cost of losing expert optimality.
The standard value-learning competitors are GCIQL, CRL, QRL and HIQL from OGBench, all run with OGBench's released settings.
The strongest competitors are MQE and TMD. They are the only methods in the file that both stitch suboptimal data and scale to long horizons. MQE was the only method with non-zero success on AntMaze-Colossal and reports a tenfold improvement over the previous best on humanoidmaze-giant-stitch. TMD is the method most likely to already handle stochasticity, through its temporal-invariance loss. ProQ is the strongest graph-planning baseline and reports 99% on PointMaze Giant-Stitch. For QRL, the file quotes an improvement of more than 37% over the best baseline on D4RL maze2d. For any method on the Teleport variants, no reported result found on Lacuna; we will produce these numbers ourselves.
For fairness, every method gets the same quasimetric encoder backbone where applicable, the same image encoder for visual tasks, the same number of gradient steps, and the same hyperparameter search of equal size on a held-out goal set, with eight seeds each. Beating the strongest baseline means a statistically clear success-rate gain over the better of MQE and TMD on the stochastic tasks, with no significant loss on their deterministic stitch tasks.
Three ablations isolate the key ingredient. The first uses only $K=\{1\}$, which gives standard quasimetric TD and tests whether long horizons matter. The second takes the max over sampled returns rather than over regressed expectations, which tests our central bias claim directly. The third uses a single fixed $k$ without the maximum, which is pessimistic toward the behavior. A fourth replaces the quasimetric critic with a plain network to test whether the triangle-inequality bias still helps under noise.
Why not just…?
Why not just use TMD, whose Bregman temporal-invariance loss was designed with stochasticity in mind? This is the most serious threat. TMD may already be close to unbiased. Its loss, however, is a consistency penalty without a stated fixed point. If its minimizer drifts toward behavior distances, it will look fine on deterministic mazes and degrade on Teleport. The tabular experiment settles this cleanly: we run TMD's update with exact expectations and with sampled data, and compare the converged values with $Q^*$. If TMD matches $Q^*$ and matches our success rates on stochastic OGBench tasks, the contribution shrinks to a proof of why TMD works. We will report that outcome honestly.
Why not just use plain n-step returns or GCIQL? One-step TD is unbiased but propagates one step per backup. The file reports that standard TD baselines score 0% on AntMaze-Colossal. Fixed n-step returns are faster but converge to the value of the behavior, which is pessimistic toward poor demonstrators. Our max over horizons is exactly the device that keeps the speed and drops the pessimism, and the "single fixed $k$" and "$K=\{1\}$" ablations measure each failure separately.
Why not just filter the demonstrations, MARWIL-style, and clone the good parts? Filtering needs a reliable value estimate. MARWIL's own advantages require scalar rewards, and errors in the value invert the weights. Filtering also cannot create routes that no single demonstrator took. OGBench shows that cloning collapses on stitching tasks, and ProQ reports that cloning fails to exceed 30% where quasimetric planning nears 100%. The GCBC and advantage-weighted-cloning rows in our tables test this directly on visual navigation.
Why not just run SLAM and A*? Metric maps work well when the scene is static and costs are symmetric. QuasiNav shows that symmetric costs waste up to 13.6% energy on uneven terrain, and the Zeus report documents the brittleness of maps when scenes change. We will include a SLAM-plus-planner reference in Habitat for honesty. We expect it to win on static, well-lit scenes and lose when furniture moves between data collection and testing.
Proposed Experiments
The first decisive check is tabular. We will build stochastic gridworlds with slip probability swept from 0 to 0.4 and teleport cells, plus a data-generating behavior mixing random walks with a noisy planner. We compute $Q^*$ exactly. We then run the exact operators of QRL-style tightening, MQE-style sampled-waypoint minimization, TMD's update, and ours, and report the sup-norm distance of each fixed point to $Q^*$ and the number of iterations to converge. The prediction is specific. All methods agree at zero slip. Sampled-minimum rules acquire an optimism gap that grows with slip. Ours stays at zero error, and its iteration count scales with corridor length divided by the useful horizon rather than with corridor length itself.
The second check uses OGBench. It covers PointMaze and AntMaze navigate and stitch datasets at medium through giant scale, the Teleport variants, visual-antmaze from 64×64 images, and versions of AntMaze in which we inject Gaussian actuation noise at test and collection time. Success rate is the metric. The decisive outcome is a clear win on Teleport and noisy-actuation mazes together with parity with ProQ's 99% and MQE's results on deterministic stitch tasks. We will also cross-check maze2d against QRL's reported margin.
The third check is mapless visual navigation in Habitat on HM3D scenes, using image-goal and pixel-goal tasks. We will build a demonstration set from noisy planners with random detours, backtracking, stop-and-go jitter, and wandering segments, and enable Habitat's actuation noise. The data will have no rewards and no shortest paths. We compare against the PixNav-style cloner, MQE, TMD and the SLAM reference, measuring success rate and success weighted by path length (SPL). Path efficiency is where escaping the demonstrators' suboptimality should show.
The single result that would most change our minds is a tie between our method and the sampled-maximum ablation on Teleport. That would mean the bias we identify is too small to matter in practice. The single result that would most support the proposal is the tabular optimism gap reappearing, at matching size, as a success-rate gap on noisy-actuation visual navigation.
References
- Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning
- Offline Goal-conditioned Reinforcement Learning with Quasimetric Representations
- Scaling Goal-conditioned Reinforcement Learning with Multistep Quasimetric Distances
- An Alternative Softmax Operator for Reinforcement Learning
- Emphatic TD Bellman Operator is a Contraction.
- Exponentially Weighted Imitation Learning for Batched Historical Data
- A Distributional Perspective on Reinforcement Learning
- Building a Winning Self-Driving Car in Six Months
- Bridging Zero-shot Object Navigation and Foundation Models through Pixel-Guided Navigation Skill
- Reinforced Imitation: Sample Efficient Deep Reinforcement Learning for Mapless Navigation by Leveraging Prior Demonstrations
- Adaptive Reward Design for Reinforcement Learning
- Active Reward Learning
- Offline Goal-Conditioned Reinforcement Learning with Projective Quasimetric Planning
- QuasiNav: Asymmetric Cost-Aware Navigation Planning with Constrained Quasimetric Reinforcement Learning
- OGBench: Benchmarking Offline Goal-Conditioned RL