acceptodds
Under review as a conference paper at ICLR 2027

Same Observation, Different Futures: Credit Assignment via Dynamics Modeling

Abstract

LLM agents are moving from single-turn answers toward long-horizon workflows spanning dozens of decisions and tool calls. As the interaction horizon grows, a sparse terminal reward must be attributed across increasingly many decisions, progressively weakening the supervision available for each individual decision. Credit assignment therefore becomes a key bottleneck in agentic RL. A common approach is to estimate intermediate history values and use them to construct step-level advantages. Existing methods group histories using heuristic local matching and estimate values from within-group Monte Carlo (MC) returns. This can introduce bias by grouping histories with different continuation dynamics and increase variance by ignoring trajectories outside the group. In this work, we propose Credit Assignment via global DYnamics (CADY), a structured credit assignment method that models global trajectory dynamics. CADY maps histories with similar continuation dynamics to similar posterior distributions over latent states, mitigating the bias induced by heuristic grouping. It further exploits the global coupling among latent states for structured value estimation. This allows information from all rollouts to be more effectively leveraged through the shared transition dynamics. We further provide a theoretical analysis explaining why global dynamics-based value estimation can achieve lower first-order asymptotic variance than a simple MC estimator. Experiments on three challenging long-horizon agentic benchmarks show that CADY produces more accurate history-value estimates and substantially higher task success rates. Even in a tool-use environment with roughly 500 API operations, CADY can still separate locally indistinguishable histories with divergent continuations, demonstrating its scaling potential.

Primary area:
reinforcement learning
Keywords:
Long-Horizon Agentic Reinforcement Learning, Credit Assignment, Large Language Models, Hidden Markov Models

Reviews

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

This paper introduces CADY, a structured credit assignment method for long-horizon agentic reinforcement learning. CADY first fits a separate CHMM to the rollout trajectories of each question to learn latent states and shared transition dynamics. It then estimates the success probability of each interaction history via dynamic programming over the learned model and combines the resulting step-level advantages with GRPO-style episode-level advantages to optimize the policy. The paper also provides a theoretical analysis showing that shared-dynamics value estimation can achieve lower first-order asymptotic variance than simple Monte Carlo estimation under correct model specification and regularity assumptions. Experiments on CookingWorld, TextWorld Commonsense (TWC), and multi-hop QA demonstrate improvements in both value estimation and downstream task success rates.

Critical strengths
  • CADY moves beyond heuristic local history matching by learning latent states that capture continuation dynamics and estimating values through a shared transition model. This provides a principled mechanism for leveraging information across rollouts and potentially reducing both grouping-induced bias and value-estimation variance.

  • CADY achieves strong results across both embodied-agent tasks and multi-hop QA. For example, with Qwen2.5-1.5B-Instruct, it achieves 95.3% on CookingWorld and 75.3% on TWC, substantially outperforming the listed baselines on these benchmarks.

Critical weaknesses
  • CADY relies on a CHMM to capture global trajectory dynamics, but its effectiveness depends on the learned model accurately representing continuation behavior. The paper does not sufficiently investigate the robustness of value estimation to model misspecification or poor local optima during EM fitting.

  • The scalability evaluation on AutomationBench focuses on latent-state separation using 300 trajectories rather than end-to-end policy optimization. Consequently, the evidence for CADY's scalability to more complex agentic workflows and the computational efficiency of per-question CHMM fitting remains limited.

Questions for authors
  • How robust is CADY to imperfect trajectory modeling, particularly when the learned CHMM fails to distinguish histories with different continuation dynamics? Can the authors quantify how such representation errors affect value estimation and downstream policy optimization?

  • Can the authors provide end-to-end evaluations on larger and more complex tool-use tasks, including computational overhead and performance under varying rollout budgets, to better establish CADY's scalability and practical efficiency?

3 comments
AuthorsOpenReview ↗

Responses to Q1

We have revised the manuscript, with all textual changes highlighted in red, and added additional experimental results in Appendix C.5.

Q1: Robustness to imperfect CHMM fitting such as small rollout budget and representation errors

We thank the reviewer for raising this important concern. We acknowledge that imperfect CHMM fitting, particularly the aliasing of histories with different continuation dynamics, can degrade value estimation and downstream policy optimization. However, CADY exhibits substantial tolerance to moderate fitting errors, as supported by experiments that deliberately degrade CHMM fitting quality through two approaches: reducing the rollout budget and removing clone states.

Rollout-budget sensitivity (Figure 11). We vary the number of rollouts used for CHMM fitting from 4 to 64 and evaluate value-estimation squared error, advantage-sign consistency, and downstream Mean@8 on CookingWorld. Advantage-sign consistency measures the percentage of step-level credit signs that agree with those produced by the CHMM fitted using the largest rollout budget. Value-estimation error is measured as the squared difference between CHMM predictions and Monte Carlo estimates on 1K held-out prefixes, where each Monte Carlo estimate is obtained by averaging the rewards of 32 additional rollouts from the corresponding prefix. As the budget decreases from 64 to 16, the mean squared error increases from approximately 0.035 to 0.057, yet 92% of step-level credit signs remain consistent with the largest-budget CHMM, and Mean@8 remains essentially unchanged (95.7% vs. 95.8%). At smaller budgets, sign consistency and performance decline together: at 8 rollouts, they decrease to 67% and 73.5%, respectively, and at 4 rollouts, to 34% and 36.4%. These results demonstrate that although reducing the rollout budget increases CHMM value-estimation error, CADY's downstream performance remains robust over a substantial budget range (16–64 rollouts). The similar trends in sign consistency and test performance suggest that this robustness can be partly explained by the stability of credit signs under fitting errors.

