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

Sizhe Tang, Rongqian Chen, Tian Lan · 2026

Read Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents by Sizhe Tang, Rongqian Chen, Tian Lan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-02995.txt.

Introduction

Computer-use agents that can backtrack are introduced by Sizhe Tang and 2 co-authors in a 2026 paper. Interface agents improve by sampling whole trajectories, but they cannot reuse partial successes or recover from early mistakes. That lack of regressive ability wastes good prefixes and locks in bad first steps during long tasks.

Their Agent Alpha unifies generation, exploration, and evaluation in step-level tree search. An alpha-UCT rule guides the search, pruning weak branches early and reusing good prefixes. Evaluation compares options against each other rather than scoring alone, reducing bias. Expansion is constrained to keep the search compact. On the OSWorld benchmark, the agent reached a state-of-the-art success rate around seventy-seven percent, beating trajectory-level baselines at equal compute.

Catalog record

CREATORSizhe Tang, Rongqian Chen, Tian Lan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-02995

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents Sizhe Tang, Rongqian Chen, Tian Lan Abstract While scaling test-time compute through trajectory-level sampling has significantly improved Graphical User Interface (GUI) agents, the lack of regressive ability prevents the reuse of partial successes and the recovery from early missteps. In this paper, we introduce Agent Alpha, a unified framework that synergizes generation, exploration, and evaluation through step-level Monte Carlo Tree Search (MCTS). It enables active modeling or exploiting structures of the planning space. By integrating alpha-UCT guided search into the interaction loop, Agent Alpha enables deliberate planning, facilitating early pruning of suboptimal branches and efficient prefix reuse. We also employ comparison-driven evaluation to mitigate absolute scoring biases and diversity-constrained expansion to maintain a compact, informative search space. Regret bound of alpha-UCT is analyzed. On the OSWorld benchmark, Agent Alpha achieves a state-of-the-art success rate of ∼ \sim 77%, significantly outperforming trajectory-level baselines under equivalent compute. 1 Introduction Figure 1 : Overview of Agent Alpha. Agent Alpha could provide regressive planning that improve the utilization of generated trajectories with refined exploration and evaluation. We use nodes with deeper color to represent states with higher potential. \mathcal{T},\mathcal{R},\mathcal{I},\mathcal{O},\mathcal{C} denotes the information of trajectory, reflection, task instruction, observation, and operation context respectively. Existing approaches operate primarily as unidirectional processes without the ability to model or exploit structures of the planning space in complex dynamic environments. Agent Alpha addresses this by synergizing generation, exploration, and evaluation capabilities of MLLMs through step-level MCTS under Alpha-UCT bound. Test-time scaling strategies such as Chain of Thoughts (CoT) [ 32 ] Tree of Thoughts (ToT) [ 36 ] and Behavior Best of N (bBoN) [ 8 ] , have demonstrated remarkable potential in enhancing computer-use agents (CUAs) based on Multimodal Large Language Models (MLLMs). Yet, despite their reasoning capabilities, these scaling approaches face a fundamental limitation in complex dynamic environments: they operate primarily as unidirectional processes [ 25 ] without the ability to model or exploit structures of the planning space. In the absence of a mechanism to adapt to dynamic value feedback, existing methods cannot retrospectively evaluate the effectiveness of past actions, either to rectify course of actions when a suboptimal branch has been chosen, or to focus on sampling promising prefixes. Consequently, a single early misstep often cascades into an irreversible failure, preventing the agents from efficiently exploring and converging to the optimal solution. To address this, we introduce Agent Alpha, a unified framework that synergizes the generation, exploration, and evaluation capabilities of MLLMs through step-level Monte Carlo Tree Search (MCTS). By transforming linear execution into a regressive planning process, Agent Alpha maximizes the utility of every interaction and leverages evaluations to autonomously recover from early and compounding errors. By integrating search into the interaction loop, Agent Alpha enables fine-grained exploration that facilitates the reuse of promising action prefixes and the early termination of stalled progress. In particular, the search is guided by alpha-UCT bound that uses the maximum value on search-paths to augment exploration and takes into account dependent samples, caused by dependent evaluations and action generations (e.g., due to evolving context and dialog history [ 18 , 30 ] ). We model the predictive residual as a martingale difference sequence and derive a regret bound for Alpha Agent by establishing a predictive-corrective coupling between internal reasoning and external evaluation. Agent Alpha achieves a tighter confidence bound [ 7 , 11 ] than standard MCTS. This reduced variance enables the algorithm to prune suboptimal trajectories with significantly fewer samples, efficiently scaling up test-time performance. Our framework also introduces several methodological innovations designed specifically for the unique challenges of the computer-use domain. First, we propose the search-aware action generation mechanism, which allows agents to aggregate information from failed branches to refine its internal proposal distribution via cross-trajectory-information guided reflection. Second, to prevent the structural redundancy caused by the mode-seeking behavior of aligned models, we implement diversity-constrained expansion, using lexical normalization to construct a compact yet diverse search space. Third, we address the challenge of sparse reward signals in GUI navigation through comparison-driven consistent evaluation. By assessing sibling actions jointly rather than in isolation, our MLLM-based judgment obtains a discriminative relative signal that significantly reduces estimation bias and anchoring effects, otherwise commonly found in absolute scoring. Empirically, we evaluate Agent Alpha on the OSWorld benchmark [ 33 ] , the premier evaluation suite for multimodal computer control across diverse task scenarios. Agent Alpha establishes a new state-of-the-art success rate of \sim 77%, significantly outperforming trajectory-level scaling methods under comparable computational budgets. Our contributions are four-fold: • Agent Alpha synergizes generative, exploratory, and evaluative capabilities of MLLMs through step-level Monte Carlo Tree Search (MCTS), moving beyond unidirectional-process scaling. • We propose three novel designs for enhancing search-based CUAs, including action generation with tree-informed reflection, comparison-driven consistent evaluation, and diversity-constrained expansion. • We analyze the regret bound of Alpha-UCT and show that it achieves a tighter confidence bound and superior scaling efficiency compared to standard MCTS. • Our framework establishes a new state-of-the-art success rate of \sim 77% on OSWorld. 2 Background Computer-Use Agents General-purpose computer use is modeled as a Partially Observable Markov Decision Process (POMDP), defined by the tuple \mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\Omega,\mathcal{O}\rangle [ 5 ] . The environment state s_{t}\in\mathcal{S} represents the underlying status of the operating system and applications, which is not fully visible to the agent [ 4 , 6 ] . Instead, at each time step t , the agent receives an observation o_{t}\in\Omega through the observation function \mathcal{O}(s_{t},\mathcal{I}) , where \mathcal{I} denotes the user instruction. This observation o_{t} comprises the current screenshot and structured accessibility metadata, such as the accessibility tree. Recent literature has seen a surge in both general-purpose agentic frameworks [ 26 , 31 , 13 ] and specialized GUI agents [ 20 , 23 , 33 ] . The standard paradigm involves training or prompting a single policy model to generate a sequence of actions. Test-Time Scaling. Scaling test-time compute for agents has proven effective for enhancing the capabilities of large models [ 19 , 38 ] , typically through parallel sampling [ 43 , 8 , 39 ] or iterative refinement [ 16 ] . Step-wise parallel decision strategies often fall into vicious cycles that are difficult to break free from. Recent trajectory-level scaling methods like bBoN [ 8 ] , which prioritize global exploration but suffer from high computational costs and lack of information sharing among different trajectories. Although these methods improves the ability of agents in complex tasks, they have several shortcomings due to the framework structure: 1) They generate actions in the one-directional prediction, which lack of the regressive ability to do in-time error recovery; 2) The diagram of isolated scaling makes it inefficient to make use interaction information across trajectories; 3) Exploration in current methods is not optimized facing the huge action space of computer-use tasks, in which blind sampling can hardly achieve optimal performance. Monte Carlo Tree Search Monte Carlo Tree Search (MCTS) [ 12 , 42 , 40 ] is a heuristic search algorithm that builds a lookahead tree to estimate the optimal policy [ 24 , 28 ] . The search proceeds iteratively, where each iteration consists of four phases: Starting from the

Read the complete text