acceptodds
Under review as a conference paper at ICLR 2027

OS-Themis: A Scalable Critic Framework for Generalist GUI Rewards

Abstract

Reinforcement Learning (RL) has the potential to improve the robustness of GUI agents in stochastic environments, yet its effectiveness critically depends on the quality of the reward signals. Existing methods for constructing such rewards struggle to achieve both scalability and accuracy. We propose OS-Themis, a scalable multi-agent critic framework that decomposes trajectories into verifiable milestones to isolate evidence and audits the evidence chain before producing the verdict. Building on these milestones, we introduce Milestone-Credit Group Relative Policy Optimization (MC-GRPO), leveraging verified milestones for fine-grained intra-trajectory credit assignment in GRPO. We also introduce OmniGUIRewardBench (OGRBench), a holistic multi-platform benchmark for GUI outcome rewards, where OS-Themis consistently outperforms existing reward approaches across models. In online RL, OS-Themis with MC-GRPO improves AndroidWorld performance by up to 9.4%, with MC-GRPO bringing an additional 2.5-2.9% improvement over standard GRPO. We further build a scalable Android online RL infrastructure, where scaling training to 1,024 tasks yields a 10.7% improvement on AndroidWorld, demonstrating the potential of OS-Themis for scalable agent evolution.

Primary area:
foundation or frontier models, including LLMs
Keywords:
GUI Agents, Reward Modeling, Reinforcement Learning, Vision-Language Models, Online RL, Scalable Critic Framework

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_QfmSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on the reliability of reward evaluation and the long-term trajectory credit allocation issues in GUI Agent reinforcement learning, and presents three main contributions. Firstly, an OS-Themis multi-agent reward evaluation framework is proposed. Through key Milestone selection, visual evidence verification, and multi-agent review, reliable trajectory-level rewards and Milestone verification results are generated. Secondly, an MC-GRPO optimization algorithm is proposed. By further utilizing the Milestone information generated by OS-Themis, the Advantage of the standard GRPO is finely re-weighted, thereby improving the credit allocation within the trajectory. Additionally, the author has constructed OGRBench, a benchmark across five types of GUI platforms, for evaluating the trajectory-level judgment ability of the reward model. In terms of experiments, the author verified the effectiveness of OS-Themis through multi-model, multi-platform comparisons and ablation experiments, and verified the additional performance benefits of MC-GRPO through the AndroidWorld online reinforcement learning experiment. At the same time, scale expansion experiments demonstrated the scalability of the overall solution.

Critical strengths

The research topic holds significant practical importance. The paper focuses on the problems of unreliable reward evaluation and difficult long-trajectory credit allocation in GUI Agent reinforcement learning, and has strong research value. There is a natural connection between OS-Themis and MC-GRPO, and the Milestone information obtained during the reward evaluation process is further utilized for strategy optimization. The overall research idea is relatively complete.

The experimental coverage is extensive, and the performance improvement is quite convincing. The authors evaluated on multiple GUI platforms and different-sized base models, and verified the practical effect of the method through online reinforcement learning experiments. OS-Themis overall outperforms existing reward evaluation methods on OGRBench, and MC-GRPO also achieves an additional 2.5–2.9 percentage points of performance improvement compared to standard GRPO, indicating the practical effectiveness of the proposed solution.

The ablation experiments are quite rich. The authors analyzed the roles of components such as Selector, Verifier, and Reviewer, and verified the effectiveness of the key step selection mechanism through experiments such as random replacement and deletion of some Milestones. These experiments provide certain empirical support for the design of different components in the framework.

It has certain systematic and engineering value. The authors constructed the cross-platform reward evaluation benchmark OGRBench and built an Android online reinforcement learning system that supports parallel interaction and asynchronous reward evaluation. The scale expansion experiments and trajectory filtering experiments further demonstrated the application potential of this framework in actual GUI Agent training. In addition, the overall writing of the paper is clear, the organization is reasonable, and the appendix provides relatively detailed implementation explanations.

Critical weaknesses

OS-Themis mainly accomplishes the key steps selection, verification, and final reward judgment through the collaboration of multiple evaluation Agents. While MC-GRPO essentially builds upon the standard GRPO framework and reweights the original Advantage based on the Milestone verification results. The overall approach is somewhat related to the existing research on process rewards and fine-grained credit allocation, but the methodological innovation is relatively limited.

The key design of MC-GRPO lacks more targeted experimental verification. Although the authors demonstrated the effectiveness of MC-GRPO through comparisons with standard GRPO and ADMIRE, they have not fully explained the advantages of its specific weight function over other simple reweighting strategies. The existing experiments can prove the practical value of the Milestone-guided credit allocation, but they are not sufficient to fully demonstrate the necessity and independent contribution of the weight function itself.

