Leveraging Interactions and Sequential Dependencies for Effective Credit Assignment in Search Agents

Search agents answer questions by iteratively issuing queries, retrieving evidence, and reasoning over the results. A key research question is how to assign informative scores to intermediate search steps without relying on an additional critic model. Our case studies highlight two factors that such scores should capture: interaction effects, where multiple pieces of evidence jointly support an answer, and sequential dependencies, where earlier search results guide later queries. We propose Sequential Shapley, a fine-grained credit assignment method for multi-turn search agents that accounts for both effects. It evaluates each subset of search steps through a continuation-induced closure within the observed trajectory. The resulting coalition value models sequential dependencies through expected future contributions, while Shapley attribution captures evidence interactions by aggregating marginal contributions across coalitions. Our theoretical analysis relates Sequential Shapley to standard Shapley values and supports an approximate backward-redistribution interpretation. We integrate these step-level rewards with GRPO to obtain SPGRPO. On seven search-augmented QA benchmarks, SPGRPO improves average success rates over the strongest baseline by 2.8 and 1.4 percentage points for Qwen2.5-3B and 7B, respectively. Ablations further support the benefit of jointly modeling evidence interactions and search dependencies in this setting.