ScreenSearch: Uncertainty-Aware OS Exploration¶

会议: NeurIPS 2026
arXiv: 2605.16024
OpenReview: https://openreview.net/forum?id=PN2v87IKXN
代码: 待确认
领域: LLM Agent
关键词: OS Agent, 桌面GUI探索, 不确定性感知, 图老虎机, 状态去重

一句话总结¶

针对桌面操作系统智能体面临的感知混淆与部分可观测性挑战，ScreenSearch 构建跨虚拟机共享的去重状态图，提出基于动作结果离散度的歧义度量与单步 PUCT 图老虎机算法，兼顾前沿扩展与歧义消解，高效收集可信状态转移并显著提升下游策略的屏幕敏感度与恢复能力。

研究背景与动机¶

基于视觉与语义界面的桌面操作系统智能体（OS/GUI Agent）近年来在端到端任务执行上取得了长足进展，但在真实操作系统环境中，部分可观测性（Partial Observability）构成了本质性的鲁棒性瓶颈。单一屏幕视口极少能完全确定底层的真实工作流状态：两张在视觉像素和控件布局上近乎完全相同的屏幕，可能隐藏着截然不同的系统权限、剪贴板内容、输入焦点、认证状态、挂起的异步后台进程或隐藏的应用程序模态。这种感知混淆（Perceptual Aliasing）意味着在相同屏幕下执行相同的交互动作可能会触发完全不可预测的不同转移结果。现有的计算机使用智能体大都局限于短视界或单步被动推理，缺乏对未知桌面环境进行系统性测绘与主动状态辨识的能力，极易在尚未理清潜在上下文时盲目提交不可逆的操作。

探索未知操作系统环境的核心难点在于平衡前沿扩展与不确定性消解。传统的内在好奇心驱动机制（如预测误差、状态新颖性奖励）倾向于追逐表面的视觉变化，在面对动态渲染或无休止的微小界面变动时容易陷入“嘈杂电视”陷阱；而纯粹以不确定性或信息增益为目标的探索策略，则往往停留在局部的模糊分支内原地打转，或者误把能够快速脱离不确定区域的平庸动作（例如单纯打开再关闭菜单）当成有效消解。此外，多工作节点分布式并行探索时，如何实现跨虚拟机的状态精确去重、动作唯一标识与全局统计量共享，也是构建可复用知识图谱必须克服的系统性挑战。

面对这些挑战，必须将屏幕观察视为关于底层工作流的“状态假设”而非确知状态，并通过动作结果的经验统计来量化潜在状态的歧义性。本文的核心切入点是将相同动作在相似屏幕下的后继状态离散度建模为结构性歧义信号，并将其与状态/边新颖性有机结合。核心 idea：ScreenSearch 构建混合检索与有界验证的分布式去重屏幕图，将匹配动作的后继分布离散度作为结构歧义代理，通过单步 PUCT 图老虎机协同推进状态边界扩展与低离散度转移，为桌面智能体提供不确定性感知的自主探索机制。

方法详解¶

整体框架¶

ScreenSearch 将桌面环境探索建模为在一个全局共享的去重屏幕图 $G_t = (V_t, E_t)$ 上的图拓扑学习与动作选择过程。整个系统由分布式的独立虚拟机环境（VM Workers）、全局混合索引系统、集中式图统计存储库（Global Graph-Bandit Store）以及轨迹后处理管线组成。

在探索运行时，每个虚拟机节点捕获当前屏幕观察并提取空间结构与语义原子，通过混合检索与两阶段有界相似度验证判断该观察是否属于已知合并状态。确认当前节点状态后，智能体枚举当前可执行的规范化动作签名，依据单步 PUCT（Predictor + Upper Confidence bounds for Trees）选择准则挑选动作并在虚拟机中执行一次。动作执行后，智能体观测真实后继屏幕，计算即时综合奖励（状态新颖性、边新颖性以及歧义消除量），并将访问计数与均值收益同步至全局存储库中。收集到的交互轨迹经过过滤去环与反事实配对后，可直接用于下游动作建议先验及条件扩散策略的离线训练。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["屏幕观察与UI候选提取<br/>UIA结构元数据 + 截图"] --> B["屏幕表征与混合检索<br/>BM25稀疏原子 + HNSW密集向量 + RRF融合"]
    B --> C["有界结构验证与状态去重<br/>空间控件/文本Jaccard比对 (τ=0.93)"]
    C --> D["动作签名规范化<br/>空间网格量化 + 角色/标签/参数归一化"]
    D --> E["单步PUCT图老虎机选择<br/>平衡探索收益Q、先验P与访问不确定性"]
    E --> F["虚拟机环境执行与后继观测<br/>真实OS单步交互与新屏幕捕获"]
    F --> G["多目标即时奖励更新与全局同步<br/>计算状态新颖性、边新颖性与歧义消除量"]
    G -->|更新统计并迭代探索| C

