SkillShift-Bench: Benchmarking Skill Learning under Environment Evolution for Web Agents

AI summary

Overview

Research area: Web agents / LLM-based agents, specifically skill (procedure) learning, benchmark design, and test-time adaptation under distribution shift.

Technical level: Intermediate. The benchmark design and empirical results are accessible, but Section 4 includes a formal nonstationary MDP formulation and a dynamic-regret bound that requires some background in online learning.

Scope: This paper introduces SkillShift-Bench, a controlled benchmark that measures whether previously learned web-agent skills remain executable when the same website changes its context, interface evidence, or runtime conditions, and proposes an executor-side reranking method (MPCR) to partially recover the resulting performance loss.

What This Paper Is About

Web agents increasingly reuse learned skills instead of planning every step from scratch, but those skills are almost always tested in fixed website snapshots. In deployment, the same site may change its navigation, its page structure, or its runtime behavior while a task's intent stays identical — so a skill can remain semantically relevant yet no longer be locally executable. The paper builds a benchmark that isolates exactly this failure (while holding the task fixed), diagnoses how existing skill-learning methods degrade, and shows that adapting the executor at test time — without relearning the skill library — recovers part of the loss.

Key Contributions

1. SkillShift-Bench, described as the first benchmark for evaluating learned skill executability under controlled open-environment shifts. It instantiates three shift modes — Contextual, Perceptual, and Execution Shift — across three self-hosted web systems (GitLab, Magento, WordPress) with 355 natural language tasks and four diagnostics (Success Rate, Average Steps, Average Skill Calls, Skill Failure Rate).

2. A formulation of shifted skill execution as nonstationary local executability, together with SWOP (Sliding-Window Optimistic Prior-Guided Planning), an idealized prior-guided adaptation model analyzed with a variation-dependent dynamic regret guarantee of Õ(K^{2/3}(V_K+1)^{1/3}) with probability at least 1−δ.

3. MPCR (Masked Prior-Guided Candidate Reranking), a practical test-time, fixed-library executor-side reranker that reselects among proposed primitive and skill-action candidates using current-page feasibility evidence, without adding new skills.

4. A diagnostic empirical study across four learned-skill methods (AWM, ASI, SkillWeaver, WALT) showing systematic robustness degradation under controlled shifts, strongest under Execution Shift, and a fixed-library comparison isolating the effect of executor adaptation.

Main Findings

• Aligned shifts degrade success even when the task is unchanged. ASI drops from 53.65% on the clean source context (Src) to 41.84% on the clean target context (Tgt, Contextual Shift) and to 15.79% on Tgt-Exec. Similar trends appear for AWM, SkillWeaver, and WALT.

• Pooled performance falls monotonically as shift pressure increases. Across the pooled views, success decreases from 40.97% (Base) to 35.23% (Perceptual) to 18.69% (Execution); average steps rise from 8.49 to 9.38 to 11.99; and skill failure rate rises from 9.83% to 16.70% to 27.60%.

• Execution Shift is the strongest pressure. Runtime modal blockers that intercept interactions degrade agents more than either contextual or perceptual change, indicating that failures are often about runtime feasibility rather than semantic relevance.

• Different methods fail through different channels. AWM is evaluated through prompted textual workflows, so explicit skill-call diagnostics are not applicable (reported as "–"). ASI and WALT expose execution pressure through skill failure rate (e.g., ASI SFR 55.20% on Src-Exec and 48.27% on Magento), while SkillWeaver more often reflects it through longer trajectories and more skill calls (e.g., AS 19.82 on Src-Exec, ASC 2.64 on WordPress).

• MPCR improves transfer under a frozen skill library. Average success rises from 37.90% (ASI) to 41.26% (MPCR), an 8.87% relative improvement, with gains in all six environments.

• MPCR's gains are pressure-dependent. Relative success gains are 24.55% on Src-Exec (26.68% → 33.23%), 12.62% on Tgt-Exec (17.75% → 19.99%), 8.51% on Tgt-Perc, 7.68% on Src-Perc, 7.35% on Src, and 1.14% on clean Tgt — largest where local execution is most fragile.

• Gains come from selection, not extra skill acquisition. ASI and MPCR share the same learned library; MPCR raises average skill calls only from 0.06 to 0.15, still well below one skill call per task, indicating evidence-conditioned activation of existing skills.

• Cumulative advantage grows with shift severity. MPCR's cumulative failure advantage over ASI is 11.0 under Base, 20.0 under Perceptual, and 32.0 under Execution, consistent with the SWOP account that recent feasibility evidence matters more when the learned prior becomes less reliable.

• The improvement is not bought with longer trajectories. Across Base, Perceptual, and Execution, MPCR improves success over ASI while staying in a comparable trajectory-cost regime.

Methodology in Plain English

The authors build a benchmark around "aligned task families." Each family has a source context (where a skill is learned) and an evolved target context (where the same task is attempted on a changed site). Four invariants are enforced so that only the environment changes, not the task: goal invariance (same instruction intent), entity invariance (same task-critical objects such as projects, issues, products, posts, pages, and accounts), functionality invariance (required operations remain available), and outcome invariance (equivalent automatic success criteria).

On top of that fixed task, three shift modes are applied:

• Contextual Shift: paired versions or themes of the same site, altering routes, navigation, page structure, workflow layout, or control placement.
• Perceptual Shift: task-preserving perturbations to layout, DOM structure, element attributes, and locator signals — the same signals that break recorded web-test scripts.
• Execution Shift: reproducible modal blockers injected on configurable schedules that intercept interactions mid-task.

