PaperlayerView exact revision on arXiv

Source-linked AI summary

A Subgoal-driven Framework for Improving Long-Horizon LLM Agents

Taiyi Wang, Sian Gooding, Florian Hartmann, Oriana Riva, Edward Grefenstette

arXiv:2603.19685v1cs.AIcs.LGcs.MA

TL;DR

Long-horizon web agents struggle to maintain coherent progress during execution and to learn from sparse, delayed RL rewards. The paper combines explicit subgoal planning with milestone-based reward shaping, reporting stronger long-horizon performance for proprietary and open models. Its shaping approach remains dependent on reliable subgoal grounding and can favor early-task progress.

  • Problem

    Long-horizon web agents lose coherent progress during execution, while sparse and delayed rewards make successful actions difficult to identify during RL fine-tuning.

  • Method

    The framework combines online inference-time subgoal planning with offline RL fine-tuning using milestone-based reward shaping.

  • Results

    The framework improves long-horizon web-agent performance, with the open Gemma3-12B model reaching state-of-the-art benchmark performance according to the paper’s conclusion.

  • Takeaways & Limitations

    Combining explicit inference-time planning with milestone-based rewards significantly boosts agents’ long-horizon capabilities.

  • Takeaways & Limitations

    Milestone shaping depends on valid subgoals and can favor early-task trajectories; failed initial grounding leaves the shaping signal silent.

Abstract

from arXiv · show

Large language model (LLM)-based agents have emerged as powerful autonomous controllers for digital environments, including mobile interfaces, operating systems, and web browsers. Web navigation, for example, requires handling dynamic content and long sequences of actions, making it particularly challenging. Existing LLM-based agents struggle with long-horizon planning in two main ways. During online execution, they often lose track as new information arrives, lacking a clear and adaptive path toward the final goal. This issue is further exacerbated during reinforcement learning (RL) fine-tuning, where sparse and delayed rewards make it difficult for agents to identify which actions lead to success, preventing them from maintaining coherent reasoning over extended tasks. To address these challenges, we propose two contributions. First, we introduce an agent framework that leverages proprietary models for online planning through subgoal decomposition. Second, we present MiRA (Milestoning your Reinforcement Learning Enhanced Agent), an RL training framework that uses dense, milestone-based reward signals. The real-time planning mechanism improves proprietary models such as Gemini by approximately a 10% absolute increase in success rate (SR) on the WebArena-Lite benchmark. Meanwhile, applying MiRA to the open Gemma3-12B model increases its success rate from 6.4% to 43.0%. This performance surpasses proprietary systems such as GPT-4-Turbo (17.6%) and GPT-4o (13.9%), as well as the previous open-model state of the art, WebRL (38.4%). Overall, our findings demonstrate that combining explicit inference-time planning with milestone-based rewards significantly improves an agent's long-horizon capabilities, paving the way for more robust and general-purpose autonomous systems.

1. Introduction

Web navigation exposes persistent long-horizon planning failures in LLM agents, especially when agents must maintain progress across complex, multi-step interactions. The paper addresses these failures with explicit subgoal planning and milestone-based RL rewards.

  • Web navigation is a rigorous testbed because complex interactions demand reasoning, planning, and context maintenance.
  • Agents frequently lose progress through non-productive loops, suboptimal goal paths, and failure to identify the next useful milestone.
  • Nearly 50% of Gemini-2.5-Pro WebArena-Lite trajectories exhibit mid-task stuck behavior, while Gemma-12B-SFT fails to progress in over 30% of cases.
  • Existing approaches use reasoning traces, static decomposition, or tree search, but explicit milestones offer intermediate checkpoints toward final objectives.
  • The proposed framework unifies online subgoal-guided planning with offline RL fine-tuning through milestone-based reward shaping.

2. Related Work

Prior web-agent research spans prompting, imitation, hierarchical planning, process rewards, and reinforcement learning, but long-horizon coherence and reward reliability remain difficult. This work uses explicit milestones to connect progress tracking with verifiable objectives.

  • LLM-based GUI agents use prompting, imitation, or RL, each offering different trade-offs in zero-shot ability, adaptability, or data dependence.
  • Hierarchical planners generate intermediate subgoals, while unified architectures use the LLM’s reasoning trace as an end-to-end plan.
  • Tasks exceeding approximately 10 interaction steps often expose impaired subgoal coherence, weak replanning, and drift from the original aim.
  • Process Reward Models provide dense feedback, but learned progress signals can incur inference overhead and reward over-optimization.
  • Explicit milestones replace soft progress estimates with rigid semantic checkpoints that preserve continuous tracking while improving objective verifiability.

3. Preliminary

