acceptodds
Under review as a conference paper at ICLR 2027

Relative Deadline Regret for Goal-Conditioned Reinforcement Learning

Abstract

Goal-conditioned reinforcement learning trains a policy to reach a desired goal from the current state with a success signal provided only upon arrival in the sparse reward setting.Policy learning near obstacles is difficult because actions that begin useful detours can receive the same immediate reward as actions that make no progress.Bellman updates compare these actions through estimated future rewards whose errors can affect policy optimization.Relative Deadline Regret (RDR) is proposed to compare candidate actions through completion probability, the probability of first arrival within a step limit called a deadline.Regret measures the completion probability lost against the best candidate as a share of the positive probability of that candidate.An arrival predictor learns from observed arrivals and unfinished attempts to compare candidate actions without Bellman action value targets.The policy fits a weighted average that favors smaller regrets across deadlines and follows a local direction of higher predicted completion called the completion gradient.Theoretical analysis bounds candidate and executed action losses and establishes convergence under stated stability conditions for the expected policy fitting update.Experimental results show the highest success rate averaged equally over the evaluated manipulation and navigation tasks and connect the candidate comparisons to learned actions near obstacles.

Primary area:
reinforcement learning
Keywords:
reinforce learning, planning, sparse reward

Reviews

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

This paper proposes RDR, which scores the policy action and its perturbations by predicted first-arrival probabilities at several deadlines, normalized by the best candidate, and fits the policy to their weighted average. It reports the best average success over manipulation and maze tasks, with the largest gains on a few maze layouts.

Critical strengths

Comparing actions through arrival probabilities at several deadlines, learned without bootstrapping, is an intuitive way to credit detours around obstacles. The maze results are strong, and the ablations openly show which components matter.

Critical weaknesses
  1. Novelty is limited. The arrival predictor comes from SVL, the candidate weighting follows MPO and the gradient term is DDPG-style, while the relative-regret normalization amounts to a per-deadline softmax temperature. The ablations show that the adaptive deadline weights and the gradient term add little. MPO: A. Abdolmaleki et al. Maximum a Posteriori Policy Optimisation. ICLR, 2018. DDPG: T. P. Lillicrap et al. Continuous Control with Deep Reinforcement Learning. ICLR, 2016.
  2. The theory does not support the method. The return bound is vacuous for every discount factor, because a step-shaped deadline utility cannot approximate geometric discounting at states that cannot reach the goal immediately, and the convergence result simply assumes the contraction it needs.
  3. The evidence is weaker than the text suggests. Much of the aggregate gain comes from a few maze layouts, RDR trails the strongest baseline on most manipulation tasks, including an obstacle task, and the candidate-fitting ablation compares against a degenerate control. The authors also report that executing the fitting target directly does not improve arrival.
  4. Key details and controls are missing. Seeds, interaction budgets and most hyperparameters are not given in the main text, the claim that Bellman errors are the problem is never tested with a TD-based critic in the same pipeline, and DWSL is not compared.
Questions for authors
  1. How many seeds were run, how many environment steps make one epoch, and do the baselines receive the same interaction budget, implementations and tuning effort? Please give per-task means with standard errors and a significance test for the small margins, and state whether Push-Hard, PickPlace-Hard and CustomLarge come from prior work.
  2. What happens if F̂ is replaced by a TD-learned Q-function or distance inside exactly the same candidate fitting and normalization pipeline? Could you also add DWSL and an AWR- or MPO-style weighting baseline? AWR: X. B. Peng et al. Advantage-Weighted Regression: Simple and Scalable Off-Policy Reinforcement Learning. arXiv:1910.00177, 2019.
  3. Please describe the direct target substitution experiment (L484-485) and its numbers. If executing ā does not raise arrival rates, where does the gain come from? A calibration plot of F̂ against empirical completion under the current policy, split into obstructed and clear states, would help.
  4. Do you agree that Δ_γ ≥ 1 - γ + γ^(max I) whenever H = 1 is not admitted, which makes Eq. (7) trivial? Could you instead bound suboptimality for the deadline objective Σ_H ω_H F_H, and check whether L_g < r holds for the hyperparameters actually used?
  5. Please tune λ_g for RDR_NoReg before comparing, explain why the completion gradient is kept given its effect on PickPlace-Hard, and report RDR_Return in the main text together with a sweep over γ.
