acceptodds
Withdrawn from ICLR 2027

CompGraphRL: Credit Assignment over Compressed Semantic State Graphs for Mobile GUI Agents

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Online reinforcement learning (RL) in open-ended environments has improved the planning and navigation capabilities of mobile graphical user interface (GUI) agents. However, long-horizon GUI tasks typically yield sparse terminal rewards, creating a severe temporal credit-assignment problem. Existing approaches either assign credit independently within trajectories or detect repeated states through exact observation or environment-state matching. As a result, they fail to identify semantically equivalent states under variations in rendering, dynamic content, and interaction history. We introduce CompGraphRL, a credit-assignment framework based on compressed semantic state graphs. CompGraphRL uses a vision-language model (VLM) to encode each observation jointly with the preceding action and interaction history, merging functionally equivalent states across trajectories into shared graph nodes. We further generalize Generalized Advantage Estimation (GAE) to graph-structured interactions by separately estimating node-level and action-conditioned edge advantages. This design propagates delayed rewards through the graph while providing fine-grained, low-variance signals for policy optimization. Large-scale online RL experiments on MobileGym, with cross-domain evaluation on AndroidWorld and MobileWorld, show that CompGraphRL consistently outperforms sequence-level and graph-based credit-assignment baselines across Qwen3.5 and GUI-OWL-1.5 backbones. With Qwen3.5-27B, it improves MobileGym success from 20.7% to 37.1% and the mean success rate on the two out-of-domain benchmarks from 31.9% to 44.9%. Further analysis shows that a node-merging rate of approximately 15% effectively balances cross-trajectory information sharing and state discriminability.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, credit assignment, semantic state abstraction, GUI agents

Reviews

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

This paper addresses sparse‑reward temporal credit assignment for long‑horizon mobile GUI agents. It proposes CompGraphRL: it leverages a frozen VLM to encode GUI states combining screenshot, prior action and interaction history, builds compressed semantic state DAGs, and generalizes GAE to graphs with separate node‑level and edge‑level advantage estimation. Evaluations run on MobileGym, with cross‑domain transfer tests on AndroidWorld and MobileWorld against sequence‑level (GSPO) and graph‑based RL baselines. Ablations and merge‑ratio analysis are also provided.

Critical strengths
  1. It properly targets two key GUI challenges: perceptually aliased states and functionally‑equivalent yet visually‑different screens. Moving past raw pixel‑based state matching is meaningful for GUI agent research.
  2. It includes backbone variants, cross‑benchmark generalization, ablations, and merge‑ratio diagnostics, showing clear improvements over compared baselines.
Critical weaknesses
  1. The main technical contribution is adapting existing GAE onto DAG structures. VLM‑based compression and merge‑budget controls are largely engineering tweaks. Prior graph‑credit‑assignment works already exist; incremental conceptual advances are modest for an ICLR submission.
  2. Performance hinges heavily on the frozen external VLM embedding quality and manually tuned target merge rate ρ_target. There is no adaptive scheme for choosing merge ratio, nor analysis on how bad VLM embeddings would break performance. Modified GiGPO/G2PO implementations also raise fairness concerns for comparison.
Questions for authors
  1. Why keep the VLM state encoder frozen? Have you tried jointly fine‑tuning it with policy? What results would we expect?
  2. ρ_target=0.15 is found via grid search. Can you propose an adaptive way to pick this hyperparameter? Would optimal values shift across different task suites?
  3. GiGPO and G2PO are modified to use image similarity in your setup. Could you provide results using their original logic for GUI settings?
  4. Your state graph is built offline after rollout collection. What are the main obstacles if you try incremental online graph construction?
4 comments
AuthorsOpenReview ↗

Response to Reviewer zLqi (Part 1 of 4)

Thank you for the constructive review. We appreciate your recognition that CompGraphRL targets two central challenges in GUI-agent learning: perceptually aliased states and functionally equivalent but visually different screens, and that our experiments include backbone variants, cross-benchmark generalization, ablations, and merge-ratio diagnostics.

We agree that the paper should state its conceptual contribution more sharply. Our claim is not that the main novelty is simply adapting an existing GAE estimator to a DAG. The central difficulty is that GUI agents operate in environments where the state identities assumed by prior graph-credit-assignment methods are no longer available. In symbolic or text-based settings such as ALFWorld or WebShop, repeated rollouts can often share a stable discrete or textual state key. In realistic GUI tasks, however, exactly repeated observations are rare: screenshots may differ because of system time, scroll position, dynamic content, cursor state, popups, notifications, input fields, or hidden app state, while still corresponding to the same functional state. Conversely, visually similar screens may require different actions depending on the previous interaction history. Thus, applying graph credit assignment to GUI agents first requires solving the state-equivalence problem: which non-identical GUI observations should share delayed credit, and which visually similar observations must remain separated.

