Quasipseudometric Value Functions with Dense Rewards
Authors: Khadichabonu Valieva
Bikramjit Banerjee
Venue: Accepted by TMLR ()

Abstract: As a generalization of reinforcement learning (RL) to parametrizable goals, goal conditioned RL (GCRL) has a broad range of applications, particularly in challenging tasks in robotics. Recent work has established that the optimal value function of GCRL $Q^\ast(s, a, g)$ has a quasipseudometric structure, leading to targetted neural architectures that respect such structure. However, the relevant analyses assume a sparse reward setting—a known aggravating factor to sample complexity. We show that the key property underpinning a quasipseudometric, viz., the triangle inequality, is preserved under a dense reward setting as well, specifically identifying the key condition necessary for triangle inequality. Contrary to earlier findings where dense rewards were shown to be detrimental to GCRL, we conjecture that dense reward functions that satisfy this condition can only improve, never worsen, sample complexity. We evaluate this proposal in 12 standard benchmark environments in GCRL featuring challenging continuous control tasks. Our empirical results confirm that training a quasipseudometric value function in our dense reward setting indeed either improves upon, or preserves, the sample complexity of training with sparse rewards. This opens up opportunities to train efficient neural architectures with dense rewards, compounding their benefits
to sample complexity.

Published in Transactions on Machine Learning Research (10/2025)
Quasipseudometric Value Functions with Dense Rewards
Khadichabonu Valieva
Khadichabonu. Valieva eduu
School of Computing Sciences 8 Computer Engineering The University of Southern Mississippi
Bikramjji Banerjee
Sikrumjt.BannerjeeBaa edu
School of Computing Sciences & Computer Engineering The University of Southern Mississippi
Reviewed on OpenReview: htips: // openreview. net/ met/ forum? id- 4Lq016pDUe
Abstract
As generalization of reinforcement learning (RI.) parametrizable goals, goal condi- tioned RL (GCRL) has broad range of applications, particularly in challenging tasks in robotics. Recent work has established that the optimal value function of GCRL Q' (s,a, g)) has quasipseucoometric structure, leading to targetted neural architectures that respect such structure. However, the relevant analyses assume a sparse reward sctting-a known aggravaling factor to sample complexity. We show that the key property underpinning a quasipseudometric, viz., the triangle inequality, is preserved under a dense reward setting as well, specifically identifying the key condition necessary for triangle inequality. Con- trary to earlier findings where certain types of dense rewards were shown to be detrimental to GCRL, we conjecture that dense reward functions that satisfy this condition can only improve, never worsen, sample complexity. We evaluate this proposal in 12 standard bench- mark environments in GCRL featuring challenging continuous control tasks. Our empirical results confirm that training quasipseudometric value function in our dense reward setting indeed either improves upon, or preserves, the sample complexity of training with sparse rewards. This opens up opportunities to train efficient neural architectures with dense rewards, compounding their benefits to sample complexity.
Keywords: Goal conditioned reinforcement learning, reward shaping, quasipseudometricc value functions
1 Introduction
Reinforcement learning (RL) is popular class of techniques for training autonomous agents to behave (near- optimally, often without requiring model of the task or environment. In goal-achieving tasks, traditional RL learns policies that reach single goal at the minimum (maximum) expected cost (value) from any state. Contrastingly in multi-task settings, goal conditioned value function models the cost-to-go to a set of goal states, not just one. This generalization from a single-goal case to goal-conditioned RL (GCRL) yields effective representations- poreeeeraatioss-poeeeedd by deep neural networks for value functions capable of capturing abstract concepts underlying goal achievement in many complex tasks [Wang et al., 2023 Liu et al. 2022 Plappert al. 2018).
Recent work has established that the true optimal value function in GCRL is always quasipseudometric i.., metric without the constraint of being symmetric, but crucially respecting the triangle inequality (Pitis ct al. 2020 Wang & Isola, 2022. Liu et al. 2023). This allows the scarch for value functions to be naturally restricted to the space of quasipseudon queaipssudometrics... Additionally, such functions are designed to be universal value function approzimators (UVFA), i.e. capable of approximating arbitrarily complex value functions. Accordingly, Liu et al. (2023) propose the metric residual network (MRN) architecture for GCRL value functions that explicitly accommodate an asymmetric component while maintaining the UVFA property and the triangle inequality. This and other similar approaches search smaller subset of the space of value

---

Published in Transactions on Machine Learning Research (10/2025)
functions, yet the true optimal value function is guaranteed to reside in it. This has led to significant gains in terms of sample efficiency in recent. GCRL, advancements (Liu et al. 2023 Wang & Isola 2022 Wang et al. 2023).
In this paper, we review some of the theoretical analyses underlying much of the work cited above. In particular, the proof of the key property of triangle inequality in Liu et al. (2023) established for a sparse reward setting that easy to design but hard learn from, ie., sparse rewards lead to poor sample efficiency. By contrast, dense reward settings using various mechanisms, e.g., reward shaping, intrinsic motivation, human feedback etc., generally known to improve sample efficiency. If dense reward- based value functions were to satisfy the triangle inequality, then their reward bias could be combined with the representational bias of quasipsseudomelriiss to deliver a double punch to sample complexity. Furthermore in GCRL, since a goal is given, it may be easy to design a dense reward scheme parametrized by the goal that neither requires onerous, intricate reward engincering, nor is computationally demanding. This could bring the benefit of dense rewards-viz viz., reduced sample complexity-to GCRL with less human effort than in other RL lasks. However, existing negative results (Plappert et al. 2018) specifically in GCRL show that certain classes of dense rewards significantly deteriorate the performance of state-of-the-an the-art RL methods, and might appear to forcelose a discussion on their efficacy in GCRL, Contradictorily, we show that a class of dense rewards, viz., potential shaped rewards, can indeed bring their benefit to bear in GCRL as long as they satisfy a condition under which the triangle inequality is preserved for the optimal value function. Furthermore, we establish a condition under which the triangle inequality is preserved for intermediate value functions that may be encountered during RL iterations. This result adds nuance to recent contradictory finding (Wang et al. 2023) that such value functions do not satisfy the triangle inequality. We show experiments in 12 benchmark GCRL tasks to establish that our prescribed dense rewards indcod improve sample complexity in some lasks, but does not deteriorate sample efficiency in any task, while certain types of dense rewards that violate the key condition deteriorate sample complexity consistent with the findings of Plappert et al. 2018). Our main contributions can be summarized as:
We show that using rewards shaped with potential functions that serve as admissible heuristics, the optimal value function does satisfy the triangle inequality. This extends similar results from Liu et al. (2023) in a sparse reward setting to a commonly used dense reward setting that is more general and beneficial to sample efficiency;
We define and delineate progressive criterion for GCRL policies and show that under such policies the intermediate value functions also satisfy the triangle inequality. This adds nuance to a prior negative result in Wang et al. (2023) which showed that there exist intermediate value functions that violate the triangle inequalily;
Via experiments in 12 standard benchmark GCRL tasks, show that our prescribed dense rewards improve sample complexity as well as the learned policy in several tasks, while not deteriorating performance in any task. This result informs us how to overcome prior negative result in Plap- pert et al. (2018) which showed that GCRL with shaped rewards had significantly worse sample complexity than with sparse rewards.
2 Background
This section covers the preliminarics on goal conditioned RL, the prevalent solution approaches for GCRL, and the recent architecture of metric residual networks that we use in this paper.
2.1
Goal-conditioned RL
Goal conditioned RL is modeled by goal-conditioned Markov decision process, M = (S, 7, Po- Pg). While S, T, Po define the state action spaces, the transition function and the initial state distribution just like standard MDP, 9 gives the space of goal states, and Pg is the distribution from which a goal sampled at the beginning of an episode. Further, the reward function R is additionally parametrized by the goal,
2

