- 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
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.
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.
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.