When and What to Teach: Budget-Aware Online Adaptation for Web Agents

Jianwei Zhang; Sihan Cao; Pengcheng Zheng; Ya Wen; Pei Ke; Kuien Liu; Shen Gao; Wei Dong; Yang Yang; Chaoning Zhang

Source-linked AI summary

When and What to Teach: Budget-Aware Online Adaptation for Web Agents

Jianwei Zhang, Sihan Cao, Pengcheng Zheng, Ya Wen, Pei Ke, Kuien Liu, Shen Gao, Wei Dong, Yang Yang, Chaoning Zhang

arXiv:2609.05513v1Aug 31, 2026cs.AIcs.CVcs.LG

TL;DR

Web agents need cost-effective online adaptation because static training does not cover evolving deployment environments and proprietary teachers are too expensive. The paper introduces a budget-aware framework that gates teacher queries by solvability and trims trajectories using student scores; experiments retain comparable first-pass success while reducing teacher calls and training compute.

Problem
Static offline training struggles with evolving web environments, while proprietary models are commercially cost-prohibitive, motivating lightweight models that adapt through online teaching.
Method
Score-Guided Online Teaching with Budgeted Trajectory Trimming combines a solvability-aware teacher gate for query timing with score-guided turn selection for retaining informative training segments.
Results
Comparable first-pass success is achieved on MiniWoB and TimeWarp while reducing teacher calls by 22.6% and student training compute by 52.1% on average.
Takeaways & Limitations
Budget-aware selection can reduce wasted supervision from unresolvable queries and redundant trajectory turns while supporting online adaptation of lightweight web-agent models.
Takeaways & Limitations
Evaluation focuses on simulated benchmarks, and the framework has not yet been extended to live websites, multimodal computer-use tasks, or non-English interfaces.

Abstract

from arXiv · show

Web agents have achieved significant success in automating complex internet tasks but deploying them in real-world environments requires continuous online adaptation. Given that deploying powerful proprietary models remains commercially cost-prohibitive, practitioners must rely on lightweight local models that evolve post-deployment via online teaching from a stronger teacher. However, standard interactive feedback imposes prohibitive costs. We show that conventional trajectory-level preference optimization wastes budget on both unresolvable episodes and redundant execution turns. To resolve these inefficiencies, we propose \textbf{Score-Guided Online Teaching with Budgeted Trajectory Trimming}, a budget-aware framework that systematically orchestrates \textbf{when} and \textbf{what} to teach. Specifically, our framework integrates a solvability-aware teacher gate to dictate \textbf{when} to query the teacher model and a score-guided turn selection mechanism to decide \textbf{what} informative turns to retain. Extensive experiments on MiniWoB and TimeWarp demonstrate that our method achieves comparable first-pass success while reducing teacher calls by 22.6\% and student training compute by 52.1\% on average. Our code is available at https://github.com/zjw131f1fc/budgeted-online-teaching.

1 Introduction

The paper frames online web-agent teaching as a budget-allocation problem: decide when teacher supervision is worth requesting and which trajectory turns are worth retaining. Its framework combines solvability-aware query gating with score-guided turn selection, preserving comparable first-pass success while reducing teaching costs.

Online teaching is needed because static offline training struggles with evolving interfaces, stochastic networks, and unseen workflows, while proprietary models are too costly for routine deployment.
Full-trajectory teaching wastes budget by querying on failures the teacher cannot solve and training on redundant actions within otherwise successful rollouts.
22.6% fewer teacher calls and 52.1% lower student training compute are achieved on average while maintaining comparable first-pass success on two online web-agent benchmarks.
The paper formulates teaching as two linked allocation decisions: when to query the teacher and what execution turns to retain for training.
The solvability-aware teacher gate uses historical teacher outcomes to suppress unnecessary queries, while score-guided selection uses student log-probability to reduce redundant training tokens.

2 Related Work

Prior work establishes online adaptation, expert-query selection, and score-based data filtering as relevant foundations, but this paper targets their combination for budgeted web-agent teaching under deployment-time constraints.

Online web-agent adaptation differs from standard online reinforcement learning because the agent is deployed, first-pass success matters on every episode, and teacher supervision has real cost.
Earlier web-agent approaches learn from successful demonstrations or privileged feedback, but some assume unrestricted teacher access or optimize final model quality rather than streaming first-pass success.
Active learning and imitation-learning methods reduce costly expert intervention through safety, novelty, or deviation-based query policies, while commonly assuming unrestricted expert access.
Perplexity, log-probability, hard-example mining, and curriculum methods use model scores to focus training on informative or difficult data, with recent preference learning moving beyond full-response optimization.

3 Method

The method treats online web-agent teaching as budget allocation over teacher-query timing and trajectory-turn selection. It gates teacher queries using historical solvability evidence, then trims matched trajectories to retain turns most informative for preference optimization.

