Horizon Generalization in Reinforcement Learning
Authors: Vivek Myers
Catherine Ji
Benjamin Eysenbach
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning
generalization
invariance
planning
Primary area: reinforcement learning
TL;DR: Can you make RL policies that generalize from short-horizon goals to long-horizon goals?

Abstract: We study goal-conditioned RL through the lens of generalization, but not in the traditional sense of random augmentations and domain randomization. Rather, we aim to learn goal-directed policies that generalize with respect to the horizon: after training to reach nearby goals (which are easy to learn), these policies should succeed in reaching distant goals (which are quite challenging to learn). In the same way that invariance is closely linked with generalization is other areas of machine learning (e.g., normalization layers make a network invariant to scale, and therefore generalize to inputs of varying scales), we show that this notion of horizon generalization is closely linked with invariance to planning: a policy navigating towards a goal will select the same actions as if it were navigating to a waypoint en route to that goal. Horizon generalization and invariance to planning are appealing because of their potential reach: they imply that a policy trained to reach nearby goals would succeed at reaching goals that are arbitrarily more distant.Our theoretical analysis proves that both horizon generalization and planning invariance are possible, under some assumptions. We present new experimental results, as well as recalling results from prior work, in support of our theoretical results. Taken together, our results open the door to studying how techniques for invariance and generalization developed in other areas of machine learning might be adapted to achieve this alluring property.