Representation aliasing (Figures 4c and 10a). Removing clone states prevents CHMM from distinguishing histories that share the same observation but have different continuation dynamics. As expected, this degrades both value estimation (Figure 4c) and policy performance (Figure 10a). Nevertheless, CADY without clones still achieves lower value-estimation error (Figure 4c) and better downstream performance than GiGPO (Figure 10a). This indicates that even when the latent representation is limited and cannot distinguish histories with different continuation dynamics, CADY can still benefit from exploiting shared dynamics and value relationships across states, rather than relying solely on Monte Carlo estimates from rollouts grouped by identical local observations, as in GiGPO.

Together, these experiments, which vary the rollout budget and remove clone-state distinctions, demonstrate that CADY's downstream performance exhibits a degree of robustness to imperfect CHMM fitting and representation errors.

AuthorsOpenReview ↗

Responses to Q2

Q2: Scalability, effectiveness under practical rollout budgets

We thank the reviewer for highlighting the need for stronger scalability evidence. The original experiment used 300 trajectories for representation analysis. We agree that this setting alone does not establish the rollout requirements of CADY, which motivates our additional budget-sensitivity evaluation.

Value estimation on AutomationBench (Figure 12b). We evaluate CHMM across rollout budgets of 8, 16, 32, and 64. Its squared error on 1K held-out prefixes decreases from 0.28 to 0.13, compared with GiGPO's reported in-sample errors of 0.33 to 0.22, even though held-out value estimation is more challenging than in-sample estimation. These results provide encouraging evidence that CHMM can obtain useful value estimates with substantially fewer than 300 trajectories, including budgets comparable to those used in practical RL training. This further demonstrates CADY's potential to maintain efficient value estimation and its advantages over the baseline in more complex agentic environments.

End-to-end policy optimization (Figure 12a). We additionally compare CADY and GiGPO across rollout budgets of 4–64 on CookingWorld. CADY consistently and substantially outperforms GiGPO across the entire budget range, achieving 36.4 vs. 13.7 Mean@8 with only 4 rollouts, 73.5 vs. 15.2 at 8 rollouts, and 95.7 vs. 22.4 at 16 rollouts. Moreover, CADY maintains approximately 95% Mean@8 across budgets of 16–64, demonstrating that its policy-learning advantage is robust across rollout budgets and does not require a large sampling budget.

Computational overhead. As reported in the original paper, under the same rollout budget, per-question CHMM fitting incurs approximately 20% additional training wall-clock time compared with the GRPO baseline under our existing end-to-end experimental settings. Unlike critic-based methods such as TurnPPO, CADY does not require a separately trained neural critic, thereby avoiding the substantial computational overhead associated with critic training.

We acknowledge that the AutomationBench evaluation does not replace end-to-end RL training on that benchmark. Nevertheless, the additional experiments provide complementary evidence: CHMM offers useful value estimation at modest rollout budgets in complex tool-use environments, while CADY maintains strong end-to-end performance across rollout budgets in our evaluated RL environment, with moderate measured training overhead. These results support CADY's scalability and practical efficiency.

We would like to know whether our responses have addressed your concerns. Please feel free to comment if there are any further confusions.

AuthorsOpenReview ↗

We Look Forward to the Reviewer's Response and Further Discussion

We sincerely thank you for your time and effort in reviewing our work, and truly appreciate your support.

With only three days remaining in the discussion period, we would appreciate it if you could let us know whether our response has addressed your concerns. Please also feel free to raise any further questions or concerns, and we would be happy to provide additional clarification.

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

The paper proposes CADY, a critic-free credit assignment method for long-horizon LLM agents with a binary terminal reward. For each question, it fits a small Cloned HMM (CHMM) by EM on the rollout group, using discrete elements (executable actions for text games, retrieved content for QA) plus a terminal CORRECT/WRONG element. The value of a history is the posterior-weighted probability of reaching CORRECT under the learned transition matrix (a backward DP). Step credits are one-step TD differences of these values, rescaled by the batch median and compressed with asinh, and added with weight α\alpha to a GRPO-style episode advantage. Theorem 3.1 shows that, for a correctly specified parametric trajectory model, the plug-in value estimate has no larger first-order asymptotic variance than a within-group MC estimate. Experiments use Qwen2.5-1.5B/7B on CookingWorld, TextWorld Commonsense (TWC) and Search-R1-style multi-hop QA, against Turn-PPO, GRPO, GiGPO, SHADOW and HCAPO. CADY gives large gains on the two embodied tasks (e.g. 95.3 vs 64.3 on CookingWorld at 1.5B), small gains on QA, lower value-estimation error on sampled histories, and a CHMM fitting study on AutomationBench.

