acceptodds
Withdrawn from ICLR 2027

Plug-and-Play Graph-Based Intrinsic Reward for Exploration of Cost-Aware Reinforcement Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Introducing action costs increases the difficulty of exploration in complex, sparse-reward state spaces for reinforcement learning (RL). To address this challenge, we propose a novel graph-based reward shaping method, termed Graph Intrinsic Reward (GIR), which uses graph to model the structure of explored state space to enable efficient exploration-exploitation in cost-aware RL. Specifically, GIR incrementally constructs a graph in which each node maintains both visit counts and value estimates, from which a count-based exploration reward and a potential-based exploitation reward are derived to guide the agent in escaping initial suboptimal states under costly actions. Through reward-gated modulation, GIR reduces ineffective exploration, while potential-based value propagation over the graph guides the agent toward high-return regions. We further analyze the impact of GIR on policy optimality and show that, from a theoretical perspective, GIR asymptotically preserves the optimal policy. Extensive experiments demonstrate that the proposed reward shaping strategy effectively guides exploration towards goal states and outperforms state-of-the-art exploration methods in cost-aware environments. Our implementation is available at https://anonymous.4open.science/r/GIR-48BD/.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Reward shaping, Cost-aware MDP, Sparse reward

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_LH7cOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Graph Intrinsic Reward (GIR), a reward shaping method for cost-aware exploration in reinforcement learning. GIR constructs a state-transition graph by clustering visited states, where nodes maintain visitation counts and edges represent observed transitions and their associated rewards. Based on this graph, GIR uses visitation counts to provide exploration bonuses and propagates value information to guide the agent toward promising states. Experiments on MountainCar, PointMaze, and MiniGrid demonstrate improvements over several exploration baselines.

Critical strengths
  • The methods combines count based bonuses and graph-based environmental reward value backups in a simple way.
  • The experiments demonstrate improvements across environments they considered over existing baselines.
Critical weaknesses
  1. Unclear connection to cost-aware RL. The proposed graph-based exploration mechanism appears to be a general exploration strategy rather than one specifically designed for cost-aware RL. Cost awareness is primarily introduced through a heuristic reward-gating function, making the motivation and novelty of the method unclear.

  2. Limited evidence of scalability. The method requires maintaining an expanding state-transition graph and performing value propagation over it. Although the authors acknowledge this limitation, the computational overhead is evaluated only for graphs with up to 1,000 nodes. This provides insufficient evidence to support the scalability claim, which is explicitly stated as one of the contributions in the Introduction:

    We provide theoretical analysis and empirical experiments to validate the effectiveness and scalability of GIR.

  3. Potential flaw in the theoretical analysis. In Appendix A.2 (Eq. 12), the authors claim that the edge weights updated via an exponential moving average (EMA) converge almost surely to their expected rewards: At+1=(1−α)At+αrt.A_{t+1}=(1-\alpha)A_t+\alpha r_t. However, for i.i.d. rewards with Var⁡(rt)=σ2>0\operatorname{Var}(r_t)=\sigma^2>0 and a constant α∈(0,1)\alpha\in(0,1), we have

=\frac{\alpha\sigma^2}{2-\alpha}>0.$$ Thus, the estimation variance does not vanish, and the claimed almost-sure convergence does not hold in general. This raises concerns about the validity of the subsequent optimality analysis, particularly if it relies on this convergence claim.
Questions for authors

What makes the proposed graph-based method suitable for cost-aware RL, compared to general sparse-reward exploration? Would the method provide similar benefits without action costs?

Reviewer_sAQ2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a new method for improving the exploration in sparse-reward environments using a dynamically generated graph over the visited transitions or the replay buffer.

Critical strengths

Please refer to the weaknesses section.

