1 Introduction↩︎

The increasing availability of large-scale offline trajectory data has shifted reinforcement learning toward reward-free pretraining: extracting from a data set a reusable policy that generalizes across an open set of goals [1]–[3] in a zero-shot manner. This objective, often described as foundation policy learning [2], has motivated a range of large-scale efforts, from unsupervised RL pretraining to Vision–Language–Action (VLA) models that train a single policy on heterogeneous trajectory data and deploy it across many previously unseen tasks [4]–[8]. We hypothesize that for such a policy to succeed at long-horizon tasks, the offline learned goal-agnostic representation must support the three capabilities jointly. Firstly, it should comply with unsupervised policy training, where the policy is learned without exposure to explicit goal-conditioned rewards, ensuring generalization to tasks defined only at deployment. Secondly, the state representations should be queryable with directional distances, as most real environments are irreversible or reversible at asymmetric costs, making it possible that routes planned with symmetric distances pass through subgoals unreachable in the required direction. Thirdly, these distances should satisfy the triangle inequality so that during multi-stage planing, local distances can compose into globally consistent plans through intermediate states never specified at training time.

Existing methods follow a trichotomy based on the quantity of interest used for offline state representation learning: successor measures, reachability distances, and hitting times. Successor measure methods [3], [9]–[11] decouple environment dynamics from rewards to allow zero-shot task adaptation. However, these methods—except CMD—fail to satisfy the triangle inequality, making them unable to compose distances across the intermediate sub-goals essential for multi-stage planning. Reachability distance methods [12]–[14] impose metric or quasimetric structures to improve compositional reasoning. Their key limitation is that they rely on goal-conditioned supervision for policy training. Hitting time methods [2], [15] are uniquely tailored for unsupervised policy training and satisfy the triangle inequality. However, their symmetric Euclidean features fail to capture the irreversible directed geometry of real-world physical transitions, limiting their stitching (hence multi-stage planning) capabilities. Furthermore, GAS [15] also necessitates real goal state labels for policy training, hence it does not qualify as a foundation policy learning method. Table [tab:methods-comparison] gives an overview of the prior art with respect to their properties relevant for foundation policy learning.

We identify the missing primitive of the prior approaches as the directional temporal geometry measured in discrete transition steps. We propose expected hitting time as this primitive. For a policy \(\pi\) and goal \(g\), \(V^\pi(x,g)\) represents the expected number of steps to reach \(g\) from \(x\). This quantity is characterized by a Poisson equation where a constant cost of one is incurred at each step until reaching the goal, at which point the cost becomes zero. This formulation provides the exact object required for multi-stage planning, bypassing the need to recover the temporal structure from surrogates such as successor measures or reachability distances. We formalize this idea via an operator-theoretic framework. For processes with a Hilbert-space feature map \(\phi\) and approximately linear latent dynamics, the hitting time satisfies the identity \(V^\pi(x,g) = \langle \phi(g)-\phi(x),\, \omega_g^\pi\rangle_{\mathcal{H}}\), where \(\omega_g^\pi \in \mathcal{H}\) identifies the task of navigating to state \(g\). This proves that representations capturing hitting-time functionals are equivalent up to a bounded linear isomorphism, implying our learning target is the invariant directed temporal geometry of the environment rather than an arbitrary coordinate system. Theoretically, we establish that this displacement-linear representation exists under latent linear closure and an adjoint solvability condition (Theorem 1) and is uniquely identifiable under a separating reference policy (Theorem 2). For finite-dimensional implementations, we prove that global hitting-time error is bounded by one-step latent transition error amplified by a transient-spectral-radius horizon factor (Theorem  3). Finally, our finite-sample regression analysis (Theorem 5) decomposes total error into approximation, statistical-complexity, coverage, and trajectory-label-mismatch terms, providing a complete PAC-oracle guarantee for the resulting displacement topology.

We use our theoretical framework to develop Isomorphic Embedding Learning (IEL) as the first foundation policy training algorithm tailored specifically for multi-stage planning. IEL trains \(\phi\) from offline trajectories by relabeling intermediate states as goals and regressing observed temporal gaps onto displacement-projected scores anchored by a learned task identifier \(\omega(g)\). At test time, IEL constructs a graph over offline latent states with edge costs given by the learned hitting-time score, and applies shortest-path search to convert local temporal predictions into global zero-shot navigation. As shown in Table [tab:methods-comparison], IEL is the only framework that integrates unsupervised policy training with a directional distance and the triangle inequality. We demonstrate the necessity of these qualities for learning foundation policies with multi-stage planning in experiments conducted on six offline goal-conditioned RL benchmarks. IEL’s directional distance features and the graph-based planning mechanism bring significant and complementary performance gains.

2 Isomorphic Embedding Learning from Hitting Time Observations↩︎

2.1 Problem statement↩︎