The data quality verification of OGRBench still has room for improvement. This Benchmark has certain cross-platform coverage capabilities, and the data sources and construction processes are relatively clear. However, the paper does not provide sufficient details on the specific standards for manual review, sample selection process, and label quality control. Considering that OGRBench is one of the main contributions of the paper, a more systematic analysis of data reliability will help enhance its persuasiveness as an independent evaluation benchmark.

The reliability of the Milestone supervisory signals lacks direct verification. The OGRBench proposed in the paper mainly provides the final task success label for the complete trajectory to evaluate the accuracy of the reward model's trajectory-level judgment. However, MC-GRPO further relies on the key Milestones selected from the trajectory and their verification results to allocate the Advantage for different steps. Although the authors indirectly proved the effectiveness of these information through Milestone selection ablation experiments and downstream reinforcement learning experiments, they have not directly evaluated the accuracy of the Milestone selection and verification results themselves. Therefore, it is still unclear how reliable these fine-grained credit allocation signals are, and to what extent potential Milestone judgment errors will affect the optimization effect of MC-GRPO.

Questions for authors

MC-GRPO reweighted the Advantage of the standard GRPO based on the verification results of Milestone, achieving certain performance improvements. However, it is not clear to what extent this improvement is attributed to the specific weight function proposed by the authors. Can the authors further compare this weight function with simpler Milestone weighting strategies (such as fixed weights or linear reweighting) and verify whether it has additional advantages under the same Milestone information and normalization conditions?

The paper validated the effectiveness of Milestone information through ablation experiments on Milestone selection and downstream reinforcement learning results. However, the credit allocation of MC-GRPO not only depends on the selection of key steps but also directly on the Verifier's judgment of the success or failure of each Milestone. Existing experiments mainly evaluated the impact of these information on the final task judgment and training effect, but have not directly measured the accuracy of the Milestone-level verification results themselves. Can the authors provide corresponding validation accuracy analysis or further discuss the impact of Milestone judgment errors on the performance of MC-GRPO?

OGRBench integrates the execution trajectories of multiple existing GUI Benchmarks, providing a unified test benchmark for cross-platform reward evaluation. However, the unique evaluation value of this paper compared to existing Reward Benchmarks can still be further clarified. Additionally, Appendix C.2 shows that OS-Themis improved Precision on AgentRewardBench, but Recall significantly decreased. Can the authors further analyze the reasons for this performance difference?

4 comments
AuthorsOpenReview ↗

Response to Weakness 1: Methodological Novelty and Contributions

We thank the reviewer for the opportunity to clarify our contributions. The novelty of OS-Themis and MC-GRPO lies in their overall integration rather than individual components in isolation. Our work unifies reliable reward construction, fine-grained trajectory understanding, and policy optimization into a framework for GUI agent reinforcement learning.

1. Research significance and practical contribution. Reliable and generalizable reward acquisition remains a major bottleneck in GUI online RL. Long trajectories, complex state transitions, and heterogeneous environments make accurate reward evaluation difficult without task-specific rules or specialized reward models. OS-Themis addresses this challenge by extracting task-relevant evidence directly from GUI trajectories to generate outcome rewards without environment-specific evaluation scripts or successful reference trajectories. We further integrate it into a scalable Android online RL infrastructure, connecting trajectory collection, reward evaluation, and policy optimization. Its effectiveness is demonstrated through cross-platform evaluation on OGRBench, online RL experiments, and trajectory filtering.

2. Methodological innovation through unified architecture and structured reward construction. Rather than simply combining multiple evaluators or modifying GRPO, OS-Themis establishes a unified evidence-driven architecture that connects global outcome evaluation with local process supervision. Conventional outcome-based methods provide global task feedback but limited fine-grained guidance, whereas process-based methods provide intermediate signals that may not reflect final task completion. OS-Themis uses the same verified milestone evidence for both purposes, establishing consistency between reward determination and policy supervision.

More importantly, OS-Themis systematically organizes long GUI trajectories into task-relevant, visually verifiable state transitions, with iterative evidence auditing to identify missing requirements and distinguish intermediate progress from actual task completion. This transforms reward evaluation from coarse trajectory-level prediction into structured evidence construction and verification. The ablations in Tables 3 and 8, together with the matched-call-budget comparison in Table 14, support the effectiveness of this evidence organization.

Crucially, MC-GRPO further connects reward construction with policy optimization. Instead of discarding milestone evidence after generating the terminal reward or introducing additional process rewards, MC-GRPO reuses the verified milestones to redistribute the original GRPO advantage across actions. It preserves the terminal optimization direction and total signed advantage while providing fine-grained credit assignment, without additional evaluator calls for this purpose. This shared evidence representation avoids relying on independently constructed and potentially inconsistent supervision signals. As shown in Table 2, MC-GRPO further improves AndroidWorld performance by 2.5–2.9 percentage points over standard GRPO using the same OS-Themis evaluator.

