Graph-Theoretic Intrinsic Reward: Guiding RL with Effective Resistance
Authors: Jatin Chauhan
Shivam Bhardwaj
Aditya Saibewar
Aditya Ramesh
Sadbhavana Babar
Manohar Kaul
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning
Intrinsic Motivation
Goal Conditioned RL
Effective Resistance
Primary area: reinforcement learning
TL;DR: We propose an intrinsic reward formulation using the notion of Effective Resistance based on spectral graph theory, for learning robust policies in sparse environments.

Abstract: Exploration of dynamic environments with sparse rewards is a significant challenge in Reinforcement Learning, often leading to inefficient exploration and brittle policies. To address this, we introduce a novel graph-based intrinsic reward using Effective Resistance, a metric from spectral graph theory. This reward formulation guides the agent to seek configurations that are directly correlated to successful goal reaching states. We provide theoretical guarantees, proving that our method not only learns a robust policy but also achieves faster convergence by serving as a variance reduction baseline to the standard discounted reward formulation. We perform extensive empirical analysis across several challenging environments to demonstrate that our approach significantly outperforms state-of-the-art baselines, demonstrating improvements of up to 59% in success rate, 56% in timesteps taken to reach the goal, and 4 times more accumulated reward. We augment all of the supporting lemmas and theoretically motivated hyperparameter choices with corresponding experiments.

