Technical Summary: WebCQ

Problem Statement

Modern web GUI software has grown increasingly complex, characterized by vast state spaces and numerous interactive elements. While Multi-Agent Reinforcement Learning (MARL) has shown promise for GUI testing, existing approaches (e.g., MARG, Fastbot) rely on tabular reinforcement learning algorithms (such as Q-learning). These methods face two critical limitations in large-scale web environments:

1. Scalability Issues: Tabular methods suffer from the "state explosion" problem, where Q-tables grow unbounded as the number of states increases, making them impractical for complex commercial websites.
2. Inefficient Coordination: Existing multi-agent frameworks often incur severe communication overhead between parallel agents. Furthermore, their action definitions are typically "locator-centric," failing to capture the semantic meaning of actions (e.g., the intent to submit a form), which limits effective validity analysis and exploration of dynamic interactions.

Methodology: WebCQ

To address these limitations, the authors propose WebCQ, a novel cooperative Multi-Agent Deep Reinforcement Learning (MARL) framework designed for scalable web GUI testing. WebCQ formulates the testing task as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) and adopts the Centralized Training and Decentralized Execution (CTDE) paradigm.

Core Components

1. QTRAN for Coordination:
   Unlike previous MARL approaches that rely on simple data exchange, WebCQ employs QTRAN, an advanced algorithm designed to handle complex agent interactions without restrictive additivity assumptions. QTRAN decomposes a global Q-function ($Q_{jt}$) into individual agent Q-functions ($Q_i$) using a state-value function ($V_{jt}$) to account for discrepancies. This allows agents to learn coordinated policies effectively in high-dimensional spaces.

2. Lightweight Synchronization Mechanism:
   Since QTRAN assumes synchronized agents but web testing is inherently asynchronous (agents run independent browser instances), WebCQ introduces a lightweight synchronization mechanism. Agents explore independently without step-level blocking. Training is triggered only when all agents have collected at least one new transition, ensuring sufficient experience for joint training while avoiding unnecessary waiting times.

3. Semantic and Exploration-Aware Representations:

   • State Vector: Instead of relying on computationally expensive HTML tag sequences or dynamic URLs, WebCQ encodes the DOM structure by computing the average depth of specific HTML tags. This creates a fixed-dimensional vector suitable for neural networks.
   • Action Vector: To capture action semantics, each UI event is transformed into a vector comprising three features:
     • Text Similarity: Cosine similarity between button text and positive keywords (e.g., "submit," "confirm") using a pre-trained GloVe model.
     • Execution Frequency: The count of how often the action has been executed to discourage redundancy.
     • Exploration Potential: A vector representing the diversity of actions available in the resulting child state.
   • Dynamic Action Space Handling: Since the set of available UI events changes per webpage, WebCQ concatenates the state vector with each candidate action vector and feeds this pair into the policy network (DQN) to estimate Q-values, rather than predicting over a fixed action set.

4. Hybrid Reward Function:
   The global reward is a product of three components designed to encourage diverse, long-term exploration:

   • Page Similarity ($R_{sim}$): Rewards visiting pages dissimilar to previously visited ones.
   • Execution Frequency ($R_{exec}$): Rewards new actions and penalizes repeated executions.
   • Temporal Compensation ($R_{time}$): A time-based term that increases as the testing session progresses to counteract reward sparsity in long-term exploration.

Key Contributions

1. Novel Formulation: The authors are the first to formulate multi-agent web GUI testing as a Dec-POMDP problem and introduce QTRAN for effective agent cooperation in this domain.
2. Scalable Framework: WebCQ integrates DRL with a lightweight synchronization mechanism, enabling asynchronous exploration while maintaining the coordination benefits of centralized training.
3. Enhanced Representations: The approach moves beyond locator-centric definitions to include semantic and exploration-relevant features in action vectors, enabling more effective decision-making in dynamic action spaces.
4. Open Source: The source code and experimental data are publicly released to facilitate future research.

Experimental Results

The authors evaluated WebCQ on eight large-scale commercial websites (e.g., GitHub, ESPN, Gap) and compared it against state-of-the-art baselines: WebExplor (extended to multi-agent) and MARG (the current MARL state-of-the-art), as well as two ablation variants (WebCQ without communication and WebCQ without QTRAN).

• Exploration Efficiency: Under the same time budget and agent count (5 agents), WebCQ explored 33.3% more states and executed 42.2% more unique actions than MARG.
• Failure Detection: WebCQ triggered more failures on six of the eight tested websites compared to MARG.
• Ablation Insights:
  • Removing communication reduced performance by 27.1% in explored states.
  • Replacing QTRAN with a simpler experience-sharing scheme (from MARG) reduced performance by 21.3%, indicating that standard communication rules are insufficient for DRL settings.
• Scalability:
  • Long-term Performance: In 20-hour experiments, WebCQ maintained higher action throughput than MARG, which suffered from rapid performance degradation due to coordination overhead as Q-tables expanded.
  • Agent Scaling: As the number of agents increased (3 to 12), WebCQ's performance steadily improved. In contrast, MARG's performance plateaued or declined with more agents, highlighting the scalability limits of tabular coordination.

Significance and Claims

The paper claims that WebCQ overcomes the key limitations of existing MARL-based approaches by replacing tabular algorithms with deep reinforcement learning and advanced coordination mechanisms. The authors assert that WebCQ provides a scalable and effective solution for modern web GUI testing, capable of handling the vast state spaces and dynamic interactions of large-scale commercial web applications where previous methods struggle. The results suggest that the combination of QTRAN, semantic action representation, and asynchronous synchronization is critical for achieving high exploration efficiency and failure detection in complex web environments.