PaperlayerView exact revision on arXiv

Source-linked AI summary

Android Coach: Improve Online Agentic Training Efficiency with Single State Multiple Actions

Guo Gan, Yuxuan Ding, Cong Chen, Yuwei Ren, Yin Huang, Hong Zhou

arXiv:2604.07277v2cs.LGcs.AI

TL;DR

Online Android-agent RL is costly because emulator interactions are high-latency and Single State Single Action rollouts underuse expensive states. Android Coach instead samples multiple actions per online state, evaluates them with a learned critic, and uses process rewards plus group-wise advantage estimation. It improves success rates on AndroidLab and AndroidWorld and reaches 1.4x higher training efficiency than PPO and GRPO at matched success rates.

  • Problem

    Online RL for Android agents is expensive because emulator interactions are high-latency and existing Single State Single Action rollouts do not fully exploit costly states.

  • Method

    Android Coach adopts Single State Multiple Actions, using a critic to evaluate multiple sampled actions without additional emulator execution, with process rewards and a group-wise leave-one-out advantage estimator.

  • Results

    Android Coach improves success rates by 7.5% on AndroidLab and 8.3% on AndroidWorld over original UI-TARS, and achieves 1.4x higher training efficiency than PPO and GRPO at matched success rates.

  • Takeaways & Limitations

    Android Coach substantially enhances online training efficiency while improving performance through multiple-action use of each online state.

  • Takeaways & Limitations

    The study does not optimize system architecture for large-scale parallelization, does not examine supervised fine-tuning, and leaves reward verification methods for future work.

Abstract

from arXiv · show

Online reinforcement learning (RL) serves as an effective method for enhancing the capabilities of Android agents. However, guiding agents to learn through online interaction is prohibitively expensive due to the high latency of emulators and the sample inefficiency of existing RL algorithms. We identify a fundamental limitation in current approaches: the Single State Single Action paradigm, which updates the policy with one-to-one state-action pairs from online one-way rollouts without fully exploring each costly emulator state. In this paper, we propose Android Coach, a novel framework that shifts the training paradigm to Single State Multiple Actions, allowing the agent to sample and utilize multiple actions for a single online state. We enable this without additional emulator overhead by learning a critic that estimates action values. To ensure the critic serves as a reliable coach, we integrate a process reward model and introduce a group-wise advantage estimator based on the averaged critic outputs. Extensive experiments demonstrate the effectiveness and efficiency of Android Coach: it achieves 7.5% and 8.3% success rate improvements on AndroidLab and AndroidWorld over UI-TARS-1.5-7B, and attains 1.4x higher training efficiency than Single State Single Action methods PPO and GRPO at matched success rates.

1 Introduction

Online GUI-agent RL is limited by costly emulator interactions and one-action-per-state rollouts. Android Coach addresses this with Single State Multiple Actions, a critic-guided framework that reuses each online state and improves training efficiency.

  • Motivation: Online GUI-agent RL faces high-latency emulator interactions and poor sample efficiency, while SSSA rollouts collect only one action per costly state.The emulator interaction time is reported as 1.7× the time for model loading and inference.
  • Android Coach: Android Coach adopts Single State Multiple Actions to generate and use multiple actions for each online state without additional emulator execution.A critic estimates action values for sampled actions, allowing more exploration within the same interaction cost.
  • Android Coach: The framework trains its critic with online rollout returns combining process and outcome rewards, then uses leave-one-out advantages to update the actor.The process reward model provides step-level supervision, including correct steps within failed trajectories.
  • Results: Extensive dynamic-benchmark experiments evaluate Android Coach’s training efficiency and component effectiveness in online reinforcement learning.The paper presents the framework as an online actor-critic approach designed to increase training samples from each rollout state.
  • Training pipeline: Android Coach follows an online rollout, critic-update, multiple-sampling, and actor-update pipeline.The actor samples multiple actions for reused online states, evaluates them with the critic, and updates the policy from their advantages.

2 Related Work

