Boosting Virtual Agent Learning and Reasoning: A Step-Wise, Multi-Dimensional, and Generalist Reward Model with Benchmark

Q1: Compared with more process reward models (PRMs) and outcome reward models (ORMs).
A1: Thank you for suggestions on more comparisons with more RMs, To our knowledge, our Similar is the first step-wise, multi-dimensional, cross-platform PRM for virtual agents (VA). PAVs[1] is a mathematical reasoning PRM that uses advantages as a single-dimensional reward. Math-shepherd[2] is a PRM for mathematical reasoning that uses soft estimation as a single-dimensional reward. Through experimentation, we found these RMs are not applicable as RMs for our proposed multi-dimensional, cross-platform VA tasks.

Following your nice advice, we try to apply these RMs in VA tasks in following comparative experiments:

The table shows that our model outperforms other RMs, likely due to its multi-dimensional scoring designed for VA tasks. In contrast, these RMs only provide either outcome rewards or single-dimensional process rewards, making them unsuitable for VA tasks.

[1] Setlur A, et al. Rewarding progress: Scaling automated process verifiers for llm reasoning. 2024.

[2] Wang P, et al. Math-shepherd: Verify and reinforce llms step-by-step without human annotations. 2023.

[3] Hunter L, et al. Let's Verify Step by Step. 2023.

Q2: Significance of gating network.
A2: The gating network (GN) balances the 5 dimensions, addressing multi-objective optimization challenges. For example, Task Relevance may dominate in instruction-following tasks, while Efficiency matters more in time-sensitive scenarios. The GN is not the focus of our research, but we will consider it in the future. The ablation experiments we have added show that removing the GN degrades performance, validating its necessity:

• Similar (w/o GN): AW SR = 33.7%, WA SR = 34.1%
• Similar (with GN): AW SR = 35.4%, WA SR = 38.2%

Q3: 4 benchmarks and more OOD experiments.
A3: Thank you for your suggestions on more OOD experiments. 4 benchmarks (WebArena, VisualWebArena, Android World, OSWorld) mentioned in our paper are widely recognized and cover the major real-world online interactive environments of Web, Android, Linux, and Windows, as well as real-world scenarios such as web navigation and app usage. Thus, we believe that these benchmarks can already reflect the situation of real scenes.

Further, as you nicely suggested, we supplement 3 OOD tests: Game of 24 (a mathematical puzzle unrelated to virtual agents), ScienceWorld (embodied science experiments), and 30 real-world Android tasks we designed (e.g., ordering bubble tea). Experimental results are shown below:

These results confirm our model’s scalability beyond the original benchmarks. We will include full details in the next version.

[4] Ruoyao W, et al. ScienceWorld: Is your Agent Smarter than a 5th Grader? 2022.

Q4: Helpfulness.
A4: We are sorry for not clearly explaining this dimension's definition. The Helpfulness quantifies each step's contribution to task completion by assigning values inversely proportional to the trajectory length. For example, each step in a 3-step successful trajectory is worth 1/3, while steps hindering progress (those failing to lead to success) receive corresponding negative values. To account for the compensatory relationship between helpful and harmful steps, we introduce an intermediate accumulator (AC) to track each step's cumulative influence throughout the trajectory.

Q5: Other inference-time scaling methods.
A5: Our model can seamlessly integrate with methods like majority voting and beam search. For example, we apply beam search as follows: 1) At each step, Similar scores k=5 candidate actions. 2) The top k=2 paths are expanded further, guided by our rewards. Additional experiments demonstrate this flexibility:

• Similar + Beam Search (k=5): AW SR = 34.1%, WA SR = 36.1%
• Similar + Majority Voting (N=10): AW SR = 34.3%, WA SR = 35.6%

Q6: Computational costs in data annotation and training.
A6:

Annotation: The 5 dimensions can directly derive from a single MCTS process. While MCTS introduces computational costs, we reduced them via pruning and limiting the number of rollouts (e.g., N=8).

