DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training
Shubham Gandhi (CMU) with Saurabh Goyal, Kiran Kate and Yara Rizk at IBM Research tackle the outcome-blind setting, where long-horizon agent tasks have no programmatic checker, by redistributing a once-per-trajectory rubric judgment over the steps that earned it.
Ask this paper
A scalar over tens of steps is a bad signal: rubrics are the popular substitute for a verifier but are scored once per trajectory, which leaves credit assignment unsolved.
Rubrics generated during training: they are produced dynamically to track the policy's evolving capability rather than fixed in advance, so the reward stays informative as the agent improves.
Closed-form redistribution: the judgment is spread over the steps responsible for annotated rubrics to give differentiated per-step advantages in GRPO, with no trained attribution module to go wrong.
Beats ground-truth-reward training: +15.9 points over base and +5.3 over GRPO with a sparse ground-truth reward on AppWorld, despite using no verifier itself.
Transfers out of domain: +5.3 points on Tau-Bench even without a frontier judge, beating both ground-truth-reward training and other rubric-based settings.
Abstract
Reinforcement Learning from Verifiable Rewards works well when a task has a programmatic checker, but most long-horizon agent domains have none. We work in the outcome-blind setting, where ground-truth success signals are not available. Multi-criteria rubrics are a popular way to supply such a reward; they are scored once per trajectory, but a single scalar is a poor signal across tens of steps. We propose DRACO: Distributing Rubric-based Advantage for Credit Optimization. It generates rubrics dynamically during training to track the policy's evolving capability, scores those rubrics once per completed trajectory, and redistributes that judgment over the steps responsible for annotated rubrics to produce differentiated per-step advantages in GRPO. The redistribution is closed-form and does not introduce any trained attribution module. On AppWorld, DRACO gains 15.9 points over the base model and 5.3 points over GRPO trained with a sparse ground-truth reward, despite not using any verifiers itself. On out-of-domain Tau-Bench, it gains 5.3 points over the base model even without a frontier judge, beating both ground-truth-reward training and other rubric-based training settings. The code for DRACO is available at https://github.com/IBM/draco.