VRL-Bench: Benchmarking agents on computer control tasks under finite trial budgets
Yu Bai and colleagues (Zhongguancun Laboratory, Tsinghua University and China Mobile) build VRL-Bench to compare verbal trial-and-error learning methods such as Reflexion under a fixed trial budget, and propose a scheduler that splits the budget between exploiting reflections and exploring.
Ask this paper
Fair comparison: All methods get the same finite number of trials on MiniWoB and WebShop with three models, and are compared against plain retry with no memory.
Mixed results: Each verbal-memory method beats memory-free retry in some settings and loses to it in others, and replay experiments show reflection can lower success.
VEX2: A language-model scheduler that selects policies and allocates the remaining trial budget is the only method with positive gains over retry in all six settings.
Abstract
Learning from trial and error is a promising way to improve language agents on complex tasks such as computer control. Reflexion introduced verbal reinforcement learning, which turns failed trials into text that guides later attempts without updating model parameters. We introduce VRL-Bench, a harness for fair evaluation of trial-and-error learning under finite trial budgets. Across three models on MiniWoB and WebShop, we evaluate updates from several prominent verbal-memory methods spanning Reflexion and later work: each improves observed success over memory-free retry in some settings but reduces it in others. Replay experiments show that using reflection can reduce success rates, revealing a trade-off between exploiting experience and continued exploration. We propose VEX$^2$, a verbal exploration--exploitation scheduler that uses a language model to jointly select policies and allocate the remaining trial budget. VEX$^2$ is the only evaluated update to achieve positive observed success-rate gains over retry in all six settings.