OSExpert: Computer-Use Agents Learning Professional Skills via Exploration

The paper introduces OSExpert, a computer-use agent that leverages a GUI-based depth-first search exploration algorithm to discover action primitives and self-construct a skill curriculum, thereby significantly improving performance and efficiency on complex tasks to approach human expert levels.

The Gist

Imagine you hire a very smart, but inexperienced, intern to help you with your computer. This intern has read millions of books about how computers should work, but they've never actually opened the specific software you use at your job.

When you ask them to "Make a complex chart in this weird new spreadsheet program," they might guess. They click a button, see nothing happen, click another, get an error, and try again. They might eventually figure it out, but it takes them 50 tries and an hour of your time. A human expert, on the other hand, knows exactly which buttons to click and finishes in 2 minutes.

OSExpert is a new system designed to turn that clumsy intern into a master expert, but without you having to sit there and teach them every single step manually.

Here is how it works, using some simple analogies:

1. The "Maze Explorer" (GUI-DFS)

Most current AI agents try to solve a problem by guessing and checking while you watch. If they get stuck, they keep guessing.

OSExpert changes the game. Before it ever tries to help you, it goes into the software alone and acts like a maze explorer.

• The Analogy: Imagine the software is a giant, dark maze. Instead of wandering aimlessly, the AI uses a systematic map-making strategy (called a "Depth-First Search"). It goes down one hallway, opens every door, tries every lever, and writes down exactly what happens.
• The Result: It creates a complete "cheat sheet" of every single button, menu, and tool in the software. It learns that "Clicking the red scissors icon cuts the image," and "Clicking the blue 'File' tab opens the save menu." It does this for every function, building a massive library of "unit skills."

2. The "Recipe Book" (Skill Construction)

Once the AI has explored the maze, it doesn't just stop. It organizes its findings into a Recipe Book.

• The Analogy: Instead of remembering "Click here, then there, then wait," it writes down a clear recipe: "To save a file: 1. Click File, 2. Click Save As, 3. Type name."
• The Magic: If the task is complex (like "Make a chart and save it"), the AI doesn't guess. It looks at its Recipe Book, finds the "Save" recipe and the "Chart" recipe, and combines them. It knows exactly how to chain these steps together perfectly.

3. The "Specialized Tools" (Fine-Grained Actions)

Sometimes, a computer task requires extreme precision, like dragging a tiny object to a specific pixel or selecting a specific word in a sentence. Standard AI agents are often clumsy here, like trying to thread a needle with boxing gloves.

• The Analogy: OSExpert keeps a toolbox of specialized micro-tools. If it needs to cut a shape out of an image, it doesn't just "try to click." It pulls out a "Precision Cutter" tool from its database, uses it to trace the edge perfectly, and then puts the tool back.
• The Result: It can perform delicate tasks that usually cause other AIs to fail.

4. The "Know-Your-Limits" Check (Efficiency)

The biggest problem with current AI is that they keep trying to solve a problem even when it's impossible, wasting your time and money.

• The Analogy: Imagine a GPS that keeps telling you to turn left even though the road is closed, just because it's "trying harder."
• The OSExpert Fix: Because OSExpert has explored the maze and written down the Recipe Book, it knows exactly what it can and cannot do. If you ask it to do something that isn't in its book, it immediately says, "I can't do that," instead of wasting 10 minutes guessing. This saves a massive amount of time.

Why is this a big deal?

• Current AI: Is like a student who has to re-learn how to use a calculator every time they see a new model. They are slow, make mistakes, and get frustrated.
• OSExpert: Is like a professional who has practiced on that specific calculator until their fingers know the buttons by heart. They are fast, accurate, and efficient.

The paper shows that by letting the AI "play" with the software first to build its own knowledge base, it becomes 20% better at solving hard tasks and 80% faster (closer to human speed) than the best AI we have today. It turns a "guessing game" into a "masterclass."

Technical Summary

1. Problem Statement

General-purpose computer-use agents (CUAs), powered by large multimodal models, have shown promise in navigating digital environments. However, they fall significantly short of human expert performance in professional settings. The authors identify four critical gaps:

• Long-Horizon Tasks: Success rates drop sharply (from near-human levels to <10%) as task complexity and the number of steps increase due to error accumulation.
• Generalization: Agents struggle to adapt to unseen User Interfaces (UIs) or creative layouts not present in their training distribution.
• Fine-Grained Control: Agents fail at precise low-level actions (e.g., selecting specific text spans, pixel-perfect dragging, rotating objects by exact angles).
• Efficiency: Agents rely heavily on "inference-time scaling" (trial-and-error), resulting in 5–50× higher latency compared to human experts.

The root cause is identified as a lack of environment-specific procedural knowledge. Current agents rely on step-by-step planning without a repository of verified skills, leading to inefficient exploration and cascading errors.

2. Methodology: OSExpert Framework