AuthorsOpenReview ↗

Response to Weakness 2 and Question 1: Effectiveness of the MC-GRPO Weighting Function

We thank the reviewer for this constructive suggestion. To isolate the contribution of our weighting function, we conducted additional controlled ablations comparing MC-GRPO with simpler milestone-based weighting strategies.

Using Qwen3-VL-4B as the policy backbone, all variants reuse the same rollout trajectories and OS-Themis Qwen3−VL−235BQwen3-VL-235B evaluation results, with identical milestone selections, verification outcomes, terminal rewards, training configurations, and token-level advantage normalization. Only the weighting strategy varies:

  • Fixed Weights: Assigns weights of 1.2 and 0.8 to milestones whose verification outcomes agree and disagree with the terminal outcome, respectively.

  • Fixed Strength: Replaces the trajectory-adaptive factor ∣ri−pi∣|r_i-p_i| in Eq. 22 with a fixed coefficient shared across trajectories, retaining the original outcome-conditioned, centered weighting structure.

  • Shuffled Milestone Labels: Randomly permutes milestone verification outcomes within each trajectory while retaining the original weighting function and normalization.

The results are summarized below meanaccuracy±half−rangeoverthreeevaluationrunsmean accuracy ± half-range over three evaluation runs:

MethodAccuracy %
GRPO51.3 ± 1.3
MC-GRPO (Shuffled Milestone Labels)50.3 ± 1.7
MC-GRPO (Fixed Weights)52.3 ± 1.3
MC-GRPO FixedStrength,α=03˙Fixed Strength, α = 0\.352.7 ± 1.1
MC-GRPO (Ours)54.2 ± 0.9

Shuffling milestone labels reduces accuracy to 50.3%, below standard GRPO ∗∗513˙**51\.3%**, highlighting the importance of milestone-action correspondence. Both simpler weighting strategies outperform GRPO but remain below MC-GRPO ∗∗542˙**54\.2%**, with gains of 1.9 and 1.5 percentage points over Fixed Weights and Fixed Strength, respectively. In particular, the Fixed Strength comparison highlights the benefit of adapting credit redistribution strength to each trajectory rather than using a constant coefficient.

AuthorsOpenReview ↗

Response to Weakness 3 and Question 3: OGRBench Data Quality, Benchmark Contributions, and AgentRewardBench Generalization

We thank the reviewer for the constructive comments. We clarify three aspects of OGRBench and its evaluation results.

1. Data quality control. As described in Appendix G, OGRBench collects real GUI trajectories from five established benchmarks, retaining original environment-based success labels. We manually screen potentially unreliable trajectories based on three criteria:

  • Ambiguous instructions: Task success criteria cannot be reliably determined.

  • Environment-related failures: Persistent environment or infrastructure issues make tasks infeasible, rather than agent errors.

  • Incomplete records: Missing or corrupted screenshots, interaction logs, or other essential records prevent reliable evaluation.

These procedures distinguish genuine agent failures from task ambiguity, environment issues, and data corruption. We further employ stratified sampling to preserve task diversity and balance label distribution. The resulting benchmark contains 1,409 trajectories, including 700 positive and 709 negative samples. We will clarify these screening criteria and quality control procedures in the revised manuscript.

2. Distinctive value of OGRBench. Beyond aggregating existing trajectories, OGRBench provides a unified evaluation setting for GUI outcome reward models across heterogeneous platforms, tasks, and agent behaviors. As shown in Table 10, existing benchmarks have more limited platform coverage: AgentRewardBench focuses on Web, while CUARewardBench primarily covers Ubuntu. In contrast, OGRBench covers five platforms: Ubuntu 741741, Android 188188, Windows 213213, macOS 7777, and Web 190190. Its trajectories are generated by diverse GUI agents, including Qwen3-VL, UI-TARS, ScaleCUA, and Claude-Sonnet-4.5. Combined with consistent outcome annotations and a unified evaluation protocol, this diversity enables systematic evaluation of reward generalization across platforms and agent-generated trajectories.

3. Recall reduction on AgentRewardBench. To investigate this issue, we excluded trajectories generated by Claude-3.7-Sonnet, many of which lack explicit action rationales. The resulting subset contains 951 trajectories (243 positive and 708 negative). OS-Themis Qwen3−VL−235BQwen3-VL-235B achieves 75.66% Precision and 70.37% Recall, improving Recall by 15.97 percentage points over the full benchmark 544˙54\.4% while maintaining comparable Precision 761˙76\.1%.

