Paper deep dive
RELACE: retrospective likelihood-based action credit estimation for long-horizon language agents
Sayak Chakrabarti, Sathish Reddy Indurthi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/7/2026, 9:12:07 AM
Summary
The paper introduces RELACE, a critic-free framework for fine-grained credit assignment in long-horizon language agents. RELACE combines retrospective likelihood-based action assessment with state-conditioned advantage estimation. It evaluates executed actions under both original and outcome-augmented contexts to derive retrospective relevance weights, which reweight discounted task returns. These weighted returns are then used to construct local advantages by comparing actions from equivalent states, complementing trajectory-level Group Relative Policy Optimization (GRPO) supervision. Experiments on ALFWorld and WebShop demonstrate that RELACE significantly outperforms baselines like GRPO, GiGPO, and HCAPO.
Entities (10)
Relation Signals (9)
RELACE → evaluatedon → ALFWorld
confidence 95% · Experiments on ALFWorld and WebShop... With the 1.5B model, RELACE achieves 96.35% success on ALFWorld
RELACE → evaluatedon → WebShop
confidence 95% · Experiments on ALFWorld and WebShop... 79.43% on WebShop
RELACE → istype → critic-free framework
confidence 95% · We introduce RELACE, a critic-free framework that integrates retrospective action assessment
RELACE → outperforms → GRPO
confidence 95% · demonstrate substantial improvements over GRPO, GiGPO, and HCAPO.
RELACE → outperforms → GiGPO
confidence 95% · surpassing GiGPO by 5.47 and 5.60 percentage points, respectively.
RELACE → outperforms → HCAPO
confidence 95% · exceed GiGPO by 5.47 and 5.60 percentage points, HCAPO by 9.35 and 10.93 points
RELACE → usesmodel → Qwen2.5-7B-Instruct
confidence 95% · Experiments on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct
RELACE → usesmodel → Qwen2.5-1.5B-Instruct
confidence 95% · Experiments on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Group Relative Policy Optimization (GRPO) avoids a separate critic by estimating advantages from rollout groups. For multi-turn agents, however, trajectory-level supervision provides coarse, noisy credit: terminal rewards do not locate errors and can penalize useful actions alongside mistakes. Group-in-Group Policy Optimization (GiGPO) and subsequent methods refine supervision through state-conditioned comparisons, but their credit estimates remain sensitive to downstream decisions and outcomes. We introduce RELACE, Retrospective Likelihood-based Action, a critic-free framework that integrates retrospective action assessment with state-conditioned advantage estimation. RELACE evaluates executed actions through teacher-forced likelihood scoring under both their original contexts and outcome-augmented contexts. Comparing these likelihoods yields a trajectory-normalized retrospective factor that captures outcome-dependent changes in action plausibility, rather than hindsight plausibility alone. We use this factor to reweight discounted task returns and construct local advantages by comparing weighted returns among actions from equivalent states within a task. This couples retrospective relevance with observed reward, producing fine-grained credit that complements trajectory-level GRPO supervision. Temporal smoothing and success-protecting masking further stabilize the local signal. RELACE requires neither auxiliary value nor reward models nor additional autoregressive rollouts for credit estimation. Experiments on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct demonstrate substantial improvements over GRPO, GiGPO, and HCAPO. With the 1.5B model, RELACE achieves $96.35\%$ success on ALFWorld and $79.43\%$ on WebShop, surpassing GiGPO by $5.47$ and $5.60$ percentage points, respectively.
Tags
Links
- Source: https://arxiv.org/abs/2610.07349v1
- Canonical: https://arxiv.org/abs/2610.07349v1
Trouble viewing inline? Open PDF directly →
Full Text
63,162 characters extracted from source content.
Expand or collapse full text
RELACE: retrospective likelihood-based action credit estimation for long-horizon language agents Sayak Chakrabarti †thanks: Work done during an internship at Zoom Communications, Inc. Affiliation: Columbia University Email: sayaksc@gmail.com Sathish Reddy Indurthi †thanks: Project Mentor. Affiliation: Zoom Communications, Inc. Email: sathishreddy.indurthi@zoom.us Abstract Group Relative Policy Optimization (GRPO) avoids a separate critic by estimating advantages from rollout groups. For multi-turn agents, however, trajectory-level supervision provides coarse, noisy credit: terminal rewards do not locate errors and can penalize useful actions alongside mistakes. Group-in-Group Policy Optimization (GiGPO) and subsequent methods refine supervision through state-conditioned comparisons, but their credit estimates remain sensitive to downstream decisions and outcomes. We introduce RELACE, Retrospective Likelihood-based Action, a critic-free framework that integrates retrospective action assessment with state-conditioned advantage estimation. RELACE evaluates executed actions through teacher-forced likelihood scoring under both their original contexts and outcome-augmented contexts. Comparing these likelihoods yields a trajectory-normalized retrospective factor that captures outcome-dependent changes in action plausibility, rather than hindsight plausibility alone. We use this factor to reweight discounted task returns and construct local advantages by comparing weighted returns among actions from equivalent states within a task. This couples retrospective relevance with observed reward, producing fine-grained credit that complements trajectory-level GRPO supervision. Temporal smoothing and success-protecting masking further stabilize the local signal. RELACE requires neither auxiliary value nor reward models nor additional autoregressive rollouts for credit estimation. Experiments on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct demonstrate substantial improvements over GRPO, GiGPO, and HCAPO. With the 1.5B model, RELACE achieves 96.35%96.35\% success on ALFWorld and 79.43%79.43\% on WebShop, surpassing GiGPO by 5.475.47 and 5.605.60 percentage points, respectively. Code: https://github.com/sayaksc/RELACE 1 Introduction Large language models (LLMs) can act as autonomous agents, making sequential decisions in partially observable environments (Yao et al., 2023). Tasks such as web navigation and simulated household interaction require coordinated actions to achieve user goals (Yao et al., 2022; Shridhar et al., 2021). Training agents for these tasks often involves sparse or delayed rewards, including terminal success signals, destabilizing training by obscuring intermediate actions’ contributions (Feng et al., 2025). This highlights the temporal credit-assignment problem: an outcome evaluates the trajectory as a whole but provides limited guidance about individual decisions (Harutyunyan et al., 2019). Group Relative Policy Optimization (GRPO) avoids a separate value critic by estimating relative advantages from samples for the same task (Shao et al., 2024). With outcome-level supervision, however, GRPO assigns the same scalar advantage to all actions within a trajectory. This coarse signal does not distinguish useful decisions from incidental or redundant actions, and a late error can obscure useful earlier behavior (Feng et al., 2025). The challenge is to obtain informative action-level credit while retaining critic-free simplicity. Group-in-Group Policy Optimization (GiGPO) compares discounted downstream returns among decisions from matched environment states (Feng et al., 2025). Such comparisons account for the decision context, but their targets still reflect subsequent actions and transitions. Moreover, limited rollout sampling can make local estimates unreliable, assigning disproportionately large advantages to rare actions with favorable continuations (Li et al., 2026). State-level comparison supports local credit assignment, while leaving room for information about an action’s relationship to the outcome. Hindsight learning offers complementary information. Hindsight Experience Replay reuses achieved outcomes as alternative goals (Andrychowicz et al., 2017), whereas Hindsight Credit Assignment uses outcome-conditioned action distributions to inform credit allocation (Harutyunyan et al., 2019). For language agents, this perspective motivates a practical question: how does outcome information change the model’s assessment of an executed action? An action may score highly in hindsight because it was already plausible in its original context. Comparing both contexts can distinguish baseline plausibility from outcome sensitivity. HCAPO applies hindsight-conditioned action scoring to long-horizon language-agent optimization (Tan et al., 2026). Although its theoretical formulation motivates a hindsight-to-original probability ratio, its practical estimator normalizes each hindsight score by the mean hindsight score along the trajectory. It does not explicitly evaluate each executed action’s original-context denominator. This raises a design question: how should explicit original-versus-hindsight scoring be combined with state-conditioned comparisons of downstream returns? We propose RELACE, a critic-free framework that combines explicit retrospective scoring with state-conditioned advantage estimation. After termination, RELACE augments each intermediate context with the observed terminal outcome. The frozen behavior policy scores the same executed action under original and outcome-conditioned contexts using teacher forcing. We form a ratio of these length-normalized likelihood-based scores, normalize the ratios within each trajectory, and clip them before reweighting discounted terminal returns. The resulting weights represent retrospective relevance rather than causal contribution. RELACE applies temporal smoothing to the weighted returns and computes local relative advantages within state-matched groups. Thus, outcome information enters the return targets before local comparison, while a trajectory-level GRPO advantage retains supervision from overall task performance. Following HCAPO, we use temporal smoothing and an asymmetric mask that removes negative local corrections from successful trajectories (Tan et al., 2026). The environment reward is unchanged; RELACE modifies advantage-estimation targets without a separate additive reward. Teacher-forced scoring adds likelihood evaluation without autoregressive rollouts or auxiliary value or reward models. Our primary contributions are: • We develop an explicit original-versus-hindsight scoring mechanism for executed language actions. Ratios of length-normalized action scores yield trajectory-normalized, clipped weights for retrospective credit estimation using the behavior policy itself. • We integrate these weights into a state-conditioned advantage estimator by reweighting discounted task returns before local group comparison. The resulting local signal complements trajectory-level GRPO supervision within critic-free optimization. • We evaluate RELACE on ALFWorld and WebShop using Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct. With the 1.5B model, RELACE achieves the highest reported mean success rates among the compared methods: 96.35%96.35\% on ALFWorld and 79.43%79.43\% on WebShop. These exceed GiGPO by 5.475.47 and 5.605.60 percentage points, HCAPO by 9.359.35 and 10.9310.93 points, and GraphGPO by 3.643.64 and 0.780.78 points, respectively. 2 Related work Credit Assignment in Agentic Reinforcement Learning. Long-horizon language-agent tasks require learning from rewards that provide limited feedback about individual decisions (Feng et al., 2025). Actor–critic implementations of PPO estimate advantages using learned value functions, introducing additional model training and value-estimation error (Schulman et al., 2017). Process supervision offers an alternative source of intermediate feedback through learned step-level evaluators, as demonstrated in mathematical reasoning (Lightman et al., 2023). Critic-free methods such as REINFORCE Leave-One-Out (RLOO) and Group Relative Policy Optimization (GRPO) instead construct advantages from sampled returns without fitting a separate value network (Ahmadian et al., 2024; Shao et al., 2024). When used with outcome-level supervision, however, a trajectory-level scalar advantage does not distinguish the roles of individual actions, motivating finer-grained credit estimators for multi-turn interaction (Feng et al., 2025). State-Conditioned and Structured Credit Assignment. GiGPO constructs local relative advantages by grouping decisions with matching environment states and comparing their discounted downstream returns (Feng et al., 2025). HGPO addresses historical-context inconsistency within step-level groups by constructing a hierarchy of groups with different degrees of context agreement (He et al., 2026). GraphGPO aggregates sampled trajectories into a state-transition graph and assigns credit according to estimated progress toward task goals (Cheng et al., 2026). ECPO focuses on the reliability of local comparisons, shrinking low-count action estimates and downweighting groups dominated by within-action noise (Li et al., 2026). These approaches refine the comparison structure, progress signal, or statistical reliability of step-level credit. RELACE builds on state-conditioned grouping and investigates how outcome-conditioned action scores can inform the return targets used in those comparisons. Exploration and Training Stability. Complementary work studies the learning dynamics of multi-turn agents. RAGEN examines training instability and the effects of rollout diversity, interaction granularity, and sampling frequency (Wang et al., 2025b). EPO regulates policy entropy across training phases to balance exploration and exploitation (Xu et al., 2025). EMPG modulates policy-gradient signals using step-wise uncertainty and final task outcomes, with an additional signal favoring predictable future interactions (Wang et al., 2025a). These methods provide complementary perspectives on how exploration and update weighting affect learning from sparse feedback. Hindsight Credit Assignment and Language Agents. Hindsight methods use information observed after an action to improve learning from collected experience. Hindsight Experience Replay (HER) relabels experience with achieved goals, enabling learning even when the intended goal is not reached (Andrychowicz et al., 2017). Hindsight Policy Gradients extends this idea to goal-conditioned policy-gradient estimation (Rauber et al., 2019). Hindsight Credit Assignment (HCA) uses outcome-conditioned action distributions to estimate the relationship between earlier actions and subsequent outcomes (Harutyunyan et al., 2019). Building on HCA, COCOA estimates counterfactual contributions to rewards or reward-relevant outcome representations, addressing limitations of conditioning on detailed future states (Meulemans et al., 2023). HCAPO brings hindsight-based credit assignment to long-horizon language agents through outcome-conditioned action scoring and a combination of trajectory-level and step-level advantages (Tan et al., 2026). Although its theoretical formulation motivates a hindsight-to-original probability ratio, its practical estimator normalizes each hindsight score by the mean hindsight score along the trajectory. RELACE explicitly scores each executed action under both its original and outcome-conditioned contexts, then incorporates the resulting relevance weights into state-conditioned return comparisons. Its distinction lies in explicit original-context scoring, integration with local group baselines, teacher-forced evaluation, temporal smoothing, and protective masking. The complete estimator is presented in Section 3. 3 Retrospective likelihood-based action credit assignment We introduce RELACE, a critic-free policy optimization algorithm for fine-grained credit assignment in partially observable multi-turn interactions. RELACE combines three components: (i) an episode-level relative advantage capturing global trajectory quality, (i) a retrospective likelihood ratio estimating intermediate actions’ relevance to the outcome, and (i) a state-conditioned baseline comparing diverging actions from matched environment states. The term retrospective emphasizes that RELACE measures how outcome information changes the policy’s assessment of an executed action, rather than the outcome-conditioned score alone. 3.1 Outcome-conditioned hindsight relabeling For each task x, we sample K trajectories from the behavior policy πθold _ _old. Trajectory τi _i contains TiT_i actions, receives terminal reward RiR_i, and ends with observed outcome sifinals_i^final. At step t, si,ts_i,t is the observable representation used for grouping, ci,tc_i,t is the policy’s interaction context, and ai,t=(yi,t,1,…,yi,t,Li,t)a_i,t=(y_i,t,1,…,y_i,t,L_i,t) is the executed token sequence. The latent environment state need not be observable. Appendix A gives the full setting and background. Following hindsight learning (Andrychowicz et al., 2017; Harutyunyan et al., 2019), we construct a retrospective context after termination, using the observed outcome for both successful and unsuccessful trajectories: ci,tH=Relabel(ci,t,sifinal).c^H_i,t=Relabel (c_i,t,s^final_i ). (1) The outcome information is the final observation sifinals_i^final, used as the hindsight target. The operator RelabelRelabel constructs this prompt using the templates in Appendix D.3, retaining the current observation and available interaction history. We then evaluate the same executed action ai,ta_i,t under both ci,tc_i,t and ci,tHc^H_i,t, using the frozen behavior policy πθold _ _old and teacher forcing. No new action is sampled. Holding the executed action fixed measures the score change between the two contexts. The terminal outcome is used only for training-time credit estimation, never for rollout generation or evaluation. Task / PromptxxRollout 1Rollout 2Rollout 3s1s_1s2s_2s3s_3s4s_4Successa1a_1a2a_2a3a_3a4a_4s1s_1s2s_2s3s_3s4s_4Failurea1a_1a2a_2a3a_3a4a_4s1s_1s2s_2s3s_3s4s_4Successa1a_1a2a_2a3a_3a4a_4Frozen Behavior Policyoriginal + hindsight scoring ++ higherweight−- lowerweight++ higherweight Figure 1: Overview of RELACE. Multiple trajectories are sampled for the same task, with colors indicating matched or similar environment states across rollouts. After the terminal outcome is observed, the frozen behavior policy scores the same executed actions under original and retrospective contexts using teacher forcing. The resulting hindsight reweighted returns are compared across matched states to construct the step-level credit signal. Arrow widths illustrate relative retrospective weights. 3.2 Retrospective credit reweighting via likelihood ratios To estimate retrospective relevance, we compare likelihood-based scores for the same executed action under its original and retrospective contexts. For Li,t>0L_i,t>0, we use a temperature-scaled geometric mean of token probabilities to account for action length. The two scores are: pi,t=exp(1τtempLi,t∑j=1Li,tlogπθold(yi,t,j∣ci,t,yi,t,<j)),p_i,t= ( 1 _tempL_i,t _j=1^L_i,t _ _old (y_i,t,j c_i,t,y_i,t,<j ) ), (2) pi,tH=exp(1τtempLi,t∑j=1Li,tlogπθold(yi,t,j∣ci,tH,yi,t,<j)),p^H_i,t= ( 1 _tempL_i,t _j=1^L_i,t _ _old (y_i,t,j c^H_i,t,y_i,t,<j ) ), (3) where τtemp>0 _temp>0 controls score sharpness. These length-normalized scores are not normalized probabilities over variable-length actions, and this score temperature is distinct from decoding temperature. We refer to pi,tHp^H_i,t as the retrospective likelihood score of the executed action. With numerical stabilizer ϵ>0ε>0, we first compute the raw retrospective score ratio: ui,t=pi,tHpi,t+ϵ.u_i,t= p^H_i,tp_i,t+ε. (4) A ratio ui,t>1u_i,t>1 indicates a higher score under the retrospective context; its magnitude depends on the stabilizer when pi,tp_i,t is small. To account for varying magnitudes across trajectories, we normalize the ratio by its trajectory mean, u¯i=1Ti∑k=1Tiui,k u_i= 1T_i _k=1^T_iu_i,k, yielding a clipped relative relevance: ρi,t=clip(ui,tu¯i+ϵ,ρmin,ρmax), _i,t=clip ( u_i,t u_i+ε, _ , _ ), (5) where 0<ρmin≤1≤ρmax0< _ ≤ 1≤ _ . We distinguish raw ratio ui,tu_i,t from normalized, clipped weight ρi,t _i,t used in credit estimation. Writing Qi,t=γTi−tRiQ_i,t=γ^T_i-tR_i for the original discounted return, we obtain: Qi,tH=ρi,tγTi−tRi.Q^H_i,t= _i,tγ^T_i-tR_i. (6) This reweights the return target without changing the environment reward. Before clipping and ignoring ϵε, the weights have trajectory mean one; this does not in general preserve the sum of discounted return targets. In particular, if Ri=0R_i=0, every Qi,tHQ^H_i,t is zero, regardless of the hindsight scores. 3.3 State-conditioned grouping and asymmetric masking To compare an action with sampled alternatives at a decision node, RELACE groups actions originating from matched observable environment states across the rollout batch (Feng et al., 2025). For a given task x and anchor state s, the anchor state group is defined as x(s)=(i,t)∣xi=x,si,t=s,G_x(s)=\(i,t) x_i=x,\;s_i,t=s\, which contains all batch occurrences from the same observed state. State matching determines which decisions share a local baseline. Here, si,ts_i,t denotes the observable representation used for grouping, whereas ci,tc_i,t denotes the full policy context used for likelihood scoring. Matched observations need not identify the same latent state under partial observability. The matching procedure appears in Appendix C. Following HCAPO (Tan et al., 2026), we use adjacent-step smoothing to share the weighted return signal with the preceding action: Q~i,tH=αQi,tH+(1−α)Qi,min(t+1,Ti)H,α∈[0,1]. Q^H_i,t=α Q^H_i,t+(1-α)Q^H_i, (t+1,T_i), α∈[0,1]. (7) At t=Tit=T_i, this leaves the terminal target unchanged; α=1α=1 disables smoothing. Both the focal target and the local baseline use the same smoothed, weighted quantity. For a nonempty group, its mean is μV(x,s)=1|x(s)|∑(j,k)∈x(s)Q~j,kH, _V(x,s)= 1|G_x(s)| _(j,k) _x(s) Q^H_j,k, (8) and its sample standard deviation is σV(x,s)=1|x(s)|−1∑(j,k)∈x(s)(Q~j,kH−μV(x,s))2, _V(x,s)= 1|G_x(s)|-1 _(j,k) _x(s) ( Q^H_j,k- _V(x,s) )^2, (9) when |x(s)|≥2|G_x(s)|≥ 2. Singleton groups receive zero local advantage without evaluating their sample standard deviation. Constant-target groups also yield zero local advantage. For groups of size at least two, the state-relative advantage is: Ai,tH=Q~i,tH−μV(xi,si,t)σV(xi,si,t)+ϵ.A^H_i,t= Q^H_i,t- _V(x_i,s_i,t) _V(x_i,s_i,t)+ε. (10) A successful trajectory can receive a negative local advantage when its weighted target falls below its matched-group mean; finite-sample noise can also affect that comparison. Following HCAPO (Tan et al., 2026), we apply a conservative do-no-harm mask. Let di∈0,1d_i∈\0,1\ indicate trajectory success; the protected micro-advantage becomes: A^i,tH=0,di=1∧Ai,tH<0,Ai,tH,otherwise. A^H_i,t= cases0,&d_i=1 A^H_i,t<0,\\ A^H_i,t,&otherwise. cases (11) The mask removes every negative local correction on successful trajectories, whether or not caused by noise, and leaves the macro-advantage unchanged. 3.4 Macro advantage and policy objective RELACE also computes an episode-wise macro advantage AiEA^E_i within each task group to preserve preference for high-reward trajectories: AiE=Ri−μR(xi)σR(xi)+ϵ.A^E_i= R_i- _R(x_i) _R(x_i)+ε. (12) The final advantage combines the episode-level and protected local terms: Ai,tRELACE=AiE+ωA^i,tH,A^RELACE_i,t=A^E_i+ω A^H_i,t, (13) where ω≥0ω≥ 0 balances global and local preferences. Credit estimates are computed with the frozen behavior policy and detached during policy optimization. The scalar Ai,tRELACEA^RELACE_i,t is broadcast to all valid tokens of action ai,ta_i,t. Let ri,t,j(θ)=πθ(yi,t,j∣ci,t,yi,t,<j)/πθold(yi,t,j∣ci,t,yi,t,<j)r_i,t,j(θ)= _θ(y_i,t,j c_i,t,y_i,t,<j)/ _ _old(y_i,t,j c_i,t,y_i,t,<j) be the policy-update ratio, evaluated under the original context. This token-level ratio is distinct from the retrospective score ratio ui,tu_i,t. The policy is updated using the clipped PPO surrogate objective (Schulman et al., 2017): RELACE(θ)=[min( _RELACE(θ)=E [ ( ri,t,j(θ)Ai,tRELACE, r_i,t,j(θ)A^RELACE_i,t, clip(ri,t,j(θ),1−ϵppo,1+ϵppo)Ai,tRELACE)], (r_i,t,j(θ),1- _ppo,1+ _ppo)A^RELACE_i,t ) ], (14) Here, the expectation uses the task, trajectory, and valid-token aggregation specified in Eq. (16), replacing AiEA_i^E with Ai,tRELACEA^RELACE_i,t. We retain the KL regularization against the reference policy from that objective. The hindsight context is used for credit estimation, not as the policy-update input. Algorithm 1 in Appendix B gives the training procedure. 4 Experiments and analysis 4.1 Experimental setup Benchmarks and metrics. We evaluate RELACE on two multi-turn environments with sparse outcome feedback: ALFWorld (Shridhar et al., 2021) and WebShop (Yao et al., 2022). ALFWorld requires household planning across six task categories: Pick, Clean, Heat, Cool, Examine, and Pick 2. We report overall and category-specific success rates. WebShop requires product search, attribute inspection, and purchases satisfying natural-language requests. We report mean task score (0–100) and success rate (SR), measuring complete task satisfaction. These distinguish partial from full completion. Episodes are capped at 5050 environment steps in ALFWorld and 1515 in WebShop. Models and comparisons. We initialize policies from Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct (Qwen Team, 2024). The comparison includes prompting-based agents, ReAct and Reflexion (Yao et al., 2023; Shinn et al., 2023); actor–critic training with PPO (Schulman et al., 2017); and critic-free methods, RLOO, GRPO, GiGPO, HCAPO, and GraphGPO (Ahmadian et al., 2024; Shao et al., 2024; Feng et al., 2025; Tan et al., 2026; Cheng et al., 2026). Table 1 combines our RELACE results with published baseline configurations: GRPO, GiGPO, and GraphGPO follow Cheng et al. (2026), while HCAPO follows Tan et al. (2026). We separately compare RELACE and GiGPO validation histories at shared checkpoints. Thus, the benchmark table and learning curves characterize task performance and training dynamics. Training and reporting. Our implementation extends the verl-agent framework (Feng et al., 2025).11 1 https://github.com/langfengq/verl-agent For the 1.5B experiments, each training batch contains 1616 prompts with K=8K=8 rollouts per prompt. The actor learning rate is 10−610^-6, and the KL regularization coefficient is 0.010.01. RELACE uses the retrospective weighting, temporal smoothing, and asymmetric masking defined in Section 3, without an auxiliary value or reward model. Validation is logged every five training steps; Figure 2 covers steps 00–200200. Hyperparameters, seed coverage, and aggregation details appear in Appendix C; agent and hindsight prompts appear in Appendix D. 4.2 Main results RELACE achieves the highest reported mean on all three reported aggregate metrics in Table 1—ALFWorld overall success, WebShop score and success rate—at both model sizes. The improvements extend beyond trajectory-level GRPO to the listed step-level and hindsight-based baselines, showing that retrospective likelihood correction can complement structured local comparisons. Strong performance with a 1.5B policy. On ALFWorld, RELACE reaches 96.35%96.35\% overall success, exceeding GRPO, GiGPO, HCAPO, and GraphGPO by 18.4918.49, 5.475.47, 9.359.35, and 3.643.64 percentage points, respectively. The subtask breakdown shows a large Cool gain: 96.49%96.49\% versus 85.26%85.26\% for GraphGPO and 81.46%81.46\% for GiGPO. RELACE also reaches 100%100\% on Pick and the highest Examine success among the listed 1.5B methods. The overall advantage includes gains on tasks requiring coordinated actions, while Clean, Heat, and Pick 2 remain strengths of other methods. On WebShop, the policy achieves a score of 90.9090.90 and a success rate of 79.43%79.43\%. The success-rate gains over GRPO, GiGPO, and HCAPO are 8.088.08, 5.605.60, and 10.9310.93 percentage points. Relative to GraphGPO, RELACE improves score by 1.611.61 points and success by 0.780.78 percentage points. Both gains indicate higher task rewards alongside more completed shopping tasks. Benefits persist at 7B scale. With Qwen2.5-7B-Instruct, RELACE reaches 97.66%97.66\% ALFWorld success, improving over GiGPO and GraphGPO by 3.393.39 and 2.352.35 percentage points. It achieves 100%100\% on Pick, Clean, and Pick 2, and the highest Cool and Examine means among these methods. On WebShop, RELACE obtains a score of 90.3490.34 and 82.29%82.29\% success, exceeding GiGPO by 3.623.62 score points and 3.913.91 success percentage points, and GraphGPO by 3.403.40 and 1.981.98, respectively. These results support the combination of original-context likelihood correction and state-conditioned return comparison across both policy sizes. Table 1: Benchmark performance of RELACE and the listed baseline configurations. WebShop Score is the mean task success rate (SR) on a 0–100 scale and all ALFWorld entries are success percentages. Baseline values follow Cheng et al. (2026) and Tan et al. (2026); Boldface and underlining indicate the highest and second-highest means within each model-size block, respectively. Method WebShop ALFWorld Score SR Pick Clean Heat Cool Examine Pick 2 Avg Closed-Source Models GPT-5.6-Sol-High 28.028.0 25.325.3 98.798.7 76.676.6 85.7¯ 85.7 83.683.6 89.889.8 80.280.2 86.086.0 GPT-5.6-Sol-Medium 26.726.7 22.322.3 95.4¯ 95.4 64.3¯ 64.3 87.687.6 79.8¯ 79.8 88.2¯ 88.2 73.1¯ 73.1 80.8¯ 80.8 GPT-4o 31.831.8 23.723.7 75.375.3 60.260.2 21.621.6 31.231.2 56.756.7 49.849.8 48.048.0 Gemini-2.5-Pro 42.542.5 35.935.9 92.892.8 63.263.2 26.626.6 62.162.1 69.069.0 58.758.7 60.360.3 Prompting (Qwen2.5-1.5B-Instruct) ReAct 40.1 11.3 17.4 20.5 7.7 15.7 6.2 2.0 12.8 Reflexion 55.8 21.9 35.3 22.2 19.4 21.7 13.6 3.7 21.8 RL Training (Qwen2.5-1.5B-Instruct) PPO 73.8±3.073.8± 3.0 51.5±2.951.5± 2.9 64.8±3.564.8± 3.5 40.5±6.940.5± 6.9 46.4±4.046.4± 4.0 57.1±4.957.1± 4.9 60.6±6.660.6± 6.6 47.4±1.947.4± 1.9 54.4±3.154.4± 3.1 RLOO 73.9±5.673.9± 5.6 52.1±6.752.1± 6.7 88.3±3.088.3± 3.0 52.8±8.652.8± 8.6 66.4±5.566.4± 5.5 71.0±5.971.0± 5.9 62.8±8.762.8± 8.7 56.9±4.756.9± 4.7 69.7±2.569.7± 2.5 GRPO 84.73±0.4984.73± 0.49 71.35±2.0571.35± 2.05 82.89±3.6282.89± 3.62 82.14±6.3782.14± 6.37 77.78±4.5477.78± 4.54 73.86±6.8473.86± 6.84 78.57±0.0078.57± 0.00 71.43±3.8971.43± 3.89 77.86±1.3377.86± 1.33 HCAPO 83.8±0.783.8± 0.7 68.5±1.068.5± 1.0 88.6±7.088.6± 7.0 97.6±1.897.6± 1.8 90.7±6.990.7± 6.9 84.2±0.084.2± 0.0 75.0±0.075.0± 0.0 74.2±6.974.2± 6.9 87.0±4.187.0± 4.1 GiGPO 87.94±0.4387.94± 0.43 73.83±2.3073.83± 2.30 98.81±1.68¯ 98.81± 1.68 95.16±3.8995.16± 3.89 94.44±0.0094.44± 0.00 81.46±0.5681.46± 0.56 78.57±0.0078.57± 0.00 93.65±5.9493.65± 5.94 90.88±0.9790.88± 0.97 GraphGPO 89.29±1.48¯ 89.29± 1.48 78.65±3.86¯ 78.65± 3.86 95.15±1.6295.15± 1.62 100.0±0.00100.0± 0.00 96.30±2.6196.30± 2.61 85.26±2.58¯ 85.26± 2.58 85.71±5.83¯ 85.71± 5.83 93.65±2.2493.65± 2.24 92.71±1.32¯ 92.71± 1.32 RELACE 90.90±1.0490.90± 1.04 79.43±2.7479.43± 2.74 100.00±0.00100.00± 0.00 98.41±2.75¯ 98.41± 2.75 94.45±9.61¯ 94.45± 9.61 96.49±6.0896.49± 6.08 87.46±11.3887.46± 11.38 93.33±3.12¯ 93.33± 3.12 96.35±0.4596.35± 0.45 RL Training (Qwen2.5-7B-Instruct) GRPO 84.31±1.2784.31± 1.27 75.00±2.7875.00± 2.78 88.98±5.3088.98± 5.30 91.98±4.4391.98± 4.43 90.74±5.2490.74± 5.24 77.89±4.5877.89± 4.58 78.57±0.0078.57± 0.00 71.43±3.8971.43± 3.89 83.33±2.0583.33± 2.05 HCAPO 85.1±1.385.1± 1.3 73.8±2.873.8± 2.8 99.10±1.30¯ 99.10± 1.30 97.30±1.90¯ 97.30± 1.90 81.80±8.8081.80± 8.80 90.80±6.6090.80± 6.60 90.30±2.0090.30± 2.00 81.90±10.0081.90± 10.00 91.40±2.3091.40± 2.30 GiGPO 86.72±1.4486.72± 1.44 78.38±1.9478.38± 1.94 97.53±1.7597.53± 1.75 100.0±0.00100.0± 0.00 94.44±0.0094.44± 0.00 83.98±1.3283.98± 1.32 90.48±6.7390.48± 6.73 100.0±0.00100.0± 0.00 94.27±1.3394.27± 1.33 GraphGPO 86.94±0.68¯ 86.94± 0.68 80.31±1.33¯ 80.31± 1.33 100.0±0.0100.0± 0.0 100.0±0.0100.0± 0.0 94.44±0.094.44± 0.0 91.40±1.5¯ 91.40± 1.5 92.86±5.8¯ 92.86± 5.8 92.06±2.2¯ 92.06± 2.2 95.31±1.10¯ 95.31± 1.10 RELACE 90.34±0.8090.34± 0.80 82.29±1.8082.29± 1.80 100.00±0.00100.00± 0.00 100.00±0.00100.00± 0.00 94.11±5.37¯ 94.11± 5.37 94.71±5.0394.71± 5.03 94.44±9.6294.44± 9.62 100.00±0.00100.00± 0.00 97.66±0.7897.66± 0.78 4.3 Learning dynamics Figure 2 compares validation success over the first 200200 logged training steps. The curves compare RELACE’s learning progress with GiGPO, complementing the benchmark results in Table 1. (a) ALFWorld Success Rate (b) WebShop Success Rate Figure 2: Validation success over steps 00–200200 for RELACE (solid) and GiGPO (dashed), using Qwen2.5-1.5B/7B-Instruct. Lines show seed means; shading shows one sample standard deviation, omitted for single-seed baselines. Seed coverage and the † run-assignment note appear in Appendix C. The 1.5B curves separate most during early and intermediate training. On ALFWorld at step 5050, RELACE reaches 51.56%51.56\% success versus 40.63%40.63\% for GiGPO, a 10.9410.94-point advantage. On WebShop, the gap is larger: 39.06%39.06\% versus 23.70%23.70\%, or 15.3615.36 points. The WebShop advantage remains 12.7612.76 points at step 100100 (60.94%60.94\% versus 48.18%48.18\%). The curves show faster early learning and higher success for RELACE. RELACE’s computational overhead appears in Appendix C. 4.4 Ablation study We examine two retrospective-estimator choices: correcting hindsight scores using the original action likelihood, and applying the resulting weights to the local comparison group. Table 2 reports four WebShop variants. Using Qi,t=γTi−tRiQ_i,t=γ^T_i-tR_i, GiGPO compares unweighted returns Q. Hindsight-score weighting uses pHQp^HQ for both the focal action and its group baseline, without the original-context denominator. Focal-only ratio weighting uses ρQρ Q for the focal action but retains a baseline constructed from Q. Full RELACE uses ρQρ Q on both sides, with the smoothing and normalization defined in Section 3.3. Table 2: Component comparison on WebShop. Columns show the focal target and group-baseline input before smoothing. Variant Focal target Baseline input Reported SR (%) GiGPO Q Q 73.8373.83 Hindsight-score weighting pHQp^HQ pHQp^HQ 75.7875.78 Focal-only ratio weighting ρQρ Q Q 60.94∗60.94 RELACE ρQρ Q ρQρ Q 79.4379.43 Original-context correction. Hindsight-score weighting reaches 75.78%75.78\%, compared with 73.83%73.83\% for GiGPO. Full RELACE reaches 79.43%79.43\%, a further 3.653.65-point increase. This ordering supports comparing an action’s hindsight and original plausibility: a high hindsight score may reflect an already probable action. Consistency of the local baseline. The focal-only variant peaks at 60.94%60.94\%, indicating that focal-return weighting alone is insufficient here. An unweighted baseline compares differently transformed quantities. In RELACE, both focal targets and group statistics use the same hindsight-weighted, smoothed returns. The ordering supports this design motivation. 4.5 Dynamics of retrospective scoring Complementing validation, we examine 200200 training steps of Qwen2.5-1.5B-Instruct on WebShop. Figure 3 tracks three run diagnostics: mean retrospective weight, mean hindsight score, and action score. These curves characterize scoring during training. Stability of the mean retrospective weight. The logged mean weight stays near one, ranging from 0.99660.9966 to 1.00111.0011. Its temporal standard deviation falls from 6.84×10−46.84× 10^-4 over steps 11–5050 to 1.58×10−41.58× 10^-4 over steps 151151–200200, a reduction of about 77%77\%. This indicates greater late-stage stability of the batch mean. Increasing hindsight scores. The mean hindsight score rises from 0.2410.241 over steps 11–1010 to 0.7850.785 over steps 191191–200200. Successive 5050-step averages are 0.2790.279, 0.4340.434, 0.5630.563, and 0.6870.687, showing an upward trend despite batch fluctuations. Thus, later actions score higher in outcome-conditioned contexts, consistent with greater compatibility with the final-observation hindsight targets. Non-monotonic action-score evolution. The action score follows a different trajectory. Its 5050-step average decreases from 0.9210.921 over steps 11–5050 to 0.8980.898 over steps 5151–100100, then recovers to 0.9110.911 and 0.9240.924 in the next two windows. Hindsight scores rise while action scores decline and recover, rather than both increasing uniformly. These patterns suggest changing action preferences during training. Figure 3: RELACE scoring dynamics on WebShop (Qwen2.5-1.5B-Instruct, steps 11–200200): (a) hindsight weight, with a dashed reference at one; (b) hindsight action score; and (c) action score. 5 Conclusion Sparse terminal rewards provide limited credit-assignment guidance in long-horizon tasks. We introduced RELACE, a critic-free framework that uses teacher forcing to compare executed actions under original and outcome-conditioned contexts. The relevance weights refine discounted returns before state-conditioned comparison, combining local credit with GRPO supervision without auxiliary models or additional autoregressive rollouts. Experiments on ALFWorld and WebShop show higher reported aggregate performance than compared baselines at 1.5B and 7B scales, with early gains over GiGPO at 1.5B. Training diagnostics show increasing hindsight scores and a more stable mean retrospective weight, supporting learning from sparse outcomes. These scores represent retrospective relevance rather than causal contribution. Future work will examine their relationship to action utility, improve partially observable state matching, and evaluate generalization across environments. AI use statement Generative AI tools assisted with sentence-level editing, literature lookup and citation formatting. Also assisted in implementing code experimentation, and LaTeX compilation checks. The authors remain responsible for the final text, analyses, and claims. References Ahmadian et al. (2024) Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting REINFORCE-style optimization for learning from human feedback in LLMs. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2024. URL https://arxiv.org/abs/2402.14740. Andrychowicz et al. (2017) Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, volume 30, p. 5048–5058, 2017. URL https://proceedings.neurips.c/paper/2017/hash/453fadbd8a1a3af50a9df4df899537b5-Abstract.html. Cheng et al. (2026) Xin Cheng, Shuo He, Lang Feng, HaiYang Xu, Ming Yan, Lei Feng, and Bo An. Beyond trajectory-level attribution: Graph-based credit assignment for agentic reinforcement learning. arXiv preprint arXiv:2605.26684, 2026. URL https://arxiv.org/abs/2605.26684. Feng et al. (2025) Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. Group-in-group policy optimization for LLM agent training. In Advances in Neural Information Processing Systems, volume 38, 2025. doi: 10.52202/085713-1544. URL https://arxiv.org/abs/2505.10978. Harutyunyan et al. (2019) Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nicolas Heess, Hado P. van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup, and Remi Munos. Hindsight credit assignment. In Advances in Neural Information Processing Systems, volume 32, p. 12467–12476, 2019. URL https://proceedings.neurips.c/paper_files/paper/2019/hash/195f15384c2a79cedf293e4a847ce85c-Abstract.html. He et al. (2026) Shuo He, Lang Feng, Qi Wei, Xin Cheng, Lei Feng, and Bo An. Hierarchy-of-groups policy optimization for long-horizon agentic tasks. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/2602.22817. Li et al. (2026) Yuanfan Li, Qi Zhou, Wenjing Duan, and Lu Chen. When denser credit is not enough: Evidence-calibrated policy optimization for long-horizon llm agent training. arXiv preprint arXiv:2606.05885, 2026. doi: 10.48550/arXiv.2606.05885. URL https://arxiv.org/abs/2606.05885. Lightman et al. (2023) Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023. URL https://arxiv.org/abs/2305.20050. Meulemans et al. (2023) Alexander Meulemans, Simon Schug, Seijin Kobayashi, Nathaniel Daw, and Gregory Wayne. Would i have gotten that reward? long-term credit assignment by counterfactual contribution analysis. In Advances in Neural Information Processing Systems, 2023. URL https://papers.neurips.c/paper_files/paper/2023/hash/d8bd445c2abe1343cce0e14b361b2fb3-Abstract-Conference.html. Qwen Team (2024) Qwen Team. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115, 2024. URL https://arxiv.org/abs/2412.15115. Rauber et al. (2019) Paulo Rauber, Avinash Ummadisingu, Filipe Mutz, and Jürgen Schmidhuber. Hindsight policy gradients. In International Conference on Learning Representations, 2019. URL https://arxiv.org/abs/1711.06006. Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. doi: 10.48550/arXiv.1707.06347. URL https://arxiv.org/abs/1707.06347. Shao et al. (2024) Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024. URL https://arxiv.org/abs/2402.03300. Shinn et al. (2023) Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems, 2023. URL https://arxiv.org/abs/2303.11366. Shridhar et al. (2021) Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. ALFWorld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations, 2021. URL https://arxiv.org/abs/2010.03768. Tan et al. (2026) Hui-Ze Tan, Xiao-Wen Yang, Hao Chen, Jie-Jing Shao, Yi Wen, Yuteng Shen, Weihong Luo, Xiku Du, Lan-Zhe Guo, and Yu-Feng Li. Hindsight credit assignment for long-horizon LLM agents. arXiv preprint arXiv:2603.08754, 2026. doi: 10.48550/arXiv.2603.08754. URL https://arxiv.org/abs/2603.08754. Wang et al. (2025a) Jiawei Wang, Jiacai Liu, Yuqian Fu, Yingru Li, Xintao Wang, Yuan Lin, Yu Yue, Lin Zhang, Yang Wang, and Ke Wang. Harnessing uncertainty: Entropy-modulated policy gradients for long-horizon LLM agents. arXiv preprint arXiv:2509.09265, 2025a. URL https://arxiv.org/abs/2509.09265. Wang (2026) Yu Wang. The dark room in the reward channel: Dense prediction rewards collapse GRPO-trained LLM agents – and the channel, not the content, decides what works. arXiv preprint arXiv:2607.21273, 2026. doi: 10.48550/arXiv.2607.21273. URL https://arxiv.org/abs/2607.21273. Wang et al. (2025b) Zihan Wang, Kangrui Wang, Qineng Wang, Pingyue Zhang, Linjie Li, Zhengyuan Yang, Xing Jin, Kefan Yu, Minh Nhat Nguyen, Licheng Liu, Eli Gottlieb, Yiping Lu, Kyunghyun Cho, Jiajun Wu, Li Fei-Fei, Lijuan Wang, Yejin Choi, and Manling Li. RAGEN: Understanding self-evolution in LLM agents via multi-turn reinforcement learning. arXiv preprint arXiv:2504.20073, 2025b. URL https://arxiv.org/abs/2504.20073. Xu et al. (2025) Wujiang Xu, Wentian Zhao, Zhenting Wang, Yu-Jhe Li, Can Jin, Mingyu Jin, Kai Mei, Kun Wan, and Dimitris N. Metaxas. EPO: Entropy-regularized policy optimization for LLM agents reinforcement learning. arXiv preprint arXiv:2509.22576, 2025. URL https://arxiv.org/abs/2509.22576. Yao et al. (2022) Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. WebShop: Towards scalable real-world web interaction with grounded language agents. In Advances in Neural Information Processing Systems, 2022. URL https://arxiv.org/abs/2207.01206. Yao et al. (2023) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations, 2023. URL https://arxiv.org/abs/2210.03629. Appendix A Preliminaries Markov decision processes. A Markov decision process (MDP) is defined by ℳ=(,,P,R,γ)M=(S,A,P,R,γ), where S is the state space, A is the action space, P(s′∣s,a)P(s s,a) is the transition kernel, R is the reward function, and γ∈[0,1]γ∈[0,1] is the discount factor. A policy π(a∣s)π(a s) selects an action conditioned on the current state, and the objective is to maximize expected discounted return. Partial observability. Long-horizon language agents generally do not have direct access to the underlying environment state. We therefore model interaction as a partially observable Markov decision process (POMDP), ℳ=(,,,P,Ω,R,γ),M=(Z,A,O,P, ,R,γ), where Z denotes latent states, O observations, and Ω(o∣z) (o z) the observation kernel. Rather than conditioning only on the current latent state, the policy acts from its available interaction history. For language agents, we represent this information by a context ctc_t, containing the task specification, previous observations and actions, and the current observation. Language-agent setting. For each task x, we sample a group of K trajectories from the behavior policy πθold _ _old. Trajectory τi=(si,1,ai,1,…,si,Ti,ai,Ti,sifinal) _i=(s_i,1,a_i,1,…,s_i,T_i,a_i,T_i,s_i^final) contains TiT_i actions, terminates in observed outcome sifinals_i^final, and receives terminal reward Ri=R(τi)R_i=R( _i). At turn t, the context ci,tc_i,t contains the task and observed interaction history, while the action ai,ta_i,t is a variable-length token sequence ai,t=(yi,t,1,…,yi,t,Li,t).a_i,t=(y_i,t,1,…,y_i,t,L_i,t). We use si,ts_i,t to denote the observable environment representation used for state-conditioned grouping. Under partial observability, identical observed states need not correspond to identical latent environment states. Group Relative Policy Optimization. GRPO (Shao et al., 2024) avoids training a separate value critic by constructing relative advantages from groups of rollouts sampled for the same task. For trajectory τi _i, the episode-level advantage is AiE=Ri−μR(x)σR(x)+ϵ,ri,t,j(θ)=πθ(yi,t,j∣ci,t,yi,t,<j)πθold(yi,t,j∣ci,t,yi,t,<j),A_i^E= R_i- _R(x) _R(x)+ε, r_i,t,j(θ)= _θ(y_i,t,j c_i,t,y_i,t,<j) _ _old(y_i,t,j c_i,t,y_i,t,<j), (15) where μR(x) _R(x) and σR(x) _R(x) are reward statistics computed over the rollout group for task x, and ϵ>0ε>0 ensures numerical stability. GRPO optimizes the clipped surrogate objective GRPO(θ) _GRPO(θ) =[1K∑i=1K1Ni∑t,jℓ(ri,t,j(θ),AiE)−βDi,t,j], =E\! [ 1K _i=1^K 1N_i _t,j \ \! (r_i,t,j(θ),A_i^E )-β D_i,t,j \ ], (16) ℓ(r,A) (r,A) =minrA,clip(r,1−ϵppo,1+ϵppo)A, = \! \rA,\,clip(r,1- _ppo,1+ _ppo)A \, where Ni=∑tLi,tN_i= _tL_i,t and Di,t,jD_i,t,j denotes the token-level KL penalty relative to a reference policy. The expectation is over tasks and rollout groups, while β and ϵppo _ppo control KL regularization and PPO clipping, respectively. When only a terminal reward is available, AiEA_i^E is shared by every action in trajectory τi _i. GRPO therefore distinguishes trajectories by overall outcome but does not by itself distinguish the contributions of individual intermediate actions. Hindsight credit assignment. Hindsight Credit Assignment (HCA) (Harutyunyan et al., 2019) uses future outcomes to retrospectively assess earlier actions. For a Markov state s, define the hindsight action posterior hkπ(a∣s,s′)=Prπ(A0=a∣S0=s,Sk=s′).h_k^π(a s,s )= _π(A_0=a S_0=s,S_k=s ). For π(a∣s)>0π(a s)>0, HCA gives the action-value identity Qπ(s,a)=r(s,a)+τ∼π(⋅∣s)[∑k≥1γkhkπ(a∣s,Sk)π(a∣s)rk],Q^π(s,a)=r(s,a)+E_τ π(· s)\! [ _k≥ 1γ^k h_k^π(a s,S_k)π(a s)r_k ], (17) where r(s,a)r(s,a) is the expected immediate reward and rkr_k is a future reward. The expectation is over trajectories beginning from s with A0∼π(⋅∣s)A_0 π(· s), rather than trajectories conditioned on A0=aA_0=a. For sparse terminal rewards, HCAPO (Tan et al., 2026) motivates the step-level quantity Qi,tH=hπ(ai,t∣ci,t,sifinal)π(ai,t∣ci,t)γTi−tRi,Q^H_i,t= h^π(a_i,t c_i,t,s_i^final)π(a_i,t c_i,t)γ^T_i-tR_i, (18) with π=πθoldπ= _ _old and the hindsight distribution conditioned on the observed terminal outcome. In practical language-agent implementations, the exact hindsight posterior is unavailable and must be approximated using policy likelihoods under outcome-conditioned contexts. The likelihood-based scores used by RELACE are therefore practical credit proxies rather than exact HCA posteriors; the HCA identity above does not imply that the resulting estimator is unbiased. Appendix B Full RELACE algorithm Algorithm 1 summarizes the complete RELACE training procedure. The algorithm first samples grouped trajectories using the frozen behavior policy, retrospectively scores each executed action under its original and outcome-conditioned contexts, constructs trajectory-normalized likelihood-ratio weights, and uses these weights to form state-conditioned local advantages. These local advantages are then combined with the trajectory-level GRPO advantage for policy optimization. Algorithm 1 Retrospective Likelihood-based Action Credit Estimation (RELACE) 1: Policy πθold _ _old, task batch X, group size K, discount γ, micro-advantage weight ω, smoothing coefficient α, ratio bounds ρmin,ρmax _ , _ , and numerical constant ϵε 2: for each task x∈x do 3: Sample K trajectories τii=1K∼πθold\ _i\_i=1^K _ _old 4: Record states, actions, final states, returns, and success labels 5: for each trajectory τi _i do 6: for t=1,…,Tit=1,…,T_i do 7: Construct outcome-conditioned context ci,tH←Relabel(ci,t,sifinal)c^H_i,t (c_i,t,s^final_i) 8: Teacher-force ai,ta_i,t under ci,tc_i,t and ci,tHc^H_i,t 9: Compute pi,tp_i,t and pi,tHp^H_i,t using Eqs. (2)–(3) 10: ui,t←pi,tH/(pi,t+ϵ)u_i,t← p^H_i,t/(p_i,t+ε) 11: end for 12: u¯i←Ti−1∑t=1Tiui,t u_i← T_i^-1 _t=1^T_iu_i,t 13: for t=1,…,Tit=1,…,T_i do 14: ρi,t←clip(ui,t/(u¯i+ϵ),ρmin,ρmax) _i,t (u_i,t/( u_i+ε), _ , _ ) 15: Qi,tH←ρi,tγTi−tRiQ^H_i,t← _i,tγ^T_i-tR_i 16: end for 17: Optionally smooth Qi,tHQ^H_i,t using Eq. (7) 18: end for 19: Group valid states within each task using the state-matching rule in Section 3.3 20: Compute μV(x,s) _V(x,s) and σV(x,s) _V(x,s) 21: Compute state-relative retrospective likelihood-based advantages Ai,tHA^H_i,t 22: Apply the do-no-harm mask to obtain A^i,tH A^H_i,t 23: Compute episode-wise advantages AiEA^E_i 24: Combine advantages: Ai,tRELACE←AiE+ωA^i,tHA^RELACE_i,t← A^E_i+ω A^H_i,t 25: end for 26: Update θ by maximizing RELACE(θ)J_RELACE(θ) Appendix C Experimental details and hyperparameters C.1 Training configuration. For the 1.5B experiments, we use a training batch size of 1616 with K=8K=8 environment rollouts per prompt. The actor learning rate is 10−610^-6 and the KL regularization coefficient is 0.010.01. KL shaping of the environment reward is disabled. Rollouts are generated using vLLM with sampling temperature 1.01.0, while validation uses temperature 0.40.4 and a validation batch size of 128128. We evaluate the policy every five training steps. Episodes are limited to 5050 environment steps in ALFWorld and 1515 steps in WebShop. For RELACE, we set the temporal smoothing coefficient to α=0.5α=0.5, the micro-advantage weight to ω=1ω=1, and clip the normalized retrospective likelihood ratio to [ρmin,ρmax]=[0.8,1.2][ _ , _ ]=[0.8,1.2]. The likelihood-score temperature is 11. Temporal smoothing and the success-protecting mask are enabled. The discount factor is γ=0.6γ=0.6 for RELACE and γ=0.95γ=0.95 for the GiGPO baseline Feng et al. (2025). The PPO mini-batch size is 6464 for all experiments except for for WebShop 7B, where the mini-batch size is 128128. State matching. The exact normalized equality in Section 3.3 defines idealized anchor groups. In practice, we construct state-conditioned groups within each task using string-similarity matching with threshold 0.950.95. Exact matching can produce sparse groups when observable representations differ textually, while approximate matching risks grouping distinct decision situations. C.2 computational overhead analysis Following the stage-wise analysis of HCAPO (Tan et al., 2026, Section 6.5), we profile RELACE on WebShop with Qwen2.5-1.5B-Instruct on one node with eight NVIDIA H100 80GB GPUs. The run uses 1616 prompts and 88 rollouts per prompt, an actor PPO mini-batch size of 6464, and a maximum of 1515 environment steps. We average the first 200200 timed training iterations (logged steps 11–200200), retaining initial iterations. This dedicated timing run is separate from the validation histories in Figure 2. Cost of retrospective scoring. Figure 4 shows that generation remains the dominant stage at 49.1649.16 s per iteration, followed by actor updates at 9.039.03 s. Hindsight scoring averages 6.856.85 s, accounting for 7.97%7.97\% of the full logged iteration time of 86.0186.01 s. Restricting the denominator to the five major stages—generation, actor update, hindsight scoring, old-policy scoring, and reference scoring—gives 68.9068.90 s and a hindsight share of 9.94%9.94\%. The remaining 17.1117.11 s comprises other logged work, including advantage and reward processing, periodic evaluation, and checkpoint saving. Figure 4: Mean training latency on WebShop over logged steps 11–200200 of one timing run. Labels show seconds per iteration and the share of full logged iteration time. Hindsight scoring (orange) averages 6.856.85 s, or 7.97%7.97\% of the full iteration. “Other logged time” includes periodic evaluation, checkpointing, and residual work. The relatively small scoring share is consistent with the computation used by RELACE: teacher forcing evaluates tokens from existing trajectories without additional autoregressive action generation or environment interaction. In this profile, the hindsight pass takes approximately 14%14\% of the generation time, making retrospective scoring a modest component of the measured training pipeline. These measurements quantify the recorded scoring stage; incremental end-to-end slowdown relative to GiGPO would require a matched run with hindsight scoring disabled. Timing aggregation details are provided in Appendix C. Appendix D Prompt templates For completeness and reproducibility, we provide the prompt templates used for policy interaction in ALFWorld and WebShop, together with the outcome-conditioned prompt used for retrospective likelihood evaluation. Variables enclosed in braces are instantiated from the current environment state and interaction history. D.1 ALFWorld agent prompt Prompt Template for ALFWorld You are an expert autonomous agent operating in the ALFRED Embodied Environment. Your task is to: task_description. Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history You are now at step current_step and your current observation is: current_observation. Your admissible actions of the current situation are: available_actions Now it’s your turn to take one action for the current step. You should first reason step-by-step about the current situation, then think carefully which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within <think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for the current step and present it within <action> </action> tags. D.2 WebShop agent prompt Prompt Template for WebShop You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to: task_description. Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history You are now at step current_step and your current observation is: current_observation. Your admissible actions of the current situation are: available_actions Now it’s your turn to take one action for the current step. You should first reason step-by-step about the current situation, then think carefully which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within <think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for the current step and present it within <action> </action> tags. D.3 Outcome-conditioned hindsight prompt RELACE performs retrospective scoring after the trajectory terminates. For each executed action ai,ta_i,t, we retain the original decision context ci,tc_i,t and augment it with the observed terminal outcome sifinals^final_i. The executed action itself is not regenerated; instead, it is scored using teacher forcing under both contexts. Hindsight Prompt Template for ALFWorld You are an expert agent operating in the ALFRED Embodied Environment. Your task is to: Navigate the environment to reach the following exact observation: [Observation]: final_obs Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history You are now at step current_step and your current observation is: current_observation Your admissible actions of the current situation are: [admissible_actions]. Now it’s your turn to take an action. You should first reason step-by-step about the current situation. This reasoning process MUST be enclosed within <think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for current step and present it within <action> </action> tags. Hindsight Prompt Template for WebShop You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to: Navigate the website to reach the following exact target page state: [Target Page]: final_obs Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history You are now at step current_step and your current observation is: current_observation. Your admissible actions of the current situation are: available_actions Now it’s your turn to take one action for the current step. You should first reason step-by-step about the current situation, then think carefully which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within <think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for the current step and present it within <action> </action> tags. The previously executed action ai,t=(yi,t,1,…,yi,t,Li,t)a_i,t=(y_i,t,1,…,y_i,t,L_i,t) is then teacher-forced under this hindsight context to compute pi,tHp^H_i,t. The same action is teacher-forced under the original context to compute pi,tp_i,t. Appendix E Qualitative case studies We provide qualitative examples illustrating how RELACE assigns action-dependent retrospective credit. In each example, we report the original-context score pi,tp_i,t, outcome-conditioned score pi,tHp^H_i,t, and the resulting trajectory-normalized relevance weight ρi,t _i,t. These examples are intended to illustrate the behavior of the estimator, rather than establish causal attribution. E.1 ALFWorld case study We visualize a successful ALFWorld trajectory to illustrate the multi-turn decision process in embodied environments. The agent receives only a terminal success signal, while intermediate actions must be assigned credit based on their contribution to completing the task. ALFWorld Rollout: Step 1 Task: cool some potato and put it in diningtable Observation: The agent is in the middle of a room. Available objects include a diningtable, fridge, cabinets, drawers, microwave, sinkbasin, and other kitchen objects. Action: go to diningtable 1 ALFWorld Rollout: Step 2 Observation: The agent arrives at the dining table. Objects on the table include: apple 3, bread 1, butterknife 3, egg 2, fork 1, knife 1, knife 2, mug 1, plate 1, potato 4, potato 2, tomato 3 Action: take potato 2 from diningtable 1 ALFWorld Rollout: Step 3 Observation: The agent is holding: potato 2 Available actions include moving to the fridge. Action: go to fridge 1 ALFWorld Rollout: Step 4 Observation: The agent arrives at the fridge. The fridge 1 is closed. Action: cool potato 2 with fridge 1 ALFWorld Rollout: Step 5 Observation: The agent successfully cools the potato: You cool the potato 2 using the fridge 1. Action: go to diningtable 1 ALFWorld Rollout: Step 6 Observation: The agent returns to the dining table with the cooled potato. Action: move potato 2 to diningtable 1 Outcome: success E.2 WebShop case study We show a successful WebShop trajectory to illustrate the multi-turn interaction structure used by our agent. The trajectory receives a single terminal success reward, while RELACE assigns credit at the action level. WebShop Rollout: Step 1 Task: Find me machine wash men’s tuxedo shirts with polyester heathers, heathers cotton, cotton heather, needle sleeve, classic fit with color: heather grey, fit type: youth, size: medium, and price lower than 30.00 dollars. Observation: Search Action: search[machine wash men’s tuxedo shirts | polyester heathers | heathers cotton | cotton heather | needle sleeve | classic fit | color: heather grey | fit type: youth | size: medium | price < 30.00] WebShop Rollout: Step 2 Observation: Page 1 (Total results: 50) B07JVVDJ6L -- Canadian Tuxedo T Shirt - Novelty Denim Tux-T-Shirt $19.99 Action: click[B07JVVDJ6L] WebShop Rollout: Step 3 Observation: Product page: fit type: men, women, youth color: royal blue, baby blue, heather grey, heather blue small, medium, large, x-large, x-large, 3x-large, 2t, 3t, 4t, x-small Action: click[youth] WebShop Rollout: Step 4 Observation: Product page after selecting fit type: fit type: youth Available colors: royal blue, baby blue, heather grey, heather blue Action: click[heather grey] WebShop Rollout: Step 5 Observation: Product page after selecting color: color: heather grey Available sizes: small, medium, large, x-large, x-large Action: click[medium] WebShop Rollout: Step 6 Observation: Final product configuration: Product: Canadian Tuxedo T Shirt - Novelty Denim Tux-T-Shirt color: heather grey fit type: youth size: medium price: $19.99 Action: click[buy now] Outcome: Successful purchase