---

Published in Transactions on Machine Learning Research (10/2025)
R R. In the sporse reward setting, R. is often defined as
R(s, = {
if M(s,a)= otherwise
(1)
where M 8 A + 9 maps the product space of S and A G, specifying the goal state reached by taking action in state As opposed to the common assumption 9 S, . allows action to decide whether the goal is reached (Liu et al., 2023) when testing whether M a) _ The agent's decision function is its policy, v, which can be either deterministic ( S S ( A) or stochastic ( S x A x 9 + [0, IJ) yielding the probability of selecting actions. We refer to trajectories or episodes as time series of states and actions that learner encounters, 80, ag: $1, ; St, .t.....
2.2 Solution Approach: DDPG+HER
A popular approach to solving GCRL is combination of ooolpo actor-critic, c.g., DDPG (Lillierap et al. 2016) with hindsight experience replay (HER) (Andrychowicz et al. 2017) DDPG in GCRL estimates a goal conditioned critic for policy
8
= _E Σ
r rrggls s, ag a,g
where ft.g R(s,, at a,,9) and the expectation is taken over future steps of rewards generated by the policy (TT), and the T, R functions. The critic is updated by minimizing the mean squared TD error over samples (st, az, St+1,g) drawn from a replay buffer D,
L(Q) = ED [(rr + (((((
- Q(s,, az (.,g))]]_
(2)
By ensuring that Q is differentiable w.r.t. actions a, the actor policy æ updated in the direction of the gradient (sv,, (t:9)]; 9)], where the expectation again evaluated using samples drawn from D. As these samples are drawn from state distributions generated by policies different from म. DDPG is an off- off-policy method.
(st,,
Hindsight experience replay (HER) (Andrychowizz et al. 2017) miligates the sparse reward problem by relabeling failed trajectories. Instead treating all experience traces where the agent failed to achieve a goal as is, HER changes the goal some of them match a step of the trace in teddsighh-ssseniallyy pretending as if the agent's goal all along was to reach the state that it actually did. This transforms some of the failed episodes into successful experiences that informative about goal achievement, and allows the agent to generalize, eventually, to the true goal distribution Pg. A more recent method, goal-conditioned supervised learning (Ghosh et al. 2021), uses the idea of HER but in the context of offline RL. Both DDPG and HER remain popular and are commonly used in online GCRL (Liu el al. 2023
2.3
Metric Residual Network
Liu et al. 2023 propose a novel noural architecture for GCRL critic based on the insight that the optimal negated action-value function, -Q" (s, a, a,g), satisfies the triangle inequality in the sparse reward selling of Eq. [ Consequently, they introduce the metric residual network (MRN) that decomposes -Q into the of a metric and asymmetric residual component that provably approximates any quasipseudomettrcc. Specifically,
(s.0,g)) g) - (daym (hsas hag) + dasgm (Isa, hsgg)
(3)
where hg and hag are latent encodings of concatenated (s, and (s,g), daym and duegm are symmetric and asymmetric distance components given by
daym (x. v) = [x) (2) dasym (I. y) max((12 (x) p2a (2)()))+
(4)
(5)
Il-I1z the Euclidean distance, (x)+ max(æ, 0) is also known as the rectified linear unit (ReLU) function, in and #2 are neural networks that map their inputs to vectors, and uzi is the i-th component, of p2 output
3

---

Published in Transactions on Machine Learning Research (10/2025)
4 5 that indeed deym (z. deym (y, 2)) but possibly dasym y) + dasym (y. The valid decomposition since ((s,a,g) is essentially a distance and any distance can be (in general) split into symmetric and asymmetric components, where either components can be 0 in limit cases. On the one hand, the Max-ReLU formulation of dasym in Eq. is proven to ensure the UVFA property of Eq. [Liu al. 2023). On the other hand, daym improves sample efficiency due to its symmetry. We use HER with MRN critic architecture as the base GCRL method for this paper.
vector. Note from Eqs. main idea is that Eg.
2.4 The Quasipseudometric Property
A space X' with distance measure d defines quasipseudomettric, (d, if (1) Vo X, d(x, 0 and (2) Vx, v, E X, d(x, y) + d(y, z) 2 d(x; z), also known the triangle inequality. A metric is special case of quasipeudornetric that is also symmetric, but symmetry is not necessary in robotics problems, e.g., a robotic arm could rotate in one direction but not in the other leading to d(z, y) * d(y. Additionally, a quasimetric is a special case of a quasipsenndmmttric where it is necessary that x * = d(x, y) > O. This also not necessarily true in robotics problems, for instance, when rotating a robotic arm, different qualernions x A y could represent the same rotation, i.e., d(x,, 5) = 0. Liu et al. (2023) argue that in general GCRL problems, -Q(s, a, may not be purely symmetric (i.e., may have an asymmetric component), or > 0 for different states. As result, the most general form of - Q 0. g) for GCRL is neither metric nor quasimetric, but quasipseuudoneetiic
constructed via Eqs. 3
Liu et al. (2023) establish the critical property (2) of a quasipseudonetric, i.e., the triangle inequality for optimal (s' a) This property is the key focus of this paper.
3 Triangle Inequality of Value Functions
In this section, we establish that both the optimal value function as well as intermediate value functions satisfy the triangle incquality under novel conditions, with the following road-map. In Sec. 3.1 we analyze the quasipseucometric property of optimal value functions that use potential-shaped dense rewards. After establishing the main condition for such value functions to satisfy the triangle inequality property, prove this property formally for two subcases in Secs. a.d 3.1.2 In 3.1.3] we prove that this property is a not a trivial consequence of a well-known property (viz., policy invariance) of potential-shaped rewards. We conclude Sec. 3.1 with discussions on associated topics: value function clipping via an informed constraint (Sec. 3.1.4) and selection of a key parameter of the main condition (Sec. 3.1.5). In Sec. 3.2) we show that another commonly used dense reward that does not use potential functions may violate the triangle inequality. Finally in Sec. 3.3 we establish novel condition under which even intermediate value functions (with dense sparse rewards) satisfy the triangle incquality, and formally prove this property.
3.1 Optimal Value Function
Our primary claim is that -Q" satisfies the triangle inequality not only in the sparse reward setting, but also in the presence of a common type of dense rewards, viz., potential shaped rewards (Ng et al. 1999). This observation lends GCRL to improved sample elficiency when approximating -Q* using a combination of MRN and potential shaped rewards.
We use the standard potential based shaping rewards (Ng et al. 1999) expressed as the difference between discounted potential (Φ) of the next state-action pair and the potential of the current stale-action pair, for the same goal:
F(s,a,s',d ro(s', , d' a(
(6)
and a simple potential function
)(s,ag)) = (1 --11--1la0000)1 11
where is a distance measure between the state and the goal, and n is a measure of the atomicity of actions distance covered per time step. The specific form of @ shown above is explained later in the context
of Obs. [ The function d must be such that
M(s.a) = a(s,a,g) =0 ((s,a.))
(7)
4

---

Published in Transactions on Machine Learning Research (10/2025)
iee, the potential is maximized when the goal is reached. Therefore, Eq. 6 can be viewed as heuristic measure of the agent's step-improvement in the desirability of its state with respect to its goal, where "desirability" is roughly the proximity of the goal. Thus F is a suitable candidate to be an immediate step-reward, and is typically added to the default reward. An important property of such potential shaped reward function is that leaves the optimal policy unchanged Ng et al. 1999). Now, in the reward regime of Eq.
@' a. ( 71-771 ('1--0)--(111----
1-7
where ('(s, 9, the oplimal expected number of sleps required to reach the goal g from state s. Note the similarity of this expression of Q to the potential function & shown above. Our comparable choice of ø be the key to satisfying observation.
leads to a simple form of the condition that we show in the next section (Eq. S
the triangle incquality. Below, formally specify its premise
Observation 1. If d(s, g. S (L"(ss,,,)) then Φ(s, a. g) 2 (s,
In other words, if d(s, a, g)/n n is an underestimate of I then the above condition will be satisfied. Thus, d acts as an admissible heuristic. In this paper, we study two simple forms of d: the arc-cosine distance dac(s,0, cos-1 M(s.a).g /x, and the Euclidean distance dg(s, 9) [|M a) all2. both of which are metrics and satisfy Eq. 7 although dg is not necessarily bounded. These choices are simple and avoid intricate, enviromment-speccfcc reward engineering, while producing underestimates of L' (for appropriate values of 7)). However, these choices are not nccessary for our theoretical results hold and any definition of d that ensures Q' could be used. Many of the experimental (asks contain state representations that include angles mixed with non-angular features. To keep the design of F simple and domain fonaii--ndeeendeett we do not segregate these feature categorics. Consequently, dg or due applied to the full state/ state/goal vectors may not be rigorous distance measures, but may suffice as admissible heuristics. When angular features are present, dac may be relatively more accurate than dg, yielding a dominant. admissible heuristic.
We distinguish (s, a,g) the optimal action values with unshaped sparse rewards from Uj(s, a,)) which corresponds to action values with rewards shaped by F in Eq. 6 Specifically,
Q' = max E,,T,R
Arz. 8, 00 0,
QF(8,a,9) = max E.,,..
7 + Ft.g) 80 = 8,00 a, g
where Fi.g F(st, a2 S141 9).. Next we establish the validity of triangle inequality with Q7 in two cases: (i) = S x A and (ii) G G A.
3.1.1 Case I: 1= A In this setting, M the identity mapping. We use the notation 2; (St, 0t), which leads to equivalent notations for Q": (=( (s,, whenever xı = (s, a) and M = g. The main result is: Proposition 1. Consider the shaped, goul-conddlioned MDP Meer = (S, A. G. T, + F,7, Po, Pg), with g =SSxA A. The optimal universal value function QF satisfies the triangle inequality: Vz x² x E X,
+ +p(x), (x?, < (7
The only condition & must satisfy is
(( ()),,,
(8)
w.r.t. the unshaped value function, for which a sufficient condition is established in Obs. 1.
Proof: As in LLu al. 2023). consider the Markov policies æ1, R2, Ts that are optimal wr.t. (7 2²))
(x2 x²), 27 (xt .x") and the (non-Markov) policy π1-22 defined for f. as:
5

---

Published in Transactions on Machine Learning Research (10/2025)
31 (1-2(())))) [1(()s)), x² & x<e (sel of states encountered prior step 1)
x2)a otherwisc.
Let be the random variable that indicates the first time T1-22 reaches x², In the steps below, we notate F ue 1 (14111)) as Ft.go and B. Er,. for brevily. Then define
0 E
MTro + Fro) = =x',g=1 = x²
42-13 EiI -2
Σ (ras + Fegg = 2², x²
=E Σ (1)re.)) +0 -0-
Now, Q7((x' xx2) Eni..
(reo [z0 x''9 x²
1=0
D0
Emi
Σ [=T+1
(rron + Pro))ET41 = =x² = x²
(9)
and Ii T1-+2 for the first T steps. Therefore, (7(x", - -qi-2
ET.
7 (r + Figg)le,, = x². g = x²
Exi
(G'Te,a) + +()) - 75- 1-11
(1're,g) - @++ 122 1
x²
I[Q""" - 6
< 0 by assumption (Eq.
Similarly,
Q7 = -REZ..
(rig + Frg))ao = x².g = x:
S 7" Brz..
Arig + F 3
1=
Exg.
xt Feg)) x3
Fkg +0 - -- 2r 1-
=Er
Arkg 7" 2r " 12, 13
k=T
-
(10)
since n2 = R1-2 after r. Therefore, Q3 (x² 2²3)
22-0 S 0. Consoquently,
F- x = ا + 22. 2 (x' x²) + (7,
But since the optimal (7 2 Q 12 (xx
) we arrive at the triangle inequality.
7

---

Published in Transactions on Machine Learning Research (10/2025)
3.1.2 Case II: 9 # xxxx A
The proof of this case closely resembles (Liu et al. 2023 ; we highlight the main difference in blue color but also provide the rest of the proof for completeness. In this case; M is an onto mapping. Given a goal g, the GCRL problem effectively reduces to standard MDP and there exists a deterministic optimal policy x² for reaching the goal g from an initial state as) Then, under deterministic dynamics,
Q2(o,))
sup (7(x, "(:
Assuming the supremum is attainable, let
Bg = arg
max <a:
Q2(2, x');
(11)
then ()((, (z)) Assune for contradiction that this is not the case, ie., (2(x,9) # Q7(1) There are two possibilities:
If (p(x, > @z(x.g): This would imply that by using policy that selects my rather than g. one could achieve a higher return. This contradicts the definition of x² as the optimal policy, thus Qj(n,, x.y) > (T, cannot be true.
If (x, Q7 g): Let
T "
min( 9);
such that is the first (s, a) pair along the optimal trajectory that achieves the goal. There are two further cases:
1. After reaching 27, will repeatedly return to 2,. In this case, we have Q7(xx 2 (z(,, by the definition of Fg (Eq. 11 and
(r(1,r,) = Q7(1, g) - 17
(7((,9) 7 (xr. 66z 9]]
2 Qr((,9), by Eq. g
(12)
Combining the two, we get Q7(2, 2 (1, which contradicts our assumption that (7(r,)) > (2))))g)
2. x" never returns to 2, after reaching it for the first time. In this case, one can find the next
7' ='= (M()))((M()))>>>>>>>>>> = =)) g). such that Fy another (s, a) along the optimal trajectory. Again, there are two sub-cases:
(a) If n² repeatedly visits x,', then the argument in the first case applies.
(b) Otherwise, recursively find the next 7", and so Eventually, may have last state zç such that no /. >>> Ç satisfies M(x,) = g. Then, (r, 2 (x( 2 Q7 g). The last inequality is derived in the same way as Eq. [2] Alternatively, there may exist an infinite sequence of such {.,). Following this sequence, the claim remains true but the supremum is not attainable. However, in this case an 2, can be found in the sequence such that Q7- xty) arbitrarily close ())
3.1.3 Insufficiency of Policy Invariance
A well-known property of potential-based reward shaping is that it does not change the optimal policy (gg let al. 1999). Could the preservation of the quasipseudometric property of the optimal value function under this strategy for reward densification be a trivial consequence of this property? We show in this section that that is not the case. Specifically, we show that violation of Eq. can break triangle inequality without affecting policy invariance.
For counterexample, consider the simple MDP shown in Fig. I It has 3 states, S S3 navigable by action and absorbing state SA that can only be reached by action b from any other state.
7

---

Published in Transactions on Machine Learning Research (10/2025)
FetchPick
FetchPush
FetchReach
FetchSlide
2
a
Block Full
Block ParalePa
Block RotateXYZ
Block RotateZ
S
b
S3
b
b
Egg Full
Egg Rotate
Pen Full
Pen
SA
Rotate
a, b
(a)
(b)
Figure 1: (a) Counterexample used in Secs. 3.1.3 and 3.2 (b) GCRL benchmark environments Plappert ct al. 2018 Figure from [Luu et al. 2023
Proposition 2. In the countererample of Pig. [a), the potential function for various states with gool S S3 can be set such that policy invariance is preserved, yet the assumption of Eq. well as the guasipscudometric property violated.
Proof: First note that the optimal policy for goal S2 or S3 is to take action a, these goals unreachable via action b. For some 0, we set:
OSS Sz) Q* a, Sz)
(satisfics Eq.
#(S2. a, 53) = Q' a, Sz)
(violates Eq.
o(S1, a, = Q"((S,, a, S2) +
(satisfies Eq.
These yield: Q7 Sz) (} a, S2) = -a, (7 Sa) a. Since the goals are unreachable via
action b, it is straightforward to set o(*, b, *) such that the optimal policy stays unchanged for Qú However, now the triangle inequality is violated:
a + (S2, = -a + 1 (i L
This proves the criticality of Eq. 8 and that policy invariance of potential based shaping is insufficient to ensure the quasipsendommttrcc property.
3.1.4 Projection
QF has the same upper bound as Q", since the MRN architecture needs no modification, specifically to Eq. 3 as the critic output is guaranteed to non-positive despite potentially positive shaping rewards. However, Qi has a more informed lower bound:
((s,a,)) - 0 by Eq. Consequently,
Q'((,,,g) Q" (8, (.gg) (ss,
1-7 Ö(s,
d(s,,.9)/1
(13)
which we impose on the critic with dar since it is bounded. Recent analyses Gupta et al. 2022 have shown that projection informed by shaping effectively reduces the size of the state space for exploration, leading to improved regret bounds. We show the full algorithm for clarity in Alg. [
8

---

Published in Transactions on Machine Learning Research (10/2025)
3.1.5 Estimation of
As both the design of F and the above projection operation needs an estimate of 77, it is useful to consider how one might estimate 7). From Obs. [ we want to ensure that d/n an underestimate of L by controlling ne. For Euelidean tasks, 7f can be set the average distance that the agent covers belween successive clock ticks. If this information is not available, it can be approximated via simple experiments. For non- non-Euclidean tasks (e.g., those with quaternions in states), this is not straightforward. Moreover, we have an added constraint that we do not separate the quaternions from the Euclidean parts of state to keep the reward design simple as mentioned in Sec. 3.1 In such cases, one could perform data-driven calibration to estimate the ratio d/L" by learning to optimally complete simpler tasks, measuring their L", and finally taking the maximum ratio over those tasks. [Snn et al. (2019) propose an approach to estimate L using the notion of k-step solvability by learning k-step subpolicies recursively; one of their solvability tests uses an approach similar to the calibration approach suggested above, although it requires the environment to have reset operator. Either of these approaches could defeat our original purpose of keeping the reward design simple in non-Euclidean tasks, and is limitation. For our experiments, we select 17 empirically via a simple parameter search.
Algorithm 1 GCRL with Potential-Shaped Dense Rewards
1: Randomly initialize MRN (or another quasimetric) critic QF and actor π for episode < ....... do Select goal g ~ Pg, initial state Po Select action a ~ g)
5: for f 1,2,..... do
6: Exccute action in state s and receive reward next state s'
7: Select next action a' ~ <<11s'g))
8: Store tuple a,,,, a', ) in replay memory D
a, a
10: end for
11:
Sample minibatch as, s','',''') g))
from DD
12:
g' + Relabel goals g to g' in the minibatch by HER with original reward r, then update to r
13:
Calculate target using shaped reward (r' + FFFsss a, ,²,,
14:
Clip target according to Eq. 13 if using arc-cosine distance dac
15:
Use (clipped) target in Eq. to update FRRN/quasimctie critic QF
16:
Update actor æ
17:
end for
3.2
Failure of a Potential Fetential-Free, Dense Reward Function
A common dense reward function is F(s,a, ,' -dg(s,a,g) (s, a) glla without involving potential function. Although Euclidean distance generally satisfies the triangle inequality, argue that - -I|M(s, a) - g||2 may not, using the same counterexample of Fig. a). Since (S1,a) transitions to (i.e., achieves) S, and (82,a) to (achieves) 83, ()) (
0, but a)) > (= 6, say). Hence, -IIM a) - S2lla - | (S2, a) S312 & -I|M a) - Szllz- Also, R(S1, a, Sz) = R(S2, a, S3) = 0, but R(SI, a, S3) = by Eq. [ Noting that the agent can never reach back state S2 once it
O and QF(51, a, 5s) = -(1 + 8). For an appropriate choice of vector representation of states (particularly S2 and Sz) such that d > T- we have @F S2) + Q7 a, S3) 1 a,, Thus, the optimal value function shaped in this way may violate the triangle inequality.
S2, Q7 a, S2) = - (S2,
3.3 Intermediate Value Functions
In their critique of on-policy Q-function estimation methods for GCRL such as DDPG in continuous control tasks, Wang et al. (2023) show that on-policy Q-function may not be a quasipscudomctric, even though the optimal Q-function is. However, their counterexample is an extreme policy that is unlikely be encountered during on-policy iterations. First, we adjust the terminology refer to these value functions as intermediate
9

---

Published in Transactions on Machine Learning Research (10/2025)
value functions, i.c., the value functions learned en-route to the optimal. This adjustment is warranted the Q-functions may not be on-policy when HER relabelling of goals is utilized. Note however, we use HER in Alg. [ and for experimentation, but it is not necessary for any theoretical result in this paper.
In this section, we establish that intermediate Q-functions do indeed satisfy the triangle inequality (and hence meet the quasipseudonetric criterion) the policy makes a minimal progress toward the goal. We call such policies progressive policies and believe they are more relevant intermediate Q-function estimation in GCRL than the counterexample in Wann et al. (2023) (Theorem 1). We first formalize the notion of progressive policies, specify assumption, and finally show that the corresponding value functions satisfy the triangle incquality.
For notational convenience, we wrile E. B.s=((()..)))))m)(()) simply as Ex' Note that the value function for a policy x satisfies
(T a() yEg (0'66,600)
(14)
Definition For any (s,a,g) E Sx Ax 9, the progress of a GCRL policy a is given by
(s, 9) = Ey' a' Q (5((''''))) - (s,
We refer to A for the optimal policy as A We assume that the progress of π is not unboundedly different from that of the optimal policy, i.e, the following holds for some 0 < e < oo
S a - A (s, S 2e.
(15)
Note that (i) does not need to be small, just finite; (ii) the counterexample Wang et al. (2023) does not satisfy this assumption. Our main result of this section is:
Proposition 3. Consider the goal-come coal-conditioned MDP Mcc
A. A,T,,,,,, 7s PoP pg). The value function Q defined in Eq. 14 for any policy π that sulisfies Eq. 15 also salisfies the triangle inequalily: Vx x² x E X,
Q= x²) Q"
(x x0) (x*,t
Proof: From Eq. 14 we have,
Ed (0)()) = (Q - R(s, g))//>
Then, using Eq. 15 and Def. for cither 2 = (x), 22) or x (x², )²), the following holds:
A - = (2) R(2) (x) (²(()) R(z) + (z)
-
[ -1Q Q²)
2 (by Eq. 15
Adding for = (x. ) and (x² )²); ) we get
2ey
Q*(xt,x2) + (2), -7()))))) (x)
(16)
But similarly for 2 = (x),,²3)
A=())-A7)) -00
1_ Finally, the result is obtained by combining this with Eq. 16 and noting that the triangle incquality holds for the optimal Q-value function, ie., Q' (x',,²)+ + 7
by Eq. 15 This gives (x x²)) < (x' x²) + 20
Qa 2 x Q* (xr1 ,²)).
10

---

Published in Transactions on Machine Learning Research (10/2025)
This result relies on the triangle inequality of the optimal value function as established before in (Liu et al, 2023) for sparse rewards and in Sec. 3.1 for potential-shaped dense rewards. But it does not have any dependence on whether M is one-to-one or onto, hence the two cases 9 = S x A and g * S x A do not need to be distinguished. The result also does not assume any specific form of, or bounds on, the reward function. Hence extends readily to shaped rewards as well, as long as the shaped value function respects the same upper bound (Sec. 3.1.4), Q%(.) 0.
4 Related Work
Several value function representations have been proposed for GCRL over the last decade. Schaul et al. (2015) introduced the bilinear decomposition, later generalized to bilinear value networks (ang et al, 2022) with better learning efficiency. Pitis et al. (2020) proposed the deep norm (DN) and wide norm (WN) families of neural representations that respect the triangle inequality. However, they are restricted to norm-induced functions, and are generally unable to represent all functions that respect the triangle inequality. By contrast, Possion Quasi-metric Embedding (PQE) (Wang & Isola 2022) can universally approximate any quasipsendometric,, thus improving upon DN/WN However, as Liu et al. (2023) argue, PQE captures the restrictive form of first hitring-time when applied to GCRL, whereas MRNs capture the more general setting of repeated return to goal (Q*(g. + 0), while preserving the UVFA property of PQFs. Durugkar et al. (2021) introduced a quasipseudometric that estimates the Wasserstein-1 distance between state visitation distributions, minimizing which is equivalent to policy optimization in GCRL tasks with deterministic transition dynamics. While they use the Wasscrstein discriminator reward shaping (as intrinsic molivation), our goal is different. We prove that dense rewards via shaping preserves the triangle inequality for the general class of potential based shaping, not just for the Wasserstein based guasipseudometric. Other recent architectures for GCRL use contrastive representation (Eysenbach) et al. 2022 but without regard to quasipsendometric architecture, and quasimetric RL (QRL) (Wang et al. 2023 where temporal distances are learned, although it unclear if respects the triangle inequality stochastic settings.
a potential for
While the above literature representation learning has been centered on expressive and flexible representa- tions for GCRL, their analyses are generally restricted to sparse reward settings. In fact, past experimentation
with certain types of dense rewards in GCRL have yielded negative results (Plappert et al. 2018 Plappert
et al. (2018) argue that dense reward signals are hard to learn from because (i) arbitrary distance measures
(e.g., Euclidean distance and quatermions for rotations) are highly non-linear; (fi) dense rewards bias the
policy toward specific strategics that may be sub-optimal. Similar arguments also appear (Liu et al.,
2022). However, our setting overcomes these objections. First, we establish the sufficient condition (Eq. [ for the triangle inequality that may not be satisfied by arbitrary distance measures, é, providing guidance the contrary. And second, we use potential based reward shaping (Ng et al. 1999) which is policy invariant, hence strategically unbiased. However, we acknowledge the large body of work on reward shaping (Tang ett al. 2017 Brys et al.) 2014 Devlin & Kudenko, 2012 Knox & Stone, 2009 Van Seijen et al., 2017) of various types (e.g., count- based, intrinsic motivation, human advice, etc.) design is often employed to explicitly bias the policies.
where careful, heuristic reward
5 Experimental Results
We use GCRL benchmark manipulation tasks with the Fetch robot and Shadow-hand domains (Plappert et al. 2018;; see Fig. [b). We use two critic architectures to demonstrate generality: MRN (Lu et al.
2023 and PQE (Wang& Isola 2022). We experimentally evaluate the following hypotheses:
Hypothesis 1: Potential-based dense rewards satisfying Eq. S may improve GCRL's sample complexity when using quasimetric critic architectures. Specifically, the property of Q* function that they capture- that it satisfies the triangle inequality-is preserved in the presence of shaped rewards with the new value function Q7. Such dense rewards may enable the less restrictive Q; to be learned more efficiently than Q*.
Hypothesis 2: Plappert et al. (2018) found that certain types of dense rewards hurt RL performance in GCRL robot manipulation tasks. This negative result contradicts our Hypothesis We conjecture that their application of dense rewards did not satisfy the required structure- strueture--ppccffcllll specifically Eq. -wiich
which is why failed. To confirm this contradiction, we verify that our dense reward setting does not deteriorate RL performance
11

---

Published in Transactions on Machine Learning Research (10/2025)
FetchReach
FetchPush
FetchSilde
FetchPick
18.9
SUccess Rate
9.%
Sparse rewards
6.7%
with due
with de
Ocvect
29%
Default dense rewards
BlockRotateZ
BlockRotateParaltel
BlockRotateXYZ
BlockFull
13.9%
Success Rate
0.9%
2.9
EggRotate
EggFull
PenRotate
PenFull
180%
Succe5s Rate
8.%
0.7%
27%
Epoch
Epoch
Epoch
Epoch
Figure 2: Comparison of MRN with sparse rewards vs. potential-shaped dense rewards with three definitions of potential & and potential-free default dense rewards. Learning curves averaged over five independent trials, and one standard deviation bands are included. We statistically significant improvement of perfor- mance due to potential-based based dense rewards with dae in 4 of the 12 environments, viz., FetchSlide, BlockFull, Eggfull and PenFull, and in 1 environment (FetchSlide) for dg. There is no statistically significant deterio- ration in any environment. for either dac or dg-
in any task using potential function basod on either das or dg. Additionally, to investigate the consequence of violating Eq.B8 [ Lest & direct potential function ddirect (s,a, a,,) g) (s, as,a) that bypasses the distance function and the potential-free default dense rewards of these environments (Cymnasium-RRoootic, 2018)
that are based on Euclidean distance and may violate the triangle inequality argued in Sec. 3.2 Note that as Pdirect is no longer comparable to Q", it may easily violate Obs. and Eq. S Moreover, as both Ødirect and the default dense rewards lead to polentially unbounded value functions, we do not clip the corresponding critics (Eq.
Table 1: How often the three potential functions satisfy Eq. critics from the final training epoch estimates of optimal
We use the learned Q-values with MRN
Environment
á with d.o. (%)
with dg (%)
Odirect (%)
ReachReach
59.098 + 1.444
86.345 4.098
8.523 + 0.203
FetchPush
98.984 = 0.480
46.860 1.071
28.664 0.599
FetchSlide
99.726 = 0.089
95.851
0.248
63.053 2.149
FetchPick
97.907 = 0.819
71.256
0.932
26.057 = 0.889
BlockRotateZ
96.453 = 1.052
0.692 82.453
4.693 = 0.182
BlockRotateearralll
98.927 = 0.387
0.681 81.996
5.751 = 0.306
BlockRotateXYZ
98.786 = 0.289
0.371 91.542
10.269 0.262
BlockFull
99.705 = 0.115
92.574 0.259
40.727 2.390
EggRotate
97.842 = 0.908
1.104 85.228
6.674 = 0.272
EgglFull
99.647 = 0.201
95.662 0.560
56.173 3.040
PenRotate
97.955 = 1.066
1.168 79.251
20.911 0.964
PenFuul
97.994 + 0.760
76.868 1.044
21.576 0.586
12

---

Published in Transactions on Machine Learning Research (10/2025)
FetchReach
FetchPush
FetchSilde
FetchPick
100%
Success Rate
Sparse rewards
6.h
with due
with de
Aetwe
279
Default dense rewards
BlockRatateZ
BlockRotateParallel
BlockRatateXYZ
BlockFull
100%
Success Ratee
0.1%
EggRotate
EggFull
PenRotate
PenFull
100%
Success Ratee
09%
29%
Epoch
Epoch
Epoch
Epoch
Figure Comparison of PQE critic architecture with sparse rewards vs. potential-shaped dense rewards with three definitions of potential e and potential-free default dense rewards. Learning curves averaged over five independent trials, and one standard deviation bands are included. We statistically significant improvement of performance due to potential-based dense rewards with dac in 3 environments, viz., BlockFull, Eggfull and PenRotate and PenFull, but none with dg. There is statistically significant deterioration in Rotate with dac which we attribute to not tuning 1 for PQE critics.
We use the MRN code repository publicly available at: ltttps://github.com http:/ttubbcoo/aaaaaaaaaaa--aaee weweerreeesuuaaaeeeeeeeeee
which implements DDPG+HER with MRN and PQE (among others) critics for the GCRL manipulation tasks. We make two simple modifications: (1) add Eq. 0 to the default (sparse) reward function (Eq.
shown line 13 in Alg, D (2) use Eq, 13 to clip the critic's output shown on line 14 in Alg. [ but only for dac- No other changes were made to any algorithm or neural architecture. The newly added parameter 1) was set to 0.01 for dae and 0.2 for dg. These values were selected from the sets (0.01, 0.02, 0.03, 0.04, 0.05] [ for dac and (0.02, 0.2, 2.0} for dg, using performance improvement with MRN architecture as the criterion. Our modified versions the code and scripts are also available at: lhttps://github. com/ www.iahon/o/oooeee........wwaoaa (CCRL-Dense Rewaer All experiments were run on NVIDIA Quadro RTX 6000 GPUs with 24 GiB of memory each and running Ubuntu 24.04.
We show the success rates of the learned policies after every training epoch for MRN and PQE critic architectures in Figs. 2 and respectively. We see from Fig, that indeed potential-based dense rewards with dac and dg improve the sample complexity in some environments, to an extent that is statistically significant as shown with standard deviation bands. In particular, there is statistically significant improvement in of the 12 environments, viz., FetchSlide, BlockFull, Eggfulll and PenFull with dac: but only one environment (FetchSlide) with dg. Not only the sample complexity improved, but also higher quality policies are learned. This confirms Hypothesis Furthermore, no statistically significant deterioration observed in any environment with duc dg, confirming Hypothesis 2. In BlockRotateParallae although the mean of Φ with dae appears worse, the difference is not statistically significant. as the other methods are subsumed within its error-band. The sample complexity of 6 with de could conceivably improve with a more informed choice of n. We did not conduct a separate parameter search for PQE critics; instead, we used the same n values as above. Fig. with PQE critics shows similar statistically significant improvements in BlockFull,
We show sensitivity results for several values of y with MRN Fig. which indicates that further reducing n detrimental and possibly fails admissibility the heuristic.
13

---

Published in Transactions on Machine Learning Research (10/2025)
FetchReach
FetchPush
FetchSilde
FetchPick
100%
Success Rate
g=0.005
0=0.01
499
0=0.02
0=0.05
BlockRotateZ
BlockRolateParallel
BlockRotateXYZ
BlockFull
100%
Success Ratee
479
EggRotate
EggFull
PenRotate
PenFull
Success Ratte
4.9
16
Epoch
Epoch
Epoch
Epoch
Figure Comparison of MRN with potential-shaped dense rewards using dac with various values of r.. 7 0.01 is used in experiments reported in Fig.
EggFull, Penrotate and PenFull with does but none with dg. Interestingly, due also shows an initial speed-up in FetchSlide, BlockRotate7, BlockRotateParalle, and EggRotate compared to the sparse reward setting, but this advantage does not persist when the policies asymptote. Contrarily to Hypothesis however, see statist ically significant deterioration with dac in EggRotate (and to lesser extent in BlockRouateXY7)) although none with dg. We attribute this to the fact that was not tuned for PQE critics.
Fig. 2 shows that sample complexity significantly worsened in of 12 environments with ddirect, viz., Rltate,, Block BlockRouateXYZ, Block EggRotate and EggFull. Similarly, Fig. 3 with PQE critics shows worse sample complexity for Ødirect in BlockRotateZ, BlockRottaeeParalle BlockRo- tateXYZ, EggRotate and Full enviromments. These are consistent with Tab. [ which shows that Ødirect has high propensity of violating Eq. R in most of these cases, which is further evidence of the criticality of Eq. Figs. 2 and 3 also show significantly worse performance from the default dense rewards in all envi- ronments, which is consistent with our finding in Sec. 3.2 In case Plappert et al. (0188) used this default dense reward, these results would also be consistent with their findings.
6 Conclusion
We have presented generalizations of previous results on triangle inequality the context of value functions in GCRL. Specifically, we have shown that the optimal value function satisfies the triangle inequality even when the reward function is densified with particular class of shaping functions. Additionally, shown that the intermediate value functions also satisfy the triangle inequality if the underlying policy satisfics a cortain progressive criterion. Both of these findings contradict previously published results in some ways, which emphasizes the importance of the nuanced conditions behind our results. Experiments in 12 benchmark GCRL tasks confirm that our prescribed dense rewards either improve upon or match the sample efficiency of the sparse reward setting, but could worsen it the key condition violated. Future investigations could focus on more general classes of reward functions that preserve the quasipsendometric property of value functions and/or lend themselves to other, potentially more effective, architectures.
have
14

---

Published in Transactions on Machine Learning Research (10/2025)
7 Acknowledgments
We would like to acknowledge constructive feedback from the anonymous reviewers which helped to substan- tially improve this paper. An earlier version of this paper was published as the first author's Honors thesis at: httpps//aqqus usm edu/honors, tttrsssttheeso//// The experiments reported in this paper were conducted on a GPU computing cluster purchasod under an Air Force Rescarch Lab grant FA8750-20-1-0105.
References
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba. Hindsight experience re- play. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 30. Curran Associales, Inc., 2017. URL https://proceediing newrineurppp... wweurips.c/ppppe..... files//paperr2/11/iiel 4sSfafabbsaaatt00drrr444455675-3
pdf
Tim Brys, Ann Nowé, Daniel Kudenko, and Matthew Taylor. Combining multiple correlated reward and shaping signals by measuring confidence, volume 28, pp. 1687-1693. AAAI Press, Quec City, Qubec, Canada, Jul 2014.
Sam Devlin and Daniel Kudenko. Dynamic potential-based reward shaping, volume 1, pp. 433 433-440. Interna- tional Foundation for Autonomous Agents and Multiagent Systems, Valencia, Spain, 2012.
Ishan Durugkar, Mauricio Tec, Scott Niekum, and Peter Stone. Adversarial intrinsic motivation for rein- forcement learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
net net.
Benjamin Eysenbach, Tianjun Zhang, Sergey Levine, and Ruslan Salakhutdinov. Contrastive learning goal-conditioned reinforcement learning. Advances in Neural Information Processing Systems, pp. 35603- 35620, Dec 2022.
Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Manon Devin, Benjamin Eysenbach, and Sergey Levine. Learning to Reach Goals via Iterated Supervised Learning. In International Conference on Learning Representations, 2021. URL http:////pppeeeeeeeeeee/rrrr//ae
Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai, Sham Kakade, and Sergey Levine. Unpacking reward shap- ing: Understanding the benefits of reward engineering sample complexity. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 15281-15295, Curran Associates, Inc., 2022. URL httpss:/ http://07555---Papa---o-or-eeeee Conferencee.nenee pdf
wwwp:eiiiiinnnnnuis.oo..... neurips. cc/
Gymmasium-Robottie. Gymnasium Roboticcs Documentation. In Farama Foundation, 2018.
https:
W Bradley Knox and Peter Stone. Intcractively shaping agents via human reinforeement: The tamer framework. In Proceedings of the Fifth International Conference on Knowledge Caplure, pp. 9 16. ACM, 2009.
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wicrstra. Contimuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference. Track Proceedings, 2016. URL http://arxiv http::///axxv..o//bbsssss/ abg/abs/1509. 02971
Bo Liu, Yihao Feng. Qiang Liu, and Peter Stone. Metric residual networks for sample efficient goal- conditioned reinforcement learning. In Shirty-Seventh AAAI Conference on Artificial Intelligence (AAAI), Februray 2023.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Minghuan Liu, Menghui Zhu, and Weinan Zhang. Goal-conditonned reinforcement learning: Problems and solutions. In Lud De Raedt (ed.); Proceedings of the Thirly-Firsl International Joönl Conference Artificial Intelligence, IJCAI-22, pp. 5502 5511. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10.24963 /tjcc/aiii22222//22 URL httpp:://oi..iooo ottp.////......///..aa..ao...... 2022/777 Survey Track.
Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proc. 16th International Conf. on Machine Learning, pp. 278-221 287.
Morgan Kaufmann, 1999.
Silviu Pitis, Harris Chan, Kiarash Jamali, and Jimmy Ba. An inductive bias for distances: Neural nets that respect the triangle inequality. In International Conference on Learning Representations, 2020. https:
//openreview. htt.:/oorromm///---oo-
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, Vikash Kumar, and Wojeiech Zaremba. Multi- Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research, 2018.
https::/arxivvorg//bbbl httpa//wwww..rga/a///a/0/// abs/1802.09464.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In Francis R. Bach and David M. Blei (eds.), Proc. International Conference on Machine Learning (ICML), volume 37 of JMLR Workshop and Conference Proceedings, pp. 1312 1320. JMLR.org, 2015. URL http: 7/dblp. trier de/ab/ cecoon///im////a/ himml//icm1211111 ht..shhhhhhhShhSHHH......
Hao Sun, Zhizhong Li, Xiaotong Liu, Dahua Lin, and Bolei Zhou. Policy continuation with hindsight inverse dynamics. In Proceedings of the 33rd International Conference Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. #exploration: A study of count-based exploration for deep reinforcement learning. In Proceedings of the 31st International Conference on Newral Information Processing Systems, pp. 2753 27622. Curran Associates, Inc., 2017.
Harm Van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tom Barnes, and Jonathan Tsang. Hybrid reward architecture for reinforcement learning, volume 30, pp. 1-10. Curran Associates, Inc., 2017.
Tongzhou Wang and Phillip Isola. On the learning and learnability of quasimetrics. In International Con- ference on Learning Representations, 2022. http:p////gaarrreeeeeeee///////a
Tongzhou Wang, Antonio Torralba, Phillip Isola, and Amy Zhang. Optimal goal-reaching reinforcement learning via quasimetric learning. In Proceedings of the 40th International Conference on Machine Learn- ing, pp. 36411-36430. PMLR, 2023.
Ge Yang, Zhang-Wa Wei Hong, and Pulkit Agrawal. Bi-linear value networks for multi-goal reinforcement learning. In International Conference on Learning Representations, 2022. https://openreviee.nst
forum?id:LedDbtl.mo
16


Reviews:
[{"review_id": "UL3SUAx7yW", "reviewer": "Reviewer_rxzY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- Revisiting the dense reward for GCRL and challenging the long-standing conclusion from Plappert et al. 2018 is an important research step. This can reopen the investigation of dense reward in GCRL. This is, for sure, an important supplement for the community to understand GCRL better.\n\n- This paper provides a convincing explanation for the performance drop reported in Plappert et al. 2018 and offers concrete guidance to avoid such deterioration when using dense rewards in GCRL. \n\n- Comprehensive experiments -- counter examples are included and discussed to better verify the key insights.\n\n### Weaknesses/suggestions:\n\n- Some of the claims are unnecessary/can be made clearer: \nIn page 3, line 7, \"DDPG is an off-policy method, although it estimates Q-values in an on-policy way\". Can the authors explain why it is necessary to emphasize that the Q value estimation is on-policy? Please also explain the on-policy argument, as DDPG and HER are off-policy methods.\n\n- The work is strongly based on MRN. I agree that the MRN and its properties are essential in inspiring the exploration of dense reward in GCRL, and it empirically outperforms original MLP designs. Yet, since the heuristic design is not necessary with the proposed algorithm, the method may gain more insight through an ablation study of comparing the usage w/ & w/o MRN. The ablation study can provide additional insights (e.g., the empirical necessity of MRN when using dense reward)\n\n- The usage of k-step reachability (ie., the notion of L) has been discussed in Sun et al. \"Policy continuation with hindsight inverse dynamics.\" NeurIPS 2019. The difficulty of introducing first-hitting-time in those tasks lies in its empirical estimation, especially in non-Euclidean tasks. An extended discussion on how to potentially approximate L in practice, and how to heuristically design such approximations, would be helpful. \n\n- The overall flow of the paper could be further improved. For example, each major section could start with a short paragraph stating its main objective and outlining its structure. This would help readers understand how the section fits into the overall argument, and what to expect in the upcoming subsections. Such paragraphs would be particularly useful for sections with multiple theoretical results (e.g., Sec. 3) to make the progression of ideas clearer.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper extends the triangle inequality property of GCRL value functions from sparse to a class of potential-based dense rewards, introduces a progressive policy condition for intermediate value functions, and empirically shows in 12 benchmarks that such dense rewards can improve or preserve sample efficiency while explaining and avoiding prior negative results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses. \n\nFor weakness two -- it's not a requested change, but adding an ablation study (even in 1 or 2 environments) would make the results more comprehensive.", "broader_impact_concerns": "The topic discussed in this paper is important, and this paper may kick-start future discussions on dense reward in GCRL.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PQgROJCGPv", "reviewer": "Reviewer_kWs5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper provides an analysis of the quasipseudometric properties of value functions and intermediate value functions in the setting of modified dense rewards.\n\n2. The authors support their claim that Metric Residual Networks (MRNs) learn more quickly in the modified reward setting and back it up with a set of experiments.\n\n**Weaknesses:**\n\n1. The presentation in the paper is very unclear, and I struggled to understand what extra contributions the authors made compared to previous work. Overall, the writing is so convoluted that it is difficult to discern the main results of the paper.\n\nIn particular, in the abstract the authors state:\n\n> \"We show that [...] the triangle inequality is preserved under a dense reward setting as well,...\"\n\nThen, in the contribution paragraph of the Introduction section, the authors state:\n\n> \"We show that using rewards shaped with potential functions that serve as admissible heuristics, the optimal value function does satisfy the triangle inequality.\"\n\nLater in the text, the authors mention:\n\n> \"Our primary claim is that $-Q^*$ satisfies the triangle inequality not only in the sparse reward setting, but also in the presence of dense rewards, particularly potential-shaped rewards (Ng et al., 1999).\"\n\nThese theoretical claims are very unclear because:\n\n(1) \"Reward density\" is never defined. When a reader has an intuition of reward density, if any mathematical claims are made about it, it must be explicitly defined.\n\n(2) The derivation of the main results in the previous work (Liu 2023) does not seem to use sparsity of rewards. Theorem 1 in that work is stated for a general GCMDP and does not require any additional assumption on reward sparsity.\n\n(3) It is not clear whether the theoretical claims apply to general dense rewards or only to potential-based shaped rewards.\n\nSecond, the experimental section is unclear about the exact reward-shaping method used. The paper states:\n\n> \"We make two simple modifications: (1) add Eq. 6 to the default (sparse) reward function (Eq. 1) as shown on line 13 in Alg. 1.\"\n\nLine 13 of Algorithm 1 reads:\n\n> \"Calculate target using shaped reward \\((r' + F(s,a,s',a',g')).\\)\"\n\nFunction F then is defined in Eq. 6 as $\\gamma*\\phi(s',a',g) – \\phi(s,a,g)$. Function $\\phi$, in turn, is defined using the distance function $d(s,a,g)$, two variants of which ($d_{ac}$ and $d_E$) rely on the mapping $M(s,a)$ — introduced earlier as \"mapping the product space of $S$ and $A$ to $G$, essentially flagging goal achievement,\" but never formally defined. This presentation of the practical method is opaque; it needs to be rewritten to be concise and explicitly show how to modify rewards based on available data.\n\n2. The paper contains numerous mathematical and notational errors, which further hinder comprehension. For example, $r_{t,g}$ in the definition of the Q function is never defined. Additionally, functions $Q^\\*$ and $Q_F^*$ are initially defined as functions of three arguments $(s,a,g)$, but in Proposition 1 they are suddenly treated as functions of two arguments from a space $\\mathcal{X}$—yet $\\mathcal{X}$ is only introduced as a generic example of a metric space and never formally defined.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors propose extending the quasipseudometric analysis of goal-conditioned reinforcement learning to a dense reward setting. They provide theoretical arguments suggesting that, under a simple potential-based reward shaping scheme and what they term a minimal “progress-toward-goal” condition, both the optimal value function $Q^*(s,a,g)$ and the on-policy value function $Q^\\pi$ may still satisfy the triangle inequality. Building on this conjecture, they present empirical results on twelve continuous-control benchmarks that appear to show properly conditioned dense rewards can maintain or even improve sample complexity relative to unmodified rewards.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "**Requested Changes:**\n\n1. Authors need to improve the clarity of the paper. The presentation was already an issue in the previous submission; rather than minor edits, I suggest the authors to rewrite the paper with a clear narrative. In particular, they should explicitly identify their contributions compared to prior work—for example, by stating that the dense reward case considered here is more general than Liu (2023) because certain assumptions have been removed or weakened.\n\n2. The authors should refine the mathematical notation.\n\n3. The authors should provide an explicit algorithm (in pseudocode or code form) and supply the code repository along with instructions for reproducing the empirical results.\n\n4. Figures 1 and 2 should be combined into a single figure with two subfigures (a) and (b) sharing a joint caption.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oJICuNH0Sk", "reviewer": "Reviewer_CTFQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The introduction of \"progressive policies\" to support triangle inequality in learned (intermediate) Q-functions is interesting.\n\n2. Solid empirical results are conducted across diverse tasks support theoretical claims.\n\n3. Ablations are abundant, which is nice. They help to clarify when reward shaping fails (e.g., default dense rewards, direct Euclidean potentials).\n\nWeaknesses:\n\n1. Evaluation is limited to MRN; generalization to other architectures is not demonstrated.\n\n2. Sensitivity to the shaping parameter $\\eta$ is not analyzed.\n\n3. It seems most of the theoretical parts are based on previous MRN results. Thus theoretical novelty is rather incremental, which is also mentioned by previous reviews.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper extends the quasipseudometric analysis of goal-conditioned RL (GCRL) value functions to dense reward settings. It identifies a sufficient condition—potential functions that upper-bound the optimal Q-values—under which the triangle inequality (and thus quasipseudometric structure) is preserved. This result is generalized from optimal to intermediate value functions, under the assumption of progressive policies. Empirical validation across 12 robotics benchmarks shows that potential-based dense rewards improve or maintain sample efficiency compared to sparse or default dense rewards. The work challenges prior negative results on dense rewards in GCRL and clarifies when such rewards are beneficial.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Generally I acknowledge this version has addressed many requested changes from the previous version's feedback. Here are two changes, the first item is more important than the second one.\n\n1. Test or discuss applicability of findings beyond MRN (e.g., with PQE or standard critics).\n2. Add sensitivity analysis for the shaping parameter .", "broader_impact_concerns": "NA. The work is theoretical and algorithmic in nature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)