Source-linked AI summary
Action Conditioned Bisimulation For GUI Agent Memory
Hongbo Zhang, Liuyang Song, Quanquan Li, Daqian Yang, Yan Wen, Zhengtao Yao
TL;DR
GUI memories can confuse pages that look alike but respond differently to actions. The paper merges states using an action-conditioned bisimulation over a frozen agent’s empirical predictive state graph. The action-conditioned rule gains +0.060 against ReAct (p < 10^-3), while the shortlist and successor-representation controls do not move.
Problem
Observation-similarity memories can merge GUI pages that look alike but respond differently to the same action.
Source: §1 · p. 1Method
The method merges states only when their predictions agree for actions both have tried, using an action-conditioned predictive state graph without training.
Source: §1 · p. 1, §2.2 · p. 2Results
+0.060 against ReAct (p < 10^-3); the shortlist and successor-representation controls do not move.
Source: §3 · p. 4Takeaways & Limitations
The shared-action requirement avoids merging states with no common action evidence, addressing a source of confident wrong recall.
Source: §2.2 · p. 2, §3 · p. 4States with no shared action evidence are never merged, even when they look alike, making the action vocabulary a load-bearing choice.
Source: §2.2 · p. 2
Abstract
from arXiv · showhide
An agent that remembers what it did on a web page must decide when two pages count as the same. Memories built on observation similarity merge pages that look alike but behave differently, and GUIs are full of such pages: two tabs of one widget or two rows of one menu answer the same click differently. We define the merge rule as an action-conditioned bisimulation over the empirical predictive state graph a frozen agent fills as it acts. Two states merge only when their shared actions lead to agreeing outcomes and successor blocks under an affordance label. Observation similarity never enters the rule, and nothing is trained. It replaces the merge rule of an existing outcome-value memory, so a closed-loop comparison isolates it. On MiniWoB++ it raises success rate over a memoryless agent, while a control taking identical exploratory detours, the prior successor-representation merge, and the same criterion without action conditioning change nothing.
1. INTRODUCTION
A GUI memory must distinguish pages that are the same state from pages that merely look alike. The paper replaces observation similarity with an action-conditioned bisimulation criterion over predicted outcomes and successor states.
1. INTRODUCTION
- A memory for an unretrained agent depends on deciding whether two observations represent the same state.Mistakes can prevent transfer between episodes or recall experience on a merely similar page.Source: §1 · p. 1
- Existing memory approaches retrieve stored experience using observation similarity, which addresses relevance but not whether two observations are the same state.The cited approaches differ in what they store, but use resemblance to retrieve it.Source: §1 · p. 1
- GUI pages that look nearly identical can respond differently to the same click, so merging them can pool evidence across different action semantics.The paper gives examples including tabs, menu rows, and controls before and after being enabled.Source: §1 · p. 1
- The paper defines an action-conditioned predictive state graph in which a state is characterized by its predicted outcomes under actions.Two states merge only when predictions agree for every action both have tried; the criterion is computed from recorded transitions without training.Source: §1 · p. 1
- The paper applies the memory-side perspective alongside work that improves GUI policy perception, grounding, or observation-action alignment.The introduction cites UI-TARS [12] and AgentOccam as examples.Source: §1 · p. 1
2. METHOD
The method builds an empirical predictive graph from a frozen agent’s GUI transitions and partitions states by action-conditioned agreement rather than page appearance. It then substitutes that partition into an existing outcome-value memory while holding the rest of the system fixed.
2.1. The empirical transition graph
- Observation signatures and episode-stable action templates turn recorded GUI transitions into states, actions, and successor counts for each state’s empirical action predictions.Action templates replace transient element identifiers with descriptors such as accessibility role and label, then resolve against the current page.Source: §2.1 · p. 1
2.2. Action-conditioned bisimulation distance
- States are compared on immediate outcomes and successor blocks for actions tried at both; distance is worst-case across shared actions and infinite for incompatible labels.Treating an action tried at only one state as evidence of agreement would merge on missing data; states with no action evidence in common are not merged.Source: §2.2 · p. 2
2.3. The partition is a fixed point
- The partition is iteratively refined to a fixed point, while states with no tried actions are placed using their incoming action-conditioned transition signatures.A terminal state falls back to its success, failure, or neither role, subject to the label requirement.Source: §2.3 · pp. 2–3
2.4. What is deliberately inherited
- Only the partition is replaced in the inherited outcome-value memory, which pools evidence over each state’s block and preserves its existing label and ranking behavior.When recalled evidence is silent, the policy’s original shortlist ordering remains; the comparison changes the merge rule, not the other memory components.Source: §2.4 · p. 3
2.5. Making B observable
- To make merge rules observable, reranking systems take seeded ϵ-greedy detours during the first third of runs, and a memoryless control takes identical detours.The caption specifies a closed-loop MiniWoB++ evaluation over 10 tasks with a frozen Qwen3-8B and 400 paired evaluation cells per system.Source: §2.5 · p. 3, Table 1 · p. 3
3. EXPERIMENTS
The closed-loop MiniWoB++ comparison isolates the merge rule: action-conditioned partitioning improves success, while matched detours, successor-representation merging, and observation merging do not. Gains concentrate where look-alike pages differ in behavior, with exploratory costs repaid during the run.
3. EXPERIMENTS
- Ten navigation-style MiniWoB++ tasks ran for 60 episodes each with a frozen Qwen3-8B policy; the shortcut fired 171 times for ReAct and 170 times for each other system.Episodes 1–20 used exploratory detours; episodes 21–60 were greedy for every system.Source: §3 · pp. 3–4
- +0.060 against ReAct (p < 10^-3) and +0.075 against the observation merge; the other ablation rungs did not move.The shortlist control takes the same detours and pays for the second model call, yet ends with no discordant evaluation outcomes against ReAct.Source: Figure 3 · p. 4, §3 · p. 4
- By episode 35, the action-conditioned partition had paid off the exploratory detours, while the identical-detour shortlist control recovered only to ReAct’s rate.The action-conditioned system started behind after spending a third of the run deliberately off-policy, then crossed ReAct and ended ahead.Source: Figure 3 · p. 4, §3 · p. 4
- Container tasks gained +0.075 against ReAct, while other tasks had no discordant pairs; click-menu-2 moved against the method for an unresolved reason.The container split was specified before the run; gains concentrated on tab and collapsible tasks, while tasks already at ceiling showed no harm.Source: §3 · p. 4
- On 272 cells solved by every system, the method used 1.70 steps against ReAct’s 1.81, where only directness could differ.The passage attributes this to filled blocks recording which look-alike pages are worth opening.Source: §3 · p. 4
- The merge trades evidence coverage for bias: pooling supplies counts, but disagreement among merged states contaminates the action estimate and is bounded only by the criterion.The threshold caps worst-case disagreement over shared actions, and iterative re-evaluation checks admitted merges against the coarser blocks they create.Source: §3 · p. 4