ScreenSearch：不确定性感知的操作系统探索

# ScreenSearch: 不确定性感知的操作系统探索
来源：https://arxiv.org/html/2605.16024
###### 摘要

桌面GUI代理在部分可观测条件下运行：视觉上相似的屏幕可能对应不同的底层工作流状态，因此局部合理的操作可能导致截然不同的结果。我们将此问题框定为计算机/操作系统状态探索问题，其中有效行为需要同时扩展可达边界和减少歧义，然后才能做出承诺。我们提出 **ScreenSearch**，一个将结构化屏幕检索与去重，以及一种用于大规模桌面探索的歧义感知 PUCT 图带算法相结合的系统。检索层将 UIA 树转换为位置感知的结构化特征，通过稀疏令牌搜索和元数据过滤器索引相关屏幕，并在 VM 工作节点之间维护一个共享的去重状态图。在此图之上，我们定义了一个基于匹配动作结果离散度的可扩展歧义信号。如果相似屏幕在相同动作签名下产生不同的下一个状态，则该状态应该被进一步探测，而不是被视为已解决。我们使用此信号以及边界奖励来驱动大规模探索，并在共享图上进行重放启动策略评估。在 11 个桌面应用程序中，ScreenSearch 收集了超过 100 万张截图和超过 3 万个去重状态，产生了具有大量跨应用和应用内多样性的大型探索语料库。在固定的重放启动切片上，我们观察到一个清晰的新颖性-歧义权衡：一些策略在快速降低歧义的同时，发现了很少的新边界。因此，仅降低歧义不足以作为探索目标。附录中的消融实验表明，更强的提议先验可以在语料库构建期间显著改善唯一状态的发现。这些结果表明，在决定何时探测和何时承诺时，状态身份、提议质量和歧义感知搜索都很重要。

## 1 引言

桌面GUI代理经常遇到视觉上相似但对应不同底层工作流状态的屏幕。权限、认证上下文、应用模式或异步状态中的微小隐藏差异，因此可能使局部合理的操作导致截然不同的结果。实践中的失败模式是过早承诺：当屏幕尚未完全解决时，就像它已经解决了一样行事。

我们通过 **计算机/操作系统状态探索** 来研究这一场景，有两个互补的目标。 **屏幕新颖性** 通过揭示全局状态图中先前未见过的去重状态或转换来扩展可达边界。 **屏幕歧义** 在视觉相似的观察允许不同未来时减少不确定性。仅优化新颖性可能会奖励表面的 UI 变化，而仅优化歧义可能会变得过于局部。有效的探索需要两者：扩展边界和区分关于当前状态的竞争假设。

我们介绍 **ScreenSearch**，一个用于歧义感知桌面探索的系统，其核心是两个想法：通过结构化检索和去重实现可重用的屏幕身份，以及使用基于匹配动作结果离散度的歧义信号在该共享状态图上的搜索。检索层将原始 UIA 树转换为位置感知的结构化表示，通过稀疏令牌搜索加元数据过滤器检索近似重复的状态，并在 VM 工作节点之间维护一个全局去重的状态图。如果相似外观的屏幕在相同动作签名下导致许多不同的未来，则当前观察是别名化的，需要进一步探测。

然后，探索使用一个不确定性引导的 PUCT 图带算法在共享图上进行，其中单步 PUCT 动作选择倾向于具有高累积探索效用和合理局部先验的签名。该效用结合了图边界扩展和歧义减少。这些轨迹也支持简单的提议先验，但这里的重点是探索问题本身：共享状态身份、歧义估计和搜索如何相互作用，以决定何时继续探测与何时承诺。随着索引状态集的增长，歧义估计变得更加清晰，反事实证据累积，探索决策在部分可观测条件下得到改善。

我们的贡献是：

- • 我们引入了桌面GUI探索的部分可观测性框架，其中有用的行为需要边界扩展和歧义减少。
- • 我们提出了一个基于去重屏幕簇上的匹配动作结果离散度的可扩展歧义分数。
- • 我们开发了一个歧义感知的探索流程，结合了结构化屏幕检索、有界近似重复验证，以及在共享去重状态图上的分布式 PUCT 图带算法。
- • 我们通过重放启动诊断和大规模探索消融实验表明，提议质量和歧义感知探索以非平凡方式相互作用：直接减少歧义不一定会转化为边界增长，而更强的提议先验在语料库构建期间提高了发现效率。

## 2 相关工作

#### 交互式 Web 和 OS 代理。

