Research map / Reinforcement learning / Visual and representation RL

ScreenSearch: Uncertainty-Aware OS Exploration

NeurIPS 2026 · Reinforcement learning › Visual and representation RL · approach: Novelty and impact-driven exploration · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ScreenSearch, a distributed desktop GUI exploration system that builds a shared deduplicated screen graph and uses a one-step PUCT graph-bandit with a matched-action outcome-dispersion ambiguity term to explore OS states.

Problem

Desktop GUI agents face partial observability: visually similar screens can hide different workflow states, so actions can have different outcomes. The paper asks how to explore computer/OS states efficiently while reducing ambiguity before committing.

Approach

Combine state and edge novelty with an empirical ambiguity score (normalized entropy of successor distributions for matched actions over near-duplicate screen clusters) in a one-step PUCT selector over a shared, hybrid-retrieval-deduplicated graph, without rollouts or multi-step backup.

Key results

• Across 3 matched applications with 50 starts each, PUCT raises macro-average state AUC from 4.820 (greedy) to 50.487.
• Adding the ambiguity term to novelty raises state AUC by 8.9% over novelty-only, with a trade-off against edge coverage.
• Counterfactual screen supervision raises screen sensitivity from 18.80 to 22.50 points and offline recovery from 21.68% to 24.35%.

Surprising findings

• Paste plus Undo raises commitment accuracy to 1.000 while menu navigation with equally low destination dispersion leaves it at 0.500, so low dispersion alone does not indicate a useful probe.
• On the three-start Notepad diagnostic, the GPT-5.4 mini reactive policy outperformed the PUCT graph-bandit on frontier AUC, and the context-enabled mini variant had the best frontier AUC.

Limitations

• Ambiguity score is an empirical structural proxy that cannot attribute dispersion to hidden state, timing, or merge errors without repeated condition labels.
• Primary matched policy study covers only three of 11 applications with a 50-action budget.
• Downstream policy metrics are teacher-forced offline proxies with low absolute three-step success; no live task completion evaluated.

Experimental setup

Datasets: ScreenSearch exploration traces across 11 applications Windows Settings three-step windows

Benchmarks: ScreenSearch matched replay-start suite (Notepad, File Explorer, LibreOffice Calc) Windows Settings downstream screen-conditioned policy eval

Metrics: new-state AUC edge AUC revisit rate loop/stall rate high-ambiguity occupancy net ambiguity change pair F1 recall@10 step match screen sensitivity

Baselines: Greedy selection with same prior Novelty-only objective Ambiguity-only objective Reactive GPT-5.4 nano Reactive GPT-5.4 mini Uniform prior

Builds on: PUCT AlphaZero POMCP Reciprocal Rank Fusion PP-OCRv4

Closest papers by meaning

• Reflection with Action-Induced Visual Differences for Desktop GUI Agents (NeurIPS 2026 · similarity 0.86)
• HATS: Hardness-Aware Trajectory Synthesis for GUI Agents (CVPR 2026 · similarity 0.84)
• GUI Exploration Lab: Enhancing Screen Navigation in Agents via Multi-Turn Reinforcement Learning (NeurIPS 2025 · similarity 0.84)
• HiconAgent: History Context-aware Policy Optimization for GUI Agents (CVPR 2026 · similarity 0.84)
• GUI-Xplore: Empowering Generalizable GUI Agents with One Exploration (CVPR 2025 · similarity 0.84)
• ProBench: Benchmarking GUI Agents with Accurate Process Information (AAAI 2026 · similarity 0.84)