Critical strengths
  1. The paper tests the mechanism, not only the final success rate. Fig. 1b measures the error of the value estimate against 16 fresh rollouts per history, Fig. 4c separates the clone representation from the shared-dynamics estimation, and Fig. 1a/4a check that histories with different futures get different posteriors. This chain is more than most credit-assignment papers give. The method itself is also simple and cheap: no critic, one small CHMM per question fit by EM, about 20% extra wall-clock and negligible memory (App. C.1). This is why I think the idea is worth publishing in some form.

  2. On the two embodied benchmarks the gains are far outside seed noise at both scales (CookingWorld 95.3 vs 64.3 at 1.5B and 97.7 vs 83.2 at 7B; TWC 75.3 vs 65.4 and 68.5 vs 36.2), against five baselines from three families, with three seeds and std reported. If these numbers hold under the checks below, this is a strong result on tasks with up to 50 decision steps.

Critical weaknesses
  1. The baseline numbers need more support before the size of the embodied gains can be interpreted. All baselines are re-run by the authors on CookingWorld and TWC, which none of the baseline papers used, and with custom environment configs (2 locations, 2-3 ingredients, no doors). I do not doubt the CADY numbers, but several things in Table 1 and the curves make the margins hard to read.

    (a) GRPO gets 2.0% and 5.3% on TWC while Turn-PPO gets 56.8% and GiGPO 65.4%, and the text does not comment. This matter a lot, because GRPO is CADY with α=0\alpha = 0 (Eq. 9), so on TWC the comparison is between the full method and a run of its own base that seems not to have trained successfully.

    (b) The spread between baselines is much larger than in their own papers. On CookingWorld 1.5B, HCAPO and SHADOW are 39 and 27 points above GiGPO; in their own papers, HCAPO is within about 1 point of GiGPO on ALFWorld/WebShop and SHADOW is about 8-9 points above it. On TWC, SHADOW is below GiGPO at both scales. Different tasks can give different rankings, but a spread this large suggests the baselines were not equally tuned for the new environments, or that seed variance is larger than the reported std.

    (c) All methods train for exactly 300 steps. In Fig. 3a GiGPO is still rising steeply at step 300 (from about 10% to 65% in the last 80 steps) and the CADY-GiGPO gap shrinks from about 50 to 10 points, so the sentence "gap over GiGPO widening later in training" does not hold for TWC. Part of the Table 1 margin may reflect how fast a method leaves the zero plateau rather than where it converges.

    (d) The 7B models use a harder config (one more ingredient / item, Table 3) with no reason given. On TWC this change roughly halves the four non-collapsed baselines (e.g. GiGPO 65.4 to 36.2) but moves CADY only from 75.3 to 68.5, so "the gains persist at 7B" mixes model scale with task difficulty. No baseline-specific hyperparameters are given and no code is released. Training curves and per-seed numbers for all baselines, longer runs (or a time-to-threshold metric), and a 7B run on the 1.5B config would resolve most of this, and I would raise my score if the margins hold.

  2. The value estimate and the step credit are not analysed in the regime where they are actually used. Each CHMM is fit on only 32 (embodied) or 64 (QA) rollouts, with up to 6 clones per element, pseudocount 10−610^{-6} and 5 EM updates, and the terminal CORRECT/WRONG element of each trajectory is part of the fitting data. After a few steps the action prefix of a 50-step rollout is unique, so EM can route each trajectory through its own clones, and the "value" of a history then becomes that trajectory's own outcome. The paper never checks this: Fig. 1b uses histories sampled "during training" (in-sample), only Fig. 1a uses held-out histories, and there is no MSE as a function of clone count. The "transition-memory coefficient" (0.6) is never defined, so I cannot tell if the CHMM is warm-started across policy updates (then it mixes stale off-policy transitions). On the credit side, raw TD credits are in [−1,1][-1, 1], but Fig. 3c shows CADY advantages up to about 8.8. With Eq. 8 this means the batch median ∣A~CHMM∣|\tilde{A}^{\mathrm{CHMM}}| is below about 0.003, so most steps carry almost zero credit, the informative steps sit in the log regime of asinh, and the telescoping identity (Eq. 7) that the text uses to interpret the credit no longer holds after normalization. Also, the only success-rate ablations are α∈{0.3,0.5,1}\alpha \in \{0.3, 0.5, 1\} and max clones {4,6,12}\{4, 6, 12\}, which all give 92-97%, while α=0\alpha = 0 (GRPO) gives 16.6%; a 3x change of the step weight does nothing but removing it costs 80 points, and this needs an explaination. "CADY w/o Clones", the paper's main novelty over shared dynamics on GiGPO groups, is only evaluated on MSE, never on success rate. Theorem 3.1 does not settle this question: it is the standard parametric efficiency result for any correctly specified plug-in estimator, uses nothing about CHMMs or clones, assumes N→∞N \to \infty rollouts per question under correct specification, and says nothing about bias under misspecification. It would be presented as motivation, not as a result about CADY.

Questions for authors
  1. What happened to GRPO on TWC (2.0% / 5.3%)? Please give validation curves and per-seed results for all five baselines on all tasks, state whether the official code of each baseline was used, and which baseline hyperparameters were tuned for the new environments.
  2. Please run CookingWorld/TWC until the curves flatten (or at least 2x longer) and report the final numbers, or report a time-to-threshold metric. Also fix the "widening" sentence for TWC.
  3. Why does the 7B setting use a harder environment? Please report 7B on the 1.5B config (or 1.5B on the 7B config), so scale and difficulty are not mixed.
  4. Report value MSE on held-out histories at the real group size (32/64), and MSE vs. max clone count. What fraction of histories have a unique prefix at each step? Please define the transition-memory coefficient: is the CHMM re-fit from scratch each batch or carried over across policy updates?
  5. Fig. 3c: is the plotted quantity A^CHMM\hat{A}^{\mathrm{CHMM}} or A^update\hat{A}^{\mathrm{update}}? What is the typical batch median of ∣A~CHMM∣|\tilde{A}^{\mathrm{CHMM}}|, and what fraction of steps get ∣A^CHMM∣<0.1|\hat{A}^{\mathrm{CHMM}}| < 0.1? Please add success-rate ablations for: step term only (no episode term), linear scaling instead of asinh, and CADY w/o Clones.
  6. For QA, the element is the exact retrieved text (C.1). How many elements are singletons? Is there any element for the answer step? Please also state the retriever, corpus and top-k, and why 2Wiki is in the training set but not in evaluation.
  7. Clone count: Table 3 says 1-6 clones per element, C.1 says "roughly 10". Which one is used in Table 1?
