PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning

Tongzhou Wang, Antonio Torralba, Phillip Isola, Amy Zhang

arXiv:2304.01203v7cs.LG

TL;DR

Goal-reaching RL has quasimetric structure in its optimal value functions, but learning those values calls for an approach designed around that geometry. QRL uses quasimetric models and a tailored objective, with theoretical recovery guarantees. It reports gains on offline and online goal-reaching benchmarks, while assuming deterministic environment dynamics.

  • Problem

    Goal-reaching RL has quasimetric structure in its optimal values, motivating a way to use that structure directly when learning them.

    Source: §1 · p. 1, §2.2 · p. 3

  • Method

    QRL learns goal-reaching value functions with quasimetric models by preserving local distances and maximally spreading other states.

    Source: §1 · pp. 1–2

  • Results

    QRL improves > 37% over the best baseline and > 46% over the d4rl handcoded reference controller on offline maze2d tasks, and has 4.9× sample efficiency on state-based FetchPush and 2.7× on state-based FetchSlide versus Contrastive RL.

    Source: §1 · p. 2, §5.2 · p. 9

  • Takeaways & Limitations

    QRL is presented as the first RL method designed for quasimetric models, and the authors hope it inspires further RL work aware of geometric structure.

    Source: §6 · p. 9

    QRL is derived under the assumption that environment dynamics are deterministic.

    Source: §3 · p. 3

Abstract

from arXiv · show

In goal-reaching reinforcement learning (RL), the optimal value function has a particular geometry, called quasimetric structure. This paper introduces Quasimetric Reinforcement Learning (QRL), a new RL method that utilizes quasimetric models to learn optimal value functions. Distinct from prior approaches, the QRL objective is specifically designed for quasimetrics, and provides strong theoretical recovery guarantees. Empirically, we conduct thorough analyses on a discretized MountainCar environment, identifying properties of QRL and its advantages over alternatives. On offline and online goal-reaching benchmarks, QRL also demonstrates improved sample efficiency and performance, across both state-based and image-based observations.

1. Introduction

In multi-goal RL, optimal value functions have quasimetric structure, unlike the unrestricted value functions of single-task RL. QRL uses that structure to learn optimal goal-reaching values, with theoretical guarantees and improved offline maze2d results.

1. Introduction

  • Multi-goal optimal value functions are quasimetrics, while single-task value functions can be arbitrary functions.Quasimetrics allow asymmetry while respecting the triangle inequality.Source: §1 · p. 1, Figure 1 · p. 2
  • QRL is designed for quasimetric models because standard RL objectives may degrade with restricted function spaces, whereas quasimetric structure is built into the model.The paper contrasts this with encouraging quasimetric properties through an objective, as in Bellman updates.Source: §1 · p. 1
  • QRL learns goal-reaching value functions with quasimetric models, preserving local distances while maximally spreading other states.The paper motivates this objective as a way to recover shortest-path costs from local transition costs.Source: §1 · pp. 1–2
  • On offline maze2d tasks, QRL improves > 37% over the best baseline and > 46% over the d4rl handcoded reference controller.The paper also reports theoretical guarantees, MountainCar analysis, and optional extensions to learn optimal Q-functions and/or policies.Source: §1 · p. 2

2. Value Functions are Quasimetrics

The section establishes how goal-reaching tasks are defined, proves that optimal goal-conditioned values correspond exactly to quasimetrics, and explains why standard RL procedures can be difficult to combine with quasimetric models.

2.1. Goal-Reaching Reinforcement Learning

  • Goal-reaching RL uses an MDP with transition costs, and a goal-conditioned policy seeks to reach a target state while maximizing expected reward, or minimizing expected cost.The setting defines a policy value as the expected total reward until the goal is reached.Source: §2.1 · p. 2

2.2. Value-Quasimetric Equivalence

  • The negative optimal goal-conditioned value obeys the triangle inequality, and every quasimetric over the state space is the negative optimal value function of some MDP.Thus, quasimetrics are exactly the function class for multi-goal optimal values; single-goal values can be arbitrary functions.Source: §2.2 · pp. 2–3

2.3. Quasimetric Models and RL

  • Quasimetric models parameterize distances with an encoder and a latent quasimetric head, but standard temporal-difference or policy-iteration methods may rely on intermediate values that are not quasimetrics.Simply using these models may yield only minor benefits or require relaxing the quasimetric inductive bias; the section asks whether optimal values can be learned directly.Source: §2.3 · p. 3

