acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
reinforcement learning
Keywords:
LLM agent, reinforcement learning, milestone reward shaping, tool‑using agent

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_zqKfOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper considers the credit assignment problem in agentic reinforcement learning of large language models. Towards this problem, the authors propose MICO (Milestone-Informed Counterfactual Optimization). This algorithm introduces two main ideas: (1) use hand-designed milestones for partial credit assignment, and (2) use sibling continuations as counterfactual signal for advantage estimation. Notably, the methodology does not generalize across environments without hand-designing the milestones to use, which is not always possible for environments beyond this paper's main focus. The authors prove some theoretical claims about the algorithm, including properties about the optimum of the shaped objective and error bounds about the advantage estimation, whose value are unclear to me. Experiments are mainly conducted on a small agentic benchmark, TaskShop, devised by the authors. On this benchmark, the authors are able to see MICO improves over GRPO and other credit assignment methods when the rollouts per task is 2 with Qwen2.5-1.5B-Instruct. But this improvement does not generalize to when rollouts per task is 8 or other more standard benchmarks like WebShop and ALFWorld.

Critical strengths
  • The problem of study in this paper is critical and relevant. If credit assignment properly is solved, we will be able to see a huge improvement in agentic reinforcement learning of large language models.
Critical weaknesses
  • (Major) This manuscript fails to follow several important research practice.
    • The manuscript exceeds the page limit for the main paper.
    • The manuscript does not contain the required statement about AI usage.
    • References to related work have major flaws. For example, the paper "IAPO: Influence-Aware Policy Optimization for Credit Assignment in Multi-Turn Service Agents" was authored by Bo Ren, Yirong Mao, Yi Yang, Wenhui Que, while the authors cited this paper under "Yirong Mao et al.". Another example is, the paper "KV-PRM: Efficient Process Reward Modeling via KV-Cache Transfer for Multi-Agent Test-Time Scaling" was authored by Peng Kuang, Haibo Jin, Xiaoyu Han, Yanli Wang, Xiaopeng Yuan, Ye Yu, Kaidi Xu, Haohan Wang, while the authors cited this paper under "Peng Kuang, Haibo Jin, and Haohan Wang".
  • (Major) The results are notably weak.
    • The proposed methodology highly relies on a hand-designed, usable miletone and has poor generalizability for new environments.
    • The theoretical results are unclear in their value.
    • The experiment results are mainly negative, with the only improvement case being a very restricted setting, where the model is 1.5B, the RL rollout size is 2, and the task is a non-standard small benchmark devised by the authors.
  • (Major) The writing quality is poor. Throughout the paper, nested clauses and phrases that are unclear in their meanings often appear.
Questions for authors
  • Q1: Feel free to respond to the weaknesses raised.
  • Q2: Could the authors disclose their use of AI tools in preparing the manuscript?
Reviewer_oYhHOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes shaping a sparse outcome reward using some deterministic, state-based milestone checkers (φ). Additionally, it estimates turn-level advantages as the (shaped reward - mean of K same-state sibling continuations), truncated at L steps, reusing the shared KV-cache prefix. The authors show that maximizers of the shaped objective solve the task and that a non-solving policy earns at most β(1−φ₀).

Critical strengths
  • Thorough reporting of experimental details like null results, paired CIs, an evidence map and a provenance table for every number
  • Their pipeline is cheap and released publicly, so reproduction is convenient
Critical weaknesses
  • MICO shows no measurable gain over its own milestone-shaping baseline: against Dense-Shaping the difference is +3.1 points.
    • The paper's empirical arguements rests on that comparison, and the effects (2–4 of 64 tasks on a 2–3-step task) are smaller than the noise (4.7-point).
  • The "provable safety" contribution does not hold up: with γ=1 the shaping reduces to a partial reward that only covers the global optimum, and the failure-boundary experiment shows MICO collapsing to 2.1% under a single false-positive milestone while Dense-Shaping, with the same objective, stays at 67.7%.
    • This matters because this is the paper's main claimed advantage, yet MICO turns out more fragile to checker errors than the simpler baseline
Questions for authors
  • In the false-positive experiment, does dense-shaping use the same broken checker?
  • Why exactly does MICO collapse, given the objective still prefers buying? Does the episode end at Φ=1?
  • Can you run an ablation with Φ(s_{T+1}) set to 0, i.e., standard episodic shaping? If the gains vanish, they come from terminal partial credit rather than dense milestones.
Reviewer_qCA9OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MICO, which combines deterministic milestone checkers, potential-based reward shaping, and same-state counterfactual branching for agentic reinforcement learning. The method is implemented through LoRA fine-tuning of a 1.5B model. Evaluation primarily uses the diagnostic TaskShop environment, supplemented by robustness experiments and a WebShop transfer study.

Critical strengths
  1. Deterministic milestone checkers provide auditable process feedback without requiring a learned reward model.

  2. The authors transparently report multiple seeds, component ablations, compute comparisons, unsuccessful transfer, and checker-misspecification failures.

Critical weaknesses
  1. The methodological novelty and the value of the proposed combination are insufficiently established. Milestone-based rewards, potential shaping, and same-state rollout baselines are established ideas. MICO combines these components with familiar memory-saving techniques, but the paper does not demonstrate a sufficiently substantial advance beyond this combination. In the five-seed comparison, MICO and Dense-Shaping achieve the same mean success rate, while matched-wall-clock results also show parity. These findings leave the necessity of the additional counterfactual mechanism unclear. The Dense-PRM comparison, which directly addresses the motivation for avoiding learned process rewards, should also appear in the main results table rather than only in the appendix.

  2. The theoretical contribution is limited in scope and contains statements requiring correction. The bounded-return argument follows largely from a bounded potential and the strong condition that full milestone satisfaction is equivalent to success. Theorem 1 additionally needs an attainability assumption before concluding that every shaped-optimal policy succeeds almost surely. Corollary 1’s exact success–failure gap is also inaccurate for a finite set of Boolean milestones. More importantly, these global objective-level statements do not guarantee reliable learning with the practical estimator, which uses asymmetric truncation, partial branching, and clamping. The reported sensitivity to clamping and poorer full-horizon results further weaken the connection between the theoretical analysis and practical gains.

  3. The experiments do not substantiate the claimed relevance to long-horizon agent learning or practical efficiency. TaskShop allows at most eight environment steps, exposes all candidate attributes, and has a base policy averaging approximately two steps. WebShop shows no improvement over the untrained base, and ALFWorld has no RL evaluation. Moreover, MICO’s additional branches make its “two-rollout” setting substantially more expensive than two-rollout GRPO; iteration time is 32 seconds versus 5–7 seconds for group baselines. The 6 GB feasibility result is useful, but relies on LoRA and short trajectories, while the expanded reported comparisons use a 24 GB RTX 4090. This establishes a restricted implementation capability rather than demonstrated efficiency for realistic long-horizon training.

Questions for authors
  1. What specific methodological advance remains beyond combining milestone shaping with same-state sampling, and can matched-budget experiments establish a consistent benefit over Dense-Shaping? Please include Dense-PRM and CF-sparse in the main comparison.

  2. Can the theoretical statements be corrected and the guarantees connected more directly to the implemented estimator? In particular, how much of the observed benefit depends on truncation and clamping rather than improved credit estimation?

  3. Can the authors demonstrate improvements on a standard, genuinely multi-step benchmark and report total interaction, generated-token, wall-clock, and peak-memory costs, clearly separating 6 GB runs from the RTX 4090 reproductions?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.