DOM-Q-NET: Grounded RL on Structured Language

Sheng Jia, Jamie Kiros, Jimmy Ba

TL;DR

DOM-Q-NET is a novel reinforcement learning (RL) architecture designed to navigate the web by treating HTML as a structured graph rather than a flat sequence of pixels or text. By factorizing the action space and using Graph Neural Networks (GNNs) to capture the structural context of web elements, the model matches or outperforms state-of-the-art methods on the MiniWoB benchmark. Notably, it achieves this autonomous exploration without requiring any expert demonstrations.

What Problem Does This Paper Address?

Navigating the web is a deceptively simple task for humans but a nightmare for standard RL agents. The challenges are three-fold:

  1. Massive, Dynamic Action Spaces: Unlike a game controller with fixed buttons, a webpage might have dozens or hundreds of interactive elements (buttons, links, text boxes) that change with every click.
  2. Structural Complexity: A webpage isn't just a flat list of items; it’s a hierarchical tree known as the Document Object Model (DOM). The meaning of a "Submit" button depends entirely on the text fields surrounding it.
  3. Sparse Rewards: Most web tasks only provide a reward at the very end of a sequence (e.g., a +1 for successfully booking a flight). Without step-by-step guidance, an agent can wander aimlessly through millions of possible action combinations.

Previous approaches relied heavily on imitation learning (mimicking human experts) or hand-crafted rules to constrain the action space. DOM-Q-NET aims to solve these tasks through pure, autonomous exploration.

Methods

The authors introduce two primary innovations to make web RL tractable:

DOM-Q-NET Architecture

1. Factorized Q-Functions

Instead of trying to calculate a single Q-value for every possible combination of "where to click" and "what to type," the authors split the problem. They define the optimal Q-value as the sum of three independent components:

  • DOM selection ($a_{dom}$): Which element am I interacting with?
  • Word selection ($a_{token}$): If I'm typing, which word from the goal instruction should I use?
  • Mode ($a_{mode}$): Am I clicking or typing?

This factorization reduces the computational complexity from quadratic (DOMs $\times$ Words) to linear (DOMs + Words), making it much easier for the agent to learn.

2. Structural Embeddings via GNNs

To understand the "context" of a DOM element, the model uses a Graph Neural Network. It represents the webpage as a graph where nodes are DOM elements, generating three levels of representation:

  • Local: Features of the element itself (tag type, text, etc.).
  • Neighbor: Information propagated from nearby elements in the HTML tree using message passing.
  • Global: A high-level summary of the entire page, often refined using Goal-Attention. This focuses the agent's "sight" on parts of the page relevant to the current instruction (e.g., looking for a calendar when the goal is to "choose a date").

Datasets

The model was evaluated on MiniWoB (Mini World of Bits), a standard benchmark consisting of various web-based tasks like clicking checkboxes, navigating menus, and filling out forms. The authors focused on tasks requiring DOM interaction and string typing, ranging from "Easy" (click-button) to "Hard" (search-engine, social-media).

Key Insights and Ideas

  • Context is King: Ablation studies showed that the "Neighbor" module is critical. Without it, an agent cannot distinguish between two identical-looking checkboxes; it needs to "read" the labels next to them via the GNN to know which is which.
  • The Power of Multi-Tasking: One of the most striking findings was that training one agent on nine different tasks simultaneously was 2x more sample-efficient than training nine separate agents. The agent learned general "web behaviors" (like how to use a scrollbar or a text box) that transferred across different environments.
  • Beyond Demonstrations: By using a structured approach to the action space, the model solved the "choose-date" task—a long-horizon problem that previous state-of-the-art models failed to solve even with human demonstrations.

Key Results

Success Rates on MiniWoB Tasks
  • Success Rates: DOM-Q-NET reached a 100% success rate on most MiniWoB tasks. Even on the complex "social-media" task, it achieved 86% success without any expert help.
  • Efficiency: In multi-task settings, the agent solved the suite of tasks in roughly 63,000 frames, compared to 127,000 frames required by single-task agents.
  • Generalization: The model successfully detected synonyms in goal instructions (e.g., matching a "Search" button to a "Find" instruction) thanks to its use of cosine distance in the text embedding space.

Limitations and Future Work

While DOM-Q-NET is a leap forward, some hurdles remain:

  • Exploration in "Blind" Environments: Tasks like email-inbox remain difficult because the agent doesn't have a simple way to generalize behaviors when the environment doesn't provide clear, incremental feedback.
  • Computational Cost: Evaluating a Q-value for every single DOM element on a massive, modern webpage (like a real-world social media feed) could become computationally expensive.
  • Real-World Scaling: The authors suggest moving toward real-world search engines and question-answering tasks, where the agent must navigate live web results to find information.

Summary updated

Abstract

Building agents to interact with the web would allow for significant improvements in knowledge understanding and representation learning. However, web navigation tasks are difficult for current deep reinforcement learning (RL) models due to the large discrete action space and the varying number of actions between the states. In this work, we introduce DOM-Q-NET, a novel architecture for RL-based web navigation to address both of these problems. It parametrizes Q functions with separate networks for different action categories: clicking a DOM element and typing a string input. Our model utilizes a graph neural network to represent the tree-structured HTML of a standard web page. We demonstrate the capabilities of our model on the MiniWoB environment where we can match or outperform existing work without the use of expert demonstrations. Furthermore, we show 2x improvements in sample efficiency when training in the multi-task setting, allowing our model to transfer learned behaviours across tasks.
BibTeX
@inproceedings{jia2019dom,
  author = {Sheng Jia and Jamie Kiros and Jimmy Ba},
  title = {{DOM-Q-NET: Grounded RL on Structured Language}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=pp5Q8pkaNL},
}
Figure