에이전트 알파: 컴퓨터 사용 에이전트를 위해 생성, 탐색, 평가를 통합한 트리 탐색

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

궤적(trajectory) 수준의 샘플링을 통해 테스트 시간 연산량을 확장하는 방식은 그래픽 사용자 인터페이스(GUI) 에이전트의 성능을 크게 향상시켰지만, 회귀 능력의 부재로 인해 부분적 성공을 재사용하거나 초기의 실수로부터 회복하는 것은 불가능했다. 본 논문에서는 단계(step)별 몬테카를로 트리 탐색(MCTS)을 통해 생성, 탐색, 평가의 시너지를 창출하는 통합 프레임워크인 '에이전트 알파(Agent Alpha)'를 소개한다. 이 프레임워크는 계획 공간(planning space)의 구조를 능동적으로 모델링하거나 활용할 수 있게 해준다. 에이전트 알파는 상호작용 루프에 alpha-UCT 유도 탐색을 통합함으로써 신중한 계획 수립을 가능하게 하며, 차선(suboptimal)의 분기를 조기에 가지치기하고 효율적인 접두사(prefix) 재사용을 촉진한다. 또한, 절대적 점수 편향을 완화하기 위해 비교 기반 평가를 도입하고, 압축적이고 유익한 탐색 공간을 유지하기 위해 다양성 제약 확장을 사용한다. Alpha-UCT의 후회 상한(regret bound)에 대한 분석도 제시한다. OSWorld 벤치마크에서 에이전트 알파는 약 77%의 최고 수준(state-of-the-art) 성공률을 달성하여, 동등한 연산량 조건에서 궤적 수준의 베이스라인 모델들을 크게 능가하였다.

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.