PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sizhe Tang, Rongqian Chen, Tian Lan

arXiv:2602.02995v1cs.AI

TL;DR

Trajectory-level test-time scaling improves GUI agents but lacks regressive ability to reuse partial successes and recover from early missteps. Agent Alpha addresses this gap with step-level MCTS that unifies generation, exploration, and evaluation, and it achieves about 77% success on OSWorld while outperforming trajectory-level baselines under equivalent compute.

  • Problem

    Trajectory-level scaling methods lack regressive ability to reuse promising prefixes and recover from early missteps in complex GUI environments.

  • Method

    Agent Alpha integrates step-level MCTS with Alpha-UCT, comparison-driven evaluation, and diversity-constrained expansion to unify generation, exploration, and evaluation.

  • Results

    ∼77% success rate is achieved on OSWorld, significantly outperforming trajectory-level scaling methods under comparable computational budgets.

  • Takeaways & Limitations

    Agent Alpha provides step-level regressive planning with error recovery, promising-prefix reuse, and early pruning of stalled or suboptimal branches.

  • Takeaways & Limitations

    Remaining failures are attributed to context fragmentation and memory loss during long horizons, environment-state reconstruction errors, and domain-specific knowledge gaps.

Abstract

from arXiv · show

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

Agent Alpha addresses the lack of regressive planning in trajectory-level GUI-agent scaling by combining step-level MCTS with generation, exploration, and evaluation. Its search designs support prefix reuse, branch pruning, and improved OSWorld performance under comparable compute.

  • Agent Alpha transforms unidirectional GUI-agent scaling into regressive planning through step-level Monte Carlo Tree Search.The framework synergizes generation, exploration, and evaluation to model and exploit planning-space structure.
  • Alpha-UCT uses maximum values on search paths and dependent samples to guide exploration with a tighter confidence bound than standard MCTS.The tighter bound is analyzed through a regret-bound framework and is intended to reduce sampling needed for pruning suboptimal trajectories.
  • Tree-informed reflection aggregates failed-branch information, while diversity-constrained expansion maintains a compact and diverse search space.These designs address redundant action proposals and use cross-trajectory information to refine generation.
  • ∼77% success rate is achieved on OSWorld, significantly outperforming trajectory-level scaling methods under comparable computational budgets.This is reported as a new state-of-the-art result.
  • Comparison-driven evaluation jointly assesses sibling actions to reduce estimation bias and anchoring effects associated with absolute scoring.The contribution list identifies comparison-driven consistent evaluation as one of three search designs for computer-use agents.

2 Background

Computer-use agents operate in partially observable environments where conventional action-sequence generation and trajectory-level scaling provide limited regressive recovery and cross-trajectory information sharing. MCTS supplies an iterative tree-search framework for selecting, expanding, evaluating, and propagating action values.

  • General-purpose computer use is modeled as a partially observable Markov decision process in which the underlying system state is not fully visible.The agent instead receives observations through an observation function.
  • A standard agent paradigm trains or prompts a single policy model to generate a sequence of computer actions.This describes the conventional general-purpose agent setup.
  • Trajectory-level scaling methods improve complex-task ability but lack regressive error recovery and information sharing across trajectories.The background characterizes these shortcomings as structural consequences of one-directional prediction and trajectory-level exploration.
  • MCTS iteratively selects tree nodes using UCT, expands unvisited children, estimates leaf values, and propagates them backward.The procedure builds a lookahead tree to estimate an optimal policy.

3 Methodology

Agent Alpha replaces single-pass GUI action generation with step-level tree search that reuses information across branches, constrains redundant expansion, and evaluates actions comparatively. Its Alpha-UCT design uses tree-wide statistics to guide pruning and search efficiency.

  • Unifying Generation, Exploration, and Evaluation: Agent Alpha builds an MCTS search tree with Selection, Expansion, and Back-Propagation, replacing reactive single-pass execution with deliberate planning.The initial task state serves as the root, and search continues until the budget runs out or tasks are completed.
  • Alpha-UCT and Regret Analysis: Alpha-UCT accounts for dependent samples created by evolving context and tree-level reflection, yielding tighter confidence bounds and more efficient pruning than standard MCTS.The framework’s theoretical analysis links predictive accuracy to search efficiency through reduced uncertainty.
  • Search-Aware Action Generation via Tree-Informed Reflection: Tree-informed reflection aggregates trajectories, observations, and node values from explored branches to refine later action proposals and address known failure modes.Trajectory information is inherited across search iterations, while reflections are regenerated at leaf nodes.
  • Search-Aware Action Generation via Tree-Informed Reflection: Action chunking groups repeated atomic actions and observations into longer-horizon transitions, allowing planning beyond a single action.The final state of the sequence is assigned to the transitioned node.
  • Diversity-Constrained Expansion: Independent sampling can create structurally redundant sibling branches, so normalized semantic representations enforce uniqueness during tree expansion.Normalization strips superficial formatting while preserving essential command elements such as coordinates and command types.