• Generating 10k trajectories required ~15,000 GPT-4o API calls, and the total annotation time is ~80 hours
• Parallel MCTS rollouts with pruning reduced per-task latency by ~30%

Training: The model is trained on preference pairs using lightweight regression with Bradley-Terry loss.

• Training Similar on 78k preference pairs took ~100 GPU hours

Q1: Claim on no manual annotations.
A1: We appreciate to clarify a misunderstanding: our claim of "no manual annotations" means while utilizing the benchmarks' evaluation scripts (for dimension calculations), our method annotates step-wise multi-dimensional data without any additional human effort. 1) In fact, these scripts are all readily available and involve only simple result-based judgments - neither complex nor labor-intensive, just basic API calls. The human effort required to write these scripts is very limited. Notably, nearly all related works use these scripts. 2) In contrast, manually annotating the 110k step-wise multi-dimensional data provided by our automated annotation framework would require substantial human effort. Our experiments show even trained annotators can only process ~25 step-wise annotations/hour.

Further, we invited researchers to reproduce these evaluation scripts. We compared their completion time against our estimated time for manually annotating our 110k data:

The table shows the coding time for evaluation scripts is negligible (relative proportion 0.19%) compared to the manual time saved by our approach.

Q2: Evaluation in Tables 2 and 3.
A2: We rigorously ensured no data overlap between training (SRMTrain) and evaluation (4 benchmarks) sets by randomly splitting the original test tasks from WebArena(WA), AndroidWorld(AW), and OSWorld into 30% for our training data collection and 70% for evaluation (as detailed in Section 4).

We further validate the fairness of our configuration through OOD experiments (in our reply to Reviewer Evp4's Q3), demonstrating our model's robust performance on out-of-distribution data.

Q3: Total number of trajectories.
A3: Thank you for your question. We achieved 10k trajectories sampling by generating multiple distinct actions per step through task-specific prompt injection and stochastic exploration. For a 5-step task with 5 action variations per step, this theoretically yields $5^5=3125$ unique trajectories (before deduplication). In this way, we easily generated 10k trajectories.

Q4: Reliability of the test set.
A4: To ensure high-quality annotations, we collaborated with a professional commercial data labeling team. The process included: 1) Training Phase: Annotators underwent three rounds of iterative "label-review-feedback" cycles to clarify ambiguities of annotation (e.g., the complexity of UI interaction tasks). Only after achieving >95% accuracy on validation samples did formal annotation begin. 2) Formal Annotation: Each test sample in SRMEval was independently labeled by three annotators and three checkers. The final data in test set required >99% accuracy.

Besides, we find that high-performing RMs on SRMEval also boost agent performance across environments. This finding additionally validates the reliability of the test set (SRMEval), motivating the following comparative experiments:

As shown in the table, achieving better performance on SRMEval often leads to greater improvement in agent performance.

Q5: Effect of the five reward dimensions.
A5: Thank you for your suggestions regarding the 5-dimension weighting scheme. As shown in Tab. 4, Section 5.5 and Appendix E's ablation study, we found the 5 dimensions' relative importance follows approximately H > OS > E > TR > C. We find these dimensions show similar importance patterns in healthcare, education, and other fields[1].

Aligning with your insightful observation, we actually avoided using equal weights and instead adopted the weighted scoring scheme presented in Section 3.2: $5×H + 3×OS + 3×E + TR + C$, with weights based on empirical analysis. As you nicely suggested, we conducted additional experiments comparing different weighting schemes:

The table demonstrates that the dynamic weights strategy also achieves significant improvements, we will explore optimal weighting in future work.

[1] Hattie J. Visible Learning: A Synthesis of Over 800 Meta-Analyses Relating to Achievement. 2008.

[2] Aminul H, et al. Adaptive Weight Assignment Scheme For Multi-task Learning. 2023.

