QPRL : Learning Optimal Policies with Quasi-Potential Functions for Asymmetric Traversal
Authors: Jumman Hossain
Nirmalya Roy
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Quasi-Potential Functions
Quasimetric Learning
Asymmetric Traversal Costs
Primary area: reinforcement_learning
TL;DR: Introduces a theoretical framework for reinforcement learning using quasi-potential functions to handle asymmetric traversal costs

Abstract: Reinforcement learning (RL) in real-world tasks such as robotic navigation often encounters environments with asymmetric traversal costs, where actions like climbing uphill versus moving downhill incur distinctly different penalties, or transitions may become irreversible. While recent quasimetric RL methods relax symmetry assumptions, they typically do not explicitly account for path-dependent costs or provide rigorous safety guarantees. We introduce Quasi-Potential Reinforcement Learning (QPRL), a novel framework that explicitly decomposes asymmetric traversal costs into a path-independent potential function ($\Phi$) and a path-dependent residual ($\Psi$). This decomposition allows efficient learning and stable policy optimization via a Lyapunov-based safety mechanism. Theoretically, we prove that QPRL achieves convergence with improved sample complexity of $\tilde{O}(\sqrt{T})$, surpassing prior quasimetric RL bounds of $\tilde{O}(T)$. Empirically, our experiments demonstrate that QPRL attains state-of-the-art performance across various navigation and control tasks, significantly reducing irreversible constraint violations by approximately $4\times$ compared to baselines.