From this perspective, the VLM-based state encoder is not an optional external enhancement, but the state abstraction mechanism that makes graph construction well-defined in GUI environments. Exact observation matching would produce almost no useful merges, reducing the method to trajectory-level credit assignment. Pure visual similarity is also insufficient, because it cannot reliably distinguish visually similar but semantically different task stages, or connect visually different but functionally equivalent screens. CompGraphRL therefore uses VLM semantic embeddings to construct comparable GUI state representations, then applies controlled graph compression to form a semantic state graph on which delayed rewards can be shared.

The contribution is the coupled mechanism rather than any isolated engineering tweak. Semantic state abstraction supplies a workable notion of node equivalence for GUI rollouts. Controlled state graph construction then turns these semantic relations into a reliable compressed graph by selecting high-confidence merges, preserving temporal consistency, and avoiding structurally invalid credit paths. Graph-GAE finally propagates delayed credit through shared semantic nodes and action-conditioned edges, while reducing the variance of advantage estimates on the compressed graph.

Our existing analyses support this interpretation. Section 4.3 compares VSC, ISC, and TSE against human semantic state groupings, showing that VSC is closest to human-labeled GUI state equivalence rather than being an arbitrary embedding choice. The same representation differences also affect downstream RL performance: weaker embeddings lead to over-splitting, where equivalent states fail to share delayed reward, or over-merging, where distinct task stages contaminate each other's credit. The Section 4.4 merge-ratio diagnostics further show the expected trade-off: moderate merging improves value sharing and delayed-credit propagation, while excessive merging introduces noisy credit and hurts policy learning. This is why the merge budget is part of the method's GUI-specific state-graph construction, not merely a hand-tuned cosmetic control.

To further isolate the sources of improvement, we have added a detailed ablation study in Section 4.5 of the revised manuscript. These experiments compare variants that replace the VSC semantic graph with alternative state graphs, remove learned value guidance, remove graph-GAE, and combine the same semantic graph with G2PO-style credit assignment. This allows us to separate the effects of GUI semantic graph construction, learned value guidance, and graph-GAE / edge-credit recursion more explicitly.

AuthorsOpenReview ↗

Response to Reviewer zLqi (Part 2 of 4)

Q1: Frozen VLM state encoder

Question. Why keep the VLM state encoder frozen? Have you tried jointly fine-tuning it with the policy? What results would we expect?

We first tried synchronously updating the VLM state encoder together with policy training. Empirically, this setting was very unstable: learning improved slowly at the beginning and only started to become better in later stages. We then considered whether this came from value-model initialization, and repeated the experiment using an already trained value model as the initialization. However, the training process remained unstable, with performance fluctuating across updates. Only after fixing the encoder/value parameters did we observe steady training improvement, and this trend held across multiple model sizes.

Our interpretation is that this stability is related to the objective used by our graph-GAE recursion. With uniform successor averaging, the value target is not intended to track the transition-frequency distribution induced by the current policy at every update. Instead, it is a branch-fair credit-propagation target for exploration-heavy GUI tasks, where low-frequency branches, including rare successful branches, should still participate in backward credit propagation. Therefore, the value model expected by this objective should not change with every policy update, which makes fixed parameters a better fit for this credit-propagation scheme.

For this reason, we use fixed VLM/state-value parameters when constructing and evaluating the compressed state graph. This keeps the semantic state space and graph value estimates stable while the policy is optimized, which was the first setting that produced reliable improvement in our experiments. In the revised manuscript, we will clarify this empirical observation and the connection to uniform successor averaging, rather than presenting freezing as the only possible design.

Q2: Adaptive merge budget and rho_target

Question. rho_target = 0.15 is found via grid search. Can you propose an adaptive way to pick this hyperparameter? Would optimal values shift across different task suites?

Yes. We agree that rho_target = 0.15 should be treated as a GUI-task empirical setting rather than a universal value. The optimal merge rate can shift across task suites depending on how often semantically equivalent states reappear, how noisy the visual observations are, and how well the embedding separates task stages.

The role of rho_target is to replace a poorly calibrated fixed embedding threshold with a more interpretable merge budget. In this sense, rho_target already functions as an adaptive threshold: for each batch of trajectories, candidate merges are ranked by similarity under temporal and acyclicity constraints, and the effective similarity cutoff is implicitly determined by the target merge rate and the current embedding distribution. In our GUI experiments, moderate merging improves value sharing and delayed-credit propagation; beyond the roughly 15% region, over-merge noise begins to dominate. We expect the best value to be lower in tasks with fewer repeated semantic states or weaker embeddings, and higher in tasks with many visually varied but functionally equivalent screens.

AuthorsOpenReview ↗

Response to Reviewer zLqi (Part 3 of 4)

Q3: Fairness of GiGPO/G2PO comparisons

Question. GiGPO and G2PO are modified to use image similarity in your setup. Could you provide results using their original logic for GUI settings?

We agree that this should be reported explicitly. The original GiGPO/G2PO logic relies on exact observation or environment-state matches. In mobile GUI settings, exact matches are extremely rare because screenshots change with system time, app content, scroll position, popups, cursor state, and hidden app state. Therefore, the original exact-match version forms very few useful merged nodes and tends to degenerate toward a trajectory-level sequence baseline. We will add original exact-match GiGPO/G2PO results in the appendix and clearly label the main-table versions as GUI-adapted baselines.