Reviewer_Sm58OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Relative Deadline Regret (RDR), a method for goal-conditioned reinforcement learning that compares candidate actions through their predicted probabilities of reaching a goal within multiple deadlines. Across ten manipulation and navigation tasks, the paper reports an average final success rate of 83.63%, compared with 74.75% for TMD, the strongest aggregate baseline.

Critical strengths
  1. The deadline-based perspective provides an interesting policy-learning objective. Comparing completion probabilities across deadlines can distinguish actions that are ineffective under short time budgets but useful when more time is available. The treatment of unfinished observations as censored data, rather than permanent failures, is also appropriate.

  2. The reported policy improvements are substantial on several tasks. RDR achieves 91.1% success on CustomLarge versus 64.7% for the best baseline on that task, and 95.6% on Medium versus 75.3%. These results support the usefulness of the overall learning procedure on some obstacle-navigation problems.

  3. The paper examines component contributions and acknowledges limitations. The ablations distinguish candidate fitting, probability normalization, completion gradients, and deadline weighting. The authors appropriately identify candidate fitting and normalization as the clearest empirical contributors, while reporting that the other components have smaller or task-dependent benefits.

Critical weaknesses

Weakness: Predictor reliability and its connection to actual policy improvement are not sufficiently validated.

The arrival predictor determines the policy’s learning targets. The central question is therefore not only whether predicted regret decreases, but whether these comparisons identify actions with higher actual completion probabilities and whether that advantage transfers to the learned, executed action.

However, the diagnostics in Figures 4–6 primarily use quantities computed by the learned predictors themselves, including predicted regret, deadline weights, and the fraction of states admitting a comparison. Figure 5 uses each method’s own predictor, while Figure 6 measures regret over different admitted subsets for different methods. These analyses help describe the learning signals and resulting behavior, but do not independently establish that predicted candidate rankings and relative probability differences agree with actual environment outcomes.

This gap matters because the predictor is trained on replay containing past policies and exploratory behavior, whereas the intended comparison concerns executing a candidate action and then following the current policy. Perturbed candidates may also differ from the actions represented in the training data. The authors acknowledge these issues and include prediction error in the theoretical analysis, but this does not establish that the error is small enough for reliable candidate comparisons in practice.

The reported finding that direct target substitution did not improve arrival rates at the tested states is particularly relevant. This does not invalidate the benefits of iterative policy training. It does, however, motivate separating three stages: identifying useful individual candidates, combining them into a weighted-average target, and transferring that target to the executed policy. The available analyses do not sufficiently establish which stages preserve an actual completion advantage. Consequently, the final success-rate improvements support the overall algorithm more strongly than they support the proposed explanation in terms of reliable completion comparisons producing better actions.

Questions for authors
  1. Do predicted candidate rankings agree with actual completion outcomes? From a common set of states and goals, how accurately does the predictor rank candidate actions when each is executed once and followed by the same fixed current policy? Empirical deadline-specific completion probabilities would provide an independent reference. On a representative task, could you compare these outcomes with the predicted rankings and relative probability differences, distinguishing recorded replay actions from perturbed candidates?

  2. How should the negative direct-target-substitution result be interpreted? Please clarify the execution protocol and results of this test. Does the lack of improvement arise from inaccurate candidate evaluation, from averaging individually useful candidates, or from benefits that emerge only through repeated policy fitting? Comparing the actual completion outcomes of individual candidates, the weighted-average target, and the updated policy would help distinguish these possibilities.

  3. What is the advantage over predicting future states and evaluating goal attainment with a world model? A relevant alternative would learn a transition model from the same collected data, roll out the current policy after each candidate initial action, and evaluate whether the predicted states reach the goal within each deadline. Multiple rollouts from a probabilistic model or an ensemble could provide completion estimates for the same regret weighting and policy-fitting procedure. Have you compared against such a model-based completion baseline? A comparison on a representative task would help clarify the benefit of predicting arrival probabilities directly rather than obtaining them through predicted future states. In particular, candidate-ranking accuracy, final policy success, and computational cost would be informative under the same environment-interaction budget.

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