This supports our analysis in Appendix C.2 that incomplete action-level information can hinder milestone construction and verification, making it more difficult for the Selector to identify intended subgoals and formulate appropriate verification targets. In our primary application, GUI online RL, action descriptions and interaction histories can be recorded directly during trajectory collection, providing the contextual information required by OS-Themis.

Furthermore, as discussed in Appendix A, reward precision is particularly important for policy optimization, since false-positive rewards may reinforce incorrect behaviors and introduce misleading training signals. OS-Themis therefore prioritizes precision while maintaining sufficient recall for effective learning. The subset results show that substantially higher Recall can be achieved while maintaining high Precision when more informative trajectory records are available.

AuthorsOpenReview ↗

Response to Weakness 4 and Question 2: Reliability of Milestone Supervision and Its Impact on MC-GRPO

We thank the reviewer for raising this concern. To directly evaluate milestone-level supervision, we conducted a human evaluation of 1,219 milestones from 200 trajectories. We sampled 100 trajectories from actual online RL rollouts and 100 from OGRBench, all evaluated by OS-Themis Qwen3−VL−235BQwen3-VL-235B. Annotators familiar with GUI environments were provided with the task goal, assignment goal, and before-and-after screenshots to assess milestone outcomes against the Verifier predictions.

The results are summarized below (accuracy is measured by agreement with human annotations):

Data SourceTrajectoriesMilestonesCorrectIncorrectAccuracy
Online RL Rollouts1004143714389.6%
OGRBench1008057267990.2%
Overall2001,2191,09712290.0%

The overall agreement with human annotations reaches 90.0%, with comparable accuracy on online RL rollouts 896˙89\.6% and OGRBench 902˙90\.2%, directly supporting the reliability of the milestone signals used by MC-GRPO.

Regarding the impact of milestone judgment errors on policy optimization, MC-GRPO constrains their influence through outcome-conditioned advantage redistribution. The terminal reward and trajectory-level GRPO advantage remain unchanged, while milestone outcomes only adjust the relative magnitudes of token-level advantages. The normalization in Eqs. 22–44 preserves each token's advantage sign and the total signed advantage within each trajectory. Thus, an incorrect milestone verdict affects relative credit allocation without changing the terminal reward or directly reversing the corresponding token-level optimization signal.

To further examine the importance of accurate milestone-action correspondence, we conducted an additional training ablation using the same Qwen3-VL-4B policy backbone, rollout trajectories, and OS-Themis evaluation results. Randomly shuffling milestone labels within each trajectory, while retaining the original weighting and normalization, reduces AndroidWorld accuracy from 54.2% to 50.3%, below standard GRPO 513˙51\.3%. This highlights the importance of preserving meaningful correspondence between milestone outcomes and their associated actions.

Table 8 provides further evidence: removing 25% of selected milestones reduces Recall by 11.16 percentage points and F1 by 8.03 percentage points, while random and final-step replacement also degrade outcome evaluation performance.

Reviewer_5FUoOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes OS-Themis, a multi-agent critic framework for GUI task evaluation. It selects and verifies task-relevant milestones, reviews the resulting evidence, and produces a terminal reward. The paper also introduces Milestone-Credit Group Relative Policy Optimization (MC-GRPO), which uses verified milestone outcomes to redistribute trajectory-level advantages across actions. Experiments on OmniGUIRewardBench, Android online reinforcement learning, and trajectory filtering demonstrate improvements in reward evaluation and downstream agent performance.

Critical strengths
  1. The paper addresses a practically important problem: obtaining reliable reward signals for GUI agents without developing task-specific evaluation scripts. Reusing verified trajectory evidence for policy learning is a useful direction.

  2. OmniGUIRewardBench covers mobile, desktop, and web environments, providing a useful resource for evaluating GUI outcome reward models across platforms.

  3. The evaluation connects reward prediction with downstream utility through online reinforcement learning and trajectory filtering, supported by component and milestone-selection ablations.

Critical weaknesses
  1. The conceptual novelty of milestones over existing process-reward-based RL is insufficiently established. Dynamically selecting subgoals and evaluating their completion can be understood as sparse process supervision with adaptive granularity. The paper mainly motivates this design by contrasting it with terminal rewards, which establishes the usefulness of local supervision but not its novelty over existing process reward methods. Although MC-GRPO differs from auxiliary reward shaping, the paper does not sufficiently clarify which fundamental limitations of prior process supervision the milestone mechanism resolves.

  2. The reliability of milestone-level supervision is not directly validated. The evaluation primarily measures final trajectory judgments and downstream policy performance, without directly assessing the completeness of milestone selection, the correctness of verification targets, or the accuracy of local verdicts. A correct terminal judgment does not necessarily imply correct intermediate supervision, since the Judge may compensate for errors in earlier stages. These intermediate signals are nevertheless used for MC-GRPO credit assignment, leaving their reliability as policy-training supervision insufficiently established.

  3. The framework introduces additional API/model-call costs and latency, while relying heavily on prompt design and a multi-agent workflow. Selection, verification, review, and final judgment require repeated VLM calls. Beyond this overhead, the method depends on detailed role-specific prompts and coordination rules. Its sensitivity to these design choices is not sufficiently analyzed, leaving uncertainty about whether the reported effectiveness transfers robustly across models and task settings without substantial prompt and workflow adjustment.