To further address fairness and isolate the source of improvement, we added a Qwen3.5-9B component-swap comparison under the same rollout, prompting, reward shaping, optimization budget, and evaluation protocol:

VariantGraphValueAdvantageMobileGym Succ. (%)Delta vs. Full
GSPONone / trajectoryGroup rewardGSPO sequence-level23.8 ± 1.2-6.6
G2POIAC graphRTGG2PO23.9 ± 2.4-6.5
G2PO + Semantic GraphVSC semantic graphRTGG2PO27.6 ± 0.8-2.8
G2PO + Semantic Graph + Learned VFVSC semantic graphLearned VFG2PO29.1 ± 1.2-1.3
CompGraphRL w/ IAC GraphIAC graphLearned VFGraph-GAE19.2 ± 1.5-11.2
w/o Semantic Graph & VFNone / trajectoryRTGTrajectory RTG22.6 ± 1.5-7.8
w/o Semantic GraphNone / trajectoryLearned VFTrajectory value-guided25.3 ± 0.8-5.1
w/o Learned VFVSC semantic graphRTGGraph-GAE25.0 ± 1.7-5.4
CompGraphRLVSC semantic graphLearned VFGraph-GAE30.4 ± 0.20.0

The component swaps give the following attribution. Replacing G2PO's IAC graph with the VSC semantic graph improves performance from 23.9% to 27.6%, showing that semantic grouping helps on its own. Adding the learned value function under the same semantic graph and G2PO advantage rule further improves performance from 27.6% to 29.1%, indicating that value prediction contributes a separate gain. Replacing G2PO's advantage rule with graph-GAE under the same graph and value setting improves performance from 29.1% to 30.4%, showing that graph-GAE adds another gain beyond semantic state information.

The IAC-graph swap also clarifies an important limitation. When CompGraphRL keeps the learned value function and graph-GAE but replaces the semantic graph with the IAC graph, performance drops to 19.2%, even below G2PO with the IAC graph (23.9%). This suggests that our value/graph-GAE pipeline is more sensitive to over-merging, and that graph-GAE is not automatically beneficial with an unsuitable graph.

Therefore, our revised conclusion is: semantic graph construction explains a substantial part of the improvement over G2PO, but the full CompGraphRL gain requires three aligned components--semantic graph construction, learned value prediction, and graph-GAE. In the revised manuscript, we will add this table to the Section 4.5 ablation study and use it to explicitly separate these component-level effects, thereby avoiding presenting Table 1 as evidence for full-system comparison alone.

AuthorsOpenReview ↗

Response to Reviewer zLqi (Part 4 of 4)

Q4: Offline graph construction and online extension

Question. Your state graph is built offline after rollout collection. What are the main obstacles if you try incremental online graph construction?

We view online or incremental graph construction as a valuable future direction. The current offline construction is mainly an implementation choice under the verl-style asynchronous training framework, where rollout generation and reward/value computation are separated rather than executed as a tightly coupled online loop. However, there are two practical obstacles in GUI environments:

  • Rewards and node values are delayed. For an intermediate GUI state, the value or process reward is often not reliable until the rollout outcome and subsequent trajectory are known. If we update nodes and edges online using only partial trajectories, we may assign high or low value to states before their downstream consequences are observed, which can inject noisy credit into later exploration.

  • GUI states are hard to reproduce exactly. Online graph expansion is most useful when the agent can return to a promising or uncertain node and resample alternative branches. In mobile GUI tasks, a state depends not only on the screenshot and action history, but also on app cache, account state, network responses, time, popups, background processes, and hidden UI state. Replaying the action sequence is often insufficient to recover the same state. Reliable online branching would require emulator- or VM-level snapshot and restore support.

For this reason, we view online graph construction in GUI tasks as a complex system-level problem that requires close coordination between the environment, snapshot/restore support, the rollout framework, and the value backfilling mechanism. We will add this discussion as an important direction for future research.

Planned revision

We will revise the manuscript in four ways in response to your comments. First, in the Introduction, we will sharpen the contribution statement to emphasize the coupled mechanism of GUI semantic state abstraction, controlled graph construction, learned value guidance, and graph-GAE credit recursion. Second, in the appendix, we will clarify the fixed VLM/state-value design and rho_target setting, including the instability observed under joint updating, the connection to uniform successor averaging, and why the best merge budget may vary across task suites. Third, in Section 4.5, we will add the component-swap comparison, report original exact-match GiGPO/G2PO results, and clearly distinguish GUI-adapted baselines from the original baseline logic. Fourth, in the Conclusion, we will add the online graph construction discussion as a future research direction, emphasizing that it requires coordinated environment, snapshot/restore, rollout-framework, and value-backfilling support in GUI tasks.

We hope these revisions address your concerns, and we would be grateful if you would consider updating your score if you find our response satisfactory.

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