关键设计¶

1. 空间结构原子与混合有界验证：解决屏幕状态去重与抗坐标漂移难题
常规桌面界面的像素级匹配极其脆弱，轻微的主题颜色切换、光标闪烁或窗口微移均会导致状态爆炸；而纯语义向量表示又容易将具有不同交互功能的相似布局混淆。ScreenSearch 结合 UI 自动化（UIA）元素集提出离散特征原子表示。将活动窗口划分为 $30 \times 30$ 的规则网格，把每个元素的归一化角色与文本分别量化到空间网格单元中，生成“单元-控件”（cell-control）和“单元-文本”（cell-text）离散结构原子集合；同时将整屏文本串联后提取密集语义嵌入，并附加显示模式与字体档位作为硬过滤元数据。在检索已知状态时，系统先经元数据硬过滤，再通过 BM25 检索稀疏原子、HNSW 检索密集向量，利用互惠排名融合（RRF）选出前 200 个候选；最后进行严格的双通道有界 Jaccard 相似度校验： $$J_{\mathrm{sparse}}(S_q, S) = 0.5 J\left(T_{\mathrm{ct}}(S_q), T_{\mathrm{ct}}(S)\right) + 0.5 J\left(T_{\mathrm{txt}}(S_q), T_{\mathrm{txt}}(S)\right)$$ 只有当综合交并比 $J_{\mathrm{sparse}} \ge \tau$（默认 $\tau=0.93$）时才将观察合并至最高排名的已知图节点 $s$；否则在全局图上开辟新状态。该机制确保密集检索仅用于召回候选，而状态合并必须经过严格的结构重叠裁定。

2. 结果离散度驱动的结构歧义建模：识别部分可观测性与隐藏状态
传统探索算法假定状态观察是确定性的，而桌面环境中相似屏幕下的动作往往受隐藏变量（如剪贴板、异步时序）控制而表现出高方差。ScreenSearch 将合并状态 $s$ 下已观测到的动作签名集合记为 $\Sigma(s)$，将某一动作签名 $\sigma$ 的经验后继分布记为 $P(s' \mid s, \sigma)$。系统将所有动作的归一化经验熵加权平均，定义状态的固有离散度 $D(s)$；为了克服低采样计数下的过拟合，引入样本可靠性收缩因子 $\rho(s)$ 与先验值 $u_0 = 0.5$ 构造平滑歧义度： $$D(s) = \sum_{\sigma \in \Sigma(s)} w_{s,\sigma} \bar{H}\left(P(s' \mid s, \sigma)\right), \quad \rho(s) = \frac{n_s}{n_s + \kappa}, \quad u(s) = \rho(s) D(s) + (1 - \rho(s)) u_0$$ 其中样本权重 $w_{s,\sigma} = n_{s,\sigma} / n_s$，平滑超参 $\kappa = 20$。该指标直接捕捉相同操作导致的后继状态分歧，将感知混淆与系统异步转化为可计算的量化风险值，使智能体能显式识别出“看似熟悉却不可靠”的界面。

