🤖 AI

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

This paper proposes a subgoal-driven framework combining online planning via subgoal decomposition and the MiRA reinforcement learning approach with milestone-based rewards, which significantly enhances long-horizon LLM agent performance on web navigation tasks, enabling open-source models to outperform leading proprietary systems.

Original authors: Taiyi Wang, Sian Gooding, Florian Hartmann, Oriana Riva, Edward Grefenstette

Published 2026-03-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Taiyi Wang, Sian Gooding, Florian Hartmann, Oriana Riva, Edward Grefenstette

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly impatient, robot to navigate a massive, chaotic city (the internet) to find a specific, hidden treasure (completing a complex task like "find the nearest cafe within 50 miles of CMU").

The problem is that the robot often gets lost, goes in circles, or gives up halfway because the city is huge and the instructions are vague. This paper introduces a new way to train these robots so they don't just "guess" their way through, but actually plan and learn how to finish the job.

Here is the breakdown of their solution, MiRA, using simple analogies:

1. The Problem: The "Lost in the Middle" Robot

Current AI agents are like tourists who have a great map for the first block but then get confused.

The Issue: When a task is long (like navigating 10 different websites), the robot forgets where it started. It gets stuck in loops (clicking the same button over and over) or wanders off into a dead end.
The Result: Even the smartest robots fail about 50% of the time on long tasks because they lose their "train of thought."

2. The Solution: Breaking the Journey into "Checkpoints"

The authors realized that if you tell a robot, "Go to the moon," it might freeze. But if you say, "First, get to the airport. Then, get on the plane. Then, land," it can handle it.

They call these checkpoints Subgoals or Milestones.

Part A: The "Smart Co-Pilot" (Online Planning)

The Analogy: Imagine the robot is driving, but it has a Smart Co-Pilot (a super-smart AI model like Gemini) sitting in the passenger seat.
How it works: Every few steps, the Co-Pilot asks: "Hey, did we actually reach the last checkpoint? Are we still on the right road? What's the next sign we need to look for?"
The Benefit: If the robot starts driving in circles, the Co-Pilot immediately says, "Stop! You're going the wrong way. Let's turn back." This prevents the robot from wasting time and getting stuck.

Part B: The "Video Game Trainer" (MiRA - The Training Method)

This is the real magic. Usually, training a robot is like playing a video game where you only get a "Game Over" or "You Win" screen at the very end. If you fail after 50 levels, you get no feedback on why you failed.

The Old Way (Sparse Rewards): The robot tries to climb a mountain. It slips and falls. It gets no points. It tries again, slips again. It never learns how to climb.
The MiRA Way (Dense Rewards): The authors built a Progress Bar for the robot.
- Instead of waiting for the top of the mountain, the robot gets a "High Five" (a reward) every time it reaches a base camp (a subgoal).
- The "Potential Critic": Think of this as a GPS that glows brighter the closer you get to the next checkpoint. It tells the robot, "You are 20% closer to the goal!" or "You are 80% there!"
- Why it helps: This gives the robot constant feedback. It learns that "clicking this button" is good because it moves the progress bar forward, even if it hasn't finished the whole task yet.

3. The Results: Small Robots Beating Giants

The team tested this on two types of robots:

The "Big Brains" (Proprietary models like Gemini): They added the "Smart Co-Pilot" (Online Planning). The robot got much better at not getting lost, improving its success rate by about 10%.
The "Small Brains" (Open-source models like Gemma): They used the "Video Game Trainer" (MiRA) to teach the small robot.
- Before: The small robot succeeded only 6.4% of the time.
- After: With MiRA, it succeeded 43.0% of the time.
- The Shock: This tiny, open-source robot, trained with this new method, actually beat the massive, expensive, closed-source robots (like GPT-4o) which only managed around 14%.

4. Why This Matters

Think of this like teaching a child to bake a cake.

Old Method: You tell them, "Make a cake." They mix flour, water, and dirt, put it in the oven, and burn it. You say, "Bad cake." They try again and burn it again. They never learn.
MiRA Method: You give them a recipe with steps. "Step 1: Mix dry ingredients." (Reward: Good job!). "Step 2: Add eggs." (Reward: Good job!). If they skip a step, you gently guide them back.
The Outcome: The child learns the process, not just the result. They become a master baker much faster.

Summary

The paper introduces a framework called MiRA that helps AI agents stop getting lost in long tasks. It does this by:

Breaking big goals into small, checkable steps (Subgoals).
Giving constant feedback (Rewards) for every small step completed, not just the final result.
Using a "Co-Pilot" to check the robot's work in real-time.

The result? We can now train smaller, cheaper AI models to be incredibly good at navigating the complex digital world, outperforming even the biggest, most expensive AI models out there.

1. Problem Statement

Large Language Model (LLM) agents have shown promise in digital environments (web navigation, OS control), but they struggle significantly with long-horizon tasks. The core challenges identified are:

Loss of Planning: During online execution, agents often lose track of the final goal as new information arrives, leading to "mid-task stuck" behaviors (repetitive loops) or suboptimal paths.
Sparse Rewards: In Reinforcement Learning (RL) fine-tuning, the reward signal is typically binary (success/failure) and delayed until the very end of a long sequence. This makes credit assignment difficult, preventing agents from learning which intermediate actions led to success.
Performance Gap: Even state-of-the-art proprietary models (e.g., Gemini 2.5 Pro) and open-source models suffer sharp performance degradation as task complexity and sequence length increase. On benchmarks like WebArena-Lite, agents frequently fail to progress beyond the first few steps.