Published as a conference paper at ICLR 2025
HORIZON GENERALIZATION IN REINFORCEMENT LEARNING
Vivek Myers' UC Berkeley
Catherine Ji Princeton University cj cj7280@princeton.co edu
Benjamin Eysenbach Princeton University
wmyers@berkeley.c edu
eysenbach@prrnnctton. edu
ABSTRACT
We study goal-conditioned RL through the lens of generalization, but not in the traditional sense of random augmentations and domain randomization. Rather, we aim learn goal-directed policics that generalize with respect the horizon: after training to reach nearby goals (which are casy to learn), these policies should succeed in reaching distant goals (which are quite challenging lo learn). In the same way that invariance is closely linked with generalization other areas machine learning (e.g., normalization layers make network invariant to scale, and therefore generalize to inputs of varying scales), we show that this notion of horizon generalization is closely linked with invariance to planning: policy navigating towards goal will select the same actions as were navigating to a waypoint en ronte to that goal. Thus, such policy trained to reach nearby goals should succeed reaching arbitrarily-distani goals. Our theoretical analysis proves that both horizon generalization and planning invariance are possible, under some assumptions. We present new experimental results and recall findings from prior work in support of our theoretical results. Taken together, our results open the door to studying how techniques for invariance and generalization developed other areas of machine learning might be adapted to achieve this alluring property.
INTRODUCTION
Reinforcement learning (RL) is appealing for its potential to use data solve long- horizon reasoning problems. However, it precisely this horizon that makes solving the RL problem difficult the number of possible solutions to a control problem often grows exponentially in the horizon (Kakade, 2003). Indeed, the requirement of collecting long horizon data precludes several potential applications of RI. (e.g., health care, robotic manipulation). Thus, desirable property of an RL algorithm is the ability to learn from short-horizon tasks and generalize long- horizon tasks. We call this property horizon gemeralization.
optimal for all (s.s') given:
5's <e
d(s, 20
s'
s"'
d(s, < 4c
Figure Horizon generalization. A policy generalizes over the horizon if performance for start-goal pairs (8, g) separated by a small tem- poral distance d(s, g) < yields improved perfor- mance over more distant start-goal pairs (s'.g') with d(s'. .g') >
Horizon Generalization (informal state- ment, see Definition 4): A goal-conditionel policy generalizes training to reach nearby goals, the policy is more successful at reaching distant goals.
the horizon if, after
Prior work on generalization in RL almost exclusively focuses on either (i) perceptual changes (e.g., changes in lighting conditions), (ii) simple randomizations of simulator parameters, or (ii) mapping together states and actions with the same reward or value function. While these methods show improved performance on perturbed datascts over the same horizon,
Website and code: iiaaai "Equal contribution.

---

Published as a conference paper at ICLR 2025
they do not generalize over horizon. In this paper, we formalize horizon generalization as a potential property of goal-conditioned RL (GCRL) algorithms, prove that policies with horizon generalization exist, and empirically demonstrate that certain algorithms enable horizon generalization in high-dimensional settings. We do so in the context of goal-conditioeed RI, where agents navigate towards specific goal in a reward-free setting.
A key mathematical tool for understanding horizon generalization is a form of lemporal invariance obeyed by optimal policies. In the same way that an image classification model that is invariant to rotations will generalize images of different orientations (Cohen and Welling, 2016; LeCun et al., 2004), we prove that a policy invariant to planning, under certain assumptions, will exhibit. horizon generalization.
Planning Invariance (informal statement, see Definition 3): A goal-conditioned policy is inmarianl to planning if il can reach distand goals with similar success when conditioned directly on the gool compared to when conditioned on a series of intermediate waypoints. In other words, breaking up a complez task into series of simpler tasks confers advantage.
The main takeaway from this paper is that there rich notions of generalization over the horizon unique to the goal-condi RL (GCRL) setting. We show that existing quasimetric methods (Wang et al., 2023; Myers et al., 2024a) already exhibit this form of generalization in high-dimensional settings. By theoretically and empirically linking planning with this form of generalization, our work suggests practical ways (ic. quasimetric methods) to achieve powerful notions of generalization from short to long horizons.
2 RELATED WORK
Our work builds upon prior work in goal-conditioned RL and generalization in RL. Section 5.5 returns to the discussion of prior work in light of our analysis.
Learning to Reach Goals. The problem of learning goal-reaching behavior dates to the early days of AI research (Newell, 1959; Laird et al., 1987). This problem has received renewed attention in recent years through the study of deep goal-conditioned reinforcement learning (GCRI.) (Chen et al., 2021; Chane-Sane et al., 2021; Colas et al., 2022; Yang et al., 2022; Ma et al., 2022; Schroecker and Isbell, 2020; Janner et al., 2021). Goal-conditioned RL relieves the burden of specifying rewards, as any state in the environment can provide a complete task specification when usod as a goal. Some of the excitement in goal-conditioned RL is a reflection of the recent success of self-supervised methods in computer vision (c.g., stable diffusion (Rombach et al., 2022)) and NLP (GPT-4 (OpenAl et al., 2024)): if these methods can achieve intriguing emergent properties (Anil et al., 2022; Brohan el al., 2023), might a self-supervised approach to RL. unlock emergent, properties for RL?
Generalization in RL. Prior work on generalization in RL mostly focuses on variations in perception (Cobbe et al., 2019; Stone et al., 2021; Laskin et al., 2020) (or, similarly, c.g., across levels of a game (Nichol et al., 2018; Farebrother et al., 2018; Justesen et al., 2018; Zhang et al., 2018)). Similarly, work robust RL (which measures worst-case notion of generalization) usually randomly perturbs the physics parameters (Packer et al., 2018; Eysenbach and Levine, 2022; Moos et al., 2022; Tessler et al., 2019; Tgl et al., 2019)). We study a different form of generalization: without changing the dynamics or the observations, can a policy trained on nearby goals succeed in reaching distant goals?
State Abstractions for Decision-Making, Many approaches for learning improved state abstractions for decision making have been proposed in recent years, including bisimulation (Ferns et al., 2011; Zhang et al., 2021a; Hansen-Fsstuuc et al., 2022), successor representa- tions (Dayan, 1993; Barreto et al., 2017), and information-thcoretio representation learning objectives (Anand et al., 2019; Rakelly et al., 2021; Castro et al., 2021; Jain et al., 2023). While prior work typically views generalization with similar horizons, horizon generalization is about generalizing from short to long horizons. Prior work that has investigated out-of -ut-o--iistrbbutin, long- horizon tasks has required extra assumptions about the setting, such as access to external planners (Singh et al., 2023; Shah and Levine, 2022; Myers et al., 2024b) or human demonstrations (Mandlekar et al., 2021).
problem of handling shift between MDPs
2

---

Published as a conference paper at ICLR 2025
3 PLANNING INVARIANCE AND HORIZON GENERALIZATION
Our analysis will focus on the goal-conditioned sctting. We first motivate our key formal defi- nitions (planning invariance and horizon generalization), provide preliminaries on quasimetric methods, and prove that these properties can be realized by quasimetric methods.
3.1 INTUTTION
Many prior works have found that augmenting goal-conditioned policies with planning can significantly boost performance (Savinov et al., 2018; Park et al., 2024): instead of aiming for the final goal, these methods use planning to find a waypoint en route to that goal and aim for that waypoint instead. In effect, the policy chooses a closer, casier waypoint that will naturally bring the agent closer to the final goal.
Invariance to planning (see Fig. 2) an appealing property for sev-
no planning invariance
planning invariance
eral reasons. First, it implies that
the policy realizes the benefits of
planning without the complex ma- chincry typically associated with hierarchical and model-based meth- ods. Second, policies optimal over space of tasks are, by definition, planning-invan invariant over the same space with respect to optimal planner: invariance to planning is necessary but not sufficient con- dition for policy optimality, and can be used as an inductive bias to achieve policy optimality. Third, we show that planning invariance, combined with other assumptions, implies that the policy will exhibit horizon generalization: given that a policy successfully navigates short at performing long-horizon tasks over the same state space S (Fig. 1).
* oe *
Figure 2: Visualizing planning invariance. Planning invariance (Definition 3) means that a policy should take similar actions when directed towards a goal (purple arrow and purple star) as when directed towards intermediale waypoint (brown arrow and star). We visualize policy with (Right) and without (Left) this property via the misaligmment and alignment of actions towards the waypoint and the goal, where the optimal path is tan and the suboptimal is gray.
trajectories covering some state space S, it will succeed
How do we actually construct methods that are planning invariant and lead to horizon generalization? To answer this question, build upon prior work on quasimetric neural network architectures (Liu et al., 2023; Wang and Isola, 2022b;a) and show that policies defined greedily with respect to quasimetric, where latents obey the triangle inequality, are invariant to planning with respect to the same quasimetric.
PRELIMINARIES
We consider controlled Markov process M with state space S, action space A, and dynamics p(s' 8, s,a). The agent interacts with the environment by selecting actions according to a policy m[a 8), which is mapping from S to distributions over A. We further assume the state and action spaces are compact. We define the discounted state occupancy measure with actions as
(5 = a)
(s. = = (. =
(1)
where pr / so a) is the probability density that policy π visits state after time steps when initialized at state with action a.
Quasimetrics on states. We equip M with an additional notion of distance between states.
We later define planning operator PLAN and policy greedily with respect to this distance. At the most basic level, a distance d S x S + R must be positive for all inputs (s, s' + s) and zero for all inputs s) (nonnegativity). We will denote the set of all distances as D:
D a (d: SSSC
S S R d(s, 0, d(s 8') > O for each s' E where s # s').
(2)
3

---

Published as a conference paper at ICLR 2025
A desirable property for distances to satisfy is the triangle inequality. A distance satisfying this property known as a quasimetric, and we define the set all quasimetric functions as
Q - {d E D: (( S d(s, w) + ((w,9) for all 8, 9, w E S)-
(3)
If we were to restrict the distances to be symmetric (d(x, y) d(y. our quasimetric would become a standard metric obeying nonnegativity, the triangle inequality, and symmelry. However, wish to quasimetric that allows for asymmetry the start and end states: the navigation task 8 + may be completely different from + 8, and the corresponding distance function should reflect this degree of freedom.
the interchange of
An important property of quasimetrics that they are invariant to the path relazation operator from Dijkstra's algorithm.
Definition 1 (Path relaxation operator). Let PATHa(S,,) g) be the path relazation operator over quasimetric d(s,g) For any triplet of states (s, w. g) xxx8,
d(s.g) + PATHA(S, min d(s, w) + d(w,g)
(4)
Thus, invariance to the path relaxation operator is a form of self consistency. Any triplet of distance predictions should satisfy the following property:
d(s.g) g) S d(s, + d(w.g)
which is the familiar triangle inequality. Quasimetries naturally satisfy this property and, combined with nonnegativity conditions, are invariant. under the path relaxation operator.
Successor distances (a quasimetric). A particular quasimetric of note here is the successor state distance (Myers et al., 2024a), dgD: defined as
(sx = 90 = g) p (SK = 9 So s)
(s g) min log
where K~ Geom(1 - 7).
The successor distance d&D is a compelling choice of distance because minimizing the distance to the goal (s, g) corresponds to optimal goal reaching with discount factor 7. y The related successor distance with actions dgD (s, a, g) (Myers et al., 2024a) allows us to optimize this distance over actions:
(9K 9 90 = 9) (5 =
(s, a min log
s.a] where K Gcom - 7)-
(6)
Given temporal distances between states and state-action pairs, we can define a quasimetric policy that greedily selects actions with respect to a(),
Definition 2 (Quasimetric policy). We define the quasimetric policy some policy vala | s. g. where
Tz(a s.g) E arg min d(s, a. a.g).
aEA
Here, d(s, a) is the successor distance with actions (Eq. 6).
INTRODUCING AND ANALYZING HORIZON GENERALIZATION
Equipped with these definitions, we can formally define planning invariance and horizon generalization in deterministic and stochastic settings. Then, we show that quasimetric policy za(a g, is planning invariant with respect to planner defined over the same quasimetric. Finally, we show that this invariance to planning implics horizon generalization. Taken together, our analysis shows that horizon generalization exists and can be achieved by quasimetric methods.
5.1 DEFINITIONS OF PLANNING INVARIANCE AND HORIZON GENERALIZATION
To construct general definitions of planning invariance and horizon generalization, will need to define a planning operator which proposes waypoints at. a given state to reach a target distribution over goals.
Formally, define an MDP with the goal-conditioned reward function ry(s) = d(s.)); Kronecker delta function which evaluates to 1 if 8 and 0 otherwise. The dyp -innimiing policy is optimal for this MDP.
4

---

Published as a conference paper at ICLR 2025
We denote by
plan - (PLAN: 8 A(S) A(S)
(7)
the class of planning functions that predict a distribution of waypoints from states and goals. In the special case of deterministic actions, waypoints, and goals, we write
plan PI A {PLANPIX :S x S + S} C plan.
(8)
Our analysis in the rest of this section will focus on the simpler "fixed" setting of PLANFIX plan We will use WPLAN to denote the waypoint produced by PLANFIX The proofs and quasimetric objects in the stochastic setting are slightly more complicated, but carry the same structure and lakeaways as this simpler case; the general stochastic proofs and definitions are presented in Appendix B. For notational brevity, we drop the label in the rest of the analysis section.
There are many possible planning algorithms one could use (e.g., Dijkstra's algorithm (Di- jkstra, 1959), A* (Hart et al., 1968), RRT (La and Kuffner, 2001)). Importantly, the constraints of a quasimetric (sce Section 4) and the related idca of path relorations from Dijkstra's algorithm provide clues for specifying our planning operator later in our analysis. We use this planning operator in one of our key definitions (visualized in Fig. 2):
Definition 3 (Planning invariance). Consider a deterministic MDP with states S, actions A, and goal-condilioned Kronecker della reward function rg(s) = ((s.))- For any goal-condilioned policy (a s, g) where S, we say that x(a s, g) is invoriant under planning operator PLAN E plan if and only if
x(a s.g) = x(a 8, W)),, where w PLAN(S,g).
(9)
Note that planning invariance says nothing about whether the planner is good or bad. We will primarily be interested in invariance under the optimal planner with respect to some quasimetric d(s,g). We denote the class of quasimetric planning functions as
plan, A (PLAN& E plan| d(s,, PLAN((,,)) g)) + (S.L.AAA,..))....... d((,.)) for all (8,9) ES
Our second key definition is horizon generalization (see Fig. 1):
Definition 4 (Horizon generalization). Suppose e O and d(s,g) is quasimetric over the start-goal space S x S. In the single-goal, controlled ("fized") ") case, a policy a(a s. generalizes over the horizon if optimality over nearby start-goal pairs B. = [(.gg) S x S d(s.g) < c} everywhere implics optimality over the entire state space S.
We highlight the key base case assumption: optimality over shorter trajectories that cover the entire desired state space S lcads to horizon gencralization. We assume this base case holds everywhere- -onibeereewee without additional assumptions about the symmetrics of the MDP, it is beyond the scope of this work to consider horizon generalization to completely unseen states. Rather, we analyze generalization to unseen, long-horizon (8,g) state pairs.
5.2 QUASIMETRIC POLICIES ARE (NONTRIVIALLY) PLANNING INVARIANT
With these notions of planning invariance and horizon generalization in hand, we will consider nontrivial quasimetric planning algorithms PLAN& E plan, that acquire a quasimetric d(s,g) g) and output a single waypoint w E S:
PLANa(s, g) = WPLAN arg min @argmin wes
d(s, w) + d(w.g).
(10)
Note that this planning algorithm takes the form of the path relaxation operator (Definition 1). By the triangle inequality, we have d(s, WPLAs) + d(WPLAN: g) = d(s g). Our first result is that quasimetric policies Fa are invariant under planning operator PLANA.
Theorem 1 (Quasimetric policies are invariant under PLAN2). Given a deterministic MDP with states S, actions A, and goal-conditioned Kronecker delta reward function rs(s) = 8( define quasimetric policy Ta(a s. g) and quasimetric planner class plan Then, for every quasimelric planner PLANA E plan,; there always erists a policy nala 88 8,9) that is planning invoriant:
Ta(a 8.9) = Ta(a 8, w for w PLANa(8,g)).
(11)
5

---

Published as a conference paper at ICLR 2025
The proof is in Appendix B.1. In practice, we measure planning invariance by comparing the relative performance of algorithms with and without planning. For this condition, we do not necessarily need Ta(a s.g) aa(a 8, WPLaN);; rather, the weaker condition d(s, ma(a 9) d(s, aa 8, (PLAN)) WPLAN) ) is sufficient, and necessary for planning invariance when there are no errors from function approximation and noise. We extend this result to stochastic settings in Appendix B.3.
5.3 QUASIMETRIC POLICIES GENERALIZE OVER THE HORIZON
Our main result of this section to prove that horizon generalization cxists for quasimetric policies through an inductive argument.
Theorem 2 (Horizon generalization exists). Consider an MDP with states S, actions A,
and goal- conditioned Kronecker delta reward (s(s) ((.g)) For any quasimetric d(s, g) over the start-goal space S x S and > O, the quasimetric policy va(a 8,9) that is optimal over B. = ((5,9) S x S d(s,g) < <c} is optimal over the entire starl-gool space x S.
The idea of the proof is to begin with a ball of states (c(s)= {s' E E d(s, s') < c} on which the policy Ta(a s;-) is optimal, and show that planning invariance and the triangle inequality in turn imply optimality over a ball of states with double the radius (2)(s).
Thus, there must exist glanning-invariant goal-reaching policies that generalize over the horizon: optimality over pairs of close states everywhere implies optimality over arbitrarily distant pairs of states. The complete proof, extended to stochastic settings, is in Appendix B.4.
We also observe that. horizon generalization is not guaranteed for goal-reaching policy that nol planning invariant (Remark 3, see Appendix B.5 for proof).
Remark 3 (Horizon generalization is nontrivial). Let finite > O and goal-conditioned MDP with states S, actions A, and goal-condilionedd Kronecker della reward function rg(#)= = be given where there are no states oulside of S. For policy that is not planning invariand, optimality over B. = ((, g) E S x S d(>,g) < c} is not a sufficient condition for optimality S.
over the entire start-goal space
Combined, these results show that planning invariance and horizon generalization, as defined in Section 5.1, exist in nontrivial forms via quasimetric policies.
5.4 LIMITATIONS AND ASSUMPTIONS
Despite our theoretical results proving that hori- zon generalization exists, expect that practi- cal algorithms will not perfectly achieve horizon generalization.
planning invariance
1.0
The "reach" of planning invariant policy corresponds to the area under this curve
Success
0.5
An assumption in our inductive proof is that horizon generalization exists as a binary cate- gory. However, in practice, each application of the inductive argument will incur some error, so the extent of horizon generalization will not. be indefinite.
0.0
planning invariance
1.0
Saccess Rate
Concretely, define SUCCESS(c) as the success rate for reaching goals in radius c, and assume that choose cp small enough that SUCCESS(c,) 1. Suppose each time the horizon is doubled (co - 2c, - 4cp - ...... the success rate de- creases by a factor of п. We will refer to as the horizon generalization parameter and later measure this parameter in our experiments (Section 6). We can now define the REACH as the sum of SUCCESS(c) over e 2 co. With the above constraints on SUCCESS(c), the worst case,
0.5-
0.0
0
5
10
15
20
25
30
Distance Goal
Figure 3: Approzimate horizon general- ization is still useful. SUCCESS when there is horizon generalization. When the attenuation factor v) 2 0.5, the REACH goes to oc. For a policy with no horizon general- ization (n 0), its REACH = 1.
REACH = -1 7 2) + 78 4) + ...
1+ if 1Oen21/2
(12)
00 if 12122/

---

Published as a conference paper at ICLR 2025
When there is no horizon generalization, the Reach is 1. We see this by integrating the success curve in Fig. 3. When the degree of horizon generalization has a low value of (say) 7 0.1 (i.e., it generalizes for only 1 out of every 10 goals), the Reach is 1.125, not much bigger than that of a policy without horizon generalization. Once the degree of horizon generalization reaches n 1/2 (i.e.; generalizes for 1 out of every two goals), the Reach is infinite. In short, the potential reach of horizon generalization is infimite, even when each step of the recursive argument incurs non-negligible degree of error.
second assumption behind our analysis is that the basc case holds everywhere: the policy must succeed at reaching all nearby goals when initialized at all possible starting states. In practice, this may translate to a coverage assumption on the training data. If the base case does not hold (poor performance not expect to see optimality over arbitrarily hard goals. We observe this empirically in our experiments (Fig. 4): random policy is invariant to planning (it always selects random actions, regardless of the goal) yet its performance on nearby goals is poor, so the policy fails to exhibit. horizon generalization.
easy goals) but planning invariance holds, then we do
Finally, note that invariance under any arbitrary planner does not guarantee horizon gener- alization. Rather, only invariance under a planner that minimizes an asymmetric distance (quasimetric) lcads horizon gencralization.
Nonetheless, planning invariance is attractive for several reasons: (1) planning-invarinnn
policies potentially automatically get the benefits of plamning, (2) optimal policies are
invariant under optimal planners, and, as we show in our analysis, (3) invariance to planners
that shorten quasimetric distances leads to horizon generalization (Theorem 2).
5.5 WIICH PRACTICAL METHODS MIGIT EXIшBт HORIZON GENERALIZATION?
Temporal difference methods (Ziebart et al., 2008), quasimetric architectures (Wang et al., 2023), RL algorithms (Savinov al., 2018), and data augmentations (Ghugare et al., 2024) that employ explicit planning all achieve planning invariance under some assumptions.
Appendix C discusses these methods in more detail. In Appendix C.1, we discuss several new directions for designing RL algorithms that are invariant to planning. Appendix C.2 recalls figures from prior works in search of evidence for horizon generalization.
EXPERIMENTS
The aim of our experiments to demonstrate horizon generalization and planning invariance in existing RL settings, and to study the extent to which existing methods already achieve these properties. We also present an experiment highlighting why horizon generalization is a useful notion even when considering temporal difference methods (Section 6.2).
We start with a didactic, tabular navigation task (Fig. 11), connecting short horizon tra- jectories and evaluating performance on long-horizon tasks. In our first experiment, we measure the empirical average hitting time distance between all pairs of states. We define policy that acts groedily with respect to these distances, mcasuring performance of this "metric regression" policy in Fig. 4 (Top Left). The degree of horizon generalization can be quantified by comparing its success rate nearby (8,g) pairs to more distant pairs, We compare to a "metric regression with quasimetric" method that projects the empirical hitting times into quasimetric by performing path relaxation updates until convergence (d(s.g) + min,, d(s, w) + d(w, g)). Fig. (Top Left) shows that this policy achieves near perfect horizon generalization. While this result makes intuitive sense (this algorithm is very similar to Dijkstra's 's algorithm), it nonetheless highlights one way in which a method trained on nearby start-goal pairs can generalize to more distant pairs.
We study planning invariance of these policies by comparing the success rate of each policy (on distant start-goal pairs) when the policy is conditioned on the goal versus on a waypoint. See Appendix E for details. As shown in Fig. (Top Right), the "metric regression with quasimetric" policy exhibits stronger planning invariance, supporting our theoretical claim that (Theorem 1) planning invariance is possible.
We next study whether these properties exist when using function approximation. For this experiment, adopt the contrastive RI. method (Eysenbach et. al., 2022) for estimating
7

---

Published as a conference paper at ICLR 2025
Tabular Horizon Generalization
Tabular Planning
1.0
Success Rate
Success Rate
0.5
10
20
25
30
40
45
Goal Distance
random
metric regression
metric regression
+ quasimetric
random
metric regression
no planning
planning
regression quasimetric
Horizon Generalization with Function Approximation
Planning with Function Approximation
1.0
Success Rate
0.5
0.5
10
20
30
40
50
Goal Distance
0.0
CRL (MLP)
CRL (de))
CMD-1
CMD4 (Cood dARR)
CRL (Crad de) CRL (Cayn. de))
CRL (Coed + dg)
no planning
planning
(Rond dsrr)
random
Figure Quantifying horizon generalization and invariance planning. On a simple navigation task, we collect short trajectories and train two goal-conditioned policies, comparing both to random policy. (Top Left) We evaluate on (s,g) pairs of varying distances, observing that metric regression with quasimetric exhibits strong horizon generalization. (Top Right) In line with analysis, the policy that has strong horizon generalization also more invariant to planning: combining that policy with planning does not increase performance. (Bottom Row) We repeat these experiments using function approximation (instead of a tabular model), observing similar trends.
the distances, comparing different architectures and loss functions. The results in Fig. 4 (Bollom Left) show that both the architecture and the loss function can influence horizon generalization, with the strongest generalization being achieved by CMD-1 (Myers et al., 2024a). Intuitively this makes sense, as this method was designed to exploit the triangle inequality, which is linked planning invariance. Fig. (Bottom Right) shows the degree of planning invariance for these policies. Supporting our analysis, the policy most invariant to planning when trained on short horizon tasks shows the strongest horizon generalization.
To better understand the relationship between planning invariance and hori- von generalization, we used the data from Fig. 4 (Bottom Left) to estimate the horizon generalization parameter 1) (see Section 5.4), and used the data from the (Bottom Right) to compute the ratio of performance with and without plan- ning (Fig. 7). These two quantities are well correlated, supporting Theorem 2's claim that horizon generalization is closely linked to planning invariance. Methods that use an 1.2-distance param- eterized architecture showed stronger horizon generalization and planning in- variance than that which uses an MLP, Figure 7: Relating horizon generalization (x-axis) to suggesting that some degree of planning planning invariance (g-axis).
Horizon Generalization and Planning Invariance
Planning Invariance
fraction
success rate relained without planning
0.8
0.4
fraction of retained goals 2x further away
CMD-1 (Crud + duse)
CRL (Cout di,)
CRI + d(.)) CRI (form
CRL (Coed + duun)
random
invariance is possible even without quasimetric architecture. Intriguingly, methods using the L2 architecture have a value of 17 ss 0.5, right at the critical point between bounded and unbounded reach (see Section 5.4). The CMD-1 method, which is explicitly designed to
8

---

Published as a conference paper at ICLR 2025
(a) Aut Euvironment
(b) Success rates stratified by distance to goal
Horizon Generalization in Ant Continuous Control Domain
1.0
CRL (de, Lnea)
CRL (di,, Lawe)
Goal Distance H
CRL (de, Caymn
CMD-1 (dyaN, Lowa)
0.8
SAC (QMur Lua)
Goal
0.6
Success
0.4
0.2
Agent
0.0
mm
10m
10m
15m
15m
20m
20m - 25m
25m 330m
short fasks
long eval
Distance to goal
Figure 5: Measuring horizon generalization in high-dimensional (27D observation, 8DoF control) task. (Teft) We use an enlarged version of the quadruped "ant" environment, training goal-conditioned RL methods on (start, goal) pairs that are most 10 meters apart. (Riggh)) We evaluate several RL methods, measuring the horizon generalization results reveal that (i) some degree of horizon generalization is possible; (si) the learning algorithm influences the degree of generalization; (tii) the value function architecture influences the degree of generalization; and (iv) method achieves perfect generalization suggesting room for improvement future work. The ratio success at 10m vs 5m and 20m vs 10m corresponds to from Section 5.4.
each. These
(a) AntMaze
(b) Humanoid
value
value
Godl
Goal
Distanec
CMD
CRL
Distance
CMD
CRL
1.00
1.00
1.00
1.00
15m
0.93
0.10
15m
0.69
0.60
Agent
25m
0.25
0.00
Agent
25m
0.24
0.16
Figure 6: Illustrating Horizon Invariance in Additional Environments. (Left) A large Ant maze environment with winding S-shaped corridor. (Right) A humanoid environment with complex, dighddimessional observation space. We evaluate the horizon generalization measured by 7 for a quasimetric architecture (CMD) and a standard architecture (CRL), quantifying the ratio of success rates when evaluating at 5m vs 10m, 15m vs 30m, and 25m vs 50m after training to reach goals within 10m. The largest values in each row are highlighted.
incorporate the triangle inequality, exhibits much stronger planning invariance and horizon generalization (1) Rs 0.8 > 0.5), well above the critical point.
Note that the random policy an outlier: achieves perfect planning invariance (it always takes random actions, regardless of the goal) yet poor horizon generalization. This random policy highlights a key assumption in our analysis: that the policy always succeeds at reaching nearby goals (in Fig. 4, note that the success rate on the easiest goals is strictly less than 1).
STUDYING HORIZON GENERALIZATION IN HIGH-DIMENSIONAL SETTING
Our next set experiments study horizon generalization and planning invariance in the context of a high-dimensional quadrupedal locomotion task (sce Fig. 5). We start by rumning a series of experiments to compare the horizon generalization of different learning algorithms (CRL (Eysenbach et al., 2022) and SAC (Haarnoja et al., 2018)) and distance metric architectures (details in Appendix E). The results in Fig. 5 highlight that both the learning algorithm and the architecture can play important role in horizon generalization, while also settings remains
underscoring that achieving high horizon generalization in open problem. See Table 1 for summary of the methods used in these experiments.
9

---

Published as a conference paper at ICLR 2025
CMD (Cbed + daRN)
CRL (Coed + dxip))
success rate
1.0
bellman error
-1.5
0.0
nearby distant goals
20000
40000
goals
gradient steps
Figure Impact of horizon generalization on Bellman errors. (Left) Two goal-reaching methods exhibit different horizon generalization. (Riggh) Despite neither method being trained with the Bellman loss, we observe that the method with stronger horizon generalization has a lower Bellman loss. Thus, understanding horizon generalization may be important even when using TD methods (which guarantee horizon generalization convergence).
These trends hold in more complex environments as well: Fig. shows greater horizon generalization (as measured by the valuuue defined in Section 5.4) for CMD-1 architecture compared to a CRL architecture in both an Aate and a Humanoid environment.
6.2 IMPACT OF HORIZON GENERALIZATION ON BELLMAN ERRORS
Why should somcone using temporal difference method care about horizon generalization, TD methods are supposed to provide this property for free? One hypothesis is that methods for achieving horizon gencralization will also help decrease the Bellman error, especially for unseen start-goal pairs. We test. this hesot by measuring the Bellman error throughout training of the contrastive RL method (same method as Fig. 4), with two different architectures. The results in Fig. 8 show that the architecture that exhibits stronger horizon generalization (dr,) also has lower Bellman error throughout training. Thus, while TD methods may achieve horizon generalization at convergence (at least in the tabular setting with infinite data), a stronger understanding of horizon generalization may nonetheless prove useful for designing architectures that enable faster convergence of TD methods.
CONCLUSION
The aim of this paper is to give a name to a type of generalization that has been observed before, but (to the best of our knowledge) has never been studied in its own right: the capacity to generalize from nearby start-goal pairs to distant goals. Seen from one perspective, this properly is trivial it is an application of the optimal substructure properly, and the original Q-learning method (Watkins and Dayan, 1992) already achieves this property. Seen from another perspective, this property may seem magical: how can one guarantee that policy trained over easy tasks can extrapolate from easy tasks to hard tasks?
We hope to provide theoretical framework for understanding this property a form of self-consistency over model architecture, and show how we can obtain and measure this property in practice. The experiments in Section 6 then connect these insights to concrete advice for structuring the representation for goal-reaching:
1. Policies that model state distance with metric architcctures have planning invariance.
Planning invariance correlated with the degree of horizon generalization of a policy. Quasimetric architectures can enable planning invariance and horizon generalization.
Appendix D discusses further implications of these notions of invariance on model consistency.
Limitations and Future Work. Future work should examine planning invariance and horizon generalization in more complex decision-making environments, such as robotic manipulation and language-based agents. Which versions of the distance parameterizations in Table 1 are most effective at scale should be investigated with larger-scale empirical experiments. We assume a goal-conditioned setting, but there are meany alternative forms of task specification (rewards, language, preferences, etc.) that could similarly benefit from generalization over long horizons. Future work should explore how iinariatt geometry could be extended mapped onto these task spaces.
invariant
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Cindy Zhang, Ryan Adams, and Seohong Park for helpful discussions. We thank Princeton Research Computing for assistance with the numerical experiments. We also thank anonymous reviewers who have helped improve the paper.
REFERENCES
Ankesh Anand, Evan Racah, Sherjil Ozair, Yoshua Bengio, Marc-Alexandre Côté, and R. Devon Hjelm. Unsupervised State Representation Learning in Atari. Newral Information Processing Systems, 2019.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Ra- masesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring Length Generalization in Large Language Models. Neural Information Processing Systems, 38556, 2022.
35(arXiv:2207 (0900019)))0 ):38546 )4304)
André Barreto, Will Dabney, Rémi Munos, Jonathan J. Hunt, Tom Schaul, Hado van Hassolt, and David Silver. Successor Features for Transfer in Reinforcement Learning. Neural Information Processing Systems, arXiv:160600531,, 2017.
Onur Beker, Mohammad Mohammadi, and Amir Zamir. PALMER: Perception-Action Loop With Mcmory for Long-Horizon Planning. Neural Information Processing Systems, 35:34258- -4277,, 2022.
Michal Bortkiewicz, Wladek Palucki, Vivek Myers, Tadeusz Dziarmaga, Tomasz Arczewski, Lukasz Kucifiski, and Benjamin Eysenbach. Accelcrating Coal-Conditioned RL Algorithms and Research. Xix:::2408. 11052, 2024.
Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Xi Chen, Krzysztof Choromanski, Tianli Ding, Danny Driess, et al. RT-2: Vision-Languugo-AAcii Transfer Web Knowledge to Robotic Control. Conference on Robot Learning, 2023.
Models
David J. Burr A Neural Network Digit Recognizer. Proc. IEEE SMC, pp. 1621-1625, 1986.
Pablo Samuel Castro, Tyler Kastner, P. Panangaden, and Mark Rowland. MICo: Improved Representatious via Sampling- Based State Similarity for Markov Decision Processes. Newral Information Processing Systems, 2021.
Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Cond-Cond Reinforcement Learning With Imagined Subgoals. International Conference on Machine Learning, pp. 1430 1440, 2021.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lec, Aditya Grover, Misha Laskin, Picter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision Transformer: Reinforcement Learning via Sequence Modeling, Newral Information Processing Systems, volume 34, pp. 15084-15097, 2021.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep Rein- forcement Learning in a Handful of Trials Using Probabilistic Dynamics Models. Newral Information Processing Systems, 31, 2018.
Philippe Clement and Wolfgang Desch. An Elementary Proof of the Triangle Incquality for the Wasserstein Metric. American Mathematical Society, 136:333 340, 2008
Karl Cobbe, Oleg Klimov, Chris Hesse, Tachoon Kim, and John Schulman. Quantifying Generalization in Reinforcement Learning. International Conference on Machine Learning, 2019.
pp.
Taco S. Cohen and Max Welling, Group Equivariant Convolutional Networks. International
Conference on Machine Learning, 2016.
Cédric Colas, Tristan Karch, Olivier Sigaud, and Pierre-Yver Oudeyer. Intrinsically Motivated Goal- Conditioned Reinforcement Learning: A Short Survey. J. Artif. Intell. Res, 2022.
Thomas Н Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms. MIT press, 2022.
Peter Dayan. Improving Generalization for Temporal Difference Learning: The Successor Representation. Neural Computation, volume 5, pp. 613 624, 1993. Ew Dijkstra. Note on Two Problems in Connexion With Graphs. Numerische Mathematik, 1:269 271, 1959.
11

---

Published as a conference paper at ICLR 2025
Benjamin Eysenbach and Sergey Levine. Maximum Entropy RL (Provably) Solves Some Robust RL Problems. International Conference on Learning Representations, 2022.
Benjamin Eysenbach, Vivek Myers, Ruslan Salakhutdinov, and Sergey Levine. Inference via Interpolation: Contrastive Representations Provably Enable Planning and Inference. Newral Information Processing Systems, 2024.
Benjamin Eysenbach, Tianjun Zhang, Ruslan Salakhutdinov, and Sergey Levine. Contrastive Learning as Goal- Soaal-oodiiiooeed Reinforcement Learning. Neural Information Processing Systems, volume 35, pp. 35603-35620, 2022.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and Regulariza- tion in DQN. arXiv:1810.00123, 2018.
Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation Metrics for Continuous Markov Decision Processes. SIAM Journal on Compuling, 40(6):1662 1714, 2011.
Raj Ghugare, Matthieu Geist, Glen Berseth, and Benjamin Eysenbach. Closing the Gap Be- tween TD Learning and Supervised Learning- a Generalisation Point of View. International
Conference on Learning Representations, 2024.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning With a Stochastic Actor. International Conference on Machine Learning, 2018.
Philippe Hansen-Fstruch, Amy Zhang, Ashvin Nair, Patrick Yin, and Sergey Levine. Bisim- ulation Makes Analogies in Goal- Condiionnd Reinforcement Learning. International Conference on Machine Learning, 2022.
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost. Paths IEEE Transaclions on Systems Science and Cybernetics, 4(2):100-115 1968.
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large Language Models Can Self-Improve. arXiv:2210. 11610, 2022.
Maximilian 1gl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Gencralization in Reinforcement Learning With Selective Noise Injection and Information Bottleneck. Newral Information Processing Systems, 32, 2019.
Geoffrey Irving, Paul Christiano, and Dario Amodei, AT Safety via Debate. 2018.
Arnav Kumar Jain, Lucas Lehnert, Irina Rish, and Glen Berseth. Maximum State En- tropy Exploration Using Predecessor and Successor Representations. Neural Information Processing Systems, 2023.
Michael Janner, Qiyang Li, and Sergey Levine. Offline Reinforcement Learning as One Big Sequence Modeling Problem. Neural Information Processing Systems, 34:1273 1286, 2021.
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Illuminating Generalization in Deep Reinforcement Learning Through Procedural Level Generation.
2018.
Sham Machandranath Kakade. On the Sumple Complexity of Reinforcement Learning. University of London, University College London (United Kingdom), 2003.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical
Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation. Neural Information Processing Systems, 29, 2016.
John E Laird, Allen Newell, and Paul S Roscebloom. Soar: An Architecture for General Intelligence. Artificial Intelligence, 33(1)11-64, 1987.
Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement Learning With Augmented Data. Neural Information Processing Systems, 33:19884 19895, 2020.
Steven M. Valle and James Kuffner. Randomized Kinodynamic Planning. International Journal of Robotics Research, 20(5):378-4D) 2001.
Y. LeCun, Fu Jie Huang, and L. Bottou. Learning Methods for Generic Object Recognition With Invariance to Pose and Lighting. IEEE Computer Society Conference on Computer Vision and Pottern Recognition, volume 2, pp. IT-104 Vol.2, 2004.
12

---

Published as a conference paper at ICLR 2025
Jonathan Lee, Annic Xie, Aldo Pacchiano, Yash Chandak, Chelsea Finn, Ofir Nachum, and Emma Brunskill. Supervised Pretraining Can Learn In-Context Reinforcement Learning.
Neural Information Processing Systems, 36, 2024.
Lisa Lee, Emilio Parisotto, Devendra Singh Chaplot, Eric Xing, and Ruslan Salakhutdinov. Gated Path Planning Networks. International Conference on Machine Learning, pp. 2947-2955, 2018.
Bo Liu, Yihao Feng, Qiang Liu, and Peter Stone. Metric Residual Network for Sample Efficient Conl-Conditioned Reinforcement Learning. AAAI Conference on Artificial Intelligence, volume 37, pp. 8799 8806, 2023.
Kendall Lowrey, Aravind Rajeswaran, Sham Kakade, Emanuel Todorov, and Igor Mordatch.
Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control.
arXiv:1811.01845 2018.
Yecheng Jason Ma, Jason Yan, Dinesh Jayaraman, and Osbert Bastani. How Far I'll
Go: Offline Conl-Conditioned Reinforcement Learning via F-Advantage Regression. arXiv:2206.0300 2022.
Ajay Mandlekar, Danfei Xu, Roberto Martin-Martin, Silvio Savarese, and Li Fei-Fei. Learning to Generalize Across Hong-Horizon Tasks From Human Demonstrations. arXiv:2003.06085, 2021.
Janosch Moos, Kay Hansel, Hany Abdulsamad, Svenja Stark, Debora Clever, and Jan Peters. Robust Reinforcement Learning: A Review of Foundations and Recent Advances. Machine Learning and Knowledge Extraction, 4(1):276-331 2022.
Vivek Myers, Chongyi Zheng, Anca Dragan, Sergey Levine, and Benjamin Eysenbach. Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making. International Conference on Machine Learning, 2024a.
Vivek Myers, Chunyuan Zheng, Oier Mees, Kuan Fang, and Sergey Levine. Policy Adaptation via Language Optimization: Decomposing Tasks for Few-Shot Imitation. Conference on Robot Learning, 2024b.
Ofr Nachum, Haoran Tang, Xingyu Lu,, Shixiang Gu, Honglak Lee, and Sergey Levine. Why Does Hierarchy (Sometimes) Work So Well in Reinforcement Learning? arXiv:1909.0611; 2019.
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural Network Dynamics for Model-Based Deep Reinforcement Learning With Model-Free Fine-Tuning. JEFE International Conference on Robotics and Automation, pp. 7559-7566, 2018.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning With Goal- Conditioned Policies. Neural Information Processing Systems, 32, 2019.
Allen Newell. Report on a General Problem-Solving Program. IFIP Congress, 1959.
Alex Nichol, Vicki Pfau, Christopher Hesse, Oleg Klimov, and John Schulman. Gotta Learn Fast: A New Benchmark for Generalization in RL. arXiv:1804.03722 2018.
OpenAI, Josh Achiam, Steven Adler, et al. GPT-4 Technical Report. arXiv:2303008774, 2024.
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing Generalization in Deep Reinforcement Learning, arXiv:1810.1228; 2018.
Giambattista Parascandolo, Lars Buesing, Josh Merel, Leonard Hasenclever, John Aslanides, Jossica B Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide- And-Conquer Monte Carlo Tree Scarch for Goal-Directed Planning. arXiv:2004.11410, 2020.
Seohong Park, Dibya Ghosh, Benjamin Eysenbach, and Sergey Levine. HIQL: Offline Goal- Conditioned RL With Latent States as Actions. Neural Information Processing Systems, 36, 2024.
Karl Pertsch, Oleh Rybkin, Jingyun Yang, Shenghao Zhou, Konstantinos Derpanis, Kostas Daniilidis, Joseph Lim, and Andrew Jaegle. Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning. Learning for Dynamics and Control, pp. 969-979, 2020.
Silviu Pitis, Harris Chan, Kiarash Jamali, and Jimmy Ba. An Inductive Bias for Distances: Neural Nets That Respect the Triangle Inequality- 2XXi:2002.00522,, 2020.
13

---

Published as a conference paper at ICLR 2025
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning Transferable Visual Models From Natural Language Supervision. International Conference on Machine Learning, arXiv:2103.00020, 2021.
Kate Rakelly, Abhishek Gupta, Carlos Florensa, and Sergey Levine. Which Mutual- Information Representation Learning Objectives Are Sufficient for Control? Neural Information Processing Systems, 34:26345 1-26345-26357, 2021.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Essor, and Björn Ommer.
High- Righ-Resolution Image Synthosis With Latent Diffusion Models. JEEE/CC CVF Conference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
F. Rosenblatt. Principles of Newrodgmamies: Perceptrons and the Theory of Brain Mecha- nisms. Spartan Books, 1961.
Oleh Rybkin, Chuning Zhu, Amusha Nagabandi, Kostas Danilldiss, Igor Mordatch, and Sergey Levine. Model-Based Reinforcement Learning via Latent-Space Collocation. International 2021.
Conference on Machine Learning, pp.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi- Topological Memory for Navigation. arXiv: 10I::1803.00653,, 2018.
Yannick Schroecker and Charles Isbell. Universal Value Density Estimation for Imitation Learning and Coal-Conditioned Reinforcement Learning. arXiv:2002.04773, 2020.
Dhruv Shah and Sergey Levine. ViKiNG: Vision- Based Kilometer-Seal Navigation With Geographic Hints. Robotics: Science and Systems XVIII, 2022.
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay,
Dieter Fox, Jesse Thomason, and Animesh Garg. ProgPrompt: Generating Situated Robot Task Plans Using Large Language Models. International Conference on Robotàes and Automation, 2023.
Kihyuk Sohn. Improved Deep Metric Learning With Multi-Class N-Pair Loss Objective. Neural Information Processing Systems, volume 29, 2016.
Austin Stone, Oscar Ramirez, Kurt Konolige, and Rico Jonschkowski. The Distracting Control Suite-a Challenging Benchmark for Reinforcement Learning From Pixels. urXiv:2001.02722,
2021.
Richard Sutton. Dyna, an Integrated Architecture for Learning, Planning, and Reacting. ACM Sigart Bulletin, 2(4):160-1633 1991.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value Iteration Networks. Neural Information Processing Systems, 29, 2016.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290(5500):2319 2323, 2000.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action Robust Reinforcement Learning and Applications in Continuous Control. International Conference on Machine Learning, pp. 6215 6224, 2019.
Tongzhou Wang and Phillip Isola. Improved Representation of Asymmetrical Distances With Interval Quasimetric Embeddings. NewrIPS 2022 Newreeps Workshop Proceedings Track, 2022a.
Tongzhou Wang and Phillip Isola. On the Learning and Learnability of Quasimetrics. International Conference on Learning Representations, 2022b.
Tongzhou Wang, Antonio Torralba, Phillip Isola, and Amy Zhang. Optimal Goal- Reaching Reinforcement Learning via Quasimetric Learning. International Conference on Machine Learning, pp. 36411-36430, 2023.
Christopher JCH Watkins and Peter Dayan. Q-Learning. Machine Learning, 8:279-292, 1992.
Alfred North Whitehead and Bertrand Russell. Principia Mathematica, volume 2. Cambridge University Press, 1927.
Grady Williams, Nolan Wagener, Brian Goldfain, Paul Drews, James M Rehg, Byron Boots, and Evangelos A Theodorou. Information Theoretic Mpc for Model-Based Reinforcement Learning. IEEE International Conference on Robotics and Automation, pp. 1714-1721, 2017.
14

---

Published as a conference paper at ICLR 2025
Rui Yang, Yiming Lu, Wenzhe Li, Hao Sun, Meng Fang. Yali Du, Xiu Li, Lei Han, and Chongjie Zhang. Rethinking Goal-Conditionss Supervised Learning and Its Connection to Offline RL. International Conference Learning Representations, 2022.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning Invariant Representations for Reinforcement Learning Without Reconstruction. Interna- lional Conference on Learning Represenlations, 2021a.
Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio. A Study Overfitting in Deep Reinforcement Learning. arXiv:1804.06895 2018.
Tianjun Zhang, Benjamin Eysenbach, Ruslan Salakhutdinov, Sergey Levine, and Joseph E Gonzalez. C-Planning: An Automatic Curriculum for Learning Goal-Roaching Tasks.
arXiv:2110.12080, 2021b.
Brian Ziebart, Andrew Maas, Andrew Bagnell, and Anind Dey. Maximum Entropy Inverse Reinforcement Learning. AAAI Conference on Artificial Intelligence, volume pp. 1433-1438, 2008.
A DEFINITION OF PATH RELAXATION
In this section, we formally define the general path relaxation operator in Definition This definition extends Definition to allow for actions and environmental stochasticity.
Definition (Path relaxation operator with actions). Let PATHA a, G) be the poth releration operator over guasimetric d(s, a, G). For any triplet of state and state distrinutions (s, G, E ((S) x ASS),
PATHA a, G) - mind(ss d(s, a, W) d(W,G).
(13)
W
In the controlled, fixed goal setting, define PATH (s, a,) & min d(s, a, w) d(w,g).
(14)
The nolation A(X) used here and throughout the appendix denotes the space of probability distributions over set. X.
B FORMALIZING PLANNING INVARIANCE AND HORIZON GENERALIZATION
In this section, we prove results discussed in Section 5.2 and versions of results in Section 5 for the general stochastic, distributional setting.
B.1 PLANNING INVARIANCE EXISTS
Theorem 1 (Quasimetric policies are invariant under PLANa). Given deterministic MDP with states S, actions A, and gond-conditioned Kronecker delta reward function ry(s)= = d(s.g): define quasimetric policy aa s. g) and quosimetric planner class plan,- Then, for every quasimetric planner PLANa E plan,, there always erists policy na(a 8,9) that is planning invoriant:
TT(a 8,g) (a(a s, w for w = = PLANN(((ss)))
(11)
Proof. Let 8. S and the action-free distance function be d(s,g) min, d(s,, a, g): this statement. true for the contrastive successor distances (Eq. 5). Define the (deterministic) planned waypoint as
WPLAN +- (PLANA(s.g)) E arg min d(s, w) + d(w.g).
(15)
wes
We can then construct the following policy:
Ta(a 8,g) arg min d(s,, a.g)
(16)
aEA
and later restrict the selection of equivalently optimal actions to obtain planning invariance, where WPLAs E arg min d(s, w) + d(wc, g). Applying this policy to (s, WPlax), we have that Tz(a 8, WPlan) E arg min d(s,, ss a, Wplan)
aEA
arg min d(s,, a, WPLAN) + d(WPLAN:9) aEA
15

---

Published as a conference paper at ICLR 2025
d(s, UPLAN) + d(wpLLN 9)
S arg min d(s, a, a, aEA
(17)
Thus, for a given deterministic planning algorithm defined as in Eq. (15), there exists some deterministic policy Tz(a 8,9) aa(a 8, WPLAN) arg min d(, a, UPLAN) arg mi a.)) that is planning invariant.
B.2 QUASIMETRIC OVER DISTRIBUTIONS
Definition 6 (Quasimetric over distributions). Given quasimetric das defined over start-goal space 8 x S, we define the quasimetric over distributions
7El((P.)) ( daw ())(p.)))(pp))))))))))) dpdq.
daND (P,Q) = inf
(18)
which is the asymmetric Wasserstein Distance with quosimetric cost function dQm (p. q).
We can interpret this object as the minimun cost to convert distribution P to Q, where the cost. function is some quasimetric between individual states.
We show Definition 6 is valid quasimetric. Because dawn is an asymmetric Wasserstein distance and cost. function das (p. g) quasimetric, this proof an extension of well-known result (Clement and Desch, 2008) that drops the metric symmetry condition. We include the proof here for completeness.
Proof. We check the conditions a quasimetric for dano (P, Q) with quasimetric cost function (p. q).
Non-negativity: By definition of 7(p q) and dq q), we have dawn (P, Q) 2 0 for all P.Q. We show that dosp (P. Q) 0 if and only if P Q, beginning with the forward direction:
inf [ dan (p. q) dp dq
dona P. (P.P)
yEll(P.P) Jsxs
<
dau(p, q) dpdg
(set 7 as diagonal matrix QD)
8xS
(pu(p))))(p)
(where u(p) = <D(P.))
(dQM (p,p) 0)
For the other direction, we have that daMp (P,Q) implies 7(, g) 0 for all p + q. However, because ((p,g) q) is probability distribution, this must mcan P = Q.
Asymmetry: We have that dasp(P, (P,() Q) is not necessarily symmetric because the quasimetric (p q) is not necessarily symmetric.
Triangle incquality: Let P,Q,R, R be three probability measurcs. Let M1 and 72.3 be minimizers of damoo (P, Q) and daun Rt) respectively. We can construct some 7,2,3(p, r) such that.
21,3(p, dr vi,a
7,,2, r) = 1523
71,2,((p q, 7. V1,3
where 71,3 is not necessarily the optimal joint distribution to minimize daup (P, R). Then, we have:
doam (P,R) < / dan dow( dp dr
SxS
= - doulp, doulp, 2222 q. r) dp dg dr
16

---

Published as a conference paper at ICLR 2025
sxsxs ISuSs (dam(..)) + dau(g, 7.23(,. do dr
(dam satisfies -inne
| dan(p: 9) (0..) dp dq dr [ JSxSvo dan rm1 q. dp dq dr
SxSxS doup (P. Q) + dQmp
as desired. Therefore, doap is quasimetric and we are done.
B.3 QUASIMETRICS, PATH RELAXATION, POLICIES, AND PLANNING INVARIANCE IN STOCHASTIC SETTINGS
We extend the definitions of quasimetrics, path relaxation, policies, and planning invariance to the setting of general stochastic MDPs.
Definition 7 (Quasimetric over actions in general stochastic setting). Denote by Sa = p(s' 5, a) the distribution over next-step states after taking action a from starting state Given the quasimetric dQND defoned as in Definition 6, we define the stochaslic-setting guasimetric over actions as
dQMb(s,a, G) - ds (saa)) + dQMD(S(s.a)) G)
Definition 8 (Quasimetric policy in general stochastic setting). Given goal-comditionel MDP M with states S, actions A, and goal-conditioned Kronecker delta reward function rg(s) d(s,9) and quasimetric over distributions dQMD (Definition 6), we extend the quasimetric policy to stochastic sellings:
Tala s, G) arg aig (qMD(s,a.G).
(19)
We can also generalize the planning class to take in states, actions, and state distributions as inputs:
plan A (PLAN: S A A(S) + A(S)).
(20)
This planner chooses a waypoint distribution conditioned on given start state, action taken from this state, and desired future goal distribution.
Definition 9 (Quasimetric planner class in general stochastic setting). Given goal-conditionee MDP M and quasimetric over distributions dQMD (Definition 6), we extend the quasimetric planning class to stochastic settings:
plan, (PLLN E plan ddgDDss, a, W) + doMD (W, G) dommps,,, G)
for all (s. a, G) E S x A A(S) where PLAN G) = W}.
The existence planning invariance in stochastic settings follows from these quasimetric definitions.
Lemma 4 (Quasimetric policies are planning invariant in general stochastic settings). Given an MDP with states S, actions A, and goal-conditioned Kronecker delta reward function (s()) d(e.g); consider quasimetric policy va(a 8, G) and planner class plana- Then, for every planning operalor
PLANA(s, a, G) WPLAN E arg min(ddMD(sss,, W) + (W, WEA(S)
there erists a quasimetric policy Ta(a | G) such that <a(a 8, G) aa(a 8, WPLAn),
i.e. the policy is invariant to the planning operator.
Proof. For any start-goal distribution (s, G) S A(S) pair,
min dondd a, G) = min ds, ( S(s,,)) + dQMD (a.)) G) (by definition (Definition 6))
min min dQMD S S(.o)) + dQMD (S (S) W) + dQM G) (A-ineq)
W
min min dOMD(s, W) + W
(21)
17

