Executable Agentic Memory for GUI Agent
Zerui Qin 1 Sheng Yue 2 Xingyuan Hua 1 Yongjian Fu 1 Ju Ren 1
arXiv:2605.12294v1 [cs.AI] 12 May 2026
Abstract
achieves only 33% success rate on the long-horizon AndroidWorld benchmark (Rawles et al., 2024), while M3A, an agentic framework powered by GPT-4o, attains merely 40.5% (Rawles et al., 2024).
Modern GUI agents typically rely on a modelcentric and step-wise interaction paradigm, where LLMs must re-interpret the UI and re-decide actions at every screen, which is fragile in longhorizon tasks. In this paper, we propose Executable Agentic Memory (EAM), a structured Knowledge Graph (KG) that shifts GUI planning from free-form generation to a robust retrievaland-execution process. Our approach includes a sample-efficient memory construction pipeline using state-aware DFS and action-group mining to compress multi-step routines. To ensure efficient planning, we introduce a value-guided graph search where a lightweight Q-function model steers Monte Carlo Tree Search (MCTS) over the KG. We theoretically establish bias-consistency for the Q-model and derive sample complexity bounds for path recovery. Empirically, EAM outperforms state-of-the-art baselines like UI-TARS7B by up to 19.6% on AndroidWorld, while reducing token costs 6× relative to GPT-4o. With a 2.8s average latency, EAM enables reliable, quick, and long-horizon GUI automation.
To improve robustness, a natural direction is to equip agents with external knowledge and memory. Some efforts (Wang et al., 2024b; 2025; Cheng et al., 2025; Sun et al., 2026) maintain textual memory of historical interactions, such as workflow patterns and decision heuristics, and inject them into the LLM’s context to guide task planning. Others construct external knowledge bases by extracting action-level knowledge (e.g., element functionality or successful trajectories) from exploration, storing them as vector databases or knowledge graphs, and retrieving relevant knowledge at inference time to augment decision-making (Xie et al., 2025; Jiang et al., 2025; Guan et al., 2025b; Li et al., 2025). However, such in-context knowledge injection remains unreliable due to model-centric generation and ignorance of inherent structured information in historical trajectories, making it difficult to reliably reproduce executable paths from historical knowledge. Moreover, repeated retrieval and step-wise generation introduce substantial cost and latency, hindering real-time deployment. In this paper, we investigate Executable Agentic Memory (EAM), which can serve as a persistent, structured representation of the environment interaction logic, learned from historical interactions, and can be queried at test time so that planning can be augmented by retrieval and verification rather than free-form generation. Specifically, EAM enables the agent to (1) remember the GUl as a state machine (what states exist, which actions are available, and where they lead), and (2) reason over this memory to extract an executable path that is guaranteed to stay on valid transitions.
1. Introduction Modern Graphical User Interface (GUI) agents powered by (multimodal) LLMs can operate real-world apps by “seeing” screens and generating actions (Wen et al., 2024; Wang et al., 2024a; Zhang et al., 2025). However, the dominant interaction paradigm remains model-centric and step-wise: at every screen, an LLM must re-interpret the UI, re-decide the next action, and implicitly maintain task progress in its context window. This makes long-horizon automation fragile: small perceptual or reasoning errors would compound, easily producing hallucinated actions and incorrect detours, especially in heterogeneous app environments where training coverage is limited (Qin et al., 2025; Luo et al., 2025; Wu et al., 2025; Gou et al., 2024). For instance, UI-TARS7B (Qin et al., 2025), considered a SOTA GUI agent model, 1
To this end, we first propose a sample-efficient memory construction pipeline: a state-aware DFS exploration strategy that systematically covers task-relevant transitions with minimal redundant interactions, coupled with state deduplication and action-group mining to compress frequent multi-step routines into reusable high-level actions, yielding a compact yet executable GUI logic knowledge graph. We then propose a compute-efficient retrieval mechanism: a value-guided graph search procedure in which a lightweight
Tsinghua University, China 2 Sun Yat-sen University, China.
Preprint. May 13, 2026.
1
Executable Agentic Memory for GUI Agent
Q-function model steers MCTS over the constrained KG action space to rapidly select faithful high-reward paths from noisy experience; when needed, the agent can make only a single cloud call to summarize and validate the retrieved path into a grounded plan. Theoretically, we establish a bias-consistency guarantee for the learned Q-model on the critical set and derive a finite-sample complexity bound under which the value-guided MCTS recovers the optimal execution path with high probability.
terns from past experiences. Mobile-Agent-E (Wang et al., 2025) introduces a self-evolving framework accumulating general guidance over time. MAGNET (Sun et al., 2026) constructs dual-level memory for element grounding and workflow retrieval to handle UI drift. However, these methods rely solely on LLMs’ contextual understanding without accounting for dynamic environment interactions. Another line of work focuses on reliable action generation. AutoDroid (Wen et al., 2024) collects transition knowledge via random exploration. GUI-explorer (Xie et al., 2025) mines element functionality by analyzing GUI state changes. KGRAG (Guan et al., 2025b) transforms UI Transition Graphs into vector databases and distills reusable actions based on intent. While these approaches improve action accuracy, path generation still relies on LLM reasoning over retrieved context rather than direct extraction from an executable state machine. Moreover, massive API calls for step-wise decision-making incur substantial costs and latency.
We evaluate our method on the AndroidWorld, MobileMiniWob++, and DroidTask benchmarks. Results show that our framework consistently outperforms the existing baselines, surpassing the state-of-the-art UI-TARS-7B by up to 19.6% while reducing token costs 6× relative to GPT-4o. Our Q-guided MCTS and iterative self-training pipeline bridge the reasoning gap for small models through fine-grained credit assignment, while the action group mechanism minimizes search complexity to reach a 2.8s average latency. These findings demonstrate that grounding decision-making in structured knowledge graphs enables reliable, high-speed, and long-horizon planning for GUI agents.
LLM-based Monte Carlo Tree Search. Inspired by AlphaGo, recent work explores guiding LLM inference with tree search to improve reasoning on structured tasks. Zhou et al. (Zhou et al., 2023) propose an LLM-MCTS framework leveraging environment feedback for decision-making, while Xie et al. (Xie et al., 2024) construct a self-learning loop using MCTS to generate preference signals for training. However, these methods require multiple LLM rollouts during simulation, limiting efficiency. More recent work employs LLMs as both policy and value models. Hao et al. (Hao et al., 2023) treat the LLM as a world model for generation and evaluation. rStar-Math (Guan et al., 2025a) trains a reward model with trajectory-level binary rewards for node scoring. ReST-MCTS* (Zhang et al., 2024a) introduces a self-trained Process Reward Model for step-wise evaluation, and Mendes et al. (Mendes & Ritter, 2025) equip the value model with look-ahead capability. Despite these advances, most methods rely on heuristic value designs without theoretical guarantees and require separate policy and value models, incurring high computational overhead.
2. Related Work GUI Agents. Early efforts adapted foundation models (GPT4, GPT-4o) to GUI tasks (Wen et al., 2024; Wang et al., 2023), with Zheng et al. (Zheng et al., 2024) demonstrating that GPT-4V outperforms text-based models in web scenarios. Zhang et al. (Zhang et al., 2025) augment GPT-4V with a memory module for historical actions. Subsequent work explored modular frameworks: Wang et al. (Wang et al., 2024a) integrate planning, decision, and reflection modules; Zhang et al. (Zhang et al., 2024b) propose multiagent collaboration; and Zhu et al. (Zhu et al., 2024) design a hierarchical planner-executor architecture. However, these cloud-based frameworks incur high API costs and latency, and suffer from hallucinations due to limited GUI domain knowledge. More recent work pursues end-to-end GUI agents via parameter training. Cheng et al. (Cheng et al., 2024) train a dedicated GUI grounding model with crossplatform data, while UI-TARS (Qin et al., 2025) introduces a comprehensive pre-training to fine-tuning pipeline. To improve generalization, Luo et al. (Luo et al., 2025) and Lu et al. (Lu et al., 2025) apply rule-based RL algorithms such as GRPO (Shao et al., 2024). AutoDroid-V2 (Wen et al., 2025) fine-tunes a lightweight model to generate executable scripts in one shot. Despite these advances, on-device models (≤3B) remain limited in reasoning, struggling with complex multi-step tasks.
3. Problem Statement GUI Logic Knowledge Graph. We define the GUI Logic Knowledge Graph as a directed graph G = (S, A, E), where S denotes state nodes representing unique GUI pages, A denotes action nodes representing executable operations, and E ⊆ (S × A) ∪ (A × S) denotes edges connecting states to actions and actions to resulting states. Each state s ∈ S contains a page description ds , and each action a ∈ A is annotated with a functional description fa . We denote A(s) = {a ∈ A : (s, a) ∈ E} as the available actions at s.
Knowledge-aware GUI Agents. To mitigate hallucinations and improve adaptability, some works utilize historical memory to guide task planning. Wang et al. (Wang et al., 2024b) propose a workflow memory extracting reusable pat-
Path Extraction as Finite-Horizon MDP. Given a user instruction x ∈ X , we formulate path extraction from the KG as a finite-horizon episodic MDP, ⟨S, A, T, R, H⟩. The 2
Executable Agentic Memory for GUI Agent
state space S and action space A(s) are induced by the KG structure. T represents a deterministic transition function where s′ = T (s, a) follows the KG edges. R is a binary terminal reward function, where R(sH , x) = 1 if terminal state sH satisfies instruction x, and 0 otherwise. H is the horizon. At each step t, the agent selects at ∈ A(st ) according to policy π(·|st , x) and transits to st+1 = T (st , at ). The objective is to find π ∗ = arg maxπ Eat ∼π [R(sH , x)] that identifies a successful path τ ∗ for instruction x.
exploration trajectories. Let ξ = ⟨s0 , a0 , s1 , a1 , . . . , sn ⟩ denote an interaction trajectory. Following (Wen et al., 2025; Xie et al., 2025), we extract transition-aware GUI knowledge by analyzing consecutive transitions to construct the graph structure and enrich semantic attributes. 1) Graph Structure Construction: The KG is constructed as a Directed Acyclic Graph (DAG) where state nodes and action nodes alternate, with each trajectory incrementally merged into the KG. The key challenge lies in accurately mapping new trajectories to the existing state space. To this end, we design a state-aware deduplication mechanism featuring dual-layer filtering: (i) Coarse Filtering—each new state is encoded by an embedding model and matched against existing states via similarity retrieval; (ii) Finegrained Filtering—candidate duplicates are verified by a Vision-Language Model for rigorous semantic comparison. For duplicate states, we further perform element-level deduplication via IoU of bounding boxes, effectively connecting discrete exploration trajectories into a cohesive graph.
4. Methodology In this section, we introduce our proposed agentic memory system which comprises two main components: 1) Offline Knowledge Graph Construction, which autonomously explores the GUI environment to collect transition data and builds a structured knowledge graph G; and 2) Online Knowledge-Augmented Reasoning, which leverages the constructed KG to extract faithful execution paths via Q-model guided MCTS. An overview of the framework is presented in Fig. 1. We elaborate on each component in the following subsections.
2) Semantic Knowledge Enrichment: Once the topological structure is established, we enrich the graph with semantic attributes derived from state transitions. The knowledge mining process is formalized as:
4.1. Offline Knowledge Graph Construction The offline stage aims to construct a comprehensive GUI Logic Knowledge Graph G = (S, A, E) that captures both the structural logic and semantic knowledge of the target GUI environment. This process consists of three key components: autonomous exploration for trajectory collection, transition-aware knowledge mining for graph construction, and action group mining for efficient high-level guidance.
G ← G ⊕ Fextract (st , at , st+1 )
(1)
where Fextract : (st , at , st+1 ) 7→ (dst , dst+1 , fat ) generates page descriptions and action functional descriptions from the state transition, and ⊕ denotes the merge operator that continuously updates the extracted knowledge into G.
Autonomous Exploration. The core of our offline stage lies in task-oriented autonomous exploration that systematically discovers GUI states and transitions contributing to task completion. We propose an element-grounded hierarchical exploration based on depth-first search (DFS). Given a task goal g, we extract Exploration Anchors from the current GUI state—interactable elements serving as structural primitives for sub-goal generation. The MLLM uses these anchors to generate up to k candidate sub-goals ranked by their likelihood of progressing toward g. At each depth, the agent evaluates progress and determines one of three outcomes: (1) C ONTINUE—the sub-goal was achieved but g requires further operations; (2) BACKTRACK—the current state deviates from the path toward g; (3) C OMPLETE—the task goal g is achieved. This DFS-based design ensures comprehensive coverage of task-relevant transitions (up to O(k d ) distinct trajectories) while the collected trajectories naturally form a prefix tree structure that can be seamlessly transformed into the knowledge graph G.
Action Group Mining. Beyond atomic actions, real-world GUI tasks often involve recurring multi-step action patterns. While recent works extract high-level actions from trajectories (Jiang et al., 2025; Wang et al., 2025), they rely heavily on LLMs to summarize these groups, suffering from poor cross-task generalizability and high computational cost. To address these limitations, we propose a statistical approach inspired by Byte Pair Encoding (BPE). We conceptualize the KG as a “path heatmap,” where high-frequency action subsequences represent high-value generalizable skills. Formally, let V = {a1 , a2 , . . . , aM } denote the initial vocabulary of atomic actions, and let P = {τ1 , τ2 , . . . , τK } denote the corpus of all historical paths in the KG, where each path τ = (ai1 , ai2 , . . . , aiL ) is a sequence of atomic actions. The mining process proceeds iteratively. At each iteration j, we compute the frequency of all adjacent action pairs and identify the most frequent pair:
Transition-aware Knowledge Mining. The knowledge construction process builds a structured KG from collected
(a∗ , a′∗ ) = arg
max ′
(a,a )∈V×V
3
X τ ∈P
count((a, a′ ), τ )
(2)
Executable Agentic Memory for GUI Agent
Knowledge Graph with Action Group Mining
Expected State
Deviated State
Tasks
Open Connection Preference
Sub-goals Execution
-Turn on Bluetooth -Turn off WIFI -Open WIFI Config
…
Toggle On
Unexplored State
Navigate To Bluetooth Page
Click Bluetooth Toggle Off
CONTINUE
BACKTRACK
Trajectory Data
Open WIFI Settings
Open Network
BPE-based Action Merging
Open Config
Navigate To WIFI Settings
Task-oriented DFS Exploration
Disable WIFI
Page Node
Offline Exploration
Atomic action Node
Action Group Node
Knowledge Graph 𝑮
Exploration Tasks
Inference Instruction input “Turn on Bluetooth and enable WIFI”
MCTS on Graph
Q-value Guided MCTS
𝟐,𝟐 = 𝟎. 𝟐𝟓 𝑄2,2 𝟐,𝟏 = 𝟎. 𝟓 𝑸 𝑄2,1 𝑸
𝜏∗ Navigate to …
Execute
Toggle on
Navigate to WIFI…
𝟏,𝟐 = 𝟎. 𝟐𝟓 𝑄1,2 𝑸
𝑸𝟐,𝟏 = 𝟎. 𝟓 𝑄1,1
𝟑,𝟐 = 𝟏 𝑸 𝟑,𝟏 = 𝟎 𝑄 𝑸 3,1
…
𝑄3,2
𝑸𝟑,𝟑 = 𝟎. 𝟓
𝑄4,2
𝑄4,1 𝟒,𝟏 = 𝟏 𝑸
Filtering & Replace
𝟒,𝟐 = 𝟎 𝑸
𝟑,𝟒 = 𝟎 𝑄3,4 𝑸
𝑄3,3
𝑄4,3
Soft BCE
𝟒,𝟏 = 𝟏 𝑸
在此处键入公式。
Executable Task Plan
Q-model Update
Self-training Pipeline
Figure 1. Overview of Executable Agentic Memory (EAM). It comprises offline automatic memory construction and inference-time executable memory reuse guided by a trained Q-model.
where count((a, a′ ), τ ) denotes the number of occurrences of the adjacent pair (a, a′ ) in path τ . If the maximum frequency exceeds a predefined threshold δf , we merge the pair into a new action group and update the vocabulary: ∗ ′∗ a(j) new = a ◦ a ,
V ← V ∪ {a(j) new }.
lapse and introduce unnecessary computational overhead. To address this challenge, we introduce a path navigating agent that leverages Monte Carlo Tree Search (MCTS) guided by a lightweight Q-model to extract executable paths from the KG. Unlike generative agents that map generated tokens into the graph, our agent explicitly operates on the graph topology and treats reasoning as planning over discrete states and actions. This design offers three key advantages. First, by constraining the action space to valid edges in G, the agent naturally decouples graph reasoning from semantic generation and treats the KG as a rigorous state machine. Second, the agent automatically generates steplevel Q-value annotations through MCTS rollouts, which obviates the need for human-labeled training data. Third, instead of fine-tuning a generative model over a vast vocabulary, the agent relies on a compact Q-model to predict scalar values, which significantly reduces computational cost.
(3)
The corpus P is then updated by replacing all occurrences of (j) (a∗ , a′∗ ) with anew . This process iterates until the frequency of the most common pair falls below δf . The mined action groups are integrated into the KG as high-level action nodes, extending the action space from atomic operations to multistep reusable skills. 4.2. Online Knowledge-Augmented Path Extraction Given a user instruction x, extracting an executable path from the KG can be formulated as the finite-horizon MDP defined in Section 3. This MDP features deterministic transitions, binary terminal rewards, and a relatively small stateaction space constrained by the KG structure. Such a tabular setting differs fundamentally from classical agentic RL scenarios, which typically involve complex reward structures and vocabulary-scale action spaces. Due to this structural mismatch, directly employing mainstream GRPO-style RL frameworks (Shao et al., 2024; Feng et al., 2025; Jin et al., 2025) is suboptimal, as they easily suffer from entropy col-
Our path navigating agent consists of three components: Qmodel guided MCTS framework, random policy valuation for node evaluation, and a self-training pipeline for iterative model refinement. Q-model Guided MCTS. The agent performs tree search on the KG starting from a root node h0 = (x, s0 ), which encodes the instruction x and initial state s0 . Each node 4
Executable Agentic Memory for GUI Agent
ht = (st , at ) in the search tree corresponds to a state-action pair. The search proceeds through four MCTS phases:
with binary rewards (He et al., 2025; Laidlaw et al., 2023), which aligns precisely with our KG setting.
1) Selection: The agent traverses the tree by selecting child nodes according to the UCT criterion until reaching a leaf node: s ln N (s) UCT(s, a) = Q(s, a) + c (4) N (s, a)
Self-Training Pipeline. We train the agent’s Q-model Qθ through an iterative self-training procedure consisting of an initialization stage and a refinement stage. 1) Initialization: Directly deploying an untrained Q-model leads to random exploration and severe label imbalance, as the search predominantly encounters dead-end nodes with zero Q-values. To address this cold-start problem, we initialize Qθ using preference learning on an existing GUI dataset. For each step t along an expert trajectory, we construct preference pairs with the expert action a+ t as + positive and a randomly sampled a− t ∈ A(st ) \ {at } as negative. The agent is trained with a pairwise ranking loss based on the Bradley-Terry model: Linit (θ) = −E(τ + ,τ − )∼Dinit R(τt+ , τt− ) (7)
where Q(s, a) is the estimated Q-value, N (s, a) the visit count, and c the exploration constant. 2) Expansion: Upon reaching a non-terminal leaf state sl , the agent expands all available actions a ∈ A(sl ) as child nodes. 3) Evaluation: Unlike standard MCTS with random rollouts, the agent queries its Q-model to initialize Q-values: Q(sl , a) ← Qθ (sl , a), where Qθ (s, a) ∈ (0, 1) predicts the task success probability.
t
− where R(τt+ , τt− ) = log σ(Qθ (st , a+ t ) − Qθ (st , at )).
4) Back-propagation: The agent propagates Q-values back to the root, updating visit counts and Q-estimates along the path via incremental averaging.
2) Iterative Refinement: After initialization, the agent iteratively refines its Q-model using self-generated data. In each round, the agent samples instructions and executes MCTS guided by the current Qθ to construct search trees, then computes target Q-values via bottom-up Bellman backup:
N (st , at ) ← N (st , at ) + 1 Q(st , at ) ← Q(st , at ) +
Q(sl , al ) − Q(st , at ) . N (st , at )
(5)
Q̂(s, a) ← r(s, a) +
After M iterations, the top-K paths with the highest mean Q-values are extracted and processed by a cloud-based LLM for one-time filtering and parameter replacement into the final executable plan.
X
πu
′
X
Q̂(s′ , a′ ).
(8)
a′ ∈A(s′ )
(s,a)∼T
(9) where pθ = σ(Qθ (s, a)) and T denotes state-action pairs from the search trees. Through this iterative process, the agent progressively improves its ability to identify promising paths within the KG.
Instead, we define the Q-value as the expected success probability under a uniform random policy πu (a|s) = 1/|A(s)|. This value can be computed via the Bellman equation: 1 Q (s, a) = r(s, a) + |A(s′ )|
1 |A(s′ )|
Since Q-values represent probabilities in [0, 1], we formulate the optimization as binary classification with soft labels: h i Lupdate (θ) = − E Q̂ log pθ + (1 − Q̂) log(1 − pθ )
Random Policy Valuation. To effectively guide the search, the agent’s Q-model should not only identify superior actions but also quantify the likelihood of success after selecting each action. Most existing MCTS frameworks employ Outcome Reward Models (ORM) that assign binary values (Cobbe et al., 2021). Such coarse signals overlook the nuanced differences among intermediate steps.
πu
t
5. Theoretical Analysis
′
Q (s , a ). (6)
In this section, we provide theoretical guarantees for the proposed Q-model guided MCTS framework. We first formalize the problem setting, then present our two main results: (1) a bias consistency guarantee ensuring the learned Q-model is close to Qπu on critical states, and (2) a sample complexity bound for extracting the optimal path.
a′ ∈A(s′ )
s′ = T (s, a) is the successor state, and r(s, a) ∈ {0, 1} is the terminal reward. The value Qπu (s, a) represents the probability of reaching a successful terminal state when starting from (s, a) and acting uniformly at random thereafter. When Qπu (s, a) = 0, no feasible path exists from (s, a) to success, whereas higher values indicate greater likelihood of task completion. Crucially, recent theoretical results have shown that acting greedily with respect to Qπu achieves optimality in finite-horizon deterministic MDPs
5.1. Problem Setting We analyze path extraction on G under the MDP formulation from Section 3. Proposition 5.1 formalizes the optimality guarantee of the greedy policy with respect to Qπu . 5
Executable Agentic Memory for GUI Agent
Algorithm 1 Self-Training for Path-Navigating Agents
where
Input: Instruction dataset D, initialization dataset Dinit , knowledge graph G Output: Trained Q-model Qθ ▷ Model Initialization Construct preference pairs (τt+ , τt− ) from Dinit Initialize Qθ by minimizing ranking loss Linit (Eq. 7) ▷ Iterative Refinement via MCTS for each round r = 1, 2, . . . , R do Sample instruction batch B from D T ←∅ for each instruction x ∈ B do Execute MCTS guided by Qθ on G to construct search tree Compute Q̂(s, a) for all nodes (Eq. 8) T ← T ∪ {(s, a, Q̂(s, a))} end for Update Qθ by minimizing Lupdate (Eq. 9) end for Return: Qθ
r ϵbias (m, δ) :=
ϵapprox is the in-class approximation error, εgen (m, δ) is the generalization error depending on m and Rademacher complexity, and ϵopt is the optimization error. Theorem 5.2 shows that the proxy error decreases as training samples increase. This bias bound directly controls the accuracy of MCTS node evaluation: when ϵbias < ∆∗min /2, the learned Q-model preserves correct action rankings on the critical set (see Appendix A.1 for details). Our second main result establishes the sample complexity for optimal path extraction. Theorem 5.3 (Sample Complexity for Optimal Path Extraction). Suppose ϵbias (m, δ/2) < ∆∗min /2. Let ∆eff := ∆∗min − 2ϵbias > 0 and K = maxs |A(s)|. Then for the greedy path ât = arg maxa Q̄n (s∗t , a) to coincide with τ ∗ with probability at least 1 − δ, the number of MCTS simulations per node must satisfy 32(K − 1)c2 ln(Hn/δ) π2 n≥ + 2(K − 1) 2N0 + ∆2eff 3 (14)
Proposition 5.1 (Optimality of Greedy Policy (He et al., 2025)). Consider the KG-induced MDP with deterministic transitions, tree-structured state space, and binary terminal rewards r ∈ {0, 1}. Let πu be the uniform policy and Qπu its corresponding Q-function. Define the greedy policy πgreedy (s) = arg maxa∈A(s) Qπu (s, a). Then πgreedy is optimal. ∗
yielding total complexity Ntotal = O
= (s∗0 , a∗0 , . . . , s∗H−1 , a∗H−1 ) denote an optimal path
Let τ induced by πgreedy . Define the critical set C as the collection of state-actions that must be ranked correctly to recover τ ∗ : C=
H−1 [
{(s∗t , a) : a ∈ A(s∗t )} .
HKc2 ln(Hn/δ) 2 (∆∗ min −2ϵbias )
+
O(HKN0 ), where c is the UCT exploration constant and N0 is a burn-in threshold. Theorem 5.3 shows that the simulation complexity scales polynomially with horizon H, branching factor K, and inversely with the squared effective action gap. This provides a theoretical foundation for the efficiency of our approach: as the Q-model improves (reducing ϵbias ), fewer MCTS simulations are needed to recover the optimal path. Complete proofs are provided in Appendix A.2.
(10)
t=0
Let |C| = H · maxs |A(s)|. Define the minimum action gap along the optimal path: ∗ πu ∗ ∗ πu ∗ ∆min := min Q (st , at ) − max∗ Q (st , a) . t∈{0,...,H−1}
1 (ϵapprox + 2εgen (m, δ/2) + ϵopt ). 2 (13)
a̸=at
6. Experiment
(11) We train Qθ using target values computed via uniform Bellman backup (Eq. 8) and perform MCTS at inference to extract the optimal path.
In this section, we will present the results of our empirical study to answer the following question: • How does our proposed method perform on standard GUI benchmarks compared to both on-device and cloud-based baselines in terms of success rate and efficiency? • Does our self-training pipeline enable stable iterative performance improvements and exhibit theoretically expected properties? • How do the various components in our method affect performance, and does the trained Q-model demonstrate cross-environment generalization?
5.2. Main Results Next, we give the bias consistency guarantee on the critical set. Theorem 5.2 (Bias Consistency on C). With probability at least 1 − δ, the learned predictor Qθ satisfies ∥Qθ − Qπu ∥2,ρC ≤ ϵbias (m, δ)
(12) 6
Executable Agentic Memory for GUI Agent
Method GPT-4o Qwen 2.5-VL-3B UI-TARS-2B UI-TARS-7B M3A AutoDroid-V2 AppAgentX GUI-Explorer EAM (Ours)
Type
Input
AndroidWorld (%)
MobileMiniWob++ (%)
DroidTask (%)
GPT-4o Qwen 2.5-VL-3B UI-TARS-2B UI-TARS-7B GPT-4o Llama-3-8B-ft GPT-4o GPT-4o GPT-4o, Qwen2.5-3B-instruct-ft
SoM SoM screen screen SoM SoM SoM SoM SoM
34.5 2.6 6.9 33.0 40.5 26.0 62.5 47.4 52.6
56.5 32.6 31.5 53.3 68.5 53.3 72.8 80.4 76.1
57.0 13.3 34.8 55.0 72.2 54.4 88.6 88.0 86.1
Table 1. Success rate (%) comparison between our method and baselines on AndroidWorld, MobileMiniWob++, and DroidTask benchmarks. “SoM” refers to Set-of-Mark prompting, which utilizes the bounding boxes recorded in the accessibility tree to annotate UI elements with numerical labels in screenshots. All results are averaged over three independent runs.
Method GPT-4o Qwen2.5-VL-3B UI-TARS-2B UI-TARS-7B M3A AutoDroid-V2 AppAgentX GUI-Explorer EAM (Ours)
Latency (s)
API Tokens Cost (K)
9.3 7.7 6.0 8.8 16.9 2.1 16 66.4 2.8
50.8 32.7 62.6 6.2 73.1 8.3
an exploration-augmented framework that collects trajectories, extracts element-wise knowledge, and uses RAG for decision-making. Implementation. Our framework is implemented as a plugand-play module built on UI-TARS-2B, which serves as a local action executor following memory-grounded planning. We use GPT-4o for task-oriented exploration and knowledge mining. The knowledge base is constructed with Neo4j for app-wise knowledge graphs and Pinecone for screenshot embeddings. We fine-tune Qwen2.5-Instruct for path extraction with three model sizes: 0.5B, 1.5B, and 3B. For Q-value estimation, we append a value head to output scalar predictions. The self-training pipeline runs for four rounds. All training is conducted on 4×A800-80GB GPUs, and inference experiments are performed on a single RTX 4090-16GB to simulate on-device deployment.
Table 2. Efficiency comparison between EAM and baselines in terms of latency and token cost. “Latency (s)” denotes the average execution time per step. “API Tokens Cost (K)” indicates the total token consumption (in thousands) per step for LLM API calls. “-” indicates that the method uses locally deployed models without API calls.
6.2. Experimental Results Comparative results. Table 1 reports success rates on the three benchmarks. Our method achieves 52.6% on AndroidWorld, 76.1% on MobileMiniWob++, and 86.1% on DroidTask, surpassing all on-device baselines by significant margins (+19.6, +22.8, and +31.1, respectively). Notably, despite utilizing a 3B model for path extraction, our method substantially outperforms GPT-4o based M3A (+7.6, +13.9, and +29.1) and achieves performance comparable to knowledge-enhanced agents like AppAgentX and GUI-Explorer. These gains indicate that grounding decisionmaking in a structured knowledge graph effectively bridges the reasoning gap between small language models and frontier LLMs. Table 2 demonstrates that our approach achieves an average latency of 2.8 s and token cost of 8.3K per step. This efficiency stems from our plan-then-execute framework: unlike cloud-based agents requiring massive iterative API calls, our method necessitates only a single API call to filter the extracted paths, reducing token cost by approximately 6× compared to GPT-4o (50.8K). While AutoDroidV2 also adopts plan-then-execute to achieve low latency
6.1. Experimental Setup Benchmarks. We evaluate the effectiveness and efficiency our method on three benchmarks: AndroidWorld (Rawles et al., 2024) (116 tasks across 20 real-world apps), MobileMiniWob++ (Rawles et al., 2024) (92 web tasks), and DroidTask (Wen et al., 2024) (158 tasks across 13 apps). Baselines. For on-device agents, we consider four baselines: 1) Qwen2.5-VL-3B, the vanilla VLM for on-device deployment; 2) UI-TARS-2B (Qin et al., 2025), the lightweight SFT version of UI-TARS-7B; 3) UI-TARS-7B (Qin et al., 2025), a SOTA GUI agent model; 4) AutoDroid-V2 (Wen et al., 2025), a code-generation agent fine-tuned on Llama3-8B that produces executable scripts for one-shot task execution. For cloud-based and knowledge-enhanced agents, we consider: 1) GPT-4o, the base VLM for cloud-based agents; 2) M3A (Rawles et al., 2024), a SOTA ReActbased agent framework; 3) AppAgentX (Jiang et al., 2025), which extracts and reuses high-level actions from GUI transitions for task guidance; 4) GUI-Explorer (Xie et al., 2025), 7
Executable Agentic Memory for GUI Agent
(2.1 s), its performance suffers due to a lack of rigorous knowledge guidance during inference.
DroidTask and MobileMiniWob++, despite never seeing these environments during training. This addresses Q.3: the learned value estimation captures transferable knowledge about GUI navigation patterns, enabling reliable path extraction in unseen scenarios. While in-environment training remains optimal, cross-environment results suggest a welltrained Q-model can serve as strong initialization for new environments.
6 X F F H V V 5 D W H
% % %
2 S W L P D O $ F W L R Q 0 D U J L Q ×10 2
5 R X Q G
(a) AndroidWorld-SR
% % %
5 R X Q G
(c) AndroidWorld-Gap
6 X F F H V V 5 D W H
6 X F F H V V 5 D W H
% D V H O L Q H
. % Z & U R V V H Q Y , Q H Q Y L Q L W P R G H O 0 R G H O 0 R G H O
(a) DroidTask
% D V H O L Q H
. % Z & U R V V H Q Y , Q H Q Y L Q L W P R G H O 0 R G H O 0 R G H O
(b) MobileMiniWob++
Figure 3. Ablation study on agentic memory with different model: cross-environment vs. in-environment trained models.
More experimental details, including analyses of training loss curves, action groups, model size, and MCTS hyperparameters, can be found in the Appendix B.
7. Conclusion
% % %
2 S W L P D O $ F W L R Q 0 D U J L Q ×10 2
6 X F F H V V 5 D W H
Substantial improvement through self-training. To answer Q.2, we analyze performance gains through iterative self-training. As shown in Fig. 2a–2b, all three model sizes (0.5B, 1.5B, and 3B) exhibit consistent improvement on both AndroidWorld and DroidTask as self-training rounds increase. Notably, the 3B model achieves the most substantial gains. Fig. 2c–2d further shows the value gap between optimal and suboptimal actions on critical paths: as self-training progresses, the model develops more accurate value estimates, enabling better separation of optimal actions. The initially negative or near-zero margins in early rounds indicate that the untrained model struggles to distinguish optimal actions, while later rounds show increasingly positive margins, demonstrating improved discriminative ability. This aligns with our theoretical analysis bounding path extraction ability by sample size and value estimation quality: as ϵbias decreases through training, the effective action gap ∆eff = ∆∗min − 2ϵbias increases, requiring fewer MCTS simulations to recover optimal paths (Theorem 5.3).
5 R X Q G
This paper presents Executable Agentic Memory (EAM), a structured knowledge graph that shifts GUI planning from free-form generation to a robust retrieval-and-execution process. Unlike prior knowledge-augmented approaches that rely on LLM reasoning over retrieved context, EAM enables agents to directly extract executable paths guaranteed to stay on valid transitions. We propose a sample-efficient memory construction pipeline and a value-guided MCTS framework with theoretical guarantees for reliable path extraction. Experimental results across three benchmarks demonstrate significant improvements in both success rate and efficiency. These findings show that treating the KG as an executable state machine, rather than a retrieval source for in-context injection, enables reliable, efficient, and long-horizon GUI automation.
(b) DroidTask-SR
% % %
5 R X Q G
(d) DroidTask-Gap
Figure 2. Self-training dynamics: (a-b) Success rate and (c-d) optimal action margin across rounds.
Limitations. Our current framework assumes a relatively static UI environment. When applications undergo significant updates, the knowledge graph may become outdated. Developing efficient incremental evolution mechanisms for the knowledge graph to adapt to the frequently updating environments remains an important direction for future work.
Ablation Study and Cross-Environment Generalization. Fig. 3 quantifies the contribution of each component. Starting from the Baseline (UI-TARS-2B without KG guidance), introducing the knowledge graph with an initializationtrained model (+KB w/ init model) yields substantial gains, demonstrating the value of structured knowledge. Training the Q-model in-environment (+In-env Model) achieves the best performance, confirming that domain-specific training further refines value estimates. Notably, replacing with a cross-environment trained model (+Cross-env Model, trained on AndroidWorld) also improves performance on
Impact Statement This paper presents Executable Agentic Memory (EAM), a framework for improving the reliability and efficiency of 8
Executable Agentic Memory for GUI Agent
long-horizon GUI automation agents. If deployed responsibly, such systems could reduce repetitive digital work, improve productivity, and support accessibility by helping users complete multi-step tasks in mobile and web applications. At the same time, GUI automation can be misused for harmful purposes, including unauthorized actions, automated abuse of online services, and privacy-invasive data collection. Our approach also raises privacy and security considerations because building and using agent memory may involve storing interaction traces or screenshots that could contain sensitive information. To mitigate these risks, we recommend deployments incorporate explicit user consent, least-privilege access, careful handling and redaction of stored artifacts, and monitoring/auditing of automated actions. We encourage future work on safety constraints for high-risk operations and privacy-preserving mechanisms for agent memory.
world model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8154–8173, 2023. He, H., Ye, Y., Cai, Q., Hu, C., Jiao, B., Jiang, D., and Pan, L. Random policy valuation is enough for llm reasoning with verifiable rewards. arXiv preprint arXiv:2509.24981, 2025. Jiang, W., Zhuang, Y., Song, C., Yang, X., Zhou, J. T., and Zhang, C. Appagentx: Evolving gui agents as proficient smartphone users. arXiv preprint arXiv:2503.02268, 2025. Jin, B., Zeng, H., Yue, Z., Yoon, J., Arik, S., Wang, D., Zamani, H., and Han, J. Search-r1: Training llms to reason and leverage search engines with reinforcement learning. arXiv preprint arXiv:2503.09516, 2025.
References
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282–293. Springer, 2006.
Cheng, K., Sun, Q., Chu, Y., Xu, F., Li, Y., Zhang, J., and Wu, Z. Seeclick: Harnessing gui grounding for advanced visual gui agents. arXiv preprint arXiv:2401.10935, 2024.
Laidlaw, C., Russell, S. J., and Dragan, A. Bridging rl theory and practice with the effective horizon. Advances in Neural Information Processing Systems, 36:58953– 59007, 2023.
Cheng, W., Ni, E., Wang, W., Sun, Y., Liu, J., Shen, W., Chen, Y., Shi, B., and Wang, D. Mga: Memory-driven gui agent for observation-centric interaction. arXiv preprint arXiv:2510.24168, 2025.
Li, R., Zhai, Y., Xu, B., Xu, L., Shi, N., Zhang, W., Lin, R., and Wang, L. Echotrail-gui: Building actionable memory for gui agents via critic-guided self-exploration. arXiv preprint arXiv:2512.19396, 2025.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. Feng, L., Xue, Z., Liu, T., and An, B. Group-in-group policy optimization for llm agent training. arXiv preprint arXiv:2505.10978, 2025.
Lu, Z., Chai, Y., Guo, Y., Yin, X., Liu, L., Wang, H., Xiao, H., Ren, S., Xiong, G., and Li, H. Ui-r1: Enhancing efficient action prediction of gui agents by reinforcement learning. arXiv preprint arXiv:2503.21620, 2025.
Gou, B., Wang, R., Zheng, B., Xie, Y., Chang, C., Shu, Y., Sun, H., and Su, Y. Navigating the digital world as humans do: Universal visual grounding for gui agents. arXiv preprint arXiv:2410.05243, 2024.
Luo, R., Wang, L., He, W., and Xia, X. Gui-r1: A generalist r1-style vision-language action model for gui agents. arXiv preprint arXiv:2504.10458, 2025. Mendes, E. and Ritter, A. Language models can selfimprove at state-value estimation for better search. arXiv preprint arXiv:2503.02878, 2025.
Guan, X., Zhang, L. L., Liu, Y., Shang, N., Sun, Y., Zhu, Y., Yang, F., and Yang, M. rstar-math: Small llms can master math reasoning with self-evolved deep thinking. arXiv preprint arXiv:2501.04519, 2025a.
Qin, Y., Ye, Y., Fang, J., Wang, H., Liang, S., Tian, S., Zhang, J., Li, J., Li, Y., Huang, S., et al. Ui-tars: Pioneering automated gui interaction with native agents. arXiv preprint arXiv:2501.12326, 2025.
Guan, Z., Li, J. C. L., Hou, Z., Zhang, P., Xu, D., Zhao, Y., Wu, M., Chen, J., Nguyen, T.-T., Xian, P., et al. Kgrag: Enhancing gui agent decision-making via knowledge graph-driven retrieval-augmented generation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 5396–5405, 2025b.
Rawles, C., Clinckemaillie, S., Chang, Y., Waltz, J., Lau, G., Fair, M., Li, A., Bishop, W., Li, W., CampbellAjala, F., et al. Androidworld: A dynamic benchmarking environment for autonomous agents. arXiv preprint arXiv:2405.14573, 2024.
Hao, S., Gu, Y., Ma, H., Hong, J., Wang, Z., Wang, D., and Hu, Z. Reasoning with language model is planning with 9
Executable Agentic Memory for GUI Agent
Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y., Wu, Y., et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
Zhang, C., Yang, Z., Liu, J., Li, Y., Han, Y., Chen, X., Huang, Z., Fu, B., and Yu, G. Appagent: Multimodal agents as smartphone users. In Proceedings of the 2025 CHI Conference on Human Factors in Computing Systems, pp. 1–20, 2025.
Sun, L., Zhang, J., Wang, S., and Wei, Z. Magnet: Towards adaptive gui agents with memory-driven knowledge evolution. arXiv preprint arXiv:2601.19199, 2026.
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, J. Rest-mcts*: Llm self-training via process reward guided tree search. Advances in Neural Information Processing Systems, 37:64735–64772, 2024a.
Wang, B., Li, G., and Li, Y. Enabling conversational interaction with mobile ui using large language models. In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pp. 1–17, 2023.
Zhang, J., Zhao, C., Zhao, Y., Yu, Z., He, M., and Fan, J. Mobileexperts: A dynamic tool-enabled agent team in mobile devices. arXiv preprint arXiv:2407.03913, 2024b.
Wang, J., Xu, H., Jia, H., Zhang, X., Yan, M., Shen, W., Zhang, J., Huang, F., and Sang, J. Mobile-agent-v2: Mobile device operation assistant with effective navigation via multi-agent collaboration. Advances in Neural Information Processing Systems, 37:2686–2710, 2024a.
Zheng, B., Gou, B., Kil, J., Sun, H., and Su, Y. Gpt-4v (ision) is a generalist web agent, if grounded. arXiv preprint arXiv:2401.01614, 2024. Zhou, A., Yan, K., Shlapentokh-Rothman, M., Wang, H., and Wang, Y.-X. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406, 2023.
Wang, Z., Xu, H., Wang, J., Zhang, X., Yan, M., Zhang, J., Huang, F., and Ji, H. Mobile-agent-e: Self-evolving mobile assistant for complex tasks. arXiv preprint arXiv:2501.11733, 2025.
Zhu, Z., Tang, H., Li, Y., Lan, K., Jiang, Y., Zhou, H., Wang, Y., Zhang, S., Sun, L., Chen, L., et al. Moba: A two-level agent system for efficient mobile task automation. arXiv e-prints, pp. arXiv–2410, 2024.
Wang, Z. Z., Mao, J., Fried, D., and Neubig, G. Agent workflow memory. arXiv preprint arXiv:2409.07429, 2024b. Wen, H., Li, Y., Liu, G., Zhao, S., Yu, T., Li, T. J.-J., Jiang, S., Liu, Y., Zhang, Y., and Liu, Y. Autodroid: Llmpowered task automation in android. In Proceedings of the 30th Annual International Conference on Mobile Computing and Networking, pp. 543–557, 2024. Wen, H., Tian, S., Pavlov, B., Du, W., Li, Y., Chang, G., Zhao, S., Liu, J., Liu, Y., Zhang, Y.-Q., et al. Autodroidv2: Boosting slm-based gui agents via code generation. In Proceedings of the 23rd Annual International Conference on Mobile Systems, Applications and Services, pp. 223– 235, 2025. Wu, Q., Cheng, K., Yang, R., Zhang, C., Yang, J., Jiang, H., Mu, J., Peng, B., Qiao, B., Tan, R., et al. Gui-actor: Coordinate-free visual grounding for gui agents. arXiv preprint arXiv:2506.03143, 2025. Xie, B., Shao, R., Chen, G., Zhou, K., Li, Y., Liu, J., Zhang, M., and Nie, L. Gui-explorer: Autonomous exploration and mining of transition-aware knowledge for gui agent. arXiv preprint arXiv:2505.16827, 2025. Xie, Y., Goyal, A., Zheng, W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.00451, 2024. 10
Executable Agentic Memory for GUI Agent
A. Theoretical Proof This appendix provides complete proofs of all theoretical results stated in Section 5. We organize the proofs following the structure of the main text. A.1. Proof of theorem 5.2 Classical MCTS with terminal rollouts produces node estimates that concentrate around their own expectations. In contrast, we use a learned value model Qθ to guide tree search, which introduces additional bias that must be controlled. A necessary condition for reliable navigation is that the proxy Qθ is consistent with the reference value Qπu on the critical set C, so that action rankings on the critical path are preserved. Thus, we first aim to control the bias induced by using a learned value model. Specifically, for any critical pair (s, a) ∈ C, we aim to bound E Q̄N (s, a) − Qπu (s, a) , (15) Q̄N (s, a) denotes the MCTS estimate produced at inference time after N visits. The expectation is taken over the internal randomness of MCTS. This bias control provides the interface to standard UCT/MCTS finite-sample analysis, where Q̄N (s, a) concentrates around its mean. Formally, for any (s, a) ∈ C,
Q̄N (s, a) − Qπu (s, a) ≤ Q̄N (s, a) − E Q̄N (s, a) + E Q̄N (s, a) − Qπu (s, a) .
(16)
The first term is the standard finite-sample deviation of MCTS and will be bounded by standard UCT/MCTS concentration results. In this section, we focus on controlling the second term, which captures the bias induced by using a learned value model. Such proxy bias can be further decomposed into two components: • Target error (estimation noise). The target Q̂ deviates from Qπu due to finite terminal rollouts. • Learning/generalization error. The learned predictor Qθ deviates from the target mapping due to finite training samples and optimization error. Target Estimation: Let Z(s, a) ∈ [0, 1] be the discounted terminal return obtained by rolling out from (s, a) to termination under πu . Then E[Z(s, a) | s, a] = Qπu (s, a).
(17)
Lemma A.1 (Unbiasedness of Bellman Backup). Let the uniform-policy Bellman operator T for deterministic transitions be X 1 (T Q̂)(s, a) = r(s, a) + Q̂(s′ , a′ ) (18) |A(s′ )| ′ ′ a ∈A(s )
where s′ = T (s, a). If each child estimate is unbiased for Qπu , then the backed-up value is also unbiased. Proof. Let s′ = T (s, a) denote the successor state under deterministic transition. Suppose for all a′ ∈ A(s′ ), the child estimates satisfy E[Q̂(s′ , a′ )] = Qπu (s′ , a′ ).
(19)
1 |A|
(20)
The backed-up value is Q̂(s, a) = r(s, a) +
11
X a′ ∈A(s′ )
Q̂(s′ , a′ ).
Executable Agentic Memory for GUI Agent
Taking expectations and using linearity: E[Q̂(s, a)] = r(s, a) + γ = r(s, a) + γ
1 |A| 1 |A|
X
E[Q̂(s′ , a′ )]
(21)
Qπu (s′ , a′ )
(22)
a′ ∈A(s′ )
X a′ ∈A(s′ )
= r(s, a) + γEa′ ∼πu [Qπu (s′ , a′ )] πu
= (T Q )(s, a)
(23) (24)
πu
= Q (s, a),
(25)
where the last equality follows from the Bellman fixed-point equation for Qπu under policy πu . Given the target values of leaf nodes obtained by rolling out under πu , Lemma A.1 propagate Unbiasedness to the whole tree. We can further bound the error between target values and the true values on the critical set. Lemma A.2. Assume that every leaf-edge value contributing to Q̂(s, a) for any (s, a) ∈ C is estimated by at least ntr min i.i.d. terminal rollouts under πu , each bounded in [0, 1]. Then with probability at least 1 − δ, s ln(2|C|/δ) πu sup Q̂(s, a) − Q (s, a) ≤ ϵtr (δ) := 2ntr (s,a)∈C min Proof. Fix (s, a) ∈ C. Let Z1 , Z2 , . . . , Zn be the i.i.d. terminal rollout returns contributing to Q̂, where n ≥ ntr min . Each Zi ∈ [0, 1] and by (17), E[Zi ] = Qπu (s, a). Pn The target estimate is Q̂ = n1 i=1 Zi . By Hoeffding’s inequality for bounded random variables: 2 Pr Q̂ − Qπu (s, a) ≥ ϵ ≤ 2 exp −2nϵ2 ≤ 2 exp −2ntr . min ϵ Setting ϵ =
q
(26)
ln(2|C|/δ) , we obtain 2ntr min
Pr
δ Q̂ − Qπu (s, a) ≥ ϵ ≤ . |C|
(27)
Taking a union bound over all |C| pairs in C: ! Pr
sup
Q̂(s, a) − Qπu (s, a) ≥ ϵ
≤ |C| ·
(s,a)∈C
δ = δ. |C|
(28)
Thus with probability at least 1 − δ, the stated bound holds. Lemma A.2 shows that the target error bound is tightened as the number of samples increases. Learning Error. We now relate the learning error of the Q-model Qθ to the training sample size. Let S = {(xi , yi )}m i=1 be the training data, where xi = (si , ai ) denotes a state-action pair and yi = Q̂(si , ai ) ∈ [0, 1] is the corresponding target value. We analyze the binary cross-entropy loss: ℓ(p, y) = −y log p − (1 − y) log(1 − p)
(29)
For analysis, we restrict predictors to [τ, 1 − τ ] for some τ ∈ (0, 1/2), solely to ensure ℓ(·, y) is Lipschitz with a finite constant L := 1/τ . 12
Executable Agentic Memory for GUI Agent
Define the expected and empirical risks under D:
R(Q) := E(X,Y )∼D [ℓ(Q(X), Y )], m 1 X R̂S (Q) := ℓ(Q(xi ), yi ). m i=1
(30)
Let Q be the function class and ℜ̂m (Q) the empirical Rademacher complexity on {xi }m i=1 . Lemma A.3 (Rademacher generalization bound). With probability at least 1 − δ over the draw of S, r ln(2/δ) . sup R(Q) − R̂S (Q) ≤ 2L ℜ̂m (Q) + 3 2m Q∈Q
(31)
Proof. The proof proceeds in four steps. ′ ′ ′ m Step 1: Symmetrization. Let S = {(xi , yi )}m i=1 and S = {(xi , yi )}i=1 be two independent samples from D. By standard symmetrization arguments (see, e.g., Theorem 26.5 in Shalev-Shwartz & Ben-David, 2014): " # m 1 X ES sup R(Q) − R̂S (Q) ≤ 2ES,σ sup σi ℓ(Q(xi ), yi ) , (32) Q∈Q Q∈Q m i=1
where σ1 , . . . , σm are i.i.d. Rademacher random variables (Pr(σi = ±1) = 1/2). Step 2: Lipschitz contraction. Since ℓ(·, y) is L-Lipschitz on [τ, 1 − τ ] (with L = 1/τ ), and the Rademacher complexity satisfies the contraction principle: # " # " m m 1 X 1 X σi ℓ(Q(xi ), yi ) ≤ L · ES,σ sup σi Q(xi ) = Lℜ̂m (Q). (33) ES,σ sup Q∈Q m i=1 Q∈Q m i=1 Step 3: McDiarmid’s inequality.
Define Φ(S) := supQ∈Q R(Q) − R̂S (Q) . Changing a single sample (xi , yi )
2 ∞ ≤m (since losses are bounded when outputs are in [τ, 1 − τ ] and labels in [0, 1]). changes Φ(S) by at most 2∥ℓ∥ m
By McDiarmid’s inequality: Pr (Φ(S) − E[Φ(S)] ≥ t) ≤ exp −
Setting t =
q
2t2 m · (2/m)2
mt2 = exp − 2
.
(34)
ln(2/δ) and combining: 2m
Pr
sup R(Q) − R̂S (Q) ≥ 2Lℜ̂m (Q) + Q∈Q
r
ln(2/δ) 2m
! ≤
δ . 2
(35)
Step 4: Two-sided bound. Applying the same argument to R̂S (Q) − R(Q) and taking a union bound yields the two-sided result with probability 1 − δ. The constant 3 (instead of 2) in the final bound accounts for technical refinements in the symmetrization step. We now convert the uniform bound into an excess-risk bound between the learned predictor and the best achievable predictor. we assume approximate ERM: 13
Executable Agentic Memory for GUI Agent
R̂S (Qθ ) ≤ inf R̂S (Q) + ϵopt ,
(36)
Q∈Q
where ϵopt ≥ 0 is the optimization error. Define the in-class optimal predictor Q⋆Q := arg min R(Q).
(37)
Q∈Q
Then we can have the excess risk bound. Lemma A.4 (Excess risk bound). On the event of Lemma A.3, we have R(Qθ ) − R(Q⋆Q ) ≤ 2εgen (m, δ) + ϵopt ,
(38)
where r εgen (m, δ) := 2L ℜ̂m (Q) + 3
ln(2/δ) . 2m
(39)
Proof. On the event of Lemma A.3, for all Q ∈ Q: R(Q) ≤ R̂S (Q) + εgen ,
(40)
R̂S (Q) ≤ R(Q) + εgen .
(41)
Now we bound the excess risk: R(Qθ ) − R(Q⋆Q ) ≤ R̂S (Qθ ) + εgen − R(Q⋆Q )
(by (40) applied to Qθ )
(42)
(by approximate ERM (36))
(43)
≤ R̂S (Q⋆Q ) + ϵopt + εgen − R(Q⋆Q )
(since Q⋆Q ∈ Q)
(44)
≤ R(Q⋆Q ) + εgen + ϵopt + εgen − R(Q⋆Q )
(by (41) applied to Q⋆Q )
(45)
≤ inf
Q∈Q
R̂S (Q) + ϵopt + εgen − R(Q⋆Q )
= 2εgen + ϵopt .
(46)
In our context, the loss function ℓ(p, y) is a strictly proper scoring rule for Bernoulli distributions. Thus, we can use Pinsker’s inequality to obtain the following direct link from risk to L2 error. Let Q† (x) := E[Y | X = x] denote the true conditional expectation under D. In our setting, because training targets are generated from terminal rollouts under πu and unbiased Bellman backups (Lemma A.1), we have Q† (x) = Qπu (x). Lemma A.5. Let Q† (x) := E[Y | X = x] denote the true conditional expectation under D. Then for any predictor Q, h EX∼D
Q(X) − Q† (X)
2 i
≤
1 R(Q) − R Q† . 2
Proof. The proof proceeds in three steps: (i) express excess log-loss as KL divergence, (ii) apply Pinsker’s inequality, (iii) specialize to Bernoulli distributions. Step 1: Log-loss decomposition. identity:
For the log-loss ℓ(p, y) = −y log p − (1 − y) log(1 − p) with p, y ∈ (0, 1), we have the
ℓ(p, y) = ℓ(y, y) + KL(Bern(y)∥Bern(p)), where KL(Bern(y)∥Bern(p)) = y log yp + (1 − y) log 1−y 1−p . 14
(47)
Executable Agentic Memory for GUI Agent
Verification: ℓ(y, y) + KL(Bern(y)∥Bern(p))
(48)
y 1−y = [−y log y − (1 − y) log(1 − y)] + y log + (1 − y) log p 1−p
(49)
= −y log y − (1 − y) log(1 − y) + y log y − y log p + (1 − y) log(1 − y) − (1 − y) log(1 − p)
(50)
= −y log p − (1 − y) log(1 − p)
(51)
= ℓ(p, y).
(52)
Step 2: Pinsker’s inequality. The classical Pinsker’s inequality states that for any two probability distributions P and Q: TV(P, Q)2 ≤
1 KL(P ∥Q), 2
(53)
where TV(P, Q) = supA |P (A) − Q(A)| is the total variation distance. Step 3: Specialization to Bernoulli.
For Bernoulli distributions Bern(y) and Bern(p): TV(Bern(y), Bern(p)) = |y − p|.
(54)
(This follows by taking A = {1} in the TV definition.) Applying Pinsker’s inequality: (y − p)2 ≤
1 1 KL(Bern(y)∥Bern(p)) = (ℓ(p, y) − ℓ(y, y)) . 2 2
Step 4: Conditional expectation and integration. p = Q(x): (Q(x) − Q† (x))2 ≤
(55)
Fix x and let y = Q† (x) = E[Y | X = x]. Taking the prediction
1 ℓ(Q(x), Q† (x)) − ℓ(Q† (x), Q† (x)) . 2
(56)
Taking expectation over X ∼ D: 1 EX (Q(X) − Q† (X))2 ≤ EX ℓ(Q(X), Q† (X)) − ℓ(Q† (X), Q† (X)) 2 1 = EX [ℓ(Q(X), Q† (X))] − EX [ℓ(Q† (X), Q† (X))] . 2
(57) (58)
Since Q† (x) = E[Y | X = x] minimizes the conditional expected log-loss, we have EY |X [ℓ(Q(X), Y )] ≥ EY |X [ℓ(Q† (X), Y )] = ℓ(Q† (X), Q† (X)) + H(Y |X),
(59)
where H(Y |X) is the conditional entropy (which cancels in the difference). Thus: 1 EX (Q(X) − Q† (X))2 ≤ R(Q) − R(Q† ) . 2
We now prove theorem 5.2. 15
(60)
Executable Agentic Memory for GUI Agent
Theorem A.6 (Restatement of Theorem 5.2). With probability at least 1 − δ, the learned predictor Qθ satisfies ∥Qθ − Qπu ∥2,ρC ≤ ϵbias (m, δ),
(61)
where r ϵbias (m, δ) :=
1 (ϵapprox + 2εgen (m, δ/2) + ϵopt ), 2
(62)
with ϵapprox := R(Q⋆Q ) − R(Q† ) ≥ 0. Proof. The proof proceeds in five steps. We decompose the excess risk of Qθ relative to Q† : R(Qθ ) − R(Q† ) = R(Qθ ) − R(Q⋆Q ) + R(Q⋆Q ) − R(Q† ) . {z } | {z } |
Step 1: Decompose total excess risk.
estimation + optimization
Step 2: Bound estimation + optimization error.
approximation
By Lemma A.4 with confidence δ/2:
R(Qθ ) − R(Q⋆Q ) ≤ 2εgen (m, δ/2) + ϵopt . Step 3: Identify approximation error.
(63)
(64)
The approximation error is: ϵapprox := R(Q⋆Q ) − R(Q† ) ≥ 0,
(65)
which is non-negative since Q† is the Bayes-optimal predictor (minimizer of population risk over all measurable functions). Step 4: Combine and apply Lemma A.5.
With probability at least 1 − δ/2:
R(Qθ ) − R(Q† ) ≤ ϵapprox + 2εgen (m, δ/2) + ϵopt .
(66)
1 EX∼D (Qθ (X) − Q† (X))2 ≤ R(Qθ ) − R(Q† ) . 2
(67)
By Lemma A.5:
Step 5: Identify Q† = Qπu and conclude. In our setting, training targets are generated from unbiased terminal rollouts under πu with Bellman backups (Lemma A.1). Thus Q† (s, a) = E[Y | X = (s, a)] = Qπu (s, a). Taking square roots: ∥Qθ − Qπu ∥2,ρC =
q
E(S,A)∼ρC [(Qθ (S, A) − Qπu (S, A))2 ]
(68)
r
1 (ϵapprox + 2εgen (m, δ/2) + ϵopt ) 2 = ϵbias (m, δ). ≤
(69) (70)
A.2. Proof of Theorem 5.3 Theorem A.7 (Restatement of Theorem 5.3). Suppose the bias consistency condition holds: ϵbias (m, δ) < ∆∗min /2. Let ∆eff := ∆∗min − 2ϵbias (m, δ) > 0. Then for the greedy path ât = arg maxa∈A(s∗t ) Q̄n (s∗t , a) to coincide with the optimal path with probability at least 1 − δ, it suffices that 32(K − 1)c2 ln(Hn/δ) π2 n≥ + 2(K − 1) 2N0 + . (71) ∆2eff 3 Proof. The proof adapts the UCT analysis of Kocsis & Szepesvári (2006) to our guided-MCTS setting. 16
Executable Agentic Memory for GUI Agent
Step 1: Setup and notation. At each decision node s∗t , UCT treats action selection as a multi-armed bandit with K = |A(s∗t )| arms. Let Ta (n) denote the number of times action a is selected after n total simulations. The payoff distributions are non-stationary because subtree estimates evolve with exploration. Step 2: Apply Kocsis-Szepesvári Theorem 1. By Theorem 1 of (Kocsis & Szepesvári, 2006), for UCB1 applied to a non-stationary bandit with bias (drift) bounded by ϵ, each suboptimal arm a with gap ∆a > 2ϵ satisfies: E[Ta (n)] ≤
16c2 ln n π2 + 2N + . 0 (∆a − 2ϵ)2 3
(72)
In our setting, the bias is ϵ = ϵbias (m, δ) (from Theorem 5.2), and for each suboptimal action a ̸= a∗t : ∆a := Qπu (s∗t , a∗t ) − Qπu (s∗t , a) ≥ ∆∗min .
(73)
π2 π2 16c2 ln n 16c2 ln n + 2N + + 2N + ≤ . 0 0 (∆a − 2ϵbias )2 3 ∆2eff 3
(74)
Thus: E[Ta (n)] ≤
Summing over all K − 1 suboptimal actions: X π2 16(K − 1)c2 ln n . E[Ta (n)] ≤ + (K − 1) 2N + 0 ∆2eff 3 ∗
Step 3: Sum over suboptimal actions.
(75)
a̸=at
Step 4: Lower bound optimal action visits. E[Ta∗t (n)] = n −
Since
P
a Ta (n) = n:
16(K − 1)c2 ln n π2 E[Ta (n)] ≥ n − . − (K − 1) 2N0 + ∆2eff 3 ∗
X
(76)
a̸=at
Step 5: Condition for optimal action dominance. For the optimal action to be selected (i.e., have the highest empirical mean), it suffices that E[Ta∗t (n)] > n/2, which requires: 32(K − 1)c2 ln n π2 n> + 2(K − 1) 2N + . (77) 0 ∆2eff 3 Step 6: Union bound over path.
The optimal path has H decision points. Taking a union bound: Pr(all ât = a∗t ) ≥ 1 − H ·
δ δ =1− . 2H 2
(78)
Combined with the 1 − δ/2 probability from the bias consistency guarantee (Theorem 5.2), the total success probability is at least 1 − δ.
B. Additional Experimental Results This appendix provides detailed analyses of the additional experimental results presented in the supplementary figures. We systematically examine training dynamics, path extraction strategies, training methodologies, hyperparameter sensitivity, and their implications for the proposed Executable Agentic Memory (EAM) framework. B.1. Effect of Action Groups We construct ablation experiments on action groups. Fig. 4 presents the length distribution of actions in the KGs. Beyond atomic actions, our BPE-based merging mechanism constructs action groups encapsulating multi-step sequences, with lengths following a long-tail distribution. AndroidWorld exhibits more long-sequence groups due to higher task complexity. Fig. 5 shows that action groups yield significant improvements in both success rate and latency, with benefits more pronounced on AndroidWorld. By consolidating frequent sequences into reusable groups, the MCTS search space is significantly reduced, enabling more efficient planning. 17
Executable Agentic Memory for GUI Agent
3 H U F H Q W D J H
3 H U F H Q W D J H
$ F W L R Q / H Q J W K
(a) AndroidWorld
$ F W L R Q / H Q J W K
(b) DroidTask
Z R D F W L R Q J U R X S
Z D F W L R Q J U R X S
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
/ D W H Q F \ I R U 3 D W K ( [ W U D F W L R Q
6 X F F H V V 5 D W H
Figure 4. Distribution action sequence lengths in KGs
Z R D F W L R Q J U R X S
Z D F W L R Q J U R X S
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
% H Q F K P D U N
% H Q F K P D U N
(a) Success Rate
(b) Latency
Figure 5. Effect of action group on performance and efficiency.
B.2. Training Loss Dynamics Across Self-Learning Rounds Fig. 6 presents the training loss curves across four self-learning rounds for three model sizes (Qwen2.5-0.5B-Instruct, Qwen2.5-1.5B-Instruct, and Qwen2.5-3B-Instruct) evaluated on three benchmarks (AndroidWorld, DroidTask, and MobileMiniWob). Progressive Loss Reduction. A salient pattern emerges across all configurations: the initial loss at the beginning of each subsequent round starts consistently lower than the previous round. This progressive reduction in starting loss demonstrates that the Q-model successfully retains and builds upon knowledge acquired in previous iterations, validating the effectiveness of our iterative self-training pipeline. Formally, this observation suggests that the empirical risk R̂S (Qθ ) decreases across rounds, which according to Lemma A.4, implies corresponding reductions in the true risk R(Qθ ). Convergence Characteristics. All training curves exhibit rapid initial descent followed by stabilization, typically converging within the first 100–150 training steps. The converged loss values decrease monotonically across rounds, indicating that the quality of self-generated training data improves as the Q-model becomes more accurate at value estimation. This phenomenon creates a virtuous cycle: better value estimates lead to more informative MCTS rollouts, which in turn produce higher-quality Bellman backup targets, further improving subsequent training rounds. Model Capacity Effects. Larger models consistently achieve lower final loss values across all benchmarks. This performance gap reflects the increased representational capacity of larger models to capture complex relationships between GUI states, actions, and their associated Q-values. The relationship can be understood through the lens of approximation error ϵapprox in Theorem 5.2: larger model classes Q reduce the gap R(Q⋆Q ) − R(Q† ), yielding tighter bias bounds. 18
Executable Agentic Memory for GUI Agent
$ Q G U R L G : R U O G 4 Z H Q % L Q V W U X F W
/ R V V
7 U D L Q L Q J 6 W H S V ' U R L G 7 D V N 4 Z H Q % L Q V W U X F W
7 U D L Q L Q J 6 W H S V ' U R L G 7 D V N 4 Z H Q % L Q V W U X F W
7 U D L Q L Q J 6 W H S V ' U R L G 7 D V N 4 Z H Q % L Q V W U X F W
7 U D L Q L Q J 6 W H S V 0 R E L O H 0 L Q L : R E 4 Z H Q % L Q V W U X F W
7 U D L Q L Q J 6 W H S V
7 U D L Q L Q J 6 W H S V
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
7 U D L Q L Q J 6 W H S V 0 R E L O H 0 L Q L : R E 4 Z H Q % L Q V W U X F W
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
7 U D L Q L Q J 6 W H S V 0 R E L O H 0 L Q L : R E 4 Z H Q % L Q V W U X F W
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
/ R V V
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
$ Q G U R L G : R U O G 4 Z H Q % L Q V W U X F W
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
/ R V V
/ R V V
$ Q G U R L G : R U O G 4 Z H Q % L Q V W U X F W
5 R X Q G 5 R X Q G 5 R X Q G 5 R X Q G
7 U D L Q L Q J 6 W H S V
Figure 6. Training loss curves across self-learning rounds. We show the training loss for each round across different model sizes and benchmarks.
19
* U H H G \ % R 1
0 & 7 6
6 X F F H V V 5 D W H
6 X F F H V V 5 D W H
Executable Agentic Memory for GUI Agent
%
%
0 R G H O 6 L ] H
0 & 7 6
%
* U H H G \ % R 1
%
(a) AndroidWorld
%
0 R G H O 6 L ] H
%
(b) DroidTask
Figure 7. The impact of different path extraction methods on performance.
B.3. Comparison of Path Extraction Methods Figure 7 compares three path extraction strategies across different model sizes (0.5B, 1.5B, and 3B parameters) on AndroidWorld and DroidTask: • Greedy: Selects actions with highest Q-values without exploration, i.e., at = arg maxa∈A(st ) Qθ (st , a). • Best-of-N (BoN): Samples 10 candidate paths independently and selects the 5 with the highest cumulative Q-value (for fair comparison with MCTS). • MCTS: Employs the full tree search procedure with UCT-based exploration-exploitation balancing. Consistent MCTS Superiority. MCTS consistently outperforms both Greedy and BoN strategies across all model sizes and benchmarks. The consistent advantage of MCTS demonstrates the substantial value of structured exploration during path extraction. Theoretical Interpretation. These empirical findings align precisely with our theoretical analysis. Theorem 5.3 establishes that MCTS recovers the optimal path with high probability when sufficient simulations are performed, with complexity HKc2 ln(Hn/δ) scaling as O (∆∗ −2ϵbias )2 . The Greedy strategy, by contrast, commits irrevocably to the highest-valued action without min accounting for estimation uncertainty, making it vulnerable to errors in Qθ . B.4. Impact of Training Strategies on Q-Model Performance
6 X F F H V V 5 D W H
6 X F F H V V 5 D W H
8 Q W U D L Q H G
, Q L W
% L Q D U \
7 U D L Q L Q J 6 W U D W H J \
4 Y D O X H
(a) AndroidWorld
8 Q W U D L Q H G
, Q L W
% L Q D U \
7 U D L Q L Q J 6 W U D W H J \ (b) DroidTask
Figure 8. Performance with Different Training Strategies.
1. Untrained: The base language model without any task-specific fine-tuning. 20
4 Y D O X H
Executable Agentic Memory for GUI Agent
2. Init: Initialization via preference learning on expert trajectories using the pairwise ranking loss (Equation 7). 3. Binary: Training with binary outcome labels indicating path success (y = 1) or failure (y = 0). 4. Q-value: Our proposed approach using soft Q-value targets computed via Bellman backup. All experiments employ the 3B model with identical MCTS inference configurations (N = 50 iterations, c = 10). Necessity of Task-Specific Training. The untrained model achieves the lowest success rate, establishing that raw language model capabilities are insufficient for effective Q-value estimation in GUI navigation. Preference-Based Initialization. The Init strategy achieves substantial improvements over the untrained baseline. This confirms that relative preference information from expert trajectories provides valuable supervision for warming up the Q-model. The Bradley-Terry formulation (Equation 7) effectively translates these preferences into initial value estimates that, while not perfectly calibrated, establish meaningful action rankings. Limitations of Binary Supervision. Training with binary outcome labels yields moderate performance. While binary labels capture the ultimate success or failure of paths, they provide identical supervision signals to all actions along successful trajectories and all actions along failed trajectories. This coarse granularity fails to distinguish among the quality of intermediate decisions. Superiority of Q-Value Training. Our proposed Q-value training achieves the highest performance: approximately 52.6% on AndroidWorld and 86.1% on DroidTask. The substantial gains over binary training demonstrate the value of continuous Q-value targets. By computing targets via Bellman backup: Q̂(s, a) ← r(s, a) +
1 |A(s′ )|
X
Q̂(s′ , a′ ),
(79)
a′ ∈A(s′ )
we obtain supervision signals that capture the nuanced probability of success from each state-action pair, enabling finegrained credit assignment across the trajectory.
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
N
/ D W H Q F \ I R U 3 D W K ( [ W U D F W L R Q
6 X F F H V V 5 D W H
B.5. Effect of MCTS Iteration Count
(a) Success Rate
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
N
(b) Latency
Figure 9. The impact of different number of MCTS iterations on performance.
Figure 9 investigates the trade-off between MCTS simulation budget and performance by varying the number of iterations N ∈ {10, 30, 50, 100}. We measure both success rate and path extraction latency across all three benchmarks using the 3B model. Monotonic Performance Scaling. Success rate increases monotonically with MCTS iterations across all benchmarks that additional simulation budget enables more thorough exploration of the search space, increasing the probability of discovering optimal paths. Diminishing Returns. The performance gains exhibit pronounced diminishing returns. Quantitatively, the marginal improvement per additional 10 iterations decreases substantially: 21
Executable Agentic Memory for GUI Agent
• N : 10 → 30: +10 points on AndroidWorld • N : 30 → 50: +6 points on AndroidWorld • N : 50 → 100: 0.7 points on AndroidWorld This sublinear scaling suggests that moderate iteration counts capture most of the benefit from tree search, with additional simulations primarily refining already-promising paths rather than discovering qualitatively better alternatives. Latency Characteristics. Path extraction latency scales approximately linearly with iteration count. This linear scaling, combined with the sublinear performance gains, implies a favorable efficiency trade-off at moderate iteration counts. Practical Operating Points. The results suggest N = 30 or N = 50 as practical operating points. At N = 50, the system achieves over 95% of the N = 100 performance on all benchmarks while requiring only 50% of the computation time. Connection to Theoretical Bounds. These findings align with Theorem 5.3, which establishes simulation complexity scaling as: 32(K − 1)c2 ln(Hn/δ) π2 n≥ + 2(K − 1) 2N + . (80) 0 ∆2eff 3 The logarithmic dependence on n in the bound is consistent with the observed diminishing returns. The empirical observation that moderate N suffices suggests that practical task instances have relatively large effective action gaps ∆eff = ∆∗min −2ϵbias , enabling efficient path recovery without exhaustive search.
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
6 X F F H V V 5 D W H
6 X F F H V V 5 D W H
B.6. Influence of Model Size and Exploration Constant
%
%
% D V H 0 R G H O 6 L ] H
%
$ Q G U R L G : R U O G 0 R E L O H 0 L Q L : R E ' U R L G 7 D V N
c
(b) Exploration constant c
(a) Model size
Figure 10. The impact of model size and exploration constant on performance.
Figure 10 presents two hyperparameter studies: (a) the effect of base model size on success rate across 0.5B, 1.5B, and 3B parameters; and (b) the impact of the UCT exploration constant c ∈ {0, 5, 10, 20} on performance, where c = 0 corresponds to pure exploitation. Model Size Analysis. Larger models achieve higher success rates across all benchmarks. Exploration Constant Analysis. Performance peaks at c = 10 across all benchmarks Both pure exploitation (c = 0) and excessive exploration (c = 20) yield degraded performance. At c = 0, the search degenerates to greedy selection, forfeiting the benefits of exploration demonstrated in Section B.3. At c = 20, the exploration bonus dominates the Q-value term in UCT, causing the search to behave nearly randomly and waste simulation budget on unpromising branches. Benchmark-Specific Sensitivity. AndroidWorld shows the highest sensitivity to c. DroidTask and MobileMiniWob++ exhibit more stable performance. This differential sensitivity correlates with task complexity: AndroidWorld’s deeper search spaces and longer optimal paths create more opportunities for both beneficial exploration and wasteful over-exploration. 22
Executable Agentic Memory for GUI Agent
Theoretical Perspective. The exploration constant c appears directly in the UCT criterion: s ln N (s) UCT(s, a) = Q(s, a) + c , N (s, a)
(81)
and in the sample complexity bound of Theorem 5.3, where it contributes to the c2 term in the numerator. The empirical finding that moderate c optimizes performance validates the theoretical exploration-exploitation trade-off: insufficient exploration risks committing to suboptimal paths before adequately evaluating alternatives, while excessive exploration incurs unnecessary simulation cost.
C. Training Data We train our Q-model in two phases, including initialization training and self-training iterations. C.1. Step-level Preference Dataset for Initialization Training Our training data pairs are derived from AMEX, which contains a large collection of expert trajectories with semantic descriptions for each action step, as well as semantic annotations for task-irrelevant elements on each page. For each page in the expert trajectories, we construct preference optimization pairs consisting of (expert action description, multiple task-irrelevant element descriptions) as follows: { "instruction": List\".",
"Open Google Tasks.
"history actions":
Delete all completed tasks in the \"Work
[],
"page caption": "The page displays a list of tasks organized by categories such as work, health, and family, with options to mark tasks as complete, add stars, and view details.", "correct actions": [ "View the list of completed tasks" ], "false actions": [ "View details of the task ’submit progress report’ due on Monday, April 15", "View details of the task ’project x’ with 1 subtask", "View tasks under ’work’ category", "View details of the task ’send a draft to the team’ due on Friday, April 12" ] }
C.2. Dataset Generated by MCTS Rollouts Following initialization, the value model is iteratively trained to predict the Q-value of state-action pairs. An example of dataset from AndroidWorld is illustrated below. Input: <|user|>: Task: Add the expenses from expenses.jpg in Simple Gallery Pro to pro expense. You are at: This is an expense tracking dashboard that allows users to monitor their spending patterns through a weekly calendar view and detailed transaction history, while providing quick access to add new expenses via the floating action button. Executed path: Start of Task Proposed action: Output: <|assistant|>: Navigate from expense tracking application to gallery app to locate and review expense-related images or receipts for reference during expense entry workflow<end of step> Label:
0.7679166666666666
23
Executable Agentic Memory for GUI Agent
D. Prompts D.1. Prompt for Sub-goals Generation at Offline Exploration Phase Given a user task, the current screenshot of {app name}, and available UI elements, generate multiple potential sub-goals to progress toward completing the user task. Each sub-goal must: 1. Start with interacting with a specific UI element from the provided element list 2. Be expressed as a single, clear directive following the pattern: [Starting action] + [Specific steps] + [End goal] 3. Be achievable within approximately 3 actions (AT MOST 5) from the anchor element 4. Provide a concrete target state that advances toward the user task completion Context Information: - User Task: {user task} - App name: {app name} - Package name: {package name} - Current screen elements (Only interact with *visible=true elements): {element list} - Activity context: {activity list} - Recent History Action (up to 5): {action history} - Sub-goals History: {subgoal history} - State Summary: {state summary} Task Execution Analysis: Before generating new sub-goals, analyze the current execution state: 1. Completed Progress: Review the sub-goals history to understand what has already been accomplished toward the main task 2. Current Position: Based on the state summary and recent actions, identify where you are in the task workflow 3. Remaining Work: Determine what specific components of the user task still need to be completed 4. Next Logical Steps: Identify the most logical next actions that build upon completed sub-goals Sub-goal Generation Strategy: - Continuation Focus: Generate sub-goals that logically continue from where previous sub-goals left off - Avoid Redundancy: Do not repeat actions or objectives that have already been successfully completed - Progressive Advancement: Each sub-goal should represent a clear step forward in the overall task completion For each sub-goal, provide: 1. Anchor Element: The specific UI element ID/description from the list to start with 2. Sub-goal: Single directive sentence following [Starting action] + [Specific steps] + [End goal] pattern 3. Confidence Score: How likely this sub-goal is to advance toward task completion (0.0-1.0) Format each sub-goal as: Sub-goal [N]: Anchor: [Element ID/description from element list] Directive: [Single clear instruction with starting action + steps + end goal] Confidence: [0.0-1.0]
24
Executable Agentic Memory for GUI Agent
D.2. Prompt for Progress Evaluation during Exploration Given the user task, action history, and current screenshot of {app name}, evaluate the current exploration state and determine the next action strategy. Context Information: - User Task: {user task} - App name: {app name} - Package name: {package name} - Recent Action History: {action history} (if the last action is ’{"action type": "status", "goal status": means the last sub-goal was complete successfully) - Sub-goals History: {subgoal history} - Current screen elements: {element list}
"complete"}’, it
Analysis Requirements: 1. Compare the current state with the expected end goal of the user task 2. Evaluate whether the recent actions are leading toward task completion 3. Assess if the current exploration path is meaningful and relevant 4. Consider whether all required steps have been executed successfully 5. Verify if the current screen/state indicates task completion 6. Account for any error states, dead-ends, or repetitive actions in the history 7. Make sure to use answer action for information retrieval task ({"action type": "answer", "text": "<answer text>"} is the last action in the action history) 8. Be strict about completion - partial progress is not completion Evaluation Criteria: - Has the user task’s primary objective been achieved? (COMPLETED) * Have we completed all the sub-goals required by the task and at the expected final state/screen for this task? - Are we making meaningful progress toward the goal? (CONTINUE) - Are we stuck, going in wrong direction, or exploring irrelevant paths? (BACKTRACK) - Is there clear evidence of task completion, progress, or deviation in the current state? Format your response as: Reasoning: [Detailed analysis of current progress, referencing specific elements from action history, current state, and task relevance. Explain why we should continue, backtrack, or if task is complete] Result: [CONTINUE/BACKTRACK/COMPLETED]
25
Executable Agentic Memory for GUI Agent
D.3. Prompt for Action Group Mining You are an AI assistant specialized in generating high-level common UI operation nodes which can be part of a variety of operations. You need to generate a complete description of a high-level action node based on the given chain information. Please generate a high-level action node based on the following UI operation chain information: Task description: {task description} Chain operations: {chain operations} Chain element details: {element details} Chain reasoning results: {reasoning results} Please generate a concise description of the high-level action node, including the following fields: - action id: Generate a unique ID for the high-level action (format like: "high level action xxx") - name: Concise name of the high-level action - function description: Brief description of the action’s functionality and purpose - preconditions: Required conditions before executing this action, including: * task state: What task context or state is needed * page state: What page/interface state must be present - post conditions: Resulting state after completing this action, including: * task state: How the task context changes * page state: What page/interface state is reached - element sequence: Simplified sequence of key elements in this action: * element id: Element ID * atomic action: Action performed * order: Execution order
26