2. Methodology: The Subgoal-Driven Framework

The authors propose a unified framework that integrates explicit subgoal decomposition into both the inference (planning) and training (RL) phases. The framework consists of three main components:

A. Automated Failure Analysis

Before designing the solution, the authors built an automated analyzer using a strong teacher model (Gemini-2.5-Flash) to inspect agent trajectories.

Function: It categorizes failures into modes (e.g., "Stuck Midway," "Wrong Termination," "Fail to Attempt") and pinpoints the exact Key Decision Step where the agent deviated from a successful path.
Finding: The dominant failure mode across all models is "Get Stuck Midway" (approx. 42-49% of failures), indicating a lack of robust long-term planning and self-correction.

B. Inference-Time Planning: Dynamic Milestoning (SGO)

To improve online execution, the framework introduces a Subgoal Generator (SGG) and a real-time planning loop.

Subgoal Generation: A teacher model (Gemini-2.5-Pro) decomposes high-level user intents into a structured checklist of intermediate subgoals (milestones).
Retrospective Reflection: At every step, the agent queries its own interaction history against the subgoal checklist. It asks:
1. What milestones have I achieved?
2. Have I completed the current subgoal?
3. What future milestones remain?
Mechanism: This creates a "situational awareness" loop. If a subgoal is unmet, the agent re-plans; if met, it anchors the state and moves to the next. This prevents hallucination and breaks repetitive loops.

C. Offline RL Fine-Tuning: MiRA (Milestoning your Reinforcement Learning Enhanced Agent)

To address the sparse reward problem in training, the authors introduce MiRA, an RL framework that uses Potential-Based Reward Shaping.

Dual-Critic Architecture:
1. Value Critic ( $V_\phi$ ): Predicts the probability of final task success (binary outcome).
2. Potential Critic ( $P_\psi$ ): A dense progress model trained to predict the fraction of subgoals completed. It acts as a "progress bar" for the agent.
Reward Shaping: Instead of waiting for the final reward, the agent receives a dense auxiliary reward at every step based on the change in the potential function:
$r'_t = r_t + \alpha [P_\psi(s_{t+1}, g) - P_\psi(s_t, g)]$
This guides the agent toward intermediate milestones, effectively smoothing the optimization landscape.
Policy Optimization: The actor is updated using a Mean Squared Error (MSE) regression on log-probability ratios (similar to DPO but adapted for RL), which offers better stability and off-policy sample efficiency compared to standard KL-divergence minimization.
Iterative Curriculum: The training loop is dynamic. Failed trajectories are analyzed to generate harder task distributions for the next phase, progressively patching the agent's weaknesses.

3. Key Contributions

Automated Failure Analysis: A systematic tool that quantifies the "mid-task stuck" phenomenon, providing data-driven motivation for subgoal-based interventions.
Dynamic Milestoning (Inference): A real-time planning mechanism that uses subgoal checklists to ground agent reasoning, reducing hallucinations and enabling self-correction without prohibitive latency.
MiRA (Training): A novel RL framework that synthesizes Process Reward Models (PRMs) with explicit, verifiable milestones. It replaces sparse binary rewards with dense, milestone-based shaping signals, significantly improving credit assignment in long-horizon tasks.
State-of-the-Art Performance: Demonstrating that a 12B open-source model (Gemma-3) trained with MiRA can outperform much larger proprietary models.

4. Experimental Results

The framework was evaluated on WebArena-Lite (165 tasks across 5 domains: Shopping, Map, Reddit, Gitlab, CMS).

Open-Source Performance:
- Gemma-3-12B + MiRA achieved a 43.0% average success rate.
- This significantly outperforms the previous open-source SOTA WebRL (38.4%) and standard SFT baselines.
- Crucially, it surpasses proprietary giants: GPT-4-Turbo (17.6%) and GPT-4o (13.9%).
Proprietary Performance:
- Applying the SGO (Subgoal-Oriented) inference framework to Gemini-2.5-Pro boosted its success rate from 23.0% to 32.1% (an absolute gain of ~10%).
Failure Mode Analysis:
- The "Stuck Midway" error rate dropped from ~48% (Base Gemini Pro) to 39.87% with SGO.
- MiRA reduced the "Stuck" rate in open models from 33% (SFT) to **21%**.
Ablation Studies:
- Removing the Potential Critic (dense shaping) caused performance to plateau at ~35%, confirming the necessity of dense rewards.
- Using KL-divergence instead of MSE regression resulted in slower convergence and lower final performance.

5. Significance and Impact

Bridging the Gap: The paper proves that explicit planning (via subgoals) combined with dense reward shaping is more effective than simply scaling model parameters. A 12B open model can outperform massive proprietary systems when equipped with the right training and inference architecture.
Solving Long-Horizon Reasoning: It addresses the fundamental bottleneck of "credit assignment" in sequential decision-making, showing that breaking tasks into verifiable milestones is a robust strategy for both training and inference.
Path to Self-Evolving Agents: The framework demonstrates a closed-loop system where a strong model can diagnose its own failures, generate curricula, and train a successor, paving the way for autonomous, self-improving digital agents.
Practicality: The approach is computationally efficient; the dynamic inference strategy allocates "thinking budget" only when necessary, balancing latency and performance.

In conclusion, this work establishes that milestoning—both as a planning tool and a training signal—is a critical component for building robust, general-purpose autonomous agents capable of navigating complex, long-horizon digital environments.