The paper models web navigation as a finite-horizon partially observable decision process in which agents act from interaction histories and receive sparse goal-completion rewards. Potential-based shaping motivates denser progress feedback for difficult long-horizon tasks.

  • Web navigation is formulated as a finite-horizon POMDP with latent states, observations, actions, transitions, rewards, and horizon H.
  • The policy selects actions from observation history because the environment state is only partially observable.
  • The state combines the current webpage view with the full interaction history, reflecting that progress depends on prior interactions.
  • The baseline environment supplies a sparse binary reward when the next state satisfies the task goal, or ends the episode at horizon H.
  • Potential-Based Reward Shaping adds progress information through a state potential, although exact potentials are difficult to obtain in high-dimensional environments.

4. Motivation: Quantitative Failure Analysis and Opportunities

The paper’s failure analysis moves beyond aggregate success rates to identify dominant behavioral errors and their earliest consequential decisions. Across tested agents, getting stuck midway is the leading failure pattern and motivates milestone-based planning.

  • Aggregate success rates reveal little about why web agents fail, motivating fine-grained analysis of failure behaviors and structural weaknesses.
  • The analyzer objectively confirms failures, categorizes them using prioritized hardcoded rules, and pinpoints the key decision step through trajectory comparison.
  • The analyzer compares failed trajectories with successful traces and detects semantic deviation or the entry point into repetitive loops.
  • In a representative task, the analyzer identifies Step 3 as the critical error because the agent selected an irrelevant film link instead of the correct entry.
  • The analyzer agrees with human labels on 10/10 Stuck in Midway and 10/10 Wrong Termination examples, but 8/10 Fail Attempt examples.
  • Get Stuck Midway dominates baseline failures across Gemini, Gemma, and Gemma-SFT, with failure ratios ranging from approximately 42% to 49%.

5. Subgoal-Oriented Web Agent

This section develops subgoals as reliable progress signals and integrates them into online planning and reinforcement-learning fine-tuning. Dynamic milestoning supports reflective execution, while MiRA combines final-outcome and progress critics for shaped policy updates.

  • Subgoal Generation: Subgoals are generated as reliable intermediate milestones spanning abstract user intents and concrete web actions.The method emphasizes website-specific constraints, appropriate granularity, and sequences of progress signals for long interactions.
  • Subgoal Quality: Generated subgoals function better as continuous progress indicators than as strict binary success gates.Completing every subgoal strongly indicates success, but agents can succeed through valid alternative paths that bypass individual milestones.
  • Subgoal Quality: 0.84 AUROC shows that the subgoal progress score rank-orders promising and failing traces, while Kendall’s τ=0.4585 confirms monotonic success progression with p<0.001.The probability of success increases strictly as more subgoals are completed.
  • Online Inference: Dynamic milestoning uses Gemini-2.5-pro for reflective state tracking, checking achieved, current, and future milestones before selecting the next action.The feedback loop turns subgoals into dynamic checkpoints for grounded planning and self-correction.
  • MiRA Reinforcement Learning: MiRA trains a binary-outcome value critic and a dense progress potential critic, then updates the actor with shaped rewards.The potential critic is driven by Sub-Goal Checker progress labels, while the value critic remains tied to final task success.
  • MiRA Reinforcement Learning: The actor optimization uses supervised regression in log-space, which the authors report as more numerically stable and more sample-efficient than probability-ratio methods.The formulation operates off-policy and leverages historical high-quality trajectories from the experience pool.

6. Experiments and Results