Questions for authors

Refer to the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Weakness 1: Novelty Beyond Existing Process Reward Methods

We thank the reviewer for the opportunity to clarify our contributions. The central contribution of OS-Themis is not merely adaptive milestone selection or sparse process supervision, but a unified framework that reuses verified trajectory evidence for both reward evaluation and policy optimization.

1. Research motivation and practical contribution. Reliable, generalizable reward acquisition remains a major bottleneck in GUI online RL. OS-Themis provides a unified pipeline for extracting task-relevant evidence from GUI trajectories and generating outcome rewards without task-specific evaluators or successful reference trajectories. We further integrate it into a scalable Android online RL infrastructure, connecting trajectory collection, reward evaluation, and policy optimization. Its effectiveness is demonstrated across five GUI platforms on OGRBench and through downstream online RL experiments.

2. Methodological distinction from conventional process supervision. Unlike approaches that independently assign process rewards or introduce auxiliary reward shaping, OS-Themis uses the same verified milestone evidence for two interconnected purposes:

  • Evidence-grounded outcome evaluation: The Selector identifies task-critical transitions, the Verifier checks their outcomes, the Reviewer audits the evidence, and the Judge determines task completion based on the overall objective. Thus, local progress is not directly equated with task completion.

  • Outcome-conditioned credit redistribution: MC-GRPO reuses verified milestones to redistribute the original GRPO advantage across actions, preserving the terminal optimization direction and total signed advantage without introducing additional process rewards.

This unified design is intended to mitigate several limitations of conventional process supervision. First, local success does not necessarily imply task completion. The Judge evaluates verified evidence against the overall task objective; removing it reduces Recall to 5.0% (Table 3). Second, dense step-level supervision may introduce weakly relevant evidence. OS-Themis instead selects task-critical transitions: Table 8 shows that full milestone selection provides a better overall balance than all-step verification, while random and final-step replacement degrade performance. Third, intermediate outcomes may conflict with terminal results. MC-GRPO uses terminal advantages to determine the optimization direction and milestone outcomes to adjust relative update magnitudes, preserving trajectory-level advantage through normalization Section 3\.4, Eqs\. 2–4. Table 2 demonstrates its improvements over GRPO and ADMIRE. Finally, the Reviewer and assignment-goal ablations in Table 3 highlight the importance of evidence auditing and explicit verification criteria.

In summary, our contribution lies in unifying structured evidence verification, reliable outcome evaluation, and evidence-guided credit redistribution, rather than introducing another form of sparse process reward. The same verified evidence supports both reward generation and policy optimization, without separate process rewards or additional evaluator calls for credit assignment.

AuthorsOpenReview ↗

Response to Weakness 2: Reliability of Milestone-Level Supervision

We thank the reviewer for raising this concern. To directly evaluate milestone-level supervision, we conducted a human evaluation of 1,219 milestones from 200 trajectories. We sampled 100 trajectories from actual online RL rollouts and 100 from OGRBench, all evaluated by OS-Themis Qwen3−VL−235BQwen3-VL-235B. Annotators familiar with GUI environments were provided with the task goal, assignment goal, and before-and-after screenshots to assess milestone outcomes against the Verifier predictions.

The results are summarized below (accuracy is measured by agreement with human annotations):

Data SourceTrajectoriesMilestonesCorrectIncorrectAccuracy
Online RL Rollouts1004143714389.6%
OGRBench1008057267990.2%
Overall2001,2191,09712290.0%

The overall agreement with human annotations reaches 90.0%, with comparable accuracy on online RL rollouts 896˙89\.6% and OGRBench 902˙90\.2%, directly supporting the reliability of the milestone signals used by MC-GRPO.

Our existing ablations provide further evidence:

  • Verifier (Table 3): Removing the Verifier reduces Accuracy by 6.1 percentage points and Precision by 15.6 percentage points, highlighting the importance of visual verification.

  • Milestone selection (Table 8): Removing 25% of milestones reduces Recall by 11.16 percentage points and F1 by 8.03 percentage points. Random and final-step replacement also degrade performance, supporting task-relevant milestone selection.

  • All-step verification (Table 8): Although it achieves higher Recall, Precision drops by 13.06 percentage points, indicating that indiscriminate step-level supervision can introduce weakly relevant evidence.

AuthorsOpenReview ↗

