Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents

TL;DR

Agent Alpha unifies generation, exploration, and evaluation for computer-use agents through step-level MCTS: instead of sampling whole trajectories, it plans deliberately at every step — pruning suboptimal branches early and reusing successful prefixes. State-of-the-art ~77% success on OSWorld.

Key contributions:

• Alpha-UCT guided step-level tree search integrated into the GUI interaction loop, with a regret-bound analysis.
• Comparison-driven evaluation to mitigate absolute scoring biases, and diversity-constrained expansion to keep the search space compact and informative.
• State-of-the-art ~77% success rate on the OSWorld benchmark, significantly outperforming trajectory-level baselines under equivalent compute.

BibTeX

@misc{tang2026agentalpha,
      title={Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents},
      author={Sizhe Tang and Rongqian Chen and Tian Lan},
      year={2026},
      eprint={2602.02995},
      archivePrefix={arXiv},
      url={https://arxiv.org/abs/2602.02995},
}