Experiments show that inference-time subgoal planning and milestone-based offline RL both improve long-horizon web-agent performance, while ablations and failure analyses identify the components and behaviors driving these gains. The methods improve success, reduce navigation stalls, and expose trade-offs involving compute and termination errors.

  • End-to-End Subgoal-Oriented Web Navigation Efficiency: 43.0% average success rate makes Gemma3 + MiRA the strongest open-source result, outperforming WebRL at 35.1% and DigiRL at 33.3%.The gains are especially large in Gitlab (56.7%) and Shopping Admin (54.3%), where procedural dependencies are strict.
  • End-to-End Subgoal-Oriented Web Navigation Efficiency: 23.0% →32.1% success rate shows Gemini-SGO improving the base Gemini-2.5-pro model by nearly 10 percentage points.This result indicates that subgoal-oriented inference optimization also benefits proprietary-model agents.
  • Inference Efficiency and Compute Trade-offs: Static inference budgets peak at ≈32.5% success with 8192 tokens but increase latency to over 19 seconds per step.The result establishes a compute–latency trade-off for explicit inference-time reasoning.
  • Multi-Phase MiRA Performance and Domain-Level Trends: MiRA rises from ~31% to 43% across training rounds, while baseline RL without subgoal shaping saturates near 35%.Per-domain trends are particularly favorable on Gitlab and Shopping Admin, where subgoal shaping supplies denser intermediate rewards.
  • Multi-Phase MiRA Performance and Domain-Level Trends: MiRA consistently outperforms its baseline across sample budgets, with a +7.9% Phase 2 gap at Pass@2 demonstrating faster convergence.The comparison uses average pass@k across tasks for MiRA and MiRA without subgoal modules.
  • Ablation Study on MiRA: Removing MiRA components causes substantial degradation: omitting the potential critic plateaus at ≈35%, while omitting doubly robust advantages collapses early performance to around 25%.The ablation summary attributes distinct roles to off-policy learning, critic-bias protection, and dense long-horizon credit assignment.
  • Result Analysis: Resolving the Planning Bottleneck: MiRA reduces Gemma3-12b-SFT’s stuck rate from ≈33% to ≈21%, outperforming WebRL at ≈25%.The reported reduction is associated with dense subgoal signals that help the agent recover from repetitive states.
  • Result Analysis: Resolving the Planning Bottleneck: MiRA’s wrong-termination errors rise to ≈31% even as navigation stalls decrease.The authors attribute this shift to termination bias and AutoRater’s focus on reaching the correct terminal page rather than verifying semantic answer details.

7. Discussion

The discussion presents MiRA as a unified approach combining explicit milestone-based reasoning with potential-based reinforcement learning, while identifying grounding quality as its key constraint. It also describes automated process supervision and a possible path toward self-evolving agents.

  • Discussion: MiRA transforms high-level intent into verifiable subgoals, combining explicit milestone-based reasoning with potential-based reinforcement learning.The framework applies milestoning across inference and training.
  • Discussion: Intermediate subgoals provide semi-supervised process supervision by densifying sparse outcome signals through a learned potential critic.The approach synthesizes semantic subgoals with a teacher model and grounds them in execution traces.
  • Discussion: Reliable grounding creates a progress curriculum, but failure to ground the first milestone leaves shaping silent and returns optimization to sparse rewards.This makes cold-start exploration difficult when initial milestones are hard to perceive or achieve.
  • Discussion: A capable model can plan, execute, judge progress, synthesize curricula, and generate shaping signals within a proposed self-improving loop.The discussion frames this as a possible shift from train-then-deploy systems toward lifelong learning.
  • Discussion: Future work targets learnable or hierarchical milestone generators, difficulty-aware shaping, and annealing auxiliary signals during training.These directions aim to address knowledge-sparse domains, unequal subgoal difficulty, and over-optimization for auxiliary rewards.

8. Conclusion

The conclusion presents dynamic milestoning and potential-based reinforcement learning as a framework for improving long-horizon web-agent planning. It reports state-of-the-art benchmark performance and argues that explicit structured planning remains important as web environments become more complex.

  • Conclusion: Dynamic milestoning and potential-based reinforcement learning enhance web agents’ long-horizon planning capabilities.The framework is presented as both an engineering solution and a scientific account of planning-oriented failures.
  • Conclusion: The open-source Gemma3-12B model outperforms vastly larger proprietary systems under the presented framework.The conclusion characterizes the result as state-of-the-art performance on the leading benchmark.
  • Conclusion: Explicit, structured planning embedded in inference and optimization is positioned as essential for bridging chat-based assistants and autonomous digital coworkers.The conclusion ties this claim to increasingly complex web environments.

Author Contributions and Acknowledgments

The paper acknowledges internship support, project guidance, conceptual direction, failure-analysis expertise, and contributions to problem formulation and experimental design. It also credits discussions on RL algorithm design, agent training, and computing resources.

  • Author Contributions and Acknowledgments: The first author’s internship took place within the Autonomous Agents team, whose members provided guidance, mentorship, and conceptual direction.Sian Gooding and Edward Grefenstette are specifically credited for overarching guidance, while Sian also contributed failure-analysis expertise.
  • Author Contributions and Acknowledgments: Oriana Riva and Florian Hartmann contributed insights to problem formulation and experimental design.The passage places these contributions within the broader project acknowledgments.
  • Author Contributions and Acknowledgments: Hao Sun and Martin Klissarov contributed discussions on RL algorithm design and the agentic training pipeline, while the A2 team provided computing resources.The acknowledgments connect these discussions and resources to the work’s completion.

A.1. Proof of PBRS Equivalence for Goal-Conditioned Tasks

