- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
Reinforcement learning for long-horizon Large Language Model (LLM) agents typically relies on sparse, terminal rewards, which complicates the credit assignment problem. Existing graph-based approaches primarily utilize the "distance to the final goal" to capture reachability; however, they struggle to distinguish between competing local actions or to determine whether a given state represents meaningful progress. To address this, we propose MileGPO. This method extracts fine-grained, process-level credit from grouped on-policy rollouts by employing a three-tiered, nested credit design. Extensive experiments on two long-horizon benchmarks ( ALFWorld and WebShop) demonstrate that MileGPO offers a clear performance advantage.
Critical strengths
-
MileGPO leverages existing on-policy sampled trajectories and final rewards to construct graphs and optimize credit assignment. It requires no external process annotations, human labels, reward models, or additional environment interactions, thereby significantly reducing training complexity and overhead.
-
Traditional graph-based methods often struggle when faced with actions that result in the same graph distance or identical transition outcomes—failing to distinguish between better and worse paths. Through Reliability Calibration (RCS) and Progress-Contrastive Calibration (PCC), MileGPO successfully differentiates between genuine local progress and success-oriented trajectories among branches originating from the same state.
Critical weaknesses
- The core motivation of the paper is to address the inability of traditional "distance-to-goal" metrics to distinguish between different branches originating from the same state; the authors introduce a graph structure to provide more fine-grained credit assignment. However, in constructing this graph, the authors employ a form of "forced abstraction" (or canonicalization)—as described in Appendix A.5—where states sharing the same current observation are merged into a single graph node, regardless of the distinct historical paths that may have led to them. Furthermore, the recent observation-action history is explicitly excluded from the policy prompt.
A central premise of the paper is that a graph structure is necessary to provide finer-grained credit because standard distance-to-goal metrics fail to differentiate between branches stemming from the same state. Yet, the "forced state aggregation" used to build the graph inherently erases differences in success rates that arise from distinct historical trajectories. (As the authors themselves acknowledge in the appendix, when omitted historical information influences the completion of subsequent tasks, this aggregation can obscure variations in success rates at the node level.) Consequently, attempting to resolve the issue of "insufficient discriminative power" by using a graph—which functions as a form of lossy compression that discards historical context—introduces a logical trade-off and a potential internal contradiction.
- As the author candidly admits at the end of Appendix B: “These results do not establish that individual candidates are valid subgoals or that the branch score estimates true action values.” There is a logical gap here: while it is mathematically proven that the mechanism can adjust the advantage component within bounded limits, there is no rigorous theoretical guarantee that the “milestones” selected by the algorithm are, in fact, the “correct subgoals” truly necessary for achieving success in real-world tasks.
Questions for authors
-
The authors note that, when constructing state graphs, they normalize "observation anchors" using "exact matches" and explicitly exclude the recent observation-action history contained in policy prompts. The authors also acknowledge that this approach may obscure differences in success rates that stem from distinct historical trajectories. Could this "history-agnostic" abstraction of the state graph lead to the erroneous merging of decision points that—in reality—require long-term memory or specific historical paths to be distinguished? If so, does this introduce noise and compromise the reliability of the graph structure?
-
Through formal propositions, the authors demonstrate that potential shaping can control residual interpolation and resolve ties in distance metrics. However, they also concede at the end of the paper that these theoretical results do not establish whether the identified "candidates" are truly valid subgoals, nor do they guarantee that the branching scores accurately estimate the actual value of actions. How, then, do the authors ensure that the "milestone candidates" extracted from successful trajectories are semantically meaningful markers of progress, rather than merely "intermediate states" that appear frequently but contribute nothing of substance toward task completion?
We thank the reviewer for raising these important questions about state aggregation and milestone validity. We address them separately below.
Q1 · Can history-agnostic state aggregation compromise graph reliability?
History-agnostic aggregation is a deliberate trade-off between history sensitivity and cross-trajectory experience sharing. We acknowledge that identical observations reached through different histories may correspond to decision points with different future values, potentially introducing noise into the aggregated graph. However, this challenge is not unique to MileGPO. Existing step-level credit assignment methods, including GiGPO, GraphGPO, and HGPO, similarly aggregate repeated states across trajectories to enable local action comparisons and cross-trajectory credit propagation. This allows useful experience to be shared without additional sampling; for example, an effective early action in a failed trajectory can benefit from successful continuations observed in other trajectories.
Incorporating complete observation-action histories could distinguish these cases more precisely, but would substantially reduce state overlap and create numerous history-specific nodes. This would weaken cross-trajectory credit propagation while increasing graph construction and storage costs. MileGPO addresses the resulting reliability challenge through reliability weighting and local progress calibration. Specifically, MD, RCS, and PCC make credit assignment more sensitive to progress consistently supported by local evidence and aligned with task success, thereby mitigating the influence of path-specific noise.
Importantly, history is excluded from graph anchors, not from policy inputs. As detailed in Appendices A.2 and A.4, each policy prompt includes the two most recent observation-action steps, the current observation, the task description, and the available actions. The complete templates are provided in Figures 6 and 7 for ALFWorld and WebShop. Thus, the graph uses observation anchors for experience aggregation, while the policy retains recent interaction history for decision-making. We will clarify this distinction and explicitly discuss the associated trade-off in the revision.
Q2 · How are milestone candidates distinguished from incidental intermediate states?
Milestone candidates are success-informed progress signals, rather than theoretically guaranteed semantic subgoals. We agree that extracting candidates from successful trajectories alone does not establish their causal importance: a successful trajectory may contain incidental intermediate states that are not essential to task completion. Accordingly, MileGPO does not rely on candidate occurrence alone as sufficient evidence of meaningful progress.
The key is to calibrate how candidate-derived signals contribute to credit assignment. MileGPO leverages reliability weighting and local progress calibration through MD, RCS, and PCC, making credit assignment more sensitive to progress supported by local evidence and aligned with task success. This reduces the influence of unreliable or incidental progress signals, rather than treating every candidate extracted from a successful trajectory as an equally meaningful subgoal. We will clarify this distinction between theoretically established properties and practical candidate reliability in the revised manuscript.