Published as a conference paper at ICLR 2026
GRAPH-THEORETIC INTRINSIC REWARD: GUIDING RL WITH EFFECTIVE RESISTANCE
Jatin Chauhan', Shivam Bhardwaj',. Aditya Saibewar, Aditya Ramesh, Sadbhavana Babar & Manohar Kaul Fujitsu Research*
ABSTRACT
Exploration of dynamic environments with sparse rewards is a significant chal- lenge in Reinforcement Learning, often leading to inefficient exploration and brit- tee policies. To address this, we introduce novel graph-based intrinsic reward using Effective Resistance, metric from spectral graph theory. This reward for- mulation guides the agent to seek configurations that are directly correlated successful goal reaching states. We provide theoretical guarantees, proving that our method not only learns a robust policy but also achieves faster convergence by serving variance reduction baseline to the standard discounted reward for- mulation. We perform extensive empirical analysis across several challenging environments demonstrate that approach significantly outperforms state-of- the-art baselines, demonstrating improvements of up to 59% in success rate, 56% in timesteps taken to reach the goal, and 4 times more accumulated reward. We augment all of the supporting lemmas and theoretically motivated hyperparameter choices with corresponding experiments.
INTRODUCTION
Training policies in sparse-reward settings has been a longstanding challenge, which has now be- come mainstream with increasing deployments of autonomous agents in real world. Initial series of works focused on leveraging meticulously engineered dense reward functions to guide the learning process (Schulman et al., 2017 Barto 202T), which achieved success tasks ranging from simple pathfinding to complex motor control (Schulman al. 2017 Barto 2021). However, the reliance such dense rewards inherently limits the scalability (Cao et al. 2024 Antonyyshy & Givigi 2024). On the contrary, in the sparse reward setting the agent receives positive signal only upon reaching a distant goal, with no intermediate feedback to guide its exploration. This credit assignment prob- lem often renders simple exploration strategies, such as e-greedy action selection or unstructured noise, rather ineffective as the agent is unlikely to encounter the reward achieving state through random behavior (Pitis et al. 2020). To overcome this, intrinsic motivation based methods have garnered much attention and success recently (Achiam & Sastry 2017] Xudong et al. 2024), which typically generate dense reward signal to encourage meaningful exploration. These signals are often based on informationntheorrtiic concepts like novelty, curiosity, or surprise (Achiam & Sastry) 2017 Pathak et al., 2017 Burda et al. 2018). These methods however have caveats. Most these methods provide empirical validation, however fail to justify the algorithms with theoretical guar- antees. Furthermore, methods like (Xudong et al. 2024), albeit better than their predecessors like Hindsight Experience Replay (HER) (Andrychowicz et al., 2018) and MEGA (Pitis et al.) 2020), further require policies pretrained via Behavioral Cloning to operate well, which can be expensive in many situations. Other methods such as the Surprise Based notion of (Achiam & Sastry 2017) focus on model-based RL where the transition probabilities are modeled explicitly, which is highly non-trivial (Viano al. (02T).
Accounting for all these factors, we introduce a novel principled approach to intrinsic motivation for goal-conditioned RL with roots in spectral graph theory. We model the agent's perception of its dynamic environment, where all entities move arbitrarily, as graph that evolves over time.
denotes Equal Contribution. Email Correpondence: (chawhan. jatin, shivam bhardwajj saibewar.adiyaa rdiey,. sadbhavona.bahin bobar, manoharr @ @fujitsu.com

---

Published as a conference paper at ICLR 2026
The nodes of this graph characterize all the objects (including the agent and the goal) whereas the weighted edges describe the vicinity relative to the agent's 's sensors. As the primary contribution of this work, we propose to use the Effective Resistance between the agent and goal nodes as intrinsic reward. Intuitively, effective resistance quantifies the information flow between two nodes in network, considering all possible paths between them (Evans & Francis (021). These possible paths naturally account for all the objects present within the agent's 'ss sensing radii. A decrease in this resistance signifies that the goal has become more structurally accessible within the agent's perceived map that may not be quantified by using simpler metrics such as Euclidean distance.
We emphasize that our proposed formulation is broadly applicable to goal-conditioned RL, where the observable (fully or partially) state space can be decomposed to extract the entities of interest in order to construct any graph. We provide detailed discussion of such settings in section A.14 Furthermore, we focus on sparse and constrained environments since such settings serve as more interesting and challenging test cases in real world. We demonstrate this via an illustration in figure| where the agent to goal relative distance remains same but the second configurations makes the task success much more feasible by providing better pathways to the agent. In both cases, evolution of Euclidean distance cannot provide any meaningful signal whereas the change in Effective Resistance provides a dense reward signal to update the policy. Furthermore, contrary to the inefficiencies of the aforementioned methods in the literature, our method does not require any pre-training and the whole process is on on-policy. We also do not restrict ourselves to explicit model- based formulation either, thus generalising our contribution.
We provide various theoretical results for the time evolution of the effective resistance (Rar) in correspondence to the state configuration rel- ative to the agent. This translates to the evolu- tion of graph connectivity (generated over the state) showing that as the Ren reduces, the con- nectivity improves. We also characterize vari- ous lemmas in section[4jor its effect on the gra- dients of the policy and improved goal visibil- ity. Additionally, we show that our formulation serves variance reduction baseline leading to improved sample complexity and faster con- vergence.
offective 0.90
022
Lffectiva
GOVL
COAL
ODSS
0,8
AGGHT
AGAAT
Figure An illustrative example showing two configurations (a) first where the agent's path is bottlenecked resulting in a denser local graph (section 3.2 and higher effective resistance value identifying it as a less sought after config- uration, (b) second with lower Effective Resis- tance where the agent can navigate through var- ious pathways. In both cases, the Euclidean dis- tance remains same and the direct path to the goal obstructed, thus any such metric does not pro- vide meaningful signal.
Our contributions in this work are thus four- fold. First, we formalize the use of effective re- sistance as surprise-based intrinsic reward for goal-conditioned reinforcement learning. Sec- ond, we provide theoretical guarantees for our method, proving that it leads to robust navi- gation policies and faster convergence. Third, we conduct extensive evaluations on a suite of challenging navigation tasks with sparse re- wards from the Safety Gym library by (Ji et al.] 2024], outperforming ofate-of-the-art baselines by upto 59% in success rate in achieving the goal, 56% in timesteps taken to achieve the goal as the trajectories unfold, and 4x better reward. Fourth, we provide detailed and rigorous empirical validation of all theoretical claims, especially including the principled selection of key hyperparam- eters.
2 RELATED WORK
Our work builds upon two primary pillars of reinforcement learning research: goal-conditioned reinforcement learning (GCRL) or goal-conditioned policy optimization (GCPO) and intrinsic mo- tivation for exploration. GCRL extends the standard RL framework by training policies that can
generalize across wide range of goals (Liu et al. 2022 Nasiriany al. 2019), making it core component of hierarchical agents and unsupervised skill discovery (Pitis et al. (2020). A key enabler for GCRL in reward settings has been Hindsight Experience Replay (HER) (Andyychowicz
2

---

Published as a conference paper at ICLR 2026
et al., 2017), which relabels failed trajectories to create dense learning signals. While effective, HER- based methods are predominantly off-py and struggle with certain task structures, such as those with non-Markovial rewards where single state cannot be treated as a hindsight goal (Xu et al. 2025). Xuudong et al. 2024) recently proposed a formulation for trajectory selection that im- proves over previous works this setting. They also provide detailed summary of this line of work and as recent SOTA method, we have used it as a baseline in our work. Our on-policy approach circumvents this limitation while still addressing the core challenge of exploration in multi-goal settings.
To tackle the exploration problem in sparse-reward tasks, researchers have proposed various forms of intrinsic motivation to generate dense rewards. These methods encourage an agent to explore based on ieftommttion-thooreee
concepts like novelty, learning progress, or surprise (Achiam & Sastry, 2017 Pathak et al. (017). Surprise, in particular, has been formulated the divergence between an agent's learned world model and the true environment dynamics, incentivizing the agent to visit unfamiliar states (Burda et al. 2018). Another line of work focuses on maximizing the entropy of the achieved state or goal distribution, encouraging broad exploration of the agent's capabilities (Pitis et al. 2020). Unlike methods that model transition probabilities directly (Achiam & Sastry 2017; Liu et al. (2222) or sample goals from a learned density such as (Pitis et al. (2020), our approach uses the structural properties of dynamically generated graph from the state configuration relative the agent in order to create an intrinsic reward that naturally for all possible pathways and all instances in the environment.
METHODOLOGY
3.1 PRELIMINARIES
We model the task as MDP defined by the tuple M = (S, The state space S consists of observations St R.,, with the actions a RV (see section A.2 for details).The transition probabilities, ( (t, az), are unknown, which is the case for majority of practical environments. The reward function R(st, ax) is a composition of an extrinsic and an intrinsic signal with 7 being the discount factor. The extrinsic reward, (ex is sparse, providing positive reward only for reaching the goal (which may never happen (Vasan et al., 2024 Hare, 2019)) along with negative cost for situations such as collision with other dynamic objects in the environment. The intrinsic reward, (fn(()), is dense signal we design to guide the agent. The total reward at time is combination of both with a weighting hyperparameter a
MDP formulation:
Tiotal (l) (t) + Fim
(1)
Problem Statement: We use the standard objective in RL, where the aim is to find the opti- mal parameters for the policy To (a((())) that maximize the expected discounted reward
arg maxy Eç-oo E ('Toss(()) where the trajectory < (so. au $1, .I....) is generated by executing the policy иe. The core challenge lies in the sparsity of rea(!), which makes exploration difficult and renders standard algorithms ineffective as shown in section
3.2 INTRINSIC REWARD VIA EFFECTIVE RESISTANCE
Intrinsic rewards have been shown to encourage learning, proving especially beneficial for environ- ments with sparse rewards (Devidze et al. 2022). Furthermore, the combination of intrinsic and (sparse) extrinsic rewards improves overall learning by balancing such exploration behavior and task-specific goal achievement during the policy update (Zheng et al. 2024).
We ground our intrinsic reward in Effective Resistance (Chung 1997). Unlike trivial metrics such as Euclidean distance which doesn't it provide an effective signal as discussed earlier, the brittle Shortest Path Distance (Goldberg Harrelson 2005) which is susceptible to single-point failures or coarse global measures like Algebraic Connectivity (Fiedler 1973), effective resistance provides a goal- oriented, pairwise metric that holistically considers the all available paths. This property yields dense signal that promotes reliable navigation empirically in section [S] We now discuss the graph construction from the state vector s; needed to compute this metric.
have proved in Theorem [ and validated
3

---

Published as a conference paper at ICLR 2026
Graph Construction: A key component of methodology is the transformation of the high- dimensional state vector 9 into weighted, undirected time evolving graph G, = (V,, Es, Wt). The state vector 8, characterizes the environment's topology in localized neighborhood w.r to the agent's (such as LiDAR), providing a very broadly applicable egocentric framework (Liu et al.) 2023b). Additionally, other variants of graph formulation from the state vector 8t have also been shown to work remarkably well for some RL settings such as DQN (Waradpande et al., [021).
In Gr, the vertex set V2 includes nodes representing the agent, the goal, and distinct objects or object clusters. The edge set E, and their corresponding weights W2 represent the connectivity and proximity between these entities. Our graph construction algorithm consists of the following steps (i) construction of nodes of similar object categories (clusters) with a separate single node for the agent (egocentric formulation) in line 6 (ii) connecting the agent node to the remaining nodes in line [T] (iii) introducing intra and selective inter-cluster connectivity (in line (24). The complete details are provided in Algorithm[[ The specific design choices for this graph construction (Algorithm[] T are not arbitrary and we provide a detailed rationale in Appendix A.5.I analytical derivation for the clustering threshold r in Appendix A.5.3 and a full empirical sensitivity analysis in Appendix A.9
Effective Resistance:
For two nodes u, v E Ve, effective resistance measures the potential differ- ence between them when unit of current is injected at u and removed v. It is computed via the Moore-Penrose pseudoinverse, T,;" of the graph's 's Laplacian matrix L,:
Rei(U, u, e; Gi) = (ew - -e,)² L ee)
(2)
where en the standard basis vector for node u. We refer to Ret(w, v; Ge) as Rem(() hereon. We define the agent's intrinsic reward based on the change in effective resistance between the agent node A and the goal node g. Let (t) be the indicator function for goal being present in agent's sensing radii and thereby its node in Vg, The intrinsic reward (t)(()) (t) is defined as:
(A, gi G4+1) Rat(A, (A,g; G.))
if 1 goal (t + 1) (t) 1 goal (t) = 1, ggau + 1) = 0
3
Fime (1)
+3
if 1 1goal (t) = 0, goa (t + 1) = 1
0
otherwise
where 3 >> 0 is hyperparameter penalizing goal loss and rewarding goal recovery. Since our Tint formulation is generic, it can be augmented with any standard RL algorithm (we use PPO in our case, section A.5.2 for all the experimental details). We highlight that the graph construction in our method is focused on guiding the reward formulation, whereas the actions are predicted using 8, input to ihe (o.)ss).
We distinguish our analytic formulation from recent approaches in Quasimetric Learning (Wang al. 2023 Liu et al. 2024), which learn distance metries from interaction data. While such meth- ods offer flexibility, we emphasize that our effective resistance-based approach leverages the strong inductive bias of spectral graph theory. This grants our method immediate structural interpretabil- ity and theoretical guarantees without the high sample complexity required to learn a metric from scratch. We provide a detailed comparison of these paradigms in Appendix A.17
THEORETICAL RESULTS
Overview of Assumptions: We provide an informal version of our assumptions here, with the formal ones stated in appendix [A.] We assume a bounded sensing range for the agent, along with bounded motions of all objects. Any practical environment has limits on the velocity of objects, thus these assumptions are fairly practical. For sample complexity results, we have basic assumptions over smoothness of (-)-)-), which are common in the literature (section
Lemma 1 (Effective Resistance and Connectivity Relationship). Under standard assumptions on the environment and graph construction (Assumptions 7 5 in the appendix), for any connected graph G. containing the agent and goal, the temporal derivatives satisfy:
dReg(!) dt for some constant C > O, where Rog defined in eq and k is the algebraic connectivity, ie the second smallest eigenvalue of the laplacian which assume be unique for simplicity.
drs(G,) dt
dx(()))
-Ci
dt
4

---

Published as a conference paper at ICLR 2026
This lemma provides the crucial insight for our intrinsic reward: decreasing effective resistance is mathematically linked to increasing graph connectiviry. This allows us to use Rey as a dense reward signal guide the agent towards better configurations. While proven here. directly using has two caveats though: (i) it provides only a coarse, environment -iide connectivity without focusing on the agent-gone goat topology, (ii) more importantly, we empirically observed that the variations in much noisier in contrast to Ref as demonstrated in sections A.7 A.8.1
Lemma 2 (Bounded Connectivity Change). Under the same assumptions, the change in algebraic connectivity between consecutive timesteps is bounded:
[<( - -x(G)) S max
where 8max is constant dependent agent/object velocities and graph size bounds. We also show that k(G)) is Lipschitz contimuous with respect to time in corollary
This result allows for relatively stable policy optimization.
Lemma 3 (Policy Updates). The intrinsic reward (ta is positively correlated with the one-step change in algebraic connectivity, Ak(t) x(G++1) n(G.).
These supporting results culminate in main theorem, which states that policy optimized with our intrinsic reward is guaranteed to be robust.
Theorem (Connectivity Preservation and Robust Navigation). Under our stated assumptions, policy π" that maximizes the expected return with our effective resistance-bass based intrinsic reward is (e, 5, Trobust.. Specifically:
1. Connectivity Preservation: The policy avoids actions that drastically reduce connectivity expectation.
2. Robust Navigation: For sufficiently large penalty/reward 3 on goal visibility loss/gain, robustness (definition 5) of n² as the policy that reaches the goal with high probability while maintaining both goal visibility and graph connectiviry, which we have also shown hold very well empirically in sections A.8. AA..2
Corollary (Practical Policy Design). For effective implementation, the goal visibility penalty should be set dominate the extrinsic reward, and the intrinsic reward weight should be scaled relative to the environment's 's dynamics.
All these results culminate in the hyperparameter choices detailed in appendix A.6 pirical justifications of the lemmas in subsequent appendix sections A.7 A.7.I A.8 A.8.2
aloano with em-
4.1 IMPROVED SAMPLE COMPLEXITY
Lemma (Variance Reduction via Intrinsic Reward). The policy gradient for our combined objec- rive (Fwaat) is almost unbiased estimator for the extrinsic-only objective. Furthermore, Time (t) acts as a variance reduction baseline, which coupled with the sample complexity results from (Yuan) at.) (2022) shows that policies trained with our formulation can achieve substantially faster con- vergence at
Uronal (2U 2p))
where Unaut is the number gradient updates for our formulation and U are gradient updates for vanilla PPO, p is correlation coefficient between the Q function as St and negative of -oRR
This result becomes particularly impactful in sparse reward settings where the extrinsic reward exhibits higher variance by default. The formal analysis is presented in Appendix A.1 A.1
EXPERIMENTS
We use environments that serve great test suite.
Environments Used:
JJ al. 2024) library as it provides sophisticated
5

---

Published as a conference paper at ICLR 2026
Navigation:
The agent needs to navigate to the goal button. There are multiple obstacles that move arbitrarily in the environment thus hindering navigation. There are 3 difficulty levels Level 0. Level and Level 2 with increasing number of obstacles. We mark these environments as Navigation-LLevl-0) Navigation-LLevll- and Navigation-LLevel-2 respec- tively in the experiments hereafter.
Building: This environment requires the agent to proficiently operate multiple machines within a construction site, while concurrently evading other robots and obstacles present in the area. Similar to the Navigation environment, we experiment on all three difficulty levels and report the numbers with same nomenclature.
Fading: This environment requires the agent to reach the goal position, ensuring it steers clear of hazardous areas. However, the goal linearly disappears after 150 steps of the environment refresh, which provides an interesting and albeit unique challenge. Following a similar setup, we have three difficulty levels in this environment as well.
A visual representation of each of these environments is provided in section A.3
Reward Sparsity: In order thoroughly assess the algorithms in a sparse reward setting. we utilize the default reward provided by the environments but at every K steps (with K = 25 following works like (Memarian et al. 202T) for sparse reward settings). Thus, in the total reward formulation discussed in section 3.1 we have (t) = Tewe (t) x 1 1t%K = 0j. This default environment reward simply the difference of the agent to goal relative distance between timestep t and + 1, ie, Text 2 O if the agent moves closer to the goal (or stays at same distance) and negative otherwise. Another aspect that makes this reward setting more challenging that this r Teze (t) which is received at timestep / is local reward of improvement between state / and [+] I and not between / and ( K, thus providing a good testbed for high sparsity settings. We scale this reward by a factor of 10 to incorporate noticeable Text for the gradient estimations and policy updates.
Baselines- To perform an extensive evaluation of our method against the literature, we implement 6 baselines as follows. PPO (Schulman et al. 2017): which is the core algorithm that is being used to train most practical algorithms, especially the recent success of RL (Stiennon et al. 2022). PPO + Ent (Schulman et al., 2017]: is the variation of PPO that explicitly incorporates the entropy loss over the action distribution obtained from the policy network, ie, na (-1ss).. SRL (Surprise RL) (Achiam & Sastry) 2017): is one of the initial works which proposed two different notions of surprise based intrinsic motivation by modeling the state transition probabilities explicitly via a separate network. These are added the extrinsic reward Fewe (f) with some weighting factor. The first one is the transition probability of st+1 given current state and action pair as Pa (st+1 1 st) (where the dy- namics model ø' is parametrized as Gaussian MLP Regressor) whereas the second method learns a stream of the dynamics models ø' at different timesteps and then considers the intrinsic reward as Po. (8t4 |0,, - Po. ($1+1 |4,, st) for iteration difference 2. We call the first version as SRL-Std for standard and the second version as SRL-Diff. NGU (Badia et al. 2020): proposed an episodic memory based intrinsic reward formulation. They construct an explicit explicit embedding model that is trained simultancously, which however also leads to larger number of parameters across the pipeline in comparison to the other methods. AIM (Drugkaa et al. 2021): constructs the intrinsic reward via the Wass-1 distance between a policy's 's state visitation distribution and specific target distribution. We use the continuous state/action extension as discussed in their work. MEGA (Pitis) ctt al. 20200:: which is a goal conditioned RL algorithm that defines a distribution over the goals and enforces the exploration of the sparsely explored areas of the goal distribution. We implement the algorithm under the PPO setup make it on-policy in order perform a more pronounced compari- son and leverage the policy improvements over the course of training. GCPO (Xudong et al. 2024): recent on-policy goal conditioned RL methodology which pretrains a goal conditioned policy via Behavioral Cloning and then perform an online self-curriculum style update to select goals from the MEGA based distribution fit and sampling from to fine-tune further. Algorithm of their work (Xudong et al. 2024) details the procedure. This method is on-policy by design.
Evaluation Methodology: We trained each of the models 5 times and then evaluated all the trained policies by rolling each of those 5 for 200 new episodes in the corresponding environments, thus providing a total of 1000 evaluation episodes in total and accounting for induced randomness due to initialization. For the main results in next section we compare the (i) The percentage of successful episodes for each method where success is defined as the agent reaching the goal ; (ii) The median number of timesteps taken to reach the goal (the maximum number of timesteps per episode is
6

---

Published as a conference paper at ICLR 2026
1000 default setting in the Safety Gym library) along with the 25th and 75th marks; (iii) The median environment reward obtained by each agent across the episodes. This is computed by considering the average reward in each episode and then computing the median across the 1000 evaluation episodes (this implicitly takes the episode length into consideration and thus provides a default normalization). We provide the core results and convergence analysis here with the parameter selection discussion in A.6] evolution of Tint during navigation in A.7, graph algorithm analysis
in A.9
A.12 runtime analysis of the methods in A.11
5.1
MAIN RESULTS
Success rate: Based on the results provided in figure we notice a consistent outperformance of our method against the baselines, particularly in the more challenging settings. For example, at Navigation-level-2, our approach achieves a success rate of 55.5%, representing an absolute im- provement of 16.8 percentage points over the strongest baseline (GCPO 38. 38).. At Building- level-2, our method reaches 88.4%, improving over GCPO by 32.7 points and more than double the performance of SRL-Std (38.8%). Even in moderately difficult tasks, such as Navigation-level- and Building-level-1, our method improves success rates to 99.6% and 99. 99,2%, compared to the best baseline scores of 84.0% and 86.4%, respectively. On the easiest tasks (difficulty 0), performance across methods is already near ceiling, but our method remains competitive, matching or exceeding the baselines. A few noteworthy aspects are (i) the fluctuation of the performance of PPO with entropy across the difficulty levels, where in some cases it substantially outperforms vanilla PPO, but much worse in Fading environment potentially due to over exploration while the goal vanishes in the meantime; (ii) GCPO first pretrains a policy using Behavioral Cloning and then fine tunes in an on-policy manner over trajectory distributions, whereas our method works from scratch which further substantiates our claims.
Navigution
Building
Fading
100
Success Ratt (56)
60
0
0
Difficulty Level
Dificuity Level
Difficulty Level
Ent
SRL-Diff
MEGA
NGU
AIM
Figure 2: Success rate (% of successful episodes out of the 1000) during evaluation for all methods across Navigation (left), Building (center) and Fading (right) environments.
Navigation
Building
Fading
Median Reward
0.02
0.01
0.00
Diffielity Level
Difficulty Level
Difficulty Level
PPU
PPU-bat
SRL-SId
SKL-Dif
MEGA
GUPO
NGU
AIM
Ouss
Figure 3: Median Reward during evaluation for all methods across Navigation (left), Building (cen- ter) and Fading (right) environments. The plots contain the 25th% and tht ticks.
Median Normalized Reward: The results are provided in figure 3 Across all the environments, our method achieves consistently higher normalized rewards, with particularly pronounced gains
7

---

Published as a conference paper at ICLR 2026
in the more difficult settings. For example, at Navigation-level2, method reaches median normalized reward of 0.0068, compared to 0.0017 for GCPO (a 4x improvement) and this reward near-zero negative values for all other baselines. Notably, our 25th percentile (-0.0017) is better than the median of PPO+Ent (-0.0018) and the PPO variants. Similarly, in Building-level. approach yields 0.0134, which more than triples GCPO (0.0041) and surpasses the upper quartile of every baseline, while their medians often remain close to zero or negative. In Building- level-1, our method reaches 0.0281, nearly doubling GCPO (0.0155) and lying well above the 75th percentile of all other methods, indicating robust shift of the entire reward distribution. Even moderately difficult environments such as dnvigation-level-- and Fading-level-1, our method maintains the highest scores (0.0249 and 0.0284, respectively), with our lower quartiles exceeding medians most baselines (e.g., our 25th percentile 0.0201 at Navigation- median of SRL-Std at 0.0050). On the easiest tasks (difficulty 0), all methods perform similarly, but our method consistently outperforms (e.g., 0.0309 at Navigation-level-O vs 0.0293 for GCPO).
surpasses the
Navigation
Building
Fading
Median Timestepo tleg seae)
10"
10"
2
Difficulty Level
Difficulty Level
Difficulty Level
PPO
PPO-Fent
SRL-Std
SRI-DiI
MEGA
NGU
AIM
Ours
Figure 4: Median Number of Timesteps per episode during evaluation for all methods across Nav- igation (left), Building (center) and Fading (right) environments. The plots contain the 25th and 75th% ticks
Navigation
Building
Fading
6000
Loss Platean Iteration
4000
2000
2
Difficulty Level
Difficulty Level SRL-Dil
Difficulty Level
SRL-Sid
MEGA
GCPO
Figure 5: Comparison of the loss plateau iterations across the methods.
Median Timesteps to reach the goal: The results are provided in figure While difficulty level 0 across the environments is relatively easier for all the methods, the levels and provide vivid dif- ference in the performance of the methods. For instance, at Navigation-levell2, our method requires median of 242 steps, which almost half of GCPO (467) and far below Surprise RL variants 769 and 881. Our median of 242 lies even below the 25th percentile of GCPO which is at 258. Sim- ilarly, at Building-level-2, our method achieves 168 steps, whereas the next best (GCPO) requires 384, again placing our median earlier than the 25th percentile of all other methods. In Building- level-1, our approach achieves a median 77 steps, compared to GCPO's 124 and MEGA's 156, with our thth percentile (116.25) still lower than the median of the baselines. Even in moderately difficult settings, such as Navigation- steps to 87 and 73 respectively, with improvements of around 26% and 15% over GCPO (118 and 86), while remaining well below the lower quartiles of SRL variants (121 and 86). On the easiest levels (difficulty 0), where performance across methods is already near-optimal, method still
and Fading-level--. our method reduces the median
8

---

Published as a conference paper at ICLR 2026
achieves the lowest near-lowest medians (e.g., 53 steps at Fading-level-O vs. GCPO's 56). At the highest difficulty Fading-level-2. our method again demonstrates clear advantage. reducing the median to 248 compared to 543 (MEGA) 1000 for other methods, with our 25th percentile (85) substantially earlier than GCPO's 315. Furthermore, the median and at times the 25th percentile timesteps hit the maximum limit of 1000 for the harder environment in some of the baselines, thus justifying the efficacy of our proposed intrinsic reward mechanism and its role in achieving the tasks. Furthermore, these significant performance improvements are achieved with high computational ef- ficiency, incurring only a marginal runtime overhead (1. (1.1x-1) 1.222xx vs. PPO) per episode training, as shown in our detailed runtime analysis in Appendix |A.10 A..I] This is however completely counterbalanced by much faster training convergence of our method as seen in figure 5
5.2 CONVERGENCE ANALYSIS
In order to empirically justify the claim lemma 4 we perform two analysis here - (i) comparison of the training iterations at which the loss plateaus across the respective methods (ii) the correlation of our proposed Reir (negative sign as discussed in the lemma) against the learned value function V during evaluation phase of the same 1000 episodes (once the trained has completed, since it is much less practical to discuss about the learned value function otherwise). While our theoretical claims offered for PG since it is harder to characterize PPO style algorithms, we still observe that our results hold well. We also point to remark 7 about the reason for computing these correlations against the value function.
The bar plots for plateau iterations are provided in figure S Uniformly across all settings, we observe faster convergence than PPO, espe- cially for easier environments where the corre- lations in figu higher (with negligible p- values). For the easier level-O difficulty across the environments, GCPO and SRL-Std also ex- hibit faster convergence. However we note that GCPO leverages a pretrained policy during training which substantially increases its over- all time. Furthermore, similar to the main re- sults discussed earlier, PPO+Ent exhibits vary- ing behavior against PPO in convergence as well. For Navigation and Building environ- ments, we also note some of the basclines ex- hibiting very delayed convergence towards end of training iterations for levels 1 and 2. Quantitatively characterizing, for eg over Building-level-O PPO has plateau at 1636 whereas ours at 576 thus the ratio of 0.35 whereas the corresponding cor- relation value of 2 2p 0.38, thus providing very strong justification of lemma A We observe similar behavior for other environment and difficulty levels as well, albeit with some margin of er- discussed in remark (7) and accounting for the difficulty of approximation of the value and Q
Mediam S Spearmen Correlation
1.0
pr100-25
0..6
0.4
0.2
Leveld
Feval
0.0
Novigation
Building
Fading
Environment
Figure 6: Spearman Correlation coefficients be- tween the value function and Reff-
functions (Moon et al. 2023: Engstrom et al. 2020).
CONCLUSION
We introduce a novel intrinsic reward formulation based on the notion of "Effective Resistance" from spectral graph theory. By providing extensive empirical results guided by the theoretical con- tributions, we show that this formulation works well across a diverse suite of tasks and only incurs a marginal increase in the runtime over baseline PPO but provides much faster convergence during training. We further conduct experiments to discuss the behavior of trained policies over the evolu- tion of our intrinsic reward, goal visibility during navigation and analysis of key hyperparameters. We expect to drive the community's attention to graph based formulations, such the one proposed in this work, as these provide a higher degree of interpretability as described earlier in figure along with the performance improvements.

---

Published as a conference paper at ICLR 2026
7 REPRODUCIBILITY STATEMENT
Adhering to the guidelines, we have provided all the relevant implementation details in section A.5 For the theoretical results, all the relevant assumptions, definitions and proofs are detailed in sec- tion A.1
REFERENCES
Joshua Achiam and Shankar Sastry. Surprise-based intrinsic motivation for deep reinforcement learning, 2017. URL htttt://aaxxxi wttp://.....//a///......... 01732
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. Advances neural information processing systems, 30, 2017.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay, 2018.
URL /ttetts::/arxiiee org. abs 707. 01495
Luka Antonyshyn and Sidney Givigi. Deep model-based reinforcement learning for predictive control of robotic systems with dense and sparse rewards. Journal of Intelligent & Robotic Systems, 110,3):100, 2024, ISSN 1573-0409. doi: 1010077/108460024021111.. URL
Adrià Puigdomënech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies, 2020. URL
https:
//arxiv.org/abs/200/3
Nikhil Barhate. Minimal pytorch implementation of proximal policy optimization. https://
github. www.///khiilaaaaaat999/// PPPoohh 2021.
Andrew G Barto. Reinforcement learning: An introduction. by richard's sutton. SIAM Rev, 6(2):
423, 2021.
J. Baxter and P. L. Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelli- gence Research, 15:319-350, November 2001. ISSN 1076-9757. doi: 10. 161 //13/jair.806
Béla Bollobás. Random Graphs. Cambridge University Press, 2nd edition, 2001.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. URLLsattps://arx.v.com wttp://gggabb//ooo// 100006.154011 01540
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei Efros. Lcrge-scale study of curiosity learning. arXiv preprint arXiv: 180..04888000 2018.
Meng Cao, Lei Shu, Lei Yu, Yun Zhu, Nevan Wichers, Yinxiao Liu, and Lei Meng. Enhancing reinforcement learning with dense rewards from language model critic. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 91 9119-9138, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. (006653/11/224.mmm/l/l m55 URL https://aclantholooe org. 2024 emnlp cacpp-mmaaa in 5157
Minjun Choi, Junhyeong Ryu, Yongseok Son, Sungrae Cho, and Jeongyeup Pack. Lidar-based local- ization for autonomous vehicles survey and recent trends. In 2024 15th International Conference on Information and Communication Technology Convergence (ICTC), pp. 456-460, 2024, doi: 10.1 109/1CTC62082.2004 201.200882..22..11733346..
Fan RK Chung- Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Charles J. Colbourn. The Combinatorics of Network Reliability. Oxford University Press, 1987.
10

---

Published as a conference paper at ICLR 2026
Rati Devidze, Parameswaran Kamalaruban, and Adish Singla. Exploration-guiide reward shaping for reinforcement learning under sparse rewards. Advances in Neural Information Processing Systems, 35:5829-58422 2022.
Ishan Durugkar, Mauricio Tec, Scott Niekum, and Peter Stone. Adversarial intrinsic motivation for reinforcement learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 0622-8636.
Curran Associates, Inc.. 2021. URL https: http:::://roceeeinsss..auus pappp pdf
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry, Implementation matters in deep policy gradients: A case study on ppo and trpo, 2020. /ttpsttts///arii.oorrrr abs 2005. 12729
E. J. Evans and E. Francis. Algorithmic techniques for finding resistance distances on structured graphs, 2021. ARRLtttss////ati..oto wttp:///.wrrraa/////e//// 011.//11080099933
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2): 298-305, 1973.
Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithmms, SODA '05, pp. 156-165, USA, 2005. Society for Industrial and Applied Mathematics. ISBN
search meets graph
0898715857.
Joshua Hare. Dealing with sparse rewards in reinforcement learning. 191.09991 2019.
arXiv preprint
Jiaming Ji, Borong Zhang, Jiayi Zhou, Xuehai Pan, Weidong Huang, Ruiyang Sun, Yiran Geng, Yifan Zhong, Juntao Dai, and Yaodong Yang. gymnasiummm A unified safe reinforcement learning benchmark, 2024. URL
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world, 2020. URL https://arxiv org/ abs /ttp//abs////222 2..00.0.3322
Sining and Ahad N. Zehmakan. Graph-based generalization of galam model: Convergence time and influential nodes. Physics, 5(4):1994-1108 2023. ISSN 2624-8174, doi: 10.3390/
physic55040071. URL https: / wwww wwwwwwppp..... cwm/2624 20t/://00222222227///7/7777
8174/5/4/71
You Li and Javier Tbanez-Guzman Lidar for autonomous driving: The principles, challenges, and trends for automotive lidar and perception systems. IEEE Signal Processing Magazine, 37(4): 50-61, July 2020. ISSN 1558-0792. doi: 10.1109/mmpp22002227333.. URL. htttp://xx. doi org/orr/10.1 109/MSPPPPPPM 2020 2973615
Yunge Li and Lanyu Xu. Panoptic perception for autonomous driving: A survey, 2024. URL ht.tps://axxis
15388
Bo Liu, Yifeng Zhu, Chongkai Gao, Yihao Feng, Qiang Liu, Yuke Zhu, and Peter Stone. Libero: Benchmarking knowledge transfer for lifelong robot learning, 2023a. URL https::/arxxii.
orq/ hbs//bb//aa 2306. 03310
Grace Liu, Michael Tang, and Benjamin Eysenbach. A single goal is all you need: Skills and explo- ration emerge from contrastive rl without rewards, demonstrations, or subgoals. arXiv preprint D.Xiv:2408.05880 2024.
Minghuan Liu, Menghui Zhu, and Weinan Zhang. Goal-conditioned reinforcement learning: Prob- lems and solutions. arXiv preprint arXiv:2201.0m 082999, 2022.
Xiaotian Liu, Hector Palacios, and Christian Muise. Egocentric planning for scalable embodied task achievement, 2023b. URL htts::// http://aaxxxvo.o/aaaaaa 2306. 01295
Oier Mees, Lukas Hermann, Erick Mosete-Beass and Wolfram Burgard. Calvin: A benchmark for language-condittooned policy learning for long-horizon robot manipulation tasks, 2022. URL
httppss/aarriv.orr//////22...

---

Published as a conference paper at ICLR 2026
Farzan Memarian, Wonjoon Goo, Rudolf Lioutikkr,, Scott Nickum, and Ufuk Topcu. Self-supervised online reward shaping in sparse-reward environments, 2021. URL htttps:/arxiv..Kr
abs/2103. 04529
Pawel Miera, Hubert Szolc, and Tomasz Kryjak. Lidar based based drone navigation with reinforcement learning, 2023.
14313
Seungyong Moon, Jun JunYeong Lee, and Hyun Oh Song. Rethinking value function learning for gener-
alization in reinforcement learning, 2023. htttlt:t/////axvvv.ooo
09960
Ofir Nachum, Mohammad Norouzi, George Tucker, and Dale Schuurmans. Smoothed action value functions for learning gaussian policies, 2018. URL htttps//arrxiv.or//abs////
02348
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. Advances in neural information processing systems, 32, 2019.
Seohong Park, Kevin Frans, Benjamin Eysenbach, and Sergey Levine Oghench: Benchmarking 20092
offline goal-conditioned rl, 2025.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pp. 2778-2787. PMLR, 2017.
Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7750-7761, PMLR, 13-18 Jul 2020. URL
mlr prwss wttp:/11t99pptt s20a html
Theodore S. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall PTR, 2nd edition, 2002.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL /
Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback, 2022. URL
https://arxiv orggabs///000000/
Gautham Vasan, Yan Wang, Fahim Shahriar, James Bergstra, Martin Jagersand, and A. Rupam Mahmood. Revisiting sparse rewards for goal-reaching reinforcement learning, 2024. URL
httpp://aarxv..rrraa////20..... 00324
Luca Viano, Yu-Ting Huang, Parameswaran Kamalaruban, Adrian Weller, and Volkan Cevher. Ro- bust inverse reinforcement learning under transition dynamics mismatch. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Process- ing Systems, 2021. URL
net. http::/www....toooooeoooeeeeaaaa
Tongzhou Wang, Antonio Torralba, Phillip Isola, and Amy Zhang. Optimal goal-reaching reinforce- ment learning via quasimetric learning. In International Conference Machine Learning, pp- 36411-36430. PMLR, 2023.
Vikram Waradpande, Daniel Kudenko, and Megha Khosla. Graph-based state representation for deep reinforcement learning, 2021.
Guangtong Xu, Tianyue Wu, Zihan Wang. Qianhao Wang, and Fei Gao. Flying on point clouds with reinforcement learning, 2025. URL
Gong Xudong, Feng Dawei, Kele Xu, Bo Ding, and Huaimin Wang. Goal-conditioned on- on-policy inforcement learning. In The ehihth- Annual Conference on Neural Information Processing Systems, 2024. URL httllhttts:///peeeeeet ew net. wwwt http:/mmmm...ppP7..........
12

---

Published as a conference paper at ICLR 2026
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient, 2022. URL httph:h///// aaxiv.iiivv../..a www.xx....ggaaaa.o wwg. httpg//bs/2100...0 21433311733
Xiao-Dong Zhang. The laplacian eigenvalues of graphs: survey, 2011. URL https://arxix
org/aba 1111.22112 2897
Xiang Zheng, Xingjun Ma, Chao Shen, and Cong Wang. Constrained intrinsic motivation for rein- forcement learning. arXiv preprint arXiv:2407.0924/ 2024.
Yongle Zou, Binlong Wu, Xinglin Wan, and Peipei Meng. A survey of lidar-based 3d slam in indoor degraded scenarios. 2024 6th International Conference on Frontier Technologies of Information and Computer (ICFTIC), pp. 856-861, 2024. doi: 10.1 1.110//CFT1664448.2000 10912938.
Markel Zubia, Thiago D. Simão, and Nils Jansen. Robust transfer of safety- coiity-conttrained reinforce- ment learning agents. In The Thirteenth International Conference on Learning Representations, 2025. URL https: wwoeeeeeiiew.eeeeoorrnia...
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 DETAILS OF THEORETICAL ANALYSIS
This section provides the formal assumptions, definitions, remarks, and complete proofs for the theoretical results presented in Section
A.1.1 CORE ASSUMPTIONS
Assumption (Bounded Sensing Range). The agent has a fixed sensing radius R > Objects beyond distance R from the agent are not included in the graph Ge. The environment is bounded: agent and objects are confined to a domain Q C I2, with diameter D < co. This ensures finite graph sizes and well-defined computational procedures.
Assumption (Consistent Graph Construction). At each timestep t, the graph Gt (V. Ee, Wo) is constructed deterministically relative to the agent using a fixed rule:
All objects within radius R are connected to the agent
Edge weights represent the notion of vicinity/closennss, which we assume E (0,
The goal is included if is within
Assumption 3 (Bounded Object Dynamics). All objects (including the goal) move with bounded velocity: l| < Vmax. The agent's 'ss velocity is similarly bounded: l|va(t)l S Umax. This
prevents arbitrary changes graph structure. This assumption realistic for any practical envi- ronment.
Assumption (Connected Goal Path). There exists at least one continuous path from any reachable agent position to the goal through free space when both are in the sensing range. This ensures the task is well-posed, as otherwise
Assumption (Graph Size Bounds). The number of nodes in G. is bounded: Amin S Vel S Timax for all t. This ensures computational tractability.
Assumption 6 (Goal Visibility Model). The probability of maintaining goal visibility is monoton- ically increasing function of the graph's current algebraic connectiviry. We model this relationship
Ellgoatt + 1)|9.) 11xp]))xe
for some constant C4 O. This is justified as higher connectivity, which implies both a greater likelihood of maintaining proximity (via lower effective resistance) and a lower likelihood of goal path occlusion due to greater number of redundant pathways. This exponential form form is standard modeling choice in network reliability and percolation theory (Colbourn) 1987: Bollobás 2001
Remark (Justification for Assumption (). This assumption formalizes the intuitive link between the abstract graph connectivity and the tangible task objective of maintaining goal visibility. The justification rests on two physical components of visibility: proximity and occlusion, both of which are positively influenced by higher algebraic connectivity (R).
1. Proximity: A policy that is incentivized to increase connectivity will naturally favor actions that maintain proximity to the goal. As established in Lemma [ high algebraic connectivity (k) corresponds to low effective resistance (Rey), and our intrinsic reward encourages the agent to minimize this resistance, thus reducing the "difficulty" of paths to the goal.
2. Occlusion: A more connected graph implies the existence of more redundant pathways between the agent and the goal. the physical environment, this translates to having more alternative lines-of-sight, which reduces the probability of total occlusion by dynamic obstacles.
Given that the probabilities of maintaining proximity and avoiding occlusion are monotonically increasing functions of K, their product (the probability of maintaining visibility) is also monoton- ically increasing. The exponential form 1 exp(-Cat is standard modeling choice for such phenomena because respects probability bounds [0, 1), captures the intuitive notion of diminish- ing returns, and is mathematically tractable. This functional form is well-established in related
14

---

Published as a conference paper at ICLR 2026
fields such network reliability analysis |Colbourn 1987, wireless communication (Rappaport 2002). and graph connectivity studies (Bollobás 2001) ), validating its appropriateness for modeling
conneeeivttyydeeeeeent events.
A.1.2 KEY DEFINITIONS
Definition 1 (Graph Laplacian). For graph Gr = (V,, Es, W/) with n nodes, the Laplacian matrix L(t) E n
x is defined as:
Enes wal(() Wislt)
ifi=
(ig(t)
if (i, E Es otherwise
The Laplacian is the core of graph theory (Zhang 2011 Definition 2 (Effective Resistance). For nodes i and j in graph Gt. the effective resistance is:
Reglin = (ey" (1)(e,-))) -ey)
where eg is the k-th standard basis vector. This measures the "difficulty" of information flow be- tween nodes and j. Definition 3 (Algebraic Connectivity). The algebraic connectivity of graph Ge is:
<(Gi) )²(I(t))
where X2 is the seoond-mmallest eigenvalue of the Laplacian. Higher values indicate better connec- tiviry. For disconnected graphs, r(G,) O.
Definition 4 (Edge weights Wi.)). The edge weights in W. function of the state/observation vector 8t, ie,
wi.((1) = hst)
described via algorithm 7 Here, we loosely define the function via indexing (i,5), but based on the aforementioned assumptions, all such higj
1. are continuous
2. Lipschitz w.e. to the input St thus
[hrr($t) hir S Llst str
and since the change is the state vectors is also bounded, we have that
[ha (sw)) S L t'l
where E and E are the respective Lipschitz constants
3. bounded between (0, 1] (notice exclusive as discussed previously)
Definition (Robust Navigation Policy). policy x. is (c, 6, -robuustt if:
1. It reaches the goal with probability 2 1 - within T steps
2. It maintains goal visibility: Eran E g() 2 (1 -1-
3. It preserves connectivity: Eynu [x(G:) 2 8 for all t
This definition captures both task success and structural stability.
A.1.3 PROOFS FOR MAIN RESULTS
Hereafter, we denote Rull as the Effective Resistance between agent and goal node, ie, Ren(t) Rer(A, A, y; Ge)
Lemma T Under Assumptions 15 the temporal derivatives of effective resistance and connectivity satisfy:
dRen(t) dx(g,) dl
dr((G)) 2
dl < -Ca
dl
15

---

Published as a conference paper at ICLR 2026
Proof. The proof establishes the inverse relationship between the rates of change of effective resis- tance and algebraic connectivity by analyzing the time derivative the spectral decomposition of Ren-
Step 1: Differentiability Framework. As established in the lemma statement, we consider a con- tinuously evolving graph Ge- As the positions of all nodes are differentiable functions of time, making the edge weights (t) and consequently the Laplacian matrix L(t) differentiable. For generic graph perturbations, the second eigenvalue s(t) A2(t) is simple (has multiplicity I), which ensures that x(t) and its corresponding eigenvector (2) are differentiable functions of time.
Step 2: Spectral Decomposition. Our starting point is the spectral representation of the effective resistance between the agent node A and the goal node g:
Rell Σ 2= (t(t)
Cg. cg, (()))²
where (t) and (t) are the eigenvalues and orthonormal eigenvectors of L(t), respectively. From this definition, Ren is also differentiable wrt time.
Step 3: Time Derivative Calculation. We now take the total derivative of Rer with respect to time t. Applying the chain rule to each term in the summation:
dRaa dt
d
d (lea - cg. v(()))))
(eA Cg. 1;(1)) + 2x(t) dt
dt (1)
Let's analyze the derivative of each part:
The derivative of the eigenvalue term is: dr (x(())
d 1
d):(1) A.(r)a
de
The derivative of the eigenvector term involves the derivative of the eigenvectors, Substituting the first part back, we get:
das
d'Rell dt
dd:(t) (t)2 dt (cA Cg. cg, ot()) + terms involving Σ Xt)y
dus
dt
For graph evolutions which the dominant effect on the change in resistance comes from the change in the eigenvalues, particularly the smallest non-zero one, A2(t) k(t), the change in eigenvectors typically has smaller impact. Thus, we can approximate the relationship by focusing on the most significant term in the sum, which is the term for 2:
dRaal
dxz(t)
dx(t), (EA eg. 02(1) + O
(EA eg. 02()) O(Eu) mil)2 dt
di
2221) di
(cea) for ds(t)
x(oja (cA- (()))) + 0
Step 4: Sign Analysis. We now analyze the terms in the relationship derived above to establish the final inequality. Let's define term C(t) xay (eA Eg. 2
For a connected graph, the algebraic connectivity x(t) >²(t) is strictly positive. There- fore. x(r)² 0.
The term (E,A cg. (t)) represents the squared projection of the vector (e.A eg) onto the Fiedler vector (Fiedler 1973) Uz))). The vector (cA eg) is orthogonal to the first eigenvector Un (t) (the constant vector). For any non satpahoologiaal connected graph, (e eg) is not orthogonal to the Fiedler vector oz(t), ensuring that (e,4 - cg. (2))))² > 0 with high probability.
16

---

Published as a conference paper at ICLR 2026
Since both components of C(t) positive, C(t)
0. Our relationship is thus:
d'Relt
-(t) dx(t) dt
dt
To arrive at the form in the lemma statement, we multiply both sides by de((),
d'Renl dt
dr((t) (dade)
(d((t)
drc(t)
CC(()
C(1)
dt
dt
Since Ctt) is strictly positive and bounded below by some constant C₁ over the compact state space over which we have the possible graph configurations, we obtain:
dRaa dk(tt) S -C1
dn((t)
dt dt
dt
This establishes the inverse relationship: when connectivity increases de decreases dede" 0), and vere-versa.
0), effective resistance
Remark Lemmal establishes that higher connectivity directly reduces effective resistance, mak- ing the goal more accessible. This is intuitive: more connections provide alternative paths, reducing the "electrical resistance" between agent and goal.
Lemma 2 Under Assumptions 1 for any action ag:
(s(Ge+1) n(Ge)] S 6max
where max C2 Ammax + k for constants C2, C3 > O, and k is the maximum number of nodes that can be added/removed per timestep (we discuss its practicality in section A..6).
Proof. The change in the graph structure from G. to G--1 is a result of two distinct processes: (1) discrete changes in the graph's 's topology as nodes and edges are added or removed, and (2) continuous changes in edge weights due to the movement of the agent and objects. We will bound the impact of each process on the algebraic connectivity x(t) and then combine them.
Case 1: Bounding the Effect of Topological Changes (Node Addition/Removal), This compo- nent bounds the change in connectivity when the set of vertices V2 changes.
Bounding the Number of Node Changes (k): Nodes are added or removed when objects cross the agent's sensing radius R. By Assumption 3 the agent's velocity is bounded by Umax and object velocities are bounded by Vmax- The maximum relative speed between the agent and any object is thus Umax + Vmax- time interval At, the number of objects that can cross agent's 's radial boundary is finite and bounded, as it depends on this maximum speed and the density of objects the environment (which is finite by Assumption 55). This implicitly bounds the value of k by algorithm
Bounding the Connectivity Change: Standard results in spectral graph theory provide bounds on the change in x when i nodes are removed or added. A simple bound is [ S
k- Wmaxx where Wmax is the maximum possible edge weight, with 0 Wii Σ as discussed earlier.
Combining these, the maximum change in connectivity due to topological changes, which we denote AK is bounded by constant factor of k:
A modes <
Case 2: Bounding the Effect of Edge Weight Perturbation. This component bounds the change in connectivity when the graph topology is fixed but edge weights change due to movement.
Bounding Weight Changes (Aw)ax): As previously discussed, since 0 < Wiij S 1, thus
0 < A AWmax <
17

---

Published as a conference paper at ICLR 2026
Applying Matrix Perturbation Theory; By Weyl's inequality, the change in any eigen- value of Hermitian matrix is bounded by the spectral norm of the matrix perturbation. Applying this to the Laplacian matrix L(t):
1x(9++1) x(G)) (2(Lx41) (2( S [14 - Lel12 ||
The spectral norm | is itself bounded by function of Awmax and the graph's 's max- imum degree (which is bounded by Remax under Assumption (5). This relationship can be expressed as || ||ا I C2 Ammax for some constant C2 which depends on the environ- ment dynamics.
Combining these, the maximum change connectivity due edge weight perturbations, denoted A weights |
is:
Ax (weights S C² - C2
Combined Effect. To find the total bound, we the triangle inequality. Let G be hypothetical graph with the same nodes as Gr but with the edge weights of Ge+1. The total change can be decomposed as:
(n(9(41) -(g.)l = (n(9(41) (((9) + k())) x(9.))
- + [k((]) x(()))
Fdffect of mode changes
Effecct of weight changes
The first term is bounded by A nodes and the second is bounded by |Ax weights Therefore, the total change is bounded by the sum of the individual bounds:
(m(G(+1) <(G)) S Axl weights Ari/modes
S C2 AWmax + k
This sum defines the maximum possible change in connectivity in a single time step, 6max-
Corollary 2 (Continuity and Lipschitzness of k almost surely, a.s.). The commectivity Ks k(G)) continuous and Lipschitz continuous with respect to time
Proof. This corollary is direct consequence of the bounded change in connectivity established in Lemma 2
We prove each property separately.
Part 1: Proof of Continuity
To prove continuity at a time f, we must show that limac-so (x()++a)) k(G)) = 0.
From the result of Lemma for any time interval At > O, the change in connectivity is bounded by:
[m(C++Ae) - k(G)) < 8max
Substituting the expression for 8max:
[n(G+a))) k(G)) I C2 AW (At) k(Att
where define Awmax (At) the change in the maximum edge weight difference and k(At) is the number of nodes that can enter or leave the sensing radius within the time interval At. We discuss each of these separately:
1. As defined earlier in definition we have Aw (At) < Eat
2. For k(At) we note that as the time interval shrinks (At - 0), the maximum distance any object can travel also shrinks. While there exists some cases when the & can change somewhat arbitrarily even as At 0 (such as when all objects are moving radially inwards towards the agent and abruptly cross cross within the sensing radius R), considering all possibilities the probability of such events P(g) Loosely speaking, such events have measure 0 and never occur almost surely, a.s and thus we have almost surely that limAt-o k(A()
where & (k(At) >> Rmmin )-
18

---

From the Published as a conference paper at ICLR 2026
Now, taking the limit of our inequality as At 0:
Ar+ (<(++a))) - x())) v lim [C2A + k(At)] =
lim
At-0
which establishes the continuity for the function k(t) almost surely.
Part Proof of Lipschitz Property
To prove Lipschitz continuity, we must show that there exists a constant Lx >> O Ouch that for any two times & and tz:
(m(()g)) x(9r)) S fx - tal
First, we establish bound on the magnitude of the time derivative of connectivity, dx inequality in Part 1, we can divide by At:
|r(9 a1) n(Gi) C2 C+
M(t))
At
At
Taking the limit At + O, the left side becomes the definition of the magnitude of the derivative.
The term k(Ac) represents the instantaneous rate of nodes crossing the sensing boundary, which almost surely (as discussed above) is a finite value bounded by the environment's dynamics. Let's call the maximum possible rate krnte-
dx
S C2
L
Kyate
This shows that the derivative of the connectivity function is bounded. Let's define this upper bound as the Lipschitz constant, T,g:
:= + kirate
Now, using the Fundamental Theorem of Calculus for any 4, la (assuming 4 < la without loss of generality):
<l12) - -(()) S.a dn(s)
ds
ds
Taking the absolute value of both sides and applying the triangle inequality for integrals ( fds s [((dds):
(m(t2) - x(tr)) 1/a
dr((s) ds
dk((s)
ds
ds
ds
We can now substitute our bound for the derivative's magnitude:
- x(ti)= 5 1/ L,ds
Evaluating the simple integral gives:
(m((2) k(tt) & Lxltz 11l
This result can be written for any t,. t2 as (n(t2) - k<fr)l s Lxltz - tzl. which proves that x<() is almost surely Lipschitz with constant L..
Remark 3. Lemma 2 ensures that connectivity cannot change arbitrarily fast, providing stability for the learning process. The bound increases with agent/object speeds and decreases with minimum graph size, which is intuitive.
Lemma 3 (Policy Updates):
The intrinsic reward (t)(() is positively correlated with the one-step change algebraic connectivity, Ax(l) = x(G++1) (G.).
Proof. The proof relies showing that actions which increase connectivity receive higher intrinsic rewards expectation. We analyze the immediate reward rim (t) based on the outcome of an action.
1. Case 1: Goal Visible (1gaat( (t) 1, 1 goa + 1): The reward is (im(t) Rn (t).
From Lemma [ an increase connectivity (Ax > 0) implies a decrease in effective resistance (AR 0). Thus, in this case, Fin 0.
19

---

Published as a conference paper at ICLR 2026
2. Case 2: Goal Lost (Igealt) (t) 1, goaal (t 1) 0): The reward is large penalty (t)
-5. Losing the goal node constitutes a major degradation the graph structure, causing a significant drop in connectivity (Ax << 0).
3. Case 3: Goal Recovery (1 (t) O, geai + 1): The reward large bonus (l) +B. Recovering the goal node is major structural improvement, causing significant increase in connectivity (Ax >> 0).
In all cases, there is a strong positive correlation between the sign of rim (t) and the sign of Ak(t). Therefore, actions that are expected to increase connectivity will yield higher expected intrinsic reward.
Remark 4. Lemma 3 shows that our intrinsic reward is well-posed. Since policy gradient methods update policies to increase the likelihood of actions that lead to higher rewards, this positive corre- lation ensures the agent will learn to favor actions that preserve or enhance the graph's 's structural connectivity.
Theorem | Under Assumptions 6
a policy л² that maximizes the expected return with our effec- tive resistance-based intrinsic reward is (e, -robbuus
Proof. Part 1: Connectivity Preservation
1. Optimality Condition:
Say the policy x² maximizes ( = Be 7'(xx((( + (T)]] At a local maximum, the policy gradient is zero: VaJ(m²) This im- plies balance between the gradients of the different reward components: V amn"(())) - -Va)ea(T").
2. Expected Change in Connectivity: From Lemma B we know that increasing intrinsic rewards (by virtue of policy updates that maximize the discounted reward) further leads to trajectories that increase connectivity It will avoid actions that needlessly decrease connectivity, especially if an alternative exists that is neutral or beneficial to the extrinsic reward.
3. Bounding the Expected Change:
The worst possible single-step decrease in connectivity is physically bounded by δmax, as shown in Lemma Since the policy π is optimized to maximize reward, and actions leading lower x are penalized by Tints the policy will learn to avoid these worst-case outcomes. Therefore, the expected change in connectivity under x' must be no worse than this physical bound: E [An] Z Smax- Substituting this gives the desired result: E ik(G+1)] 2 x(G.) 8max
Part 2: Robust Navigation We demonstrate that nं satisfies the three conditions of Definition 5
1. Goal Visibility Maintenance: By choosing 8 to be sufficiently large ( CCrollary I the penalty for goal loss, -8, dominates all other single-step rewards or costs. An optimal policy π will strongly driven select actions that maintain goal visibility avoid the catastrophic -3 penalty. This directly ensures that the expected time the goal is visible is high, satisfying condition 2: E 1 [t) Z 5)T.
2. Connectivity Preservation:
This follows from Part of this theorem and the result above. Since the agent maintains goal visibility most of the time, its behavior is primarily governed by the intrinsic reward Pim ARer.. As established, optimizing this reward preserves connectivity. Thus, the expected connectivity under =² will remain above some positive threshold 6, > O, satisfying condition above.
3. Goal Reaching Probability: With goal visibility maintained (from point 1) and connec- tivity preserved (from point 2), the agent has a consistent view of the goal and receives a dense, informative reward signal (rmm) that guides it towards more "accessible" configura- tions. This effectively transforms the sparse reward problem into one with continuous guidance signal. Standard RI. convergence results apply, showing that an agent in this
20

---

Published as a conference paper at ICLR 2026
setting will learn policy that reaches the goal with high probability, 1 e, satisfying condition 1.
Since 'T" satisfies all three criteria, it is, by definition, (e, d, -robuust policy.
Remark 5. Theorem Desaabisses that our effective resistance-based intrinsic motivation naturally leads robust navigation policies. The key insight is that optimizing for goal accessibility (via effective resistance) inherently promotes graph connectivity, which in nurn supports reliable goal reaching and visibility maintenance.
Corollary I For practical implementation, choose B 2 C max (raa( a)) and a 2 C
m8X.. [
Amax C1
Proof. This corollary provides design principles derived directly from the theoretical results.
Choice of 3: The role of the =3 reward is to make goal visibility transitions the most salient events for the learning agent. To guarantee that the agent prioritizes maintaining or regaining goal visibility over any other immediate reward, the magnitude of ß must exceed the maximum possible value of any other reward or cost achievable in single step. Setting 3 2 C maxx,a (s, for safety factor C' formally enforces this dominance.
Choice of at The role of a is to scale the intrinsic reward's influence on the policy up- dates. This influence must be strong enough to promote exploration based on connectivity, counteracting small extrinsic rewards that might otherwise lead the agent to degrade its connectivity. The term 8max from Lemma 2 quantifies the maximum possible one-step degradation of connectivity, while C1 from Lemma quantifies the sensitivity of the ward signal to connectivity changes. Combining these with the extrinsic reward value, the ratio m [naiss.)] thus provides natural scale for how much "work" the intrinsic Smav
reward must do. Setting proportional to this ratio ensures the signal appropriately weighted against the environment's 's dynamics, with the safety factor C" providing an additional buffer.
Remark 6. Theorem estaabisses that our effective resistance-based intrinsic motivation naturally leads to robust navigation policies. The key insight is that optimizing for goal accessibility (via effective resistance) inherently promotes graph connectivity, which in supports reliable goal reaching and visibility maintenance.
A.1.4 DETAILS CONVERGENCE AND SAMPLE COMPLEXITY ANALYSIS
Here, we provide the background and proof for the sample complexity result Section 4.1 We leverage the general sample complexity framework for policy gradient methods established by Yuan ct al. 2022).
Definition 6 (Policy Gradient Estimator). Let
(e) = EsNTo
Y (en((t)
1=0
be the expected extrinsic return and
Jr (0) = Eç
(t)
be the truncated version of it Additionally, let the GPOMDP gradient estimator Baxter & Bartlett 2001) for the finite horizon T and with m trajectories be:
m T-1 ΣΣ
Jr aa (f)
Vo log To 116))
2/ (t)
m
t=
k==
21

---

Published as a conference paper at ICLR 2026
Similarly, for our method, the estimator for the total reward Trotal Tea + af'i be denoted as V montoni)))
Assumption 7 (Smoothness and Truncation, assumption 3.1 and 3.2 Yuaa et al. 2022 The
objective function (0) is Lipschitz-smoon with the constant G 0. The truncation error of the finite-horizon objective (()) w.rt the original objective Jex is bounded by constants D, D'
Assumption 8 (ABC Condition (Khaled Richtárik] 20201). Let J supg (en. There exist
non-negative constants A, B, C. such that the policy gradient estimator J() satisfies:
E J (0)1 - 2A(J* - Jen(O)) Vi +C
Under these conditions, the sample complexity to find an e-approximate stationary point is derived by Yuan et al. 2022) follows:
Theorem 2 (Sample Complexity of Policy Gradient, Thm 3.4 in Yuan et al. 2022 ). Under As-
sumptions 7 and 8 to find a point such that [[] S 6, the number of iterations required
is bounded by:
(3)
126gG U
120g A 20 e² e2
B,
2
where 6n J J' is the initial suboptimality gap.
Proof of variance reduction in lemma
4 with sample complexity bounds using Pint
Lemma For the intrinsic reward be (f) Rer((t) Ret(tt + 1). The policy gradient estimator for the total reward satisfies:
Almost Unbiased Estimator: E[V TT.maal) ~ (o))
2. Variance Reduction: Crotal & Cewt p²). where p = Corr (oeeaQeet($t,. ac), - (s))(s:)).
Proof. Part Almost Unbiased Gradient Estimator: The sum of intrinsic rewards from time to finite horizon 7 forms telescoping series:
Σ Tint (k)
Σ k=t
n k (Rot(()) - Ret(( + 1))
(4)
T-1
Renr(()) +
k-t-1 Σ k=H+1
x ( 18Re - T-1-11 RRa((T))
(5)
As the value of y R (0.99 used in our experiments and commonly across the literature, table we note that all the terms but (e) become negligible comparison, ie _k=++1 - x (? 1)RoF((s)) -
+ 0. Thus the total reward-to-go admits the form Quoai (st, as) R Qoa( a.) + (R.(((). Since the second term depends only on the current state, we can consider b(sz) aRe (t) state dependent baseline. is foundational result of the policy gradient theorem that subtracting a state-dependent baseline b(s;) from the returns does not change the ex- pectation of the gradient. Therefore,
B mJ soual (0) E( sx)) exx.
Part 2: Variance Reduction. The constants B and C' iimprrtant components in the variance of the reward-to-go estimator V Var(Q(st, at)) in the ABC condition and adapting to our formulation of the second moment of the gradient [E[] Jonal [1) will affect values B and C' in the bound of the assumption. Thus we focus on providing an argument reduce this. Essentially.
Var(Quota) Var Var(Qex b(st))
From the literature, we know that the optimal baseline that minimizes variance the value function itself. Our term -t) is designed proxy for the value function: it is low when far
22

---

Published as a conference paper at ICLR 2026
from the goal (low expected return) and high when near the goal (high expected return). This is essentially what we justified empirically in the correlations plot 6 of section 5.2 where we showed a strong correlation between (t) with the value function.
Using the standard definition of Var(X - Y) Var(X) Var(Y) YY),, that:
Var b(s=)(()))))))))))))))) Var(aauruu Var(b(s.)) - x px Var(Qua)) x (Var(b(s.) (6)
where / = Correlation (Qx.: ((+))
As discussed in implementation (sections A.5 and A.6 we have (t) (Feaa (t)) and thus
within reasonable approximations we consider ar st)) = O(V This leads to the
Var(Qes b(s:))
2p))
The larger this correlation coefficient p. the more improvement we expect in the sample complexity and thereby the convergence.
This formulation thus leads to a direct reduction the variance-dependent constants and in assumption 8 as Broeal O (B 2p)) as well as Croma ((Cext 2p)) which even with relatively weaker correlation of p 2 0.5 leads to improvements. Especially in the sparse reward settings where Qext has high variance, a high correlation leads to substantial variance reduction.
Plugging the above results in Thereom 2 and noting that in sparse reward settings the terms B as well 2C in the complexity bound are the bottleneck, we have the following version of the improved sample complexity bound:
as 22
126g
126g
2Ctoral ?2
Utotal 2
118x
Biotal
2
where Usoal are the number of gradient iterations in our case. Even with Avnal Rs Aext to obtain an 6-accurate solution, ie,
Uwial ( 2p)
This justifies the faster convergence we observe empirically in section 5.2 of the main paper.
Remark 7. We note that in the implementation of PPO algorithm, for which we use the above policy gradient bounds as a proxy, we only learn to approximate the value function v via neural network and not the Q function environments where the agent and object dynamics are continuous, we expect the value function and Q function exhibit high correlation (following works such Nachum et al. (2018) that focus gaussian smoothed version of the Q function), ie, the states with very high value function with high probability have actions leading to high discounted cumulative rewards. Thus the plots provided in section 5.2 serve again as proxy for what the correlation of the baseline - RoRg looks w.r. the Q function.
discussed in the proof above. Since we are dealing with
A.2
EXPERIMENTAL DETAILS
A.2.1 AGENT
We use the Point agent from the Safety Gym similar to (Zubia al. 2025 which has dimensions (using the notation (t) at the tth timestep for its vector):
Accelerometer in (-o0, oo)3, for measuring the acceleration in m/s²
Velocimeter in (-o0, o. for measuring the velocity of the agent in m/s
Gyroscope in (-o0, o.)?, for measuring the angular velocity in rad/s
Magnetometer in (-00, 0o)3, for measuring the magnetic flux in Wb
23

---

Published as a conference paper at ICLR 2026
A.2.2 THE OBSERVATION VECTOR
The observation or state vector st, which we will interchangeably refer as Lobs to characterize the LiDAR, includes the goal as well as all the other objects and is environment specific. The dimensionality of this vector is defined by the number of LiDARs used for each type of object as well as the goal. We have used 32 LiDARs for each object category in this work. As provided in the implementation of the Safery-gym library, the values of the LiDAR are normalized between 0 and 1 and they represent the vicinity of the objects w.r. the agent. If any of the LiDARs record some object o, being extremely close to A, the corresponding value + 1, whereas for faraway readings the values- + 0.
Practicality of Using LiDAR data (Loba): Before providing further details, we highlight the core reasons for using the LiDAR information the environment state (t) or st. In most real world scenarios the agents are mounted with LiDARs to precisely assess the vicinity. (Choi et al.) 2024] Zou al., 2024), and training RL agents using LiDAR information has become mainstream in many recent works (Zubia et al. 2025; Miera et al. 2023 Xu et al.) 2025). This has happened since the often better than other mechanisms such as sonar, radar, cameras etc (Li & Xu 2024, Li & Ibanez- Guzman 2020). Other example include the entire self-driving industry (Waymo, Cruise), humanoid startups such Boston Dynamics etc which all mount sensors, most often LiDAR, on the agents.
LiDARs measurements
To generalize further to broader sensory data input, even the popular contemporary RL benchmarks such as CALVIN (Mees et al., (2022), LIBERO (Liu et al. (2023a) etc, utilize sensory information.
Environment Specifications:
1. Navigation: For the navigation environment, along with the goal object there are obstacles which consist of gremlins, hazards and buttons in the environment. There is a specific negative cost associated with each of obstacle categories across difficulty levels. These negative costs are again very sparse as collisions occur rarely.
(a) Difficulty Level O: consists of LiDARs for the four buttons which is a 32 dimensional the 32 dimensions for the goal object (note the goal is mounted on one of the buttons but contains a separate set of LiDARs for its tracking). Thus, Lobe (4) [0, 64, There no gremlins and hazards in this environment.
vector and another set of LiDARs corresponding
(b) Difficulty Level I: consists of LiDARs for the four buttons which is a 32 dimensional vector, LiDARs for the 32 dimensions for the goal object. LiDAR for the four gremlins which is also 32 dimensional vector and lastly the LiDARs for the four hazards which is again a 32 dimensional vector. Thus, Lots (t) E [0, 1] 128_
(c) Difficulty Level 2: consists of the same setting as Level 1, but this contains 6 gremlins and 8 hazards instead of 4 each in Level 1, thus making it significantly more chal- lenging. Note that Lohs (t) E [0, 1| since each of the 32 dimensional LiDAR vector corresponding to either type of the objects remain fixed, but the specific type of object LiDARs are now tracking many more those objects, as in the case of gremlins and hazards increasing in number at this difficulty level 2.
2. Building: In this environment, along with the goal object, there are multiple machines, other robots and risk areas which are the obstacles the agent needs to avoid. Similar to above, there is a negative cost associated with the obstacle categories across difficulty levels
(a) Difficulty Level 0 : consists of LiDARs for the four machines which a 32 dimen- sional vector and another set of LiDARs corresponding to the 32 dimensions for the goal object, this (t) E [0, 1,64. There are no robots and risk areas in this environ- ment.
(b) Difficulty Level 1: consists of LiDARs for the four machines which is 32 dimen- sional vector, LiDARs for the 32 dimensions for the goal object, set of LiDARs for the four robots which is also a 32 dimensional vector and lastly the LiDARs for the four risk areas which is again a 32 dimensional vector. Thus, Loss E [0, 1
(c) Difficulty Level 2: consists of the same setting Level but this contains 6 robots and 8 risk areas instead of 4 each in Level 1, thus significantly increasing the difficulty of navigation, (1) E [0, 1]128
24

---

Published as a conference paper at ICLR 2026
3. Fading: The Fading environment poses unique challenge in that the goal disappears lin- early after 150 steps of the environment' refresh. The environment contains the goal object which the agent needs to navigate to, along with obstacles termed as hazards and vases. The negative cost is again provided per category.
(a) Difficulty Level O: consists of LiDARs for the goal object with Lobs(t) [0, 1|32 without any obstacles.
(b) Difficulty Level consists the usual 32 LiDARs the goal object, 32 LiDARs corresponding to the eight hazards and 32 LiDARs corresponding to the vase. Thus Lobe (t) E [0, 1
(c) Difficulty Level 2: consists the usual 32 LiDARs for the goal object, 32 LiDARs corresponding to the hazards and 32 LiDARs corresponding to ten vases. Thus Lobs (t) E [0, 1] with significantly more obstacles to avoid disappearing goal object.
A.3 VISUALIZATIONS
Environments: A visualization representation of all these combinations of environments with vary- ing difficulty levels is provided in figures 7 and reepecttvely
Goal Not Captured at certain timestep: Our definition Tint (t) from section 3.1 characterizes the visibility of goal and significant penalty of -3 when its not captured Agent's LiDAR. We provide a sample visualization of case where the agent drifts far off in the environment in figure such that the goal outside the sensing range and thus the indices corresponding the goal in the observation vector become zero. These high negative intrinsic reward situations provide a strong signal the agent learn better policy and we empirically show that the learned policies have much better navigation during evaluation in section A.8.2
(a) Navigation-LLevel00
(b) Navigation-Leevll1
(c) Navigation-LLevel2
Figure 7: Visualization of the Navigation Environment with Level-0 (left figure), Level-1 (center figure) and Level-2 (right figure), where the Red spherical ball with a pointed blue cube is the agent with the LiDARs mounted over it and the goal is the green colored cylinder.
25

---

Published as a conference paper at ICLR 2026
(a) Building-LLevel-0
(b) Building-I.eve-11
(c) Building-LLeell2
Figure 8: Visualization of the Building Environment with Level-0 (left figure), Level-1 (center fig- ure) and Level-2 (right figure), where the agent needs operate various machines with the Parking symbol being the goal machine.
(a) Fading-Lovel-0
(b) Fading-Level-1
(c) Fading-Level-2
Figure 9: Visualization of the Fading Environment with Level-0 (left figure), Level-1 (center figure) and Level-2 (right figure). Notice how the goal appears faded and eventually vanishes.
Figure 10: An example from the Navigation Environment where the agent wanders off far away and thus the goal is not captured on the agent's 's LiDAR. The agent is thus also not captured the camera angle.
26

---

Published as a conference paper at ICLR 2026
A.4 GRAPH CONSTRUCTION ALGORITHM
Algorithm Graph Construction from LiDAR Data
Input: LiDAR observation vector Lobs RN (environment specific), LiDAR threshold
Output: Graph G. = (V,, E,, W,) with weighted-undirectedd edges
1:
Initialize:
2: Graph G, with empty node set V,, edge set E,, and weight set W,.
3: Create central agent node V and add to V,.
4: Fetch the partitions of Lobs for each category (object type): Lst, Ls., Lsp, Legoat, where
(1 S P), P number of categories (excluding Agent and Goal).
5:
1. Generate nodes for each category via LiDAR segments using algo [SegmentToNodes(LLe) Strpr///wwwooooooooooeee/eeeeerr SegmentToNodes( (gout))
6: Velusters +
7: Add all nodes from Valuseess to V,
8: > 2. Connect agent to each node and also Create fully connected subgraphs within each cluster
9:
for each cluster Vo in "......., Vse) do
10: for each node in Vo do
11:
Add edge (uA, uz) to E, with weight was equal to agent-object vicinity end for
12:
13:
for each pair of distinct nodes (m,, my) in Ve do
14:
Add edge (v;, vy) F, with weight way equal to inter-object vicinity
15:
end for
end for
b 3. Compute cluster representatives
18:
Vrepe f- Ø
19:
for each cluster Ve in Vatusters do
20: Calculate representative node Urep (e.g., degree central node) for Vo and add to Vreps-
end for
22:
D Connect all cluster representatives to each other 23: for each pair of distinct representatives (Urepais Urep.)) in Vreps do
24: Add edge (Urepis Urep.) to E, with weight based on vicinity.
25: end for
return G.
27

---

Published as a conference paper at ICLR 2026
Algorithm 2 Segment to Nodes Function
function ScCMENYTONNDDSSLLeeeenll
2: Vnodes &-G 0
Initialize an empty set for nodes in this segment
3: current reaoding <
4: for i = 1 to length( L segmentt) do
5:
d; f segment [1]
> Current LiDAR reading (vicinity)
6:
if d; > 0 then
7:
is cupty(current.noe.rrddd
or pd, lssteaureent.ooderrrddigg))))))) <
then
8:
Append d; to current node readings
9:
Create node e from current. current..noe readinggg Add to V Vodes else
10:
current mowddtood_ereee readinggs [d.] end if
Start node
12:
else is not empyyccureent..ode.eeeeee
then
14:
Create node from current node readings; Add to Vnodes
current node readings end if end for if is not wmppyccurrent.nnd.eeeedddd then
Reset on zero reading
16:
18:
Add the last processed node
19:
Create node u from wurrent..ode. Add v to V Voodes
20:
end if
21:
return Vnodes
22:
end function
A.4.1 SAMPLE GRAPH VISUALIZATION CONSTRUCTED VIA ALGORITIIM
A visual representation of the graph that is constructed via algorithm is provided in figure II with the respective environment state in figure
along
Current State Graph Structured Layout
Figure 11: A sample visualization of the generated graph on the Building-Levee environment. The edge weights here describe the vicinity of the objects discussed in the graph construction algorithm. The dark red edges are emphasized to show the edges from agent node to all other nodes, and remaining edges shown in lighter color.
28

---

Published as a conference paper at ICLR 2026
Figure 12: The environment state corresponding to the graph in figure 11
A.5 IMPLEMENTATION AND HYPERPARAMETER DETAILS
A.5.1 GRAPH CONSTRUCTION HYPERFARAMETERS
Since the construction of G. in algorithm T is the core of our method, we discuss the corresponding design and hyperparameter choices as follows and explicitly detail these table
1. The value of LiDAR reading difference threshold т, which is used to generate the nodes, is fairly non-trivial problem which depends on many factors of the environment dynam- ics. We first obtained an approximate range for analytically, described in section [A.5.3 Using this range, performed a sensitivity analysis over set of values (results in section A.9). Aggregating everything, we select T = 0.1. Additionally, we emphasize that the con- sistent choice of 0.1 also eases the setting of hyperparameters and reproducibility across environments.
2. Graph Laplacian is un-normalized. Consider a simple example where there we have two graphs G1 and G2 where G2 has the exact same connectivity as 91 but the edge weights of G2 are scaled by some arbitrary factor b, ie the adjacency matrix of Ag, = b Ag, (where is multiplied to all elements of the adjacency matrix). Now the Normalized graph laplacians of both the graphs are exactly the same, Lç, = Lg,, due to the normalization property by the diagonal degree matrix. This has a counter effect as it completely ignores the environment state and location of the goal w.r.t the agent which also want to encode in Tema (1) in the first place. On the other hand, the Un-normalized laplacians provide us form Lg. b Lg,, retaining the changes of all other objects w.r. the agent.
3. For the choice of graph connectivity (structure) described in algorithm 1 note that simply the possible edge connections (ignoring the edge weights) are combinatorial and thus an informed design decision has be made to construct the graph G. from Lob. We reiterate the algorithm here along with the rationale behind these decisions:
(a) Using each category cluster Vc. a star graph is created where the agent node is con- nected to every other node in the graph. This is done since in any environment the agent is the core node w.r.t which we obtain information about the surroundings.
(b) Then we construct complete graphs within each Ve order to symbolize strong notion of object category (described in detail in section A.2 for all environments). Another straightforward way to do is to introduce a different edge type for each object, however such construction makes the graph more complicated and usually requires further decomposition in order to compute any property of the graph. Thus we restrict ourselves to unified edge type identified by its node-edge tuple (i.j, W.y). Two strong reasons led to this choice (i) the number of nodes for each object type are limited and thus even for complete graph the subgraph size remains manageable, (ii)
29

---

Published as a conference paper at ICLR 2026
Li & Zehmakan 2023) describes the ease of obtaining node centrality (see next point for this) in a complete graph.
(c) We then obtain the degree based central nodes, also called representatives, in Vrepe and connect those amongst each other making another subgraph. This type of subgraph is generally small in most scenarios of interest we are considering different types of objects (in an environment which contains too many types, one can perform some form of clustering/grouping)) and is thus manageable. While the construction of this subgraph can be ignored, this however leads to a relatively trivial graph which only factors the agent to object nodes, and nodes of same object type, but completely ignore the geometric locations of the object type w.r.t one another. The choice of con- necting only the central nodes of the object rypes is made to restrict the graph size from becoming fully connected which increases the complexity of Laplacian Pseudoinverse computation. We have empirically justified this central node connectivity in section A. a.ablatin
(d) Note: We only generate node for the goal object in algorithm | The reason that (i) this simplifies the calculation of Time (in equation 2 in contrast to the case where we have multiple goal nodes, (ii) in any practical environment, by default the goal LiDAR values in Lobs are contiguous as the goal is single object and their difference is < T which creates a single node automatically.
Table 1: Our method Graph Construction Hyperparameters
Parameter
Value 0.1
LiDAR reading difference threshold π Graph G. Laplacian type
Un-normalized
A.5.2 PPO HYPERRPARAMETES
Since our method is directly based on the PPO implementation, we retain same hyperparameters for PPO, PPO with Entropy and Our Method in order to perform the direct analysis of adding our proposed (t). Hyperparameters such as learning rate, reward discounting factor factor for Generalized Advantage Estimates, entropy lambda factor for PPO with entropy etc are borrowed from the recent literature (Xudong et al., 2024). Based on many works in the literature, we also utilize parallel PPO implementation these agents all operate in independent instances of the cor- responding environment in order to collect the demonstrations faster and we note that this is NOT multi-agent RL setting. We use a shared 2-layer MLP to feed the concatenation of the agent vector (section I (a(t) and the Lots(t) (t) (aka the state vector s(t) from section A.2.2) as input which a common approach in the literature. Over this shared MLP backbone we have two separate heads the first one is linear projection of size 256 2 which behaves the Policy Network Ty predict the action whereas the second one is 256 x 1 for the critic for Value function approximation. As discussed in sections 1 and 3.1 the action space is [-1, corresponding to the throttle and steering angle of the agent respectively which, following (Barhate) 2021). is formulated as a gaus- sian N (Lobs a²)) The Policy Network output this 2-dim prediction for the mean and there is a separate Pytorch trainable parameter of size 2 for the standard deviation values (therefore the standard deviation values are learned directly via gradient updates). We also discuss the evolution of this standard deviation values over the course of training in section A.13 During training an action sampled at random from this gaussian whereas during evaluation we simply consider the mean (which is the output of the Policy Network as is) based on the original pytorch implementation. The hyperparameter values are provided in table
For the remaining baselines we take source code of the Surprise RL Standard and Surprise RL Diff and train it with PPO as it is the SOTA RL algorithm. For MEGA and GCPO, we borrowed the source codes from their implementations and MEGA Github (MRL Library of the author) and GCPO Github respectively.
For the baselines using entropy loss, the entropy is calculated over the gaussian of the aforemen- tioned action distribution following the actual implementation. The experiments were conducted on NVIDIA A 100 GPUs
30

---

Published as a conference paper at ICLR 2026
Table 2: PPO algorithm hyperparameters. Note that using 20 agents in parallel simply speeds up the process for on-policy setup and all these agents operate in independently created instances of the environment.
Parameter
Value
Learning Rate
le
Batch Size
2048
Num Agents Used in Parallel
20
Num Episodes per agent
2500
Max Timesteps per episode
1000
Num Episodes between Policy Update
2
Num Epochs for update
4
Entropy Coefficient (for baselines using entropy loss)
le-2
Shared MLP size
[|4a| + Lbs 256] + [256, 256]
Actor size
Shared MLP - [256, 2]
Critic size
Shared MLP > [256, 1]
Discounting Factor
0.99
Generalized Advantage Estimate factor PPO clipping e
0.95
0.2
A.5.3 OBTAINING THE RANGE FOR THRESHOLD 7
We first reiterate (as already mentioned section A.5.I) that obtaining a tight range for a fairly non-trivial problem that requires deeper investigation of its own. However, here lay out the approximations that we used to first obtain a range for 7 which we then plugged in with the corresponding observations from the environment and then lastly did the sensitivity analysis to arrive at the specific value of - = 0.1 that worked well across most settings and furthermore as pointed out earlier in section A.5.I single value helps in reproducibility well.
As mentioned earlier in section A.2 the LiDAR values denote the vicinity to the agent rather than the normalized distance. However for the ease of reading, we use the notion of distance below but is trivial to switch to vicinity/closeness. We have the following steps in our derivation:
Approximation of r and its intuition: Defining
be the sensing (LiDAR) radius, discussed earlier in section A.I.I
Suppose we are merging the LiDAR values (for detailed discussion on the LiDAR values we refer the reader to section A.2.2) of two arbitrary objects 01, o2 using T in the Segment- ToNodes function defined in algorithm 2 Then we define d as the distance from agent to the nearer of the two objects being considered (i.e. d min(dA,0. dA,o2)). with dAAo, being agent to object o, distance
let re be the collision buffer term which is characterized by the agent's size, the object size(s) along with some small safety margin
let v be slack parameter that we use to control the the dependence on d. In other words, it defines how aggressively we combine objects in single node as the value of decreases
We define the upper bound as function of d as follows:
r(d) min R, dgep) min(R, R, + slack(d) min R. + eb (1-11-1
R
R
R
where dsep = =r + slack(d) is the separation term depending upon (which becomes fixed once know the agent and obstacle dimensions) and some slack term which is function of d. As a key property, we need this slack term to behave in a manner such that when the objects are far from the agent, we can create separate nodes in our graph and does have notable impact on the Ref value. At d - 0, the objects are fairly close to agent A and thus we create unified node in the graph, keeping larger slack term. The choice of linear decay formulation as slack(a) = xb
is the simplest formulation satisfying the desired property, defined next.
31

---

Published as a conference paper at ICLR 2026
2. Approximation of de in terms of agent and object velocities: While the choice of t again complex, we leverage an aggregate the velocities (exact computation discussed below) of the agent and objects
Vagg
a:
Vogg + Vagg
where
Vaga aggregate of the speed (interchangeably used for velocity when direction of motion is fixed) of the agent
Vagg aggregate of the speed of the objects
Thus, when Vagg >>
Vagy, the likelihood of the agent navigating through the space between the objects is extremely high admitting slack(d) + 0 and vice-versa.
3. Aggregating over d: While equation charracerizss the threshold, we still have dependency the term d. We integrate over this term by assuming that the objects 0r and 02 independently located within the radius R centered around the agent.
Thus the cumulative density function, F.. of = minfdA,0s dA.oz } can be defined as follows:
x, dA x)
=1((1-
(10)
where Fa(x)) is cumulative density function of an arbitrary object being located within distance =²
from the agent on the disc of radius R, ie. Fa(r) above with the independence of the location of the objects, we obtain
(simply the ratio of areas). Plugging this
Rz
x²
Fa(x)= =
R²
Since this function is differentiable, we can compute the PDF
x²
fa(ω) 4 R²
0
SISR
R2
The expectation B(d) is then
B(d) 1
R
8 R
afz(z)dr
(11)
15
4. Putting it all together: aggregate value of Using the derivations above and putting them in we obtain an aggregate of as
equation 8
Te +
Vane Vasg + uapy
R
(1
87/11 R
T < min
1,
(12)
R
Te +
Vaga Voun
Vayg
13
7
R
min
1
(13)
R
Numerical approximation:
1. typically << R and thus ignore this term
32

---

Published as a conference paper at ICLR 2026
2. to obtain reasonable estimate of Vagg and Vagg> compute the median values via monte carlo estimate as follows:
(a) We considered 10, 000 arbitrary timesteps independently for each of the environ- ments and the respective 3 difficulty levels
(b) for each timestep & of these 10000 rollouts, obtained the median of the absolute value differences between the LiDAR vector values at t and corresponding t This is loose approximation since these LiDAR values are w.r. the agent, but that suffices as the agent and the objects have restricted motion at any particular timestep. For the agent, already have the estimate of the velocities using its velocimeter as discussed in section A
(c) obtain the median values of the distances for the objects and the median values for the velocities of the agent respectively
(d) compute the ratio Varz
(as in our case velocity is being calculated as the distance
+aps
in particular direction over unit time)
(c) The rationale for using median is the same as earlier experiments that the mean values are extremely noisy (with the standard deviation being higher than mean in skewed distribution where the absolute values are bounded below by 0). Thus, we rely on the median in this estimate.
Plugging all the values, we obtained analysis below this threshold value, with more details in section A.9
(1.0.124) 0.124. We then performed the sensitivity
A.6 SETTING VALUES OF B AND O
Corollary A.1.3 provides practical implementation choices for the values of and a in terms of the maximum absolute extrinsic reward and the maximum graph connectivity change respectively. We discuss the selection below and note the values explicitly in table
Selecting 9: Based on the code of the Safety Gym library, we noted that the maximum absolute value of the extrinsic reward is < 1 and thus factoring in the constant C, we performed some initial experimental checks and select 5 as penalty factor to keep, which is sufficiently but not extremely large, to steer the agent for goal visibility. Values greater than 1 worked reasonably well and is primarily a design choice.
Selecting a: We consider each of the components max3,a (xx a)}, mmxx and C1 separately:
1. from the empirical details of section have max,,a Tred as) 10 scaled it with a factor of 10
2. Note that òmaz derived in lemma A.1.3 O(k). where defines maximum number of node changes in the graphs per timestep. Based the environment specifications from section A.2 As discussed previously, the event E (k(At) >> nmnin) almost never occurs, and thus retain h
3. C1 as the lower bound of C'(t) k(( (EA Eg. (t)) which empirically observed be 0.837
Putting it all together, we approximate 10. If we plug in the numbers, we obtain 0.337 = 11.94. We however, to again focus on simplicity and consistency of the same hyperparamter across the environments, chose the value of 10, similar to the selection of earlier.
10
Table 3: The values of and / in the implementation of Our method.
Parameter
Value 5
3 penalty factor to enforce goal visibility factor for scaling Fint
10
A Note on Robustness: critical to note that these single, principled values (3 5, = 10) were used consistently across all 9 environments (all 3 tasks and all 3 difficulty levels) without
33

---

Published as a conference paper at ICLR 2026
any per-environment tuning. This stands in stark contrast to methods that require intensive, per-task hyperparameter sweeps and strongly demonstrates the robustness and generality of our theoretically- grounded selection process.
A.7 EVOLUTION OF Tint DURING NAVIGATION
We plot the cumulative intrinsic reward Ei=1 (I), E [7*] where Te the length of the cor- responding episode e being evaluated upon, at the median along with the 25th and 75th percentiles with shaded region over these 1000 (200 per trained model and 5 models with random seeds) eval- uation episodes. The aim of this experiment is to assess how the rine evolves as the agent navigates the enviromments post the policy training. Since Tint fluctuates at every time step depending upon the current state, we visualize the cumulative value. The results are plotted in figures 13 14 and T5 for the environments respectively.
Note that there are many timesteps during a trajectory rollout where (ime(t) is negative for some timestep & but the agent is still closer the goal. This happens due to more intricate dynamics where all the other objects are also navigating in the environment and this impacts the edge weights in Gt. The effects this can be noticed in the plots for difficulty level 2 primarily. We discuss this in more detail with thorough quantitative analysis in next section A.7.1
Another noteworthy aspect is the difficulty of navigating in the environment can also be assessed via these plots. As observed in the main section result 4 and difficulty level 2 (and level 1 to some extent), which are harder for the agent to navigate in due to presence large number of randomly moving obstacles, its corresponding Tint also exhibits fluctuations.
0.20
25-33 parcencie median
25-75 percentiee
percentic
median
0.15
Cumdative
0.2
Cumutabue
6:00
0.25
-0.16
0.30
202
420
200
200
1000
700
460
-20
D03
1200
205
660
6.5
6.0
1000
Trajectory Stop
Trajectory
Trajectery
(a) Nevilatioo-Level-0
(b) Navigation-Level-1
(c) Eerigation-Level-
Figure 13: Visualization of the Cumulative Tint across the timesteps for the Navigation Environment with Level-0 (left figure), Level-1 (center figure) and Level-2 (right figure)
25-75
percentie
25-75 percencle median
25 perconsie media
23.35
W/w
Curulaative
0.3
Cumulebiers
0.002
0.275
0.228
220
400
250
820
2000
200
400
6000
500
1200
220 Trajectory
400
500
202
1000
Trajectory
Trajectory
(a) Building-Level-O
(b) Building-Level-1
(c) Building-LLvel-2
Figure 14: Visualization of the Cumulative Tine across the timesteps for the Building Environment with Level-0 (left figure), Level-1 (center figure) and Level-2 (right figure)
34

---

Published as a conference paper at ICLR 2026
0.22
25-75 persentle median
percenble
23-75 percenlle median
0.20
0.35
Cummutative
Cumulaatve
0:30-
-0:2
0:55
0.20
20
40
30
103
50
150
150
400
602
1000
Trajectory Time Step
Trajectory Stop
Trajectory Time Step
(a) Fading-Level-0
(b) Fading-Level-1
(c) Fading-Level-2
Figure 15: Visualization of the Cumulative Tint across the timesteps for the Fading Environment with Level-0 (left figure). Level-1 (center figure) and Level-2 (right figure)
A.7.1 CONFIGURATION FOR NEGATIVE Tine (1) BUT IMPROVED NAVIGATION TO GOAL
As mentioned in the previous section, while plotting (section A. 7). there can be configurations where (t) (t + S but the agent navigates closer the goal. Note that such situations occur since the computation of Ref is non-trivial w.r. to the distance of agent to the goal, as it incorporates the entire observation space captured on its LiDAR Toohs (1) and T.abs (1+1). To quantify such situationn,, we perform the following experiment:
1. Load each the & trained policies
2. Roll each policy for 20 episodes, thus 100 (20 5) arbitrary rollouts total incorporating for the randomness
3. Obtain the count of the timesteps at which the aforementioned situation of negative Tint but agent navigating closer the goal happened. Lets call this count J
4. Obtain the total number of timesteps that the agent navigated across all episodes, call this count J
5. Compute the ratio
The outcomes mentioned in justiffy the fluctuations in the plots of the Tint and how it affects the monotonicity of even the cumulative reward.
Table 4: Fraction of times when Tine < 0 but agent moves closer to the goal, in order to justify the rationale behind plotting the cumulative Time instead of raw values in section A.7
Jeeg rrnd
Environment Name
jneg
Ratio
Navigation-level-0
501
5977
0.083S
Navigation-level-1
2220
10293
0.2157
-aviga
12138
51186
0.2371
Building-level-0
627
6755
0.0928
Building-level-2
3132
16008
0.1956
Building-level-2
9472
37007
0.2560
Fading-level-0
84
5123
0.0164
Fading-level-1
1928
7047
0.2736
Fading-level-22
12078
51846
0.2329
A.8 BRIDGING THE RESULTS FROM LEMMA 1 AND THEOREM WITH EMPIRICAL OBSERVATIONS
A.8.1 EMPIRICAL VERIFICATION OF BOUNDED GRAPH CONNECTIVITY
We proved in lemma that the change in Rell and x have opposite gradient signs over time. Earlier showed that generally Ret tends decrease over time, and such, expect x(G)) to increase. We also claimed in the first part theorem] that the expected graph connectivity at timestep lower bounded via Erar- (m(G [.] 2 (GG)) dmax where the dmax from lemma A.1.3
35

---

Published as a conference paper at ICLR 2026
To justify both of these empirically, we provide the plots for the absolute difference of k k(9(+1) and k(G)) across the timesteps at the median along with the 25th and 75th percentile bands across the environments and difficulty levels in figures 16 17 and can be made:
18 The following important observations
1. as argued from the lemma I] we expect the value of increase over time. This essentially leads to larger absolute differences which can observed in various plots.
2. we notice various arbitrary fluctuations in the plots. These values typically characterize non-trivial changes to the graph structure, which are also reflected in dmax dervied in lemma Using mmax = O(l)) for l = 1, clearly holds.
0.05
0.05
23-75
25-75 percentee
modian
modian
medin
0.00
0.03
0.00
0.07
0.02
0.00
0.00
0.01
75
150
400
1000
Trajectory
Trajectory Time
Time
(a) Navigation-Level-0
(b) Navigation-Lovel-1
(c) Navigation-Leveee
Figure 16: The absolute value of the difference of second eigenvalues, |x<(G)) - =6(G+1)) across the Navigation environment.
0.00
0.05
0.05
25-75 percencle
25-75 percencee
25-75 percente
mosion
medon
medon
InGol 1000--00--00 +30
0.02
0.02
0.02
0.01
0.01
0.01
202
4.0
4.50
200
1.000
0.00
205
450
400
1300
250
400
400
1000
(a) Buiveing-Level-0
(b) Building-Level-
(c) Building-Level-2
Figure 17: The absolute value of the difference of second eigenvalues, |m((G)) - x(GG+1)) across the Building environment.
0.00
0.05
0.05
25-75 perrentlee
25-75 permertiee modian
25-75 prcsenie
modian
0.08
median
0.00
0.02
0.01
0.01
0.07
6.00
20
23
0.00
20
40
60
20
100
120
220
400
500
802
2000
Trajectory
Step
Trajectory
Trajectory
Step
(a) Lading-Leeve--0
(b) Fading-Level-1
(c) Pading-Level-2
Figure 18: The absolute value of the difference of second eigenvalues, ie |m(G]) - x(G++1)) across the Fading environment.
A.8.2 EMPIRICAL VERIFICATION OF GOAL VISIBILITY MAINTENANCE
We also argue that well trained (otherwise optimal) policy will learn to maintain a high goal visibility (i) in order to maximize the expected reward and (ii) to avoid the large negative penalty
36

---

Published as a conference paper at ICLR 2026
of -3. We demonstrate that this indeed happens and during evaluation the 5 trained policies indeed maintain much higher goal visibility as shown table across all environments and difficulty levels in comparison to randomly initialized policies.
Table Percentage of timesteps which the goal visible on the agent's observation Lobs during the evaluation in contrast to randomly initialized policy.
Environment Name
Randomly Initialized Policy
Trained Policy
Navigation-level-0
50.26%
99.59%
Navigation-levellI
48.61%
99.35%
Navigation-Ievel-2
56.39%
98. 98.99%
Building-level-0
85.33%
99.48%
Building-level-1
81.00%
99.27%
Building-level-2
77.12%
99.09%
Fading-level-O
94.88%
99.92%
Fading-level-1
88.60%
99.67%
Fading-level-2
86.90%
99.21%
A.9 SENSITIVITY ANALYSIS OF GRAPH CONSTRUCTION THRESHOLD T
One of the components of method is the threshold which is used in the clustering of elements of the LiDAR array to construct nodes in the graph as discussed in algorithm [ Since, numerically attained т < 0.124 earlier, we vary the corresponding policies. Since the values in this set are relatively close, we also expect less susceptibility. The sensitivity analysis plots are provided in figure (all the computations are done in the same manner as discussed in Evaluation Methodology of section 5). While we do notice minor fluctuations in the results and there no unified value of that works the best across all types of evaluation metrics and environments,
{0.08, 0.09, 0.1, 0.11, 0.12) and evaluate
0.1 still provides great parameter setting and can be used for all difficulty levels and environments, thus significantly reducing the hyperparameter search workload mentioned previously in section A.5.I
Nesprae Builiig Tack
Nangaoe
Haking
Tack
Medita Thsanae
Nokiake
Butling
Faling
305
Valbe
(a) Success Rate
(b) Median Environment Reward
(c) Median Timesteps
Figure 19: Success Rate, Median Timesteps and Median Normalized Reward across the environ- ments for varying values of the graph construction hyperparameter 7 in algorithm I
A. COMPLEXITY ANALYSIS AS FUNCTION GRAPH SIZE
We provide a formal analysis of the computational complexity of our method, which is incurred at each timestep. The total per-step cost the sum of (1) graph construction and (2) effective resistance computation.
1. Graph Construction (Algorithm 1) The complexity of constructing G. is highly efficient. The Segment T ToNodes function (Algorithm 2 iterates through the LiDAR observation vector (Lobs (f)), say of size N, which has complexity of O(N). The subsequent con- nection steps (lines 9-25 in Algorithm I iterate through the nodes n = [V] and object categories P. In the worst case, this involves creating complete graph within clusters, resulting in a complexity of Onz?). Since the dependence on is linear and n is designed to be small, the total graph construction cost, which is additive, of O(N + n²) is not large.
37

---

Published as a conference paper at ICLR 2026
2. Effective Resistance Computation (Eq 2):
This is the primary computational bottleneck of our intrinsic reward. The calculation, as defined in Eq [ requires the Peooreee pseudoinverse, LT, of the x n graph Laplacian L, Standard numerical methods for computing the pseudoinverse (e.g.. via Singular Value Decomposition) have a computa- tional complexity of O(n*), where
[V] is the number of nodes in the graph.
Connecting Theory to Practice: While a theoretical complexity of O(n") might seem prohibitive, it is crucial to note that our entire framework is explicitly designed ensure remains small.
Bounded Graph Size: As enforced by our Algorithm I which clusters nearby LiDAR readings, the number of nodes is not function of the observation dimension (128) but of the number of perceived entities.
Empirical Validation:
The practical cost of this Onn²) computation is trivial because y is small. This is empirically validated by runtime analysis in figures 20 21 and 22 in the next section, where we note our method's total runtime is only 1.1x to 1.25x, for per episode training run, that of vanilla PPO across all the benchmarks. This marginal increase confirms that the time spent on PPO's policy/value updates far exceeds the time spent on our graph and Reff calculations. Additionally, this marginal increase in runtime is completely countered by the much faster convergence during training from figure 5
In summary, while the formal complexity is Onn"), our principled graph construction ensures is small and bounded, making the practical computational cost negligible and significantly lower than other SOTA baselines like GCPO.
A. EFFICIENCY OF OUR METHOD
To further justify the practicality of our method, we also compute the per episode rollout time based on the process time (in order to provide fair comparison by ignoring the sleep time, cache misses etc) and compare those across all methods. The plots in figures 20 21 and 22 show the median process time per episode along with the percentiles as done previously. fastest since it does not incur any additional computation whereas PnO+Ent incurs small additional cost for the entropy calculation, but the ratio of median runtime per episode for Our method vs PPO only between 1.2 1.25 on navigation environment, which further reduces to between 1.1 1.17 on a more complex building environment. This is much better than bascline ratio of SRL-Std to PPO 1.29 1.51 navigation and the best baseline GCPO's s ratio to PPO at 1.38- 1.62. Notice that the graph construction and Ret calculation of our method can be done on any standard CPU core within milliseconds per state observation, which further becomes favorable the environment gets complex.
expected, PPO runs the
22004 Cat
SaL-dd
SAL-9E
HEAA
Maden
(a) Difficulty Level 0
(b) Difficulty Level 1
(c) Difficulty Level
Figure 20: Navigation Environment Times
38

---

Published as a conference paper at ICLR 2026
RECHAA
MM
J.I
300
HHAL
(a) Difficulty Level 0
(b) Difficulty Level 1
(c) Difficulty Level 2
Figure 21: Building Environment Times
S0L.5M
S0L.50
SIL4M
MEM
MEAM
HEAA
0090
0220
0230
(a) Difficulty Level 0
(b) Difficulty Level 1
(c) Difficulty Level 2
Figure 22: Fading Environment
A.12 ABLATION FOR THE CENTRAL NODES CONNECTIVITY OF THE OBJECT TYPE SUBGRAPHS
Another key component of the graph construction algorithm 1 is the connectivity of central nodes based on the degree for each type (Vs,, E [P). We provided rationale for this in section A.5. and justify this empirically in figure 23 While the success rate does not fluctuate much since the agent still navigates to the goal eventually, we see a much more pronounced effect on the number of timesteps taken reach the goal well the median reward the agent receives its trajectories. For eg in the navigation environment we see around 10% increase in the number timesteps to reach the goal and around 14% increase for the building environment. Correspondingly, the agent's rewards are reduced by almost 8.4% and 12% respectively. The fading environment is relatively less sensitive this component of the graph construction.
140
2.095
Median Timwstape
L50.2
Normallaed
80
3,03
k0
3.11
With ConnectorS No Connection
With Connectors No Co Coactooss
Comnoctore Connectiors
19.7
Ain
Builing
Tuding
3002
Modostion
Builing
Fudrig
hongetion
Bulking
Fadrg
(a) Success Rate
(b) Median Environment Reward
(c) Median Timesteps
Figure 23: Success Rate, Median Timesteps and Median Normalized Reward across the environ- ments for the ablation of algorithm
39

---

Published as a conference paper at ICLR 2026
A.13 EVOLUTION OF THE STANDARD DEVIATION (t(t) OF THE ACTION DISTRIBUTION DURING TRAINING
Figures 24 25 and 26 compare the evolution of the standard deviation parameter A over the course of training. Our primary emphasis here is to compare this against PPO (and PPO+Ent) while con- necting to the convergence results from sections 4 and experiments of 5.2 Since during training we sample the agent's s action from the N (Huo (t)), d²), there is natural exploration component this formulation, however high deviation values for longer can lead to slower convergence, more timesteps to reach the goal and furthermore not reaching the goal in many cases due to excessive exploration in the environment. Thus, we argue that higher negative slope of standard deviation curve, but not too extreme (as this will hinder the exploration in the environment leading to poor outcomes), favorable. This rationale has been also thoroughly justified in the previous sections of this work.
1,4
RO
Stundardd Drvvation
Stonde Deerattion
Trjectory Time Step
Trajectory Time Step
Trajector Time
(a) Navigation-Level-0
(b) Navigation-Level
(c) Navigation-Lever Level-22
Figure 24: Standard Deviation (t) of the action distribution during training in the Navigation environments.
Staddar Drilatin
Trojectry Time Step
Tripetery Time Step
Trojectory Time Stop
(a) Hailding-Level-e
(b) Building-Level-
(c) Building- Level-2
Figure 25: Standard Deviation (t) of the action distribution during training in the Building envi- ronments.
Sondare Drvietiie.
1.0
Tajectery Shpp
Thojctory Stop
Troectory Time
(a) Lading-Level-0
(b) Fading-Level-1
(c) Fading-Level-2
Figure 26: Standard Deviation (t) of the action distribution during training in the Fading envi- ronments.
40

---

Published as a conference paper at ICLR 2026
Mallan
0.7
0.0
Noigaka
Buikiing
Faling
Eavirosment
(a) Difficulty Level 2
Figure 27: Spearman Correlation coefficients between the value function and -Ren level for the environments. We note the weaker correlation values are primarily due to the difficulty in approximating the value function noted in several works (Moon al. 2023 Engstrom et al., 2020) in conjunction with other factors affecting the training.
A.14 EXTENSION TO DENSE ENVIRONMENT REWARD SETUP
provide an extension of our experiments to the case where the reward obtained from the envi- ronment is dense, ie, Text is used every timestep K 1 in contrast to the K 25 mentioned in main results of section We perform empirical validation across all the environments on both the easier level-0 difficulty and the much more difficult level-2, which covers both ends of the spectrum. We have several observations from the results described tables [
Inline with the results from figure 6 (correlation between the value function and RReltt) and the theoretical results, the augmentation of Tint keeps the results consistent, without interfering the learning and convergence process.
For difficulty level where the results of our sparse setting already reach complete success, the observed improvements are marginal.
For difficulty level 2, which is a much more complex setup due to significantly larger number of obstacles and goal reaching difficulty (section (A.2.2), again that Tint does not interfere and rather serve as a reward shaping mechanism to assist the learning process.
Lastly, we also emphasize that the focus of our work is to improve the convergence of sparse goal conditioned online RL,, and this set of experiments is to merely justify that breadth of applicability of our propsed Reft-
Table 6: The comparison of evaluation results, over difficulty level 0, for policies trained via the Sparse formulation where the standard environment reward is provided at every K 25 steps (results copied from figures 2, [ and against the Dense formulation where we utilize the standard environment reward at every timestep K = The columns for Normalized Reward and Timesteps detail the median results along with the 25th and 75th percentile results.
Env
Setup
Success Rate
Normalized Reward f
Timesteps | 55 (46 69)
Navigation-level-0
Sparse
99.90%
0.03091 (0.02709 0.03545)
Dense
100.0%
0.03124 (0.02771 0.03633)
51.5 (43; 67.75)
Building-level-0
Sparse
99.60%
0.02833 (0.02533 0.03250)
60 (48 78)
Dense
100.0%
0.02974 (0.02702 0000413)
56.25 (44: 77)
Fading-level-O
Sparse
99. 99.90%
0.03075 (0.02868 0.00340)
53 (44.75 61)
Dense
100.0%
0.03218 (0.02959. 00.3491))
52 (42.5 59.5)
41

---

Published as a conference paper at ICLR 2026
Table 7: The comparison of evaluation results, over difficulty level 2, for policies trained via the Sparse formulation where the standard environment reward is provided at every K 25 steps (results copied from figures [nd Banddaggen against the Dense formulation where we utilize the standard environment reward at every timestep K = The columns for Normalized Reward and Timesteps detail the median results along with the 25th and 75th percentile results.
Env
Setup
Success Rate
Normalized Reward
Timesteps
2
Sparse 55.50%
0,00682 (-0.00169: 0.00996)
242 (97 1000)
Dense
100.0%
0.02790 (0.02238 0.03365)
88 (63 122)
Building-level-2
Sparse
88.40%
0.01339 (0.00994: 0.01679)
168 (89 518.75)
Dense
100.0%
0.02420 (0.01959: ; 0.02998)
98 (71; 137)
Fading-level-2
Sparse 60.10%
0.00702 (0.00004: ; 0.01100)
248 (85 ; 1000)
Dense
100.0%
0.02790 (0.02228: 0.03380)
92 (69; 114)
A.15 DISCUSSION ON GENERALIZATION BEYOND LIDAR
We emphasize that the core requirement of our framework is not LiDAR, but rather state 8 that can be meaningfully decomposed into a graph of interacting entities (c.g.. agent, goal, obstacles and such). The LiDAR data used in our experiments is merely practical instantiation of this, as it directly provides categorized, egocentric information that our Algorithm| Taan parse into nodes and edges. We have also characterized this experimental choice by attributing to the extensive success of the use of sensory data (such as LiDAR) in both simulation and real world environments (as discussed in section A.2.2). The following extensions, which essentially cover almost real world implementations, support of our arguments:
Raw Pixel Inputs (Vision): For environments where the state s, is image, the graph can be constructed by deploying perception frontend. For example, a pre-trained (or jointly trained) object detector keypoint extractor identifies the "agent," "goal," and various "obstacles" in the scene. The bounding boxes or keypoints of these detected entities serve as the nodes Vg. Edges E, and weights W; are then be defined via the spatial (e.g., pixel distance) or semantic relationships, and the Rem computation directly proceeds as discussed in our Algorithm []
Tabular MDPs (e.g., Grid Worlds): In discrete grid world, the graph construction is even more straightforward. The nodes V₁ are the agent's 's current cell, the goal cell, and all cells identified obstacles or hazards. The edges E, represent physical adjacency (e.g., connecting all non-obstacle cells that share a border), with weights We set to unity. In Euclidean distance metric that accounts for all walls and pathways, providing dense and informative reward signal.
this configuration, Ragenttnt, goal) serve robust,
General Sensory Inputs: are trivial to handle with our current construction directly.
This flexibility demonstrates that our core contribution-usingg Ref a goal-directed structural reward-is a general principle that can be adapted to any MDP where the state can be abstracted into an entity-based graph.
A. GENERALIZATION OF REF TO OTHER ENVIRONMENTS
In the previous section we characterized the generality of our algorithm and proposed metric to various types of inputs, albeit within navigation and manipulation tasks. We start by noting that these two types of tasks describe a substantial percentage of the real world deployments of RL humanoids, delivery bots, warehouse robots and such. We have a general implementation as follows:
Nodes: by discretizing the state space into regions, eg using a VQ-VAE, where each code- book vector becomes a node in the graph G
Edges and Weights: connecting temporally adjacent or regions in vicinity, with the weights representing transition probabilities or inverse distance.
Computing Ryp: by considering two nodes from the graph G. the Re can be calculated and minimized against a baseline set of RSt values computed over some expert's s data or simply using the highest reward states. We discuss this with the following two examples.
42

---

Published as a conference paper at ICLR 2026
Example environments for generalization of Rett
Antmaze (OGBench (Park al., 2025): The following simple construction can generate a graph over which we compute Ren
1. Nodes: each cell or group of cell describes a node in the graph G. The cells are binned by their respective categories of the agent location, the obstacle (wall) and the cells containing the goal.
Edges and Weights; are computed simply by inverse distance of the cells on the grid to incorporate for basic geometry, or by connecting neighboring cells for more trivial graph.
3. Ref the computation simply follows our eq between the agent and goal node cells.
Locomotion tasks (e.g., Half-Cheetah) (Brockman et al. 2016):
1. Nodes:
The graph nodes V are the agent's 's primary body parts (e.g., for Half- Cheff-h this includes the torso, thighs, shins, and feet). The agent's s state 8, (containing joint positions) defines the spatial embedding of these nodes at time L.
2. Edges & Weights: The graph Gr could be fully connected, where the weight way (t) between any two nodes and is function of their spatial distance, e.g., way 1/([[pos,()) pos,(())) (1) + e). This graph's Laplacian, L,, holistically represents the agent's entire pose time t.
3. Reg: The task (e.g.. learning a stable gait) can be framed as matching a target pose. We can define a set Rearger of "target effective resistance" Rearget values (computed either from various expert's "stable" poses or high reward states/poses) between two key nodes (e.g.. front foot and back foot).
4. Intrinsic Reward: The intrinsic reward would be shaping reward to match this target: Tint -RRan(t) Rurge)? where Runget E Riarget- This guides the agent to learn a stable pose configuration, demonstrating the flexibility of Rem as a holistic state descriptor.
A.17 COMPARISON WITH LEARNED METRIC APPROACHES
Recent advancements in Quasimetric Learning (QRL) (Wang et al. 2023 Liu et al.] 2024) have
demonstrated the utility of learning distance metries from interaction data capture the underlying geometry of the state space. While both QRL and our Effective Resistance (R.f)) formulation serve distance metrics guide exploration, they differ fundamentally in their derivation, sample efficiency, and interpretability.
Analytic vs. Learned Derivation: Approaches like Wang al. (2023) learn metric function d(s, 8') via optimization over extensive transition data. While this allows the metric to adapt to complex, non-Fuclidean dynamics, inherently requires significant samples converge a useful representation. In contrast, our method analytically computes Ress from the graph Laplacian at each timestep based on the local observation. This analytic nature climinates the need for metric- learning phase, allowing our intrinsic reward to provide dense, meaningful signal immediately upon interaction.
Inductive Bias and Interpretability; A key advantage of our approach is its strong inductive bias: we posit that the "difficulty" of reaching goal is structurally correlated with the resistive connec- tivity of the graph constructed from the state. This yields high interpretability. As illustrated in Figure 1, a reduction Refs directly corresponds to tangible structural improvements, such as the widening of bottleneck the opening of new pathway. Conversely, metrics learned via function approximation can act as "black boxes." " making it difficult to ascertain whether the learned distance reflects true reachability spurious correlations in the training data.
Theoretical Guarantees: Finally, because our metric is grounded in spectral graph theory, we can derive formal guarantees regarding connectivity preservation and robust navigation (as detailed in Lemma 1 and Theorem 1). Establishing similar theoretical bounds for metrics learned purely from stochastic environment interactions remains challenging open problem.
43

---

Published as a conference paper at ICLR 2026
A.18 USE OF LLMS
We have used LLMs, particularly GPT and Perplexity, for paraphrasing some sentences to make them academically sound, basic proof reading and finding relevant literature works ensure com- pleteness and coverage.
44


Reviews:
[{"review_id": "21sJGJg7pw", "reviewer": "Reviewer_FfQG", "summary": "This paper proposes a reward shaping methods orignated from spectral graph theory to tackle reward sparsity in reinforcement learning setting. By modifying its instrinsic reward, the agent needs to maintain a graph of its surrounding environment first through its sensors (e.g. LIDARs) every timestep, then calculates its effective resistance between itself and the goal, which will be used as part of its reward construction.  They provide theoretical guarantees to prove they can learn a robust policy and also achieves faster convergence. Through experiments, they show their methods can beat state of the art baselines.", "questions": "- To increase the impact of this paper, can this method apply to a more general MDP setting, e.g. continuous MDP or tabular MDP, how would you construct the graph in such MDPs? specifically, what are nodes/edges/weights in these settings?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Good originality: abstract objects into nodes in graph, and design rewards based on the constructed graph. An novel reward shaping methods that encourage the agent to get closer to goal.\n- Quality: theoretically sound. Assumptions setup with proper citation and completely. Proved decreasing the effective resistance can also maintain connectivity on the graph. This paper also show the advantage of its algorithms emprically with extensive experiments.", "weaknesses": "- This methods can only be applied to specific domains, for example, robotics navigation tasks in the paper, in which the robots have a suite of sensors that are assumed not having noise and the robots having a good localization capability and can categorizes or recognize objects as nodes in the map. \n- I would appreciate more explanation on how the graph is constructed and what reducing effective resistance would bring on the main text, but overall the paper is easy to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T0kMV7acov", "reviewer": "Reviewer_Pwps", "summary": "This paper introduces a novel intrinsic reward mechanism for reinforcement learning in sparse reward environments based on effective resistance from spectral graph theory. The key idea is to construct a time-evolving graph from the agent's observations (specifically LiDAR data) where nodes represent the agent, goal, and environmental objects, and edges encode proximity relationships. The intrinsic reward is defined as the negative change in effective resistance between the agent and goal nodes, encouraging the agent to seek configurations that improve structural accessibility to the goal.", "questions": "1. How does the method scale to environments with many more objects or higher-dimensional observation spaces? What is the computational complexity as a function of graph size?\n2. How does the method scale to environments with many more objects or higher-dimensional observation spaces? What is the computational complexity as a function of graph size?\n3. How does the method perform in environments with dense rewards? Does the intrinsic reward provide benefits or potentially interfere with learning in such settings?\n4. How does the method perform in environments with dense rewards? Does the intrinsic reward provide benefits or potentially interfere with learning in such settings?\n5. Beyond τ, how sensitive is the method to other hyperparameters like α and β? The theoretical guidelines (Corollary 1) provide bounds, but practical selection seems to require empirical validation.\n6. How does this approach compare to more recent intrinsic motivation methods like NGU, RND, or ICM on the same environments?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The application of effective resistance from spectral graph theory to RL is creative and theoretically grounded. \n2. The paper provides a comprehensive theoretical analysis with multiple lemmas and a main theorem.", "weaknesses": "1. The method is specifically designed for environments where meaningful graph construction from observations is possible. The reliance on LiDAR data limits applicability to certain domains, and it's unclear how this would extend to other observation modalities or higher-dimensional state spaces.\n2. Algorithm 1 involves many design choices (clustering threshold τ, connectivity patterns, central node selection) that appear to require careful tuning. The sensitivity analysis (Section A.9) shows some robustness to τ, but the overall complexity raises concerns about generalizability.\n3. While the paper compares against several baselines, most are relatively older methods. More recent state-of-the-art intrinsic motivation methods could strengthen the comparison.\n4. While Section A.10 provides some runtime analysis, the computational cost of repeated graph construction and effective resistance computation could be prohibitive in real-time applications or larger graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uQXtf0gQ2v", "reviewer": "Reviewer_nmWg", "summary": "This paper proposes a new metric termed effective resistance that can be used as an intrinsic motivation reward for goal-conditioned RL tasks. The paper hypothesizes that this reward is better than using one proportional to Euclidean distance to the goal. The paper also performs some analysis to show that the proposed intrinsic reward is almost unbiased with respect to the extrinsic reward, and that using the proposed intrinsic reward leads to improved sample complexity.\n\nThe empirical evaluation on a suite of environments called Safety-Gymnasium seek to show that the above proposed theoretical guarantees hold, and that the proposed technique outperforms some reasonable baselines.", "questions": "* Could the authors clarify how more general exploration will be handled under the given scheme? Perhaps contrast with [3] from the weakness section, since that is an approach that handles more general exploration?\n* Could approaches like Quasimetric learning [1] also learn some metric like effective resistance?\n\n## References\n[1] Wang, T., Torralba, A., Isola, P. and Zhang, A., 2023, July. Optimal goal-reaching reinforcement learning via quasimetric learning. In International Conference on Machine Learning (pp. 36411-36430). PMLR.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Overall the idea is somewhat novel and might be a useful addition to the literature.\n* The proposed technique is interesting. Using ideas that consider graph flows to estimate how easy it is to navigate from one point to another has been seen to be useful in the past [1], and this modern revival of the technique could present some benefits.\n* Dynamic graph updates are very useful, allowing an environment that changes over time.\n* Theoretical analysis seems to be sound and gives some confidence that the proposed approach will not converge to a suboptimal solution and will help with some local exploration.\n* The evaluation methodology seems robust and statistically sound, and I especially appreciate the 1000 episode evaluations (5 training seeds and 200 episode evals per seed), which should capture variance in the policy and variance in the training.\n* The baselines that are used in the evaluation seem mostly reasonable. There are caveats here that I expand on in weaknesses.\n\n\n\n## References\n[1] Şimşek, Ö., Wolfe, A.P. and Barto, A.G., 2005, August. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd international conference on Machine learning (pp. 816-823).", "weaknesses": "There are some issues that keep this paper from being of a quality that I can confidently recommend for acceptance:\n* This paper is trying to suggest a new intrinsic motivation based on effective resistance in a graph. But seems to be specific to robotics type problems with objects present in the environment causing navigational or manipulational difficulties. If specific to robotics problems, the setup and writing should clarify and try to position itself accordingly so that it will attract the same community of researchers. It also does not compare to other GCRL methods for exploration in literature [1, 2, 3], or more up to date GCRL benchmarks like OGBench [4].\n* Part of the issue here is that the problem setup is specific to continuous state spaces and a 2 dimensional action space (Section 3.1).\n* My understanding is that the intrinsic reward is only calculated when the reward enters the agent's field of view. This seems like it will help mostly with local exploration instead of more generally.\n* The baselines proposed do not seem to be exploiting the structure of GCRL based problems from what I can tell. One of [1] or [3] would be great additions to show how effective the proposed intrinsic reward is in GCRL problems specifically.\n\n\n## References\n[1] Grace Liu, Michael Tang, and Benjamin Eysenbach. A single goal is all you need: Skills and exploration emerge from contrastive RL without rewards, demonstrations, or subgoals. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //openreview.net/forum?id=xCkgX4Xfu0\n\n[2] Ma, Y.J., Yan, J., Jayaraman, D. and Bastani, O., 2022. How Far I'll Go: Offline Goal-Conditioned Reinforcement Learning via $ f $-Advantage Regression. arXiv preprint arXiv:2206.03023.\n\n[3] Durugkar, I., Tec, M., Niekum, S. and Stone, P., 2021. Adversarial intrinsic motivation for reinforcement learning. Advances in Neural Information Processing Systems, 34, pp.8622-8636.\n\n[4] Park, S., Frans, K., Eysenbach, B. and Levine, S., 2024. Ogbench: Benchmarking offline goal-conditioned rl. arXiv preprint arXiv:2410.20092.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)