---

Published as a conference paper at ICLR 2025
start at 50
after reaching $j
plan
plan
plan
space R
Φ x
55 st)
a1
action space
policy
f:
=: S x A
Figure 9: Invariance to planning leads to horizon generalization. (Left) Invariance to planning maps (so, 52, 843) together in latent space, which results in a shared optimal action. (Right) After successfully reaching the closest waypoint in 1 step, the next optimal action also shared, meaning any trajectory of length 2 is optimal. We can repeat this argument for trajectories of length 4, 4,8.... until the entire reachable state space is covered.
From Definition 8, let quasimetric policy be aa(a 8, G) E arg min dQMD a, G).
aEA
Now, applying this policy to stale-waypoint distribution pair (s, WPLAN) E A(S),
xt (aass, WPLAN) E arg min dQ a, WPLAN)
аеd
arg min dQMD (s, WPLAN) + dQMD(WPLAN. G)
aaA
S arg min ds aEA
(22)
as desired. Thus, for any quasimetric planner PLANA(S, a, G), there exists some quasimetric policy
Ta(a| 8, G) =Ta(al 8, WPIAK) E arg min dQMD a, WPLAN) aeA
C arg min d(s, a, G), aEA
(23)
as desirod.
B.4 HORIZON GENERALIZATION EXISTS
In this section, we include a proof of Theorem 2 for the general stochastic setting. This result is visualized in Fig. 9.
Theorem 2 (Horizon generalization exists). Consider MDP with states S, actions A, and goal- con-iconde Kromecker delta reward (s) ((s.))- For any quasimetric d(s, g) over the start-goal space S S and c > 0, the quasimetric policy Ta(a s,g) that is optimal over B. ((8,g) E S x S d(>,g) c} is oplimal over the entire starl-gool space S x S.
Proof. We prove the more general result for policies Tz(a s, G') defined over start-gos distribution pairs (s, G). See earlier sections in Appendix B.3 for quasimetric, policy, and planning definitions over distributions.
Lemma 5. For a goal-conditioned MDP with states S, actions A, and gonl-conditioned Kronecker delta reward function (s(s) 6( Let finite thresholds c and quasimetrics dqMd(s, G) over the start-goal distribution space S x A(S) be given. Then, quasimetric policy Tala s, G) that is optimal over B, = {(s, G) x (SS) d(s, c} is optimal over the entire starl-goal distribution space S (SS).
18

---

Published as a conference paper at ICLR 2025
Note that recover the fixed, deterministic action and goal setting ("fixed" setting) by letting goal-distribution G be a Dirac delta function at a single goal g.
We prove Lemma 5 using induction. Assume optimality over B, = {(s, G) S x A(S) d(s, G) ) for arbitrary E 2 Without loss of generality, consider arbitrary state E S and all goal distributions (s) = (G E A(S) d(s, G) < )2
We consider the space of distributions (G) that c2n distance away from goal distribution G E (s):
(G) = {S' E A(S) d(G, < G GEB((s)) [S' E ASS) d(s,S") < 2
(s)+((s)
(24)
where we correspondingly define the ball of start-goal distribution pairs drawn from (G)
By ((, E (S)) 5' (, GE Bn
((s, E S x ((8) S Bs+1
B,+1-
(25)
Invoking the definition of the quasimetric policy Ta(a 8, S')" for some waypoint distri- bution WPLAN E arg miggwee.... (dQMD W) + dQMD(W, G)) and goal distribution G E (8)1
aala 8, G) E arg min dQMD (s, a, WPLAN).
aaA
To show that there always cxists some planned waypoint distribution WPLAN within the region of assumed optimality B, from the inductive assumption, consider the case WPLAN & (s) and show that there exists some WPLAN, E B, such that
dQMD(s,a a, WPLAN, 1S) + dQMD uu G) dQMD G). We drop the QMD subscript on quasimetric d for readability. By the triangle inequality, d(s, a, G)
min (d(s, a, W) d(W,G))
WEBx41(s)
d(s, a, WPIAN) + d(W G)
min d(s, a, WoUr) + d(Wour: G)
Worr (o.161111))88666)
min Eo WxEB,
(d(s, a, Win) + d(Win, Warr)) + d(W orr, G) min
min (e. (o) d(s,a, Win) + (d(W Wour) + d (ours G))
min
min d(s, a WTx) + d(Win. G)
(A-ineq)
(x)
= =d(s a, WPLAN, 1N) + d(WPLSS, IN; G):
(26)
for all s E S. Thus, there always exists an optimal state waypoit distribution pair within the assumed optimality region B,; we can thus restrict (s, WPLAN) B,. Therefore, with the previously defined quasimetric policy Tz(a 8, G), aa(a (s, WPLAK) E B.) arg min d(s8, a, WPIAN)
(inductive assumption)
aeAA
C arg min d(s, a. G),, (Lemma 4: planning invariance)
aEA
so, the policy Tz(a 8, G) is optimal over Bu+1 following the inductive assumption. Since we assume the base case holds everywhere, Theorem 2 follows.
B.5 HORIZON CENERALIZATION IS NONTRIVIAL
We observe that planning invariance and horizon generalization can be arbitrarily violated for general policies and MDPs.
19

---

Published as a conference paper at ICLR 2025
Remark 3 (Horizon generalization is nontrivial). Let finite >> O and goal-conditioned MDP with states S, actions A, and goal-conditee conditionndd Kronecker delta reward function rg(s)= = ò be given where there are no states outside of S. For policy that is not planning invariant, optimality over B. = ((..g) E S x S d(s,g) < c) is not a sufficient condition for optimality over the entire start-goal space 8 S.
Proof. We restrict our proof to the fixed, controlled setting and let quasimetric d(ss,) g) be the successor distance (sD(8,g) g) (Myers et al., 2024a) this assumption lets us directly equate the optimal horizon H to the distance dsD(s, g), but note that similar arguments can be applied by treating d(s, g) as a generalized notion of horizon.
Consider the goal-conditioned policy x x*. (al 8,9) that is optimal for (s,g) pairs over some horizon H. Assume there is at least one goal g' that is optimally H + 1 actions away from s. and that there exists some optimal waypoint s' on the way to g' reachable via actions A' C A (where A A', the set of suboptimal actions, is nonempty).
We can then construct policy π HH+1 where (1) x (a s.g') returns an action in the suboptimal set A \ A' and (2) H+1 restricted to start-goal pairs horizon H apart is equivalent to - Therefore, an arbitrary, nou-planning invariant goal-reaching policy does not necessarily exhibit horizon generalization.
C WHICH PRACTICAL METHODS MIGHT EXHIBIT HORIZON GENERALIZATION?
In this section, we discuss how temporal difference methods, quasimetric architectures, RL. algorithms, and data augmentations that employ explicit planning can all achieve planning invariance under some assumptions. Appendix C.1 discusses several new directions for designing RL algorithms that are invariant to planning. Appendix C.2 recalls figures from prior works in search of evidence for horizon generalization.
Dynamic programming and temporal difference (TD) learning. We expect that dynamic programming and TD methods will achieve planning invariance in tabular settings. The int is that TD met hods "stitch" (Ziebart et al., 2008) logether trajectories which is natural route to obtain policies with horizon generalization. Indeed, our definition of planning invariance is very closely tied with the optimal substructure property (Cormen et al., 2022, pp. 382-387) of dynamic programming problems, and likely could be redefined entirely in terms of optimal substructure. Viewing horizon generalization and planning invariance through the lens of machine learning allows us to consider a broader set of tools for achicving invariance and generalization (c.g., special neural network layers, data augmentation).
Quasimetric Architectures (implicit planning). Prior methods that employ special neural networks may have some degree of horizon generalization. For example, some prior methods (Wang et al., 2023; Pitis al., 2020; Myers et al., 2024a) use quasimetric networks to represent a distance function. As the correct distance function satisfies the triangle inequality, it is useful to employ special quasimetric neural network architectures (Liu et al., 2023; Wang and Isola, 2022b;a) that are guaranteed to satisfy the same property before sccing any training data. These architectures are invariant to path relaxation by construction, though prior work rarely examines their generalization or invariance properties. Other prior methods (Tamar et al., 2016; Lee et al., 2018) have proposed architectures that perform value iteration internally and (hence) may be invariant to the Bellman operator. Because Bellman optimality implies invariance to optimal planning (c.f. optimal substructure), we expect that these value iteration networks to exhibit some horizon generalization as well.
Explicit planning modh While our proof of planning used a specific notion of planning, prior work has proposed RL methods that employ many different styles of planning: graph search methods (Savinov et al., 2018; Zhang et al., 2021b; Beker et al., 2022; Chane-Sane et al., 2021), model-based methods (Sutton, 1991; Chua et al., 2018; Nagabandi et al., 2018; Lowrey et al., 2018; Williams et al., 2017), collocation methods (Rybkin et al., 2021), and hicrarchical methods (Kulkarni et al., 2016; Parascandolo et al., 2020; Nasiriany et al,, 2019; Pertsch et al., 2020). Insofar as these methods approximate the method used in our proof, it is reasonable to expect that they may achieve some degree of planning invariance and
20

---

Published as a conference paper at ICLR 2025
horizon generalization (see Fig. 10). Prior methods in this space are typically evaluated on the training distribution, so their horizon generalization capabilities are typically not evaluated. However, the improved generalization properties might have still contributed to the faster learning on the training tasks: after just. learning the easier tasks, these methods would have already solved the complex tasks, leading to higher average success rates.
Data augmentation. Finally, prior work (Ghugare al., 2024; Chane-Sane et al., 2021) has argued that data augmentation provides another avenue for achicving the benefits typically associated with planning or dynamic programming.
C.1 NEW METHODS FOR PLANNING INVARIANCE
While the aim of this paper is not propose a new method, we will discuss several new directions that may be examined for achieving planning invariance.
Representation learning. As shown in Fig. 2, planning invariance implies that some internal representation inside a policy must map start-goal inputs and wtart-waypoint imputs to similar representations. What representation learning objective would result in representations that, when used for a policy, guarantee horizon generalization? The fact that plans representations sometimes correspond to geodesics (Tenenbaum et al., 2000; Eysenbach et al., 2024) hints that this may be possible.
Flattening hicrarchical methods. While hicrarchical methods often achieve higher suc- coss rates practice, remains unclear why flat mothods cannot achiove similar performance given the same data. While prior work has suggested that hierarchies may aid in explo- ration (Nachum el al., 2019), it may be the case that they (somehow) exploit the metric structure of the problem. Once this inductive bias is identified, it may be possible to imbue into a "flat" policy so that can achieve similar performance (without the complexity of hierarchical methods).
Policies that learn to plan. While explicit planning methods may be invariant to planning, recent work has suggested that certain policies can learn to plan when trained on sufficient data (Chano-Sanc et al., 2021; Lee al., 2024). Insofar as neural networks are universal function approximators, they may learn to approximate a planning operator internally. The best way of learning such networks that implicitly learn to perform planning remains an open quest.on.
C.2 EVIDENCE OF HORIZON GENERALIZATION AND PLANNING INVARIANCE FROM PRIOR WORK
Not only do the experiments in Section provide evidence for horizon generalization and planning invariance, but we also can find evidence of these properties in the experiments run by prior work. This section reviews three such examples, with the corresponding figures from prior work in Fig. 10:
Zhang et al. (2021b) propose a method for goal-conditinned RL in the online setting that performs planning during exploration. While not the main focus of the paper, ablation experiment in that paper hints that their method may have some degree of planning invariance: after training, the policy produced by their method is evaluated both with and without planning, and achieves similar success rates. This experiment hints at another avenue for achieving planning invariance: rather than changing the architecture or learning rule, simply changing how data are collected may be sufficient.
2. Ghugare et al. (2024) propose a method for goal-conditioned RL in the offline setting that performs temporal data augmentation. Their key result, reproduced above, is that the resulting method generalizes better to unseen start-goal pairs, compared with a baseline. While this notion of generalization generalization (unseen start-goal pairs may still be close to one another), the high success rates of the proposed method suggest that method does not just generalize to nearby start-goal pairs, but also exhibits horizon generalization by succeeding in reaching unseen distant start-goal pairs.
not exactly the same as horizon
"The construction in our proof is a degenerate case of this, where the internal representations
equal the output actions.
21

---

Published as a conference paper at ICLR 2025
5 Waypoints
Wiggoiins
Waysonss
C-lamning -688
0.250
0.25
R.bve M0n Dilance
0.200
0.225
S.boee Nln 0ideace
0.200
0.150
0.1
0.325
0.150
0.100
0.075
0.05
0.130
0.050
0.2
Envirunment
Los
Environment
Ic6
Environmentt
165
(a) Zhang et al. (2021b)
RvS
RvS + state a sugmentation (ours)
RvS + only geal sugmentation (eurs)
sugmentation (ours)
only augmentation tion (ours)
po soint-aaze
ant-maze
paint-maze
ant-maze
1.02
2.500
Success rabe
0.25
0.00
medium
medium
large
medium
large
medium
(b) Chugare et al. (2024)
Figure 10: Evidence of Horizon Generalization and Planning Invariance from Prior work. (a) Prior work has observed that if policies are trained in online setting and perform planning during exploration, then those policies see little benefit from doing planning during evaluation. This observation suggests that these policies may have learned to be planning invariant. While results are not stratified into training and testing tasks, we speculate that the faster learning of that method (relative to baselines, not shown) may be explained by the policy generalizing from easy tasks (which are learned more quickly) to more difficult tasks. (b) Prior work studies how data augmentation can facilitate combinatorial generalization. While the notion of combinatorial generalization studied there is slightly from horizon generalization, a method that performs combinatorial generalization would also achieve effective horizon generalization.
D COLL-CONSISTENT MODELS
In machine learning, usually strive for consistent models: ones that faithfully predict the training data. Sometimes (often), however, a model that is consistent with the training data may be inconsistent with other yet-to-be-scen training examples. In the absence of infinite data, one way of performing model selection is to see whether a model's predictions are self- consistent. with one another. This is perhaps most easily seen in the case of metric learning, as studied in this paper. If we are trying to learn metric d(x, y), then the properties of metrics tell us something about the predictions that our model should make, both on seen and unscen inputs. For example, even on unscen inputs, our model's predictions should obey the triangle incquality. Given many candidate models that are all consistent with the training data, we may be able to rule out some of those models if their predictions unseen examples are not "logically" consistent (e.g., if they violate the triangle inequality). One way of interpreling quasimelric neural networks is that they are archilecturally construined to be self self-consistent. We will discuss few implications this observation.
Do self-consistent models know what they know? What if we assume that quasimetric networks can generalize? That is, after learning that (say) and 82 are 5 steps apart, will predict that similar states sf and s/ are also 5 steps apart. Because the model is architecturally constrained to be quasimetric, this prediction (or "hallucination") could also result in changing the predictions for other s-g pairs. That is, this new "hallucinated" edge si - s/2 might result in path relaxation for yet other edges.
22

---

Published as a conference paper at ICLR 2025
What other sorts of models are self-consistent? There has been much discussion of self-consistency in the language-modest modeling literature (Huang et al., 2022; Irving et al., 2018). Many of these methods are predicated on the same underlying quasimetric networks: checking whether the model makes logically consistent predictions on unseen inputs. Logical consistency might be used to determine that prediction is unlikely, and so the model can be updated or revised to make different prediction instead.
self-consistency in
There is an important difference between this example and the quasimetrics. While the axiom used for checking self-consistency in quasimetrics was the triangle inequality, in this language modeling example colsissssstt is checked using the predictions from the language model itself. In the example of quasimetrics, our ability to precisely write down mathematical notion of consistency enabled us to translate that axiom into an architecture that is self-consistent with this property. This raises an intriguing question: Can quantify the rules of logic in such a way that they can be translated into a logically self-comsistent language model? What makes this claim seem alluringly tangible that there is abundant literature from mathematics and philosophy on quantifying logical rules (Whitehead and Russell, 1927).
MDP reductions. Finally, is it possible to map MDP to another MDP (e.g., with different observations, with different actions) so that any RL algorithm applied to this transformed MDP automatically achieves the planning invariance property?
E EXPERIMENT DETAILS
Table 1: Summary of methods and modifications tested
Method Description
Losses
Critics
CRL
Contrastive RL (Eysenbach et al., 2022)
Limds Lowds Laym) (Lecc]
{de, dMLP) [QMPP) {dMRN)
SAC
Soft Actor-Critic (Haarnoja et al., 2018)
CMD-1
Contrastive metric distillation (Myers et al., 2024a)
{Lowd]
(a) Losses
(b) Architectures
Liwa
InfoNCE loss: predict goal
dez
L2-distance parameterized architec- lure, uses [[Ø(s) (gg)) as dis- lance/critic (Eysenbach el. al., 2024)
from current stale-action (8,a) pair (Sohn, 2016)
Dowd Backward InfoNCE loss: predict current state and action (s, a) from future state g (Bortkiewicz et al., 2024)
dMLr
Uses multi-layer perceptron (MLP) to parameterize the distance critic (Rosenblatt, 1961; Burr, 1986)
dMRN
Metric residual network, uses a quasimetric architecture parame- terize the distance /critic (Liu et al., 2023)
Laym
Symmetric contrastive loss: com- bine the forward and backward con- trastive losses (Radford et al., 2021)
Lsac Temporal difference loss (Haarnoja et al., 2018)
QMPP
MLP aaLP-parameterized
Q-function
(Haarnoja et al., 2018)
The following subsections discuss the environment details for the figures in the main text.
E.1 DIDACTIC MAZE: FIGURE 2
This task is a maze with walls shown as in Fig. 2. The dynamics are deterministic. There are actions, corresponding the cardinal directions and a no-op action.
For this plot, generated data from random policy, using 1000 trajectories of length 200. We estimated distances using Monte Carlo regression. The left two subplots were generated by selecting actions uses these Monte Carlo distances. We computed the true distances by rumning Dijkstra's algorithm. The right two subplots show actions selected using Dijkstra's algorithm.
23

---

Published as a conference paper at ICLR 2025
E.2 TABULAR MAZE NAVIGATION: FIGURE 4 (ToP)
This plot used the same environment as described in Appendix F.1. For this plot, we generated 3000 trajectories of length 50 using random policy. Only 14% of start-goal pains have any trajectory between them, meaning that the vast majority of start-goal pairs have never been seen together during training. Thus, this is a good setting for studying generalization.
We first estimated distances using Monte Carlo regression. We select actions using Boltzmann policy with temperature 0.1 (i.e., x aa 8,9) x =0 Evaluation done over 1000 randomly-sample path distance. The data are aggregated so that start-goal pairs with distance between (say) 20 and 30 get plotted at 30. The "metric regression + quasimetric" distances obtained by performing path relaxation on these Monte Carlo distances until convergence. The corresponding policy is again Boltzmann policy with temperature 0.1.
start-goal pairs. The X axis is binned based the shortest
For the Top Right subplot, we perform planning using Dijkstra's algorithm. We first identify set of candidate midpoint states where d(s, w) and d(w, g) are both within one unit of half the shortest path distance. We then randomly sample a midpoint state. This planning is done anew at every timestep.
E.3 LEARNED MAZE NAVICATION: FIGURE (BOTTOM)
This plot used the same environment as described in Appendix E.1. The CRL method refers to (Eysenbach et al., 2022) and CMD refers to (Myers et al., 2024a). We used representation ion dimension of 16, a batch size of 256, neural networks with hidden layers of width 32 and Swish activations, 7 0.9, and Adam optimizer with learning rate 3 1000 The loss functions and architectures are based on those from (Bortkiewicz et al., 2024).
For the Bottom Right subplot, we performed planning in the same way as for the Top Right subplot.
E.4 JAXGCRL BENCHMARK ENVIRONMENTS
Ant (Figure 5): For this task we used a version of the Ant environment from Bortkiewicz et al. (2024) modified to have variable start positions and distances to the goal. All other hyperparameters are kept as the defaults from that paper. Training is done for 100M steps
AntMaze and Humanoid (Figure 6): Both environments are modified versions of the AntMaze and Humanoid environments from Bortkiewicz et al. (2024). The CMD-1 and CRL methods (with the backward infoNCE loss and & distance paramelerization) were evaluated at the listed distances and twice as far, and the ratio of the two success rates was used to compute
E.5 LONG MAZE: FIGURE 8
For this experiment we used an S-shaped maze, shown in Fig. 11.3 3 The dynamics are the same those of Fig. 2.
Figure 11: Long S-shaped maze.
We collected 3000 trajectories of length 10 and applied CRL with a representation dimension of 16, a batch size of 256, neural networks with 2 hidden layers of width 32 and Swish activations, the backward NCE loss (Bortkiewicz et al., 2024), 7 0.9, using the Adam optimizer with learning rate 3 1 We measured the Bellman error as follows, where To, I1, Er are the current, immediate next, and future states:
1 pdist metric_fn. (params, x0[:, None], xT [None])
2 pdist_ness metric fn. apply (params, x1[:, Nonel, xT [None])
3. td_target (1 gamma) (x1 [Nonee, :, o])
4
gamma jax softmax (ammxxpddit_next axis=1)
5 bellman optax. kl_ di_dieergeenee
WW used this maze in preliminary versions of other experiments, but opted for the larger maze in the other paper experiments because the results easier to visualize.
24

---

Published as a conference paper at ICLR 2025
6 td_ targer, jax mn. wof. tamax axis=1) 7 ). ))
For the success rales in the Left subplot, we stratify goals into "easy" (less than 100 steps away, under an optimal policy) and "distant" (more than 100 steps away).
We repeated this experiment 10 times for generate the standard errors shown in both the Left and Right subplots.
25


Reviews:
[{"review_id": "TWIcRxf9pp", "reviewer": "Reviewer_7Gwa", "summary": "This paper studies the generalization of RL from the perspective of horizon invariance. An RL agent that has been trained to reach nearby goals should succeed on distant goals and hence generalize to different horizon lengths. The paper intends to study how the techniques on invariance and generalization from other machine learning domains can be adapted to make goal-directed policies generalize to different horizons.", "questions": "1. Generalization in RL and in goal-conditioned setting can come in different forms. While generalizing over different horizons is important, why do you think invariance will help here? As the horizon changes and the trajectories get longer, it is possible that any of the waypoints relevant over shorter horizons are not that relevant anymore if better paths are discovered for example.\n2. How does the method relate to when we are no longer looking at smaller horizons as being sub-goals of the longer horizons? Or even when we are not considering the goal as a condition. Do you think this work can include those cases?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. The paper aims to study an important question of generalization and planning under different horizon lengths for a goal-conditioned RL agent.\n2. Connections between existing methods and the new proposed methods are provided.", "weaknesses": "1. The writing of the paper needs some work to strengthen the motivation and claims. The related works section can also benefit from further elaboration and coverage of the related literature.\n2. The paper mentions that horizon generalization means that a policy that can achieve a goal n steps away should also be able to reach any new goal for which that original goal is a waypoint. This is a bit far-fetched of a statement as in a longer horizon, a lot of different things could happen over this longer timeframe and not all en-route waypoints would be relevant. Moreover, things could demand a completely different set of actions or approach after these n steps. Defining horizon generalization in this scenario needs a more thorough definition.\n3. The example of dominoes considered in the paper is a very simple bandit setting, while the paper focuses on more general RL settings with different horizon lengths. Providing relevant working examples will be beneficial to the understanding.\n4. Experiments are over simpler environments / task settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "woFDnLon8s", "reviewer": "Reviewer_h6Gn", "summary": "This paper explores the problem of horizon generalization in goal-conditioned reinforcement learning. It presents clear definitions of planning invariance and demonstrates how this concept can facilitate horizon generalization.", "questions": "I was unable to assess the correctness of the theorems due to some undefined symbols mentioned earlier. Please respond to my previous queries in weakness. I will reassess them in case I missed anything.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 3, "strengths": "The problem studied in the paper is novel and very interesting to me. The motivation of the paper is clear and the writing of the paper is generally clear and easy to fllow.\n\nThe paper presents clear definition of planning invariance and horizon generalization, which make sense to me.", "weaknesses": "The paper contains some symbols that are not well defined, some of which even affect the readability of the paper.\n\n- I got lost from Line 245 with $d(s,a,g)$. I don't understand the meaning of this symbol and why it contains an action. The paper didn't clearly define it. This is critical as I failed to fully understand the proof of Lemma 1 and Lemma 2, which are the major results of the paper. I hope I didn't miss anything.\n\nSome undefined symbols that do not affect reading:\n\n- Eq. (2): $p_\\gamma^\\pi$, $Geom$ is never defined\n- Line 117: $\\delta$, $r_g$\n\nThe paper also uses different terminology from the common terminology, making it seem less professional.\n\nUsually, the distance (metric) function should satisfy the three rules: Non-negativity, Triangle Inequality, and Symmetry; while a quasimetric relaxes one or more of the metric's defining properties.\n\nMinor Comments:\n\n- It seems Lemma 1 and 2 are some important results of the paper. Then please use \"Theorem\" rather than \"Lemma\".\n- \"Markove process\" should be \"Markov Decision Process\". You didn't include the definition of the reward function.\n\n\n\nAnother weakness is the paper's lack of clarity on how its discoveries could inspire future algorithm development. I hope future revisions of the paper will devote more effort to exploring this aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cXOdbRjp41", "reviewer": "Reviewer_ctUj", "summary": "This paper studies horizon generalization in goal-conditioned RL. The main contributions of the paper are a definition of horizon generalization and planning invariance, and proofs of existence for both, as well as some small-scale experimental studies. I admit I am unclear what the takeaways for the reader are - it seems like the main contributions, i.e. the definition of horizon and planning invariance, are quite obvious, as well as the existence of these kinds of invariances. I do agree that the goal of inducing invariances that facilitate generalization in RL is important. It may be that I misunderstood parts of the paper, hence I am putting my confidence at 3 and recommendation at borderline.", "questions": "- It seems obvious that if the series of waypoints produced by a planner is optimal, then we should have planning invariance according to the definition given here (i.e., the optimal action to reach the next waypoint is the same at the optimal action to reach the final goal), so my guess is that this is not the main message of the paper. The other way around, where the agent trains on easy goals and generalizes to hard ones, seems much more useful, so that this is what the paper is getting at. The paper refers to this as the “forward perspective”. However, there doesn't seem to be any suggestions on how to induce this kind of invariance. Also, this seems related to compositional generalization in language-conditioned RL, where the agent is trained on language commands and asked to generalize to novel combinations. How does this relate to planning invariance/generalization?\n\n- The paper claims that most prior work on generalization in RL relates to invariance to perceptual changes or simulation parameters. But there is a rich literature on state abstractions which induce invariances to criteria other than perceptual differences, for example: optimal actions (known as policy irrelevance), rewards/Q-values (utile distinctions) [1] bisimulation [2]  belonging to a common latent state (however defined) [3]. It seems like the proposed planning invariance could be seen as a special case of one of these other abstractions (such as policy irrelevance). It would be helpful to include a discussion of other types of state abstraction/generalization in the paper. If the proposed invariance cannot be subsumed in any of the prior ones, it would be helpful to describe in what ways. \n\n- It would help to give more examples of non-trivial cases where planning invariance is or is not met, in order to build intuitions. There is one example in Section 4.1, but it didn’t really help my understanding because in that example, there was a single action that was optimal for all goals (and the problem is in a sense trivial for that reason). Also, the example of knocking over dominoes with levers felt fairly contrived. Would it be possible to add one or more examples that 1) have different actions that are optimal for different goals, 2) one can construct some policies that do have planning invariance and others not, in order to illustrate their differences, and 3) are more closely related to common sequential decision-making problems? I know there is also the example in Figure 6, but there the goal-conditioned policy on the left is not optimal. \n\n[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=ca9a2d326b9de48c095a6cb5912e1990d2c5ab46\n\n[2] https://www.auai.org/uai2014/proceedings/individuals/67.pdf\n\n[3] https://arxiv.org/pdf/1901.09018", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Conceptual investigations are welcome\n- The paper's figures are well drawn", "weaknesses": "- As mentioned above, the takeaways for the reader are not clear - this does not propose a new method, or (to my understanding) clearly shed light on existing methods, highlight a previously unknown weakness,...\n- The relationship of this work to other areas of work is unclear in some cases. \n\nPlease see my detailed questions/comments below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wWJ92BLE58", "reviewer": "Reviewer_6v2T", "summary": "The motivation and insight presented in this paper are interesting and straightforward. This paper presents the abundant theoretical contribution to Planning Invariance and Horizon Generalization. Experimental results of existing methods support the theoretical results.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Good writing and structure.\n2. The authors illustrate their research problem via the good toy example (Figrue 3).\n3. Theoretical results are clear and sound.", "weaknesses": "I have no concern with the main contribution of the theoretical part of this paper. The main concern is related to the application and limitations.\n\n1. One of the main concerns of the reviewer is the limitations of the planning invariance and horizon generalization, as mentioned by the authors (Section 4.5).\n2. I am also concerned about real-world applications (e.g., more complicated tasks). In real-world settings, the planning invariance and horizon generalization seem to be limited in their application to general cases, although they indeed exist as mentioned by the authors. In the high-dimensional settings (Section 6.2), it is hard to derive insightful results.\n3. The authors provide some interesting future directions in Appendix C, but it would be better to present some experimental results or practical implementations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)