Response to Weakness 3: Computational Cost, Latency, and Generalizability

We thank the reviewer for raising these concerns. We clarify three aspects of OS-Themis:

1. Model-call costs. OS-Themis does not rely on proprietary commercial APIs. Instead, we use open-source Qwen3-VL models with self-hosted inference, allowing direct control over deployment costs and avoiding dependence on external API availability or pricing. As shown in Table 1, the Qwen3-VL series achieves strong performance under OS-Themis, demonstrating that effective reward evaluation does not require proprietary models. We also impose explicit limits on refinement, review, and retry rounds to bound the number of model calls AppendixK1˙Appendix K\.1. These additional calls serve an important purpose: GUI trajectories are often long, and critical failures may occur in only a few steps. A one-shot judgment can easily overlook such failures, producing false-positive rewards and misleading policy updates. The structured verification and review process helps mitigate this risk. Moreover, Table 14 shows that OS-Themis achieves 88.01% Accuracy, compared with 80.41% for ZeroGUI under a comparable 14-call budget, indicating that the improvement comes from structured evidence verification rather than simply increasing the number of model calls.

2. Evaluation latency. Our online RL infrastructure decouples trajectory collection from reward evaluation through asynchronous execution Section42˙1˙andAppendixH4˙Section 4\.2\.1 and Appendix H\.4. Completed trajectories are submitted for evaluation while other environment workers continue collecting rollouts, allowing reward computation to overlap with environment interaction. As reported in Appendix I, OS-Themis evaluation accounts for only 3%–3.4% of rollout time. Since environment interaction is the dominant cost in GUI online RL, this small evaluation overhead has minimal impact on overall training efficiency. Thus, the additional evaluation cost does not become a significant bottleneck in policy training.

3. Generalizability across models and task settings. Generalization is a central objective of our work and is extensively evaluated through OGRBench. The benchmark contains 1,409 real interaction trajectories across five GUI platforms: Ubuntu 741741, Android 188188, Windows 213213, macOS 7777, and Web 190190. These trajectories are generated by diverse GUI agents, including Qwen3-VL, UI-TARS, ScaleCUA, and Claude-Sonnet-4.5, covering different model architectures and execution behaviors.

We further evaluate OS-Themis using eight evaluator configurations, including five Qwen3-VL variants, GPT-5-mini, GPT-5, and Gemini-3-Flash, while keeping the same prompts and multi-agent workflow across all models without model-specific adaptation. As shown in Table 1, OS-Themis outperforms both DigiRL and ZeroGUI in overall Accuracy and F1 across all eight evaluator configurations, achieving a mean Accuracy of 81.6%, compared with 73.9% for ZeroGUI. These experiments validate generalization along two complementary dimensions: evaluating trajectories generated by diverse GUI agents across five platforms, and transferring the same evaluation framework across different underlying VLMs without modifying its prompts or workflow.

Reviewer_79QROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to produce reliable rewards for GUI agents from recorded trajectories. OS-Themis selects task-relevant milestones, verifies their visual state transitions, and uses a reviewer and a final judge to check whether the evidence supports task completion. MC-GRPO then reuses milestone outcomes to redistribute the magnitude of the trajectory-level advantage across action tokens while preserving its sign and total. The authors introduce OGRBench, with 1,409 trajectories across five platforms, and evaluate reward prediction, online Android RL, and trajectory filtering for SFT. With a Qwen3-VL-235B critic, OS-Themis reaches 88.0% accuracy on OGRBench; MC-GRPO adds 2.5–2.9 percentage points over GRPO using the same critic on AndroidWorld.

Critical strengths
  1. The critic is validated beyond agreement with a single benchmark. Table 1 covers several model families and five platforms, while Table 2 and Appendix D test whether the rewards actually improve agents through RL and data filtering. Appendix H.7 also compares the evolving critic rewards against rule-based success checks. This combination is consequential: it connects better reward predictions to useful policy improvement and checks that this relationship persists during training.
  2. The evidence-organization claim has meaningful controls. Table 8 compares selected milestones with random and terminal-near steps at the same step count, and Table 14 compares against 14-call ZeroGUI voting. Both favor OS-Themis by substantial margins. Together with the reviewer and assignment-goal ablations in Table 3, these results make a reasonable case that the gain comes from how evidence is organized, beyond simply making more evaluator calls.