6 comments
AuthorsOpenReview ↗

Responses to Q1–Q4

We have revised the manuscript, with all textual changes highlighted in red, and added additional experimental results in Appendix C.5.

Q1:Baseline Reproducibility and Explained Performance Gaps

The complete training curves and per-seed results for all five baselines across all tasks are provided in Figs. 6–8 and Tables 4–6. We faithfully reproduced each baseline, tuned its method-specific hyperparameters for stable, strong performance, and controlled advantage magnitudes across methods to eliminate scaling effects. All hyperparameter settings are provided in Appendix C.4, Table 8.

The unusual performance of Turn-PPO and GRPO on TWC stems from its unique difficulty: agents can repeatedly pick up objects and undo correct actions, causing a mismatch between trajectory outcomes and step-level correctness. This particularly disadvantages GRPO, which assigns uniform advantages to entire trajectories. In CookingWorld, correct actions cannot be undone, reducing sensitivity to credit assignment granularity. Moreover, low accuracy leads to sparse feedback and advantage collapse, which poor credit assignment further exacerbates. This "snowball effect" amplifies performance gaps. As shown in Fig. 7a, GRPO improves the 1.5B model's TWC accuracy from 0.3% to 2.0%, indicating limited improvement due to advantage collapse.

Table 1 reports mean@8, which has lower seed variance and yields more stable results than pass@1. The larger performance gaps on CookingWorld and TWC stem from their greater difficulty (0.3% initial accuracy for Qwen2.5-1.5B-Instruct vs. 4% on ALFWorld), amplified by the aforementioned "snowball effect." This demonstrates their greater ability to distinguish between algorithms.

Q2:Near-Convergence Comparisons and Extended Training Curves

We thank the reviewer for this careful observation. The statement "gap over GiGPO widening later in training" should have been specified as an observation on CookingWorld. We have corrected this in the revised PDF. We report results at 300 training steps because all methods have nearly converged by this point. Therefore, the margins in Table 1 reflect the performance differences among methods near convergence. Detailed training curves over longer runs are provided in Figs. 6–8 of the revised PDF.

Q3:Fair Cross-Scale Evaluation and Demonstrated Scalability

We use different environment configurations for the 1.5B and 7B models because their capabilities differ substantially. After multiple trials, we selected environments with appropriate difficulty for each model scale, ensuring that the models neither receive almost no success signals nor master the tasks too quickly. Under the 1.5B configuration, most methods with the 7B model converge to nearly perfect accuracy, making it difficult to distinguish their capability limits, although CADY still converges faster than the other methods.

Notably, although different model scales use different environment configurations, all algorithms are compared fairly under the same model and environment settings. CADY's effectiveness indeed scales to stronger models and more challenging environments.

Q4:Dynamics Modeling Beyond Memorization, Ablation for Max Clone Count, and Fitting Details

Evidence of Dynamics Modeling Beyond Memorization

The reviewer raises the concern that CHMM may simply memorize rollout outcomes. However, the low squared error of CADY in Fig. 1b suggests otherwise: accurate prefix-value estimation requires modeling future trajectory dynamics, whereas memorizing a single sampled continuation would introduce substantial errors, even larger than those of GRPO. We use training data in Fig. 1b because CHMM is actually used to estimate the values of historical prefixes on these data, and we aim to directly evaluate its estimation accuracy. Moreover, the MSE on held-out histories shows a trend similar to the in-sample MSE (Fig. 9a), and the cross-fitted model achieves performance comparable to CADY (Fig. 10a). These results further support that CHMM does not simply memorize rollout outcomes.

Effect of the maximum clone count

We provide ablation curves for the maximum clone count in Appendix C.5 and additionally report MSE versus maximum clone count in Fig. 9b. CADY achieves its best performance with a moderate clone count (6), but its performance varies only slightly with clone count, indicating that CHMM fitting is relatively stable.

Meaning of transition-memory coefficient

CHMM is randomly initialized and fitted on each training batch, so no CHMM is carried across policy updates, avoiding the issue of mixing off-policy transitions. During each fitting procedure, the data are divided into multiple chunks. The "transition-memory coefficient" controls memory between these chunks, all of which belong to the same training batch.

AuthorsOpenReview ↗

Responses to Q5–Q7

Q5:Accurate Relative Credits and Component Ablations

Advantage magnitude and relative credit accuracy

