Choosing Which Mistakes to Correct: Submodular Selection of Drifted States for Training Multimodal Agents

Computer-use agents fail over long tasks for a simple arithmetic reason. If each step succeeds 95% of the time, a 20-step task succeeds only about a third of the time. Much of this per-step failure comes from states the agent was never trained on: screens it reached through its own earlier mistakes. A recent fix lets the student agent act for a while, then asks a stronger teacher to take over for a few short steps from wherever the student ended up. The student then trains on those recovery snippets. Current implementations choose these hand-off points at random. When teacher calls are expensive, most of the budget goes to near-duplicate situations, such as the hundredth copy of "wrong tab is open," while rare failures that ruin whole tasks go uncorrected.

We propose to treat the choice of hand-off points as a budgeted coverage problem. The student generates a large pool of candidate states it drifted into. We pick a small subset of them to send to the teacher by maximizing a submodular objective, meaning a set score with diminishing returns, so each new pick counts for less if it resembles states already chosen. The objective measures similarity in the student's own internal representation, weighted by how unsure the student is at each state. The corrected snippets serve as a supervised warm-start before reinforcement learning (RL). The claim to test is concrete. At a fixed teacher budget, covering the student's failure space beats sampling it uniformly, and the advantage persists after RL rather than showing up only in post-fine-tuning accuracy.

Core Claim

The closest work is A Few Teacher Steps Go a Long Way (OP-SHORT). It frames agent post-training as a budget split between teacher inference cost and training cost. The student rolls in for a random number of steps, a teacher continues for $K$ steps, and all snippets are kept without outcome filtering. On Terminal-Bench-Dev, this approach with 10% of the behavioral-cloning data matched a baseline that used 100% of the data plus a separate RL stage. That result motivates the proposal, since correcting student-induced states is what matters. It also constrains the design. OP-SHORT found that filtering by outcome wastes teacher budget, so our selection must happen before the teacher is queried and must use only signals the student produces cheaply. OP-SHORT decides where to intervene at random. We make that decision the object of study.

The selection method comes from coreset work. PaCS-ICL selects few-shot prompt examples by trading off density-based representativeness against diversity from a determinantal point process (a model that favors sets of dissimilar points). It reports a 3.2 to 3.6 point accuracy gain over IDEAL, RDSS and InfoMax at an 18-example budget. Talisman uses submodular mutual information to mine rare target slices. Both operate on fixed, static pools embedded with frozen encoders. Our pool is different. It is regenerated by the policy being trained, it consists of multi-step multimodal states rather than single prompts, and it is selected for teacher labeling rather than for use as prompts.

The multimodal direction explains why the representation matters. MATH-Vision attributes 42.2% of GPT-4V errors to reasoning that follows correct perception, against 31.9% to recognition errors. Plot Twist shows models solving hard chart questions while failing simple perceptual probes. For agents, two screenshots that look the same to CLIP can hide different failures. In one, the agent misread the button. In the other, it read the button correctly but planned the wrong step. A coverage objective over screenshot embeddings would treat these as one state. An objective over the student's own decision-time features should separate them. This representation choice is the key hypothesis, and one ablation isolates it.

Formally, let $V$ be the pool of drifted states, $\phi(v)$ the student's pooled hidden state at the action-emission position for state $v$, and $u_v$ the student's disagreement across $m$ sampled actions at $v$ (the fraction of samples that differ from the modal action). We select $S \subseteq V$ with $|S| \le B$ to maximize

$$F(S) = \sum_{v \in V} u_v \max_{s \in S} \mathrm{sim}(\phi(v), \phi(s)),$$

which is an uncertainty-weighted facility location objective. It rewards picks that are similar to many uncertain states and gives little credit for a second pick near an already-covered region. $F$ is monotone submodular, so greedy selection achieves at least $(1-1/e)$ of the optimum, the standard guarantee cited via Multi-document Summarization via Budgeted Maximization of Submodular Functions and implemented in apricot. Nothing in the pipeline depends on the teacher before selection.

Research Program

The pipeline has four stages. First, a base vision-language agent is warm-started by behavioral cloning on expert trajectories. Second, the student rolls out on training tasks, and states are logged at random cutoffs, as in OP-SHORT, to form the pool $V$. Each logged state carries the screenshot, the history, $\phi(v)$ and $u_v$. Third, greedy maximization of $F$ picks $B$ states, and the teacher writes $K=3$ continuation steps from each. OP-SHORT found $K=3$ better than $K=5$ on HotpotQA, and short continuations also avoid the verbosity problem documented by The Synergy Dilemma of Long-CoT SFT and RL, where long reasoning traces inflated output length up to tenfold and hurt simple perception. Fourth, the student is fine-tuned on the mixture of expert and correction data and then trained with GRPO (group relative policy optimization, an RL method that compares sampled responses within a group) against execution-based rewards. For this stage we use the ComputerRL codebase.

The selection may be repeated for two or three rounds as the student changes. This is the "non-stationary pool" setting that the coreset literature has not addressed.

We treat post-RL success as the primary outcome and post-fine-tuning accuracy as secondary. Quagmires in SFT-RL Post-Training showed, over roughly 1M GPU hours of text math, that post-fine-tuning Pass@1 can be uncorrelated or even anticorrelated with post-RL results. It recommends held-out generalization loss and Pass@large-$k$ as proxies. We report those proxies and test whether they predict which selection method wins after RL in the agent setting. That extends their finding beyond text math.