CompGraphRL addresses credit assignment in mobile GUI reinforcement learning by sharing information across semantically related interaction states. A frozen VLM encodes the screenshot, preceding action, and interaction history; controlled cross-trajectory merging constructs an acyclic graph for each task query. A briefly pretrained, frozen value model and graph recursions produce node and transition advantages for policy optimization. The reported experiments train on MobileGym and evaluate on MobileGym, AndroidWorld, and MobileWorld using four policy backbones. Table 1 shows improvements over GSPO, including MobileGym success increases from 23.8% to 30.4% for Qwen3.5-9B and from 34.0% to 37.1% for Qwen3.5-27B. The main text also studies human-annotated state partitions, merge budgets, and graph/value ablations.

Critical strengths

A well-motivated representation of GUI decision context

Sections 3.2–3.3, pp. 4–5, lines 201–248, explicitly include the screenshot, preceding action, and interaction history in the state representation. The graph construction accepts a merge only when acyclicity is preserved and treats the requested merge rate as a budget rather than a guaranteed compression level. This design directly addresses visual variation and observation aliasing in GUI interaction while keeping the backward graph computation well defined. The controlled merge budget is a sensible way to limit harmful information sharing.

Encouraging results across policy families and evaluation environments

Table 1, p. 7, reports improvements over GSPO on all three benchmarks for Qwen3.5-9B/27B and GUI-OWL-1.5-8B/32B. For example, Qwen3.5-27B improves from 34.0% to 37.1% on MobileGym and from 62.0% to 71.0% on AndroidWorld. GiGPO and G2PO are also evaluated at both Qwen3.5 scales under shared rollout, shaping, prompting, and optimization settings. The breadth of the reported results makes the full-system improvement more persuasive than a demonstration on one backbone or only the training environment. Evaluation on AndroidWorld and MobileWorld provides useful evidence of transfer.

Useful analysis of when state sharing helps or hurts

Section 4.3 and Table 2, p. 8, compare six compression strategies against human partitions from 240 trajectories over 30 tasks. Figure 3 studies target merge rates and training dynamics. Table 3, p. 9, includes graph-only removal, value-only removal, and joint removal, reducing MobileGym success from 30.4% to 25.3%, 25.0%, and 22.6%, respectively. These analyses connect the method to interpretable failure modes and provide direct evidence that both major components contribute within CompGraphRL. The moderate merge-rate optimum is a practical insight for future work on state abstraction.

Critical weaknesses

The comparison with prior graph methods does not isolate semantic compression

isolate the benefit of semantic state compression

Source: Section 4.2 Main Results; PDF p. 7; manuscript lines 373–374.

Concern. The full-system comparison is valuable, but this particular interpretation is stronger than the controls establish. Section 4.1, lines 312–322, gives GiGPO and G2PO image-based grouping and explicitly withholds the proposed semantic compressor and learned value model; the credit rules also differ. Table 3 usefully tests graph and value guidance within CompGraphRL, but it does not determine how much of the improvement over existing graph methods comes from semantic grouping rather than the critic or the new recursion. This matters because the paper's central methodological claim concerns the source of the advantage over those methods.

Suggested clarification or experiment. Please add a compact component-swap comparison at Qwen3.5-9B scale: give the applicable graph baselines the same semantic state groups, and compare G2PO and CompGraphRL using the same value predictions where compatible. Holding rollout and optimization budgets fixed would make the attribution substantially clearer. If such a control is infeasible, please narrow the causal claim and explain the incompatibility.

The target of uniform successor averaging needs justification

expected advantage averaged over subsequent actions

Source: Section 3.4 Graph-based Credit Assignment; PDF p. 6; manuscript lines 280–281.

Concern. The recursions on pp. 5–6 deliberately average distinct successor nodes uniformly. That is a fully specified design choice, but it need not represent the current policy's expectation over subsequent actions and transitions. For example, a successor observed once and another observed seven times receive equal node-level weight; multiple actions leading to the same successor also do not create additional successor-set entries. This graph weighting may be useful for sharing rare outcomes, yet the main text does not define that intended estimand or show when it is beneficial. Because the resulting node advantage enters upstream edge advantages, the choice affects the learning signal rather than only the exposition.

Suggested clarification or experiment. Please state whether the recursion targets a policy expectation or an intentionally reweighted graph objective. A small controlled branching example and one ablation comparing uniform successor weighting with transition-frequency weighting, under the same graphs and critic, would establish the consequences at modest cost.

The reported variation does not clearly distinguish training and evaluation runs

same three evaluation seeds across all experiments

Source: Section 4.1 Experimental Setting; PDF p. 7; manuscript lines 359–360.

Concern. Using common evaluation seeds is a helpful control for MobileGym difficulty. However, Table 1 describes three random seeds, while Section 4.1 describes three evaluation runs; the main text does not clearly identify the number of independently trained policies or define the reported ± statistic. Consequently, it is unclear how much of the reported variation captures optimization, rollout collection, and graph construction. This is especially relevant to the smaller MobileGym gains at larger scales, such as 37.1±2.8 versus 34.9±0.6 for G2PO with Qwen3.5-27B. These numbers alone do not establish or refute statistical significance.