Fig. 3c shows A^update\hat{A}^{\mathrm{update}} during the early stage of CADY training, rather than A^CHMM\hat{A}^{\mathrm{CHMM}}. The batch median of CHMM advantages first increases and then decreases as the policy improves (Fig. 10b). Initially, CookingWorld and TWC are extremely difficult for the base model, with an average accuracy of only 0.3%. Therefore, the values and credits predicted by CHMM are very small in early training. As the model improves, the credits gradually increase, and then decrease again as model performance approaches saturation. However, small s^CHMM\hat{s}_{\mathrm{CHMM}} does not imply that informative credits lie predominantly in the logarithmic regime of asinh. As detailed in Appendix C.2, s^CHMM\hat{s}_{\mathrm{CHMM}} is the token-weighted median of raw credit magnitudes. Thus, normalization brings typical credits to a comparable scale. The asinh transformation is approximately linear for small normalized credits, preserving their fine-grained differences, while logarithmically compressing the relatively few large-magnitude credits to prevent them from dominating optimization. In our experiments, only approximately 2% of raw credits have sufficiently large normalized magnitudes to enter the strongly compressed regime, while the remaining credits retain their fine-grained distinctions.

Importantly, small-magnitude credits can still provide informative distinctions between actions. The logarithmic regime serves to suppress extreme values, rather than define which credits are informative. CADY's effectiveness depends on accurately distinguishing the relative contributions of individual actions, rather than simply increasing advantage magnitudes. Indeed, scaling up advantages also amplifies noise, without necessarily improving the quality of credit assignment. To rule out scale effects, we controlled the average advantage magnitudes across methods for RL experiments. Thus, CADY's gains stem from more accurate relative value and advantage estimates (supported by its lower value-estimation MSE in Figs. 1b and 9a), rather than scale differences.

Telescoping identity and CADY advantages

The telescoping identity (Eq. 7) indeed no longer holds after normalization. It is a theoretical property of the raw credits and provides a perspective for understanding their allocation. The subsequent nonlinear transformation in Eq. 8 is introduced for optimization stability while preserving the relative ordering of the original credits.

Additional component ablations

"CADY w/o Clones" converges to performance between GiGPO and CADY (see Fig. 10a), consistent with the squared-error results in Fig. 4c. These results demonstrate the value of clone latent states and shared dynamics beyond local Monte Carlo estimation.

Combining episode- and step-level advantages is common in credit assignment (e.g., GiGPO, SHADOW, HCAPO), rather than a contribution of CADY. Thus, the step-only ablation has limited relevance to CADY's contributions.

Likewise, asinh⁡\operatorname{asinh} is not our innovation. It is widely used to preserve fine-grained differences while preventing large values from dominating policy updates, improving gradient stability (e.g., CAST, Wang et al., 2026). Thus, ablating it with linear scaling is also of limited relevance to CADY's contributions.

Q6:QA Implementation Details and Additional 2Wiki Evaluation

Details of CHMM elements in QA tasks

In our QA experiments, roughly 400 retrievals associated with each question typically correspond to approximately 80 CHMM elements, of which around 7% are singletons. We do not assign an element to the answer step because the terminal CORRECT/WRONG elements serve a similar function to an answer element, making an additional answer-step element unnecessary.

Retrieval settings and additional 2Wiki evaluation

We use E5-base-v2 as the retriever and Wiki-18 as the corpus, retrieving the top 3 most relevant passages at each step. These are the standard QA settings used in Search-R1 (Jin et al., 2025). We have also added experimental results on the 2Wiki test set (Table 7).

Q7:Clarified Clone Number Across Environments

The number of clones assigned to each element depends on its frequency of occurrence, with a linear relationship under our experimental settings. However, the maximum allowed clone count differs across environments: 6 for CookingWorld and TWC, and 12 for AutomationBench. This explains the description of "roughly 10" clones in Appendix C.1. We acknowledge that this wording was imprecise and have corrected it.

AuthorsOpenReview ↗

Responses to Q8

Q8:Explanation of the Performance Gap Between α=0\alpha=0 and α=0.3\alpha=0.3

The key distinction is whether fine-grained CHMM credit is enabled, rather than the precise value of α\alpha. As shown in Eq. (9), α=0\alpha=0 completely removes CHMM-based step-level advantages, leaving only GRPO-style episode-level credit, whereas α>0\alpha>0 introduces fine-grained credit assignment. Figures 1b and 3c demonstrate that CHMM provides more accurate value estimates and distinguishes the contributions of individual actions. Moreover, Figure 5a shows similar performance across α∈0.3,0.5,1.0\alpha\in{0.3,0.5,1.0}, indicating that enabling fine-grained credit matters more than its precise weight. The extreme difficulty of CW and TWC (0.3% initial accuracy) further amplifies this performance gap through the interaction between sparse success signals and ineffective credit assignment discussed in Q1.

We would like to know whether our responses have addressed your concerns. Please feel free to comment if there are any further confusions.

Reviewer_ypwUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses credit assignment for LLM agents on long-horizon tasks with a sparse terminal reward. It argues that existing critic-free methods (GRPO, GiGPO, SHADOW) group histories by local matching and estimate values only from rollouts in the same group, which can bias the value (histories with different futures share a group) and raise its variance (other rollouts are ignored). CADY instead fits, for each question, a cloned hidden Markov model (CHMM) to all rollouts with EM, computes each history's value as the probability of success from its posterior over clone states by dynamic programming, takes the change in value between consecutive steps as step-level credit, and adds it to the episode-level advantage (Eq. 9). Theorem 3.1 states that, with a correctly specified parametric trajectory model and an efficient estimator, the model-based value estimate has lower first-order asymptotic variance than a plain Monte Carlo estimate. Experiments use Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct on CookingWorld, TWC and question-answering benchmarks, against Turn-PPO, GRPO, GiGPO, SHADOW and HCAPO; the paper also reports lower value-estimation error (Figure 1b) and fitting experiments on a tool-use environment with about 500 API operations.