3.1 Problem Formulation: The online setting maximizes first-pass success over a fixed task stream while constraining total teacher queries and student training tokens.Student failures may trigger teacher intervention, producing matched trajectories for student updates.
3.2 Motivation: Unselective teaching wastes budget by querying on failures the teacher cannot solve and training indiscriminately on redundant full trajectories.The framework addresses inefficiency at both episode and turn levels.
3.3 Solvability-Aware Teacher Query Gating: The solvability-aware teacher gate estimates whether a failure is teachable from semantically similar historical teacher outcomes, querying when the estimate exceeds λ.Sparse retrieval evidence overrides the threshold so under-sampled regions remain explorable; the memory adapts to distribution drift.
3.4 Score-Guided Turn Selection: After teacher success, score-guided selection keeps the M lowest-log-probability teacher turns and M highest-log-probability student turns in temporal order.The positive side targets difficult actions, while the negative side targets errors the current policy is prone to repeat.
3.5 Trimmed Trajectory-Level Preference Optimization: The trimmed trajectory pair supports trajectory-level preference optimization using either DPO with a reference policy or SimPO without one.Both objectives use the same trimmed pair, and the query gate and turn selection are independent of the objective choice.

4 Experiments

Experiments evaluate online teaching on fixed MiniWoB and TimeWarp streams, measuring first-pass success alongside teacher and student budgets. Across carriers and settings, query gating and turn trimming reduce resource use while preserving broadly comparable success, with the gate favoring failures more likely to yield usable supervision.

Experimental setup: Experiments use fixed-order streams of 125 MiniWoB and 150 TimeWarp episodes, enabling controlled comparisons of online learning behavior.MiniWoB covers common web interactions, while TimeWarp contains longer, more heterogeneous tasks.
Experimental setup: The evaluation reports first-pass success, teacher calls, failed positive resolutions, updates, and Student Total PFLOPs.Student PFLOPs include training and positive-side scoring overhead under a dense-equivalent accounting assumption.
Main results: Full-trajectory preference optimization outperforms Naive SFT on both benchmarks, with SimPO reaching 44.5±1.5/125 on MiniWoB and 50.0±3.0/150 on TimeWarp.Naive SFT reaches 29.0±1.0/125 and 17.0±2.0/150, respectively.
Main results: 22.6% fewer teacher calls and 52.1% lower student compute occur on average across four same-carrier comparisons.The comparisons cover gated and trimmed variants against full-trajectory DPO and SimPO on MiniWoB and TimeWarp.
Query efficiency: The query gate reaches 20 oracle-positive hits in 45 queries versus 56.6 for random ordering, a 20.5% reduction.It uses fewer queries than random ordering at all 35 reachable hit targets, including 84 versus 95.9 queries at 35 hits.
Turn selection ablation: Negative-side trimming reduces student PFLOPs by 36% while changing success from 38/125 to 40/125, and trimming both sides yields a 41% overall saving.Positive-side trimming contributes less on MiniWoB because teacher trajectories average about three turns.
Sensitivity analyses: Gate threshold perturbations preserve the advantage over random selection, with oracle-hit gains ranging from +2.5 to +5.9 at the same query budget.The default setting records 35 hits with 85 queries versus 31.1 expected random hits.
Sensitivity analyses: Across turn budgets, trimmed configurations match or exceed the untrimmed reference at substantially lower student PFLOPs.Different turn budgets can also alter subsequent policy evolution, failure distributions, and total training volume.

5 Conclusion

The work addresses online teaching for web agents under realistic budget constraints by combining query filtering with selective trajectory training. On MiniWoB and TimeWarp, the framework achieves comparable or superior online success while reducing teacher calls and student training compute.

The framework targets online teaching for web agents when proprietary models are commercially cost-prohibitive.
It combines a solvability-aware teacher gate with score-guided turn selection to filter queries and retain informative execution segments.
22.6% fewer teacher calls and 52.1% lower student training compute were achieved on average across MiniWoB and TimeWarp.
The framework achieved comparable or superior online success compared with trajectory-level DPO.

Limitations

The evaluation is limited to simulated web-agent benchmarks and uses fixed modeling choices for retrieval, turn scoring, and teacher configuration. The authors identify live and multimodal environments, domain-adapted embeddings, richer selection signals, and multiple teachers as future directions.

The evaluation focuses on simulated web-agent benchmarks rather than live websites, multimodal computer-use tasks, or non-English interfaces.
The teacher gate uses a standard text-embedding model, which may be less suitable for environments with highly heterogeneous page structures.
Turn selection relies solely on student log-probability, although state novelty or action diversity could provide additional signals.
The framework assumes a single fixed teacher model, leaving multi-teacher and self-improving teacher configurations unexplored.
The implementation uses the standard AgentLab and BrowserGym setup, including default observation, action, and prompt configurations.

B Full Hyperparameter and Gate Configuration

The appendix specifies training objectives, optimizer settings, teacher-gate parameters, and turn-selection budgets used in the experiments. These configurations differ between MiniWoB and TimeWarp where sequence lengths, learning rates, thresholds, and retained-turn budgets require separate settings.