We consider a dynamical environment formulated as a Controlled Markov Process (CMP) defined by the tuple \((\mathcal{X}, \mathcal{A}, \mathcal{P})\), where \(\mathcal{X}\) and \(\mathcal{A}\) are real-valued, potentially multidimensional state and action spaces. The transition dynamics are governed by a Borel measurable kernel \(\mathcal{P}: \mathcal{X} \times \mathcal{A} \to \Delta(\mathcal{X})\), which assigns a probability measure over next states \(x'\) given a current state-action pair \((x, a) \in \mathcal{X} \times \mathcal{A}\). We assume the existence of a fixed behavior policy \(\pi_B: \mathcal{X} \to \Delta(\mathcal{A})\) used to provide us with an offline dataset \(D = \{\tau_i\}_{i=1}^n\) consisting of \(n\) independent and identically distributed (i.i.d.) trajectories \(\tau_i = (x_0, a_0, x_1, a_1, \dots, x_{T_i})\) of length \(T_i\) generated by the interaction of \(\pi_B\) with the kernel \(\mathcal{P}\).

Let \(T_{x \rightarrow g}^\pi = \inf \{t \geq 0 \mid x_0=x, x_t = g\}\) be a random variable representing the hitting time to a goal state \(g \in \mathcal{X}\) under a policy \(\pi\). We assume that for any \(g\) reachable from \(x\), there exists at least one policy in the admissible set \(\Pi_D\) such that the expected hitting time \(V^\pi(x, g) = \mathbb{E}[T_{x \rightarrow g}^\pi \mid x_0 = x]\) is finite. Our objective is to identify the optimal in-distribution foundation policy \(\pi_{D,g}^*\) defined as \(\pi_{D,g}^* = \arg\min_{\pi \in \Pi_D} V^\pi(x, g)\) for all \(g \in \mathcal{X}\) where the admissible policy set \(\Pi_D\) is defined by the in-distribution criterion of absolute continuity. Formally, for a fixed state \(x \in \mathcal{X}\), let \(\pi(\cdot|x)\) and \(\pi_B(\cdot|x)\) be the probability measures over the Borel \(\sigma\)-algebra \(\mathcal{B}(\mathcal{A})\). We define the in-distribution criterion of absolute continuity as \(\Pi_D = \{\pi: \mathcal{X} \to \Delta(\mathcal{A}) \mid \forall x \in \mathcal{X}, \pi(\cdot|x) \ll \pi_B(\cdot|x) \}.\) The notation \(\pi \ll \pi_B\) signifies that \(\pi(\cdot|x)\) is absolutely continuous with respect to \(\pi_B(\cdot|x)\), which is symbolically defined as: \(\forall B \in \mathcal{B}(\mathcal{A})\) with \(\pi_B(B|x) = 0\) implying \(\pi(B|x) = 0.\) By the Radon-Nikodym Theorem, this condition is necessary and sufficient for the existence of a non-negative and measurable function \(w: \mathcal{X} \times \mathcal{A} \to [0, \infty)\), names as the Radon-Nikodym derivative, such that for any \(B \in \mathcal{B}(\mathcal{A})\) we have \(\pi(B|x) = \int_B w(a|x) \, d\pi_B(a|x).\) This criterion ensures that the optimal policy only assigns mass to actions within the support of the behavior policy. We treat the trajectories in the data set as the empirical basis for estimating the expectations of the hitting time variable and the underlying transition dynamics. We refer to \(\pi_{D,g}^*\) as a foundation policy due to its capability to solve a large set of policy search tasks in a zero-shot manner.

We develop our solution using a Hilbert space framework because it combines high expressive power with geometric consistency. Hilbert spaces are a standard tool in control theory for the analysis of nonlinear dynamical systems, particularly through the use of Koopman and Perron-Frobenius operators [19]–[22]. This framework has recently inspired new approaches in offline reinforcement learning [3], [9], [23] and the development of foundation policies [2] by providing a structured way to represent state-action transitions as linear operators in a latent space. We approach the foundation policy learning problem from a rigorous Hilbert space perspective. The definition below specifies the conditions under which a CMP is representable within a Hilbert space subject to a bounded approximation error \(\epsilon\).

A Sufficient CMP is simply an \(\epsilon\)-Sufficient CMP where \(\epsilon = 0\), representing the case where the transition dynamics are perfectly captured by the linear action-operators in the latent Hilbert space. This definition is the Hilbert-space analogue of the linear-feature transition condition underlying linear action models [24], [25], with \(\epsilon\) playing the role of the misspecification term familiar from approximate linear MDPs [26]. It is also closely related to conditional mean feature models of MDP transition dynamics [27]–[29], which embed the full conditional \(\mathcal{P}(\cdot | x, a)\) in an RKHS rather than matching expected features under a fixed \(\phi\).

2.2 The Methodology: Hitting Time Isomorphism↩︎

Our main methodological contribution builds on the key fact that in a sufficient CMP, it is actually possible to relate the expected hitting time to feature difference. This fact bridges the gap between temporal dynamics and the Hilbert space geometry, using the property that the features \(\phi\) act as a system of coordinates for the latent state space. The below result states that if the feature map \(\phi\) is rich enough to linearize the dynamics (via the transition operators \(\{\mathcal{K}_a\}\)) and expressive enough to represent the passage of time (via the range condition on the adjoint), then the expected hitting time is exactly a linear functional of the displacement in the feature space. Throughout, we work on the closed feature span \(\overline{\operatorname{span}}\{\phi(x):x\in\mathcal{X}\}\), so equality of inner products against all feature vectors identifies elements of \(\mathcal{H}\). For hitting-time identities with goal \(g\), the relevant feature span is the closed span generated by \(\{\phi(x):x\neq g\}\).

For any policy \(\pi\) such that the policy-induced latent dynamics close linearly on \(\mathcal{H}\), i.e., there exists a bounded linear operator \(\mathcal{K}_\pi \in \mathcal{L}(\mathcal{H})\) satisfying \(\mathcal{K}_\pi \phi(x)=\mathbb{E}_{a\sim \pi(\cdot\mid x)}[\mathcal{K}_a \phi(x)]\) for all \(x\in \mathcal{X}\), Theorem 1 shows that the expected hitting time admits a linear representation in the displacement coordinates whenever the unit-cost functional lies in the range of \((\mathcal{K}_\pi-I)^*\). Thus, once the range condition holds, the passage of time is encoded by the latent linear dynamics rather than by an ad hoc distance heuristic. The next result establishes the stronger identifiability statement —namely that alternative representations recovering the same hitting-time geometry must be related by a bounded linear change of coordinates—under additional assumptions. Specifically, we assume the existence of a separating policy that can reach any goal and that the mapping from latent displacements to hitting times is well-conditioned. These requirements are reasonable as they merely ensure the environment is fully explorable and that the feature space does not merge distinct temporal transitions.

This identifiability ensures the learned displacement space is a linear transformation of the environment’s true geometry, preserving the relative temporal distances between states. Because the isomorphism \(M\) connects these representations, any hitting-time information encoded in the canonical dynamics can be pulled back and read out from our learned features as formalized below.

HILP [2] and GAS [15] rely on a symmetric \(L_2\) distance heuristic that fails in the realistic case where the environment dynamics are directed. Contrarily, our framework identifies an isomorphism between the MDP dynamics and a directed displacement geometry, which captures both the direction and the scale of time. Instead of assuming that features can be forcibly mapped to a spatial distance, our Sufficient CMP framework ensures that the latent coordinates \(\phi(x)\) are mathematically constrained by the linear transition operator \(\mathcal{K}_a\). This provides a provable link between latent dynamics and hitting times, enabling reliable multi-stage planning through directed graph search—a capability fundamentally missing in symmetric feature methods. Furthermore, we establish an algebraic identifiability absent in the quasimetric representations of TMD [14], which exploits asymmetric distances to approximate hitting times. This approach lacks the operator-theoretic grounding necessary to ensure that these distances are globally consistent across the state space. In our framework, Theorem  1 proves that the expected hitting time is a linear function of latent displacement coordinates whenever the unit-cost functional satisfies the adjoint range condition. Theorem 2 provides the stronger structural guarantee: any representation satisfying this identity is related to the canonical one by a unique bounded linear isomorphism. This fact ensures that our learned geometry is a coordinate-consistent reflection of the underlying process rather than an unconstrained distance heuristic. Consequently, our framework recovers the environment’s latent displacement structure with a level of mathematical rigor that current distance-based models do not guarantee.

2.3 The Algorithm: Isomorphic Embedding Learning (IEL)↩︎

We next introduce a new foundation policy learning algorithm building on the theoretical framework developed earlier. Our algorithm, named as Isomorphic Embedding Learning (IEL), comprises the four components explained below. The related pseudocode can be found in Appendix 11.

(i) Task identifier learning: We learn a mapping \(\omega_\psi(\cdot)\) that transforms a target state \(g\) into a task identifier \(\omega_g^\pi\), which defines the directional axis of the latent space for that specific navigation objective. This is essential for implementing the directional asymmetry in the hitting-time calculation \(V^\pi(x, g) = \langle \phi(g) - \phi(x), \omega_g^\pi \rangle_{\mathcal{H}}\) established in Theorem 1. We adopt a contrastive learning approach to implement this step by computing an InfoNCE loss that contrasts the task identifier \(\omega_\psi(g_i)\) against a corresponding augmented positive view \(\omega_\psi(\tilde{g}_i)\) and a set of negative candidates within a batch. Specifically, for a batch of goals \(\{g_i\}_{i=1}^N\) sampled from the replay buffer, where \(\tilde{g}_i\) denotes the augmented view paired with \(g_i\) as in Algorithm 2, we minimize: \[\begin{align} \mathcal{L}_{\text{NCE}}(\psi) = -\frac{1}{N}\sum_{i=1}^N \left[ \frac{\omega_\psi(g_i)^\top \omega_\psi(\tilde{g}_i)}{\tau} - \log \sum_{j=1}^N \exp\left( \frac{\omega_\psi(g_i)^\top \omega_\psi(\tilde{g}_j)}{\tau} \right) \right]. \end{align}\] The denominator contrasts the paired positive view against other batch candidates, encouraging augmented views of the same state to have similar identifiers while separating distinct states. This stage should be interpreted as learning an injective task parameterization, not as directly solving the policy-specific Poisson equation for the exact representers \(\omega_g^\pi\) in Theorem 2.2. In the finite-sample analysis, the learned task encoder is treated as fixed and denoted by \(\bar \omega_\psi\). Any mismatch between this learned identifier and an ideal hitting-time readout is absorbed into the approximation/oracle-competitiveness terms of the regression analysis.

(ii) Hitting time regression: We sample an intermediate point from a trajectory. We then learn to predict the hitting-time progress supported by the behavior data. Following the lines of IQL [30], we perform expectile regression to bias the learned geometry toward shorter in-distribution distances from observations. To keep the empirical hitting-time target bounded and stable, we implement discounted hitting times in line with common practice in sufficient-MDP-based approaches.

(iii) Temporal difference learning. The Monte Carlo approach used in the previous component is effective for learning to predict hitting times in an unbiased manner. However, collecting long-horizon hitting-time observations is difficult: long-range data is rare, often following a power-law tail, and such targets become increasingly hard to predict accurately. Instead, we restrict the interim goal horizon and support the stitching capabilities of our approach via TD learning. The detrimental effect of the limited horizon of trajectories on stitching capabilities has been observed earlier [14]. A direct Bellman backup implementation of the hitting time machinery is susceptible to numerical instabilities. To account for them, we first establish an analytical link between our hitting time formula and HILP, noting that HILP’s \(L_2\) norm formulation appears as an upper bound to ours. We bridge these two models by grounding the latent displacement in the projection of the embedding difference onto the canonical unit vector. This projection represents the directed progress toward the goal state. By normalizing the task identifier we get \[\begin{align} \langle \phi(g) - \phi(x), \omega_\psi(g) / \|\omega_\psi(g)\| \rangle = \|\phi(g) - \phi(x)\| \underbrace{ \frac{\langle \phi(g) - \phi(x), \omega_\psi(g) \rangle}{\|\phi(g) - \phi(x)\| \cdot \|\omega_\psi(g)\|} }_{=\cos(\xi_{x\rightarrow g, g})} \end{align}\] where \(\xi_{x\rightarrow g, g}\) is the angle between the embedding vectors of \(s\) and \(g\). We further employ a transformation \(V^\pi(x,g) \approx \|\phi(g) - \phi(x)\| \exp \left( \beta (1 - \cos(\xi_{x\rightarrow g, g})) \right)\) which penalizes both the Euclidean distance and the angular misalignment relative to the goal, introducing a directional bias that symmetric HILP objective lacks. The exponential factor is monotone in \(\cos(\xi_{x\rightarrow g, g})\): it equals one when \(\phi(g) - \phi(s)\) is aligned with \(\omega_\psi(g)\) and grows smoothly as alignment degrades, so it acts as a soft directional constraint that augments the underlying Euclidean term. We adopt this transformation as a smoother proxy for the directed hitting-time score. Notably, \(\beta=0\) recovers the HILP objective.

(iv) Graph search for multi-stage planning. We exploit the learned asymmetric geometry by constructing a directed graph \(G=(V,E)\). The vertex set \(V\subset \{\phi(s) | s \in \mathcal{B} \}\) is extracted from the dataset using a greedy approximation for Determinantal Point Process inference [31], ensuring diverse coverage of the state manifold. The edge set \(E\) is initialized via a symmetrized Minimum Spanning Tree (MST) based on \(d_{sym}=d(s,t,g)+d(t,s,g)\), ensuring strong connectivity. This backbone is augmented with \(k\)-Nearest-Neighbors (\(k\)-NN) for each vertex. While the MST backbone is determined by \(d_{sym}\), all edge costs retain their asymmetric costs defined in 1 , leveraging the learned quasimetric isomorphism of the state space; induced graph distances respect the triangle inequality: \[\begin{align} d(s,t, g) :=\| \phi(t) - \phi(s)\|_2 \cdot \exp ( \beta ( 1 - \cos(\xi_{s\rightarrow t, g}))). \label{eq:edge95cost} \end{align}\tag{1}\] Navigation is performed by computing the Single Source Shortest Path (SSSP) on the reversed graph \(\bar{G}\) from the goal vertex \(\phi(g)\). This yields a global navigation function. At evaluation time, the agent identifies the nearest vertex \(s\in V\) and pursues the subsequent node on the optimal path toward \(g\). See Algorithm 4 for the full pseudocode. Note that a symmetric variant of the asymmetric graph planning algorithm can be derived by using a symmetric distance function (e.g., \(d(s,t)=\|\phi(t)-\phi(s)\|_2\)) and undirected edges for the graph. This reduces the computational overhead significantly, as the graph and shortest path can be precomputed before evaluation, as the distance function is goal-agnostic.

3 Theoretical Analysis↩︎

This two-part analysis bounds errors from \(d\)-dimensional latent compression and provides finite-sample PAC guarantees. The results establish conditions for recovering a near-oracle displacement topology—modulo a bounded linear map—while quantifying the impact of approximation, coverage, trajectory-label mismatch, and finite-sample effects.

3.1 Consistency Analysis↩︎

For the consistency analysis, let \(\widetilde{\mathcal{H}}\) denote an ambient Hilbert space with feature map \(\widetilde{\phi}:\mathcal{X}\to \widetilde{\mathcal{H}}\). Fix a \(d\)-dimensional subspace \(\mathcal{H}\subseteq \widetilde{\mathcal{H}}\) with orthogonal projection \(P_d:\widetilde{\mathcal{H}}\to \mathcal{H}\), and define the encoder \(\phi(x):=P_d\widetilde{\phi}(x)\in\mathcal{H}.\) We work henceforth in the compressed space \(\mathcal{H}\), so \(\dim(\mathcal{H})=d\).

The following lemma shows that the compressed operator \(\mathcal{T}^\pi\) correctly approximates the mean transition of the compressed features.

Define the out-of-subspace leakage by \(\eta(x):=\|(I-P_d)\mathbb{E}_{x'\sim\mathcal{P}^\pi(\cdot\mid x)}[\widetilde{\phi}(x')]\|_{\widetilde{\mathcal{H}}}.\) Then it holds that \(\|\mathbb{E}_{x'\sim\mathcal{P}^\pi(\cdot\mid x)}[\widetilde{\phi}(x')]-\mathcal{T}^\pi\phi(x)\|_{\widetilde{\mathcal{H}}} \le \epsilon+\eta(x)\). If the ambient features are already subspace-contained, i.e. \(\mathcal{R}(\widetilde{\phi})\subseteq \mathcal{H}\), then \(\eta(x)=0\). We now partition the latent space into the goal subspace \(\mathcal{H}_g:=\operatorname{span}\{\phi(g)\}\) and the transient subspace \(\mathcal{H}_Q:=\mathcal{H}_g^\perp\), assume that \(\mathbf{w}_{\mathbf{1}}\in\mathcal{H}_Q\), and write \(P_Q\) for the orthogonal projection onto \(\mathcal{H}_Q\). For a fixed policy \(\pi\), let \(P^\pi\) denote the policy-induced Markov operator on scalar functions, \((P^\pi f)(x):=\mathbb{E}_{x'\sim\mathcal{P}^\pi(\cdot\mid x)}[f(x')]\), and let \(P_Q^\pi\) denote its restriction to the transient state space \(\mathcal{X}\setminus\{g\}\), which is defined as \((P_Q^\pi f)(x):= \mathbb{E}_{x'\sim\mathcal{P}^\pi(\cdot\mid x)} \bigl[ f(x')\mathbf{1}\{x'\neq g\} \bigr]\). Equivalently, \(P_Q^\pi f\) is obtained by extending \(f\) to the goal with boundary value \(f(g)=0\) and then applying \(P^\pi\) on transient states. We also define the compressed transient latent operator \(\mathcal{T}_Q^\pi:=P_Q\mathcal{T}^\pi\big|_{\mathcal{H}_Q}\). The following theorem bounds the global error of the hitting-time predictor induced by a representation satisfying the sufficient capacity condition.

This result shows that the approximation error is amplified by the factor \((1-\rho(\mathcal{T}_Q^\pi))^{-1}\), which acts as an effective-horizon term for the transient latent dynamics. Practically, this means that small one-step representation errors can accumulate more severely when the goal is difficult to reach. Thus, any admissible reference representation whose compressed latent dynamics are sufficiently accurate under the policy of interest induces a hitting-time predictor with controlled global error. We therefore compare the learner to the best such reference geometry available within this class. Concretely, fix \(x_0\in \mathcal{X}\), a policy \(\pi_{\mathrm{sep}}\in\Pi_D\), and a full-support probability measure \(\nu\) on \(\mathcal{X}\). Let \(\mathfrak R_\epsilon\) denote the class of admissible reference tuples \(r=(\mathcal{H}^r,\phi^r,\mathcal{T}^{r,\pi_{\mathrm{sep}}}, \{\omega_g^{r,\pi_{\mathrm{sep}}}\}_{g\in \mathcal{X}})\) for which Theorem 3 applies under \(\pi_{\mathrm{sep}}\) with constants \(C_H(r,g)\), and for which the associated analysis operator \((B_r d)(h):=\langle d,\omega_h^{r,\pi_{\mathrm{sep}}}\rangle_{\mathcal{H}^r}\) is bounded and bounded below, where \(d\in \mathcal{D}_r:=\overline{\mathrm{span}}\{\phi^r(g)-\phi^r(x_0):g\in \mathcal{X}\}.\) Writing the supremum constants \(C_H(r):=\sup_{g\in \mathcal{X}}C_H(r,g)\), \(C_\omega(r):=\sup_{g\in \mathcal{X}}\|\omega_g^{r,\pi_{\mathrm{sep}}}\|_{\mathcal{H}^r},\) and \(\rho_r:=\sup_{g\in \mathcal{X}}\rho(\mathcal{T}_{Q,g}^{r,\pi_{\mathrm{sep}}}),\) we define the best achievable benchmark scale as \(\eta_\epsilon^\star := \inf_{r\in\mathfrak R_\epsilon} (C_H(r)\,C_\omega(r)\epsilon)/(1-\rho_r)\). Thus \(\eta_\epsilon^\star\) is the smallest error level guaranteed by Theorem 3 over all admissible \(\epsilon\)-Sufficient compressed representations. Let \(\mathcal{F}\) be the class of predictors realizable by an algorithm in the form \(f(x,g)=\langle \phi(g)-\phi(x),\omega_g\rangle_\mathcal{H}\), and suppose that this class can match the oracle benchmark up to excess \(\eta_{\mathrm{cls}}\), i.e. \(\inf_{f\in\mathcal{F}}\|f-V^{\pi_{\mathrm{sep}}}\|_{L^2(\nu\times\nu)} \le \eta_\epsilon^\star+\eta_{\mathrm{cls}}\). The next result shows that any population minimizer of the regression objective aligns with the corresponding reference displacement geometry through a bounded linear map.

3.2 Finite Sample Analysis↩︎

We analyze the sample complexity of the hitting time regression part of Algorithm 1, conditioned on a fixed task encoder \(\bar \omega_\psi: \mathcal{X} \to \mathcal{H}\). Theorem 5 bounds finite-sample recovery of the temporal displacement geometry associated with the policy defining the regression target. For offline control, the relevant policy is the in-distribution optimum \(\pi^*_{D,g}\in\Pi_D\), but trajectories from this policy are not observed. The IQL-style expectile objective therefore provides an offline approximation to its value geometry by emphasizing shorter behavior-supported hitting-time outcomes. The gap to the ideal in-distribution-optimal geometry can thus be viewed as the representation error controlled by Theorem 5 plus a separate IQL approximation error. Let \(\Phi\) be the class of admissible state encoders, and define the induced predictor class for hitting time regression as \(\mathcal{F}_{\Phi,\bar \omega_\psi} := \left\{ f_\phi(s,u,g)=\langle \phi(u)-\phi(s),\bar \omega_\psi(g)\rangle_\mathcal{H} : \phi\in\Phi \right\}.\) Assume \(\|\phi(x)\|_\mathcal{H}\le C_\phi\) for all \(\phi\in\Phi,\;x\in \mathcal{X}\) and \(\|\bar \omega_\psi(g)\|_\mathcal{H}\le C_{\bar \omega_\psi}\) for all \(g\in \mathcal{X}\). From \(N\) i.i.d. trajectories sampled under \(\pi_B\), we extract exactly \(m_{\mathrm{tr}}\) tuples of the form \(z_{j,t}=(s_{j,t},u_{j,t},g_{j,t},H_{j,t})\) per trajectory, where \(t \in \{1,\dots,m_{\mathrm{tr}} \}\), \(u_{j,t}\) is an intermediate state on the same trajectory as \(s_{j,t}\) and \(g_{j,t}\), and \(H_{j,t}\) is the replay-buffer temporal-gap label extracted for that tuple (e.g. the number of steps from \(s_{j,t}\) to \(u_{j,t}\) along the sampled trajectory segment). Assume \(0\le H_{j,t}\le H_{\max}\) almost surely. Let \(\mu\) denote the law of a uniformly selected extracted tuple and write \((S,U,\mathsf G,H)\sim\mu\) for a generic such tuple. Let \(\lambda\) be the \((S,U)\)-marginal of \(\mu\), and define the ideal displacement target \(G^{\pi_B}(s,u,g):=V^{\pi_B}(s,g)-V^{\pi_B}(u,g).\) We also define the replay-buffer conditional mean \(m_{\mathrm{traj}}(s,u,g):=\mathbb{E}[H\mid S=s,U=u,\mathsf G=g].\) Let \(\widehat \phi_N\in\arg\min_{\phi\in\Phi}\widehat R_N(\phi)\) be the empirical minimizer of the tuple-level regression objective, let \(\widehat G_N(s,u,g):=\langle \widehat\phi_N(u)-\widehat\phi_N(s),\bar \omega_\psi(g)\rangle_\mathcal{H},\) and define the learned displacement space \(D_N:=\overline{\mathrm{span}}\{\widehat\phi_N(u)-\widehat\phi_N(s):(s,u)\in\operatorname{supp}(\lambda)\}.\) For each extraction slot \(t\), define the slotwise trajectory class \((\mathcal{F}_{\Phi,\bar \omega_\psi})^{(t)} := \left\{ \tau\mapsto f_\phi(s_t(\tau),u_t(\tau),g_t(\tau)) : \phi\in\Phi \right\},\) and let \(\overline{\mathfrak R}_N(\Phi,\bar \omega_\psi) := \frac{1}{m_{\mathrm{tr}}}\sum_{t=1}^{m_{\mathrm{tr}}} \mathfrak R_N\!\bigl((\mathcal{F}_{\Phi,\bar \omega_\psi})^{(t)}\bigr)\) denote the average slotwise trajectory-level Rademacher complexity. The resulting statistical error term is \[\begin{align} \Gamma_N(\delta) := 16(2C_\phi C_{\bar \omega_\psi}+H_{\max})\,\overline{\mathfrak R}_N(\Phi,\bar \omega_\psi) + 2(2C_\phi C_{\bar \omega_\psi}+H_{\max})^2 \sqrt{\frac{\log(1/\delta)}{2N}}. \end{align}\] The next result lifts this statistical error into a finite-sample displacement-topology recovery guarantee.

The term \(\eta_{\mathrm{traj}}\) quantifies the discrepancy between replay-buffer temporal gaps and ideal hitting-time targets, such that smaller values indicate better alignment between the learned displacement topology and the oracle reference topology within the established error bounds.

4 Experiments↩︎

We evaluate IEL on six offline goal-conditioned RL benchmark environments from two different suites taken from the D4RL data set [32]. HILP serves as our primary baseline, being the only prior art designed for foundation policy training and multi-stage planning. We strictly adhere to the planning experimental setup and hyperparameters reported in HILP (Table 2) to ensure a direct comparison. As practiced in HILP experiments, we do not consider approaches such as CRL, QRL, TMD, and GAS as fair baselines since their pipelines are tuned for goal-supervised training rather than foundation policy learning. We compare against GC-IQL and GC-CQL as the only representatives of zero-shot RL for which HILP reported complete results. To isolate the effect of our isomorphic embeddings, we evaluate both HILP and IEL using our graph-based planning approach. Specifically, we compare IEL under symmetric (\(\beta=0\)) and asymmetric (\(\beta=0.1\)) distance scores. HILP+Sym is the closest GAS-equivalent baseline for our problem setting. Like GAS, it builds on HILP-style representations, but omits the hierarchical supervised subgoal-reaching objective (see Eqs. 13–14 of [15]). Instead, HILP+Sym isolates the graph-planning ingredient relevant to foundation policy training by applying symmetrized graph construction and shortest-path subgoal selection on top of HILP. Each algorithm navigates the shortest path extracted from the planning graph using its respective distance metric. Thus, the symmetric variant of IEL still benefits from directional identifiers during the planning process. We report our main empirical results in Table 1, which reveals two critical outcomes: (i) IEL leverages graph-based planning more effectively than HILP, with its symmetric graph performance surpassing recursive midpoint planning by a significant margin in five environments. (ii) asymmetric planning yields further significant gains for IEL in four environments and causes minor degradation in the remaining two environments. These results validate our core hypothesis: directional embedding learning is essential for effective multi-stage planning in foundation policies. IEL’s performance is mildly sensitive to its hyperparameters \(H_{\max}\), \(\beta\), and \(\sigma\). See Appendix 12 for a discussion and further experiment details. IEL’s offline training-time computational cost is ignorably different from HILP. We set the coreset size to be \(8192\), which is the largest size that maintains a wall-clock time proportional to the Rec-Mid evaluation period. In this setting, Asym-Graph runs at a comparable speed to Rec-Mid, while Sym-Graph is approximately three times faster due to graph reusability.

3pt

5 Open Questions and Scientific Impact↩︎

The theoretical framework we built to set a foundation for the IEL algorithm unfolds new open questions. The range condition defined in Theorems 1 and 2 requires rigorous verification across non-linear environments to ensure universal representability. While identifiability is established up to a linear isomorphism, the impact of state-space discretization on directed geometry in high-dimensional settings remains unquantified. Consistency analysis reveals that global hitting-time error scales by the factor \(1/(1-\rho(\mathcal{T}_Q^\pi))\), creating high sensitivity to the transient spectral radius. The \(\epsilon\)-Sufficient CMP assumption (Definition 1) restricts the framework to environments where expected feature transitions are sufficiently linearizable. This formulation fails to cover dynamics with high-order stochasticity or non-Markovian dependencies that exceed the latent Hilbert space span. On the practical side, the upper bound used in the TD learning part can be tightened so that the directionality of the learned embeddings can be strengthened. This work provides the mathematical foundation to transition VLA research from its current reliance on imitation learning toward reward-based policy learning. By replacing symmetric distance heuristics with a directed temporal geometry, our framework enables agents to navigate complex, irreversible environments with provable efficiency. The outcome could be versatile general-purpose robots with enhanced autonomy and maintained trustworthiness, supported by the rigorous operator-theoretic guarantees of our framework.

6 Basic Linear Analysis Concepts↩︎

\[\mathcal{K}_Q := P_Q \mathcal{K} \big|_{\mathcal{H}_Q}\]

7 Auxiliary Lemmata↩︎

8 On the supervision of policy training in offline goal-conditioned RL↩︎

Table [tab:methods-comparison] distinguishes between ordinary reward-free or zero-shot training and a stricter property denoted as Unsupervised Policy Training. This column should be interpreted as goal-agnostic training and not as a claim that other methods such as FB are not unsupervised RL. This distinction is important because many methods are unsupervised in the sense that they do not use externally provided reward labels during pretraining, but nevertheless train their policy or actor on conditioning variables that are constructed from dataset states treated as goals, targets, or reward/task latents.

We use the following operational definition. Consider a latent-conditioned policy \(\pi(a\mid x,z)\). We say that its training is goal-agnostic if, during policy optimization, the conditioning variable \(z\) is sampled from an exogenous distribution over abstract latent directions and is not instantiated as an embedding of a dataset state selected as a goal. We allow the representation or geometry-learning stage to use states, future states, temporal gaps, or self-supervised relabeling. Our criterion concerns the policy-training stage: whether the policy network itself is trained by seeing real goals, directly as goal inputs or indirectly through goal-derived latent variables.

Under this definition, HILP satisfies goal-agnostic policy training in its core formulation. HILP first learns a temporal representation \(\phi\), and then trains a latent-conditioned policy over arbitrary directions \(z\) in the learned representation space using the intrinsic reward \(r_z(x,x')=\langle \phi(x')-\phi(x), z\rangle.\) The goal state is not used as the policy-conditioning variable during this policy-training phase. A downstream goal is converted into a direction only at test time, for example by using the direction from the current state embedding toward the goal embedding.

IEL follows the same separation principle but replaces HILP’s symmetric geometry with a directed hitting-time geometry. In IEL, replay-buffer states and intermediate trajectory states are used to learn the embedding \(\phi\) and the task identifier \(\omega_\psi(g)\) through self-supervised temporal-gap and identifier losses. This use of goals is part of representation learning, not policy supervision. The resulting foundation policy is trained over abstract directions in the learned geometry, and concrete goals enter only at test time through prompting or graph-based planning. Thus, the policy is not trained on goal labels even though the representation is learned from self-supervised goal relabeling.

This definition separates HILP and our IEL from the rest of reward-free or zero-shot methods. FB representations are reward-free and zero-shot in the usual sense. They learn from reward-free interactions and can construct policies for rewards specified after pretraining. However, the policy parameter in FB is a reward/task latent. Once a reward is specified, FB forms \(z_R = \mathbb{E}[r(s,a)B(s,a)]\) and for a target-state reward this latent can be instantiated from the backward representation of the target state. Moreover, standard deep zero-shot FB implementations sample task vectors partly by passing replay-buffer states through the backward representation, i.e. \(z=B(s)\) for sampled states \(s\). Thus, FB is reward-free but its policy-training distribution is at least partly anchored to reward or goal-state latents rather than purely to arbitrary directions in a learned temporal geometry.

Similarly, goal-conditioned RL and reachability-learning methods train policies, critics, or classifiers on state–goal pairs sampled from the replay buffer, often using future-state or random-state relabeling. These methods may be self-supervised or reward-free, but their policy updates explicitly use dataset states as goals. Therefore they do not satisfy the stricter goal-agnostic policy criterion used in Table [tab:methods-comparison]. The last column of the table identifies whether the policy is trained as a reusable foundation policy whose conditioning variables are not real goals or goal-derived task latents. This is the property needed for our multi-stage planning setting, where concrete goals should be introduced only at test time and composed through the learned temporal geometry.

9 Problem span↩︎

We next clarify when the learned representation can be reused beyond the specific hitting-time regression problem used to train it. A suitable Hilbert representation supports goal-conditioned hitting-time geometry through displacement readouts of the form \(V^\pi(x,g) = \langle \phi(g)-\phi(x),\omega_g^\pi\rangle_{\mathcal{H}}\). A natural question is therefore: which other control tasks can be solved using the same representation, rather than relearning the geometry? We refer to this family of compatible tasks as the problem span of the representation. We aim to identify sufficient conditions under which the same latent geometry can support additional rewards and value functions. We distinguish three notions: (i) reward representability: whether the immediate reward can be read out from the learned latent geometry; (ii) policy-evaluation closure: whether the value function of a fixed policy remains in the latent linear span; (iii) optimal-control closure: whether the Bellman optimality operator preserves the latent value class. The first two follow from natural linear-operator assumptions. The third depends on whether maximization over actions preserves linearity.

9.1 Latent reward span↩︎

We first define the class of immediate rewards that are directly represented by the learned geometry.

This definition says that the reward can be computed from an interaction between the state embedding \(\phi(x)\) and the goal embedding \(\phi(g)\), possibly transformed by an action-dependent task operator \(\mathcal{R}_a\). It is a representability condition on the one-step reward only. By itself it does not yet imply that the corresponding optimal value function is bilinear. Several common goal-conditioned reward families fit this template.

Kernel goal similarity. If \(\mathcal{R}_a=\alpha_a I\) for scalars \(\alpha_a\), then \(r(x,a,g)=\alpha_a\langle \phi(x),\phi(g)\rangle_{\mathcal{H}}\). This is a smooth goal-similarity reward. It should be interpreted as a soft similarity objective, not as an exact hitting-time objective. Exact hitting-time objectives are governed by the Poisson/range-condition results in the main paper.

Weighted or anisotropic goal similarity. If \(\mathcal{R}_a\) is positive semidefinite or low rank, then the reward compares \(x\) and \(g\) only along selected latent directions: \(r(x,a,g)=\langle \phi(x),\mathcal{R}_a\phi(g)\rangle_{\mathcal{H}}\). This covers tasks where different actions or task modes emphasize different aspects of the goal, such as position, object identity, safety-relevant features, or other latent factors.

Region and fuzzy goals. A goal need not be a single state. Let \(\rho_g\) be a distribution over acceptable goal states and define its latent mean embedding \(\mu_g:=\mathbb{E}_{Y\sim\rho_g}[\phi(Y)]\). Then rewards of the form \(r(x,a,g) = \langle \phi(x),\mathcal{R}_a\mu_g\rangle_{\mathcal{H}}\) are also in the problem span. This covers fuzzy goals, goal regions, and safety corridors, provided that the relevant region can be summarized by its latent mean embedding.

Compositional goals. If a downstream task is described by a finite combination of goals \(g_1,\ldots,g_m\), one can define \(\mu:=\sum_{j=1}^m \alpha_j\phi(g_j)\) and use \(r(x,a,\mu)=\langle \phi(x),\mathcal{R}_a\mu\rangle_{\mathcal{H}}\). Thus the representation supports linear composition of goal specifications in latent space.

9.2 Fixed-policy evaluation span↩︎

We next show that latent reward representability becomes a value-function representation result for fixed-policy evaluation, provided that the transition dynamics close linearly in the same representation.

The assumption that \(r_\pi\) is represented by a single operator \(\mathcal{R}_\pi\) is structurally guaranteed in some simple cases, for example when the policy uses a state-independent mixture over action-specific reward operators. In general, however, action probabilities may depend on \(x\), so this assumption should be understood as a policy-level reward closure condition.

9.3 Optimal-control span↩︎

The previous propositions concern policy evaluation. Optimal control requires additional care. Even when each action-value candidate is bilinear, the optimal value is obtained by a pointwise maximization: \(V^*(x,g)=\max_{a\in\mathcal{A}}Q^*(x,a,g)\). A maximum of linear or bilinear functions is not generally linear. Therefore, latent bilinear rewards and latent transition closure do not by themselves imply that \(V^*\) is bilinear. We can nevertheless define the additional closure condition under which optimal control remains inside the problem span.

We adopt optimal closure as an assumption, because the condition \(\mathcal{B}^*\mathcal{V}_\phi\subseteq\mathcal{V}_\phi\) is not guaranteed by construction. It rules out cases where the maximization over actions creates a piecewise-linear or otherwise nonlinear envelope outside the latent bilinear class. Thus the representation supports optimal control for tasks whose Bellman updates are closed in the learned span, but latent bilinear rewards alone do not guarantee this closure.

9.4 Relation to hitting-time geometry↩︎

The hitting-time objectives studied in the main paper are not merely discounted latent-bilinear reward problems. They are undiscounted stopping-time objectives with boundary condition \(V^\pi(g,g)=0\) and unit cost before hitting the goal. Their linear representation is governed by a Poisson equation and the range condition \(\mathbf{w}_{\mathbf{1}} \in \operatorname{range}((\mathcal{K}_\pi-I)^*)\), as established in Theorem 1. The approximation theory in Theorem 3 then shows that compressed latent transition consistency yields controlled error in the corresponding hitting-time predictor. Thus the paper contains two complementary notions of problem span: (i) a hitting-time span, controlled by the Poisson/range-condition theory and used directly by IEL; and (ii) a discounted reward span, where additional latent-bilinear rewards can be evaluated or optimized when the relevant Bellman closure conditions hold.

9.5 When should the representation work?↩︎

IEL-style representations are useful under the following conditions: (i) Predictive latent closure. The representation should make one-step latent prediction approximately linear: \(\mathbb{E}[\phi(X')\mid x,a]\approx \mathcal{K}_a\phi(x)\). If important transition-relevant information is absent from \(\phi(x)\), then no linear readout can recover it downstream. (ii) Goal information is represented in the latent space. The downstream task should depend on goals through features present in \(\phi(g)\), or through simple combinations such as mean embeddings or finite linear mixtures of goal embeddings. If the task depends on goal attributes that are not encoded by \(\phi\), it lies outside the problem span. (iii) Rewards or costs admit latent readouts. For discounted reward tasks, the immediate reward should be expressible, at least approximately, as \(r(x,a,g)\approx \langle \phi(x),\mathcal{R}_a\phi(g)\rangle_{\mathcal{H}}\). For hitting-time tasks, the unit-cost representer and Poisson/range condition play the analogous role. (iv) The effective horizon is controlled. Local representation errors accumulate through the relevant resolvent. Long horizons, nearly noncontractive transient dynamics, or poor goal reachability can amplify small one-step errors into large value errors. (v) Optimal control may require additional closure. For policy evaluation, latent transition and reward closure are enough. For optimal control, the maximization over actions must also preserve the latent value class, or one should interpret the representation as supporting approximate rather than exact optimal planning. All in all, the learned IEL geometry provides a shared displacement and transition structure rather than a universal reward solver. It enables reuse across goal-conditioned tasks where rewards, boundary conditions, and Bellman updates remain compatible with this established geometry.

10 Main Results↩︎

10.1 Proof of Theorem 1↩︎

10.2 Proof of Theorem 2↩︎

10.3 Proof of Corollary 1↩︎

10.4 Proof of Lemma 1↩︎

10.5 Proof of Theorem 3↩︎

10.6 Proof of Theorem 4↩︎

10.7 Proof of Theorem 5↩︎

This subsection proves Theorem 5. The proof has two steps. We first establish a finite-sample excess-risk bound for the phase-2 tuple-regression problem induced by the hitting-time channel of Algorithm 1, conditional on a fixed frozen task encoder \(\bar \omega_\psi\). We then lift this statistical control to a displacement-topology recovery statement by comparing the learned predictor to a near-oracle reference representation from \(\mathfrak R_\epsilon\), using the coverage assumption on the conditional goal law and the bounded-below property of the reference analysis operator.

11 Algorithm Pseudocode↩︎

12 Experiment details and additional results↩︎

Hyperparameter configuration. See Table 2 for the hyperparameter configurations used to generate the results in Table 1. Several parameters specific to Isomorphic Embedding Learning (IEL) can be tuned to optimize performance based on the environment’s structural characteristics and the quality of the offline dataset.

Hyperparameter sensitivity. As shown in Table 3, almost all evaluated configurations yield performance within two standard deviations with respect to the best-performing configuration. This proximity suggests a failure to reject the null hypothesis—that there is no statistically significant difference between these configurations—under standard significance testing. We therefore conclude that IEL is robust and not overly sensitive to the hyperparameter ranges.

Tuning rules of thumb. Firstly, \(\beta\) determines the sharpness of the enforced topology in the embedding space, defining the perceived distance between nearby points. For datasets with high noise or low structure, a low \(\beta\) (\(< 0.1\)) is recommended for training stability. In contrast, datasets with high-quality, expert trajectories can be better resolved with \(\beta \in [0.3, 1.0]\). Secondly, \(H_{\max}\) defines the prediction horizon for hitting times. While low values (\(H_{\max} \le 5\)) ensure stability, they limit the agent’s ability to differentiate between long-range goals. Conversely, excessively large values (\(H_{\max} \ge 30\)) can introduce variance that leads to chaotic predictions. For general use, \(H_{\max}\) is relatively easy to tune by observing the distribution of trajectory lengths; it should be set high enough to capture meaningful progress but low enough to avoid the noise of unstructured exploration. Thirdly, \(\tau'\) denotes the expectile for hitting time regression. Decreasing \(\tau'\) encourages the exploitation of shorter paths, which is effective when the hitting time range \(H(u)\) is narrow (e.g., in expert datasets). When dataset quality is unknown, the unbiased \(\tau'=0.5\) provides the most robust results.

Coreset selection and computational efficiency. Regarding evaluation, the coreset selection parameter \(\sigma\) determines the similarity threshold between points. This parameter is heavily dependent on the embedding scale set by \(H_{\max}\). We find that \(\sigma \in [0.3\mu, 0.75\mu]\), where \(\mu\) is the mean pairwise distance in the coreset, provides a reliable heuristic for tuning. Coreset selection primarily serves two distinct purposes: it limits the number of vertices in the planning graph to control computational complexity, and it removes distribution bias from the dataset. By reflecting the spatial coverage rather than the density of the original data, the coreset enables unbiased, coarse-grained long-horizon planning. Increasing the size of the coreset beyond the point of sufficient spatial coverage yields diminishing returns and can potentially degrade planning performance. This occurs when the graph becomes too fine-grained, presenting short-distance targets that fall below the resolution of the hitting-time predictions the agent was trained on. Consequently, an ideal coreset is one where the mean distance to \(k\)-nearest neighbor (\(k\)-NN) vertices is approximately constant across the state space and remains proportional to the hitting times seen during training. We configured the coreset size to ensure Asym-Graph evaluation remains proportional to Rec-Mid wall-clock time. Specifically, Rec-Mid with 50,000 samples requires 400–600 seconds, while Asym-Graph with a coreset size of \(2^{13}=8192\) takes approximately 700 seconds. For reference‚ Sym-Graph requires only \(150\) seconds. These timings vary with the specific graph topology and complexity.

All experiments were conducted on a system equipped with an NVIDIA GeForce RTX 4090 (24 GB VRAM) and an Intel Core i7-14700K (96 GB RAM). A full experimental cycle, including model training and final evaluation, requires approximately one hour.

3pt

5pt

References↩︎