OSExpert introduces a paradigm where agents autonomously learn and construct a skill set by directly interacting with the target digital environment before deployment. This process consists of three core technical innovations:

A. GUI-DFS Exploration Algorithm (Bottom-Up Discovery)

Instead of relying on human-curated tutorials, OSExpert uses a Graphical User Interface Depth-First Search (GUI-DFS) to systematically discover unit functions.

• Modules: The process involves three coordinated modules:
  1. Planning Module: Generates exploration plans and prepares inputs.
  2. Action Module: Executes UI interactions and analyzes screen states.
  3. Feedback Module: Evaluates state transitions, classifying them as Intermediate, Terminal (success), or Error.
• Process: The agent initializes a DFS stack. It explores UI elements, executes actions, and verifies outcomes.
  • Terminal States: Validated plans and action sequences are condensed into Unit Function Skills (e.g., "Bold selected text").
  • Error States: The agent retries with bounded attempts. If it fails, the error is recorded.
• Curriculum Construction: Once unit functions are discovered, the agent self-proposes a curriculum to compose these units into higher-level Composite Skills, effectively creating a procedural knowledge base.

B. Fast Planner & Skill Boundary Check (Efficiency Optimization)

To address inference latency, OSExpert deploys two mechanisms during the execution phase:

1. Single-Pass Fast Planner: Instead of iterative step-by-step planning, a lightweight LoRA-tuned language model generates a complete plan in a single forward pass based on the learned skill set. This reduces planning overhead and avoids error accumulation.
2. Skill Boundary Check: The agent maintains an explicit map of its capabilities. If a task maps to a "failed" skill (one that the agent could not complete during exploration despite retries), the agent terminates early and reports an error. This prevents wasting time on futile trial-and-error attempts (blind inference-time scaling).

C. Fine-Grained Action Primitives

To handle precise control tasks that standard agents fail at, OSExpert utilizes a database of action primitives.

• When the feedback module detects a need for fine-grained control (e.g., "select this specific text"), the agent searches the database for a suitable primitive (e.g., a script using pyautogui to drag-select).
• These primitives are executed with grounding verification. If successful, the procedure is added to the skill set for future reuse. This avoids the need for massive manual annotation of fine-grained data.

3. Key Contributions

1. OSExpert-Eval Benchmark: A new benchmark evaluating CUAs on four dimensions: Long-horizon workflows, Unseen UI generalization, Fine-grained action execution, and Execution efficiency. It contains 113 tasks across environments like GIMP, LibreOffice, Tableau, and a custom MiniWord editor.
2. Environment-Learning Paradigm: A shift from training on static human demonstrations to autonomous exploration where agents build their own skill sets without human curation for each environment.
3. GUI-DFS Algorithm: A systematic method for discovering and verifying unit functions and composing them into composite skills.
4. Efficiency Mechanisms: The combination of a single-pass planner and a skill-boundary check that significantly narrows the latency gap between agents and humans.

4. Experimental Results

The authors evaluated OSExpert against state-of-the-art agents (e.g., Agent-S3, OpenCUA, Qwen-3-VL) on the OSExpert-Eval benchmark.

• Performance Gains:
  • Success Rate: OSExpert achieved a ~20% absolute improvement in success rates compared to existing agents. While baseline agents hovered around 10% on long-horizon tasks, OSExpert reached ~30%.
  • Generalization: The agent demonstrated robust transfer to unseen UIs (Tableau, MiniWord) and reliable execution of fine-grained actions, areas where baselines often scored near 0%.
• Efficiency Gains:
  • Latency: OSExpert reduced the efficiency gap with human experts by ~80%.
  • Time: While human experts took ~18–48 seconds per task, existing agents took 160–1200+ seconds. OSExpert reduced this to 27–49 seconds, bringing it much closer to human speed.
• Ablation Studies:
  • The Skill Boundary Check was the primary driver of efficiency gains, preventing wasted time on impossible tasks.
  • The Fast Planner provided additional latency reductions.
  • Environment-specific skills were crucial for long-horizon and unseen UI tasks.

5. Significance and Impact

• Bridging the Expert Gap: OSExpert demonstrates that agents can approach human-level competence in professional software by learning procedural knowledge rather than just mimicking trajectories.
• Scalability: The framework reduces the reliance on expensive human annotation. Once the exploration phase is complete, the agent can operate efficiently across diverse tasks within that environment.
• Safety and Reliability: By explicitly defining skill boundaries and recording failure modes, the system avoids the "hallucination" of attempting impossible tasks, making it more reliable for real-world deployment.
• Future Direction: The paper suggests a shift from "building agents" to "building skills," offering a path toward adaptive, self-improving systems for software engineering, robotics, and general computing.

In conclusion, OSExpert represents a significant step toward expert-level computer use by combining systematic environment exploration with efficient inference strategies, effectively closing the performance and efficiency gap between current AI agents and human professionals.