Each task family is instantiated under six conditions: Src, Src-Perc, Src-Exec, Tgt, Tgt-Perc, Tgt-Exec. Tasks are built with a validity-first pipeline — seeded data, aligned entities, natural-language instructions, task-specific automatic scorers — and manually validated before shifted variants are generated. Each run is scored on four diagnostics: Success Rate (SR), Average Steps (AS), Average Skill Calls (ASC), and Skill Failure Rate (SFR).

For the method side, the authors first write down an idealized model (SWOP) in which an executor stays anchored to a reference prior (the fixed skill library plus base executor) while updating its beliefs from a sliding window of recent evidence, with optimism for uncertainty and KL regularization toward the prior. They prove a dynamic-regret bound that scales with a measured "variation budget" of the environment. Because real web agents do not have explicit MDP models, they translate the same three principles — use recent evidence, keep uncertainty-aware alternatives, regularize toward learned skill preferences — into MPCR: propose primitive and skill-action candidates, verify them against current-page feasibility evidence, score them for executability, and rerank a shortlist. In the main fixed-library comparison, MPCR considers at most 2 candidate actions per step and keeps a top-2 shortlist. The benchmark-level analysis uses DeepSeek-V3.2, GPT-5 mini, and Claude Haiku 4.5; the fixed-library ASI-vs-MPCR comparison uses GPT-5 mini.

Why This Matters

Impact on research. Most web-agent benchmarks ask "can the agent solve this task here?" This paper asks a different question: "does experience gained there still work here, when the task is identical?" That reframing turns environment evolution into a controlled intervention on skill transfer rather than a harder end-to-end test, and it yields failure attribution that aggregate success rates hide. It also connects web-agent evaluation to longstanding work on the breakage and repair of recorded web procedures in software testing, while arguing that runtime-feasibility breaks cannot be fixed by repairing a stored script.

Real-world applications:

• E-commerce administration (Magento-style backends): agents that reuse learned procedures for order, catalog, and inventory operations, where admin themes and layouts change across releases.
• Content management (WordPress-style systems): publishing, page, and account workflows that break when themes, plugins, or editor layouts update.
• Developer collaboration tooling (GitLab-style systems): issue, project, and merge-request procedures reused across version upgrades and navigation redesigns.
• Browser automation and RPA maintenance: recorded end-to-end scripts that break as applications evolve, and self-healing approaches that must distinguish "wrong target" from "target temporarily blocked."

Industry relevance. Any organization deploying browser agents or RPA on vendor-hosted or frequently updated software faces exactly this problem: skills learned during development silently stop executing after a routine upgrade. The paper's practical claim — that reranking candidate actions with current-page feasibility evidence improves transfer while the skill library stays frozen — is directly applicable to deployed executors, since it avoids the cost and risk of relearning skills in production.

Future Directions

• Broadening environment coverage. The authors note that SkillShift-Bench focuses on self-hosted same-site evolution over representative web systems, leaving broader website coverage to future work.
• Smaller and more resource-constrained models. Experiments mainly use relatively capable LLM-based agents to reduce confounding from basic instruction-following or tool-use failures; the authors call for studying smaller models.
• Multilingual, mobile, and accessibility-oriented settings. The current benchmark focuses on English desktop web interactions, and the authors identify these as natural extensions.
• Relearning versus test-time adaptation. The paper contrasts executor-side adaptation with relearning the library in the target environment (Appendix E.7); a fuller characterization of when each route pays off remains open. Separately, the informal regret guarantee relies on an oracle-tuned fixed window chosen before the run as a deterministic function of the variation budget — how to set that window in practice is not resolved here.

Target Audience

Researchers and practitioners working on LLM-based web agents, agent skill/procedure learning, and browser automation evaluation. It is most useful for those designing benchmarks for robustness or experience transfer, and for engineers building production browser agents or RPA systems who need to keep learned procedures working across site updates. Readers without an online-learning background can skip Section 4.1 and still follow the benchmark design and empirical results; those interested in the theory will find the nonstationary-MDP formulation and regret analysis in Section 4.1 and Appendix C.

Note: the provided content is truncated partway through Appendix B.1, so details beyond environment selection and version pairing (including several appendix sections referenced in the text) are not reported in the material available.

Authors’ abstract

Skill learning enables web agents to reuse prior experience for long-horizon interactive tasks. However, learned skills are typically evaluated in closed environments, overlooking the fact that real-world web deployment involves continuous shifts in invocation context, perceptual grounding, and execution feasibility. To this end, we introduce SkillShift-Bench, the first benchmark for evaluating skill learning with controlled open-environment shifts. SkillShift-Bench simulates Contextual Shift, Perceptual Shift, and Execution Shift across three self-hosted web systems, and evaluates agents with diagnostics covering task success, interaction cost, skill use, and skill failure. Comprehensive experiments reveal systematic robustness degradation under controlled shifts, characterized by lower success rates, higher interaction costs, and more frequent skill failures, with Execution Shift exerting the strongest pressure. We further formulate shifted skill execution as a nonstationary local executability problem and provide both a dynamic-regret analysis and a practical test-time adaptation method, demonstrating the feasibility of improving learned-skill execution without relearning the skill library. Code, tasks, environments, documentation, and the leaderboard are available at https://skillshift-bench.github.io/.