This paper focuses on goal-conditioned RL with deadlines. They propose to learn a predictor to estimate the completion probabilities, and then learn the policy from this predictor. The authors tried to provide some theoretical analysis of the proposed methods. They also provide experimental results and an ablation study to demonstrate the effectiveness of their methods.

Critical strengths

None.

Critical weaknesses
  1. The proposed method is not well explained. It is unclear how the proposed method differ from existing methods, and how it addresses the difficulties of the setting as described in Section 1.
  2. The notations are inconsistent and hence confusing. For example, rr is used for reward, regret, the penalty coefficient and the displacement bound simultanteously, while the policy is represented by either uu or μ\mu. It is also weird to first define a gradient v^\hat{v} and then define the loss as ⟨⋅,v^⟩\langle\cdot,\hat{v}\rangle.
  3. The theoretical analysis relies on strong and unreasonable assumptions, and the presentation is unclear. Theorem 4.1 requires strong penalty such that r>Lgr>L_g the Lipschitz factor of the gradient. Theorem 4.2 involves many notations which are not formally defined (e.g. t,c,et, c, e).
  4. The experiments are not convicing enough. In Figure 3 (especially (b) and (d)), RDR seems to converge fast but not at the highest success rate, while other methods like TMD have the trends to reach higher success rates if given more training epochs. In the ablation studies (Figure 6,7), the completion gradient seems to contribute little while the candidate fitting dominates. Besides, RDR_fixed and RDR_return are missing in the figures.
Questions for authors

See Weaknesses.

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

The paper proposes Relative Deadline Regret for GCRL in obstacle-cluttered environments. Instead of relying on Bellman value objectives, RDR compares candidate actions based on their probabilities of reaching the goal within multiple deadlines, and derives a policy-fitting objective from this. The paper establishes convergence guarantees, and empirically benchmarks RDR against HER/GCSL/SVL/CRL/QRL/TMD on 10 manipulation and navigation tasks.

Critical strengths

The paper is well-motivated, a policy may prefer different actions depending on the time budget.

Critical weaknesses

The main file does not include the references or the appendix, even though they are provided in the supplementary material.

Theorem 2 is largely a qualitative characterization of the error sources and cannot serve as a quantitative performance guarantee.

The theoretical assumptions are strong and difficult to satisfy in practice. The theory assumes prediction quality and coverage of the candidate set; however, in the actual algorithm the candidates are sampled via Gaussian perturbation, which provides no guarantee that the candidate set covers the important actions. Theoretical analysis shows that the coverage gap hurts performance, yet the paper offers no empirical analysis of how large this gap actually is on the benchmark tasks.

The motivation section emphasizes the error issues caused by Bellman bootstrapping, yet no experiment directly quantifies the impact of the Bellman error in the test environments. Throughout the paper, there is no set of diagnostic experiments that directly compares the magnitude of the TD-bootstrap error with the RDR prediction error.

The paper does not specify how the hyperparameters of the compared (baseline) methods were obtained.

The paper barely discusses computational overhead. In practical engineering deployment, K=32 is quite costly; how much does performance degrade as K decreases?

The method involves a large number of hyperparameters, K,Hmax,η,β,λg,bHK, H_{max}, \eta, \beta, \lambda_g, b_H, the hindsight ratio, the noise scaling schedule, among others — yet the paper provides no hyperparameter sensitivity analysis.

Questions for authors

Refer to the Weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.