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

arXiv 2606.22948 ↗First posted 22 Jun 2026cs.AI cs.CVcited by 0

On the map: LLM agents and tool use → GUI and mobile agents

Abstract (arXiv)

As multimodal agents move from interface understanding to real software control, successful trajectory discovery in live desktop environments becomes a key challenge. GUI tasks require long-horizon sequences of precise mouse and keyboard actions, while feedback is sparse, delayed, and costly to obtain through VM rollouts. We propose Environment-Native Verified Search (ENVS), a training-time search-and-filter pipeline that uses the environment to construct verified supervision before policy optimization: it branches over behaviorally distinct GUI actions in live OSWorld VMs, verifies successful leaves, and trains from globally balanced step-level supervision. To evaluate robustness under realistic desktop interruptions, we also introduce OSWorld-Noisy, a dynamic benchmark for recoverable desktop interruptions that preserves the original tasks while testing whether agents can refocus, dismiss, wait, or recover under live perturbations. On the 300-task OSWorld pool, ENVS reaches 30.3 pass@8 on original evaluations and 29.0 on OSWorld-Noisy, outperforming matched ARPO-style online RL while reducing compute from 184-192 to 138-153 GPU-hours; even with only 30% of its search data, ENVS reaches 27.0 pass@8, exceeding ARPO from the base model. Training from noisy environments also better preserves visual-reasoning abilities on auxiliary benchmarks, including OSWorld-G Refusal (16.7 vs. 1.9) and BLINK Functional Correspondence (26.2 vs. 23.1).

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in GUI and mobile agents, one of 16 directions in LLM agents and tool use. Builds on 22 of its 38 references that are in the map. First posted on arXiv 22 Jun 2026.

Builds on

22 of 38 references.

Closest ancestors · 4

Same direction, newest first

Other references · 18

2017Proximal Policy Optimization Algorithmscited by 14,441
2021Training Verifiers to Solve Math Word Problemscited by 9,743
2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
2023WebArena: A Realistic Web Environment for Building Autonomous Agentscited by 1,908
2017Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real Worldcited by 1,401
2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
2023Mind2Web: Towards a Generalist Agent for the Webcited by 1,210
2019Leveraging Procedural Generation to Benchmark Reinforcement Learningcited by 478
2025The Entropy Mechanism of Reinforcement Learning for Reasoning Language Modelscited by 463
2017Robust Adversarial Reinforcement Learningcited by 439
2020Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Designcited by 260
2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245

6 more

2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 235
2020Prioritized Level Replaycited by 190
2022Evolving Curricula with Regret-Based Environment Designcited by 166
2024Tree Search for Language Model Agentscited by 148
2025SEEA-R1: Tree-Structured Reinforcement Fine-Tuning for Self-Evolving Embodied Agentscited by 15
2019Robust Visual Domain Randomization for Reinforcement Learningcited by 13

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way