Q1: Benefit of SRMEval as a benchmark.
A1: Thank you for suggestions on more comparisons with other benchmarks. Section 1 of our paper proposes that SRMEval is the first multi-step, multi-dimensional, and multi-platform benchmark specifically for evaluating reward models(RMs) in virtual agents, featuring 32k professionally annotated preference pairs. Our Section 5.2 experiments further demonstrate its challenging nature. We summarize and compare the benefits of our RM:

Through experimentation, we find these benchmarks cannot evaluate RMs for Virtual Agent, which constitutes SRMEval's benefit. We find that high-performing RMs on SRMEval also boost agent performance across environments, which also indicates the benefit of SRMEval. Relevant experiments are in our reply to Reviewer sojt's Q4.

[1] Nathan L, et al. RewardBench: Evaluating Reward Models for Language Modeling. 2024.

[2] Enyu Z, et al. RMB: Comprehensively Benchmarking Reward Models in LLM Alignment. 2024.

Q2: AC and M.
A2: We are sorry for not clearly explaining the definition of our dimensions. And we appreciate the opportunity to clarify these terms:

• $AC$: Purely an intermediate computational variable with no standalone semantic meaning. It serves as a mathematical placeholder to recursively track cumulative Helpfulness scores during MCTS rollouts.
• $M$: Already defined in Section 3.1 under Helpfulness: "M is the total number of reasoning steps".

For a detailed explanation of Helpfulness, please refer to our reply to Reviewer Evp4's Q4.

Q3: Human evaluation details.
A3: Thank you for suggestions on more human evaluation details. The human evaluation details on how to train annotators and ensure data quality can be found in our response to Reviewer sojt's Q4.

The Human Acceptance in Appendix C is that, we randomly sampled data from SRM and asked trained annotators to verify these data. If the annotator considers a sample is correct, mark it as 1; otherwise, mark it as 0, and calculate Accuracy as Human Acceptance.

Q4: Sample size variation.
A4: The varying sample sizes occur because the five dimensions inherently contain different amounts of data. This stems from their fundamental design - for instance, Task Relevance and Coherence are binary values, which naturally yield fewer possible preference pairs.

The distribution of dimensions in SRM is roughly as follows:

We think dimensions with small amounts of data indicate weak discriminability and are easily trained for prediction.

Q5: Why is our model better than GPT-4o in SRMEval?
A5: We appreciate the opportunity to clarify "why our model performs better than GPT-4o":

• GPT-4o was only used to provide reliable labels for binary Task Relevance and Coherence dimensions in SRM construction. For SRMEval testing, GPT-4o served as a zero-shot reward model. It failed to accurately evaluate the three formula-based dimensions (Helpfulness/Odds of Success/Efficiency), causing unreliable predictions.
• Conversely, our dedicated reward model (Llama 3.2-V + SimilarRL) was trained on 78k multi-dimensional preference pairs using our Triple-M strategy. The model employs a purpose-built architecture with gating and regression layers for precise prediction of the benchmark's action pairs.

Q6: Pretrained MLLM and backbone.
A6: We used Qwen2-VL-7B-Instruct and Llama-3.2-11B-Vision-Instruct as frozen backbones (mentioned in Section 5.1) which are also the pretrained MLLMs.

Q7: Lack of qualitative analysis?
A7: We appreciate this suggestion. But in fact, we have provided qualitative analyses in: 1) Fig. 5: Illustrates how Similar guides the agent during both the training and testing phases. 2) Appendix D: Includes 6 visible detailed cases.

As you nicely suggested, we add textual descriptions of failure cases qualitative analysis, which we will continue to explore and improve our dimension weighting strategy in the future:

• Efficiency Misjudgment: Prioritized shortcut clicks over explicit menu navigation, even when shortcuts were contextually invalid.
• Coherence Over-penalizing: In a "file backup" task, our model incorrectly penalized opening a text editor and file explorer simultaneously, though both were necessary.

Q8: Writing issues.
A8: We thank you for the suggestions and will address these writing issues in the next version.