Critical strengths
  1. A well-motivated, simple, critic-free idea. Estimating each history's value from one model fitted to all rollouts addresses both problems the paper names (bias from local grouping, variance from ignoring other rollouts), and the paper states its extra cost (about 20% training time, Appendix C). This is consequential because it is a practical alternative to training a critic of the actor's size.

  2. The paper measures value-estimation error directly (Figure 1b) and not only success rate, and the reported gains on the embodied tasks are large (for example CookingWorld 95.3 versus 64.3 for the best baseline at 1.5B). This is consequential because it ties the claimed mechanism to the outcome, if the evidence can be trusted (see weakness 1).

Critical weaknesses
  1. The experiments are not convincing, and they are not well presented or explained.

    • The meaning of "±" in Table 1 is never defined; the caption says only that values are averaged over three random seeds. The values are tightly clustered: in my count, 21 of the 96 ± values equal 0.7 and 68% lie between 0.5 and 0.9, and the 72 QA values span about 0.3 to 0.9. Standard deviations or errors estimated from three runs should vary by a factor of several between cells, so this looks more like an evaluation-set error than seed variance, which would make "three seeds" uninformative about significance. Test-set sizes and the evaluation protocol are not stated.
    • The provenance and tuning of the baselines are not stated. The environment settings are the authors' own (and differ between the 1.5B and 7B models), so the numbers cannot come from the original papers. Appendix C.4 lists one RL configuration and I could not find baseline-specific tuning. Some baseline results are unexplained: GRPO scores 2.0 and 5.3 on TWC, far below even Turn-PPO (56.8 and 30.9), and 7B baselines score below 1.5B ones on TWC.
    • Only two models of one family are used (Qwen2.5-1.5B and 7B). The gains on question answering are small and not uniform (for example TriviaQA at 1.5B: SHADOW 54.4, CADY 53.9; Bamboogle at 7B: CADY 43.8, GRPO 41.2). The training curves compare only with GiGPO. The paper does not report its compute; from its own run times (about 10 and 30 hours on 8 A100 GPUs per run, plus 20% for CADY) Table 1 implies roughly 6,000 to 18,000 A100-hours (computed), depending on whether each cell is one training run or three.

    This is consequential because the central claim of large improvements over strong baselines cannot be assessed or reproduced from what is reported.

  2. The positioning, theory and figures are weaker than the framing suggests.

    • Important prior work is missing from the references: VinePPO (Kazemnejad et al., ICML 2025; arXiv:2410.01679), which estimates intermediate-state values from Monte Carlo rollouts for LLM credit assignment, and RUDDER (Arjona-Medina et al., 2019; arXiv:1806.07857), return decomposition for delayed rewards. The "local versus global" framing also overstates the difference, since the CHMM is fitted per question on the same rollouts the group-based methods use.
    • Theorem 3.1 is the standard statement that an efficient, correctly specified parametric estimator has lower asymptotic variance than a plain average. It assumes a fixed continuation-sufficient abstraction, a correctly specified model and an efficient estimator, which a discrete CHMM fitted by EM with smoothing is unlikely to satisfy, and it says nothing about bias under misspecification, finite samples or the quality of the resulting policy gradient.
    • Figure 2, the method overview, is a dense slide-style graphic with many icons and very small text that is hard to read at print size; the other figures are simple (box plots and two-curve plots) and carry little information.

    This is consequential because a reader cannot tell what is new relative to existing work, nor whether the theory supports the practical method, and the method itself is hard to follow from its main figure.

Questions for authors
  1. What does "±" in Table 1 measure (standard deviation, standard error, or a bootstrap over test questions), over how many training seeds and evaluation samples, and how were checkpoints chosen? Please give test-set sizes for each benchmark, and a significance test for the small gaps.
  2. How were the baseline numbers in Table 1 produced? Were all baselines rerun by you, in the same environments, with the same budget and equal tuning effort, and why is one shared configuration listed in Appendix C.4? Please explain the GRPO results on TWC (2.0 and 5.3) and show training curves for all baselines, not only GiGPO.
  3. Can you evaluate on other model families and sizes, and on the benchmarks used in the baselines' own papers?
  4. How does CADY relate, in idea and in results, to VinePPO (arXiv:2410.01679) and to RUDDER (arXiv:1806.07857) return decomposition?
  5. Do the assumptions of Theorem 3.1 (fixed continuation-sufficient abstraction, correct specification, efficient estimator) hold for the CHMM that is actually fitted for each question? Please show an empirical comparison of the variance (and bias) of the CHMM values against plain Monte Carlo values, and explain how the baselines' values were defined in Figure 1b, where the target is the mean of only 16 extra rollouts.
  6. Each CHMM is fitted on rollouts whose sequences end in their own outcome, and values are then computed for histories from the same rollouts. Does a rollout's outcome leak into its own credit? Please compare with leave-one-out or cross-fitted models.
7 comments
AuthorsOpenReview ↗

Responses to Q1–Q3

We have revised the manuscript, with all textual changes highlighted in red, and added additional experimental results in Appendix C.5.