最近的基准测试评估了语言引导代理在日益逼真的环境中的表现，从程序化 Web 接口到涵盖许多应用的完整计算机环境（Liu 等，2018 (https://arxiv.org/html/2605.16024#bib.bib15)，Deng 等，2023 (https://arxiv.org/html/2605.16024#bib.bib14)，Zhou 等，2024b (https://arxiv.org/html/2605.16024#bib.bib13)，Xie 等，2024 (https://arxiv.org/html/2605.16024#bib.bib57)）。它们突显了在长视界、UI 可变性和真实执行约束下的持久脆弱性。我们的场景则侧重于大规模桌面探索，其中系统必须构建可重用的状态身份、检索相关屏幕，并在同一演化状态图上收集信息丰富的轨迹。

#### 感知别名、主动感知和部分可观测性。

我们的框架遵循经典观察，即即时感知输入可能不足以安全地选择动作。在强化学习中，这表现为 **感知别名**（Chrisman，1992 (https://arxiv.org/html/2605.16024#bib.bib318)）；在机器人学和规划中，相关概念作为主动感知和主动感知出现，其中动作用于在承诺之前收集信息性证据（Veiga 和 Renoux，2023 (https://arxiv.org/html/2605.16024#bib.bib319)，Bajcsy 等，2018 (https://arxiv.org/html/2605.16024#bib.bib320)）。像 POMCP 这样的 POMDP 方法通过显式的信念状态规划形式化了这一挑战（Silver 和 Veness，2010 (https://arxiv.org/html/2605.16024#bib.bib321)）。我们采用相同的动机，但将显式的贝叶斯更新替换为基于去重屏幕状态上的匹配动作结果离散度的可扩展 GUI 歧义结构代理。

#### 内在目标下的探索与搜索。

大量研究使用内在目标进行探索，例如预测误差、状态新颖性、访问奖励、不确定性或学习的世界模型（Pathak 等，2017 (https://arxiv.org/html/2605.16024#bib.bib316)，Burda 等，2019 (https://arxiv.org/html/2605.16024#bib.bib317)，Sekar 等，2020 (https://arxiv.org/html/2605.16024#bib.bib322)）。与这些文献一样，我们将探索视为一等信号。但在桌面 GUI 中，视觉上相似的观察可能隐藏着意义不同的工作流状态，因此仅凭新颖性是不够的。代理还必须知道何时继续探测而不是承诺。我们的歧义分数补充了边界寻求目标，我们的 PUCT 图带算法实例遵循了 AlphaZero 风格规划器使用的相同 PUCT 风格搜索族，同时在模拟器支持的 GUI 环境中使用单步在线选择，而不是通过学习的潜在动力学模型进行多步展开（Silver 等，2017 (https://arxiv.org/html/2605.16024#bib.bib20)，2018 (https://arxiv.org/html/2605.16024#bib.bib21)，Schrittwieser 等，2019 (https://arxiv.org/html/2605.16024#bib.bib323)）。

#### 逐步代理、刻意搜索和检索增强记忆。

许多语言代理交织着短视界的推理和动作选择，通常贪婪地依赖于当前观察和短上下文（Yao 等，2023 (https://arxiv.org/html/2605.16024#bib.bib22)）。响应式重规划、反思和刻意搜索变体提高了鲁棒性（Ahn 等，2022 (https://arxiv.org/html/2605.16024#bib.bib23)，Shinn 等，2023 (https://arxiv.org/html/2605.16024#bib.bib24)，Zhou 等，2024a (https://arxiv.org/html/2605.16024#bib.bib25)），而检索增强代理使用记忆来根据当前上下文检索相关过往经验（Kagaya 等，2024 (https://arxiv.org/html/2605.16024#bib.bib16)）。我们的关注点更窄：检索定义了可重用的屏幕身份，并支持近似重复检测、歧义估计以及基于图搜索的桌面状态。学习的提议先验仅在其改进这种共享的歧义感知探索过程时才有意义。

## 3 计算机/操作系统状态探索

我们使用两个互补信号形式化计算机/操作系统探索： **屏幕新颖性**，它扩展去重状态图；以及 **屏幕歧义**，它识别那些仍然允许竞争未来并应在承诺之前探测的屏幕。

图 1：互补探索信号：新颖性扩展覆盖面，而歧义减少在承诺之前解决别名状态。

设 $G_t = (V_t, E_t)$ 表示到搜索时间 $t$ 为止累积的全局去重状态图，其中 $V_t$ 是已发现的去重状态集，$E_t$ 是已观察到的带标签转换集。我们将一条已实现的图边表示为转换三元组 $(s, \sigma, s')$，其中 $\sigma$ 是执行的动作签名，$s, s'$ 是去重状态。

#### 屏幕新颖性。

令 $s$ 表示一个去重屏幕状态。如果一条已实现的转换三元组 $(s, \sigma, s')$ 揭示了先前未见过的去重目标状态 ($s' \notin V_t$) 或全局图中先前未见过的带标签转换 ($(s, \sigma, s') \notin E_t$)，则该三元组是新颖的。我们使用这个节点/边边界信号作为内在覆盖目标。

#### 屏幕歧义。

令 $\mathcal{O}(s)$ 是去重状态 $s$ 的近似重复簇，令 $\Sigma(s)$ 是该簇中观察到的动作签名。我们通过问一个简单问题来估计歧义：*如果我们将相同的动作签名应用于相似外观的屏幕，我们会得到一致的结果吗？* 对于每个 $\sigma \in \Sigma(s)$，令 $P(s' \mid s, \sigma)$ 是从 $\mathcal{O}(s)$ 中执行签名 $\sigma$ 的已记录转换中得到的经验下一个状态分布。我们将轨迹离散度定义为：

$$D(s) := \sum_{\sigma \in \Sigma(s)} w_{s,\sigma} \, \bar{H}\!\left(P(s' \mid s, \sigma)\right), \qquad w_{s,\sigma} := \frac{n_{s,\sigma}}{\sum_{\tilde{\sigma} \in \Sigma(s)} n_{s,\tilde{\sigma}}},$$

其中 $\bar{H}(\cdot)$ 是归一化到 $[0,1]$ 的熵，$n_{s,\sigma}$ 是从 $\mathcal{O}(s)$ 出发的签名-$\sigma$ 转换计数。

为了避免在很少访问的状态中出现过于自信的分数，我们应用置信度收缩：

$$\rho(s) := \frac{n_s}{n_s + \kappa}, \qquad n_s := \sum_{\sigma \in \Sigma(s)} n_{s,\sigma},$$

并定义

$$u(s) := \rho(s) \, D(s) + (1-\rho(s)) u_0 \in [0,1]. \qquad (1)$$

这里 $\kappa > 0$ 是收缩伪计数，控制经验离散度覆盖先验的速度，$u_0 \in [0,1]$ 是分配给具有很少或没有匹配动作证据的状态的先验歧义水平。该分数是别名化的结构代理，而不是潜在工作流状态的显式后验不确定性。在实践中，较高的 $u(s)$ 可能反映隐藏的工作流变化、异步应用行为、噪声执行或不完美的去重，所有这些都使得在匹配动作签名下未来结果更不可预测。直观地说，高的 $u(s)$ 意味着当前屏幕仍然是别名化的，因此策略应该在承诺之前优先选择探测动作。

#### 探索目标。

纯新颖性可能会过度奖励表面的 UI 变化，而纯歧义减少可能变得过于局部。因此，我们通过扩展可达边界 **和** 减少别名区域中的歧义来优化两者。该歧义项不是显式的信念状态更新和预期信息增益，而是高维 GUI 环境中信息寻求探索的一个可扩展结构代理。我们使用这个目标来指导 PUCT 图带算法数据生成，并评估共享图上的搜索策略。

#### 探测与承诺。

这导致了两种动作类型。 **探测** 动作通过移动到更具诊断性的观察来减少不确定性； **承诺** 动作利用已经解决的解释。在部分可观测的 GUI 环境中，稳健行为取决于延迟承诺，直到收集到足够的证据。

## 4 屏幕表示、相似性和检索

我们将每个屏幕观察 $S$ 表示为从 UIA 树中提取的 UI 元素集 $\mathcal{E}(S)$ 导出的稀疏离散特征集。每个元素 $e \in \mathcal{E}(S)$ 提供边界框坐标 $\mathbf{p}_e$、控制标签 $\tau_e$ 和文本描述符 $x_e$。此外，通过任务配置提供两个屏幕范围属性：文本大小百分比 $s_{\mathrm{screen}}(S)$ 和屏幕级显示模式 $m(S)$。目标是将 UI 观察映射到对微小布局变化鲁棒的可比较表示。

在计算机使用环境中，屏幕观察经常是 **别名化的**。相同或几乎相同的 UI 结构可能对应不同的隐藏工作流状态（权限、认证上下文、待处理异步事件）。因此，我们不仅使用屏幕特征进行去重，还支持循环避免、别名检测和搜索时间提议建模。检索模块为重访和近似重复提供快速证据，我们将其视为折叠未来的信号。

### 4.1 特征宇宙与集合

图 2：屏幕表示组件：共享离散宇宙（左）和特征集提取（右）。

我们使用由 UIA 派生的特征族在共享离散宇宙上构建的紧凑混合签名来表示每个屏幕。对于 $\mathcal{E}(S)$ 中的每个 UI 元素，我们将其边界框量化为一个 $30 \times 30$ 的空间网格单元，并将位置与控制类型配对形成结构化的控制类型特征，并将位置与归一化文本配对形成结构化的文本特征。这些稀疏的结构化原子保留了布局和局部词汇线索，同时对微小的 UI 移动保持鲁棒。

此外，我们构建相同 UIA 屏幕行的确定性文本序列化，并使用文本嵌入模型进行编码。这种密集的屏幕嵌入通过捕捉标签在词汇上不同但描述相似 UI 的屏幕之间的语义相似性，补充了稀疏原子。