Technical Summary: ENVS: Environment-Native Verified Search for Long-Horizon GUI Agents

1. Problem Statement

The paper addresses the challenge of training multimodal agents to control real software through Graphical User Interfaces (GUIs). While foundation models have advanced in interface understanding, executing long-horizon sequences of precise mouse and keyboard actions in live desktop environments remains difficult. The core bottlenecks are:

• Sparse and Delayed Feedback: In environments like OSWORLD, feedback is typically a binary success/failure signal only at the end of a trajectory. A failed trajectory does not reveal which specific intermediate action caused the failure.
• High Cost of Rollouts: Obtaining feedback requires executing actions in live Virtual Machines (VMs), which is computationally expensive and slow.
• Inefficiency of Online RL: Current approaches, such as ARPO (Adaptive Reinforcement Policy Optimization) and tree-search methods like SEEA-R1, often couple trajectory discovery with policy updates. This leads to issues where easy tasks dominate the gradient signal, long trajectories are over-represented, and the global allocation of gradient mass across tasks and trajectory lengths is difficult to control.

2. Methodology: ENVS

The authors propose Environment-Native Verified Search (ENVS), a training-time framework that decouples trajectory discovery from policy optimization. Instead of using online reinforcement learning (RL), ENVS constructs a verified, balanced supervised dataset before training begins.

Core Pipeline

1. Behavioral-Disagreement-Gated Search:
   • The system searches within live OSWORLD VMs using a frozen base policy.
   • At each step, it samples $K$ candidate actions and reduces them to coarse "behavioral fingerprints" (e.g., action type + discretized coordinates or text).
   • Candidates are bucketed by fingerprint. The system explores the top $k$ buckets with the highest agreement (majority actions) while pruning minority actions. This ensures the search focuses on behaviorally distinct paths rather than token noise.
2. VM-Bounded Search:
   • Unlike classical Monte Carlo Tree Search (MCTS) which assumes cheap simulations, ENVS operates in live desktops where revisiting states is costly.
   • It replaces adaptive selection (UCB/PUCT) with explicit cost gates: per-task branch budgets, per-step caps, and hard step cutoffs. It does not use learned value functions.
3. Environment Verification and Filtering:
   • Once a trajectory reaches a leaf node, the OSWORLD task oracle assigns a binary reward ($R(\tau) \in \{0, 1\}$).
   • Failed trajectories are discarded. Successful trajectories are decomposed into per-step supervised examples $(x, o_{\le t}, a_t)$, converting sparse terminal success into dense action-level supervision.
4. Global Balancing of Supervision:
   • The collected dataset is naturally imbalanced (easy tasks yield many successes; hard tasks yield few).
   • ENVS applies a reweighting scheme before training. The weight $w_i$ for task $i$ is calculated as:
     $$w_i = \text{clip}\left(\frac{(1 - SR_i)^\beta}{T_i}, w_{\max}\right)$$
     where $SR_i$ is the search success rate and $T_i$ is the number of steps. This shifts gradient mass toward hard tasks and normalizes for trajectory length, preventing easy tasks from dominating the training signal.

OSWORLD-NOISY Benchmark

To evaluate robustness, the authors introduce OSWORLD-NOISY, a dynamic benchmark injecting recoverable desktop interruptions (e.g., pop-ups, focus changes, background dialogs) during task execution.

• Constraints: Perturbations are "non-sabotage"; they do not touch task-relevant files or deliver input to the target window, ensuring tasks remain solvable.
• Scheduling: During training, noise intensity scales with task success rates (harder tasks receive less noise). Evaluation uses a fixed, deterministic schedule of held-out perturbations.

3. Key Contributions

• ENVS Framework: A search-and-filter pipeline that uses the environment itself to verify successful trajectories, converting them into globally balanced supervised data. This separates discovery from optimization, allowing for explicit control over gradient allocation.
• OSWORLD-NOISY: A new benchmark for testing GUI agent robustness against realistic, recoverable desktop interruptions, preserving original tasks while adding dynamic perturbations.
• Efficiency and Robustness: Demonstrating that verified search can achieve higher accuracy with significantly less compute than online RL, while preserving visual-reasoning capabilities.

4. Experimental Results

Experiments were conducted on a 300-task OSWORLD pool (86 trainable, 214 held-out) using the UI-TARS-1.5-7B base model.

• Clean Performance: ENVS achieved 30.3% pass@8 on clean OSWORLD, outperforming the base model (22.7%) and ARPO (26.7%).
• Noisy Robustness: On OSWORLD-NOISY, ENVS reached 29.0% pass@8, significantly outperforming the base model (20.3%) and noisy ARPO (21.7%). Notably, noisy ARPO degraded on clean tasks, whereas ENVS maintained high performance across both conditions.
• Compute Efficiency: ENVS required 138–153 GPU-hours compared to 184–192 GPU-hours for matched ARPO baselines. This efficiency stems from collecting verified trajectories once and reusing them for Supervised Fine-Tuning (SFT), whereas ARPO requires fresh on-policy rollouts for every training step.
• Data Efficiency: Using only 30% of the collected search data, ENVS reached 27.0% pass@8, matching or exceeding ARPO trained on the full dataset.
• Capability Retention: Training on noisy environments better preserved auxiliary visual-reasoning abilities. For instance, on the OSWORLD-G Refusal benchmark, noisy ENVS scored 16.7% compared to 1.9% for clean ENVS, suggesting that interruptions provide useful supervision for perception and recovery.

5. Significance and Claims

The paper claims that ENVS offers a structural advantage over online RL by decoupling trajectory discovery from policy updates. This allows for:

1. Global Gradient Control: The ability to cap overrepresented easy tasks and upweight rare-success tasks, addressing the "binomial degeneracy" and gradient imbalance inherent in online RL.
2. Entropy Preservation: Unlike online RL which often suffers from entropy collapse (narrowing action distributions), ENVS maintains higher action entropy by training on diverse, verified trajectories, leading to better generalization.
3. Cost-Effective Training: By amortizing expensive environment interactions into a verified dataset, ENVS reduces compute costs while improving performance.
4. Robustness via Interruption: The results suggest that dynamic perturbations are not just a stress test but a source of supervision that helps agents learn to refocus, wait, and recover, without sacrificing clean task completion.

The authors conclude that environment-native training can make agent training cheaper and more reusable, though they note limitations regarding the synthetic nature of the noise and the specific infrastructure requirements (parallel VMs, reliable resets) of the OSWORLD environment.