Proposer-Agent-Evaluator (PAE): Autonomous Skill Discovery For Foundation Model Internet Agents

Thank you for your review and feedback on the paper. We have provided additional clarifications to the questions that you have raised on how PAE handles cases where the proposed task is infeasible, how the agent recognizes when to reuse a learned skill, and whether intermediate reward signals can help. Please let us know if your concerns are addressed and if so, we would appreciate it if you could re-evaluate our work based on this context. We are happy to discuss further.

However, failure analysis is limited—cases where PAE-generated tasks lead to incorrect generalizations or inefficient behaviors are not thoroughly discussed.

We actually do have comprehensive analysis in appendix B with manual classifications of the trajectories from each model. We have also provided qualitative examples of each failure mode in Figures 7-11. We will include them in a revised version of the paper.

How does PAE handle the situations where the proposed task is infeasible or ambiguous?

An important factor for PAE to choose to use vanilla REINFORCE without a baseline value function is that this loss function (line 239 in the manuscript) automatically takes care of the cases when the proposed task is infeasible or ambiguous. In these cases, the agent would not be able to finish the task and therefore can only get a reward 0. As shown in the loss function in line 239, if the trajectory reward is 0, it automatically zeros out the loss so it does not affect the training process, except a slight waste of sample efficiency during online trajectory collection.

Does the agent recognize when to reuse a learned skill versus learning from scratch? How does PAE facilitate long-term skill retention?

A crucial difference in skill discovery considered in this setting of web agents versus skill discovery in traditional hierarchical deep reinforcement learning [1, 2] is that most tasks that current sota open-source VLM web agents can complete are rather atomic and short-horizon (~10 steps), such as “Find the Easy Vegetarian Spinach Lasagna recipe on Allrecipes and tell me what the latest review says” as shown in appendix Figure 7. Under such a setting, skills are essentially equivalent to the tasks that the agents are practicing on so the issues of identifying new skills and long-term skill retention are not major concerns at this stage. However, as open-source models get more capable and are able to handle more complicated tasks, we believe that there will be more interesting research problems related to those concerns and the framework of PAE will serve as a foundation to facilitate such research.

[1] HIQL: Offline Goal-Conditioned RL with Latent States as Actions

[2] Data-Efficient Hierarchical Reinforcement Learning

Would intermediate reward signals improve agent learning?

The choice of the reward is actually an important ablation choice that we have made to maximize the exploitation of asymmetric capabilities of SOTA VLMs as skill proposers/evaluators and as agents. As shown in Figure 3, we found the use of sparse outcome rewards only achieved the best performance while other choices such as autonomous step rewards and functional evaluators tend to result in lower performances. Through a more careful inspection, we found that in many cases it would be very hard to give an accurate step-level reward because there can be multiple paths to solving the tasks. That said, we also believe that as the tasks get harder and models get more capable, how to exploit autonomous intermediate reward signals would be an important future direction to be explored.

Thank you for your review and feedback on the paper. We have included additional clarifications in the multi-turn nature of WebArena and WebVoyager, and details of computational efficiency. We are running additional experiments comparing different RL algorithms and we will share them here once we have preliminary conclusions. Please let us know if your concerns are addressed and if so, we would appreciate it if you could re-evaluate our work based on this context. We are happy to discuss further.

Experiments are only conducted on single-turn interactions on WebVoyager and WebArena. It would be beneficial to experiment with multi-turn interactive tasks or long-term interaction scenarios

To the best of our understanding, WebVoyager and WebArena environments are multi-turn and interactive environments where the agent needs to interact with the websites for a few steps (~10-20 steps) to be able to complete a task like “Find the Easy Vegetarian Spinach Lasagna recipe on Allrecipes and tell me what the latest review says” as shown in appendix Figure 7. While we agree that these environments are still relatively short-horizon in that most tasks require between 10-20 steps for successful executions, these are already the hardest interactive benchmarks on which existing open-source VLM web agents can achieve non-trivial performance results. We expect that more research in credit assignments over longer horizons would be possible in the future as the capabilities of open-source VLMs improve.

The paper lacks a detailed analysis of computational efficiency