QPRL: Learning Optimal Policies with Quasi-Potential Functions for Asymmetric Traversal
Jumman Hossain
Nirmalya Roy'
Abstract
Uphill: c(#1 + 82) =5
Reinforcement learning (RL) in real-world tasks such as robotic navigation often encounters envi- ronments with asymmetric traversal costs, where actions like climbing uphill versus moving down- hill incur distinctly different penalties, or tran- sitions may become irreversible. While recent quasimetric RL. methods relax symmetry assump- tions, they typically do not explicitly account for path-dependent costs provide rigorous safety guarantees. We introduce Quasi-Potentes Rein- forcement Learning (QPRL), novel framework that explicitly decomposes asymmetric traversal costs into a path-independent potential function (b) and path-dependent residual (I)). This de- composition allows efficient learning and stable policy optimization via Lyapunov-basse safety mechanism. Theoretically, prove that QPRL achieves convergence with improved sample com- plexity of (vT)), surpassing prior quasimetric RL bounds of Ö(T). Empirically, our experi- ments demonstrate that QPRL attains state-of-the- art performance across various navigation and control tasks, significantly reducing irreversible constraint violations by approximately 4x com- pared to baselines.
82
Downhill: c(32 81)
Figure 1. Asymmetric traversal costs hetween states and 82- The uphill traversal from 81 82 incurs a higher cost of 5, repre- sented by the solid orange arrow, whereas the downhill traversal from $2 to S1 incurs a lower cost of 1, shown by the dashed teal arrow. This visualization highlights the direction-dependeen asym- metry, emphasizing QPRL's ability to learn traversal paths under asymmetric costs.
after one traversal actions have irreversible or direction- dependent costs (Fig. 1). In such environments, the cost of moving from one state to another may differ based on direction wath-dependence, a challenge that remains derexplored in the RL literature (Eysenbach et al., 2019b), Traditional RL algorithms, in practice, often overlook asym- metric or irreversible dynamics, treating costs as if they were symmetric. This can lead to suboptimal policies in environments with one-way transitions.
Project Page: http::/pralgomaahiigggtbbbbiiii
1. Introduction
Existing work has introduced the concept of quasimetrics relax the symmetry requirement in modeling traversal costs (Wang et al., 2023). Quasimetrics allow for more accurate representations of environments where directionality mat- ters, such as uphill and downhill navigation or irreversible state transitions (Valieva Banerjee, 2024). While recent advances in quasimetric learning have shown promise in goal-reaching tasks (Eysenbach al., 2019b; Park et al., 2023), these approaches largely focus estimating value functions without fully considering the cumulative, path- dependent traversal costs that arise in long-term planning scenarios (Valieva & Banerjee, 2024). QuasiNav (Hossain et al., 2025b) applied quasimetric RL to navigation, show- ing that modeling uphill vs. downhill costs leads to safer
Reinforcement Learning (RL) has shown great success in solving sequential decision-making tasks, from robotic con- trol autonomous navigation (Sutton Barto, 2018; Silver al., 2016). In many real-world scenarios for example, robot traversing terrain where uphill moves consume more energy than downhill, or path that becomes inaccessible
'Department of Information Systems, University of Maryland, Baltimore County, USA. Correspondence to: Jumman Hossain <jumman. hossain @ umb..edu>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Quasi-Potential Reinforcement Learning (QPRL)
paths. However, QuasiNav did not incorporate formal safety guarantee and primarily addressed cost asymmetry in planning context.
Φ- constraints through Lagrange multipliers, ensur- ing quasimetric properties and robustly avoiding irre- versible states.
In this paper, we propose Quasi-Potentie Reinforcement Learning (QPRL), extending quasimetric approaches by explicitly decomposing asymmetric traversal costs into a muthinddeendeet potential (I) and a path-dependent resid- ual (L) This decomposition is intuitive; the potential (+) represents reusable energy cost, analogous to gravita- tional potential in navigation tasks, while the residual (V) captures additional irreversible or dissipative costs, such as friction or single-use resources. Unlike conventional value functions, which often overlook path sath-dependency, our quasi-potential explicitly modeling the path-dependent and directional nature of real-world environments (Wang al., 2023).
Extensive Empirical Validation: We conduct compre- hensive empirical evaluations across a range of chal- lenging environments with asymmetric traversal costs, showing that QPRL significantly outperforms state-of- the-art methods in terms of sample efficiency, asym- metric cost handling, and overall performance.
2. Related Work
Reinforcement Learning (RL) has traditionally focused on optimizing policies under symmetric traversal assumptions, limiting its applicability in environments with inherently asymmetric dynamics. Recent advancements have intro- duced frameworks like quasimetric learning to model traver- sal asymmetry effectively (Wang al., 2023). Quasimetrics (Wang & Isola, 2022b;a) extend traditional metrics by al- lowing for non-symmetric distance calculations, which are particularly crucial in scenarios where traversal costs vary based on directionality or path-dependent factors (Silver et al., 2016). Existing research has made significant progress in applying quasimetric models for goal-reaching tasks. No- tably, (Eysenbach et al., 2019a) introduced diversity-driven skill learning, emphasizing the decomposition of skill leam- ing, exploration, and planning, which set a strong foundation for handling asymmetric and complex dynamics. Similarly, (Eysenbach et al., 2022) leveraged contrastive learning prin- ciples to improve generalization in goal-conditioned RL. However, these approaches largely focus on estimating value functions without fully considering the cumulative, path- dependent traversal costs required in long-term planning scenarios.
Our framework is grounded in rigorous theoretical founda- tions. We derive convergence guarantees for quasi-potential functions (Wiewiora, 2003; Devlin & Kudenko, 2012) us- ing a modified Bellman operator and establish PAC-MDP bounds for sample efficiency (Dann et al., 2017; Jin al., 2020; Wang al., 2020), similar existing theoretical anal- yses in goal-reaching RL (Gong et al., 2024; Palan et al., 2019). Additionally, we provide a L.yapunov-basee stability analysis that ensures constraint satisfaction during explo- ration, drawing inspiration from stability analyses in safe RL (Achiam et al., 2017; Chow et al., 2018). This theoreti- cal foundation allows QPRL to optimize exploration while maintaining safety constraints, critical requirement in dy- namic, asymmetric environments (Thomas et al., 2023).
Our main contributions: We propose Quasi-Potential Re- inforcement Learning (QPRL), with the following advances;
Quasi-potential decomposition: A novel quasimet- ric decomposition d(s,g) = (g)) (ss) + (s + g). separating path-independent potential & and path- dependent residual w. This generalizes prior quasimet- ric RL. (Wang et al., 2023) and enables interpretable modeling of irreversible transitions.
Recent advances in safe reinforcement learning have also highlighted the importance of stability during explo- ration, especially in dynamic, asymmetric environments. Lyapunov-bases based safety analysis (Lobo et al., 2024; Chow et al., 2018) has been proposed ensure that policies derived from quasi-potential functions maintain safety constraints during exploration (Chow et al., 2018). These methods ensure robust learning, especially in environments characterized by high variability and traversal asymmetries. Inspired by these approaches, QPRL incor- porates a Lyapunov-based based recovery mechanism to provide stability guarantees during exploration, contributing to both safety and performance in complex environments.
effective means to
Theoretical and empirical advances: We prove a faster convergence rate for QPRL (improving sample complexity from linear to Õ(VT) and demonstrate state-of-the-aad performance on tasks with irreversible dynamics, with significantly fewer constraint viola- tions (4x reduction) than baselines.
Lyapunov Safety Mechanism and Algorithmic De- sign: We incorporate I. Lyapunov- -based safety layer (Perkins & Barto, 2002) that monitors and restricts the policy to avoid irreversible unsafe transitions. Specifi- cally, our policy optimization algorithm (Algorithm 1) incorporates anfety-by-destte principles by enforcing
The idea of leveraging potential functions (Jeon et al., 2023) to modify the reward structure and accelerate learning is well established in RL literature. For instance, potential- based reward shaping, as presented by Ng et al. (Ng et al., 1999), has shown how modifying rewards through poten-
2

---

Quasi-Potential Reinforcement Learning (QPRL)
tial functions preserves the optimal policy while improv- ing learning speed. Wiewiora et al. (Wiewiora et al., 2003) fürther developed principled methods for advising re- inforcement learning agents using potential functions. More recently, Okudo and Yamada (Okudo & Yamada, 2023) demonstrated the effectiveness of learning subgoals using potential- reward shaping long-horizon tasks.
costs. QPRL addresses this via decomposition:
d(s,g) +(g) ((s) + V 9))
(1)
Path Independentt
Dependent
where:
+ S - R is state potential (e.g., elevation in navigation).
This paper extends the quasimetric learning paradigm by introducing QPRL, which explicitly models path-dependent traversal costs with quasi-potential functions. Unlike tra- ditional value-based RL methods (Haarnoja et al., 2018: Lillicrap. 2015), which often struggle in environments with directional cost disparities, our approach designed to opti- mize long-term cost efficiency under asymmetric dynamies. The experimental results demonstrate QPRL's superior per- formance across multiple benchmarks compared to both standard baselines like DDPG + HER (Andrychowicz et al., 2017) and recent state-of-the aart approach Quasimetric Re- inforcement Learning (QRL) (Wang et al., 2023).
v S x S 7 R20 models irreversible costs (e.g., energy for uphill traversal).
3.2. Theoretical Challenges in Quasimetric MDPs
Extending reinforcement learning quasimetric MDPs in- troduces two fundamental challenges absent in symmetric settings:
Asymmetric Bellman Contraction: The standard Bellman operator T, defined as:
(s)
min (P' (C(s,,,s') [C(,,a,))+ aad
3. Background
loses its contraction property under quasimetrics.
3.1. Quasimetric Spaces for Asymmetric RL
Specifically, T is contractive only if:
Consider a Markov Decision Process (MDP) with asym- metric costs, defined by the tuple
d(s, 8²) d(ss'ss)) <000
sup sfss
7), where C S x A S + IR is cost function satisfying C(s,a, a.aa 8') # C(s',a', s) for some transitions. The ob- jective is to learn a policy π :: S + A(A) minimizing:
d(s,8')
where d(s, the quasimetric. This condition fails in real-world tasks with irreversible transitions (e.g.. robotic hardware degradation).
((T) = E Σ
CC(s, a,, s(+1)
s(t1)
Non-Markovian Reward Attribution: Path- dependent costs V/(s - 8') violate the Markov
property, rendering traditional dynamic programming inapplicable. Specifically, the optimality condition:
Traditional RL methods (Sutton & Barto, 2018) struggle in such settings due to their implicit assumption of sym- metric dynamics. A quasimetric space (S, d) provides the mathematical foundation for modeling direction-dependent traversal costs. Formally, a quasimetric is a function d: x Rz0 satisfying:
(s; g) min Eg [C(s, a, s') + +
no longer holds when C(s, a, s') depends on historical state transitions.
Our framework addresses these challenges via:
1. Non-negativity: d(s, 20200 Vs,
Stable Policy Updates: By decomposing d(s, g) = ((g) - (s)) + ( - g). QPRI. ensures the Bellman operator contracts to a unique fixed point even under unbounded asymmetry (Theorem 4.1).
2. Identity: d(s,8) 0 VsES,
3. Triangle Inequality: d(s,s") S d(s,s))
d(s', Vs, 8" S.
Decoupled Cost Modeling: Path-dependent costs V/s s') are learned separately from path- independent potentials ((s), enabling dynamic pro- gramming through the modified Bellman equation:
Unlike metrics, quasimetrics do not require symmetry (d(s, 8') * d(s',s)), making them ideal for asymmetric RL.
( + g) = min E.r [C(s, 8') + Vi's' + g)]
QPRL's Quasimetric Structure Prior quasimetric RL methods (Wang et al., 2023) learn a monolithic d(s, g) but fail distinguish path-dependent and path-independent
This isolates non- non-Markovian dynamics, preserving con- vergence guarantees (Lemma 4.2).
3

---

Quasi-Potential Reinforcement Learning (QPRL)
3.3. Potential Functions and Safety
QPRL. introduces structured decomposition:
Potential functions Φ + IR have been used in RL for reward shaping (Ng et al., 1999), but existing methods assume symmetry. QPRL reinterprets & as Lyapunov function enforcing:
d(s,g) +(g)
(())
+
V -
Pall-Independent
Path- Gath-Dependent
where:
Eg 1x < V(8) +e,
S R state potential capturing reversible costs (e.g., gravitational potential in navigation).
where 6 > 0 bounds allowable risk. This ensures recover- ability from unsafe states, a novel extension of potential- based methods asymmetric settings.
: S S Ryo models irreversible residual costs (e.g., energy expenditure for uphill traversal).
3.4. Relationship Value Functions
This decomposition enables interpretable cost attribution: i encodes global state values, while y captures action- specific penalties. For instance, in terrain traversal task, (s)) could correspond to an estimated elevation potential of state s, while V(s, ú, 8') captures additional cost due to the specific move (like slippage or one-time obstacles).
For goal g. the optimal value function V (* g) relates to the quasimetric as V (s: g) d(s,g)) QPRL extends this via:
V (s;g) = (g) (s) + (s - g)),
enabling Bellman equation that accounts for path depen- dence:
4.2. Learning Framework
State Representation Learning A state encoder fo S + Z maps high-dimensional states latent space 2, reducing dimensionality while preserving critical fea- tures. A transition model Tw. Z A + Z predicts the next latent state 2':
(is -) min E,, [C(s,a, (ss - g]]
This decouples reversible (④) and irreversible (V) costs, differing significantly from prior quasimetric RL. We rep- resent the asymmetric cost of transition c(s,a,,s) ((s) - (s') + (s, a, s'), where is learnable poten- tial function and V is the residual that accounts for non- conservative (path-dependent) cost.
1' = Tobzaa,) where fø(s).
The encoder and transition model are trained jointly via:
LT (,,,,,, ([T)()(()) -
ensuring accurate latent dynamics for downstream planning.
QRL
QPRL (Ours)
Sufe Region V(s) s
Quasi-Potential Function Learning The quasi-potential function d(s,g) g) is trained reconstruct observed costs c(s g):
=(5))=
((x,) 5
d(si, 5x) -5
(5: -> 5.)
S1
$2
$1
$2
d(s2, =;)=1
(ss - 51)
Lu (s ( ((s) - -
-)))
d(s). 5z) (1s)) 0(s) + (s)
To enforce quasimetric axioms, we impose constraints:
Figure QPRL vs. QRL: QRL uses a monolithic quasimetric d(s1. #2). QPRI. decomposes costs into & (state potentials) and (path residuals), enabling Lyapunov-stable exploration (green region).
Non-Negativity:
( + s') 2 max (0, 8') - (0(s') (())))
Triangle Inequality: V s") s ((s - 8) + (iss' + s").
4. Methodology
These implemented via penalty term:
4.1. Quasi-Potential Decomposition
Traditional quasimetric RL methods model asymmetric costs with a monolithic function d(s,g) conflating path- dependent and path- -ndeinndeeendnnt dynamics. To address this,
Leonstraint E( ReLLU (T((s + -s)
(3)
-(c(s + - (3))((((s')) ((((s'))(ss))))
(4)

---

Quasi-Potential Reinforcement Learning (QPRL)
4.3. Safe Exploration via Lyapunov Stability
Algorithm 1 Quasi-Potential Reinforcement Learning (QPRL)
To prevent irreversible transitions, we treat & a Lyapunov function (s)) (s)), enforcing:
Input: Replay buffer D, learning rates Cigy Cipy 0g,, Ows threshold e
E (-)) [s))) S V(s) +,,
2: for iteration = 1 to N do
3: Sample batch [ss; a, s/: Ca ) D
where e > 0 bounds allowable risk. This is achieved by projecting policy updates into safe regions (Fig. 3):
4: Update Encoder & Transition Model:
5:
2, = fo(s.), 24 = (2..
C = B E. 11 {
safe (a s) = arg min Banx [d(s, 9)1
Update Φ, 1 using V V.r
8:
Update Quasi-
Function:
s.t. Eg (0(s)) & ((s) +
(5)
9:
LU B L. (Po(g.) Dg(s:)
10:
+Mo0s8 + gi) -c,) c)2²
Following the (Achiam et al., 2017: Chow et al., 2018), we solve (5) with primal-dual update. simple scalar penalty may discourage but cannot prevent unsafe actions.
11:
Comnttrintt = E, (max (0.
12:
Vols: + $ (c: - Po(s,) + fo(s)))))
In contrast, the Lyapunov condition preserves the contrac- tion of the asymmetric Bellman operator (Theorem 4.1) and, by Lemma 4.2, provably bounds the probability of enter-
13:
Update using VolLu: + Acccomttrii)
14:
Update Policy with Safety Layer:
15:
2j fa(si), as = Tu (st,
ing inreversible states. Empirically (Sec. 6.6) disabling the I Lypunov layer increases constraint violations by approxi- mately 4x.
16:
2 Te(zi, az)
17:
d = (b())) -Do(s;) + Vo(s: - gs)
18:
Cx = E,d,
19:
+A max (0, (2()) (x,))) -c)
20: Update w using WuLr
Safety Laver
V(* S
21:
end for
Cestmate
Our policy update explicitly ensures that the selected action satisfies a safety constraint based on the learned potential function Dg. We require that the expected potential of the subsequent state does not exceed the current potential by more than small threshold e >> O:
Preintial ox(A)
(lig) 01A.
Sah Expleraion
Envircemenn (x.s.r)
State
Encoder Sala]
Labve
Transiionn Tule.a)
Resdial Quls g)
Eere(()la.)) [Po(s'] S DD(() +
(6)
Policy (A(r)e))
After encoding the current state s into latent representation
z (s)), the policy (s. g) selects an action a. The tran- sition model then predicts the next latent state ś' = To a), from which estimate the subsequent state's potential (3'). The policy loss incorporates safety penalty enforc- ing this constraint:
Figure 3. QPRL Framework: Decomposes asymmetric costs into path-indepente inhheeeddenddn potential and aath-dependen residual v. Inte- grates Lyapunov safety constraints (yellow) for stable exploration.
B
4.4. QPRL Algorithm
L.
Σ
d + ARLU (Do(E) - Dal(s) - {))
B
In Algorithm 1, the encoder fo and transition model To learn a compressed state representation and dynamics model, critical for efficient planning in high-dimensional spaces. The quasi-potential function is trained to reconstruct costs while satisfying quasimetric constraints. The term Cconstraiot ensures V captures only residuals beyond 4 preserving non- negativity and triangle inequality. The policy tw minimizes the expected quasimetric cost d(s, g), with a penalty term enforcing Lyapumov safety. This ensures actions do not lead to states where & (ss)) > ((s) + e, preventing irreversible transitions.
(7)
where the quasi-potential cost is defined
d ( ()()s) + Vo(s. 9:),
(8)
and À is a dynamically adjusted Lagrange multiplier: This penalty term effectively projects policy updates onto the safe set:
Taat s) = TTa |s) subject to
E [[ < Do(s)
(9)
5

---

Quasi-Potential Reinforcement Learning (QPRL)
The dual ascent method dynamically tunes À throughout training, ensuring adherence the Lyapunov safety con- straint across all iterations. Algorithm I and Fig. 3 detail these explicit steps, including parameter initialization, latent encoding, and the policy and Lagrange multiplier updates.
of while moving downhill costs 0.5. The agent navigates obstacles to reach the goal at the opposite corner.
MountainCar (Modified): The classic MountainCar problem is modified with asymmetric costs, where moving uphill incurs penalty o and downhill costs -0.1. The agent must balance speed and energy effi- ciency.
4.5. Theoretical Guarantees
Theorem 4.1 (Convergence). Under Lipschitz continuity of and V, QPRL converges to a policy with (vVT) regret, improving over the (TT) bound of monolithic quasimetric RL.
FetchPush (Asymmetric): A modified FetchPush- vI environment where pushing objects uphill requires more energy than moving downhill, simulating real- world manipulation challenges.
Lemma 4.2 (Lyapunov Safety). The policy safe ensures [[{(s++1)] & ((s)) cor all t, guaranteeing recoverabil- ity from e-bounded unsafe states.
LunarLander-v2 (Asymmetric): A continuous con- trol task where upward thrust incurs higher fuel costs than lateral movement. The agent learns to land effi- ciently while considering asymmetric fuel consump- tion.
Proof. See the appendix for proofs of Theorem 4.1 and Lemma 4.2.
5. Experimental Evaluation
These environments test QPRL's ability to exploit low-cost traversal paths in the presence of asymmetries. An example of agent's movement illustrated in Fig. 4.
In this section, we empirically evaluate QPRI. in environ- ments designed to challenge agents with asymmetric traver- sal costs.
5.2. Baselines
G
We compare QPRL to the following state-of-the-art base- lines, focusing on their handling of goal-reaching tasks with asymmetric traversal costs:
2
QRL (Quasimetric Reinforcement Learning) (Wang al., 2023): Directly comparable to QPRL, QRL uses quasimetric models for goal-reaching tasks, making it an ideal baseline.
0.5
DDPG+HER (Lillicrap, 2015; Andrychowicz et al., 2017): Deep Deterministic Policy Gradient with Hind- sight Experience Replay, effective for sparse rewards but lacking specific asymmetric handling.
SAC+HER (Haarnoja et al., 2018; Andrychowicz et al., 2017): Soft Actor-Critie with Hindsight Experi- ence Replay, a robust algorithm for continuous control tasks but without explicit mechanisms for asymmetric costs.
Figure Illustration of an Asymmetric GridWorld environ- ment designed to demonstrate QPRL's effectiveness in handling direetion-dependeett costs. The agent (red) begins at must reach G while avoiding walls. Horizontal moves cost 1, climbing upward costs 2, and descending costs 0.5 (blue arrows with labels).
Contrastive RL (Eysenbach et al., 2022): A con- trastive learning approach for goal-conditioned RL, useful for general navigation but lacking explicit asym- metric cost management.
5.1. Environments
We evaluate QPRL in enviromments that exhibit significant asymmetries traversal costs, emphasizing the need for optimal path planning:
5.3. Implementation Details
Our QPRL is implemented as a quasimetric model, adhering to the foundational principles of quasimetric learning for goal-reaching tasks.
Asymmetric GridWorld: A 20x20 grid with direction- dependent traversal costs. Moving uphill incurs cost
6

---

Quasi-Potential Reinforcement Learning (QPRL)
Environment
Metric
QPRL (Ours)
QRL
Contrastive RL
DDPG+HER
SAC+HER
Asymmetric GridWorld
Success Rate (%)
92.5 + 2.2
87.3 = 3.0
82,4 3.5
:.2
80.3 -121.22 77.0
MountainCar
Normalized Return
-95.6 4.1
-108.4 + 6.7
-118.3 8.1
-125.5
FetchPush
Success Rate (%)
91.2 3.0
85.5 3.6
79.3 + 4.1
I Lunarl ander
Lunder.ander
Success Rate (%)
88.9 + 3.4
81.4 +
76.7 + 4.5
7
74.2 + 4.8
Maze2D
Success Rate (5)
85.3
+ 3.7
78.1 + 4.3
72.6 + 4.7
68.9 + 5.2
70.1 + 4,9
Table 1. Performance Comparison on Asymmetrie Environments
Enstroment Shaps (K1llond)
Ensimmmmnnt Stept lonci
Escmmmment Shept (Millene)
Enunnonment Stepe (Mil
Envirommnt Stape (Milloon]]
GPL Dbusi
Ouzandtii
DOPO HER
Figure Sample-efficincc and stability across tasks. Success rate learning curves for all five asymmetric environments. The x-axis shows environment interactions (in millions of steps); the y-axis shows mean success rate. Solid lines are the mean over 5 random seeds; shaded bands denote standard deviation. QPRL (blue) reaches high performance earliest and maintains highest asymptotic success with visibly lower variance.
5.3.1. NETWORK ARCHITECTURE
specting local traversal constraints. The loss function is formulated follows:
QPRL utilizes neural network architecture for approxi- mating the quasi-potential function Ug. The architecture consists of the following components:
((() = (()s))><Pnn (U((8, ())
+ X Be,,, o', ('ota,,"".ottt (ostt)-Prmmiiinn (ReL_U(U(ss,'')
-cost
State Encoder (fø): The state encoder maps states from the original state space S into a latent representa- tion in 6d It is implemented as a feedforward neural network comprising two fully connected layers, each followed by ReLU activations. The first layer maps the input state 128 hidden units, while the second layer projects it to the 64-dimensional latent space.
(10)
where À is the Lagrange multiplier that enforces adher- ence to the local cost constraints.
Optimization Algorithm: The model is optimized using the Adam optimizer, with learning rates 0g 10-4 for the quasi-potentic model and ax = 1003 for the Lagrange multiplier. The Adam optimizer is chosen for its adaptive learning rate capability, which well- suited for the sparse gradient scenarios encountered in reinforcement learning.
Quasimetric Head (U+):: The quasimetric head com- putes the quasi-potential between latent state repre- sentations. Given two states in the latent space, the quasimetric head consists of fully connected layers that ensure a non-negative output by applying ReLUU acti- vations. This design enforces the quasimetric property, particularly the triangle inequality, which is crucial for accurately capturing the directional traversal dynamics.
Training Schedule: Training conducted for a total of million timesteps. Evaluation performed every 10,000 timesteps using 100 test episodes to observe the progress of learning. During training, the agent interacts with the environment and collects experience to update the model parameters, gradually learning an optimal representation the asymmetric traversal landscape.
5.3.2. TRAINING PROCEDURE
The QPRL training procedure is tailored to learn the quasi- potential function while maintaining quasimetric properties across states:
Theoretical Properties: The quasi-potential function is constrained to a quasimetric by design. This ensures that the triangle incquality holds, which is vital for achieving optimal value function estimation
Objective Function: The training objective is to max- imize the expected potsnialtential Uo(s, g) while re-

---

Quasi-Potential Reinforcement Learning (QPRL)
in asymmetric environments. The theoretical guaran- tees presented in Theorem 1 asserting that quasimetric functions are suitable approximation class for value
asymmetry. QPRL consistently achieves higher success rates compared other methods, indicating its superior ability to leverage the underlying asymmetries for efficient exploration and exploitation. Notably, in the Asymmetric GridWorld, QPRI. achieves a success rate of 93.2% %, outper- forming QRL by approximately 6%.
functions in goal-reaching tasks.
5.4. Evaluation Metries
To evaluate the performance
Reinforce- ment Learning (QPRL), we consider the following metrics, specifically tailored to environments with asymmetric traver- sal dynamics:
6.2. Learning and Sample Efficiency
Figure 5 presents learning curves for QPRL and baseline methods across five environments: Asymmetric GridWorld, LunarLander, MountainCar, FetchPush, and Maze2D, The x- axis shows environment interactions (in millions), while the y-axis represents the success rate. QPRL. deRRonsemssssrtess faster convergence and higher stability compared to baselines across all environments. In LunarLander, QPRL achieves a 90% success rate within 250,000 steps, outperforming meth- ods like SAC+HER and DDPG+HER, which take longer and exhibit greater variability. In Asymmetric GridWorld and Maze2D, QPRL shows superior sample efficiency and robustness, maintaining high success rates with minimal fluctuations.
The proportion of episodes in which the agent successfully reaches the goal within a predeter- mined number of steps. This metric captures the over- all effectiveness of the learned policy in goal-reaching tasks.
Success Rate:
Traversal Cost Efficiency: The total traversal cost incurred by the agent during episode, normalized by the optimal traversal cost. This metric is particularly relevant for evaluating QPRL in environments with direction-dependent traversal costs.
Sample Efficiency: The number of environment inter- actions required for the agent to achieve 95% success rate. This metric is critical for understanding how quickly converges compared baseline meth- ods.
6.3. Traversal Cost Analysis
Figure 6 reports the average traversal cost efficiency across different environments. QPRL consistently achieves lower traversal costs compared to the baselines, underscoring its capability to optimize routes under asymmetric traversal dynamics. In the MountainCar environment, QPRL demon- strates a reduction of approximately % in traversal cost compared to QRI, showing its ability to exploit lower-cost traversal paths effectively.
Asymmetric Performance Gap: The difference in agent performance between symmetric and asymmetric versions of the same task. This metric helps quantify QPRL's ability to leverage asymmetric cost structures to improve goal-reaching performance.
The cumulative reward accumu- lated during an episode, normalized against an expert policy. This provides comparative measure of how effectively QPRL learns optimal policies relative to existing state-of-the-an baselines.
Normalized Return:
6.4. Performance Gap between Symmetric and Asymmetrie Tasks
Table 2 quantifies the performance gap between symmetric and asymmetric versions of the same task. QPRL demon- strates smaller performance gap compared to the baselines, indicating its robustness in environments with direction- dependent dynamics. This result emphasizes the importance of incorporating quasimetric properties into the learning process for handling asymmetry efficiently.
Each metric is computed over multiple evaluation episodes and averaged across five random seeds to ensure statistical significance and reduce the influence of variability in training.
6.5. Statistical Analysis
6. Results and Analysis
To confirm the robustness of the results, we conducted paired t-tests comparing QPRL against each baseline for all evaluation metrics. The results consistently yielded p- values less than 0.01, establishing statistical significance for QPRL's superior performance. Effect sizes (Cohen's d) ranged from 0.9 to 1.4, indicating substantial practical significance.
The empirical evaluation of QPRL demonstrates its effec- tiveness across variety of goal-ng tasks characterized by asymmetric traversal costs.
6.1. Performance in Asymmetric Environments
Table presents a comparative analysis of QPRL and the baselines in environments featuring significant traversal
8

---

Quasi-Potential Reinforcement Learning (QPRL)
Environment
Method
Symmetric (%)
Asymmetric (%)
Gap
Asymmetric GridWorld
QPRL
94.1 1.8
88.7 =
5.4
QRL
92.3 = 2.0
83.5 + 2.8
8.8
SAC HER
90.2 = 2.3
81.0 = 3.2
9.2
DDPG HER
89.8 2.5
80.5 + 3.5
9.3
MountainCar
QPRL
-90.5 4.3
-98.2
7.7
QRL
88.2 4.1
96.5 5.2
8.3
SAC + HER DDPG HER
87.0 - 4.0
95.8 + 5.3
8.8
86.5 + 4.2
94.5 + 5.1
8.0
FetchPush
QPRI. QRL
92.0 + 2.2
85.3 + 3.1
6.7
90.5 2.3
81.0 + 3.2
9.5
SAC HER DDPG HER
89.8 2.5
79.8
10.0
88.5 1 2.4
78.5 + 3.4
10.0
LunarLander
QPRL
88.6 3.4
82.4 + 3.7
6.2
QRL
87.0 + 3.5
80.0 + 4.0
7.0
SAC HER
85.5 = 3.8
77.5 = 4.2
8.0
DDPG HER
84.0 3.6
76.0
Table Performance on symmetric vs. asymmetric variants of each environment (mean 1: s.d. over 5 seeds). Gap (%) is the absolute difference between the settings- lower better, indicating robustness asymmetric traversal costs. Table presents results from our ablation studies, isolat- ing the impact of key components in QPRL. These results demonstrate the importance of the constrained optimiza- tion and quasimetric structure in QPRL's performance. The choice of & function also impacts performance but to lesser extent.
age Thateesel Conds activs towinumeents
6.6. Ablation Studies
0781
*i 0001
SAC + FER
ORL
60
DDPS HER
00
Aeeenge Thanesal
40
10
7. Conclusion
MountainCer
Asymmetiic
In this paper, we introduced Quasi-Potential Reinforcement Learning (QPRL), novel framework that extends rein- forcement learning to efficiently handle environments with asymmetric traversal costs. The experimental results clearly demonstrate that QPRL able to effectively capture and ex- ploit asymmetries traversal dynamics, leading to superior performance in goal-reaching tasks compared to state-of- the-art baselines. QPRL's faster convergence and lower traversal costs make it particularly suitable for real-world applications where sample efficiency and cost-efficctiveness are critical. In future work, we aim to extend the QPRL framework to real-world applications (Hossain et al., 2023; 2024a), particularly in topological navigation and multi- agent systems. This includes integrating QPRL into topo- logical navigation frameworks (Hossain et al., 2024b) for efficient exploration in sparse-reward environments. Ad- ditionally, we plan to incorporate QPRL into multi-agent coordination systems (Hossain et al., 2025a) for real-time collaborative safe decision-making
Figure Average traversal cost across different environments QPRL and baseline methods. QPRL demonstrates significantly lower traversal costs due to its ability to exploit asymmetric traver- sal dynamics efficiently.
Method
Success Rate (%)
Full QPRL
(3.1)
QPRL w/o constraint
78.3 (5.7)
QPRL w/ metric (not quasimetric)
83.5 (4.2)
QPRI. w/ linear &
89.1 (3.8)
Table Ablation study results on FetchPush. Values represent success rates after I million steps.

---

Quasi-Potential Reinforcement Learning (QPRL)
Acknowledgements
Devlin, S. M. and Kudenko, D. Dynamic potential-based reward shaping. In 1ith International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), Pp. 143-440. IFAAMAS, 2012.
This work has been partially supported by ONR Grant #N00014-23-I-2133 U.S. Army Grant #W91 WINIIN220000 U.S. Army Grant #W91 INF2410367. NSF REU Site Grant #2050999, NSF CNS EAGER Grant #2233879, and NSF CAREER Award #1750936.
Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations (ICLR), 2019a.
Impact Statement
This work advances the field of reinforcement learning (RI.) by introducing framework for learning optimal policies in environments with asymmetric traversal costs. Our primary contribution is theoretical and algorithmic, focusing im- proving sample efficiency and safety in goal-reaching tasks. While the immediate impact of this work is to advance the theoretical understanding of RI in asymmetric settings, we acknowledge potential broader implications:
Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. Learning robust options by balancing skill learning, exploration, and planning. In International Conference on Learning Representations (ICLR), 2019b.
Eysenbach, B., Zhang, T., Levine, S., and Salakhutdinov, R. R. Contrastive learning as goal-conditioned reinforce- ment learning. Advances in Neural Information Process- ing Systems, 55:35603-35622 2022.
Our framework, Quasi-Potential Reinforcement Learning (QPRL., could enable safer and more efficient decision- making in real-world applications such as robotics, where irreversible actions (e.g.. hardware wear) are common. By explicitly modeling path-dependent costs, QPRI. provides a principled approach to handling irreversible dynamics, which could lead to more sustainable and ethical resource management.
Gong, X., Dawei, F., Xu, K., Ding, B., and Wang, H. Goal-conditioned on on-policy reinforcement learning. Ad- vances neural information processing systems, 37: 45975-46001, 2024.
Haarojja, T., Zhou, A., Abbeel, P., and Levine, Soft actor-critic: Off-policy maximum entropy deep reinforce- ment learning with a stochastic actor. In International conference on machine learning, pp. 1861-1870. PMLR, 2018.
As with all RL methods, biases in the training data cost functions could lead to unsafe or unfair policies. We empha- size the importance of rigorous testing and fairness audits before deploying QPRL in real-world systems. Additionally, the use of Lyapunov-base based safety constraints in QPRL pro- vides a mechanism for ensuring recoverability from unsafe states, which could mitigate risks in high-stakes applica- tions.
Hossain, J., Faridee, A.-Z., Roy, N., Basak, A., and Asher, D. E. Covernav: Cover following navigation planning in unstructured outdoor environment with deep reinforce- ment learning. In 2023 IEEE International Conference on Autonomic Computing and Self- Self-Organizing Systems (ACSOS), pp. 132- IEEE, 2023.
References
Hossain, J., Faridee, A.-Z., Roy, N., Asher, D. E.,, Freeman, J., Gregory, T., and Trout, T. Encomp: Enhanced covert maneuver planning with adaptive target-aware visibility estimation using offline reinforcement learning. In 2024 IEEE International Conference on Autonomic Computing and Self- Oriaaiigggi Systems (ACSOS), pp. 51-60. IEEE, 2024a.
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In International Conference on Ma- chine Learning (ICML), pp. 22-31. PMLR, 2017.
Andrychowiez, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Pieter Abbeel, O., and Zaremba, W. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Hossain, J., Faridee, A.-Z., Roy, N., Freeman, J., Gregory, T., and Trout, T. ToopoNv: topological navigation for efficient exploration in sparse reward environments. In 2024 IEEE/RS. International Conference Intelligent Robots and Systems (IROS), pp. 693-700. IEEE, 2024b.
Chow, Y., Nachum, O., Duenez-Guzman, E., and Ghavamzadeh, M. Lyapunov-based safe policy optimiza- tion for continuous control. In International Conference on Learning Representations (ICLR), 2018
Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Hossain, J., Dey, E., Chugh, S., Ahmed, M., Anwar, M. S., Faridee, A., Hoppes, J., Trout, T., Basak, A., Chowd- hury. R. Mistry, R., Kim, H., Freeman, J., Suri, N., Raglin, A., Busart, C., Gregory, T., Ravi, A., and Roy, N.
10

---

Quasi-Potential Reinforcement Learning (QPRL)
SERN: simulation-enhanced realistic navigation for multi- agent robotic systems in contested environments, 2025a. URL atttp::/aaxiiis org/ /410 166866
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Thomas, P., Baturone, I., and Hernandez-Leal, P. Safe explo- ration in reinforcement learning: A survey. In Proceed- ings of the 40th International Conference on Machine Learning (ICML., 2023.
Hossain, J., Faridee, A.-Z., Asher, D., Freeman, J., Trout, T., Gregory, T., and Roy, N. QuasiNav: learning opti- mal policies with quasi-potential functions for asymmet- ric traversal. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2025b.
Valieva, K. and Banerjee, B. Quasimetric value functions with dense rewards. arXiv preprint arXiv:2409.087) 087244 2024.
Jeon, S.-H., Heim, S., Khazoom, C., and Kim, S. Bench- marking potential based rewards for learning humanoid locomotion. In 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023. doi: 10.1 109/ arra4889120023. 2003990111222..11185555
Wang, R., Du, S. S., Yang, L., and Salakhutdinov, R. R. On reward- reinforcement learning with linear function approximation. Advances in neural information process- ing systems, 33:17816-17826 2020.
Wang, T. and Isola, P. Improved representation of asymmet- rical distances with interval quasimetric embeddings. In Workshop on Symmetry and Geometry in Neural Repre- sentations (NeurReps) Conference on Neural Informa- tion Processing Systems (NeurIPS), 2022a. Proceedings Track.
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. Reward-free exploration for reinforcement learning. In International Conference Machine Learning, pp. 4870- 4879. PMLR, 2020.
Lillicrap, T. Continuous control with deep reinforcement learning, arXiv preprini arXiv: urXiv::509.022 1509.02971 2015.
Wang, T. and Isola, On the learning and learnability of quasimetrics. In International Conference on Learning Representations, 2022b.
Lobo, F., Hristu, P., and Sun, Critic as Yyapunov fune- tion (calf): A model-free, stability agent. arXiv preprint 209.9990. 2024.
Wang, T., Torralba, A., Isola, P., and Zhang, A. Opti- mal goal-reaching reinforcement learning via quasimetric learning. In International Conference on Machine Learn- ing. pp. 3641 1 1-34400. PMLR, 2023.
Ng, A. Y., Harada, D., and Russell, S. J. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the Sixteenth Inter- national Conference on Machine Learning (ICML), pp- 278 287, 1999.
Wiewiora, E. Potential-based shaping and q-value initial- ization are equivalent. Journal of Artificial Intelligence Research, 19:205 208, 2003.
Okudo, T. and Yamada, S. Learning potential in subgoal- based reward shaping. IEEE Access, 11:17116-17177, 2023. doi: 10.1 20110//ccess..02333444444
Wiewiora, E., Cottrell, G. W., and Elkan, C. Principled methods for advising reinforcement learning agents. In Proceedings of the 20th International Conference on Ma- chine Learning (ICML-03), pp. 792-799, 2003.
Palan, M., Shevehuk, G., Charles Landolfi, N., and Sadigh, D. Learning reward functions by integrating human demonstrations and preferences. In Robotics: Science and Systems, 2019.
Park, S., Ghosh, D., Eysenbach, B., and Levine, S. Hiql: Offline condiiond rl with latent states as actions. Advances in Neural Information Processing Systems, 36: 34866 -38916 2023.
Perkins, T. J. and Barto, A. G. Lyapunov design for safe reinforcement learning. Journal of Machine Learning Research, 3(Dec):803-83, 2002.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587))448 489, 2016.

---

Quasi-Potential Reinforcement Learning (QPRL)
Appendix
2. Contrastive penalty. A contrastive term encourages IIfa(s') - To (f)()))) |I to be small for the true suc- cessor state but large for randomly drawn negatives, penalizing any embedding that maps all states to a single point.
A. Additional Background and Discussion
A.I. Symmetric vs. Asymmetric Cost Assumptions:
In many navigation and planning contexts, symmetric cost implies that the effort or cost to traverse from state s to g is equivalent that from 9 back to 8. Traditional RL algorithms can handle arbitrary cost functions in principle; however, they often rely on heuristics or shaping rewards that assume an underlying symmetric structure ge.g., using Euclidean distance to goal as a potential-based reward shap- ing). This assumption breaks down in environments with ir- reversible or prrection-dependeer costs. For example, climb- ing up hill vs. going down may have drastically different energy costs, yet a symmetric distance heuristic would treat them as equal. Our QPRL framework relaxes this assump- tion by learning a quasimetric that allows d(s. g) * d(g,s) s). In other words, we do not require the cost of forward and reverse transitions to be the same.
Regularization & monitoring. We apply stan- dard weight decay and track the reconstruction loss (+)) (fa(s), a) each epoch. A sudden plateau very low value indicates collapse; in that case, we early-terminate the run or adjust hyperparameters.
B. Reward Functions
In our approach, we leverage customized reward functions to model the challenges of asymmetric traversal, sparse rewards, and goal-reaching tasks. Each environment utilizes reward structures that effectively capture the asymmetries present in the system, encouraging efficient policy learning. Below are the reward functions applied across different environments:
A.2. Decomposition d(s.g) = (g) (()) + (s - g):
The agent incurs a negative reward equivalent to the traversal cost for each move. Specifically, moving uphill results in a penalty of -5, while moving downhill incurs a smaller penalty of -1. This reward structure emphasizes the importance of minimizing high-cost traversals and encourages the agent to seek more efficient paths.
Asymmetric GridWorld:
This equation defines the learned quasi-potential distance between any state s and goal as having two components: (1) potential difference ((g) (s). and (2) an extra path- dependent term (s - g). Intuitively, (zz) can be seen as learned "height" or potential at state (independent of any specific path), while ( + g) captures irreversible costs incurred along the particular path from s to g (violations of symmetry). If the environment were fully reversible (no asymmetric costs), one could choose V = 0 and d(s, g) re- duces to (gg) - (s)), a standard potential-based difference. In general asymmetric environments, however, such a pure potential cannot exist globally- V is necessary to account for the non-conservative part of the cost. By decompos- ing the distance function this way, our approach improves upon prior quasimetric RL (QRL) methods, which did not explicitly separate conservative and non non-conservative cost components.
MountainCar-v0: We modify the traditional sparse reward structure to incorporate asymmetric costs for movement. Accelerating uphill costs 11, while ac- celerating downhill costs -0.1. The agent receives a reward of +1 only upon reaching the goal. This asymmetry helps guide the agent towards maximizing momentum and minimizing energy expenditure during ascent.
FetchPush-vi, FetchSlide-vl: In these robotic ma- nipulation environments, we apply a potential-based reward shaping approach, where the agent receives a negative reward proportional to the distance to the goal. Additionally, penalties are increased for moves that involve direction changes associated with high-cost ter- rain, while successful goal geal-iee is rewarded with +10. This setup incentivizes efficient movement plan- ning and direct paths towards the goal.
A.3. Preventing Representation Collapse
Representation collapse, where the encoder maps every state to the same latent vector, is a common failure mode when training latent dynamics models. We employ three comple- mentary strategy to avoid collapse in QPRL:
1. Replay diversity. We aggregate data from multiple exploration seeds so the replay buffer contains tran- sitions covering a wide range of states. A constant (collapsed) embedding would yield high reconstruc- tion error across such varied samples, making collapse suboptimal.
The reward function is adjusted to reflect asymmetry in thrust costs. Upward thrust in- curs a higher penalty (-3 per unit of fuel) compared to horizontal thrust (-1 per unit). Successfully landing on the target pad provides a reward of +100, while crashing results in reward of -100. The asymmetry
LunarLander-y
12

---

Quasi-Potential Reinforcement Learning (QPRL)
reflects realistic scenarios where vertical fuel consump- tion is more expensive, encouraging optimized usage
of thrust.
(TU))(() (TTU)()))TUU))))
min aEA
(c(s, B(Ui
min
aEA
Maze Navigation (Procedural Maze): A sparse re- ward setting where the agent receives +1 only upon reaching the goal. Traversal penalties are applied de- pending on terrain diffieulty, with higher penalties for uphill movement or traversing through rough ter- rain (-2) versus moving flat ground (-0.5). This helps the agent focus on avoiding difficult areas unless strictly necessary.
-
B [Us (s') [2(''11
< | U2|1oc
Taking the supremum over all states st
T T S || U2ll
Therefore, T is contraction mapping with factor 1. By the Banach Fixed-Point Theorem, I has a unique fixed point U and the sequence Un+1 = TU, converges to U as n 0c.
D4RL Maze2D Environments: In the offline settings, we follow a reward structure that combines distance- based rewards with asymmetric penalties for inefficient trajectories. Each step incurs small penalty of -0.1, while transitions that move away from the goal are penalized more heavily. Goal-reaching rewards are standardized across all maze environments to ensure comparability.
C.2. Theorem: Sample Complexity Bound
Theorem C.1 (PAC-MDP Sample Complexity Bound). The QPRL algorithm finds an e-optimal policy with probability at least 1 - using O IS |A] is the desired accuracy.
2 log( [S][Al)) samples, where e
These reward functions are designed to align with the core principles of Quasi-Potential Reinforcement Learn- ing (QPRL), where asymmetry in traversal costs plays crucial role in shaping optimal policies. By incorporating direction-depender penalties, we create incentive struc- ture that encourages the agent to exploit lower-cost routes, thereby learning more efficient and effective goal-reaching strategies.
Proof. Let n² be the optimal policy and R be the policy learned by QPRL after n samples.
Define the optimality error as:
Emr(# E(U)(s)) BB---BUU- (s)
Using Hoeffding's inequality, can bound the error in estimating transition probabilities:
C. Proofs
P([P(s'|ssa)) - P(s'(s, t) 2 2nt2
C.1. Theorem 4.1 Convergence
where P is the empirical estimate of P after samples. Similarly, for the cost function:
Proof. We prove convergence by showing that the Bellman operator T is contraction mapping in the sup-norm.
P((((s,a) - c(s, > 1) S 2e 2nr²
Define the Bellman operator 7 as:
Let E1 be the error in estimating P and eg be the error in estimating c. We require:
(TU)(s) min(c(s,a) + (ewr(haa( A
e1 S 4
and
S 2
Setting e₁ in the bound for P and E2 in the bound for and using the union bound over all state-action pairs, we get:
Consider two arbitrary quasi-potential functions Un and Uz- Let of and as be the actions that achieve the minimum for Uj and U2 respectively under T.
For any state S:
P(error > 2 - 2ne
2 -2ne
13

---

Quasi-Potential Reinforcement Learning (QPRL)
Setting this probability to 6 and solving for n,, we get:
D. Additional Theoretical Analysis
n = 0 100(5111 [ log( |
D.1. Optimality Learned Quasi-Potential Function
Theorem D.1 (Optimality of Learned Quasi-Potential Func-
tion). Let Ug be the quasi-por -otentiall function learned by QPRL at convergence. Then, for any states 8, S, have:
C.3. Lemma 4.2
Lyapunov Safety
(s g) = =
where (*(s:) g) is the true optimal value function for reach- ing goal g from state s.
Proof. Define Lyapunov function (s) that satisfies:
V(s) 2 for all S
Proof. To prove the optimality of the quasi-potential func- tion Ug. we proceed by contradiction. Suppose that the learned Už (8,9)) does match (s for some states and g.
V**)= 0 for all E Saate C S
(s) is continuous and differentiable
Let r be the policy derived from (*) Define the expected change in (s) under policy x:
Case 1: (3, < -V*(sgg) If (8,,9) is smaller than -v* it implies that U3 underestimates the cost to reach g from s. However, the optimization objective of QPRL involves maximizing Ug while respecting the con- straints set by the transition costs. Therefore, if U% (s, g) underestimates the true optimal cost, violates the opti- mization constraint since there exists a valid path with higher actual cost that Ug fails to represent accurately. This contradicts the convergence condition, as Up is expected to maximize its estimate while maintaining fidelity to the true traversal costs.
(v(s) E. (( [V({) ((s)
Consider the Taylor expansion of V(s') around s:
V(8) = V(s) + VV(s) 8) O(Iss' x112)
Taking the expectation:
(s)) = + (() - O =|(2))
The QPRL policy minimizes the quasi-potential U (s), which implies:
Case 2: U. (s, -V'(sssg)) If (s.g) is greater than (>;s)) -V* g). it implies that Up overestimates the cost of reaching g from s. In this case, Uğ is not optimal because the value could be reduced to better align with the true op- timal value function - (s; g). Since Už is result of a maximization objective, this overestimation indicates that there exists room to further optimize Ug. implying that the solution is not converged.
E (s) (s' -s)] (U) for some À >>> 0
Assume Vss) and (s) are related by a scaling factor
> 0:
V(s) = (s)
Then:
- })] aE (x) s)] E ( (s'-
Since both underestimation and overestimation lead to con- tradictions, conclude that the only feasible solution convergence is:
< -axu (s) = (sV
Substituting back into the equation for AV(())
(s < - (s) + [ =)
(g(8 - V (8:9)
for all states s,9 9 E S.
For sufficiently small state transitions, the second-order term can be bounded:
D.2. Consistency of Quasi-Potential Function
O - x111) - < A (s)
2
Lemma D.2 (Local Consistency of Quasi-Potentia Func-
tion). For any transition (s, a, s'.r) in the MDP, the learned quasi-potential function Un satisfies:
Therefore:
A AV(s) < - v(s)
Ug(s, s') 5 5-
Setting = X/2, we have shown that (s) < (n),ss, which guarantees Lyapunov stability under the QPRL policy.
The consistency of the quasi-potential function is enforced through the constraint in the QPRL. optimization
Proof.
14

---

Quasi-Potential Reinforcement Learning (QPRL)
objective. Specifically, have the constraint:
E. Convergence Analysis
E( -Pusssiiinn RReL s') =
Theorem E.1 (Convergence Rate). The QPRL algorithm converges to an e-optimal quasi quasi-potential function in ([log(L/e) iterations.
This implies that the penalty for violating the constraint should be minimal satisfy the bound e Consider the ReLU term:
Proof. Let Uj be the quasi potsi-pottntial function at iteration k, and let U* be the optimal quasi-potential function. We want to show that the error between UR. and U diminishes at rate proportional to log(1/e).
ReLU((U((s,)) + max(0, (s(s, s') +r)
(s, s') +r> 0, then the ReLU term contributes posi- tively to the objective, leading violation of the bound e². For the expectation to remain within this bound, it must be that:
Consider the update rule for Ug:
Us+1(5,9) = (x(s.g) - VVV
Us( + = Uo(5,5')
where is the learning rate, and L(Ux) represents the loss function to be minimized, incorporating both the quasi- potential objective and the constraint terms.
Thus, (s(s, 8¹) must be less than equal to the negative of the reward for the constraint to hold for almost all transitions (s, 0, 8 r)), establishing local consistency. D
We assume that the learning rate a is chosen such that ensures sufficient decrease in the loss at each iteration. Specifically, we have:
D.3. Generalization Bound
Theorem D.3 (Generalization Bound). Let Üig be the quasi- potential function learned from m ii.dd samples. Then, with probability at least - 8. all s.g g E S:
| - S | - ~0 -
where is the amount of improvement made towards the op- timal solution at each iteration. This implies exponential decrease in the error:
(8, to(s, so (
(og((1)10)) (108(11110) m
I 1 S (1- ac) ac) 10
where Uj is the true optimal quasi-potential function.
determine the number of iterations required to reach an e-optimal solution, we need:
Proof. We use statistical learning theory to derive the gen- eralization bound. Let F be the class of quasi-potentin functions that model can represent. By the properties of quasi- quasi-potential funetions, we know that the VC-dimension of F is at most S[SS] log (S]). This allows us to apply the standard VC-bound for uniform convergence.
(1 - ac > - U Se
Taking the logarithm of both sides:
log(e/1[Uo l7
Using the VC generalization bound, we have that with prob- ability least - 8, for all Up F:
log(1 aε)
( | (V
Using the approximation log(1 1)) - for small æ, we get:
SS log
sup s.9ES
g)1 s
k log -
k
To simplify this bound, note that for sufficiently small 6, we can approximate:
Thus, the QPRL algorithm converges c-optimal solu- tion in O iterations.
|S] log [S] + 1og(1/8) = Ollo(((S)/5)
Thus, we obtain the desired result:
F. Lemmas and Proofs
( 1og(((1/0)) m
Lemma F.1 (Monotonicity Quasi-PPtential Function). Let Ug be a quasi-potential function learned by QPRL. For any states 81, 82,9 g E S. if there exists path from 81 82 with non-negative cunulative cost, then:
sup [o(s, g) (o( - *.gES
This completes the proof, showing that as the number of samples m increases, the learned quasi-potential function converges to the true function with high probability.
Uo(81, g) U0(82,0)
15

---

Quasi-Potential Reinforcement Learning (QPRL)
Proof. Consider path p (81, 41, $1.-.., 1 :: On 82) from 82, where the cumulative cost of the path is non-negative. We need to show that Up(s1.g) (ø(52, g).
Part 2: U0(#2, g) (g( $1,91 9) S Ug($1, 82) Similarly, apply the triangle inequality, but starting from 822
U0 9) = 81) Ub($1,9)
The quasi-potential function Ug should satisfy a triangle inequality-like property along sequence states. For each segment along the path, the quasi-potential from a state to the goal must be at most the sum of the quasi-potentian along individual transitions.
Rearranging this yields:
Uo(52, g) (s()1.9) S (0(
Let us apply this property iteratively over the entire path p:
Note that (82, 81) might not equal U0($1; 82) due the asymmetry in traversal costs. However, by the constraints in the QPRL objective, we have that (s 81) S ( because the cost of traversing in the reverse direction is at least as high.
Uo(s1, 9) I Uo(s1, s() 9))
Uo($1,9) & Uo($1, 5/2) + Uo(552g)
Combining Both Inequalities we conclude:
Combining these two parts,
Uo(Kn-1,9) & Uo 82) + Uo (82.g)
Summing these inequalities, obtain:
(0>(s1. Us (52,, 1 80)
Ue(s1,9) I Σ Uo($(_1,5)) (s(
This completes the proof.
Lemma F.3 (Bellman-like Equation for Quasi-Potential
where 5i $1 and i' 52-
Functions). At optimality, the quasi-potential functtiol Uj
From the local consistency property of Ug. we know that for each transition (s, a, s',, r)) in the path, (s(s, s') < -r. Since the cumulative cost of the entire path is non-negative, follows that:
satisfies the following equation for all s. E S:
U (s, g) -min(-r(s,a) Be
aEA
where r(s, a) is the immediate reward for taking action a in state s.
Σ Uo($1_1.5)) 50
Proof. We proceed by contradiction. Assume that there exists a state-goal pair (s, g) E such that:
Thus:
(8( S 5 Uo(22, 9) (8()2.
U (s * min(-r(s, + Bv- aEA
This completes the proof, showing that the quasi-potential decreases (or remains constant) along any path with non- negative cost, hence proving the monotonicity property. O
Case 1: (z(s.g)
minoca(-r(s,a) +
Ee- (s' [ [)''))]}} If (s. is greater than the minimum value over all possible actions, then there exists an action a" such that:
Lemma F.2 (Bounded Difference Property). Let Ue be a quasi-poti puasi-potential function learned by QPRL. For any states 81, 82, 9 E S, have:
(8. > r(s,a)) + Es-P(s s. 1 (s'.')
[U((11.9) U0(82, g)l & Uo(s1, 82)
This means that the quasi quasi-potential Ug overestimates the ac- tual cost of reaching the goal g from state s by not choosing the optimal action a". Since U/ is obtained by minimizing over all possible paths, this violates the Bellman principle of optimality, leading contradiction.
Proof.
To prove this property, we need to show two inequal- ities:
Part 1: Up($1.9) g) (o(s2, 9) S 82) Using the triangle inequality property of the quasi-potential function:
mineea(-r(s,d) + Ex-r(e (U If (), is less than the minimum value, implies that the quasi-potential underes- timates the true expected cost. This would mean that Uβ is providing an infeasible solution that doesn't 't account for the
Case 2:
(z.)))
Uo($1.9) & U0(s1, s2) + (o(82.g)
Rearranging this expression gives:
Uo($1.9) Uo(82,g) S Uo(si 82)
16

---

Quasi-Potential Reinforcement Learning (QPRL)
actual costs associated with all possible transitions. This also contradicts the Bellman optimality condition because the true cost cannot be lower than what is physically achievable.
Constraint Threshold (e) 90% Success
Average Steps to Stability
0.01
115,000
Conservative exploration
0.05
88,000
Balanced learning
0.1
78,000
Fastest convergence
Since both overestimation and underestimation lead to con- tradictions, we conclude that the quasi-potential function Ug must satisfy:
0.2
95,000
High variance
Table 5. Effect constraint threshold (e) on sample efficiency Asymmetric GridWorld.
(z = ..A
a) + M(s (8', ,))}
results, summarized Table indicate that a batch size of 128 provides the best performance in terms of convergence speed and stability.
for all states s and goals g. This completes the proof.
G. Hyperparameter Sensitivity Analysis
Batch Size Steps to (B)
Computational
We conducted hyperparameter sensitivity analysis in the Asymmetric Wrild environment to understand the effect of various hyperparameters on the performance of Quasi-Potential Reinforcement Learning (QPRL). Specifi- cally, we varied the learning rate, constraint threshold (c), and batch size, measuring their impact convergence speed and stability. This analysis provides insights into the appro- priate choice of hyperparameters for efficient learning in environments with asymmetric traversal costs.
Stability
95% Success
Efficiency
32
140,000
High variance
Low
64
95,000
Balanced Stable
Moderate
128
78,000
High
256
85,000
Slightly oscillatory
High
Table 6. Effect of batch size convergence time and stability in Asymmetric GridWorld.
G.1. Learning Rate Sensitivity
H. Computational Complexity Analysis
The effect of different learning rates (av' in the Asym- metric Wrild environment. including 10-5, 10-1, 5 x 10-4, and 10-3, is shown in Figure 7. A learning rate of 10-4 results in the fastest and most stable convergence.
We analyze the time and space complexity of QPRL, focus- ing on its unique aspects related to quasi-potential functions.
H.1. Time Complexity
The time complexity of QPRI. per step is O log d [A]), where d is the dimensionality of the state representation and
Learning Rate
Steps to 95% Success Rate Behavior
Observed
(av)
A is the size of the action space. This complexity arises from:
10
320,000
Slow convergence
10
75,000
Fast and stable
x 10
105,000
Oscillatory behavior
10-3
Divergence
O(d log d): Updating the coasi-potential function
O([Al): Policy evaluation and selection
Table Effect of leamingg rate on convergence time in Asymmetric GridWorld (steps to reach 95% success rate).
The d² log d term dominates in high-dimensional state spaces, making QPRL more computationallyy intensive per step compared to simpler methods like Q-learning However, QPRL often requires fewer steps to converge, potentially offsetting this cost.
G.2. Constraint Threshold Sensitivity
The constraint threshold controls how strictly QPRL forces the quasi-potential constraint. Figure 7 shows the impact of different values of e in the Asymmetric Grid-
World environment on sample efficiency and stability. A value of = 0.1 achieves the best balance between explo- ration and constraint satisfaction.
H.2. Space Complexity
The space complexity of QPRL is O(d + [A]), which in- cludes:
G.3. Batch Size Sensitivity
O(d)): Storage of the quasi-potential function
We analyzed the effect of batch sizes (B) of 32, 64, 128, and 256 in the Asymmetric World environment. The
O(IA)): Storage of the policy
17

---

Quasi-Potential Reinforcement Learning (QPRL)
Hyperperameter Sensitivity Analysis for OPRL in Asymmetric GridWorld
3.3
Oweseen (Piiess
Supo Sriiist
seseennt Stepo Shaien
3.-
3.3
Barch
Butch
Barch Sze
Batch
Owitstnen: 2111
One commett Stepe 9rBloo
Ona comeent Stpee (48lin))
Cnatooment Stepe (illinn)
Figure 7. Hyperparameter Sensitivity Plots for QPRL in the Asymmetric GridWorld Environment. Top row: Learning rate sensitivity. Middle row: Constraint threshold (e) sensitivity. Bottom row: Batch size sensitivity. QPRI. sensitive to appropriate hyperparameter selection, with optimal values yielding stable and efficient convergence.
This space requirement scales well with increasing state space size, making QPRL suitable for complex environ- ments where tabular methods become infeasible.
assumes stationary environments, limiting its direct applica- bility dynamic, real-world scenarios. The interpretability of learned quasi-potential functions remains challenge, as their high-dimensional nature can obscure insights into func-
While QPRL introduces additional computational overhead, its improved sample efficiency often leads to faster overall convergence complex, asymmetric environments. Future work could focus on developing more efficient update mech- anisms for the quasi-potential function further improve QPRL's computational efficiency.
policy decisions. Lastly, the use of tions in policy exccution introduces a modest computational overhead compared to traditional value-based methods. Ad- dressing these limitations through techniques such di- mensionality reduction, adaptive learning rates, online adap- tation mechanisms, and improved visualization methods represents promising directions for future research, poten- tially broadening QPRL's applicability and enhancing its performance across a wider range of reinforcement learning tasks.
I. Limitations of QPRL
Despite its advantages in handling asymmetric traversal costs, QPRL faces several challenges that warrant further investigation. The approach may struggle with scalability in high-dimensional state spaces, the quasi-potential func- tion grows quadratically with the state space size, potentially leading to computational bottlenecks. In environments with extremely sparse rewards, QPRL's sample efficiency can de- grade, requiring additional samples to achieve comparable performance, The method's sensitivity to hyperparameters, particularly the learning rate for the quasi-potential function, necessitates careful tuning. QPRL's current formulation
18


Reviews:
[{"review_id": "ZMT9TDlaVv", "reviewer": "Reviewer_gCKW", "summary": "This paper proposes a new RL algorithm designed to effectively deal with asymmetric traversal costs, for example, when transitions are irreversible or incur different costs in forward and backward directions. The main idea is to decompose asymmetric costs into path-independent potentials and path-dependent residuals. In contrast, prior quasimetric RL methods learn asymmetric costs with a monolithic function. The proposed method is demonstrated to be more sample efficient than  a large number of relevant baselines in simulated tasks.\n\n## update after rebuttal\nI thank the reviewers for their retailed rebuttal to my concerns. I have a better understanding of the motivation for their method and this paper's contributions. Hence, I am increasing my score to \"Weak Accept\".\n\nMy primary remaining concern is that the paper makes broad and sweeping claims about facts that are much more nuanced in reality. For example, the claim about about the inability of \"most\" existing RL algorithms to deal with asymmetric costs, which the authors also agree is not fully correct. Hence, this paper needs to be revised to tone down the language.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and insightful questions. We address your concerns in detail below.\n\n> “The paper lacks clarity on its motivation.”\n\nWe appreciate this critique and will revise the introduction to emphasize more real-world scenarios where cost asymmetry is central—**e.g.,** mobile robots facing steep terrain (where uphill vs. downhill cost differs), or mechanical systems experiencing irreversible wear from certain operations. In such settings, ignoring the directional nature of costs can lead to inefficient or risky strategies. By explicitly modeling these costs via a quasimetric decomposition, our method addresses these concerns.\n\n> “The authors claim that traditional RL approaches assume ..standard algorithms like DQN/PPO/SAC do not. Could the authors please clarify which algorithm they are referring to?”\n\nWe apologize for any confusion in our statement. **Our intent is not to say that standard off-the-shelf algorithms explicitly require symmetrical costs or dynamics** in a strict manner. The classical MDP indeed allows arbitrary transition probabilities and reward structures, and thus does *not* force symmetry.\n\nHowever, many popular RL methods — and especially earlier potential-based reward shaping approaches — *do* rely on distance or reward-shaping functions that are typically symmetrical. For instance, potential-based shaping often uses a potential function $\\Phi(s)$ that is akin to a “distance-to-goal,” which is treated as a metric rather than a quasimetric, implying symmetry. Additionally, analyses of standard Q-learning or policy-gradient algorithms often do not explicitly account for irreversible or direction-dependent transitions, so they may fail to handle such cases efficiently.\n\n**Symmetric vs. Asymmetric Cost Assumptions:** In many navigation and planning contexts, symmetric cost implies that the effort or cost to traverse from state $s$ to $g$ is equivalent to that from $g$ back to $s$. Traditional RL algorithms can handle arbitrary cost functions in principle; however, they often rely on heuristics or shaping rewards that assume an underlying symmetric structure (e.g., using Euclidean distance to goal as a potential-based reward shaping). This assumption breaks down in environments with irreversible or direction-dependent costs. For example, climbing up a hill vs. going down may have drastically different energy costs, yet a symmetric distance heuristic would treat them as equal. Our QPRL framework relaxes this assumption by learning a quasimetric that allows $d(s,g) \\neq d(g,s)$. In other words, we do not require the cost of forward and reverse transitions to be the same.\n\n**Decomposition $d(s,g) = \\Phi(g) - \\Phi(s) + \\Psi(s\\to g)$:** We appreciate the chance to clarify this core contribution. This equation defines the learned quasi-potential distance between any state $s$ and goal $g$ as having two components: (1) a potential difference $\\Phi(g)-\\Phi(s)$, and (2) an extra path-dependent term $\\Psi(s\\to g)$. Intuitively, $\\Phi(x)$ can be seen as a learned “height” or potential at state $x$ (independent of any specific path), while $\\Psi(s\\to g)$ captures irreversible costs incurred along the particular path from $s$ to $g$ (violations of symmetry). If the environment were fully reversible (no asymmetric costs), one could choose $\\Psi\\equiv0$ and $d(s,g)$ reduces to $\\Phi(g)-\\Phi(s)$, a standard potential-based difference. In general asymmetric environments, however, such a pure potential cannot exist globally — $\\Psi$ is necessary to account for the non-conservative part of the cost. By decomposing the distance function this way, our approach improves upon prior quasimetric RL (QRL) methods, which did not explicitly separate conservative and non-conservative cost components.\n\n> Similarly, the authors claim, “Unlike traditional value functions, which assume reversibility and symmetry in costs.” It is.. make this assumption, but the claim is quite broad.\n\nWe agree that this statement can be read as overbroad. Our intent was to highlight how typical reward/value formulations do not enforce the directionality constraints that appear in irreversible or asymmetrically costly transitions. A standard value function can be learned in such scenarios, but it will not explicitly embed or guarantee any properties reflecting $\\text{cost}(s \\to s') \\neq \\text{cost}(s' \\to s)$.\n\n> “Algorithm 1 seems to use a fixed batch of data, suggesting offline RL. Is it offline or online?”\n> \n\nWe apologize for the ambiguity in Algorithm 1’s description. Our method is designed for **online RL** with replay. Specifically:\n\n1. The agent interacts with the environment, gathering new transitions continuously.\n2. These transitions are stored in a replay buffer.\n3. Algorithm 1 outlines how we sample mini-batches from that buffer to update the network parameters.\n\nAlthough the pseudo-code shows the mini-batch updates, we *do* gather new data between iterations. We will clarify this in the final version.", "claims_and_evidence": "Experimentally, the paper does show that their proposed algorithm is more sample efficient than baselines in environments with asymmetric costs.", "methods_and_evaluation_criteria": "Yes, the paper analyses their algorithm using a range of relevant evaluation metrics, such as, success rate and traversal costs.", "theoretical_claims": "I did not check the proofs of the theoretical claims.", "experimental_designs_or_analyses": "Yes, the experimental design is sound. The authors ran their experiments with 5 seeds and reported the mean and standard deviation for their metrics.", "relation_to_broader_scientific_literature": "The paper is most closely related to Quasimetric Reinforcement Learning (QRL) by (Wang et al., 2023). The main contribution is to decompose the quasimetric into a potential function and a path-dependent residual function instead of modeling the quasimetric as a single function.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths**\n\n- The paper addresses an important problem of RL with asymmetric traversal costs and irreversible transitions, which are common in practical tasks.\n    \n- The algorithm is theoretically analysed and its convergence and safety are guaranteed.\n    \n- Empirical experiments in simulated domains show a decent performance over a large number of baselines.\n    \n\n**Weaknesses**\n\n- The paper claims traditional RL assumes symmetric costs but it is not the case, to my knowledge. Overall, the paper lacks clarity on its motivation.\n    \n- The paper does not clearly convey the intuition for the proposed method. While empirically it leads to an improvement but it is not clear to my why it should do better than QRL.", "other_comments_or_suggestions": "See questions.", "questions_for_authors": "1. The authors claim that traditional RL approaches assume symmetric traversal costs between states. However, to my knowledge most state-of-the-art RL algorithms, such as PPO, SAC, DQN, do not make this assumption. Could the authors please clarify which algorithm they are referring to? This is important to judge the significance of their contribution.\n    \n2. Similarly, the authors claim, “Unlike traditional value functions, which assume reversibility and symmetry in costs”. It is possible that specialized methods make this assumption, but the claim is quite broad.\n    \n3. Intuitively, it is not clear to me why the decomposition of asymmetric costs in the proposed way is beneficial, apart from interpretability. However, the experiments do show that this representation boosts performance. Could the authors please clarify?\n    \n4. Is the proposed algorithm used in online or offline RL setting? Algorithm 1 seems to use a fixed batch of data which seems to imply offline RL.", "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": "ovocJGsfAe", "reviewer": "Reviewer_MjcM", "summary": "This paper proposes Quasi-Potential Reinforcement Learning (QPRL), a framework that decomposes asymmetric costs into pathindependent potentials and path-dependent residuals, enabling Lyapunov-stable policy optimization. The performance of the proposed QPRL has been validated in some customized classic RL environments against some baseline methods.\n\n## update after rebuttal\n\nI appreciate author's additional results and further explanation. QPRL seems to be an incremental work on top of QRL, I remain my overall recommendation", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">What's the main different between QRL and QPRL? Just additional potential function s.t. provide Lyapunov stability guarantee? It seems to me that the asymmetric transition is more important, which is the same as QRL\n\nOur work indeed builds directly on the insight from Quasimetric RL (QRL) that many tasks benefit from asymmetry-aware cost functions. However, the key novelty of QPRL is the $\\Phi + \\Psi$ decomposition of the quasimetric into:\n\n$\nd(s, g) = Φ(g) - Φ(s) [path-independent potential] + Ψ(s → g) [path-dependent residual]\n$\n\nwhich offers two major improvements over a single monolithic quasimetric:\n\n**Better Sample Efficiency Through Structured Modeling:**\nInstead of learning one unconstrained $d(s, g)$, we factor out the portion that is roughly state-potential-like ($\\Phi$) from the portion that truly depends on direction or path ($\\Psi$). This leads to faster training convergence, as demonstrated by our stronger sample-complexity bounds (see Section 4.5) and by empirical results.\n\n**Lyapunov-Based Safety Layer:**\nBecause $\\Phi$ can be treated as a Lyapunov function, we enforce a constraint that effectively avoids large jumps in $\\Phi$ between consecutive states. This drastically lowers the chance of irreversible transitions during exploration. QRL, by contrast, learns a single function $d(s, g)$ with no built-in safety or stability guarantee.\n\n**Please also check rebuttal response 1 for further discussion**\n\n>It will be interesting to see whether such method can work on senarios with sparse reward. Dense reward senarios are relatively easy to train in general.\n\nWe agree that sparse-reward environments pose a distinct challenge, and we believe our method is well-suited for them. Indeed, potential-based shaping has historically been used to address sparse rewards by providing intermediate signals. Because QPRL is inherently a form of potential-based approach (though adapted to asymmetric costs), it can similarly mitigate sparsity by providing an auxiliary shaped cost function.\n\n> In section 5.5.5, no error bar provided in Fig 6 and I don't think that is a proper way to do statisitc analysis with simply mean with variance\n\nWe have updated the figure (Please check here: https://imgur.com/a/tPM3pfC). Each bar now has error bars providing information about variance.  For each environment, a line is drawn between the QPRL bar and the baseline and annotated with a significance marker (e.g., * (p < 0.05))\n\n---\n>... Table 2 there is no any baseline methods performance data\n\nBelow is an updated version of Table 2 that incorporates baseline performance data, along with the corresponding performance gaps (i.e., the difference between symmetric and asymmetric task performance) for each method. \n\n| Environment         | Method       | Symmetric (%)      | Asymmetric (%)     | Gap (%) |\n|---------------------|--------------|---------------------|---------------------|---------|\n| **Asymmetric GridWorld** | QPRL        | 94.1 ± 1.8          | 88.7 ± 2.5          | 5.4     |\n|                     | QRL         | 92.3 ± 2.0          | 83.5 ± 2.8          | 8.8     |\n|                     | SAC + HER   | 90.2 ± 2.3          | 81.0 ± 3.2          | 9.2     |\n|                     | DDPG + HER  | 89.8 ± 2.5          | 80.5 ± 3.5          | 9.3     |\n| **MountainCar**     | QPRL        | -90.5 ± 4.3         | -98.2 ± 5.0         | 7.7     |\n|                     | QRL         | -88.2 ± 4.1         | -96.5 ± 5.2         | 8.3     |\n|                     | SAC + HER   | -87.0 ± 4.0         | -95.8 ± 5.3         | 8.8     |\n|                     | DDPG + HER  | -86.5 ± 4.2         | -94.5 ± 5.1         | 8.0     |\n| **FetchPush**       | QPRL        | 92.0 ± 2.2          | 85.3 ± 3.1          | 6.7     |\n|                     | QRL         | 90.5 ± 2.3          | 81.0 ± 3.2          | 9.5     |\n|                     | SAC + HER   | 89.8 ± 2.5          | 79.8 ± 3.5          | 10.0    |\n|                     | DDPG + HER  | 88.5 ± 2.4          | 78.5 ± 3.4          | 10.0    |\n| **LunarLander**     | QPRL        | 88.6 ± 3.4          | 82.4 ± 3.7          | 6.2     |\n|                     | QRL         | 87.0 ± 3.5          | 80.0 ± 4.0          | 7.0     |\n|                     | SAC + HER   | 85.5 ± 3.8          | 77.5 ± 4.2          | 8.0     |\n|                     | DDPG + HER  | 84.0 ± 3.6          | 76.0 ± 4.1          | 8.0     |\n\n>Fig. 5\n\nPlease check the updated Fig. 5 here: https://imgur.com/a/KwA2Ktk", "claims_and_evidence": "- The decomposed asymmetric costs is adapted from previous paper [Wang et al., 2023]\n- The convergence to optimal policies under asymmetric dynamics (Theorem 4.1) is supported by Appendix B.1\n- The sample complexity is supported by Appendix B.2 and empirically by 5.5.2\n- The Lyapunov stability certificates for safe exploration (Lemma 4.2) is supported by Appendix B.3", "methods_and_evaluation_criteria": "The evaluation criteria does make sense", "theoretical_claims": "I've checked Appendix B1, B2, and B3, looks good to me", "experimental_designs_or_analyses": "To me I think the experimental design is clever. They modify the classic RL environment with asymmetric transition reward so that all classic RL methods can be directly deployed on these environment. The evaluation metrics can support their assumptions in general. There are some issues:\n- In section 5.5.4, authors claim that QPRL demonstrates a smaller performance gap compared to the baselines, indicating its robustness in environments with directiondependent dynamics, but in Table 2 there is no any baseline methods performance data\n- In section 5.5.5, no error bar provided in Fig 6 and I don't think that is a proper way to do statisitc analysis with simply mean with variance", "relation_to_broader_scientific_literature": "This paper is highly related to previous literature on Quasimetric Reinforcement Learning (QRL) and RL with potential function. My major concern is the novelty of the proposed QPRL as compared to QRL, more elaboration on their difference will be helpful.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well-written and easy to follow in general. The proofs seems correct to me. The empirical experiments spans 4 customized RL environment with multiple baseline methods. The experimental analysis part is relatively short and insufficient. The statistic analysis with average traversal cost might not be enough to prove the advantage statistically, p-test or some other statistical tests will be preferred. The ablation studies are also short, some extended ablation studies in the Appendix will be helpful.", "other_comments_or_suggestions": "Authors can consider change the color and font in Figure 5 & 6 to increase the readability. Table 2 & 3 needs to be updated with more results.", "questions_for_authors": "1. What's the main different between QRL and QPRL? Just additional potential function s.t. provide Lyapunov stability guarantee? It seems to me that the asymmetric transition is more important, which is the same as QRL.\n2. It will be interesting to see whether such method can work on senarios with sparse reward. Dense reward senarios are relatively easy to train in general.", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "qrSjrkqyyT", "reviewer": "Reviewer_c6vF", "summary": "The paper proposes Quasi-Potential Reinforcement Learning to tackle environments with asymmetric traversal cost.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In Fig 5, what do the authors mean by \"learning curves\"? ... is the std or confidence interval used?\n\nThe learning curves represent the mean success rate measured over 5 independent runs (each with a different random seed) as a function of environment interactions. The shaded regions (or error bars) correspond to ±1 standard deviation across these runs. We chose the mean and standard deviation as our reporting metrics to clearly convey both the central tendency of the performance and the variability due to randomness in training. \n\n> In Fig 6, could the author add std .... about the results? ... results is not sufficient to say ... better than others.\n\n**Please check the rebuttal response 2**\n\n>In section 4.3, the equation regarding the is incomplete. Fig 3 is unclear to me. More details can be given for the policy update (...lines 13-16 in Algorithm 1).\n\nOur policy update is designed to ensure that the chosen action satisfies a safety constraint based on the learned potential function $\\Phi$. We require that the expected potential of the next state does not exceed the current potential by more than a small threshold $\\epsilon$. We enforce:\n\n$\n\\mathbb{E}_{s'\\sim P(\\cdot\\mid s,a)}\\big[\\Phi(s')\\big] \\leq \\Phi(s) + \\epsilon.\n$\n\nafter encoding the current state $s$ into a latent representation $z = f_\\phi(s)$, the policy $\\pi_\\omega(s, g)$ selects an action $a$. The transition model then predicts the next latent state $\\hat{z}' = T_\\psi(z,a)$ from which we estimate the potential $\\Phi(s')$. The policy loss is augmented with a penalty term:\n\n$\nL_{\\pi} = \\mathbb{E}\\left[d(s,g) + \\lambda\\,\\operatorname{ReLU}\\Big(\\Phi(\\hat{z}') - \\Phi(s) - \\epsilon\\Big)\\right],\n$ \nwhere\n\n$d(s,g) = \\Phi(g) - \\Phi(s) + \\Psi(s \\to g)$\nis our quasipotential cost and $\\lambda$ is a Lagrange multiplier. This term penalizes actions that would lead to $\\Phi(s')$ exceeding $\\Phi(s) + \\epsilon$, effectively projecting the policy update onto the safe set:\n\n$\\pi_{\\text{safe}}(a\\mid s) = \\pi(a\\mid s) \\quad \\text{subject to} \\quad \\mathbb{E}\\big[\\Phi(s')\\big] \\leq \\Phi(s) + \\epsilon$\n\n**Fig. 3 Clarification:**\n\n-  It shows the decomposition of the asymmetric cost:\n  $\n  d(s,g) = \\Phi(g) - \\Phi(s) + \\Psi(s \\to g),\n  $\n  where $\\Phi$ captures the path-independent cost (acting as a potential or Lyapunov function) and $\\Psi$ captures the path-dependent (irreversible) residual cost.\n\n- the predicted potential $\\Phi(s')$ is compared against the safe threshold $\\Phi(s) + \\epsilon$. An arrow or boundary indicates that if $\\Phi(s')$ exceeds this threshold, a penalty is applied. This guides the policy towards actions that keep the state within a “safe” region.\n\n-  It shows that the policy is updated to minimize both the overall quasipotential cost $d(s,g)$ and the safety penalty, ensuring that:\n  $\n  \\mathbb{E}\\big[\\Phi(s')\\big] \\leq \\Phi(s) + \\epsilon.\n  $\n\n> \"... the authors claim that ....Could the authors offer more evidence to support this claim?\"\n\nPlease check the rebuttal 1 response.\n\n> *“For the non-Markovian reward, the paper claims .....$. Could the authors explain this in detail?”*\n\nOur approach does not entirely break the Markov property in the traditional MDP. Instead, we **locally** model path-dependent costs through the function $\\Psi(s \\to s')$. This allows us to capture direction-dependent or irreversible effects (e.g., “uphill” vs. “downhill”) *without* explicitly encoding full trajectory history.\n\n\n> *“When training the enco.....How did the authors prevent training collapse?”*\n\nTo avoid the collapse, we employ the following strategies:\n\n-  We collect data from multiple exploration runs so that the replay buffer contains *diverse transitions* $(s,a,s')$. This diversity makes the collapsed solution suboptimal, since a single constant embedding would incur high reconstruction error across varied transitions.\n\n-  We add a *contrastive term* that forces the encoder to separate distinct states in latent space. For instance, we encourage $\\|f_\\phi(s') - T_\\psi(f_\\phi(s), a)\\|$ to be small for the *true* next state but large for randomly sampled negative examples. This negative sampling technique effectively penalizes collapsed embeddings.\n\n- We apply standard regularization (e.g., weight decay) and **monitor** the magnitude of $\\|f_\\phi(s') - T_\\psi(f_\\phi(s), a)\\|$ over each training epoch. If the model collapses, this loss quickly saturates. We terminate or adjust hyperparameters if we detect such behavior.\n\n>\"... the safety aspect ..is not well supported..\"\n\nIn our paper, “safety” means preventing the agent from entering irreversible or highly risky states. We enforce this by using a Lyapunov-based constraint on the potential function $\\Phi$, ensuring that at every step the expected increase in $\\Phi$ is bounded by a small threshold $\\epsilon$. This keeps the agent within a “safe” region of the state space, avoiding transitions that could lead to costly failures.\n\n>Fig .7\n\nPlease check the requested Fig. here: https://imgur.com/a/AHdJa6s", "claims_and_evidence": "The paper claims several contributions: \n1. The decomposed asymmetric costs enable Lyapunov-stable policy optimization.\n2. Theoretically, it proves QPRL has better sample complexity compared to QRL. The proof is given in the appendix.\n3. QPRL introduces a Lyapunov-based recovery mechanism that reduces irreversible constraint violations by 4 times compared to baselines. For this claim, according to my understanding, the proof in the appendix only shows Lyapunov stability under the QPRL policy, the \"4 time\" is neither shown in the proof nor the experiments.\n4. \"Results demonstrate that explicitly modeling path-dependent costs via quasi-potential decomposition enables safer, more efficient RL in complex navigation tasks with asymmetric costs.\" For this claim, I am not sure which results can be used to support \"safer\" RL.", "methods_and_evaluation_criteria": "The paper is mainly tested on 5 tasks, including asymmetric grid world, lunar lander, mountain car, fetch push and maze 2D. The method performance is discussed w.r.t. success rate, traversal cost efficiency, sample efficiency, asymmetric performance gap and normalized return.\nThe proposed method and evaluation criteria make sense in general. However, the evaluation criteria used do not demonstrate the safety aspect of the proposed method.", "theoretical_claims": "Unfortunately, I did not check the correctness of the proof.", "experimental_designs_or_analyses": "The experimental designs look good to me. The used environmental designs and analyses look good in general.\n\nSeveral questions:\n1. In Fig 5, what do the authors mean by \"learning curves\"? Specifically, is the mean or median reported, and is the std or confidence interval used?\n2. In Fig 6, could the author add std to include more information about the results? Also, reporting average results is not sufficient to say QPRL is \"significantly\" better than others.", "relation_to_broader_scientific_literature": "The paper considers a setting where the environments have asymmetric traversal costs. The paper is closely related to the quasimetric in RL.", "essential_references_not_discussed": "I do not notice essential but missing references.", "other_strengths_and_weaknesses": "The paper is well-motivated and aims to solve the asymmetric traversal costs in RL. The proposed method, which decomposers asymmetric costs into path-independent potentials and path-dependent residuals, is a reasonable design. \n\nAlthough the paper claims \"extensive empirical validation\", the proposed method is only evaluated on five modified classical control tasks and navigation tasks. Also, the safety aspect of the proposed method is not well supported by the experiments.", "other_comments_or_suggestions": "In section 4.3, the equation regarding the $\\pi_{\\text{safe}}$ is incomplete.\nFig 3 is unclear to me. \nMore details can be given for the policy update (corresponding to lines 13-16 in Algorithm 1).", "questions_for_authors": "1. In the paper (lines 53-54, right column), the authors claim that \"unlike traditional value functions, which assume reversibility and symmetry in costs\" and \"Traditional RL methods struggle in such settings due to their implicit assumption of asymmetric dynamics\" (lines 130-131). Could the authors offer more evidence to support this claim?\n\n2. For the non-markovian reward attribution, the paper claims that the path-dependent costs violate the Markov property since $C(s, a, s')$ depends on historical state transitions. According to the notation, $C(s, a, s')$ depends on $s$, $a$ and $s'$, which is still Markovian if $s^{\\text{new} = [s', s]}$. Could the author explain this claim in detail?\n\n3. When training the encoder and the transition model, the paper uses the equation in Line 172 (right column). However, minimizing this equation may cause a collapsed solution where both encoder $f_\\phi(s)$ and latent dynamics $T_\\psi$ return a constant. How did the author prevent the training collapse?", "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:

Meta-review: The paper introduces Quasi-Potential Reinforcement Learning (QPRL), designed to handle environments with asymmetric traversal costs by decomposing these costs into path-independent potentials and path-dependent residuals. QPRL aims to achieve Lyapunov-stable policy optimization with improved sample complexity compared to prior quasimetric RL methods. The authors present theoretical proofs and empirical validation of their approach in simulated tasks.

Reviewers appreciated the novelty of addressing asymmetric costs and the theoretical guarantees of convergence and safety. Reviewers also found the experimental design clever and the paper generally well-written. However, concerns were raised regarding the clarity of the motivation and potential overstatements about the limitations of traditional RL in handling asymmetric costs. The most significant criticism was around the incremental novelty of QPRL over existing Quasimetric Reinforcement Learning (QRL) methods, and room for strengthening the empirical validation, with suggestions for more extensive analysis and statistical rigor. The authors' rebuttal clarified the motivation, the differences between QPRL and QRL, and provided updated results and figures. 

Overall the paper addresses asymmetric costs with the strong theoretical underpinnings, and the new empirical evidence, with somewhat incremental novelty.
Decision: Accept (poster)