Why the Screen Deceives
Imagine an agent working with a desktop application. It sees a window with several fields and a "Save" button. From a screenshot's perspective, this is the same screen, but in reality the form may be empty, partially filled, or already submitted — and only the hidden logic of the operating system knows which scenario is currently executing. This situation is called partial observability: the agent has access only to external manifestations, not the true state of the system.
The danger is that a locally plausible action — for example, a click on a button — in one case will complete the scenario, in another will trigger a validation error, and in a third will simply be ignored. Visually similar screens may belong to different branches of the workflow, leading to significantly different outcomes. Therefore, effective behavior requires not only recognizing interface objects but also active exploration: one must determine which states are even reachable and resolve ambiguity before making a decision.
This is precisely the task addressed by the paper "ScreenSearch: Uncertainty-Aware OS Exploration" (arXiv:2605.16024), authored by Michael Solodko and Justin Weigle. They frame the problem as exploring computer states: the agent must balance between expanding the reachable frontier and reducing uncertainty.
Approach: State Graph and Bandit
Instead of relying on individual screenshots, the proposed ScreenSearch system builds a shared graph of deduplicated states. To do this, it uses structural search: UIA trees are converted into features accounting for element layout, and related screens are indexed via sparse token search and metadata filters. The state graph is maintained across multiple virtual machines, allowing exploration to scale.
The strategy for selecting the next action is driven by a PUCT graph bandit that accounts for state ambiguity. This means the agent prioritizes not only transitions promising in terms of novelty but also those that reduce uncertainty. In essence, the system simultaneously explores the state space and refines its knowledge about it.
How to Measure Ambiguity
The key contribution of the work is a scalable ambiguity signal. It is based on a simple observation: if visually similar screens with the same action signature lead to different next states, then the current state is insufficiently understood. The variance of outcomes becomes an indicator that the agent has not yet figured out how this part of the workflow works.
This signal is combined with rewards for expanding the exploration frontier. As a result, it becomes possible to evaluate policies on the shared graph via replay-start: a policy is run from a fixed set of starting states, and its performance on tasks is observed. Importantly, some policies can quickly reduce ambiguity but barely open new states, while others explore actively but fail to "close out" unclear situations. The authors therefore emphasize: simply reducing ambiguity is not a sufficient goal.
Experiments: Diversity and Trade-offs
To validate the approach, 11 desktop applications were used. During the experiments, over a million screenshots and more than 30,000 unique states were collected. The resulting corpora exhibit significant diversity both across applications and within each one — this allows testing agents under realistic conditions.
On a fixed replay-start slice, the trade-off between novelty and ambiguity is clearly visible. Some strategies almost immediately reduce uncertainty levels but rarely discover new states. Others, conversely, quickly expand the boundaries of the known but leave many "gray zones." The authors conclude that the exploration objective must be comprehensive.
Additional ablations revealed an interesting effect: strengthening proposal priors noticeably improves the discovery of unique states during corpus construction. In other words, the completeness of the collected state graph directly depends on how good the action proposals offered to the agent are.
Conclusions
The ScreenSearch study confirms that for reliable agent operation in an operating system, recognizing interface elements well is not enough. What matters more is understanding state identity, generating high-quality action proposals, and being able to search with ambiguity in mind. These three factors determine when to continue exploration and when to finalize the result.
The authors presented a 22-page paper with 8 figures and 21 tables, detailing both the method itself and the experiments. It is a solid foundation for further work in the field of reliable GUI agents.
