MICO: VERIFIABLE MILESTONES FOR PROVABLY BOUNDED CREDIT ASSIGNMENT IN AGENTIC REINFORCEMENT LEARNING

Reinforcement learning (RL) for language-model agents must assign credit across long, multi-turn tool-use trajectories from a single terminal outcome. Existing methods either train process reward models (PRMs) or LLM verifiers, an expensive and gameable investment, or discover subgoals from rollout statistics without formal guarantees. We propose MICO (Milestone-Informed Counterfactual Optimization), a training-time credit-assignment method built on verifiable milestone checkers: deterministic, environment-grounded predicates evaluated from environment state, with no auxiliary-model training or inference cost. MICO uses milestone progress as a potential for reward shaping and proves a practically checkable sufficient condition, milestone completeness, under which the shaped objective is maximized only by policies that solve the task, progress hacking is capped by the terminal reward gap, and an approximate-completeness bound quantifies how the guarantee degrades. MICO estimates per-turn counterfactual advantages from same-state sibling branches via shared-prefix KV-cache reuse (unbiased, variance-reducing, bounded truncation bias), on a single 6 GB consumer GPU with a 1.5B policy. Because the hypotheses require controlled completeness and spurious-signal injection, primary validation uses TaskShop, a deterministic diagnostic environment: MICO improves over the untrained base and two-rollout GRPO, matches eight-rollout GRPO at saturation, keeps a noncollapsing intermediate success rate at a two-rollout budget, degrades only 2.6 points under spurious per-view rewards that collapse Dense-Shaping by 24.5 points, and we map the failure boundary of the guarantee when the condition is violated. A learned PRM offers no accuracy advantage while needing auxiliary training; on WebShop at 1.5B we report a null RL-transfer result alongside verification of MICO’s checker against the official reward on 115,500 purchases.