Q1:Reliable Evaluation Protocol and Per-Seed Results

Evaluation Details

CookingWorld and TWC each contain 128 test instances (comparable to ALFWorld), while each QA benchmark contains 2k. All results are averaged over three training seeds, using the last-step checkpoint of each run. For each seed, we average the accuracy over eight rollouts per test question (mean@8), and ±\pm denotes the standard deviation across seeds. Compared with the commonly reported pass@1, mean@8 yields smaller variations and more stable results. These details and the per-seed results for all five baselines across all tasks (Tables 4–6) have been added to the revised PDF.

Statistical significance

Following common practice in agentic RL, we report the mean and standard deviation over three independent training seeds, with complete per-seed results provided in Tables 4–6. Given the limited number of seeds, formal seed-level significance tests would have low statistical power and be sensitive to distributional assumptions. We therefore avoid drawing potentially unreliable significance conclusions, and faithfully report per-seed results.

Q2:Fair Baseline Comparisons and Explained Performance Gaps

Baseline reproduction and hyperparameter tuning

We reproduced open-source baselines using their official repositories and faithfully implemented the others following their original papers. All shared configurations were kept identical, while method-specific hyperparameters were tuned to achieve strong and stable performance. Detailed settings are provided in Appendix C.4, Table 8.

Performance differences between GRPO and Turn-PPO on CookingWorld and TWC

The differences mainly stem from TWC's unique difficulty: agents can repeatedly pick up objects and undo correct actions, creating a severe mismatch between final outcomes and intermediate action correctness. This particularly disadvantages GRPO, which assigns a uniform advantage to the entire trajectory. In CookingWorld, correct actions cannot be undone, reducing sensitivity to coarse-grained credit assignment. Instead, Turn-PPO's critic estimation errors dominate, making it less effective than GRPO. We have added training curves for all methods in the revised PDF (Figures 6–8).

Explanation of Performance Differences Between 1.5B and 7B Models on TWC

The 7B models use a more challenging TWC configuration. Given the large capability gap between model scales, we selected appropriate difficulty levels through multiple trials to ensure sufficient success signals without rapid saturation. Thus, results across model scales on TWC are not directly comparable.

Q3:Additional Experiments Demonstrate Broad Generalization

Additional evaluation on ALFWorld

We have additionally reported the performance of all methods on ALFWorld in Table 7. The results show that our method maintains a consistent advantage even on this relatively simple and nearly saturated benchmark. We focus on CookingWorld and TWC because they require multiple dependent subgoals, including ingredient preparation and multi-object rearrangement. Under our configurations, completing these tasks involves multiple essential interactions, making credit assignment challenging. They are also empirically harder for our base model: Qwen2.5-1.5B-Instruct achieves only 0.3% initial accuracy, compared with 4% on ALFWorld. These challenging environments better reveal the capability limits of credit assignment methods in long-horizon RL.

Generalization across model families

We have additionally evaluated Llama-family models on CookingWorld. The results show that our method consistently improves over the baselines across different model families.

Performance on single-hop QA

Although CADY performs slightly worse than SHADOW on TriviaQA, it outperforms all other baselines on the remaining single-hop datasets. Although CADY is not designed for single-step tasks such as single-hop QA, it demonstrates robust generalization to these tasks.

AuthorsOpenReview ↗

Responses to Q4–Q6

Q4:Differences from RUDDER and VinePPO

Differences between CADY and RUDDER:

  1. Task settings. RUDDER was proposed in 2018 for credit assignment in traditional RL tasks (e.g., Atari). It cannot be directly transferred to LLM-based settings, making a direct experimental comparison difficult.
  2. Modeling objectives. RUDDER uses an LSTM to directly predict the final trajectory return. Like the critic in PPO, it models the value of historical states. In contrast, CHMM explicitly models latent transition dynamics, directly exploiting trajectory dynamics.

Differences between CADY and VinePPO:

VinePPO estimates intermediate values through multiple additional rollouts, incurring substantial computational overhead. As acknowledged in the original paper, its experiments are limited to mathematical reasoning tasks with at most 10 steps, rather than long-horizon agentic tasks. In contrast, our tasks involve dozens or hundreds of steps (e.g., 50 steps in CookingWorld and TWC), where even a single rollout is costly. Thus, VinePPO's additional rollout overhead is impractical. CADY instead efficiently estimates values by leveraging global trajectory dynamics without additional rollouts.

Q5. Theoretical Clarifications and Reliable Value Estimation

Applicability of Theorem 3.1.

Theorem 3.1 indeed relies on idealized assumptions abstracted from the practical algorithm. Its role in our paper is to provide motivation and theoretical support, rather than a rigorous guarantee for the practical algorithm. We have discussed this in detail in Appendix A.2.

Value estimation results in Figure 1b.

Although Figure 1b computes squared errors using 16 rollouts, we repeated the experiments over 1,000 prefixes with five random seeds and observed the same trend as in Figure 1b. This shows that CADY consistently achieves lower value estimation MSE than the baselines, rather than benefiting from random sampling fluctuations. We believe that analyzing the absolute magnitudes of bias and variance relative to MC estimation is of limited value. What matters more is the relative MSE of CADY compared with other baselines.

Definitions of baseline value estimates in Figure 1b.