3. Quasimetric Reinforcement Learning

QRL uses quasimetric models and a dedicated objective to recover optimal goal-conditioned values, with theoretical guarantees and MountainCar analyses.

3. Quasimetric Reinforcement Learning

  • QRL learns optimal goal-conditioned V* with a quasimetric, maximizing state–goal distances while keeping observed transition distances within their costs.The method assumes deterministic environment dynamics.Source: §3 · p. 3

3.1. QRL Learns the Optimal Value Function

  • Local costs constrain paths through the triangle inequality; maximizing dθ then recovers the shortest-path cost and thus −V*.The recovery argument assumes sufficient coverage of sampled states and goals.Source: §3.1 · p. 4

3.1.1. THEORETICAL GUARANTEES

  • With the full quasimetric space, QRL exactly recovers −V* almost surely; with a universal approximator and relaxed constraints, it recovers values up to a known scale with stated probability.The approximate guarantee applies to sampled state–goal pairs and requires a universally approximating quasimetric model family.Source: §3.1.1 · p. 4

3.2. A Practical Implementation

  • The practical implementation uses Interval Quasimetric Embeddings and relaxed expected local-cost constraints, with a transformed distance objective to stabilize maximization.The transformed objective downweights already-large distances, addressing slow convergence associated with growing late-layer weight norms.Source: §3.2 · p. 4

3.3. Analyses and Comparisons via Discretized MountainCar

  • On offline MountainCar, QRL alone recovers ground-truth values across single- and multi-goal settings and learns faster than Q-learning; contrastive RL estimates on-policy values.A symmetric-value QRL ablation underperforms; quasimetric Q-learning plans comparably here but learns more slowly and misses finer value details.Source: Figure 3 · p. 5, §3.3 · pp. 5–6

3.4. From V ∗to Q∗and Policy

  • QRL extensions learn Q* using a latent transition model; quasimetric structure bounds global Q-function error from local transition loss, while formal guarantees for Q* and policies remain future work.The estimated Q* uses the predicted next latent state and the value estimate; the transition loss trains both the quasimetric and transition model.Source: §3.4 · p. 7

4. Related Work

QRL differs from prior geometric and contrastive RL approaches by using quasimetric structure to estimate optimal goal-reaching values directly. Related work also studies state-space abstractions and geometric bounds, rather than directly outputting values for every goal.

Contrastive Approaches to RL

  • Most contrastive RL methods pull together states from the same trajectory to capture on-policy values, rather than enforcing quasimetric structure, local costs, and maximal state spreading for optimal values.Yang et al. (2020) preserves local costs but fixes non-adjacent distances at 2 using a metric, while goal-alignment models estimate density ratios rather than optimal cost-to-go.Source: §4 · p. 7

Quasimetric Approaches to RL

  • Prior quasimetric RL methods mainly estimate on-policy values or support planning and hierarchy learning, whereas QRL uses full quasimetric geometry to estimate optimal values and produce goal-reaching agents.Liu et al. (2022) parameterize Q-functions with quasimetric models; Durugkar et al. (2021) use a one-dimensional Euclidean geometry for each goal.Source: §4 · p. 7

Metrics and Abstractions in RL

  • Bisimulation metrics bound value differences for single tasks, while QRL's quasimetric directly outputs the optimal value for reaching any goal.Other state abstractions relate to value functions, transition dynamics, or factorized dynamics.Source: §4 · p. 7

5. Benchmark Experiments

Across offline maze2d and online Fetch benchmarks, QRL performs strongly against baselines, and its learned value functions can also improve planning and trajectory sampling. Online results include strong sample efficiency, including in image-based settings despite their partial observability and stochastic dynamics.

5.1. Offline Goal-Reaching d4rl maze2d

  • With two critics, QRL outperforms MSG by 20% on single-goal maze2d tasks and 188% on multi-goal tasks, and beats all baselines in both settings.QRL also outperforms both Diffuser planning settings without external information or a controller.Source: §5.1 · p. 8
  • QRL value functions improve MPPI planning and Diffuser goal-conditioned sampling, with consistent, non-trivial gains especially in multi-goal settings.Planning with the QRL Q-function greatly improves MPPI over using ground-truth dynamics.Source: §5.1 · p. 8