GUI-agent RL spans offline and online training, while existing multiple-action methods face constraints from dynamic environments and large action spaces. Android Coach introduces online SSMA exploration with critic-based action evaluation and process-aware supervision.

  • GUI-agent RL: Offline GUI-agent methods depend on pre-collected expert data, whereas online training supports exploration and trial-and-error in real environments.Offline methods are limited by data quality and difficulty adapting to environment updates.
  • GUI-agent RL: Existing online GUI-agent methods often use SSSA rollouts, leaving expensive states underexploited and requiring more interaction steps.The related-work discussion motivates generating and evaluating multiple actions for each state under limited interaction budgets.
  • Advantage estimation: Trajectory-level methods compute advantages from outcome rewards, while critic-based methods estimate action values but typically lack process-reward supervision online.Offline step-level supervision avoids this limitation but inherits the constraints of offline training.
  • ANDROID COACH: ANDROID COACH is presented as an online SSMA framework that improves sample efficiency under limited interaction costs and introduces ACLOO for advantage estimation.The table comparison identifies SSMA, SSSA, and ACLOO as the relevant framework distinctions.
  • Multiple-action estimation: Exact multiple-action evaluation is restricted to small action spaces, making it impractical for reasoning VLM-based GUI agents with combinatorially large action spaces.GRPO also cannot provide the same long-term value supervision through parallel follow-up executions in dynamic, irreversible GUI environments.

3 Android Coach

Android Coach trains an online actor-critic agent with Single State Multiple Actions, reusing costly online states to evaluate multiple candidate actions through a learned critic. Process rewards, online critic updates, and leave-one-out advantages support reliable action evaluation and policy optimization.

  • Reliable Critic: The critic is trained from online rollout returns that combine process rewards from intermediate actions with outcome rewards from final results.A pretrained process reward model supplies step-level supervision, and the outcome verifier supplies final-result rewards for critic targets.
  • Reliable Critic: Before online reinforcement learning, the value model is pretrained with the process-reward dataset to reduce misleading guidance from an initially unprepared critic.The paper identifies early GUI value estimation as a challenge when actor and critic are trained together from the beginning.
  • Single State Multiple Actions: For each online state, the current policy samples k candidate actions, and the critic scores them without additional emulator interactions.This reuses costly states from online trajectories and enables further exploration within the same interaction budget.
  • Evaluation: Table 2 reports success rates for proprietary and open-source models on AndroidWorld and AndroidLab, with QD and OP denoting query-detect and operation task types.Standard deviations are reported for non-proprietary models according to the table caption.
  • Actor-Critic Leave-One-Out: Actor-Critic Leave-One-Out advantages compare each candidate action with the other sampled actions, reducing variance without a separate value network.The estimator also captures relative action quality and guides updates toward actions that outperform the within-state average.
  • Training Procedure: The algorithm alternates parallel online rollouts, critic updates from process and outcome rewards, and actor updates using resampled actions, Q-values, and advantages.The actor is optimized with a policy-gradient update after the critic has been updated on the collected batch.

4 Experiments

Experiments evaluate Android Coach on AndroidLab and AndroidWorld against RL baselines, showing improved performance and training efficiency. Ablations attribute gains to multiple action samples, ACLOO, critic initialization, and process rewards.

  • Main Results: Android Coach raises UI-TARS-1.5-7B success rate from 31.9% to 39.4% on AndroidLab and from 32.8% to 41.1% on AndroidWorld.
  • Training Efficiency: 1.4× higher efficiency than SSSA methods GRPO and PPO is achieved at comparable success rates, while performance exceeds PPO by 5.2% under the same training time.The method samples more actions while using fewer environment interactions under a fixed training budget.
  • Action Samples: AndroidLab success rate increases from 34.8% at N = 1 to 37.0% at N = 4, while training time rises sub-linearly to 1.62× the baseline.Increasing N to 8 yields marginal additional performance gains and requires 2.18× baseline time.
  • Advantage Estimation: Removing ACLOO lowers success rate to 36.0%, whereas ACLOO produces a more stable upward outcome-reward trend during training.
  • Critic Initialization: Pre-training Q provides a stable initialization and more consistent critic-loss convergence during joint policy optimization.
  • Process Rewards: Process rewards improve success rate from 37.0% to 39.4% on AndroidLab and from 39.1% to 41.1% on AndroidWorld.Process rewards also improve reasonable operation ratio by 6.6% and 5.1% on the two benchmarks, respectively.

5 Conclusion

Android Coach uses Single State Multiple Actions to improve online training efficiency by estimating multiple sampled-action returns without extra emulator overhead. A Process Reward Model guides critic training, while a group-wise advantage estimator stabilizes policy updates and experiments show improved performance.

  • Android Coach estimates returns for multiple sampled actions without additional emulator overhead, using a Process Reward Model and low-variance group-wise advantage estimator.

Limitations