The value estimates of all baselines strictly follow the advantage construction methods in their original papers:

  • GRPO: The mean reward of all rollouts for the same question.
  • GiGPO: Rollouts are grouped based on local history similarity, and the value estimate is the mean reward of all rollouts within the same group.
  • SHADOW: Histories are softly grouped using the proposed DOW matrix, and the value estimate is the weighted mean reward within the group.

Q6. Evidence of Dynamics Modeling Beyond Memorization

CHMM is trained on all rollouts to exploit their dynamics; the potential "leakage" noted by the reviewer is therefore a deliberate design choice, not an error. Fig. 1a shows that CHMM distinguishes future dynamics on held-out rollouts, while Fig. 1b shows more accurate value estimates than baselines on training rollouts. Moreover, a cross-fitted variant achieves comparable performance on CookingWorld (see Fig.10a), suggesting that CADY's gains do not primarily rely on using each rollout's own outcome during fitting. Together, they support CHMM's ability to model overall trajectory dynamics. Our approach is also more efficient than leave-one-out fitting, which requires approximately one CHMM per rollout instead of one.

AuthorsOpenReview ↗

Responses to Q7

Q7. Global Dynamics Modeling Beyond Local Grouping

The reviewer suggests that our characterization of CADY as "global" is overstated. We believe this concern stems from a misunderstanding of what "global" refers to in our work.

We agree that CHMM is fitted per question using the same rollouts available to group-based methods. However, the distinction between global and local lies in how these rollouts are used for value estimation, rather than which rollouts are available.

Group-based methods such as GiGPO and SHADOW have two limitations:

  1. They group histories based only on local features (e.g., the previous observation), which can introduce substantial grouping bias.
  2. They do not consider value relationships across groups and estimate values using only rollouts within each group, leading to relatively high estimation variance.

In contrast, CADY fits global trajectory dynamics to implicitly group historical states based on global information about future trajectory similarities, assigning them to similar latent clone states through posterior inference. Moreover, CADY leverages the relationships among value equations for different historical states to estimate the value of a particular state, rather than restricting estimation to samples within a local group. In summary, by utilizing global dynamics, CADY achieves more accurate value estimation, which is the key distinction between CADY and group-based methods.

We would like to know whether our responses have addressed your concerns. Please feel free to comment if there are any further confusions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal and Remaining Concerns

Dear Area Chair,

We would like to briefly summarize our rebuttal and the current discussion. CADY tackles a fundamental challenge in long-horizon agentic RL: how to achieve accurate fine-grained credit assignment from sparse terminal rewards. Existing critic-free methods rely on heuristic history grouping based on local observations, which can introduce bias by conflating histories with different future dynamics and increase variance by ignoring information from other rollouts. CADY instead learns global trajectory dynamics through a lightweight CHMM. By modeling these global dynamics, CADY can distinguish histories that share the same current observation but have different future continuations, implicitly grouping them through distinct posterior distributions over CHMM latent states. It further estimates history values by leveraging shared transition dynamics across all rollouts. This provides a principled approach to improving both history-value estimation and fine-grained credit assignment, without the substantial computational cost of training a large critic.

Importantly, all three reviewers explicitly recognized the motivation and methodological merits of CADY. They described our approach as a “well-motivated, simple, critic-free idea”, a “principled mechanism” for reducing grouping-induced bias and value-estimation variance, and a practical alternative to training a large critic. One reviewer further emphasized that our mechanism-level validation is “more than most credit-assignment papers give” and that “the idea is worth publishing in some form.” The reviewers also acknowledged the substantial performance improvements and the direct evidence connecting improved value estimation to downstream success.

Throughout the rebuttal, we have responded point by point to all three reviewers' concerns with extensive additional experiments and clarifications:

  • Mechanism and robustness: We added action-level Progress/Undo credit analysis, showing that CADY assigns significantly higher credits to progress-advancing actions than to reversing actions (p < 0.001). Cross-fitting experiments further suggest that CHMM's effectiveness does not rely on memorizing the terminal outcomes of its fitting rollouts, but rather on learning shared trajectory dynamics. Additional rollout-budget sensitivity and representation-aliasing analyses demonstrate that CADY remains robust to moderate CHMM fitting errors. Together, these results provide direct evidence supporting the effectiveness and robustness of dynamics-based fine-grained credit assignment.
  • Scalability and generalization: We expanded our evaluation with additional benchmarks and model families, providing broader evidence of CADY's generalizability. To examine practical efficiency, we added end-to-end evaluations under varying rollout budgets, where CADY consistently outperforms GiGPO, even with only 4 rollouts (36.4% vs. 13.7%). Held-out value-estimation experiments on AutomationBench further demonstrate that CHMM can produce effective value estimates with limited rollout data in substantially more complex tool-use environments. These results support CADY's generalization, scalability, and practical efficiency.
  • Experimental reliability and reproducibility: We provided complete 400-step training curves for CADY and all five baselines across all evaluated benchmark categories and both model scales, together with per-seed results, raw success counts, baseline hyperparameter search ranges, and computational cost analysis. We also clarified the final evaluation checkpoint, training-curve construction, baseline implementations, and the intended role of single-hop QA, while acknowledging and explaining the identified reporting inconsistencies.

Taken together, these additions directly address the key concerns raised by the reviewers and provide stronger evidence for CADY's effectiveness. We respectfully hope the AC will consider both the reviewers' consistent recognition of CADY's core methodological contribution and the substantial additional evidence provided during rebuttal when making the final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.