Critical weaknesses
  1. The main weakness of the paper is that the proposed idea of constructing a graph from the replay buffer or previously visited transitions has already been explored in prior work [1], which is not cited in this paper. Other studies have also employed tree- or graph-based search to improve exploration, but [1] is particularly relevant because its approach closely resembles the proposed method. Furthermore, the idea of clustering states based on Euclidean distance has also been introduced in [1].

  2. Although the paper introduces cost-aware RL, it does not provide a sufficiently clear mathematical formulation explaining how costs and rewards jointly affect the value function.

  3. The paper contains considerable repetition between the Introduction and Preliminaries sections.

  4. The preliminaries do not adequately introduce the MDP formulation or define the variables associated with the directed graph constructed from the environment. More precise definitions are needed to make the proposed method understandable.

  5. What is the difference between ϕ\phi, which is computed using the graph's adjacency matrix, and the main value function estimated by the critic? They both estimate the discounted return, and the former seems unnecessary here.

  6. The proposed method constructs a graph and updates its adjacency matrix through KK steps of value iteration over the entire graph. This raises significant scalability concerns, particularly in high-dimensional state spaces commonly encountered in robotic tasks. The authors should explain how these computations can be performed efficiently as the number of visited states and graph nodes increases.

  7. The paper claims that the proposed method achieves asymptotic optimality. However, no clearly stated theorem with its assumptions is presented to support this claim.

  8. The evaluated environments do not appear sufficiently challenging to establish the effectiveness of the proposed method. Additionally, the paper does not clearly explain how costs were manually introduced into these environments. The experimental evaluation also lacks comparisons with existing graph-based exploration methods, making it difficult to assess the advantages of the proposed approach over relevant prior work.

1- ETGL-DDPG: a deep deterministic policy gradient algorithm for sparse reward continuous control

Questions for authors

Please refer to the weaknesses section.

Reviewer_RtVmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Graph Intrinsic Reward (GIR), a reward shaping framework for exploration in cost-aware reinforcement learning. GIR incrementally constructs a state transition graph and combines two intrinsic rewards: a count-based exploration bonus and a potential-based reward obtained through value propagation over the graph. A reward gate based on immediate environment rewards is further introduced to suppress costly exploration. The authors provide an asymptotic policy invariance analysis and evaluate GIR on MountainCar, PointMaze, and MiniGrid environments. The experiments report improvements over several exploration baselines, supported by ablation studies and computational overhead analysis.

Critical strengths
  1. Relevant problem formulation.

The paper addresses the exploration difficulty introduced by action costs under sparse rewards. This is a meaningful problem, as conventional novelty-driven exploration may incur substantial penalties without improving task performance. The motivation is clear and relevant to practical RL applications.

  1. A modular combination of exploration and exploitation signals.

GIR combines visitation-based novelty with graph potential propagation, allowing the agent to explore under-visited regions while receiving guidance toward previously discovered high-value regions. The formulation is relatively simple and does not require modifying the underlying RL optimization procedure.

  1. Encouraging empirical performance and component analysis.

Figures 2 and 4 show substantial performance improvements on MountainCar and PointMaze. The ablations in Figure 5 provide evidence that the exploration bonus, potential reward, and reward gate contribute to the overall performance. These results support the usefulness of the proposed combination.

  1. Evaluation across different RL algorithms and observation types.

The additional experiments in Appendix C examine compatibility with several value-based and actor-critic algorithms, as well as pixel-based MiniGrid environments. The reported computational analysis in Table 4 also provides useful information about the implementation overhead of the graph-based module.

Critical weaknesses
  1. A significant mathematical gap in the policy invariance proof.

The theoretical analysis in Section 4.3 and Appendix A relies on the convergence of graph edge weights. Specifically, Appendix A.2 claims that the fixed-step-size exponential moving average in Eq. (3) converges almost surely to the expected environment reward under a stationary visitation distribution.

This conclusion does not generally hold. For a stationary sequence of stochastic rewards with nonzero variance, an EMA with constant coefficient α typically retains nonzero asymptotic variance rather than converging almost surely to its expectation. Stationarity of the visitation distribution is insufficient to establish Eq. (12) in Appendix A.

Consequently, the subsequent convergence claims for the graph potentials and the limiting shaped reward are not justified under the stated assumptions. Since asymptotic policy preservation is a central theoretical contribution, this is a substantive concern rather than a minor proof omission.

  1. The graph potential may not accurately represent achievable long-term returns.

Equation (6) computes node potentials through a max-based value iteration over observed graph edges. However, these edges store averaged immediate rewards without explicitly modeling action-conditioned transition probabilities.

