OS-Themis: A Multi-Agent Judge Framework for Training GUI Agents
Background: Why GUI Agents Need Better Critics
A GUI Agent is an AI system that operates a phone or computer interface on behalf of a user, tapping buttons, typing text, and navigating menus to complete real tasks such as ordering food, sending messages, or booking travel. Training such an agent with reinforcement learning requires a reliable reward signal, yet defining that signal is surprisingly hard.
Three common approaches each have drawbacks:
- Sparse reward: feedback is delivered only when the whole task finishes. The agent wanders in the dark for many attempts before stumbling on success.
- Dense, hand-crafted reward: every action is scored by human-written rules. Accurate, but expensive to author and hard to generalize.
- Automated critic: a model scores the agent's behavior. Scalable, but error-prone. Published critic systems report error rates around 20-30%, which means a large share of the agent's training signal is misleading.
- Milestone Decomposition: A lightweight language model breaks a task description into a sequence of verifiable milestones. For "set an alarm for 7 a.m. tomorrow" this yields checkpoints such as opening the clock app, entering the new-alarm screen, setting the time to 07:00, selecting the date, and saving.
- Multi-Expert Critics: Each milestone is routed to one of four specialist judges:
- Visual expert: evaluates on-screen layout and UI state.
- Text expert: checks typed strings and OCR output.
- Execution expert: inspects system state changes (records in a database, files on disk, app status).
- Logic expert: judges whether the agent's choices are consistent with task goals and whether alternative paths are acceptable.
- Review Mechanism: An attention-based aggregator fuses the experts' verdicts and their rationales, flags contradictions, weights by confidence, and emits a final score plus a human-readable evidence trail.
- Blurry screenshots: The visual expert cannot confirm the label on a button, but the execution expert confirms the system advanced to the next page; the reviewer trusts execution evidence and marks success.
- Alternative valid paths: Deleting a contact via the detail page is judged a success even when the reference path used long-press, because the core milestone (contact removed) was achieved.
- Conflicting experts: When the text expert misreads an OCR field while visual and execution experts agree, the reviewer down-weights the outlier and avoids a cascading training error.
- Compute cost rises by roughly 30% relative to a single critic.
- Milestone definitions still require human input for unusually complex or ambiguous tasks.
- Validation is currently limited to Android; portability to iOS, web, and desktop GUIs is future work.
- Game AI: milestones such as founding a base or researching a key technology.
- Robotic manipulation: milestones such as grasping, aligning, and assembling a part.
- Code generation: milestones such as syntactic validity, passing tests, and stylistic conformance.
- Zehao Li, Zhenyu Wu, Yibo Zhao, et al. *OS-Themis: A Scalable Critic Framework for Generalist GUI Rewards*. arXiv:2603.19191. https://arxiv.org/abs/2603.19191
- Rawles et al. *AndroidWorld: A Benchmark for Mobile GUI Agents*. arXiv:2405.14536
- Schulman et al. *Proximal Policy Optimization Algorithms*. arXiv:1707.06347
OS-Themis (named after Themis, the Greek goddess of justice) tackles this problem by replacing a single monolithic judge with a panel of specialists, coordinated by a review layer that produces auditable verdicts.
Key Points
1. From a Single Judge to a Panel of Experts
OS-Themis is built around three stacked layers:
2. Three Empirical Wins on AndroidWorld
Experiments on the AndroidWorld benchmark (113 tasks spanning alarms, email, shopping, and travel) report consistent gains:
| Scenario | Improvement vs. strong baseline | |---|---| | Online RL training (OS-Themis as reward) | +10.3% | | Trajectory filtering for dataset curation | +6.9% | | Offline evaluation as final scorer | competitive |
Ablations isolate the contribution of each component:
| Configuration | Online RL gain | Trajectory filter gain | |---|---|---| | Full OS-Themis | +10.3% | +6.9% | | Without milestone decomposition | +4.1% | +2.3% | | Without multi-expert critics | +3.7% | +1.8% | | Without review mechanism | +5.2% | +3.1% | | Single general-purpose critic | baseline | baseline |
The largest contributions come from milestone decomposition and the review layer.
3. Illustrative Failure Modes That OS-Themis Handles
4. Stated Limitations
5. Broader Implications
The architecture generalizes naturally to other domains where progress can be expressed as ordered checkpoints:
The paper also frames an old philosophical question in modern terms, *quis custodiet ipsos custodes* (who watches the watchmen?), and argues that the review mechanism provides a form of built-in self-supervision: experts that consistently disagree with the majority can be flagged for human inspection.