4 Experiments and Analysis

Experiments on OSWorld compare Agent Alpha with strong baselines and analyze its performance, efficiency, hyperparameters, and component choices. Agent Alpha reaches state-of-the-art performance, while ablations identify search settings and mechanisms that affect accuracy and runtime.

  • Main Results: Agent Alpha achieves a 77.29% average Success Rate on OSWorld, outperforming the strongest baseline by 4.71%.
  • Main Results: Agent Alpha attains the highest success rates in 7 of 10 categories, including 100% in VSCode and 96.15% in GIMP.
  • Comparison with SOTA: 64.27% versus 54.29% Success Rate, with higher Alignment Score and fewer average steps than Agent S3, but 1116.5s versus 313.37s average inference time.The comparison uses GPT-5-mini for both agents.
  • Hyperparameter Analysis: Expansion factor 5 and maximum 20 iterations provide strong performance before gains plateau, while broader search reduces successful trajectory depth.For long-horizon tasks, chunking 5 improves performance, whereas chunking 7 causes a drop.
  • Failure Analysis: Remaining failures arise from context fragmentation and memory loss, environment-state reconstruction errors, and domain-specific knowledge gaps.The analysis identifies long-term memory mechanisms as a future direction.
  • Ablation Study: Replacing the Comparative Judge with an Independent Judge reduces performance from 64.27% to 57.96%.
  • Ablation Study: Replacing Max backup with Mean backup lowers success rate to 45.42%, while Action Parallelism and Environment Parallelism provide 4.4x and 2.1x speedups.

5 Conclusion

Agent Alpha is presented as an MCTS-based framework for general-purpose computer-use tasks that uses step-level regressive planning to improve error recovery and prefix reuse. On OSWorld, it outperforms state-of-the-art baselines in success rate while supporting scalable and efficient test-time inference.

  • Agent Alpha uses Alpha-UCT and step-level regressive planning to support error recovery and prefix reuse in computer-use tasks.
  • Empirical results on OSWorld show higher success rates than state-of-the-art baselines together with strong test-time inference scalability and efficiency.

A Theoretical Proofs

The analysis models Agent Alpha’s value estimation with martingale-based concentration and quantifies how reflection reduces uncertainty. Its engineering design uses robust max-UCB selection, while efficiency gains arise from reflection and evaluation.

  • Theoretical setup: Agent Alpha’s regret analysis treats predictive residuals through martingale concentration and uses reflection to quantify variance reduction.The appendix explicitly frames the proof around concentration inequalities and the variance-reduction effect of reflection.
  • Theoretical setup: The framework uses robust max-UCB selection for engineering stability, while reflection and evaluation reduce the effective variance of value estimation.The paper distinguishes the selection criterion from the mechanism responsible for the core efficiency gain.
  • Theoretical setup: Agent Alpha assumes evaluation scores X_t lie in [0, 1] and uses a reflection prior as a predictor for each evaluation score.The uncertainty is governed by the conditional residual variance associated with prediction error.

A.2 Proof of Theorem 1

