Organizations: University of Electronic Science and Technology of China · Institute of Software Chinese Academy of Sciences · Xi’an University of Architecture and Technology
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 Score-Guided Online Teaching with Budgeted Trajectory Trimming, a budget-aware framework that systematically orchestrates when and what to teach. Specifically, our framework integrates a solvability-aware teacher gate to dictate when to query the teacher model and a score-guided turn selection mechanism to decide 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.
Figures & tables
Figure 1: Overview of Score-Guided Online Teaching with Budgeted Trajectory Trimming. The framework first utilizes a solvability-aware teacher gate to decide whether a student failure warrants a teacher query. It then applies a score-guided turn selection mechanism to trim the resulting matched trajectory pair using the student log-probability before performing a trajectory-level preference optimization update.
Method
Success
%T
Upd.
Student PFLOPs
T. Calls
MiniWoB (125 episodes, teacher ceiling 84/125)
Baseline Student
30/125
35.72%
0
–
–
Teacher (GPT-4o)
84/125
100%
0
–
–
Naive SFT
29 ± 1.0/125
34.52 ± 1.19%
53 ± 2.0
6.22 ± 0.49
95 ± 2.0
Trajectory DPO
37.5 ± 1.5/125
44.65 ± 1.79%
44.5 ± 2.5
16.66 ± 1.23
87 ± 1.0
+ Query Gate
38.0 ± 1.0/125
45.24 ± 1.19%
42.0 ± 1.0
14.37 ± 0.45
70.5 ± 1.5
Table 1: Main results on MiniWoB (125-episode stream) and TimeWarp (150-episode stream). %T = success as a percentage of teacher success. Upd. = student updates triggered. Student PFLOPs = training plus positive-side scoring overhead. T. Calls = teacher calls. “–” = no training cost.
Method
T. Calls
Failed Res.
Upd.
Trajectory DPO
87
41
46
+ Query Gate
70
29
41
+ Query Gate + Turn Sel.
66
28
38
Table 2: MiniWoB teacher-side statistics on the DPO carrier. T. Calls = teacher calls, Failed Res. = teacher calls that did not produce an acceptable matched-positive trajectory, Upd. = number of student updates triggered.
Figure 2: Teacher queries required to reach each oracle-positive hit target on the TimeWarp offline replay stream. The solvability-aware teacher gate uses fewer queries than random ordering at every reachable target; the random curve is averaged over 128 seeds.
Method
Success
Student PFLOPs
Δ PFLOPs
T. Calls
No Trim
38/125
14.37
–
70
Trim Pos Only
37/125
13.25
− 8%
67
Trim Neg Only
40/125
9.13
− 36%
65
Trim Both
40/125
8.45
− 41%
65
Table 3: Turn selection ablation on MiniWoB (DPO carrier, top-3/side). All variants include the query gate. Student PFLOPs = Student Total PFLOPs.
(λ,εexp)
Queries
Gate Hits
Random Hits
Δ Hits
(0.25, 0.50)
92
36
33.5
+2.5
(0.30, 0.50) †
85
35
31.1
+3.9
(0.35, 0.50)
79
35
29.1
+5.9
(0.30, 0.40)
83
35
30.6
+4.4
(0.30, 0.60)
88
36
32.1
+3.9
Table 4: Gate threshold sensitivity on the TimeWarp offline replay stream constructed from the completed DPO+Gate run. Random Hits is the expected number of teacher-positive oracle hits for a random gate at the same query budget, averaged over 128 seeds. † denotes the default TimeWarp setting.
Method
Success
Student PFLOPs
T. Calls
top-2/side
38/125
5.17
63
top-3/side
40/125
8.45
65
top-4/side
41/125
9.84
61
Full Trajectory
38/125
14.37
70
Table 5: Turn budget sensitivity on MiniWoB (DPO carrier). Student PFLOPs = Student Total PFLOPs.
β
Success
Student PFLOPs
T. Calls
0.05
39/125
8.70
65
0.1 †
40/125
8.45
65
0.2
39/125
8.35
63
0.5
42/125
9.23
64
Table 6: Sensitivity to the preference-optimization coefficient β on MiniWoB (full method, DPO carrier, top-3/side). † = default setting. Student PFLOPs = Student Total PFLOPs.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
#
Action
Score
Sel.
0
fill(’17’, ’Gua’, auto=T)
0.702
✓
1
click(’24’) ( Guam )
0.065
✓
2
fill(’17’, ’Guaguam’)
1.000
✓
3
click(’18’) ( Submit )
0.000
–
Appendix
Table 7: Teacher-positive trajectory for use-autocomplete-nodelay . Selection retains the autocomplete-trigger and the subsequent text edit, dropping the trailing submit click that the student already handles correctly.
#
Action
Score
Sel.
0
fill(’17’, ’Gua’)
0.389
–
1
click(’18’) (premature submit)
0.868
✓
2
fill(’17’, ’’)
0.578
–
3
fill(’17’, ’Guat’)
0.405
–
4
click(’18’) (premature submit)
1.000
✓
5
fill(’17’, ’Guama’)
0.176
–
Appendix
Table 8: Student-failure trajectory for use-autocomplete-nodelay . Selection retains two premature submits and the malformed final string Guamau , which together capture the failure modes the student is most likely to repeat.
#
Action
Score
Sel.
0
fill(’257’, ’Utah’)
0.000
–
1
click(’258’) ( Go )
0.034
–
2
click(’132’) open Utah result
0.047
✓
3
fill(’151’, ’New Orleans’)
0.395
✓
4
click(’152’) ( Go )
0.000
–
5
click(’132’) open New Orleans result
0.931
✓
Appendix
Table 9: Teacher-positive trajectory for the multi-hop search task. Selection drops the initial search-box fill and both routine Go clicks, while retaining the two cross-article jumps, the intermediate New Orleans query, and the final answer, which together form the actual reasoning chain of the task.
#
Action
Score
Sel.
0
click(’48’) enter Sci/Tech
0.515
✓
1
click(’48’) re-enter Sci/Tech
1.000
✓
2
click(’105’) unrelated tech article
0.453
✓
3
fill(’150’, ’New Orleans’) in wrong context
0.134
✓
4
send_msg_to_user("Incomplete task: ...")
0.000
–
Appendix
Table 10: Student-failure trajectory for the multi-hop search task. Selection retains the diverging navigation into Sci/Tech , the unrelated tech article, and the misplaced New Orleans search, while dropping the closing “incomplete task” message.