Suggested clarification or experiment. Please explicitly report the numbers of training seeds and evaluation seeds and define the error bars. If independent training repeats already exist, show the corresponding per-run paired differences. Otherwise, a repeated-training comparison for the principal Qwen3.5-9B result, evaluated with common task seeds and summarized with uncertainty over training runs, would materially improve confidence.

Questions for authors
  1. How much of the gain over GiGPO/G2PO remains when the methods share the same semantic grouping and, where compatible, the same value predictions?

  2. What distribution is uniform successor averaging intended to represent, and how does it compare with transition-frequency weighting on unevenly sampled branches?

  3. How many independently trained policies underlie each Table 1 result, what does ± denote, and what are the paired gains across those training runs?

3 comments
AuthorsOpenReview ↗

Response to Reviewer r24p (Part 1 of 3)

Thank you for the careful and constructive review. We appreciate your recognition of the motivation behind representing GUI decision context with screenshots, previous actions, and interaction history; treating the merge rate as a controlled budget rather than a guaranteed compression level; the consistent gains across model families and evaluation environments; and the analysis of when state sharing helps or hurts. These are exactly the issues CompGraphRL is designed to address: GUI interaction suffers from both visual variation and observation aliasing, and useful credit propagation requires state sharing that is semantic, controlled, and compatible with backward graph computation.

We agree that the original manuscript needs to state the source of the gain more directly. We therefore added a Qwen3.5-9B component-swap experiment that plugs our two main components into G2PO one at a time. First, replacing G2PO's IAC graph with our VLM-extracted VSC semantic graph improves MobileGym success from 23.9% to 27.6%, a +3.7 point gain. Second, adding our learned value function on top of the same semantic graph further improves G2PO from 27.6% to 29.1%, another +1.5 points. Third, replacing the G2PO advantage rule with our graph-GAE recursion under the same semantic graph and learned value setting improves performance from 29.1% to 30.4%, a further +1.3 point gain. These results show that all three components contribute: the VLM-based semantic graph provides a better trajectory graph, the learned value function provides better value prediction than G2PO's empirical return-to-go, and graph-GAE further reduces advantage variance and yields better advantage estimates than G2PO. We will add these new experimental results to the ablation study in Section 4.5.

For uniform successor averaging, we agree that the manuscript should state the intended objective more carefully. It is not intended to approximate the transition-frequency distribution under the current policy; rather, it is a branch-fairness choice for exploration-heavy GUI tasks. GUI trajectories are long-horizon and failure-dominated, so the agent must learn from many failed paths while preserving credit from low-frequency branches that may contain more informative actions, including rare successful branches. When designing graph-GAE recursion, our goal was therefore to let every explored successor branch participate in backward credit propagation, instead of further biasing value updates toward branches that the current policy already visits more often. Otherwise, high-frequency failure branches can receive larger recursive weight, while low-frequency but potentially valuable exploration branches can be drowned out. This distinction is especially important near the initial GUI states, where most trajectory-graph values are close to zero: uniform successor averaging avoids prematurely amplifying or suppressing early values according to the current policy's visitation frequency, which is also why we use fixed value/encoder parameters rather than parameters that drift with each policy update. To study how this choice differs from an empirical current-policy approximation, we also conducted a rebuttal-period experiment with frequency-weighted successor averaging, which weights successors by the observed transition frequency; as reported below, it does not show a significant difference from our current uniform version.

For the statistical reporting, we clarify that the three seeds reported in Table 1 are three evaluation seeds, not three independent training seeds. We used the same three evaluation seeds across methods because MobileGym difficulty is seed-dependent: changing the evaluation seed can change the instantiated goal, app content, and task instance, so common seeds provide a controlled comparison over task difficulty. We agree that the current wording in Section 4.1 and Table 1 does not clearly distinguish training repeats from evaluation runs or define what the reported ± statistic measures. We will revise all related descriptions throughout the manuscript and in addition, during rebuttal we added two more independent Qwen3.5-9B CompGraphRL training repeats, evaluated on the same three MobileGym seeds, to provide a repeated-training estimate of training-run variation.

AuthorsOpenReview ↗

Response to Reviewer r24p (Part 2 of 3)

Q1: Shared semantic grouping and value predictions

Question. How much of the gain over GiGPO/G2PO remains when the methods share the same semantic grouping and, where compatible, the same value predictions?

We decompose our method into three aspects, which also correspond to the main implementation differences between CompGraphRL and G2PO.

  • Graph construction. G2PO originally groups steps with the same observation. In our GUI implementation, because exact observation matches are rare, we use an IAC graph: two steps are grouped only when their screenshots are similar and their action categories are the same. CompGraphRL instead defines each state by the current screenshot, previous action, and interaction history, encodes it with a frozen VLM, and obtains a semantic compressed graph using a controlled merge budget.
  • Value estimation. G2PO computes discounted returns within each trajectory and averages the values of all constituent steps in each state group. CompGraphRL instead uses a well-learned value function over semantic embeddings, frozen during policy optimization.
  • Advantage estimation. G2PO uses its standardized advantage rules, including episode-level, node-centric, and edge-centric standardization. CompGraphRL uses recursive graph-GAE on the compressed DAG to compute node and action-conditioned edge advantages, allowing delayed rewards to propagate along graph edges.