The proof derives Alpha-UCT’s confidence bound with Freedman’s inequality, then bounds suboptimal-arm sampling through standard UCT failure events and sums the resulting regret.

  • Proof of Theorem 1: The proof establishes concentration with Freedman’s inequality, derives suboptimal-arm sample complexity, and sums the resulting regret.These are the three stated proof steps.
  • Concentration bound: The martingale sum uses bounded deviations, while the predictor-induced residual variance controls the predictable quadratic variation.The analysis explicitly notes |X_k,a − μ_a| ≤ 1 and bounds variance using the predictor.
  • Concentration bound: With δ = T^-2, the empirical mean deviates from the true mean by at most the confidence radius with high probability.The bound is stated for every action’s empirical mean and confidence radius.
  • Suboptimal-arm analysis: Suboptimal actions can be selected only through optimal-arm underestimation, suboptimal-arm overestimation, or true means lying within twice the confidence width.These are the three standard UCT failure events used in the proof.
  • Suboptimal-arm analysis: The dominant regret contribution comes from the close-means event, which determines the samples needed to resolve each optimality gap.The other two events are bounded by δ = T^-2, while the third controls the necessary number of pulls.
  • Regret bound: Cumulative regret is obtained by weighting each action’s expected pulls by its optimality gap and combining the resulting bounds.The proof defines cumulative regret in this form before simplifying the final expression.

A.3 Proof of Corollary 2 (The Order of Regret Bound)

The corollary analyzes the dominant terms in the regret bound using the branching factor, minimum optimality gap, and maximum residual variance.

  • Parameterization: The asymptotic analysis identifies the branching factor K, minimum optimality gap Δ_min, and maximum expected residual variance as key parameters.The proof treats Δ_min as positive and problem-dependent while analyzing scaling behavior.
  • Parameterization: The proof bounds each term in the regret summation before deriving the asymptotic order.This intermediate step precedes the combined regret bound.

3. Constant Term: X

The simplified regret bound grows logarithmically with time, linearly with the action-space size, and linearly with residual variance. Perfect reflection removes the variance-dependent constant factor.

  • Constant term: The combined regret bound is simplified by treating gap parameters as problem-dependent constants and absorbing numerical factors into asymptotic notation.The analysis focuses on scaling with horizon T, branching factor K, and residual variance σ².
  • Constant term: Regret grows logarithmically with time T, linearly with action-space size K, and linearly with residual variance σ².This is the stated asymptotic dependence of the simplified bound.
  • Constant term: As residual variance approaches zero under perfect reflection, the logarithmic-time constant vanishes relative to standard UCT with fixed variance.The comparison is explicitly made against standard UCT.

A.4 Proof of Corollary 3 (Efficiency Gain)

The proof compares Alpha-UCT with standard UCT using variance-based regret terms. It establishes an efficiency ratio below one, indicating a tighter bound for Alpha-UCT.

  • Alpha-UCT is compared with standard UCT using asymptotic regret terms and Hoeffding’s inequality.Standard UCT uses a variance proxy σ2_raw = 1/4 for rewards bounded in [0, 1].
  • The efficiency ratio η is shown to satisfy η < 1.This establishes a lower asymptotic regret term for Alpha-UCT relative to the standard-U​​CT reference.

B.1 Task1: Can you make Bing the main search engine when I look stuff up on the internet?

Task 1 uses a short Chrome-domain search with fixed MCTS settings and successfully finds the solution at depth 5.

  • Task 1 uses 20 maximum MCTS iterations, expansion factor 3, and action chunking 1.The task is described as relatively simple and Chrome-domain specific.
  • The search successfully locates the solution at depth 5.

B.2 Task2: Help me export the first image from the doc file attached in the most recent email in Notes folder, and set this image as the new desktop background.

Task 2 is a long-horizon multi-app operation evaluated through an MCTS tree and successful-path screenshots. The surrounding system prompts govern planning, reflection, evaluation, stagnation detection, and alternative-path exploration.

  • B.2 Task2: Task 2 uses action chunking 5, 15 maximum MCTS iterations, and expansion factor 5.The generated search tree and screenshots of the successful path are referenced for this task.
  • B.2 Task2: The task’s MCTS tree highlights an optimal path, while trajectory visualizations show Task 2 across two parts.
  • System prompts: Reflection instructions identify repeated actions without progress as incorrect and require changing actions without prescribing a specific replacement.
  • System prompts: Evaluation prompts emphasize visible final-screen evidence, exact filenames, and verification of the requested task before completion.
  • System prompts: The planning prompt requires checking the initial environment, respecting navigation constraints, and aligning actions with the current website.
  • System prompts: Dynamic prompts require alternative actions when reflection reports problems and trigger deeper search or infeasibility analysis after extended unsuccessful exploration.
Loading 2602.02995v1…