ScreenSearch: Uncertainty-Aware OS Exploration

# ScreenSearch: Uncertainty-Aware OS Exploration
Source: [https://arxiv.org/html/2605.16024](https://arxiv.org/html/2605.16024)
###### Abstract

Desktop GUI agents operate under partial observability: visually similar screens can correspond to different underlying workflow states, so locally plausible actions can lead to sharply different outcomes\. We frame this as a problem of computer/OS state exploration, where effective behavior requires both expanding the reachable frontier and reducing ambiguity before committing\. We presentScreenSearch, a system that combines structural screen retrieval and deduplication with an ambiguity\-aware PUCT graph\-bandit for large\-scale desktop exploration\. The retrieval layer converts UIA trees into location\-aware structural features, indexes related screens through sparse token search and metadata filters, and maintains a shared deduplicated state graph across VM workers\. On top of this graph, we define a scalable ambiguity signal based on matched\-action outcome dispersion\. If similar screens produce different next states under the same action signature, the state should be probed further rather than treated as resolved\. We use this signal together with frontier rewards to drive large\-scale exploration and replay\-start policy evaluation over the shared graph\. Across 11 desktop applications,ScreenSearchcollects over 1M screenshots and over 30K deduplicated states, yielding large exploration corpora with substantial cross\-application and within\-application diversity\. On a fixed replay\-start slice, we observe a clear novelty–ambiguity trade\-off: some policies reduce ambiguity quickly while discovering little frontier\. Ambiguity reduction alone is therefore not a sufficient exploration objective\. Appendix ablations show that stronger proposal priors can materially improve unique\-state discovery during corpus building\. These results suggest that state identity, proposal quality, and ambiguity\-aware search all matter when deciding when to probe and when to commit\.

## 1Introduction

Desktop GUI agents often encounter visually similar screens that correspond to different underlying workflow states\. Small hidden differences in permissions, authentication context, application mode, or asynchronous state can therefore make a locally plausible action lead to a sharply different outcome\. The practical failure mode is premature commitment: acting as if the screen is fully resolved when it is not\.

We study this setting through*computer/OS state exploration*, with two complementary objectives\.*Screen novelty*expands the reachable frontier by revealing previously unseen deduplicated states or transitions in the global state graph\.*Screen ambiguity*reduces uncertainty when visually similar observations admit different futures\. Optimizing only novelty can reward superficial UI change, while optimizing only ambiguity can become overly local\. Effective exploration requires both: expanding the frontier and distinguishing among competing hypotheses about the current state\.

We introduceScreenSearch, a system for ambiguity\-aware desktop exploration centered on two ideas: reusable screen identity via structural retrieval and deduplication, and search over that shared state graph using an ambiguity signal derived from matched\-action outcome dispersion\. The retrieval layer converts raw UIA trees into location\-aware structural representations, retrieves near\-duplicate states with sparse token search plus metadata filters, and maintains a global deduplicated state graph across VM workers\. If similar\-looking screens lead to many distinct futures under the same action signature, the current observation is aliased and warrants further probing\.

Exploration then uses an uncertainty\-guided PUCT graph\-bandit over the shared graph, where one\-step PUCT action selection favors signatures with high accumulated exploration utility and plausible local priors\. This utility combines graph frontier expansion and ambiguity reduction\. These trajectories also support simple proposal priors, but the focus here is the exploration problem itself: how shared state identity, ambiguity estimation, and search interact to decide when to keep probing versus when to commit\. As the indexed state set grows, ambiguity estimates sharpen, counterfactual evidence accumulates, and exploration decisions improve under partial observability\.

Our contributions are:

- •We introduce a partial\-observability framing of desktop GUI exploration in which useful behavior requires both frontier expansion and ambiguity reduction\.
- •We propose a scalable ambiguity score based on matched\-action outcome dispersion over deduplicated screen clusters\.
- •We develop an ambiguity\-aware exploration pipeline that combines structural screen retrieval, bounded near\-duplicate verification, and a distributed PUCT graph\-bandit over a shared deduplicated state graph\.
- •We show through replay\-start diagnostics and exploration\-scale ablations that proposal quality and ambiguity\-aware exploration interact non\-trivially: direct ambiguity reduction need not translate into frontier growth, while stronger proposal priors improve discovery efficiency during corpus building\.

## 2Related work

#### Interactive web and OS agents\.

Recent benchmarks evaluate language\-guided agents on increasingly realistic environments, from programmatic web interfaces to full computer settings spanning many applications\(Liuet al\.,[2018](https://arxiv.org/html/2605.16024#bib.bib15), Denget al\.,[2023](https://arxiv.org/html/2605.16024#bib.bib14), Zhouet al\.,[2024b](https://arxiv.org/html/2605.16024#bib.bib13), Xieet al\.,[2024](https://arxiv.org/html/2605.16024#bib.bib57)\)\. They highlight persistent brittleness under long horizons, UI variability, and real execution constraints\. Our setting instead focuses on large\-scale desktop exploration, where the system must build reusable state identity, retrieve related screens, and collect informative traces over the same evolving state graph\.

#### Perceptual aliasing, active sensing, and partial observability\.

Our framing follows the classic observation that immediate perceptual input may be insufficient for safe action selection\. In reinforcement learning this appears as*perceptual aliasing*\(Chrisman,[1992](https://arxiv.org/html/2605.16024#bib.bib318)\); in robotics and planning, related ideas appear as active sensing and active perception, where actions are used to gather informative evidence before commitment\(Veiga and Renoux,[2023](https://arxiv.org/html/2605.16024#bib.bib319), Bajcsyet al\.,[2018](https://arxiv.org/html/2605.16024#bib.bib320)\)\. POMDP methods such as POMCP formalize this challenge with explicit belief\-state planning\(Silver and Veness,[2010](https://arxiv.org/html/2605.16024#bib.bib321)\)\. We adopt the same motivation, but replace explicit Bayesian updates with a scalable structural proxy for GUI ambiguity based on matched\-action outcome dispersion over deduplicated screen states\.

#### Exploration and search under intrinsic objectives\.

A large body of work studies exploration using intrinsic objectives such as prediction error, state novelty, visitation bonuses, uncertainty, or learned world models\(Pathaket al\.,[2017](https://arxiv.org/html/2605.16024#bib.bib316), Burdaet al\.,[2019](https://arxiv.org/html/2605.16024#bib.bib317), Sekaret al\.,[2020](https://arxiv.org/html/2605.16024#bib.bib322)\)\. As in this literature, we treat exploration as a first\-class signal\. But in desktop GUIs, visually similar observations can conceal meaningfully different workflow states, so novelty alone is not enough\. An agent must also know when to keep probing instead of committing\. Our ambiguity score complements frontier\-seeking objectives, and our PUCT graph\-bandit instantiation follows the same PUCT\-style search family used in AlphaZero\-style planners while using one\-step online selection in a simulator\-backed GUI environment rather than multi\-step rollouts through a learned latent dynamics model\(Silveret al\.,[2017](https://arxiv.org/html/2605.16024#bib.bib20),[2018](https://arxiv.org/html/2605.16024#bib.bib21), Schrittwieseret al\.,[2019](https://arxiv.org/html/2605.16024#bib.bib323)\)\.

#### Stepwise agents, deliberate search, and retrieval\-based memory\.

Many language agents interleave short\-horizon reasoning and action selection, often greedily conditioned on the current observation and short context\(Yaoet al\.,[2023](https://arxiv.org/html/2605.16024#bib.bib22)\)\. Reactive replanning, reflection, and deliberate search variants improve robustness\(Ahnet al\.,[2022](https://arxiv.org/html/2605.16024#bib.bib23), Shinnet al\.,[2023](https://arxiv.org/html/2605.16024#bib.bib24), Zhouet al\.,[2024a](https://arxiv.org/html/2605.16024#bib.bib25)\), while retrieval\-augmented agents use memory to surface relevant past experience conditioned on current context\(Kagaya and others,[2024](https://arxiv.org/html/2605.16024#bib.bib16)\)\. Our focus is narrower: retrieval defines reusable screen identity and supports near\-duplicate detection, ambiguity estimation, and graph\-based search over desktop states\. Learned proposal priors matter only insofar as they improve this shared ambiguity\-aware exploration process\.

## 3Computer/OS state exploration

We formalize computer/OS exploration with two complementary signals:*screen novelty*, which expands the deduplicated state graph, and*screen ambiguity*, which identifies screens that still admit competing futures and should be probed before commitment\.

![Refer to caption](https://arxiv.org/html/2605.16024v1/figures/ambiguity_vs_novelty.jpg)Figure 1:Complementary exploration signals: novelty expands coverage, while ambiguity reduction resolves aliased states before commitment\.LetGt=\(Vt,Et\)G\_\{t\}=\(V\_\{t\},E\_\{t\}\)denote the global deduplicated state graph accumulated up to search timett, whereVtV\_\{t\}is the set of discovered deduplicated states andEtE\_\{t\}is the set of observed labeled transitions\. We represent a realized graph edge as a transition triple\(s,σ,s′\)\(s,\\sigma,s^\{\\prime\}\), whereσ\\sigmais the executed action signature ands,s′s,s^\{\\prime\}are deduplicated states\.

#### Screen novelty\.

Letssdenote a deduplicated screen state\. A realized transition triple\(s,σ,s′\)\(s,\\sigma,s^\{\\prime\}\)is novel if it reveals a previously unseen deduplicated destination state \(s′∉Vts^\{\\prime\}\\notin V\_\{t\}\) or a previously unseen labeled transition \(\(s,σ,s′\)∉Et\(s,\\sigma,s^\{\\prime\}\)\\notin E\_\{t\}\) in the global graph\. We use this node/edge frontier signal as an intrinsic coverage objective\.

#### Screen ambiguity\.

Let𝒪​\(s\)\\mathcal\{O\}\(s\)be the near\-duplicate cluster for deduplicated statess, and letΣ​\(s\)\\Sigma\(s\)be the action signatures observed in that cluster\. We estimate ambiguity by asking a simple question:*if we apply the same action signature to similar\-looking screens, do we get consistent outcomes?*For eachσ∈Σ​\(s\)\\sigma\\in\\Sigma\(s\), letP​\(s′∣s,σ\)P\(s^\{\\prime\}\\mid s,\\sigma\)be the empirical next\-state distribution over logged transitions from observations in𝒪​\(s\)\\mathcal\{O\}\(s\)where signatureσ\\sigmawas executed\. We define trajectory dispersion as

D​\(s\):=∑σ∈Σ​\(s\)ws,σ​H¯​\(P​\(s′∣s,σ\)\),ws,σ:=ns,σ∑σ~∈Σ​\(s\)ns,σ~,D\(s\):=\\sum\_\{\\sigma\\in\\Sigma\(s\)\}w\_\{s,\\sigma\}\\,\\bar\{H\}\\\!\\left\(P\(s^\{\\prime\}\\mid s,\\sigma\)\\right\),\\qquad w\_\{s,\\sigma\}:=\\frac\{n\_\{s,\\sigma\}\}\{\\sum\_\{\\tilde\{\\sigma\}\\in\\Sigma\(s\)\}n\_\{s,\\tilde\{\\sigma\}\}\},whereH¯​\(⋅\)\\bar\{H\}\(\\cdot\)is entropy normalized to\[0,1\]\[0,1\]andns,σn\_\{s,\\sigma\}is the count of signature\-σ\\sigmatransitions from𝒪​\(s\)\\mathcal\{O\}\(s\)\.

To avoid overconfident scores in rarely visited states, we apply confidence shrinkage with

ρ​\(s\):=nsns\+κ,ns:=∑σ∈Σ​\(s\)ns,σ,\\rho\(s\):=\\frac\{n\_\{s\}\}\{n\_\{s\}\+\\kappa\},\\qquad n\_\{s\}:=\\sum\_\{\\sigma\\in\\Sigma\(s\)\}n\_\{s,\\sigma\},and define

u​\(s\):=ρ​\(s\)​D​\(s\)\+\(1−ρ​\(s\)\)​u0∈\[0,1\]\.u\(s\):=\\rho\(s\)\\,D\(s\)\+\(1\-\\rho\(s\)\)u\_\{0\}\\in\[0,1\]\.\(1\)Hereκ\>0\\kappa\>0is a shrinkage pseudo\-count that controls how quickly empirical dispersion overrides the prior, andu0∈\[0,1\]u\_\{0\}\\in\[0,1\]is the prior ambiguity level assigned to states with little or no matched\-action evidence\. This score is a structural proxy for aliasing, not an explicit posterior uncertainty over latent workflow state\. In practice, highu​\(s\)u\(s\)may reflect hidden workflow variation, asynchronous application behavior, noisy execution, or imperfect deduplication, all of which make future outcomes less predictable under matched action signatures\. Intuitively, highu​\(s\)u\(s\)means the current screen is still aliased, so the policy should prefer probing actions before committing\.

#### Exploration objective\.

Pure novelty can over\-reward superficial UI change, while pure ambiguity reduction can become overly local\. We therefore optimize both by expanding the reachable frontier*and*reducing ambiguity in aliased regions\. Rather than explicit belief\-state updates and expected information gain, this ambiguity term is a scalable structural proxy for information\-seeking exploration in high\-dimensional GUI environments\. We use this objective to guide PUCT graph\-bandit data generation and to evaluate search policies over the shared graph\.

#### Probing versus committing\.

This induces two action types\.*Probe*actions reduce uncertainty by moving to more diagnostic observations;*commit*actions exploit an already\-resolved interpretation\. In partially observable GUI environments, robust behavior depends on delaying commitment until enough evidence is gathered\.

## 4Screen representation, similarity, and retrieval

We represent each screen observationSSas a sparse set of discrete features derived from the UI element setℰ​\(S\)\\mathcal\{E\}\(S\)extracted from the UIA tree\. Each elemente∈ℰ​\(S\)e\\in\\mathcal\{E\}\(S\)provides bounding box coordinates𝐩e\\mathbf\{p\}\_\{e\}, a control labelτe\\tau\_\{e\}, and a text descriptorxex\_\{e\}\. In addition, two screen\-scoped attributes are supplied via the task configuration: text\-size percentagesscreen​\(S\)s\_\{\\mathrm\{screen\}\}\(S\)and a screen\-level display modem​\(S\)m\(S\)\. The goal is to map UI observations into a comparable representation that is robust to small layout changes\.

In computer\-use environments, screen observations are frequently*aliased*\. Identical or near\-identical UI structure can correspond to different hidden workflow state \(permissions, auth context, pending async events\)\. We therefore use screen features not only for deduplication, but to support loop avoidance, aliasing detection, and search\-time proposal modeling\. The retrieval module provides fast evidence for revisits and near\-duplicates, which we treat as a signal for collapsed futures\.

### 4\.1Feature universes and sets

![Refer to caption](https://arxiv.org/html/2605.16024v1/x1.png)\(\(a\)\)Discrete feature universes\.
![Refer to caption](https://arxiv.org/html/2605.16024v1/x2.png)\(\(b\)\)Feature\-set extraction pipeline\.

Figure 2:Screen representation components: shared discrete universes \(left\) and feature\-set extraction \(right\)\.We represent each screen with a compact hybrid signature built from UIA\-derived feature families over shared discrete universes\. For each UI element inℰ​\(S\)\\mathcal\{E\}\(S\), we quantize its bounding box into a30×3030\\times 30spatial grid cell and pair location with control type to form structural control\-type features, and pair location with normalized text to form structural text features\. These sparse structural atoms retain layout and local lexical cues while remaining robust to small UI shifts\.

In addition, we construct a deterministic text serialization of the same UIA screen rows and encode it with a text embedding model\. This dense screen embedding complements the sparse atoms by capturing semantic similarity between screens whose labels differ lexically but describe similar UI content\. We also include two screen\-scoped discrete attributes supplied by task configuration, namely text\-size bin and display mode \(light/dark\)\. Canonical state IDs are computed from the structural representation by sorting structural rows lexicographically and appendingmode:andtext\_size:tags; the dense embedding is used for retrieval similarity, not for canonical ID construction\.

#### Unified representation\.

The active representation combines location\-aware sparse structural atoms, a dense text embedding of the serialized UIA screen, and lightweight screen metadata\. These components are used for indexing, retrieval, deduplication, and ambiguity\-aware action selection\.

### 4\.2Screen similarity and retrieval

Given a query screenSqS\_\{q\}and a corpus of previously observed screens𝒟\\mathcal\{D\}, we retrieve candidates with a sparse structural index over the stored screen signatures\. Each screenSSstores structural termsW​\(S\)W\(S\)together with filter metadata, while Figure[6](https://arxiv.org/html/2605.16024#A1.F6)summarizes the overall pipeline\.

### 4\.3Structural and semantic retrieval over UIA screens

We index structural atoms as searchable lexical tokens in a sparse retrieval index and store a dense semantic embedding for each serialized screen\. We also retain screen\-level mode and text size as filter metadata\. At query time, we first restrict candidates by rollout\-group prefix, mode, and text\-size compatibility, then retrieve screens through the structural fieldsstruct\_control\_type\_featuresandstruct\_text\_features, which contain tokens such asr3\_c12\|T:buttonandr3\_c12\|X:save\. The dense embedding provides a complementary semantic view of the same UIA\-derived screen serialization\.

### 4\.4Bounded near\-duplicate verification

We then verify the retrieved top\-KKset with a bounded sparse\-overlap score so retrieval becomes a stable revisit signal rather than only a ranked list\. Specifically, we split sparse atoms into cell–control\-type tokensTct​\(S\)T\_\{\\text\{ct\}\}\(S\)and cell–text tokensTtxt​\(S\)T\_\{\\text\{txt\}\}\(S\), and compute Jaccard overlap for each component:

Jj​\(Sq,S\)=\|Tj​\(Sq\)∩Tj​\(S\)\|\|Tj​\(Sq\)∪Tj​\(S\)\|∈\[0,1\]\.J\_\{j\}\(S\_\{q\},S\)=\\frac\{\|T\_\{j\}\(S\_\{q\}\)\\cap T\_\{j\}\(S\)\|\}\{\|T\_\{j\}\(S\_\{q\}\)\\cup T\_\{j\}\(S\)\|\}\\in\[0,1\]\.We combine these overlaps into a single bounded similarity,

Jsparse​\(Sq,S\)=∑j∈\{ct,txt\}λj​Jj​\(Sq,S\),∑jλj=1\.J\_\{\\text\{sparse\}\}\(S\_\{q\},S\)=\\sum\_\{j\\in\\\{\\text\{ct\},\\text\{txt\}\\\}\}\\lambda\_\{j\}\\,J\_\{j\}\(S\_\{q\},S\),\\qquad\\sum\_\{j\}\\lambda\_\{j\}=1\.In our experiments, we setλct=λtxt=0\.5\\lambda\_\{\\text\{ct\}\}=\\lambda\_\{\\text\{txt\}\}=0\.5and mark a candidate as a near\-duplicate whenJsparse​\(Sq,S\)≥0\.93J\_\{\\text\{sparse\}\}\(S\_\{q\},S\)\\geq 0\.93\. Exact\-feature deduplication follows first\-seen order, and equal\-similarity ties keep the first returned result\. This verification step supports deduplication, loop avoidance, and ambiguity\-aware planning\.

## 5Uncertainty\-guided PUCT graph\-bandit for computer state exploration

Our exploration policy is an uncertainty\-guided PUCT graph\-bandit that uses a one\-step PUCT action rule over the evolving deduplicated state graphGt=\(Vt,Et\)G\_\{t\}=\(V\_\{t\},E\_\{t\}\), where realized edges are transition triples\(s,σ,s′\)\(s,\\sigma,s^\{\\prime\}\)\. Because many different interaction histories collapse to the same deduplicated screen, we share statistics across transpositions rather than treating the search space as a pure tree\.

For a deduplicated statess, letΣexec​\(s\)\\Sigma\_\{\\mathrm\{exec\}\}\(s\)denote the set of executable action signatures available fromss, and letN​\(s,σ\)N\(s,\\sigma\)denote the number of times signatureσ\\sigmahas been executed fromssin the shared graph statistics\.

At each statess, the policy selects an executable action signatureσ∈Σexec​\(s\)\\sigma\\in\\Sigma\_\{\\mathrm\{exec\}\}\(s\)with the PUCT rule,

σ⋆=arg⁡maxσ∈Σexec​\(s\)⁡\[Q​\(s,σ\)\+U​\(s,σ\)\],U​\(s,σ\)=cpuct​P​\(σ∣s\)​∑σ~N​\(s,σ~\)1\+N​\(s,σ\)\.\\sigma^\{\\star\}=\\arg\\max\_\{\\sigma\\in\\Sigma\_\{\\mathrm\{exec\}\}\(s\)\}\\bigl\[Q\(s,\\sigma\)\+U\(s,\\sigma\)\\bigr\],\\qquad U\(s,\\sigma\)=c\_\{\\text\{puct\}\}\\,P\(\\sigma\\mid s\)\\frac\{\\sqrt\{\\sum\_\{\\tilde\{\\sigma\}\}N\(s,\\tilde\{\\sigma\}\)\}\}\{1\+N\(s,\\sigma\)\}\.HereQ​\(s,σ\)Q\(s,\\sigma\)is the empirical mean of one\-step exploration utility on the shared graph, whileU​\(s,σ\)U\(s,\\sigma\)favors under\-visited but locally plausible signatures through the policy priorP​\(σ∣s\)P\(\\sigma\\mid s\)\.

The utility is designed to encourage two behaviors: expanding the discovered graph frontier and moving toward less ambiguous states\. For a realized transition\(s,σ,s′\)\(s,\\sigma,s^\{\\prime\}\), we use the immediate reward

r​\(s,σ,s′\)=λstate​1​\[s′∉Vt\]\+λedge​1​\[\(s,σ,s′\)∉Et\]\+λamb​\[u​\(s\)−u​\(s′\)\]\+,r\(s,\\sigma,s^\{\\prime\}\)=\\lambda\_\{\\text\{state\}\}\\,\\mathbf\{1\}\[s^\{\\prime\}\\notin V\_\{t\}\]\+\\lambda\_\{\\text\{edge\}\}\\,\\mathbf\{1\}\[\(s,\\sigma,s^\{\\prime\}\)\\notin E\_\{t\}\]\+\\lambda\_\{\\text\{amb\}\}\\,\[u\(s\)\-u\(s^\{\\prime\}\)\]\_\{\+\},where\[x\]\+:=max⁡\(x,0\)\[x\]\_\{\+\}:=\\max\(x,0\)\. The first two terms give first\-discovery credit for new deduplicated states and realized edges, while the third rewards ambiguity reduction through transitions to less ambiguous deduplicated states\.

HereQ​\(s,σ\)Q\(s,\\sigma\)tracks the running mean of this immediate reward over observed executions of\(s,σ\)\(s,\\sigma\)\. Search is one step deep: there are no simulated rollouts, no rollout budget, and no discounted multi\-step backup;γ\\gammais configured as 1\.0 for compatibility but is not used in backup\.

Overall, the policy treats GUI exploration as action selection under partial observability: the prior proposes locally plausible actions, frontier utility pushes outward into new regions of the graph, ambiguity utility favors informative disambiguating transitions, and shared graph statistics turn those signals into reusable action values across revisits\.

## 6Proposal priors from exploration traces

The PUCT graph\-bandit exploration runs produce a large corpus of short interaction traces that expose aliasing, loops, and failure modes\. The main contribution of this paper is the exploration pipeline itself, but these traces also support lightweight proposal priors over executable action signatures conditioned on the current screen\. In replay\-start evaluation, we use these priors only to bias one\-step PUCT selection through the prior termP​\(σ∣s\)P\(\\sigma\\mid s\)in the rule above; we do not treat them as standalone planners with separate control objectives\.

The default search prior isuniform\_prior@1, and an optional deterministicheuristic@1profile produces a compact ranked set of plausible signatures from the current screen using local structural cues\. Search remains responsible for frontier\-sensitive selection, ambiguity reduction, and commitment timing via the shared graph statistics in Section 5\. This keeps the paper centered on retrieval\-defined state identity and ambiguity\-aware exploration while still letting us test whether better local proposals improve search efficiency\. Because proposal priors are secondary to our main thesis, we place that analysis in the appendix rather than in the main benchmark comparison\.

## 7OS exploration setup

We evaluate ScreenSearch as a large\-scale desktop GUI exploration system\. For each application, we report exploration budget \(VM\-hours\) together with dataset\-level outputs including total screenshots, unique screenshots after deduplication, unique screen discovery rate, cross\-application states, and exploration traces used for subsequent analysis\. We also compare a uniform prior against a deterministic heuristic prior to measure the effect of prior\-guided exploration\.

![Refer to caption](https://arxiv.org/html/2605.16024v1/x3.png)Figure 3:System overview of the data generation pipeline distributed across VMs\.Each run starts from a clean VM snapshot, and we vary a small set of initial conditions—seeded content, display mode, and window size/placement—to broaden coverage without introducing uncontrolled state carryover\. The action space contains mouse clicks and keyboard typing instantiated from the UIA candidate table, restricted to elements attributed to the target application\. We separately log cross\-application states when interactions surface external dialogs or auxiliary apps, and we retain raw exploration trajectories for subsequent offline analysis before filtering loop\-heavy or near\-no\-op segments for downstream analysis\.

#### Deduplication hyperparameters\.

Table[1](https://arxiv.org/html/2605.16024#S7.T1)lists the set of thresholds and weights used for state matching\. The similarity thresholdτ\\taudetermines whether a new observation is merged into an existing state or indexed as new\. The two Jaccard weights balance structural control\-type evidence against textual evidence in the final duplicate score\.

Table 1:Experiment hyperparameter values\.HyperparameterValueSimilarity Threshold \(τ\\tau\)0\.93Cell×\\timesControl\-type Jaccard Weight0\.5Cell×\\timesText Jaccard Weight0\.5

## 8Large\-scale OS exploration results

#### Overall performance\.

Table[2](https://arxiv.org/html/2605.16024#S8.T2)summarizes the datasets produced by theScreenSearchexploration pipeline across applications\. Here,ScreenSearchrefers to the shared retrieval/deduplication system together with the ambiguity\-aware PUCT graph\-bandit explorer used for data collection\. Reporting total screenshots and unique screenshots after similarity\-based deduplication shows how much reusable state structure the explorer uncovers, along with the resulting unique screen discovery rate and cross\-application states surfaced during exploration\. Across the apps, we generate between 300 and 9K unique screenshots per application, and observe substantial variation in the unique screen discovery rate—from 1\.03% in Notepad to 7\.83% in LibreOffice Calc—reflecting differences in UI variability and reachable workflows\. We also observe cross\-application transitions in several apps, indicating that exploration frequently surfaces dialogs beyond the target app\. Detailed ablations on temporal discovery dynamics, the heuristic prior, scaling behavior, and screen\-similarity fidelity are deferred to the appendix; see[Sections˜B\.1](https://arxiv.org/html/2605.16024#A2.SS1),[B\.2](https://arxiv.org/html/2605.16024#A2.SS2),[B\.3](https://arxiv.org/html/2605.16024#A2.SS3)and[B\.4](https://arxiv.org/html/2605.16024#A2.SS4)\.

Table 2:Overall data generation statistics\.Application\# ofVM hours\# of Cross\-AppDiscovered\# ofTotalScreenshots\# ofUniqueScreenshotsUnique ScreenDiscovery Rate \(%\)\# ofTrajectories\(length 3\)Clock21414250013663\.213701File Explorer36685276339857\.552662Microsoft Excel66368602525853\.004324Microsoft Word1377121361387594\.1010777Microsoft PowerPoint1809146611581241\.7415834Notepad1101304453141\.03612Settings460205303723104\.3613457VS Code25013953319444\.921995LibreOffice Writer92278405877\.49924LibreOffice Calc85178416147\.83396LibreOffice Math98176945587\.251088Overall5524431007406311463\.0955770

## 9Exploration under uncertainty: policy evaluation

We evaluate ScreenSearch as a*policy problem under uncertainty*: good behavior should expand the discovered frontier while avoiding repeated commitment to already known or low\-yield branches\. Because the replay\-start benchmark directly measures frontier growth and ambiguity trajectories rather than human\-annotated semantic disambiguation, this section focuses on how frontier growth and ambiguity reduction trade off across reactive and search\-based policies over the shared deduplicated state graph\.

### 9\.1Evaluation protocol

We use a replay\-start protocol\. Each episode begins from a verified replayable state reached from a clean snapshot by replaying a deterministic prefix\. A state is included in the replay\-start pool only if verification shows that the stored prefix reliably returns to the intended deduplicated state\. For Table[3](https://arxiv.org/html/2605.16024#S9.T3)and Figures[4](https://arxiv.org/html/2605.16024#S9.F4)–[5](https://arxiv.org/html/2605.16024#S9.F5), we evaluate on a fixed Notepad slice reconstructed from the benchmark configuration\. We restrict this slice to eligible Notepad states with generation\-mode provenance, at least three occurrences, and a completed replay anchor at step≥5\\geq 5, then deterministically select three replay\-start cases\. This yields three replay\-start episodes;s50refers only to the 50\-step budget\.

We compare four reactive baselines that act directly from the current screen, and the uncertainty\-guided PUCT graph\-bandit with the default uniform prior\. Every episode uses a fixed50\-actionbudget \(steps 0–49 in the plots\), starts from the same replayed state, and receives the same public information\. Runs are not initialized with states, edges, or search statistics discovered in earlier episodes\. The appendix prior ablation separately measures how the deterministic heuristic prior affects discovery rate during corpus construction\. For the main diagnostic slice, we keep the uniform prior so the comparison isolates local proposal quality from graph\-based search\.

### 9\.2Metrics and reporting

We focus on frontier discovery and a direct ambiguity\-trajectory diagnostic under replay\-start evaluation\. For any replay\-start setℬ\\mathcal\{B\}, letSt\(b\)S\_\{t\}^\{\(b\)\}be the raw observation at stepttin episodebb, letst\(b\):=π​\(St\(b\)\)s\_\{t\}^\{\(b\)\}:=\\pi\(S\_\{t\}^\{\(b\)\}\)be its deduplicated state under the retrieval/deduplication mapπ\\pi, and define

MV​\(t\):=1\|ℬ\|​∑b∈ℬ\|\{sτ\(b\):0≤τ≤t\}\|,Δ​ut:=1\|ℬ\|​∑b∈ℬ\(u​\(st\(b\)\)−u​\(s0\(b\)\)\)\.M\_\{V\}\(t\):=\\frac\{1\}\{\|\\mathcal\{B\}\|\}\\sum\_\{b\\in\\mathcal\{B\}\}\\left\|\\\{s\_\{\\tau\}^\{\(b\)\}:0\\leq\\tau\\leq t\\\}\\right\|,\\qquad\\Delta u\_\{t\}:=\\frac\{1\}\{\|\\mathcal\{B\}\|\}\\sum\_\{b\\in\\mathcal\{B\}\}\\left\(u\(s\_\{t\}^\{\(b\)\}\)\-u\(s\_\{0\}^\{\(b\)\}\)\\right\)\.We report the final\-horizon valuesMV​\(49\)M\_\{V\}\(49\)andΔ​u49\\Delta u\_\{49\}together with the discrete AUC summaries∑t=049MV​\(t\)\\sum\_\{t=0\}^\{49\}M\_\{V\}\(t\)and∑t=049Δ​ut\\sum\_\{t=0\}^\{49\}\\Delta u\_\{t\}\. Table[3](https://arxiv.org/html/2605.16024#S9.T3)reports these exact curve\-derived summaries on the fixed Notepad slice used in Figures[4](https://arxiv.org/html/2605.16024#S9.F4)–[5](https://arxiv.org/html/2605.16024#S9.F5)\. Table[2](https://arxiv.org/html/2605.16024#S8.T2)separately reports exact full\-corpus exploration totals\.

Table 3:Exact frontier and ambiguity summaries derived from the fixed three\-start Notepad replay\-start slice\. Higher frontier metrics are better; lower ambiguity metrics are better\.MethodMV​\(49\)↑M\_\{V\}\(49\)\\uparrowFrontierAUC↑\\uparrowΔ​u49↓\\Delta u\_\{49\}\\downarrowAmbiguityAUC↓\\downarrowReactive gpt\-5\-nano \(no ctx\)10\.00340\.33\-0\.005\.37Reactive gpt\-5\-nano \(ctx\)10\.00362\.000\.035\.41Reactive gpt\-5\-mini \(no ctx\)13\.67362\.33\-0\.090\.55Reactive gpt\-5\-mini \(ctx\)10\.00411\.00\-0\.18\-1\.23PUCT graph\-bandit10\.00253\.330\.051\.08

05510101515202025253030353540404545022446688101012121414StepMV​\(t\)M\_\{V\}\(t\)5\.4n \| no ctx5\.4n \| ctx5\.4m \| no ctx5\.4m \| ctxPUCT graph\-bandit
Figure 4:Frontier\-state trajectories on the fixed three\-start Notepad replay\-start slice\. Search continues to discover frontier states late in the budget, even after some reactive policies plateau\.05510101515202025253030353540404545−0\.3\-0\.3−0\.2\-0\.2−0\.1\-0\.100\.10\.10\.20\.20\.30\.30\.40\.4StepΔ​ut\\Delta u\_\{t\}5\.4n \| no ctx5\.4n \| ctx5\.4m \| no ctx5\.4m \| ctxPUCT graph\-bandit
Figure 5:Ambiguity change on the same subset\. LowerΔ​ut\\Delta u\_\{t\}indicates stronger disambiguation, not greater frontier growth\.
### 9\.3Results analysis

Table[3](https://arxiv.org/html/2605.16024#S9.T3)shows substantial variation across policies on this slice\. The reactive gpt\-5\-mini variants attain the largest frontier totals, with the context\-enabled gpt\-5\-mini policy achieving the best frontier AUC while also substantially reducing ambiguity\. The gpt\-5\-nano variants are weaker on both frontier metrics, and the PUCT graph\-bandit with the default uniform prior is more conservative on this diagnostic slice\.

The slice\-level comparison is therefore best read as evidence that proposal quality and policy family materially affect exploration behavior, not as evidence that one method uniformly dominates every benchmark slice\.

Appendix[B\.2](https://arxiv.org/html/2605.16024#A2.SS2)adds a corpus\-scale efficiency comparison: on the corpus\-building runs from Section 6, replacing the uniform prior with the deterministic heuristic prior raises the aggregate unique\-state discovery rate from 1\.74% to 4\.10%\. Together, the slice\-level diagnostics and corpus\-level prior comparison show that proposal quality, shared state identity, and ambiguity\-aware search play complementary roles in robust desktop exploration\.

## 10Limitations

Our study has several limitations\. First, the evaluation still covers a limited set of applications and bounded episode budgets, so these gains should be read as evidence for the value of ambiguity\-aware exploration rather than as a complete account of desktop interaction\. Second, the ambiguity score is a scalable structural proxy based on matched\-action outcome dispersion over deduplicated states\. It does not fully capture semantic uncertainty, long\-range latent state, or irreversible user\-specific side effects, and we validate it indirectly through frontier\-growth and robustness outcomes rather than through a separate semantic calibration study\. Third, replay\-start evaluation improves control and comparability, but it does not reproduce the full non\-stationarity of open\-ended deployment, where history, background processes, and timing effects can interact in less predictable ways\. Finally, performance remains coupled to the retrieval index, deduplication pipeline, and the quality of the proposal prior, so errors in state matching or retrieval can propagate into both corpus quality and downstream policy evaluation\.

## 11Conclusion

We presented ScreenSearch, which combines structural retrieval and deduplication with an ambiguity\-aware PUCT graph\-bandit for desktop exploration\. The central issue is the one introduced at the start of the paper: under partial observability, visually similar screens can correspond to different underlying workflow states, so useful behavior requires both frontier expansion and ambiguity reduction before commitment\.

The replay\-start diagnostics support that framing\. Frontier growth and ambiguity reduction do not move together: a policy can reduce ambiguity quickly while still discovering little of the shared state graph\. The appendix prior ablations also show that stronger proposal priors improve unique\-state discovery during large\-scale exploration\.

Overall, robust desktop exploration appears to depend on three pieces working together: reusable screen identity, proposal quality, and ambiguity\-aware search\. Structural retrieval and deduplication make revisits and aliasing explicit, ambiguity estimates show when a screen still needs probing, and search uses those signals to decide when to probe and when to commit\.

## References

- M\. Ahn, A\. Brohan, N\. Brown, Y\. Chebotar, O\. Cortes, B\. David, C\. Finn, C\. Fu, K\. Gopalakrishnan, K\. Hausman, A\. Herzog, D\. Ho, J\. Hsu, J\. Ibarz, B\. Ichter, A\. Irpan, E\. Jang, K\. Jeffrey, S\. Jesmonth, N\. Joshi, R\. Julian, D\. Kalashnikov, S\. Levine, L\. Lu, C\. Parada, K\. Rao, U\. Rückert, J\. Schneider, K\. Sheng, P\. Sermanet, S\. Sriram, A\. Stone, T\. Tan, H\. Tran, V\. Vanhoucke, F\. Xia, T\. Xu, and A\. Zeng \(2022\)Do as i can, not as i say: grounding language in robotic affordances\.ArXiv preprintabs/2204\.01691\.External Links:[Link](https://arxiv.org/abs/2204.01691)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px4.p1.1)\.
- R\. Bajcsy, Y\. Aloimonos, and J\. K\. Tsotsos \(2018\)Revisiting active perception\.Autonomous Robots42\(2\),pp\. 177–196\.External Links:[Document](https://dx.doi.org/10.1007/s10514-017-9615-3),[Link](https://doi.org/10.1007/s10514-017-9615-3)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px2.p1.1)\.
- Y\. Burda, H\. Edwards, A\. J\. Storkey, and O\. Klimov \(2019\)Exploration by random network distillation\.In7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6\-9, 2019,External Links:[Link](https://openreview.net/forum?id=H1lJJnR5Ym)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- L\. Chrisman \(1992\)Reinforcement learning with perceptual aliasing: the perceptual distinctions approach\.InProceedings of the Tenth National Conference on Artificial Intelligence \(AAAI\-92\),W\. R\. Swartout \(Ed\.\),pp\. 183–188\.External Links:[Link](https://dblp.org/rec/conf/aaai/Chrisman92)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px2.p1.1)\.
- X\. Deng, Y\. Gu, B\. Zheng, S\. Chen, S\. Stevens, B\. Wang, H\. Sun, and Y\. Su \(2023\)Mind2Web: towards a generalist agent for the web\.InAdvances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 \- 16, 2023,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),External Links:[Link](http://papers.nips.cc/paper%5C_files/paper/2023/hash/5950bf290a1570ea401bf98882128160-Abstract-Datasets%5C_and%5C_Benchmarks.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px1.p1.1)\.
- T\. Kagayaet al\.\(2024\)RAP: retrieval\-augmented planning with contextual memory for multimodal agents\.ArXiv preprintabs/2402\.03610\.External Links:[Link](https://arxiv.org/abs/2402.03610)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px4.p1.1)\.
- E\. Z\. Liu, K\. Guu, P\. Pasupat, T\. Shi, and P\. Liang \(2018\)Reinforcement learning on web interfaces using workflow\-guided exploration\.In6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 \- May 3, 2018, Conference Track Proceedings,External Links:[Link](https://openreview.net/forum?id=ryTp3f-0-)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px1.p1.1)\.
- D\. Pathak, P\. Agrawal, A\. A\. Efros, and T\. Darrell \(2017\)Curiosity\-driven exploration by self\-supervised prediction\.InProceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\-11 August 2017,D\. Precup and Y\. W\. Teh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.70,pp\. 2778–2787\.External Links:[Link](http://proceedings.mlr.press/v70/pathak17a.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- J\. Schrittwieser, I\. Antonoglou, T\. Hubert, K\. Simonyan, L\. Sifre, S\. Schmitt, A\. Guez, E\. Lockhart, D\. Hassabis, T\. Graepel, T\. Lillicrap, and D\. Silver \(2019\)Mastering atari, go, chess and shogi by planning with a learned model\.External Links:1911\.08265Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- R\. Sekar, O\. Rybkin, K\. Daniilidis, P\. Abbeel, D\. Hafner, and D\. Pathak \(2020\)Planning to explore via self\-supervised world models\.InProceedings of the 37th International Conference on Machine Learning, ICML 2020, 13\-18 July 2020, Virtual Event,Proceedings of Machine Learning Research, Vol\.119,pp\. 8583–8592\.External Links:[Link](http://proceedings.mlr.press/v119/sekar20a.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.InAdvances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 \- 16, 2023,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),External Links:[Link](http://papers.nips.cc/paper%5C_files/paper/2023/hash/1b44b878bb782e6954cd888628510e90-Abstract-Conference.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px4.p1.1)\.
- D\. Silver, T\. Hubert, J\. Schrittwieser, I\. Antonoglou, M\. Lai, A\. Guez, M\. Lanctot, L\. Sifre, D\. Kumaran, T\. Graepel,et al\.\(2018\)A general reinforcement learning algorithm that masters chess, shogi, and go through self\-play\.Science362\(6419\),pp\. 1140–1144\.Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- D\. Silver, J\. Schrittwieser, K\. Simonyan, I\. Antonoglou, A\. Huang, A\. Guez, T\. Hubert, L\. Baker, M\. Lai, A\. Bolton,et al\.\(2017\)Mastering the game of go without human knowledge\.Nature550\(7676\),pp\. 354–359\.Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px3.p1.1)\.
- D\. Silver and J\. Veness \(2010\)Monte\-carlo planning in large pomdps\.InAdvances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010\. Proceedings of a meeting held 6\-9 December 2010, Vancouver, British Columbia, Canada,J\. D\. Lafferty, C\. K\. I\. Williams, J\. Shawe\-Taylor, R\. S\. Zemel, and A\. Culotta \(Eds\.\),pp\. 2164–2172\.External Links:[Link](https://proceedings.neurips.cc/paper/2010/hash/edfbe1afcf9246bb0d40eb4d8027d90f-Abstract.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px2.p1.1)\.
- T\. Veiga and J\. Renoux \(2023\)From reactive to active sensing: a survey on information gathering in decision\-theoretic planning\.ACM Computing Surveys55\(13s\),pp\. 280:1–280:22\.External Links:[Document](https://dx.doi.org/10.1145/3583068),[Link](https://dl.acm.org/doi/10.1145/3583068)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px2.p1.1)\.
- T\. Xie, D\. Zhang, J\. Chen, X\. Li, S\. Zhao, R\. Cao, T\. J\. Hua, Z\. Cheng, D\. Shin, F\. Lei, Y\. Liu, Y\. Xu, S\. Zhou, S\. Savarese, C\. Xiong, V\. Zhong, and T\. Yu \(2024\)OSWorld: benchmarking multimodal agents for open\-ended tasks in real computer environments\.InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 \- 15, 2024,A\. Globersons, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. M\. Tomczak, and C\. Zhang \(Eds\.\),External Links:[Link](http://papers.nips.cc/paper%5C_files/paper/2024/hash/5d413e48f84dc61244b6be550f1cd8f5-Abstract-Datasets%5C_and%5C_Benchmarks%5C_Track.html)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. R\. Narasimhan, and Y\. Cao \(2023\)ReAct: synergizing reasoning and acting in language models\.InThe Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1\-5, 2023,External Links:[Link](https://openreview.net/pdf?id=WE%5C_vluYUL-X)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px4.p1.1)\.
- A\. Zhou, K\. Yan, M\. Shlapentokh\-Rothman, H\. Wang, and Y\. Wang \(2024a\)Language agent tree search unifies reasoning, acting, and planning in language models\.InForty\-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21\-27, 2024,External Links:[Link](https://openreview.net/forum?id=njwv9BsGHF)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px4.p1.1)\.
- S\. Zhou, F\. F\. Xu, H\. Zhu, X\. Zhou, R\. Lo, A\. Sridhar, X\. Cheng, T\. Ou, Y\. Bisk, D\. Fried, U\. Alon, and G\. Neubig \(2024b\)WebArena: A realistic web environment for building autonomous agents\.InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7\-11, 2024,External Links:[Link](https://openreview.net/forum?id=oKn9c6ytLx)Cited by:[§2](https://arxiv.org/html/2605.16024#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix AScreen similarity and retrieval overview

Figure[6](https://arxiv.org/html/2605.16024#A1.F6)shows how raw UIA observations are converted into retrievable representations and then merged into the shared state graph used by the system\.

![[Uncaptioned image]](https://arxiv.org/html/2605.16024v1/x4.png)

Figure 6:Overview of screen similarity and retrieval process\.

## Appendix BAblation experiments

This section reports supporting ablations on temporal discovery dynamics, the effect of the proposal prior, online scaling behavior, and the fidelity of the screen\-similarity pipeline\.

### B\.1State discovery over time

Figure[7](https://arxiv.org/html/2605.16024#A2.F7)shows the cumulative number of unique screenshots discovered as a function of wall\-clock time\. The curve rises rapidly early on as exploration traverses high\-branching UI regions and uncovers many previously unseen states\. Over time, the discovery rate declines and the curve gradually flattens, indicating increasing revisit rates and near\-duplicate encounters as the search concentrates in already mapped neighborhoods\.

![[Uncaptioned image]](https://arxiv.org/html/2605.16024v1/figures/unique_screenshots_over_time.png)

Figure 7:Cumulative number of unique states discovered over wall\-clock time\.

### B\.2Heuristic prior vs uniform prior

Table[4](https://arxiv.org/html/2605.16024#A2.T4)summarizes corpus\-building efficiency from Section 6\. Using the aggregate discovery\-rate definition100×\#​unique states/\#​interactions100\\times\\\#\\text\{unique states\}/\\\#\\text\{interactions\}, the deterministicheuristic@1prior reaches 4\.10% versus 1\.74% foruniform\_prior@1\. These are aggregate percentages over the corresponding runs, not per\-step instantaneous rates\. The heuristic prior steers action selection toward UI elements that are more likely to induce meaningful transitions, reducing time spent on redundant clicks and no\-op interactions\. The uniform\-prior setting still discovers new states, but less efficiently under this aggregate measure\.

Table 4:Prior type effect on unique state discovery rate \(%\) in the corpus\-building runs\.Prior TypeUnique State\[\-2pt\]Discovery Rate \(%\)Heuristic Prior \(heuristic@1\)4\.10Uniform Prior \(uniform\_prior@1\)1\.74

### B\.3Efficiency and system scaling

Figure[8](https://arxiv.org/html/2605.16024#A2.F8)plots per\-step action decision time over the course of a full exploration run\. The decision latency remains stable throughout, with no systematic upward trend as additional states are discovered and indexed\. This suggests online action selection is not bottlenecked by dataset growth: candidate enumeration and scoring remain effectively constant\-time with respect to the accumulated state set\. A few large spikes likely reflect transient system or application\-level delays\.

![[Uncaptioned image]](https://arxiv.org/html/2605.16024v1/figures/action_decision_time_vs_total_wall_clock.png)

Figure 8:Per\-step action decision time over total wall\-clock time\.

### B\.4Screen similarity accuracy

Figure[9](https://arxiv.org/html/2605.16024#A2.F9)summarizes, for each deduplicated screen state, the maximum fraction of pixels that change among observations grouped into that state\. The distribution is heavily concentrated near zero, indicating that our similarity pipeline consistently clusters observations that differ only by minor visual variations, such as cursor movement, focus highlights, or small dynamic regions\.

![[Uncaptioned image]](https://arxiv.org/html/2605.16024v1/figures/pixels_changed.png)

Figure 9:Maximum fraction of changed pixels within each deduplicated screen state\.