In stochastic environments, an observed transition does not necessarily correspond to an outcome that the agent can reliably select. Maximizing over observed successors may therefore overestimate achievable returns, especially when several actions or stochastic outcomes are aggregated into the same edge.

The paper does not sufficiently discuss the assumptions under which this graph-based propagation provides a meaningful approximation of long-term value. Additionally, Figure 1 depicts an edge update using Q predictions, whereas Eq. (3) and Algorithm 1 use environment rewards. This inconsistency should be clarified.

  1. The reward-gated mechanism provides limited evidence of genuine cost awareness.

The proposed reward gate in Eq. (4) is defined as σ(r_env), making its effect highly dependent on the numerical scale of the environment reward.

For instance, Appendix B.2 specifies an action penalty of -0.1a² for MountainCar, with a ∈ [-1, 1]. Consequently, the sigmoid gate varies only between approximately 0.475 and 0.5 for ordinary non-terminal transitions. Such a narrow range raises questions about whether the gate can meaningfully distinguish actions with different costs.

More importantly, the method does not explicitly separate action costs from task rewards. It remains unclear whether the proposed gate offers a principled mechanism for cost-aware exploration or simply rescales the conventional count-based bonus.

  1. The methodological novelty is limited, and the experimental attribution is incomplete.

The main components of GIR, including visitation-based exploration, potential-based reward shaping, and graph-based value propagation, are individually well-established. The primary contribution appears to be their integration with a reward-dependent modulation mechanism.

Although Figure 5 evaluates several ablations, the paper does not compare GIR against a straightforward combination of count-based exploration and potential-based shaping without the proposed graph formulation.

Such a comparison is important for determining whether the performance gains arise from the particular GIR design or primarily from combining complementary intrinsic reward signals. Without this control, the incremental contribution over existing exploration and reward shaping approaches remains difficult to assess.

  1. The experimental evaluation does not sufficiently isolate cost-aware exploration.

The main experiments use conventional sparse-reward benchmarks with action penalties. While these environments are suitable for evaluating exploration, they do not fully establish the effectiveness of GIR across different cost regimes.

In particular, the paper does not systematically vary the action-cost coefficient or report how goal-reaching success, accumulated action cost, and exploration efficiency change as costs increase. The learning curves primarily report cumulative rewards, making it difficult to distinguish improvements in task success from reductions in exploration cost.

Furthermore, Figure 4 evaluates fixed start-goal configurations selected to create difficult exploration tasks. Results across additional configurations would help establish whether the observed improvements generalize beyond these specific layouts.

  1. Scalability and sensitivity to graph construction remain insufficiently characterized.

GIR relies on online state clustering, graph updates, and repeated potential propagation. Its performance may therefore depend considerably on the clustering threshold, state representation, and graph size.

Although Figure 5 includes a graph-size ablation, the analysis does not systematically characterize the sensitivity of the method across environments. Table 4 reports increasing computational overhead as the graph grows: the total time rises from approximately 4.17 ms per step for TD3 to 6.02 ms for GIR with 1000 nodes.

This overhead may be acceptable in the evaluated tasks, but the experiments do not establish scalability to substantially larger graphs or higher-dimensional continuous state spaces. The broad plug-and-play and scalability claims should therefore be interpreted more cautiously.

Questions for authors
  1. Convergence analysis: How is the almost-sure convergence of the fixed-step-size EMA in Appendix A.2 justified? Would the policy invariance result require a diminishing update coefficient or additional assumptions on reward stochasticity?

  2. Graph potential estimation: How does the max-based propagation in Eq. (6) account for stochastic transitions and action-dependent reachability? Also, does the implementation update graph edges using immediate environment rewards or Q-value estimates, as suggested by Figure 1?

  3. Cost-aware reward gate: Given the narrow range of σ(r_env) in MountainCar, what evidence supports the claim that the gate meaningfully suppresses costly exploration? Are there results under different action-cost coefficients?

  4. Contribution of the graph formulation: How would GIR compare with a baseline that combines count-based intrinsic rewards and conventional potential-based shaping under matched training conditions?

  5. Evaluation robustness: Are the reported improvements consistent across different start-goal configurations and action-cost settings? Can the authors distinguish gains in goal-reaching success from reductions in accumulated action costs?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.