To make the attribution clearer, we added a Qwen3.5-9B component-swap comparison under the same prompting, reward shaping, optimization budget, and evaluation protocol:

VariantGraphValueAdvantageMobileGym Succ. (%)
GSPONone / trajectoryGroup rewardGSPO sequence-level23.8 ± 1.2
G2POIAC graphRTGG2PO23.9 ± 2.4
G2PO + Semantic GraphVSC semantic graphRTGG2PO27.6 ± 0.8
G2PO + Semantic Graph + Learned VFVSC semantic graphLearned VFG2PO29.1 ± 1.2
CompGraphRL w/ IAC GraphIAC graphLearned VFGraph-GAE19.2 ± 1.5
w/o Semantic Graph & VFNone / trajectoryRTGTrajectory RTG22.6 ± 1.5
w/o Semantic GraphNone / trajectoryLearned VFTrajectory value-guided25.3 ± 0.8
w/o Learned VFVSC semantic graphRTGGraph-GAE25.0 ± 1.7
CompGraphRLVSC semantic graphLearned VFGraph-GAE30.4 ± 0.2

The component swaps give the following attribution:

  • Replacing G2PO's IAC graph with the VSC semantic graph improves 23.9% -> 27.6%, so semantic grouping helps on its own.
  • Adding the learned value function under the same semantic graph and G2PO advantage rule improves 27.6% -> 29.1%, so value prediction adds a separate gain.
  • Replacing G2PO's advantage rule with graph-GAE under the same graph and value setting improves 29.1% -> 30.4%, so graph-GAE adds another gain.
  • Replacing CompGraphRL's semantic graph with the IAC graph drops performance to 19.2%, even below G2PO with the IAC graph (23.9%). This suggests that our value/graph-GAE pipeline is more sensitive to over-merging, and graph-GAE is not automatically beneficial with an unsuitable graph.

Therefore, our revised conclusion is: semantic graph construction explains a substantial part of the improvement over G2PO, but the full CompGraphRL gain requires three aligned components--semantic graph construction, learned value prediction, and graph-GAE. We will add this table to the ablation study, thereby avoiding presenting Table 1 as evidence for full-system comparison alone.

AuthorsOpenReview ↗

Response to Reviewer r24p (Part 3 of 3)

Q2: Uniform successor averaging

Question. What distribution is uniform successor averaging intended to represent, and how does it compare with transition-frequency weighting on unevenly sampled branches?

Uniform successor averaging defines a distribution over distinct successor nodes rather than over transition samples:

\qquad \bar V_{\mathrm{unif}}(c_i)=\sum_{c_j\in\mathrm{Succ}(c_i)}q_{\mathrm{unif}}(c_j\mid c_i)\left(r_i^j+\gamma V(c_j)\right).$$ The frequency-weighted alternative instead uses empirical transition counts: $$q_{\mathrm{freq}}(c_j\mid c_i)=\frac{n_{ij}}{\sum_{c_k\in\mathrm{Succ}(c_i)}n_{ik}}, \qquad \bar V_{\mathrm{freq}}(c_i)=\sum_{c_j\in\mathrm{Succ}(c_i)}q_{\mathrm{freq}}(c_j\mid c_i)\left(r_i^j+\gamma V(c_j)\right).$$ Thus, for uneven branches with counts $n_{i1}=1$ and $n_{i2}=7$, uniform successor averaging assigns weights $(1/2,1/2)$, whereas frequency weighting assigns $(1/8,7/8)$. The submitted recursion therefore represents a branch-balanced graph target, not the current policy's empirical transition distribution. We also tested the frequency-weighted variant you suggested, using the same graphs and learned critic: | Successor averaging | MobileGym Succ. (%) | |---|---:| | Uniform successor averaging | 30.4 ± 0.2 | | Frequency-weighted successor averaging | 29.8 ± 0.2 | The difference is modest, likely because both variants use the same learned value function and the same compressed graph under rho_target = 0.15. We will add this ablation in appendix and clarify in the method section that uniform successor averaging is a branch-fair design choice, not an unbiased estimator of the current policy transition distribution. ## Q3: Training/evaluation variation and paired gains **Question.** How many independently trained policies underlie each Table 1 result, what does ± denote, and what are the paired gains across those training runs? During rebuttal, we added two independent Qwen3.5-9B CompGraphRL training repeats, giving three independently trained policies in total: | Training run | Description | Eval seed 42 | Eval seed 1 | Eval seed 2 | Mean ± std over eval seeds | |---|---|---:|---:|---:|---:| | Run 1 | Original run reported in Table 1 | 30.5 | 30.1 | 30.5 | 30.4 ± 0.2 | | Run 2 | Additional independent training run | 29.7 | 30.1 | 28.9 | 29.6 ± 0.5 | | Run 3 | Additional independent training run | 31.6 | 31.2 | 30.1 | 31.0 ± 0.6 | | Across-run summary | Mean ± std over all 9 evaluations | | | | 30.3 ± 0.7 | Where corresponding repeated-training baselines are available, we will report paired run-level gains. Where they are not available, we will avoid making statistical-significance claims from evaluation-seed variation alone. We will revise Table 1 and the experimental protocol to explicitly report the number of independently trained policies, the number of evaluation seeds/task instances, and the definition of ±. ## Planned revision We will revise the manuscript in three ways in response to your comments. First, in Section 4.5, we will add the component-swap comparison and narrow the attribution claim so that the gain is described as arising from semantic graph construction, learned value guidance, and graph-GAE recursion together. Second, in Section 3.4, we will further clarify that uniform successor averaging is a branch-fair graph objective rather than an empirical transition-frequency estimator, and we will add the frequency-weighted successor-averaging ablation in the appendix. Third, we will revise the experimental reporting to make clear that the original reported seeds are evaluation seeds, distinguish evaluation-seed variation from training-run variation, and add the independent training-run variation experiment in the appendix. We hope these revisions address your concerns, and we would be grateful if you would consider updating your score if you find our response satisfactory.
Reviewer_ysAaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Within this manuscript, the authors propose a way to give mobile GUI agents denser, lower-variance learning signals during online reinforcement learning. It does this by merging equivalent screens from different rollouts into a shared graph and propagating credit over that graph.