5.2. Online Goal-Reaching RL

  • QRL shows strong sample efficiency across online environments, with 4.9× and 2.7× sample efficiency versus Contrastive RL on state-based FetchPush and FetchSlide, respectively.Only QRL and Contrastive RL learn in those two more challenging state-based settings; QRL also performs strongly with image observations despite their partial information and stochastic dynamics.Source: §5.2 · p. 9
  • On complex continuous-control tasks, DDPG with quasimetric Q-functions is among the slowest or least-performing methods, while QRL learns quickly.The pattern holds for both IQE and MRN quasimetric models.Source: §5.2 · p. 9

6. Implications

QRL combines quasimetric models with an objective that preserves local distances and spreads states apart, and is proved to recover optimal value functions without temporal-difference or policy iteration. The paper reports stronger value learning and control results, and discusses extensions and future directions for quasimetric methods.

6. Implications

  • QRL's objective captures local distances while maximally spreading states, and provably recovers the optimal value function without temporal-difference or policy iteration.This distinguishes QRL from many prior approaches.Source: §6 · p. 9
  • MountainCar analyses support the importance of QRL's components, and additional benchmarks show better control results in online and offline settings.The paper also reports that QRL can directly improve other RL methods and has strong online sample efficiency.Source: §6 · p. 9
  • The authors identify QRL results as evidence for the usefulness of quasimetrics and of incorporating quasimetric structure into RL algorithm design.To their knowledge, QRL is the first RL method designed for quasimetric models.Source: §6 · p. 9
  • QRL can be viewed as decision-aware representation and latent world-model learning, but those properties were not substantially used in this work.Combining them with multi-step returns or auxiliary losses may yield stronger performance or variants better suited to partial observability and stochasticity.Source: §6 · p. 9
  • Learned asymmetric quasimetric distances may support long-range planning and exploration; locally distance-preserving quasimetrics are consistent and admissible heuristics that guarantee A* optimality.The paper presents quasimetric-aware actors and general search or planning solvers as possible directions.Source: §6 · p. 9
  • The paper proposes active probing based on uncertain or erroneous quasimetric distances or dynamics as a direction for improving online structure learning.For example, an agent could test a pair estimated to be close when no short connecting path has been observed.Source: §6 · p. 9
  • The authors hope QRL's performance will inspire further RL algorithms designed around quasimetric or other geometric structures.They describe QRL as the first method designed for quasimetric models, to their knowledge.Source: §6 · p. 9

A. Discussions and Generalizations of QRL

  • The appendix notes that self-transition constraints are inherently satisfied, constant-cost objectives can drop relu without significant result changes, and goals can be sets of states.For self-transitions, the constraint contribution is zero; general goals are handled by adding a goal state and transitions into it.Source: A. Discussions and Generalizations of… · p. 13

B.1. Theorem 1: Value-Quasimetric Equivalence

The proof states that the negative optimal value belongs to the quasimetric class and that the optimal value is represented by the negative distance, regardless of discounting. A three-state cyclic example shows on-policy values violating the triangle inequality.

B.1. Theorem 1: Value-Quasimetric Equivalence

  • The proof establishes that −V* belongs to the quasimetric class and that the optimal value is −d, regardless of discounting.The supplied proof passage cites Proposition A.4 of Wang & Isola (2022b) for the quasimetric property.Source: §B.1 · p. 13
  • With three distinct states and self-transitions plus cyclic next-state actions, the specified on-policy values violate the triangle inequality.The example assigns reward −1 to all transitions and uses a policy that takes the next-state action from s1 toward s2.Source: §B.1 · p. 13

B.2. Theorem 2: Exact Recovery

Under deterministic transitions, the proof relates locally connected state paths and their costs to the shortest-path cost, then establishes exact recovery of the optimal goal-reaching value by the quasimetric.

B.2. Theorem 2: Exact Recovery

  • The proof defines local connectivity through a deterministic transition and defines path cost as the sum of rewards over its transitions.It uses connected paths to reason about the shortest path between states.Source: §B.2 · p. 14
  • The proof identifies the negative optimal value −V*(s; g) with the total cost of the shortest path from s to g.It then shows the learned quasimetric is bounded above by this shortest-path cost.Source: §B.2 · p. 14
  • Theorem 2’s equality condition is dθ(s, g) = −V*(s; g) almost surely.The proof concludes that the optimal quasimetric equals the negative optimal value almost surely.Source: §B.2 · p. 14