Our main experiments of 7B models were conducted using 1 8x40G A100 and 3 8x24G A10G machines where the gradient update steps are performed on A100 only and A10G machines are only used for distributed data collection (i.e. trajectory rollouts). The trajectory collection phase takes around 90% of the training time while gradient updates only take 10%. The trajectory collection speed using all 4 machines is around 1k-2k trajectories per hour, so 7B experiments can be completed within 2 days. Our run of 34B model was conducted using 3 8x40G A100, where gradient update steps are performed on one of the A100 machines and all machines participate in trajectory collections. The training for the 34B model takes around 5 days under this setup. We will include this section in the appendix for the revised version.

The paper lacks comprehensive comparisons with other reinforcement learning algorithms and does not sufficiently explore performance differences with other LLMs.

The novel finding of this paper is to study whether an entire self-improvement framework of LLMs for web agents is possible and what the necessary design choices are. While additional RL results are good to have, because of the computational constraints discussed in the last response, we were unable to perform systematic tuning for other reinforcement learning algorithms like ppo and grpo with more hyperparameters and more sample complexity. Therefore, we refrained from drawing comparisons between different RL algorithms. With that being said, we are running additional experiments with PPO as the RL algorithm. We will share the results here once we have preliminary conclusions.

Thank you for your review and feedback on the paper. Just a gentle reminder that by the definition established by the ICML2025 committee, concurrent work includes all papers from within 4 months of the submission deadline. This applies to all other pipelines for web agents [1,2,3] with similar components (task proposers, agents, and evaluators). As such, they should not be considered as an established standard. With that being said, we also provide additional discussions on the differences with these works to address your concerns regarding novelty and also answer your other concerns below. Please let us know if your concerns are addressed and if so, we would appreciate it if you could re-evaluate our work based on this context. We are happy to discuss further.

Overall, the originality of this work looks somewhat limited to me

First, we would like to emphasize that while other pipelines [1,2,3] with similar components (task proposers, agents, and evaluators) have been applied to web agents because of the effectiveness of these components, they are all made public within 4 months of the submission deadline of ICML. As stated in the reviewer guideline of ICML, they should be considered as concurrent instead of an established standard and “Authors cannot expect to discuss other papers that have only been made publicly available within four months of the submission deadline. “.

Additionally, a key difference is that [1,2,3] generate instructions and evaluation rewards from stronger proprietary models such as GPT4o to train weaker models, while our PAE system focuses on exploiting the asymmetric capabilities of foundation model web agents to achieve self-improvements, where even weaker models can be used to improve the performance of stronger agents. We propose that this is a meaningful contribution, as it demonstrates a path to advance state of the art capabilities. In our main results, we have also performed extensive experiment analysis seeking to understand when such self-improvements are possible (the use of a reasoning step, the use of sparse outcome-based reward, different choices of the models etc) and how well such self-improvements can generalize (to unseen tasks and unseen websites). This is the novel finding of this paper.

[1] Nnetscape navigator: Complex demonstrations for web agents without a demonstrator, 2024. [2] Openwebvoyager: Building multimodal web agents via iterative real-world exploration, feedback and optimization, 2024b. [3] Webrl: Training llm web agents via self-evolving online curriculum reinforcement learning, 2024.

Using the original WebArena would give better comparisons across different papers.

In addition to experiments on WebArena Easy as reported in the main text, in appendix G Table 4 we also reported the performance of our models on the original WebArena using only screenshots as observations, and provided additional explanations in terms of why WebArena Easy is used as opposed to original WebArena. For your convenience, we also include results from Table 4 below. These results in Table 4 would be directly comparable with other papers testing screenshot-only models on WebArena. At the time when the main experiments of this paper were conducted, the best open-source VLM that we were able to train was LLaVa-Next but they were not able to achieve higher than chance performance (around 5%) for most of the websites on WebArena. In these cases, RL would be almost impossible because the base model does not perform meaningful explorations for these hard tasks.

The use of the term "skill" may not be appropriate in this context and may be replaced with a clearer term.

We used the term “skill” because most of the tasks that can be completed by open-source VLM web agents were restricted to rather short-horizon and atomic tasks like “find a chicken recipe with more than 4.8 reviews”. To avoid confusion, we will replace them with the term “policy” as suggested in the context.

The readability and presentation of the manuscript can be improved. Many of the tables and figures have too small fonts to read.

Thank you for the concrete advice on improving the presentation of the paper. We will increase the fonts in the updated version.