Improving Autonomous AI Agents with Reflective Tree Search and
  Self-Learning
Authors: name: Xiao Yu, name: Baolin Peng, name: Vineeth Vajipey, name: Hao Cheng, name: Michel Galley, name: Jianfeng Gao, name: Zhou Yu

Autonomous agents have demonstrated significant potential in automating
complex multistep decision-making tasks. However, even state-of-the-art
vision-language models (VLMs), such as GPT-4o, still fall short of human-level
performance, particularly in intricate web environments and long-horizon
planning tasks. To address these limitations, we introduce Reflective Monte
Carlo Tree Search (R-MCTS), a novel test-time algorithm designed to enhance the
ability of AI agents, e.g., powered by GPT-4o, to explore decision space on the
fly. R-MCTS extends traditional MCTS by 1) incorporating contrastive
reflection, allowing agents to learn from past interactions and dynamically
improve their search efficiency; and 2) using multi-agent debate to provide
reliable state evaluation. Moreover, we improve the agent's performance by
fine-tuning GPT-4o through self-learning, using R-MCTS generated tree
traversals without any human-provided labels. On the challenging VisualWebArena
benchmark, our GPT-4o-based R-MCTS agent achieves a 6% to 30% relative
improvement across various tasks compared to the previous state-of-the-art.
Additionally, we show that the knowledge gained from test-time search can be
effectively transferred back to GPT-4o via fine-tuning. The fine-tuned GPT-4o
matches 97% of R-MCTS's performance while reducing compute usage by a factor of
four at test time. Furthermore, qualitative results reveal that the fine-tuned
GPT-4o model demonstrates the ability to explore the environment, evaluate a
state, and backtrack to viable ones when it detects that the current state
cannot lead to success. Moreover, our work demonstrates the compute scaling
properties in both training - data collection with R-MCTS - and testing time.
These results suggest a promising research direction to enhance VLMs' reasoning
and planning capabilities for agentic applications via test-time search and
self-learning.