3. 单步 PUCT 图老虎机机制：无模拟回传下的全局分布式探索协调
在跨越数十台并行虚拟机的真实操作系统中，多步蒙特卡洛树搜索（MCTS）内部的虚拟回滚与树回传机制极度昂贵且受限于不可逆操作。ScreenSearch 摒弃多步回滚与模拟展开，创新性地提出了轻量高效的单步 PUCT 图老虎机（One-Step PUCT Graph-Bandit）。在已知状态 $s$ 下，智能体根据全局维护的访问计数 $N(s,\sigma)$ 和运行经验均值 $Q(s,\sigma)$ 贪心选取最佳动作： $$\sigma^* = \arg\max_\sigma \left[ Q(s, \sigma) + c_p P(\sigma \mid s) \frac{\sqrt{\sum_{\tilde{\sigma}} N(s, \tilde{\sigma})}}{1 + N(s, \sigma)} \right]$$ 其中 $P(\sigma \mid s)$ 为动作建议先验（可采用基于文本规则的启发式或离线扩散先验）。动作在真实操作系统中执行后，系统基于当前全局快照计算包含状态扩展、拓扑转移与歧义消除三维度的即时复合奖励： $$r(s, \sigma, s') = \lambda_{\mathrm{state}} \mathbb{I}[s' \notin V_t] + \lambda_{\mathrm{edge}} \mathbb{I}[(s, \sigma, s') \notin E_t] + \lambda_{\mathrm{amb}} [u(s) - u(s')]_+$$ 各系数均置为 1.0。全局数据库原子化递增 $N(s,\sigma)$ 并更新平均奖励 $Q(s,\sigma)$。不同虚拟机即使经由不同路径到达同一合并状态，也能共享该状态下的尝试成本与收益统计，从而协同压制低收益死锁分支并扩大高回报前沿。