The paper identifies system-scaling, initialization, and reward-verification boundaries for Android Coach. It does not optimize large-scale parallelization, study supervised fine-tuning, or fully eliminate Outcome Verifier errors.

  • The method improves sample efficiency algorithmically but does not optimize system architecture for large-scale parallelization.Integrating it into advanced engineering pipelines could further improve wall-clock training efficiency.
  • Experiments apply reinforcement learning directly to a base GUI model and do not study supervised fine-tuning because of budget constraints.The paper notes that supervised fine-tuning could raise the performance upper bound.
  • Outcome rewards depend partly on the Outcome Verifier, whose occasional GPT-4o hallucinations make rewards imperfect.Future work targets more reliable verification methods that avoid LLM hallucinations and labor-intensive manually designed rules.

A Implementation Details

Implementation uses full-parameter training on a single eight-A100 node, parallel emulators, and vLLM-accelerated rollouts. Outcome verification combines AndroidWorld rules with GPT-4o for AndroidLab, while PRM and baseline evaluations use specified training and comparison procedures.

  • Policy Training: Policy models are full-parameter fine-tuned on a single node with 8 NVIDIA A100 GPUs using a modified verl pipeline and parallel emulators matching batch size.vLLM accelerates inference during rollout.
  • Outcome Verification: Outcome rewards use AndroidWorld’s official rule-based judge and GPT-4o with compressed XML and actions for AndroidLab trajectories.
  • PRM Training: The Process Reward Model is full-parameter SFT-trained with verl on 8 NVIDIA A100 GPUs, using FSDP2, batch size 32, and 2 epochs.Optimization uses AdamW with cosine decay and gradient clipping.
  • Baselines: PPO and GRPO use the same eight-80GB-A100 hardware configuration, verl implementations, and Outcome Verifier as Android Coach.
  • Model Evaluation: Selected open-weight GUI agents are re-evaluated with identical inputs, while proprietary-model results are taken from prior reports because of budget constraints.

B Benchmarks and Data

Experiments use controlled Android 13 emulator environments at API Level 33 with the complete Google Mobile Services suite.

  • All experiments run in controlled emulator environments configured with Android 13 at API Level 33 and the complete Google Mobile Services suite.

B.2 Benchmarks

The evaluation uses AndroidLab and AndroidWorld, which differ in task scale, application coverage, and scenario variability.

  • AndroidLab: AndroidLab contains 138 tasks across nine mobile applications with fixed initial states and expected outcomes.
  • AndroidWorld: AndroidWorld contains 116 tasks across 20 applications with dynamically generated inputs and adaptive initialization states.

B.3 Data

The paper combines Android data, evaluator-generated supervision, and a staged online training algorithm that collects trajectories, trains a critic, and updates the actor with multiple actions per state.

  • Data: AndroidControl provides 15,283 demonstrations across 833 Android applications and is used exclusively to construct the Process Reward training dataset.
  • Data: The Process Reward training dataset filters successful, non-redundant trajectories and labels eight candidate reasoning-action pairs per state using ground-truth alignment.
  • Training procedure: The algorithm first collects online trajectories, then assigns returns, updates the critic, and updates the actor.
  • Training procedure: For each online state, the actor generates K responses, computes advantages with ACLOO, and applies a PPO loss.

D.1 Proof of Unbiasedness

The proof establishes that the ACLOO policy-gradient estimator is unbiased by showing its bias term is zero under independent action sampling.

  • Lemma 1 states that the policy-gradient estimator gi is an unbiased estimator of the true policy gradient ∇θJ(θ).
  • The estimator’s policy-gradient term depends only on the sampled action, while the leave-one-out baseline depends on the other samples.
  • Because the sampled action and leave-one-out baseline are independent, the baseline contribution to the expected gradient separates into the product of expectations.
  • The proof concludes that the bias term is zero, so the estimator’s expectation equals the true policy gradient.

D.2 Proof of Variance Reduction (via Shift-Invariance)

The proof shows that the advantage estimator is unchanged when a constant is added to the Q-function. This shift-invariance centers advantage values and reduces gradient-estimator variance.

  • The advantage estimator ˆA(i) remains unchanged under any constant shift C to the Q-function.The proof defines Q′(s, a) = Q(s, a) + C and shows that the shifted estimator equals the original estimator.
  • Centering the advantage values reduces the variance of the gradient estimator g_i.The passage characterizes this centering property as producing a dramatic variance reduction.
  • The proof obtains the shifted estimator by recomputing the baseline from the shifted Q-values and substituting Q′ and b′ into ˆA′(i).These substitutions establish algebraically that the constant terms cancel.
  • The resulting estimator measures each action's relative quality against the average quality of its peers.This interpretation follows from the estimator's centering construction after the shift cancels.
Loading 2604.07277v2…