TL;DR
SCOPE (Skill-Composed Progressive Exploration) is a new framework that trains LLM-based Web agents by decomposing complex, long-horizon tasks into a series of manageable "local skills." By iteratively discovering, chaining, and expanding these skills from both successful and failed attempts, SCOPE enables agents to systematically explore environments and achieve up to 18.6% relative performance gains over state-of-the-art baselines.
What Problem Does This Paper Address?
Building autonomous agents that can navigate the Web—ordering a pizza, managing a GitHub repo, or finding specific orders on a shopping site—is notoriously difficult. These are long-horizon tasks where a single mistake at step 2 can lead to total failure at step 20.
Current training methods (like Reinforcement Learning from Task rewards) suffer from two main issues:
- Sparse Successes: In a complex environment, an agent might almost never stumble upon a complete successful trajectory by chance, leaving it with nothing to learn from.
- Unexploited Failures: Most methods discard failed trajectories entirely. However, a "failed" attempt often contains 90% of the correct steps. Ignoring these partial successes is a massive waste of data.
Methods
Inspired by human skill acquisition theory, the authors propose SCOPE, which moves away from "naive" end-to-end exploration toward a progressive, additive approach.
The framework operates in four iterative stages:
- Skill Discovery: An auxiliary LLM parses historical trajectories into "Contiguous Memory Units." It identifies which segments were successful "local skills" (e.g., "navigating to the order page") and which were "failure experiences."
- Skill Orchestration: The agent treats discovered skills as nodes in a state graph. It selects a promising "frontier state"—a point it has reached successfully before—to serve as the starting point for the next exploration attempt.
- Skill Expansion: Once at the frontier, the agent uses its memory of past failures to avoid repeating mistakes. The authors tested two strategies: OPTI (Teacher Intervention, using a stronger model to guide the next step) and OPSI (Self Intervention, where the agent uses its own failure logs to correct itself).
- Skill Distillation: Finally, the successful "skill chains" are internalized into the agent's policy parameters through on-policy distillation, making the agent natively capable of performing the task without needing the external memory bank during inference.
Datasets
The authors evaluated SCOPE across three diverse environments:
- WebArena-Lite: A realistic, hosted offline environment covering Reddit, GitLab, and Shopping sites.
- WebVoyager: A challenging benchmark involving real-time interactions with live websites like GitHub, Amazon, and ArXiv.
- WebShop: A simulated e-commerce environment frequently used for RL agent evaluation.
Key Insights and Ideas
- From Exponential to Polynomial: The paper provides a theoretical proof (Proposition 1) showing that naive exploration's difficulty grows exponentially with task depth. By exploring from a "frontier" of known skills, SCOPE reduces this complexity to a polynomial scale, making long-horizon tasks tractable.
- Failure is a Compass: Instead of viewing failures as noise, SCOPE treats them as boundary markers. By knowing exactly where a previous attempt went off the rails, the agent can focus its exploration budget on finding the "correct" branch at that specific state.
- The Power of Self-Correction: A fascinating finding was that for stronger models (like Llama 3.1-8B), the "Self-Intervention" (OPSI) strategy often outperformed "Teacher Intervention" (OPTI). This suggests that as models become more capable, they benefit more from learning how to fix their own mistakes than from following a perfect external script.
Key Results
SCOPE consistently outperformed the strongest baselines (like WebRL and GRPO) across all benchmarks:
- WebArena: Achieved a 54.3% success rate with Llama 3.1-8B, a relative improvement of 18.6% over the previous best method.
- WebVoyager: Showed a 14.7% relative gain, proving the method's robustness on live, non-stationary websites.
- Efficiency: As shown in the exploration dynamics, SCOPE discovers significantly more successful trajectories for the same number of environment interactions compared to naive sampling.
Limitations and Future Work
- Text-Centricity: The current implementation relies primarily on text-based webpage observations (HTML/AXTree). The authors note that incorporating visual cues (screenshots) could further improve performance by providing layout and color context.
- Dynamic Environments: While SCOPE uses "robust skill execution" to ground actions in new page states, extremely volatile websites might still render some learned skills obsolete.
- Safety: The authors acknowledge that training agents on live websites carries risks of unintended actions, highlighting the need for better monitoring and "guardrail" mechanisms in future iterations.
Summary updated