4. 探针动作与单纯逃逸的因果辨识：防止平庸歧义消除
仅仅奖励歧义度下降 $[u(s) - u(s')]_+$ 可能会导致智能体采取逃避行为：例如在面临不确定性的文本框时直接点击“关闭窗口”，虽然进入了一个完全确定的桌面初始状态（低离散度），但并未揭示任何对任务有用的潜在状态信息。ScreenSearch 在机制设计中严格区分了探针动作（Probe）与伪逃逸（Escape）。真正的探针动作必须满足“操作可逆”且“能揭示隐藏上下文以显著提升后续依赖该状态的关键决策准确率”。通过反向剪贴板粘贴与撤销验证，系统在保证状态可控复原的前提下，使后续不可逆动作获得决策增益。

损失函数 / 训练策略¶

ScreenSearch 的在线探索阶段由上述无参数训练的单步 PUCT 驱动，无需价值网络预训练。而在离线轨迹转化阶段，系统从 5,524 小时的海量轨迹中抽取出高质量的三步状态转移窗口，构建反事实屏幕监督训练下游扩散策略（Diffusion Policy）。训练中固定用户任务目标文本 $g$，构造具有相同指令但屏幕环境或目标动作相异的反事实负样本对： $$\mathcal{L}_{\mathrm{policy}} = \mathcal{L}_{\mathrm{diff}}(\epsilon_\theta) + \beta \mathcal{L}_{\mathrm{contrastive}}(a_{\mathrm{pred}}, a_{\mathrm{target}}, S_t, S'_t)$$ 通过惩罚在不同界面状态下因任务文本相同而产生的盲目动作预测，迫使策略模型强行依赖当前屏幕的细粒度结构特征，从而在保持单步动作匹配精度的同时，将面对屏幕打乱时的敏感度大幅提升。

实验关键数据¶

主实验¶

论文在 Notepad、File Explorer 和 LibreOffice Calc 三个标准桌面应用上，设计了涵盖 150 个经验证的可重放起始状态（均匀分层覆盖低、中、高歧义状态）的基准评估。各方法在相同的 50 步动作预算下，评估新状态发现数、状态发现累积曲线面积（State AUC）、边发现累积曲线面积（Edge AUC）及状态重访率（Revisit）。

应用环境	选择策略 (均使用启发式先验)	新增状态数 (New States @ 50)	状态曲线面积 (State AUC)	边曲线面积 (Edge AUC)	净歧义变化 (Net $\Delta u$)	重访率 (Revisit Rate)
Notepad	PUCT (本文)	1.000	32.900	361.960	+0.0608	0.9796
	Greedy 基线	0.240	11.560	78.500	-0.0505	0.9951
File Explorer	PUCT (本文)	3.140	98.080	1,076.400	+0.0351	0.9357
	Greedy 基线	0.040	1.920	55.640	+0.0691	0.9992
LibreOffice Calc	PUCT (本文)	0.580	20.480	709.720	-0.0711	0.9882
	Greedy 基线	0.020	0.980	49.940	+0.0182	0.9996
宏观平均 (Macro-Avg)	PUCT (本文)	1.573	50.487	716.027	+0.0083	0.9678
	Greedy 基线	0.100	4.820	61.360	+0.0123	0.9980

消融实验¶

在固定的 150 个起始状态与候选动作池下，对探索目标函数的各个构成要素以及状态合并机制进行了全面消融，揭示了覆盖度与歧义消除之间的实际权衡关系：

探索配置与目标构成	新增状态数	状态 AUC	边 AUC	高歧义占比 (High-u occ.)	重访率	循环/卡死率 (Loop/Stall)
完整目标 (新颖性 + 歧义消除)	1.573	50.487	716.027	0.6568	0.9678	0.8593
仅新颖性 (Novelty Only)	1.427	46.347	901.533	0.4907	0.9705	0.8828
仅歧义消除 (Ambiguity Only)	1.047	34.300	761.987	0.6818	0.9786	0.9000
仅先验引导 (Prior Only)	2.233	71.867	982.900	0.7068	0.9544	0.8153
完整目标 + 均匀先验 (Uniform Prior)	4.733	132.527	1,094.720	0.7983	0.9028	0.6937
完整目标 + 严格精确匹配 (Exact Match)	2.100	67.847	997.240	0.6038	0.9570	0.8651

关键发现¶

PUCT 统计量对前沿扩展至关重要：在相同动作先验下，PUCT 较贪心选择将宏观平均状态 AUC 从 4.820 提升至 50.487（超过 10 倍增幅），边 AUC 从 61.36 提升至 716.03，成功避免了贪心策略陷入单一高频界面的严重锁死。
新颖性与歧义消除存在本质权衡：加入歧义消除项使状态发现 AUC 提升了 8.9%（从 46.347 提升到 50.487），并略微降低了卡死率，但边发现 AUC 相对纯新颖性有所回落。纯歧义消除由于过度拘泥于局部不确定性区域，状态发现能力明显不足；而纯新颖性虽然边覆盖多，但可能忽视了状态内部的潜在不可靠性。
因果探针验证了歧义度量的物理意义：受控实验表明，隐藏剪贴板内容（差异化分支）导致的离散度完全由跨环境条件差引起（组间离散度 1.000，组内为 0.000）；而异步更新延迟引起的离散度则全为组内噪声（组内离散度 0.971，组间为 0.000）。通过“可逆粘贴+撤销”这一有效探针，下游决策准确率由 50% 跃升至 100%，而无信息量的菜单点击无法带来任何增益。
反事实监督赋予策略真实的屏幕感知：下游扩散策略实验中，反事实屏幕配对训练使屏幕打乱敏感度提升了 3.70 个百分点，状态改变敏感度提升 4.50 个百分点，离线三步任务恢复率提升至 24.35%。

亮点与洞察¶

将单步图老虎机引入分布式 OS 探索：摒弃昂贵不可行的长序列 MCTS 展开，以极其轻量的方式复用 PUCT 置信上限，在真实不可逆桌面环境下实现了跨虚拟机的探索协同与去冗。
离散度作为无先验知识的歧义代理：无需预先建立复杂的状态转移概率模型或隐马尔可夫网格，仅凭匹配动作的多重后继经验熵就精准捕捉到了部分可观测性。
有界结构相似度与向量检索解耦：利用密集向量保证语义召回深度，利用离散网格原子与 Jaccard 硬阈值守护合并边界，为 GUI 大规模状态图拓扑提供了高可信度保障。

局限与展望¶

歧义代理缺乏单次因果归因能力：经验离散度无法区分分歧究竟源于关键的工作流隐变量、异步执行延迟、系统随机抖动，还是检索系统的合并误判，在无反复重放环境的实际在线部署中难以单次定性。
单步机制难以预见长程不可逆灾难：单步图老虎机缺乏对多步长远信息价值和不可逆破坏性动作（如格式化、删除系统文件）的前瞻推演，必须严格依赖沙箱与白名单限制。
依赖标准化控件树与静态渲染假设：当前表征高度依赖 UIA 自动化树或清晰的 OCR 文字，对于基于 WebCanvas 渲染、自绘 Direct2D 控件或高动态 3D 渲染界面的状态识别仍有待拓展。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将图老虎机与动作结果离散度结合应用于分布式桌面环境的自监督探索。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 11 个应用、5,524 虚拟机小时，兼具宏观大规模统计与微观受控因果探针消融。
写作质量: ⭐⭐⭐⭐⭐ 问题表述严谨克制，诚实呈现指标权衡，避免泛化的性能夸大。
价值: ⭐⭐⭐⭐⭐ 为计算机使用智能体（Computer-Use Agents）提供了极为宝贵的基础设施思路与状态表征范式。