Critical weaknesses
  1. The specific contribution of milestone credit remains under-tested. Section 3.4 assigns credit according to agreement between local and terminal outcomes, but a locally failed action can be recovered later, and a successful intermediate action can still be necessary in a failed trajectory. Table 2 shows a useful gain over uniform GRPO and ADMIRE, yet Table 8 tests milestone perturbations only for outcome prediction. There is no corresponding policy-training control with shuffled milestone labels or matched nonuniform weights. Moreover, the three runs in Table 2 are evaluations, rather than independent training seeds. These gaps leave uncertainty about whether the 2.5–2.9-point gain specifically reflects accurate local credit.
  2. The independent benchmark gives a narrower picture of generality. In Appendix C.2, Table 6, OS-Themis with Qwen3-VL-235B raises precision from 67.5% to 76.1% but lowers recall from 81.7% to 54.4% relative to the listed direct judge. The authors reasonably discuss missing action rationales, but such variation in trajectory metadata is relevant to a generalist reward framework. All downstream training demonstrations are on Android, so the practical effect of this substantial recall loss remains unresolved. I would like the generality claim to distinguish the strong OGRBench results from this less favorable transfer setting.
Questions for authors
  1. Under the Table 2 training setup, does MC-GRPO still outperform a control that shuffles milestone outcomes within each trajectory while keeping the same weights and normalization? Can you report variation across independently trained policies for this comparison?
  2. For AgentRewardBench, how much of the recall loss is attributable to missing rationales rather than the decision threshold? A breakdown by rationale availability, or a comparison at matched precision/recall, would help establish where the framework transfers reliably.
2 comments
AuthorsOpenReview ↗

Response to Weakness 1 and Question 1: Milestone Credit Assignment

We thank the reviewer for the constructive comments. We agree that locally failed actions may be recovered by subsequent operations, while successful intermediate actions may still occur in ultimately failed trajectories. These observations are consistent with the design of MC-GRPO. Rather than reversing the optimization direction based on local milestone outcomes, MC-GRPO adjusts only the relative magnitude of token-level advantages. The terminal advantage determines the optimization direction, while verified milestones guide intra-trajectory credit redistribution. Our normalization preserves both the sign of each token's advantage and the total signed advantage of the trajectory. Consequently, successful intermediate actions in failed trajectories receive smaller negative updates, while successful milestones in successful trajectories receive greater relative weight.

To further verify the contribution of milestone-guided credit assignment, we conducted additional controlled ablations using Qwen3-VL-4B as the policy backbone. All variants reuse the same rollout trajectories and OS-Themis Qwen3−VL−235BQwen3-VL-235B evaluation results, ensuring identical milestone selections, verification outcomes, and terminal rewards. Training configurations and advantage normalization remain unchanged, with only the weighting strategy varied. Specifically:

  • Fixed Weights: Assigns weights of 1.2 and 0.8 to milestones whose verification outcomes agree and disagree with the terminal outcome, respectively.

  • Fixed Strength: Replaces the trajectory-adaptive factor ∣ri−pi∣|r_i-p_i| in Eq. 22 with a fixed coefficient shared across trajectories, retaining the original outcome-conditioned, centered weighting structure.

  • Shuffled Milestone Labels: Randomly permutes milestone verification outcomes within each trajectory while retaining the original weighting function and normalization.

The results are summarized below meanaccuracy±half−rangeoverthreeevaluationrunsmean accuracy ± half-range over three evaluation runs:

MethodAccuracy %
GRPO51.3 ± 1.3
MC-GRPO (Shuffled Milestone Labels)50.3 ± 1.7
MC-GRPO (Fixed Weights)52.3 ± 1.3
MC-GRPO FixedStrength,α=03˙Fixed Strength, α = 0\.352.7 ± 1.1
MC-GRPO (Ours)54.2 ± 0.9

Shuffling milestone labels reduces accuracy to 50.3%, below standard GRPO ∗∗513˙**51\.3%**, highlighting the importance of milestone-action correspondence. Both simpler weighting strategies outperform GRPO but remain below MC-GRPO ∗∗542˙**54\.2%**, with gaps of 1.9 and 1.5 percentage points, respectively. This demonstrates the additional benefit of trajectory-adaptive weighting over fixed weighting strength.

All methods are independently trained from the same initialization under identical configurations, ensuring a fair comparison. Given the substantial computational and environment-interaction costs of GUI online RL, we prioritize controlled comparisons using the same initialization, training data, and evaluation protocol. The results consistently demonstrate the effectiveness of milestone-guided credit redistribution.

AuthorsOpenReview ↗

Response to Weakness 2 and Question 2: Generalization to AgentRewardBench

We thank the reviewer for highlighting the performance difference on AgentRewardBench. To investigate this issue, we conducted an additional analysis excluding trajectories generated by Claude-3.7-Sonnet, which frequently lack explicit action rationales.

The resulting subset contains 951 trajectories (243 positive and 708 negative). OS-Themis Qwen3−VL−235BQwen3-VL-235B achieves 75.66% Precision and 70.37% Recall, improving Recall by 15.97 percentage points over the full benchmark 544˙54\.4% while maintaining high Precision 761˙76\.1% on the full benchmark. This supports our analysis in Appendix C.2 that incomplete action-level information can hinder milestone construction and verification, making the Selector less effective at identifying intended subgoals and potentially leading to conservative outcome judgments.