In this work, each state is defined as the previous action, the current screenshot and the interaction history. A frozen Qwen3-VL-4B model encodes it into an embedding, and states are compared by cosine similarity. Because action and history are included, pixel-identical screens at different task stages stay separate. States from the 8 rollouts of the same query are merged into shared nodes, and actions become directed edges. Merging is capped by a target merge rate rather than a similarity threshold. Merge candidates are ranked with penalties for being far apart in time or late in an episode. The authors extend Generalized Advantage Estimation to the graph. The edge advantages distinguish different actions taken from the same merged state. These step-level advantages then go into a GRPO-style clipped objective with a KL penalty. A small value model is pretrained briefly and then frozen.

Per reported experimental result, with Qwen3.5-27B, on MobileGym, the success rises from 20.7% to 37.1%, and AndroidWorld reaches 71.0%.

Critical strengths

Within the manuscript, the authors report somehow comprehensive experimental results, including four backbones, up to 32B parameters, as well as in-domain plus out-of-domain benchmarks.

The authors also tried to allocate the concrete reason why existing graph-based credit assignment fails in GUI environments, and two hypothesis proposed, equivalent screens rarely repeat exactly, so exact matching finds almost nothing to share, and identical screens can sit at different task stages.

Critical weaknesses

My major concern regarding the work is about compression and merging. First of all, even though multiple prior arts were using this mechanism already, it won't relax the vulnerability of this design in real-world setting:

Within single "page" there could be multiple visual similar screen time, which means differently towards Agent or RL-learning trajectory, that shall not be treated together or similarly. The case will be the same even you loop actions into the merging, per there usually are multiple actions on a single "page". In other words, I'm not so sure merging or clustering design shall be a straight forward gain towards RL, or adding extra noisy reward.

Further more, within the manuscript, the compression-quality study uses one similarity threshold across very different embedding spaces. All strategies share a cosine threshold of 0.95 across image, text and VLM embedding spaces. Those spaces have very different similarity distributions. A fixed threshold therefore mostly measures how each embedding space happens to be calibrated at 0.95, not how good its representation is. The other strategies’ over-merging may be an artifact of this choice.

Questions for authors
  1. How much does each input (screenshot, previous action, history) contribute to merge quality? An ablation of VSC without history or without the previous action would show whether the history component is what resolves perceptual aliasing. Along with the question, what is really given to Qwen3-VL-4B for each state?

  2. Can the authors leverage more regarding the clustering algorithm, that it is not clear to me after two clusters merged, the cluster centers are recomputed before scoring or not. Also, how the similarity thresholding and the merging budget relate to each other.

2 comments
AuthorsOpenReview ↗

Response to Reviewer ysAa (Part 1 of 2)

Thank you for your thoughtful comments. We agree with your observation that real GUI environments often contain perceptually similar screens that correspond to different task stages. This is exactly the setting that CompGraphRL is designed for: the goal is not to merge states by visual appearance alone, but to merge states that correspond to the same semantic embedding across different rollouts.

When multiple trajectories reach similar milestone states, merging them allows the learned value of that milestone to become more consistent across trajectories, which improves value fitting and reduces the variance of delayed credit assignment. As you correctly point out, however, state merging also has a negative side: excessive merging can introduce incorrect equivalence relations and noisy rewards. Therefore, our method influences the original RL algorithm in two directions: better value fitting from appropriate state sharing, and possible reward noise from over-merging.

To analyze this trade-off, we introduced the merge ratio and studied its relationship with model performance. As shown in Section 4.4, mild state merging improves the policy, while excessive merging causes a clear performance drop. This directly addresses your concern and clarifies the intended operating region of CompGraphRL: under-merging loses useful value sharing, whereas over-merging is more harmful because it creates wrong credit assignment.