B.3. Theorem 3: Function Approximation

The function-approximation result considers quasimetric models that can approximate the quasimetric class, and states a guarantee for sampled states and goals. A formal version assumes a compact state space and continuous optimal value.

B.3. Theorem 3: Function Approximation

  • The formal function-approximation theorem assumes a compact state space and continuous optimal value V*.The proof notes that compactness and continuity ensure V* is bounded.Source: §B.3 · p. 14
  • The result considers quasimetric model families that universally approximate Qmet(S) in L∞ error.IQE and MRN are given as examples of such model families.Source: §B.3 · p. 14
  • Theorem 3 states an approximation guarantee for states sampled from pstate and goals sampled from pgoal, for every δ > 0.The supplied theorem statement does not specify the bound itself.Source: §B.3 · p. 14
  • A lemma establishes the existence of an approximating quasimetric d(ϵ/2) under the theorem’s assumptions.The proof constructs a modified MDP with rewards shifted by ϵ.Source: §B.3 · p. 15

C. Experiment Details and Additional Results

The appendix reports experiment details for discretized MountainCar and offline maze2d, including task construction, evaluation, and method-specific training and planning choices. Results aggregate five runs with different seeds.

C. Experiment Details and Additional Results

  • 5 runs with different seeds are aggregated across the reported experiments.The appendix says its general design details apply across settings, with task-specific details in separate subsections.Source: C. Experiment Details and Additional… · p. 16

C.1. Discretized MountainCar

  • MountainCar uses 160 bins per state dimension, yielding 160 × 160 discrete states, and augments the offline data with 240 transitions for the general hilltop goal.The dataset also contains 199,888 transitions from a random actor across 1,019 episodes.Source: §C.1 · pp. 16–17
  • MountainCar planning is evaluated from all 160 × 160 states with a 200-step budget, and specific-goal tasks use a 13 × 13 success neighborhood.QRL and Q-Learning select actions by minimizing distance or maximizing Q value rather than using trained policies.Source: §C.1 · p. 17
  • MountainCar QRL trains for 5 × 10^5 gradient steps with batch size 4096 and a transition-loss weight of 75.Its value model uses an IQE-maxmean head with 16 components of size 32.Source: §C.1 · p. 17

C.2. Offline d4rl maze2d

  • Offline maze2d QRL trains for 2 × 10^5 gradient steps with batch size 4096 and adds a behavior-cloning loss of weight 0.05 to policy training.The behavior-cloning goal is a future state sampled from the same trajectory.Source: §C.2 · p. 18
  • Maze2d planning also tests MPPI with QRL dynamics and value, while Diffuser uses QRL values for guidance alongside its goal conditioning.MPPI uses a five-step planning horizon and 10,000 samples per step; Diffuser guidance is applied over four steps at each sampling iteration.Source: §C.2 · p. 18

C.3. Online GCRL

In online goal-reaching benchmarks, QRL outperforms the compared alternatives, including methods that add quasimetrics to DDPG. The image-based FetchSlide setting is omitted because no method reaches non-trivial success.

C.3. Online GCRL

  • No method reaches non-trivial success on image-based FetchSlide, so that setting is omitted from the results.The authors report trying hyperparameter tuning and image rendering adjustments.Source: §C.3 · p. 18
  • The evaluation marks an episode successful if the task is completed within its 50-step time limit and evaluates methods every 2,000 environment steps.Success-rate curves are smoothed over a window of five before aggregation across five seeds.Source: §C.3 · p. 18
  • QRL consistently outperforms both tested approaches for integrating DDPG and quasimetrics on online GCRL benchmarks.The Figure 6 comparison reports that QRL learns faster and better; no method has access to ground-truth rewards.Source: Figure 6 · p. 19, §C.3 · p. 20
  • Image observations are encoded as 1024-dimensional vectors using the same convolutional backbone architecture across compared methods.Separate modules use independent copies of that backbone.Source: §C.3 · p. 19
  • Adding two critics and exploration action noise sometimes improves Contrastive RL, but does not fully explain its performance gap with QRL.The authors attribute part of QRL’s advantage over Contrastive RL to fundamental algorithmic differences.Source: §C.3 · p. 19
Loading 2304.01203v7…