Importantly, our primary application is GUI agent online RL, particularly with open-source policies. In these settings, action intentions, operation descriptions, and interaction histories can be recorded alongside screenshots during trajectory collection. OS-Themis relies on such explicit action-level context rather than access to hidden internal reasoning, making the required information readily available in our target RL settings.

Furthermore, OS-Themis prioritizes reward precision while maintaining sufficient recall for effective policy learning, as discussed in Appendix A. False-positive rewards can reinforce incorrect behaviors and introduce misleading policy updates, making precision particularly important in RL. The additional analysis shows that OS-Themis maintains high precision while achieving substantially higher Recall when more informative trajectory records are available.

Together with the cross-platform and cross-agent evaluations on OGRBench, these results support the broad applicability of OS-Themis and clarify the importance of trajectory information completeness for reliable reward evaluation.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We sincerely thank all reviewers for their careful and constructive feedback. Reviewers 79QR, 5FUo, and QfmS recognized the practical importance of reliable reward evaluation for GUI agents and the value of connecting verified trajectory evidence with policy learning. Reviewer 79QR particularly appreciated our comprehensive validation across reward prediction, online RL, and trajectory filtering, as well as the meaningful controls for evidence organization. Reviewer 5FUo acknowledged the significance of obtaining reliable rewards without task-specific evaluation scripts and the value of cross-platform benchmarking. Reviewer QfmS highlighted the broad experimental coverage, extensive ablations, and the systematic and engineering contributions of our scalable online RL framework.

We have carefully addressed the reviewers' concerns through additional experiments and detailed clarifications:

  • Reviewers 79QR and QfmS questioned the specific contribution of milestone-guided credit assignment and the proposed weighting function. We conducted additional controlled ablations using identical rollout trajectories and OS-Themis evaluation results. MC-GRPO achieves 54.2% Accuracy, outperforming shuffled milestone labels (50.3%), fixed weights (52.3%), fixed-strength weighting (52.7%), and standard GRPO (51.3%). These results support the importance of meaningful milestone-action correspondence and trajectory-adaptive credit redistribution.

  • Reviewers 5FUo and QfmS questioned the reliability of milestone-level supervision. We conducted a new human evaluation covering 1,219 milestones from 200 trajectories, including both online RL rollouts and OGRBench samples. Milestone verification achieves 90.0% agreement with human annotations, with consistent results on training trajectories (89.6%) and OGRBench (90.2%). Together with the existing milestone and component ablations, this provides direct evidence for the quality of the intermediate supervision signals used by MC-GRPO.

  • Reviewers 5FUo and QfmS raised concerns about methodological novelty relative to existing process reward methods. We clarified that our contribution extends beyond sparse process supervision or individual agent modules. OS-Themis establishes a unified evidence-driven framework that connects structured milestone verification, reliable outcome evaluation, and fine-grained policy optimization. MC-GRPO reuses the same verified evidence for credit redistribution while preserving the terminal advantage direction and total signed advantage, without introducing separate process rewards or additional evaluator calls for credit assignment.

  • Reviewers 79QR and QfmS questioned benchmark generalization and data quality. We clarified OGRBench's manual screening criteria, stratified sampling, and distinctive coverage of 1,409 trajectories across five GUI platforms, generated by diverse agent families. We also analyzed AgentRewardBench after excluding Claude-3.7-Sonnet trajectories that frequently lack action rationales. On the resulting 951 trajectories, Recall increases from 54.4% to 70.37%, while Precision remains high at 75.66%, supporting our analysis of the importance of complete action-level context for reliable milestone verification.

  • Reviewer 5FUo raised concerns about computational cost, latency, and transferability across models. We clarified that OS-Themis supports self-hosted open-source Qwen3-VL models and asynchronous reward evaluation, with evaluation time accounting for only 3%–3.4% of rollout time. Under a comparable 14-call budget, OS-Themis achieves 88.01% Accuracy, compared with 80.41% for ZeroGUI. Furthermore, using the same prompts and workflow across eight evaluator configurations, OS-Themis consistently outperforms DigiRL and ZeroGUI in overall Accuracy and F1, demonstrating its effectiveness across different underlying VLMs without model-specific adaptation.

We believe these additional experiments and clarifications strengthen the evidence for OS-Themis as an integrated, evidence-grounded reward framework that connects reliable GUI outcome evaluation with effective policy optimization. The additional experiments and corresponding analyses have been incorporated into the revised manuscript, with the new content clearly marked for ease of reference. We sincerely hope these efforts address the reviewers' concerns and respectfully invite the reviewers and Area Chair to reconsider their assessment of our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.