The appendix establishes an equivalence between potential-based reward shaping and original-reward training with Q-function initialization by the potential. The result is stated for goal-conditioned tasks.

  • A.1. Proof of PBRS Equivalence for Goal-Conditioned Tasks: Potential-Based Reward Shaping is equivalent to training with the original reward while initializing the Q-function to the potential function Φ.The appendix provides a mathematical proof of this equivalence.
  • A.1. Proof of PBRS Equivalence for Goal-Conditioned Tasks: The proof applies to goal-conditioned settings where reward, value, and potential functions depend on a goal g∈G.The goal dependence is part of the stated proof conditions.

A.1.1. Equivalence of Bellman Updates

This section establishes, by induction, that potential-based reward shaping preserves the relationship between shaped and unshaped goal-conditioned Bellman updates. The proof relies on cancellation of potential terms and their independence from action and next-state variables in the relevant operations.

  • The two learning scenarios use shaped and original rewards with different Q-function initializations and Bellman updates.Scenario A adds γΦ(s′, g) − Φ(s, g) to the reward, while Scenario B initializes Q with Φ(s, g).
  • The proof proceeds by induction on iteration step k, checking the base case and then assuming the relationship at step k.The inductive step substitutes the shaped-reward definition and the inductive hypothesis into the Bellman update.
  • Because Φ(s′, g) does not depend on action a′, it can be pulled outside the maximization, allowing the γΦ(s′, g) terms to cancel.This reduces the shaped update to the corresponding unshaped Bellman expression with the potential offset preserved.
  • Because Φ(s, g) does not depend on next state s′, it can be pulled outside the expectation, completing the equivalence with the alternative Bellman update.The remaining parenthesized expression is exactly the Bellman update for Q^k+1(s, a, g) in Scenario B.

A.1.2. Implication: Goal-Conditioned Policy Invariance

The derived Q-function relationship implies that potential-based shaping leaves the goal-conditioned policy unchanged. The result follows because the potential is constant with respect to the action maximization, although the shaping scale still requires empirical calibration.

  • The shaped goal-conditioned Q-function equals the original Q-function offset by the potential Φ(s, g).This relationship directly establishes policy invariance for each specified goal.
  • Since Φ(s, g) is constant across actions, subtracting it does not change which action maximizes the Q-function.The shaped policy therefore matches the policy derived from the original Q-function at every iteration.
  • The final optimal policy under the shaped reward is identical to the optimal policy under the original reward.The stated guarantee applies for every state s and goal g.
  • α is selected by grid search on held-out validation tasks to maximize Success Rate while preventing shaped rewards from overwhelming the environmental signal.The reported best trade-off is α = 0.3.

A.2. Benefits and Trade-offs of Online Reasoning via Subgoals

Online subgoal reasoning improves long-horizon web-agent planning but introduces a reasoning-depth versus latency trade-off. The broader MiRA pipeline combines milestone-based feedback, filtering, offline updates, and evolving curricula to support learning from sparse-reward trajectories.

  • Benefits and trade-offs: Additional thinking budget can improve task success but increases inference latency.The section identifies this as an inherent trade-off of dynamic milestoning and deeper reflective planning.
  • Benefits and trade-offs: 32.5% Overall Success Rate is reached at 8192 static thinking tokens, while inference time rises from approximately 6.5 to 19 seconds.The increase is reported across the tested static-budget range.
  • Benefits and trade-offs: 26% Overall Success Rate at 16384 tokens shows diminishing returns from excessively large static reasoning budgets.The passage attributes the decline to unnecessary deliberation without improved decision quality.
  • Benefits and trade-offs: 32.12% success rate is achieved by Gemini’s Auto (Dynamic) thinking mode with 16.74 seconds average inference time.This is statistically comparable to the optimal static budget and avoids manual budget tuning.
  • MiRA pipeline: Subgoal completion checks are interpolated into dense progress scores, while perplexity filtering removes trajectories above a dynamic threshold.The resulting targets support potential-critic, value-critic, and actor optimization.
  • MiRA pipeline: Offline batched RL updates incorporate successful and failed trajectories while decoupling gradient updates from environment noise.The curriculum then evolves from simpler to more complex tasks through repeated interaction and refinement cycles.
  • Ablation findings: 36.4% performance at α = 0.3 indicates that moderate reward shaping improves credit assignment without overwhelming the terminal reward.Larger shaping factors reduce performance by distorting the reward landscape toward auxiliary progress.
  • Ablation findings: 36.4% is achieved with moderate-perplexity replay filtering, whereas low-perplexity-only and high-perplexity-only data achieve 27.9% and 23.6%, respectively.The high-perplexity tail is associated with noisy or out-of-distribution states that destabilize the value critic.
Loading 2603.19685v1…