Regarding your question about compression quality, we agree that different embedding spaces have very different similarity distributions. Section 4.3 is therefore not meant to claim that one universal threshold is optimal for all spaces. Instead, it asks a controlled question: under the same condition, which representation is most consistent with human-labeled state equivalence? We inspected the similarity distributions of the compared methods and found that 0.95 is an appropriate threshold for analyzing the agreement between embedding spaces and human annotations in this setting.

The observed similarity distribution is as follows:

Method0-0.60.6-0.650.65-0.70.7-0.750.75-0.80.8-0.850.85-0.90.9-0.950.95-1.0
VSC151759156390923277023921454164096
VSC without history44812181341140841537814554649444586
VSC without history and previous action003060121866950853269876172
ISC641212511768246125923659340534466464
TSE011834019505337821586046993

The relationship between Sections 4.3 and 4.4 is progressive. Section 4.3 shows that, at a fixed threshold, VSC has the highest consistency with human labels, while also suggesting potential over-splitting or over-merging issues under fixed-threshold compression. Based on this observation, Section 4.4 further studies the merge ratio and identifies a better operating region that balances improved value fitting from state merging against noisy rewards from over-merging.

AuthorsOpenReview ↗

Response to Reviewer ysAa (Part 2 of 2)

Q1: Contribution of screenshot, previous action, and history

Question. How much does each input (screenshot, previous action, history) contribute to merge quality? An ablation of VSC without history or without the previous action would show whether the history component is what resolves perceptual aliasing. Along with the question, what is really given to Qwen3-VL-4B for each state?

For each state, our implementation uses the current screenshot together with previous action and history as the input context, and feeds this context to Qwen3-VL-4B to generate the state embedding. The generated embedding is then used for candidate merge scoring. We will describe the exact details in the Experimental Setting section.

We added the requested ablation by removing history and then removing both history and previous action:

MethodARI ↑NMI ↑VI_norm ↓Hom. ↑Comp. ↑Precision ↑Recall ↑F1 ↑
VSC, screenshot + previous action + history0.6760.8450.1900.9660.7570.9190.5940.705
VSC without history0.6770.8480.1910.9790.7560.9110.5940.703
VSC without history and previous action0.5610.7990.2400.9010.7440.8180.5800.606

This result is somewhat beyond our initial expectation. We originally assumed that adding longer interaction history would consistently improve state disambiguation, and therefore did not include this ablation in the submitted manuscript. The new result shows a more nuanced picture: removing history keeps ARI, NMI, and F1 almost unchanged. In contrast, removing both history and the previous action causes a much larger drop. The current result suggests that the most recent action may contribute more than the longer interaction history in the present setting. We will add this ablation study and the corresponding analysis to the appendix in the revision.

Q2: Clustering algorithm, similarity thresholding, and merge budget

Question. Can the authors leverage more regarding the clustering algorithm, that it is not clear to me after two clusters merged, the cluster centers are recomputed before scoring or not. Also, how the similarity thresholding and the merging budget relate to each other.

As described in Section 3.3, CompGraphRL performs controlled cross-trajectory merging. Candidate pairs are first filtered by similarity, then ranked by an adjusted score that combines cluster-center cosine similarity with temporal constraints. Importantly, after two clusters are merged, the implementation recomputes the merged cluster center and updates the trajectory-round statistics before any later candidate scoring. This update rule can be directly seen in the code, and we will make it explicit in the revised manuscript to avoid ambiguity. The merge budget is the main control variable. The fixed threshold only defines a candidate pool, while the target merge rate ρtarget\rho_{\mathrm{target}} caps the number of accepted merges, with Bmerge=round⁡((N−Ninit)ρtarget)B_{\mathrm{merge}}=\operatorname{round}((N-N_{\mathrm{init}})\rho_{\mathrm{target}}). Thus, ρtarget\rho_{\mathrm{target}} is an upper bound rather than a guaranteed final compression rate.

This design avoids hand-tuning a single global threshold whose effect may drift across embedding distributions. Instead, each rollout set can induce its own effective cutoff after ranking and temporal penalties, while keeping the same merge budget. This also matches Section 4.4: over-merging is more harmful, and a mild target merge rate around 15% best balances value fitting from state sharing against noisy rewards from excessive merging.

Planned revision

We will revise the manuscript in three ways in response to your comments. First, we will provide a more detailed explanation of Sections 4.3 and 4.4, and make their respective purposes and connection clearer so that there is no ambiguity about why both analyses are needed. Second, we will add the input-component ablation above to the appendix, describe exactly what is given to Qwen3-VL-4B for each state, and discuss the somewhat unexpected finding that the most recent action may matter more than the longer interaction history in the present setting. Third, we will revise Section 3.3 to describe the clustering procedure in more detail, including how similarity thresholding defines the candidate pool, how the merging budget limits the accepted merges, and how cluster centers are recomputed after each merge before later scoring.

We hope these revisions address your concerns, and we would be grateful if you would consider updating your score if you find our response satisfactory.

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

Related papers

Discussion (0)

Sign in to comment.