DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training

DRACO. Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training. By Shubham Gandhi and three others, from Carnegie Mellon University and IBM Research. Published on the third of September. Its code repository is worked out: about one hundred and ten source files, with a readme and a licence.

Reinforcement learning from verifiable rewards works well when a task comes with a programmatic checker. Most long-horizon agent domains do not have one. This work operates in what it calls the outcome-blind setting, where ground-truth success signals are simply unavailable. The popular substitute is a multi-criteria rubric, scored once per trajectory. But one scalar handed back at the end of tens of steps is a poor signal, because it says the run went well without saying which of the things you did along the way made it so.

The move is to keep the rubric judgment where it is cheap to get, at the end, and then redistribute it over the steps that earned it. Rubrics are also generated dynamically during training rather than fixed in advance, so they track the policy's evolving capability instead of testing it against a bar set when it was worse.

Rubrics are scored once per completed trajectory, then that judgment is spread over the steps responsible for the annotated criteria, producing differentiated per-step advantages. The important detail is that this redistribution is closed-form. There is no trained attribution module anywhere in it, so nothing learns to assign blame and nothing can learn to assign it wrongly.

On AppWorld the method gains fifteen point nine points over the base model, and five point three points over the same algorithm trained with a sparse ground-truth reward, while itself using no verifiers at all. Beating verified training without a verifier is the result that matters. Out of domain on Tau-Bench it gains five point three points over the base model even without a frontier judge, beating both ground-truth-reward training and other rubric-based settings.

The claim to hold onto is about where the difficulty sits. Getting a judgment is easy and getting it attributed to the right step is hard, and the paper's answer is that attribution does not have to be learned if the rubric already names what it is judging.

DRACO. Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training. By Shubham Gandhi and three others, from Carnegie Mellon University and IBM Research. Published on the third of September. This is the long version: the whole paper rather than the abstract.

Two hard problems meet here, and what makes the combination interesting is that they are usually studied apart. One is training an agent when no verifier exists. The other is credit assignment across a long trajectory. Each has a literature. The intersection, which is where a lot of real agent work actually sits, has almost none.

Reinforcement learning from verifiable rewards drove much of the recent progress in language models, and its appeal is that it sidesteps a learned reward model entirely. A programmatic verifier, unit tests for code, exact match for maths, task-pass checks for agents, supplies a terminal reward that is reliable and hard to game. But the recipe rests on an assumption that fails in many real settings: that such a verifier exists at all. Customer-support agents and open-ended research agents have no programmatic oracle for success, and building one is frequently as hard as the task. So this work operates in what it calls the outcome-blind regime, where the training signal comes entirely from process criteria with no access to a ground-truth success or gold answer at any point during training. That is strictly harder than most of the reward literature assumes.

The second difficulty is specific to long horizons. A trajectory on a benchmark like AppWorld spans tens of interdependent tool-calling steps. Even when a reward does exist, spreading a single trajectory-level scalar uniformly over every step is statistically wasteful and can be actively harmful, because successful trajectories contain redundant or lucky steps and failed trajectories contain mostly correct ones. That is the classic credit-assignment problem, well studied when a terminal reward exists. What is missing is credit assignment when there is no verifier outcome to route, only a rubric verdict.

The full loop runs like this. For each task, a judge proposes criteria from the instruction and from each sampled trajectory. Those proposals are merged, deduplicated and scored, producing an outcome-blind reward for the trajectory. Then, within a rollout group, the surrounding algorithm normalises rewards into trajectory-level advantages in the usual way. The new part is what happens next: that trajectory advantage is reallocated across steps according to the judge's per-criterion verdicts, so credit concentrates on the steps the rubric actually implicates. The redistribution is closed-form, with no trained attribution module anywhere, and neither component assumes access to a ground-truth outcome at training time, which is what separates it from prior methods that tie step rewards to terminal verifiers or gold answers.

The numbers bear that out. On AppWorld the method gains fifteen point nine points over the base model, and five point three points over the same algorithm trained with a sparse ground-truth reward, while using no verifier itself. AppWorld is chosen deliberately: it is a benchmark where every previously reported reinforcement learning result had a verifier available, so the comparison is against methods operating with more information rather than less. Out of domain on Tau-Bench it gains five point three points over the base model even without a frontier judge, which matters because a method that only works with the strongest available judge is a method with an expensive dependency rather than a technique.

The limitations section is unusually honest and worth taking seriously, because it undercuts the natural reading of the results. First, using rubrics as rewards on unverifiable tasks means there is no independent signal against which to check whether the criteria describe the task faithfully. Validating them would need human raters, which the authors leave to future work. They use a single frozen judge for most experiments and do not report a chance-corrected measure of its agreement with human annotators, so as they put it: a judge that is internally consistent can still be systematically wrong, and these experiments cannot separate the two. Second, and this is the sharper admission, the same gap appears one level down in the attribution itself. The method is validated by end-task performance, which does not establish that credit lands on the right steps. A redistribution that credits the wrong steps can still improve a policy, and one that credits the right steps can fail to.

That second admission is the one to carry away. The paper demonstrates that this redistribution helps, and explicitly does not demonstrate that it is correct. Both of those are worth knowing, and a paper that only reported the first would be the more common kind.