We also run an analytic study. On 300 sampled drifted states per method, annotators label the failure as perceptual (wrong element or misread content) or procedural (right perception, wrong plan). We compare the failure-type distributions covered by each selector against the distribution in the full pool, and against the failures that remain after training.

Baselines

The naive reference is the behavioral-cloning agent with no correction data, followed by the same GRPO stage. On VisualAgentBench, VisualAgentBench reports InternVL-2 (8B) reaching a 16.0% average success after fine-tuning on its 4,482 trajectories, up from near zero. We reproduce that number before building on it. A second naive point spends the correction budget on additional full expert trajectories instead of snippets, matched in teacher-generated steps. This checks whether correction data is needed at all.

The strongest direct competitor is OP-SHORT-style uniform selection. It uses the same pool, the same teacher, the same $K$, the same budget $B$, and the same fine-tuning and GRPO recipe, but picks states uniformly at random. OP-SHORT is strongest because it already exploits student-induced states and has shown large data-efficiency gains. The only thing we change is which states are chosen. No reported result was found on Lacuna for OP-SHORT on multimodal GUI benchmarks, so we run it ourselves, with three seeds per budget. Beating it means higher post-RL task success at small and medium budgets (for example 5% and 20% of the pool) with non-overlapping seed intervals. We expect the gap to shrink toward zero at full budget, where every method selects everything.

For the RL stage on real desktops, the strongest reported system is BEPA. It raises UITARS1.5-7B on OSWorld-Verified from 22.87% to 32.13%, and from 5.74% to 10.30% on the held-out split. It does this with self-rolled plans and a cache of successful rollouts during GRPO. BEPA acts during RL and our method acts before RL, so the two can be combined. We therefore report our warm-start with and without BEPA's cache. Beating BEPA's 32.13% is not required. A gain on top of BEPA, especially on the held-out split, would count as a strong result.

Three ablations isolate the ingredients. The first keeps facility location but replaces $\phi$ with frozen CLIP screenshot embeddings, which tests the representation claim. The second sets $u_v = 1$ to remove uncertainty weighting. The third drops coverage and takes the top-$B$ states by $u_v$ alone. All variants share the same budget, fine-tuning hyperparameters (tuned once on the uniform baseline and then frozen), and number of GRPO steps.

Why not just…?

Why not just pick the states where the student is most uncertain? This is the simplest active-learning answer, and it is a real threat, since uncertainty alone might carry most of the signal. The worry is redundancy: a single confusing dialog can generate hundreds of high-uncertainty states that all receive the same correction. The top-$B$-by-$u_v$ ablation settles this directly. If it matches the full objective at every budget, we will report that coverage adds nothing, and the contribution reduces to cheap uncertainty-guided roll-in.

Why not just cluster screenshots and sample per cluster? k-means on CLIP features is the cheap version of coverage. PaCS-ICL found that static geometric baselines trail adaptive submodular selection under tight budgets. That evidence comes from text classification, however, not from agents. More importantly, the MATH-Vision error split and the Plot Twist results suggest that visual similarity does not match failure similarity. The CLIP-embedding ablation tests exactly this. If CLIP coverage matches student-feature coverage, the representation hypothesis is wrong.

Why not just scale expert demonstrations? OSWorld reports open models at 0 to 3% without trajectory training. GUI Exploration Lab shows fine-tuned agents memorizing paths and breaking at depths of 5 to 7 steps, with multi-turn RL reaching 17.47% Pass@1 against 14.30% for fine-tuning alone. OP-SHORT shows that pure behavioral cloning loses to on-policy correction at matched budgets. The matched "more full trajectories" baseline checks whether this holds for multimodal agents.

Why not just search at test time with a process reward model? GuidNav scores $k$ candidate actions per step with CogVLM2, lifting dynamic AitW success from 40.3% to 58.1%. This costs an extra model call over several candidates at every step, and it cannot undo irreversible actions on a live system. The two approaches are complementary. We report deployment cost per task and also test whether our trained agent still benefits from GuidNav-style reranking. If reranking erases our gain, that would indicate training-time correction and test-time search fix the same errors.

Proposed Experiments and Decisive Checks

The main testbed is VAB-WebArena-Lite and VAB-Mobile from the VisualAgentBench codebase, with InternVL-2 (8B) as the student. For transfer we use OSWorld-Verified with UITARS1.5-7B, so our results sit next to BEPA's reported numbers.

Teacher quality is a real confound. GPT-4o averages only 36.2% on VisualAgentBench, so some of its continuations will be wrong. We therefore also log how often teacher snippets execute validly, and we check that selection does not merely steer toward states the teacher happens to handle well.

The first decisive check is the budget curve. Post-RL success for the full objective versus uniform selection at 5%, 10%, 20%, 50% and 100% of the pool should show a gap that is largest at small budgets and closes at 100%. A gap that stays constant would suggest a confound rather than a coverage effect.

The second check fits the product rule. We estimate per-step success as a function of step index and ask whether the gain concentrates in later steps, where drifted states live. This would show that the method reduces compounding errors specifically, rather than improving first-step grounding.

The third check tests whether Pass@large-$k$ and held-out loss after fine-tuning rank the selectors in the same order as post-RL success, extending the Quagmires finding beyond text math.

The fourth check uses the annotated failure-type study. The student-feature selector should cover procedural failures that the CLIP selector under-samples, and those failure types should shrink most after training.

A clean negative on all four checks would still be informative. It would say that for multimodal agents, where the student fails matters less than how often it is corrected.