LoRA and Training Objectives: All methods fine-tune the student with LoRA using rank 16, scaling 32, dropout 0.05, and the listed projection modules.
LoRA and Training Objectives: DPO uses β = 0.1 with an explicit reference model, while SimPO uses β = 2.0 and γ = 0.5 without a reference model.
Optimizer: Maximum sequence lengths are 4,000 tokens for MiniWoB and 7,000 tokens for TimeWarp.
Teacher Gate: The teacher memory retrieves k = 10 neighbors with similarity bandwidth κ = 0.16 and dataset-specific solvability and exploration thresholds.
Turn Selection: Turn budgets retain the top 3 turns per side on MiniWoB and the top 4 turns per side on TimeWarp; negative-side scoring adds no cost.

C Full Trimmed Trajectory Pairs

The appendix presents full teacher-positive and student-failure trajectory pairs together with the turns selected by score-guided turn selection. Selection ranks turns differently on positive and negative sides before retaining the highest-scoring top-M turns.

The appendix shows teacher-positive and student-failure trajectories alongside the turns selected on each side.
Positive-side scoring ranks turns by lowest student log-probability, identifying turns the student finds most difficult.
Negative-side scoring ranks failure turns by highest student log-probability, targeting failures the student is most likely to repeat.
The method retains the top M turns by score on each side, with M = 3 for MiniWoB and M = 4 for TimeWarp.

C.1 Example A: use-autocomplete-nodelay (MiniWoB)

In the autocomplete task, turn selection retains the interaction that exposes the student's corrective behavior while discarding a routine action already handled correctly.

Selection retains the autocomplete trigger and subsequent text edit, while dropping the trailing submit click the student already handles correctly.

C.2 Example B: Multi-hop Search (TimeWarp)

In the multi-hop search task, selection preserves the student's navigation errors and the teacher trajectory's cross-article reasoning chain while removing routine actions. The examples illustrate why informative turns can occur inside, rather than only at the end of, trajectories.

C.2 Example B: Multi-hop Search (TimeWarp): The intended chain searches Utah, opens the fourth result, identifies New Orleans, searches it, and reports Texas from another fourth result.
C.2 Example B: Multi-hop Search (TimeWarp): Teacher-positive selection drops routine search-box and Go actions while retaining the cross-article jumps, intermediate query, and final answer.
C.2 Example B: Multi-hop Search (TimeWarp): Positive-side selection extracts the corrective subroutine, whereas negative-side selection isolates the divergence pattern the student is most likely to repeat.
C.2 Example B: Multi-hop Search (TimeWarp): A positional heuristic that keeps only recent turns cannot reproduce these selections because the informative segments are interior in both trajectories.
C.2 Example B: Multi-hop Search (TimeWarp): Student-failure selection retains the Sci/Tech divergence, unrelated article, and misplaced New Orleans search while dropping the closing incomplete-task message.
D PFLOPs Accounting: Student Total PFLOPs add objective-dependent training cost to positive-side scoring cost when score-guided turn selection is used.The accounting uses c_obj · P · N_train + 2 · P · N+ for methods with turn selection.

E Compute, Artifacts, and Responsible NLP

The experiments colocate student rollout and LoRA fine-tuning on RTX 4090 GPUs while reporting artifact-derived Student PFLOPs. The study uses named open and API-accessed models, environments, and benchmarks under their stated research-use terms.

E Compute, Artifacts, and Responsible NLP: Experiments colocate student rollout through vLLM and LoRA fine-tuning on one NVIDIA GeForce RTX 4090 GPU, with DPO's reference model on CPU.
E Compute, Artifacts, and Responsible NLP: Student PFLOPs are reported from exported artifacts rather than as an aggregate GPU-hour estimate.
E Compute, Artifacts, and Responsible NLP: Qwen2.5-3B-Instruct is the student model, GPT-4o is the teacher model, and text-embedding-3-small supplies semantic task embeddings for the teacher gate.
E Compute, Artifacts, and Responsible NLP: BrowserGym and AgentLab provide the web-agent interface, while MiniWoB and TimeWarp serve as evaluation benchmarks.
E Compute, Artifacts, and Responsible NLP: The artifacts are used within their intended research-use terms and are not redistributed.

F Data and Privacy

The study uses published synthetic or curated web-interaction benchmarks without collecting new user data or including personally identifying information about end users. Deployment to live websites is outside the paper's scope and would require additional safety considerations.

F Data and Privacy: MiniWoB and TimeWarp are used as published synthetic or curated web-interaction tasks, without modification or newly collected user data.
F Data and Privacy: The benchmark tasks do not contain personally identifying information about end users.
F Data and Privacy: The method targets controlled benchmark environments rather than human-subject research, harmful-content generation, or live web-service deployment.
F Data and Privacy: Deploying derivatives on real websites would require rate limiting, action whitelisting, and error monitoring, which are out of scope.