Training Needs Trustworthy Worlds: Verified Synthetic Web Environments for Agent Learning

# Training Needs Trustworthy Worlds: Verified Synthetic Web Environments for Agent Learning
Source: [https://arxiv.org/html/2608.21898](https://arxiv.org/html/2608.21898)
###### Abstract

Web agents promise to automate complex digital workflows, but their training remains limited by synthetic environments that look plausible while hiding broken links, inconsistent states, or infeasible tasks\. We address the gap between scalable environment generation and trustworthy agent learning by constructing synthetic web environments that are executable, auditable, and grounded in backend state\. Our framework represents each generated website as a structured scaffold of pages, navigation links, database records, state\-change markers, and task constraints, then verifies and repairs structural, semantic, consistency, and feasibility defects before policy training\. During interaction, ordinary UI transitions are executed deterministically, while persistent backend updates are invoked only through validated state\-change markers, enabling dense rewards compiled from verified task\-progress predicates\. Across 500 synthetic environments spanning six domains, our method reduces task\-blocking defects and improves feasible\-task rate from 48\.6% to 94\.8%, while producing stronger PPO policies and improving transfer to WebArena, WebShop, and MiniWoB\+\+ without LLM calls at evaluation time\. These results show that verified synthetic environments can serve as a scalable and reliable training substrate for compact web agents, shifting synthetic web\-agent learning from surface\-level plausibility toward executable, state\-grounded supervision\.

††footnotetext:1University of Pennsylvania\.††footnotetext:2Shenzhen Campus of Sun Yat\-sen University\.††footnotetext:3Pace University\.## 1Introduction

Autonomous web agents aim to complete user\-specified tasks by perceiving graphical interfaces, selecting grounded actions, and manipulating persistent web states\. This capability is increasingly important for automating digital workflows such as shopping, booking, form submission, customer\-service operations, and enterprise knowledge work\. Despite rapid progress in large language and multimodal agents, web interaction remains challenging because successful execution requires long\-horizon planning, precise grounding in dynamic interfaces, and reliable reasoning over hidden backend states rather than only visible page content\.

Recent benchmarks and systems have substantially advanced web\-agent research\. Early platforms such as World of Bits and MiniWoB\+\+ established reproducible browser\-control tasks for reinforcement learning\([Shi et al\. 2017](https://arxiv.org/html/2608.21898#bib.bib15);[Liu et al\. 2018](https://arxiv.org/html/2608.21898#bib.bib9)\), while WebShop, Mind2Web, WebArena, VisualWebArena, WorkArena, and BrowserGym introduced more realistic tasks, websites, demonstrations, and evaluation protocols\([Yao et al\. 2023a](https://arxiv.org/html/2608.21898#bib.bib17);[Deng et al\. 2023](https://arxiv.org/html/2608.21898#bib.bib5);[Zhou et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib20);[Koh et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib8);[Drouin et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib6);[Chezelles et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib4)\)\. In parallel, LLM\-based agents such as ReAct, WebVoyager, AgentOccam, Agent Q, and WebRL have improved reasoning, exploration, and learning from interaction traces\([Yao et al\. 2023b](https://arxiv.org/html/2608.21898#bib.bib18);[He et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib7);[Yang et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib16);[Putta et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib12);[Qi et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib13)\)\. These works demonstrate that web agents can benefit from richer environments and larger\-scale interaction data\. However, they also expose a central bottleneck: high\-quality web\-agent training requires many executable, stateful, and verifiable environments, yet realistic web environments are expensive to build, difficult to reset, and often limited in task coverage\.

A natural direction is to use LLMs to synthesize environments, tasks, or agent experiences\. Prior work has shown that generated environments and synthetic trajectories can support agent learning in embodied and digital settings\([Zala et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib19);[Patel et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib11)\)\. Nevertheless, directly generated web environments are prone to a deeper reliability problem: locally plausible pages may still contain globally invalid workflows\. For example, links may be unreachable, database values may contradict rendered content, required controls may be missing, and task success conditions may not correspond to any executable state transition\. Such defects are especially harmful for reinforcement learning, because the agent may receive supervision from environments whose apparent failures are caused by scaffold errors rather than policy mistakes\. Existing approaches do not fully resolve this high\-level mismatch between*plausible generation*and*executable, state\-grounded interaction*\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/teaser.png)Figure 1:Prior methods train on superficially plausible but inconsistent web interactions, while our approach verifies and repairs the environment to provide executable, state\-grounded supervision for more effective agent policies\.This paper asks:*How can we construct synthetic web environments that are not only diverse and realistic, but also executable, auditable, and useful for training compact web agents?*We address this question by shifting the object of generation from isolated pages or trajectories to verified environment scaffolds\. As shown in Fig\.[1](https://arxiv.org/html/2608.21898#S1.F1), our approach first represents a synthetic website as a structured environment with pages, navigation, data records, state\-changing events, and task constraints; then it verifies and repairs the scaffold before policy learning; finally, it trains agents using rewards derived from backend\-grounded task progress rather than from surface\-level textual judgments\. This design aims to make synthetic web interaction a reliable training substrate, where failures are attributable to the policy instead of hidden environment invalidity\.

Our contributions are summarized as follows:

- •We identify a core limitation of trajectory\- or page\-level generation: web\-agent training depends on whether tasks are executable under consistent backend dynamics, not merely whether the generated interface appears plausible\.
- •We propose a framework that canonicalizes, verifies, and repairs generated web scaffolds, producing environments with explicit navigation structure, database bindings, state\-change events, and task constraints\.
- •By deriving dense rewards from verified backend\-state progress and executing ordinary interactions without LLM calls at evaluation time, our framework enables efficient reinforcement learning in synthetic web environments while preserving task\-level auditability\.

## 2Related Work

##### Web interaction benchmarks and web agents\.

Early work framed web interaction as language\-conditioned control over semi\-structured interfaces, from instruction following to reproducible environments such as World of Bits and MiniWoB\+\+\([Branavan et al\. 2009](https://arxiv.org/html/2608.21898#bib.bib1);[Shi et al\. 2017](https://arxiv.org/html/2608.21898#bib.bib15);[Liu et al\. 2018](https://arxiv.org/html/2608.21898#bib.bib9)\)\. Later benchmarks expanded realism and task diversity, including WebShop, Mind2Web, WebArena, VisualWebArena, WorkArena, and BrowserGym\([Yao et al\. 2023a](https://arxiv.org/html/2608.21898#bib.bib17);[Deng et al\. 2023](https://arxiv.org/html/2608.21898#bib.bib5);[Zhou et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib20);[Koh et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib8);[Drouin et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib6);[Chezelles et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib4)\)\. Recent agents such as WebVoyager and AgentOccam further show that improved observation and action design can benefit web navigation\([He et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib7);[Yang et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib16)\)\. However, these efforts mainly provide fixed benchmarks or agent\-side improvements, rather than methods for automatically constructing large\-scale, executable, stateful, and verifiably valid training environments\. Our work instead generates checked web environments whose pages, data bindings, events, and task constraints are explicitly represented and verified before policy learning\.

##### Synthetic environments and agent experience generation\.

A complementary line of work uses LLMs to reduce the cost of interactive learning by generating environments, tasks, or trajectories\. EnvGen uses LLMs to adaptively create training environments for embodied RL agents\([Zala et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib19)\), while DreamGym synthesizes agent experiences through a learned reasoning\-based environment model\([Chen et al\. 2025](https://arxiv.org/html/2608.21898#bib.bib3)\)\. For web agents, self\-improvement methods synthesize or refine interaction data from agent rollouts, including model\-generated web trajectories\([Patel et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib11)\), search\- and preference\-based refinement in Agent Q\([Putta et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib12)\), and self\-evolving curriculum RL in WebRL\([Qi et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib13)\)\. These methods show the promise of using generated interaction data, but the generated supervision is often trajectory\-centric and may inherit invalid dynamics, inconsistent states, or unverifiable task completions\. Our method instead treats the environment itself as the object of generation: raw scaffolds are canonicalized, verified, repaired, and instrumented with constrained state\-change markers, so that rollouts are produced by an executable simulator rather than by unconstrained trajectory synthesis\.

##### Reward, verification, and policy learning for digital agents\.

Learning web agents is difficult because long\-horizon tasks often provide sparse terminal feedback\. Prior RL methods improved exploration with demonstrations and workflow constraints\([Liu et al\. 2018](https://arxiv.org/html/2608.21898#bib.bib9)\), while WebShop used programmatic matching functions to provide task\-specific rewards\([Yao et al\. 2023a](https://arxiv.org/html/2608.21898#bib.bib17)\)\. More recent work studies automatic evaluators and process reward models for web or device\-control agents, such as autonomous evaluator\-guided refinement and Web\-Shepherd’s step\-level reward modeling\([Pan et al\. 2024](https://arxiv.org/html/2608.21898#bib.bib10);[Chae et al\. 2025](https://arxiv.org/html/2608.21898#bib.bib2)\)\. These approaches improve feedback quality but often rely on learned or LLM/VLM\-based evaluators, which can be costly, miscalibrated, or disconnected from the true backend state\. Our work takes a more environment\-grounded route: task constraints are compiled into backend\-state predicates that yield dense progress rewards, while invalid marker\-triggered updates are rejected by construction\. This enables standard PPO training\([Schulman et al\. 2017](https://arxiv.org/html/2608.21898#bib.bib14)\)of compact policies in checked synthetic environments, without requiring LLM calls during policy evaluation\.

## 3Preliminaries

### 3\.1Web Interaction and Environment Scaffold

We model web interaction as a goal\-conditioned sequential decision process\. A taskt∈Tt\\in Tprovides an instructionxtx\_\{t\}and a programmatic completion constraintCtC\_\{t\}evaluated on the environment state\. Starting froms0∼ρts\_\{0\}\\sim\\rho\_\{t\}, the agent observes a rendered interface, selects a DOM\-grounded action, and triggers a state transition:

ok=Render⁡\(sk\),ak∈A⁡\(ok\),sk\+1=𝒯⁡\(sk,ak\)\.o\_\{k\}=\\mathrm\{Render\}\(s\_\{k\}\),\\qquad a\_\{k\}\\in A\(o\_\{k\}\),\\qquad s\_\{k\+1\}=\\mathcal\{T\}\(s\_\{k\},a\_\{k\}\)\.\(1\)The terminal success signal is given byCt​\(s\)∈\{0,1\}C\_\{t\}\(s\)\\in\\\{0,1\\\}\. This setting is difficult because the agent only observes the rendered interface rather than the full backend state, and successful completion often requires long\-horizon navigation, form filling, and stateful updates\.

We represent a generated web environment asE=\(P,L,D,T\),E=\(P,L,D,T\),wherePPis the page set,L⊆P×PL\\subseteq P\\times Pis the navigation graph,DDis the database schema with initialized records, andTTis the task set with verifiable constraints\. Each pagepi∈Pp\_\{i\}\\in Pcontains a DOM treeτi\\tau\_\{i\}and interactive elementsIiI\_\{i\}, whose action types and argument schemas ground high\-level actions in executable UI operations\.

This representation separates two layers\. The*static scaffold*defines pages, links, database bindings, interactive elements, and task constraints before execution\. The*dynamic layer*specifies how actions update persistent records and session variables during interaction\. This separation is necessary because one\-shot LLM generation often produces interfaces that are locally plausible but globally invalid\. We consider four scaffold defects: structural defects\(ΔS\)\(\\Delta\_\{S\}\), such as broken links or unreachable pages; semantic defects\(ΔC\)\(\\Delta\_\{C\}\), such as invalid field values or placeholder content; consistency defects\(ΔX\)\(\\Delta\_\{X\}\), such as contradictory entity attributes across pages; and feasibility defects\(ΔT\)\(\\Delta\_\{T\}\), where missing controls or workflow steps make a task unsatisfiable\.

### 3\.2Motivating Diagnostics

We run a lightweight diagnostic study on 500 raw LLM\-generated environments from six domains, covering 6,842 generated tasks, and analyze 1,800 successful trajectories from scripted and human\-assisted rollouts\. For defect categorycc, letNc​\(E\)N\_\{c\}\(E\)be its per\-environment count\. We measure its task\-blocking effect as

Bc\(E\)=1\|T⁡\(E\)\|∑t∈T⁡\(E\)\[Blockc\(E,t\)=1\],B\_\{c\}\(E\)=\\frac\{1\}\{\|T\(E\)\|\}\\sum\_\{t\\in T\(E\)\}\\mathbf\{1\}\\\!\\left\[\\operatorname\{Block\}\_\{c\}\(E,t\)=1\\right\],\(2\)whereBlockc⁡\(E,t\)\\operatorname\{Block\}\_\{c\}\(E,t\)indicates that taskttis blocked by categoryccunder bounded trace analysis\. For a trajectoryτ=\(s0,a0,…,sH\)\\tau=\(s\_\{0\},a\_\{0\},\\ldots,s\_\{H\}\), we measure marker\-trigger sparsity by

M\(τ\)=1H∑k=0H−1\[μ\(pk,ak\)≠∅\],U\(τ\)=∑k=0H−1\[μ\(pk,ak\)≠∅\],M\(\\tau\)=\\frac\{1\}\{H\}\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\],\\qquad U\(\\tau\)=\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\],\(3\)whereμ⁡\(pk,ak\)\\mu\(p\_\{k\},a\_\{k\}\)returns the state\-change marker triggered by actionaka\_\{k\}\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/prelim_diagnostics.png)Figure 2:Motivating diagnostics\.\(a\)Raw LLM\-generated environments contain frequent defects, with semantic and structural defects dominating the average total of 12\.4 defects per environment\.\(b\)Defect frequency and harmfulness differ: feasibility defects are less frequent but most likely to block task completion\.\(c\)Marker\-triggered updates are sparse across domains, indicating that most interactions are deterministic UI transitions\.\(d\)The number of state\-write calls remains small even for longer episodes\.Figure[2](https://arxiv.org/html/2608.21898#S3.F2)supports two design choices\. First, raw scaffolds require verification because defect counts alone understate task\-level harm: feasibility and structural defects are especially likely to block executable workflows\. Second, runtime state updates are sparse: most steps are navigation, inspection, scrolling, or local input editing, while persistent backend writes occur only at a few marker\-triggered events\. These observations motivate verified static scaffolds and event\-driven dynamic updates\. Additional details on bounded trace analysis, defect attribution, marker statistics, and plotting protocol are provided in Appendix[A\.1](https://arxiv.org/html/2608.21898#A1.SS1)\.

### 3\.3Dynamic State and Event\-Driven Updates

The dynamic layer maintains the database instance and session state used for rendering and access control\. Ordinary actions, such as navigation, scrolling, menu expansion, and local text entry, are executed deterministically\. Only marked events, such asadd\-to\-cart,submit\-order, orupdate\-profile, invoke a constrained state writer to propose a backend delta\. The delta is committed only if it satisfies marker preconditions, schema constraints, and environment invariants\. Thus, the simulator avoids calling a generative model at every step while keeping persistent state changes explicit, auditable, and aligned with the verified scaffold\.

## 4Method

Given a domain\-level website description, our method constructs an executable synthetic web environment for training compact web agents\. The environment is first represented as a structured scaffold with pages, links, database records, state\-change markers, and task constraints\. We then verify and repair the scaffold before training, so that generated tasks correspond to reachable workflows instead of artifacts of one\-shot generation\. During interaction, the simulator executes ordinary UI transitions deterministically and invokes constrained state writes only when a verified marker is triggered\. Task constraints are compiled into backend\-grounded progress predicates, which provide dense rewards for PPO training while keeping the learned policy independent of LLM calls at evaluation time\. Fig\.[3](https://arxiv.org/html/2608.21898#S4.F3)shows the pipeline of our method\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/pipeline.png)Figure 3:Pipeline of verified synthetic web\-environment construction and policy training\.The offline stage generates a scaffold from a site specification, canonicalizes it into pages, data, tasks, and markers, and verifies/repairs navigation, data consistency, and workflow feasibility\. The online stage trains a compact policy in the checked environment, where deterministic transitions and marker\-validated state updates provide state\-grounded rewards for PPO\.### 4\.1Environment Representation and Marker Instrumentation

A generated web environment must support three operations throughout training: rendering observations, executing actions, and checking task completion against ground\-truth state\. We therefore represent the environment as a structured object instead of a collection of independent HTML pages\. This representation exposes the causal chain from backend records to rendered DOM nodes, from UI events to state updates, and from state changes to task progress\.

We represent an environment as

ℰ=\(𝒫,ℒ,𝒟,ℳ,𝒬\),\\mathcal\{E\}=\(\\mathcal\{P\},\\mathcal\{L\},\\mathcal\{D\},\\mathcal\{M\},\\mathcal\{Q\}\),\(4\)where𝒫\\mathcal\{P\}is the page set,ℒ⊆𝒫×𝒫\\mathcal\{L\}\\subseteq\\mathcal\{P\}\\times\\mathcal\{P\}is the navigation graph,𝒟\\mathcal\{D\}is the database schema with initialized records,ℳ\\mathcal\{M\}is the set of state\-change markers, and𝒬\\mathcal\{Q\}is the task set\. Each taskt∈𝒬t\\in\\mathcal\{Q\}contains an instructionxtx\_\{t\}, an initial\-state distributionρt\\rho\_\{t\}, and a completion constraintCt:𝒮→\{0,1\}C\_\{t\}:\\mathcal\{S\}\\rightarrow\\\{0,1\\\}evaluated on simulator state\.

At stepkk, the simulator state, rendered observation, and executable action satisfy

sk=\(pk,bk,σk,hk\),ok=Render⁡\(pk,bk,σk\),ak∈𝒜⁡\(ok\)\.s\_\{k\}=\(p\_\{k\},b\_\{k\},\\sigma\_\{k\},h\_\{k\}\),\\qquad o\_\{k\}=\\mathrm\{Render\}\(p\_\{k\},b\_\{k\},\\sigma\_\{k\}\),\\qquad a\_\{k\}\\in\\mathcal\{A\}\(o\_\{k\}\)\.\(5\)Here,pkp\_\{k\}is the current page,bkb\_\{k\}is the database instance,σk\\sigma\_\{k\}is the session state,hkh\_\{k\}is the action history, and𝒜⁡\(ok\)\\mathcal\{A\}\(o\_\{k\}\)is the DOM\-grounded candidate action set extracted from the current observation\. The rendering function fills page templates using database bindings and session variables, making the observation a deterministic view of the underlying state\.

State\-changing operations are specified by markers:

m=\(em,prem,Rm,Wm,Ωm\)\.m=\(e\_\{m\},\\mathrm\{pre\}\_\{m\},R\_\{m\},W\_\{m\},\\Omega\_\{m\}\)\.\(6\)In Eq\. \([6](https://arxiv.org/html/2608.21898#S4.E6)\),eme\_\{m\}is the triggering UI element,prem\\mathrm\{pre\}\_\{m\}is a precondition over the current state and action,RmR\_\{m\}andWmW\_\{m\}are the permitted read and write fields, andΩm\\Omega\_\{m\}is the operation signature\. A marker therefore constrains which backend fields are accessed and modified when a UI event commits a persistent update\. Additional parsing rules and marker schemas are given in Appendix[A\.2](https://arxiv.org/html/2608.21898#A1.SS2)\.

### 4\.2Verification\-Guided Scaffold Construction

One\-shot LLM generation often produces locally plausible pages with globally invalid workflows\. Broken links, inconsistent entity attributes, invalid database bindings, and infeasible tasks create misleading training signals\. The verification stage detects these failures before policy learning; the repair stage modifies only the scaffold components implicated by accepted defect reports\.

Given a site descriptionqq, the generator produces raw scaffold artifactsℰ~\\widetilde\{\\mathcal\{E\}\}, including page templates, navigation links, database records, task instructions, and completion constraints\. A canonical parser convertsℰ~\\widetilde\{\\mathcal\{E\}\}intoℰ\(0\)\\mathcal\{E\}^\{\(0\)\}, extracts DOM elements and database bindings, and builds the initial marker set\. Deterministic checks handle reachability, link integrity, schema validity, DOM–database binding, and marker read–write consistency\. These checks are specified in Appendix[A\.2](https://arxiv.org/html/2608.21898#A1.SS2)\.

At repair iterationrr, symbolic checks and semantic verifiers produce a defect set

Δ\(r\)=Δsym\(r\)∪Δstr\(r\)∪Δsem\(r\)∪Δcons\(r\)∪Δfeas\(r\)\.\\Delta^\{\(r\)\}=\\Delta\_\{\\mathrm\{sym\}\}^\{\(r\)\}\\cup\\Delta\_\{\\mathrm\{str\}\}^\{\(r\)\}\\cup\\Delta\_\{\\mathrm\{sem\}\}^\{\(r\)\}\\cup\\Delta\_\{\\mathrm\{cons\}\}^\{\(r\)\}\\cup\\Delta\_\{\\mathrm\{feas\}\}^\{\(r\)\}\.\(7\)The five terms denote deterministic symbolic defects, structural defects, semantic content defects, cross\-page consistency defects, and task feasibility defects\. Each reported defectddis associated with a location, affected object, severity score, evidence, and verifier confidence\. Reports with the same canonical key are merged\. The aggregated confidence is

conf⁡\(d\)=∑jωjcj\(d\)𝟏\[d∈Δj\(r\)\]∑jωj𝟏\[d∈Δj\(r\)\],\\mathrm\{conf\}\(d\)=\\frac\{\\sum\_\{j\}\\omega\_\{j\}c\_\{j\}\(d\)\\mathbf\{1\}\[d\\in\\Delta\_\{j\}^\{\(r\)\}\]\}\{\\sum\_\{j\}\\omega\_\{j\}\\mathbf\{1\}\[d\\in\\Delta\_\{j\}^\{\(r\)\}\]\},\(8\)wherejjindexes verifiers,cj​\(d\)c\_\{j\}\(d\)is verifierjj’s confidence for defectdd,ωj\\omega\_\{j\}is the reliability weight of verifierjj, and𝟏​\[⋅\]\\mathbf\{1\}\[\\cdot\]is the indicator function\. Defect\-triggered verifier coordination is used to re\-check only defect categories that affect one another; the coordination protocol is described in Appendix[A\.3](https://arxiv.org/html/2608.21898#A1.SS3)\.

Accepted defects are repaired in dependency order\. We rank each defect by

score⁡\(d\)=λ1​sev​\(d\)\+λ2​log⁡\(1\+dep⁡\(d\)\)\+λ3​scope​\(d\)−λ4​cost​\(d\),\\mathrm\{score\}\(d\)=\\lambda\_\{1\}\\mathrm\{sev\}\(d\)\+\\lambda\_\{2\}\\log\(1\+\\mathrm\{dep\}\(d\)\)\+\\lambda\_\{3\}\\mathrm\{scope\}\(d\)\-\\lambda\_\{4\}\\mathrm\{cost\}\(d\),\(9\)wheresev⁡\(d\)\\mathrm\{sev\}\(d\)is severity,dep⁡\(d\)\\mathrm\{dep\}\(d\)is the number of downstream defects that depend ondd,scope⁡\(d\)\\mathrm\{scope\}\(d\)counts affected pages and tasks,cost⁡\(d\)\\mathrm\{cost\}\(d\)estimates repair complexity, andλ1,…,λ4≥0\\lambda\_\{1\},\\ldots,\\lambda\_\{4\}\\geq 0are fixed scheduling weights\. The repair operator updates the environment asℰ\(r\+1\)=ℛd⋆​\(ℰ\(r\)\)\\mathcal\{E\}^\{\(r\+1\)\}=\\mathcal\{R\}\_\{d^\{\\star\}\}\(\\mathcal\{E\}^\{\(r\)\}\), whered⋆d^\{\\star\}is the highest\-scoring defect whose dependencies have been satisfied\. Structural repair modifies links and required elements; semantic repair rewrites content while preserving database bindings; consistency repair propagates canonical database values; feasibility repair inserts missing workflow steps and marker signatures\. The loop terminates when no accepted critical defect remains and each task has a bounded executable trace satisfying its completion constraint\. Repair operators and termination checks are given in Appendix[A\.4](https://arxiv.org/html/2608.21898#A1.SS4)\.

### 4\.3Event\-Driven Simulation

A training simulator must be efficient and inspectable\. Most web interactions, such as navigation, scrolling, local text entry, and client\-side validation, follow deterministic rules\. Persistent changes, such as form submission, entity creation, profile update, and permission change, require backend writes\. We therefore execute deterministic transitions by default and restrict generative state updates to verified marker\-triggered operations\.

Letμ⁡\(pk,ak\)\\mu\(p\_\{k\},a\_\{k\}\)return the marker triggered by actionaka\_\{k\}on pagepkp\_\{k\}, and let∅\\varnothingdenote no marker\. The simulator transition is

\(sk\+1,ϵk\)=\{\(Fdet​\(sk,ak\),0\),μ⁡\(pk,ak\)=∅,\(Fmark\(sk,ak,δk\),𝟏\[δk=⊥\]\),mk=μ⁡\(pk,ak\)≠∅\.\(s\_\{k\+1\},\\epsilon\_\{k\}\)=\\begin\{cases\}\(F\_\{\\mathrm\{det\}\}\(s\_\{k\},a\_\{k\}\),0\),&\\mu\(p\_\{k\},a\_\{k\}\)=\\varnothing,\\\\ \(F\_\{\\mathrm\{mark\}\}\(s\_\{k\},a\_\{k\},\\delta\_\{k\}\),\\mathbf\{1\}\[\\delta\_\{k\}=\\bot\]\),&m\_\{k\}=\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\.\\end\{cases\}\(10\)Here,FdetF\_\{\\mathrm\{det\}\}applies deterministic UI transitions,FmarkF\_\{\\mathrm\{mark\}\}applies a validated backend update,δk\\delta\_\{k\}is the state delta, andϵk\\epsilon\_\{k\}indicates a rejected transition\.

For a marker\-triggered operation, a constrained state writer proposes a candidate delta using the current page, relevant database fragments, session state, action arguments, and marker signature\. The candidate is accepted only after validation:

δk=Validatemk​\(δ^k,sk,ak\)∈𝒰mk​\(sk,ak\)∪\{⊥\}\.\\delta\_\{k\}=\\mathrm\{Validate\}\_\{m\_\{k\}\}\(\\hat\{\\delta\}\_\{k\};s\_\{k\},a\_\{k\}\)\\in\\mathcal\{U\}\_\{m\_\{k\}\}\(s\_\{k\},a\_\{k\}\)\\cup\\\{\\bot\\\}\.\(11\)The feasible update set𝒰mk​\(sk,ak\)\\mathcal\{U\}\_\{m\_\{k\}\}\(s\_\{k\},a\_\{k\}\)contains deltas satisfying the marker precondition, permitted read–write fields, database schema, and environment invariants\. If validation returns⊥\\bot, the simulator keeps the previous state and records a violation\. This design makes every accepted persistent update traceable to a marker, a write set, and a validated state delta\. The state writer interface and validation rules are detailed in Appendix[A\.5](https://arxiv.org/html/2608.21898#A1.SS5)\.

### 4\.4State\-Grounded Reward and Policy Learning

Terminal success alone gives sparse supervision for long\-horizon web tasks\. Since the checked environment exposes backend records and session variables, intermediate progress is computed from task constraints rather than from natural\-language self\-assessment\. The reward therefore measures verified state progress and penalizes rejected transitions\. For each tasktt, we compile its completion constraintCtC\_\{t\}into progress predicatesΦt=\{ϕt,1,…,ϕt,Mt\}\\Phi\_\{t\}=\\\{\\phi\_\{t,1\},\\ldots,\\phi\_\{t,M\_\{t\}\}\\\}, where eachϕt,i:𝒮→\{0,1\}\\phi\_\{t,i\}:\\mathcal\{S\}\\rightarrow\\\{0,1\\\}checks a necessary intermediate condition\. These conditions include visiting required pages, satisfying form constraints, creating target entities, updating correct attributes, and matching rendered views with backend state\. The predicates define a progress potential:

Ψt​\(s\)=1∑i=1Mtwi​∑i=1Mtwi​ϕt,i​\(s\),\\Psi\_\{t\}\(s\)=\\frac\{1\}\{\\sum\_\{i=1\}^\{M\_\{t\}\}w\_\{i\}\}\\sum\_\{i=1\}^\{M\_\{t\}\}w\_\{i\}\\phi\_\{t,i\}\(s\),\(12\)wherewi≥0w\_\{i\}\\geq 0is the importance weight of predicateϕt,i\\phi\_\{t,i\}\. The policy observesoko\_\{k\}andxtx\_\{t\}, whileCtC\_\{t\},Φt\\Phi\_\{t\}, and backend state are used only by the environment to compute rewards\.

The step reward is

rk=𝟏\[Ct\(sk\+1\)=1\]\+α\(Ψt\(sk\+1\)−Ψt\(sk\)\)−γϵk−η\.r\_\{k\}=\\mathbf\{1\}\[C\_\{t\}\(s\_\{k\+1\}\)=1\]\+\\alpha\\bigl\(\\Psi\_\{t\}\(s\_\{k\+1\}\)\-\\Psi\_\{t\}\(s\_\{k\}\)\\bigr\)\-\\gamma\\epsilon\_\{k\}\-\\eta\.\(13\)The first term gives terminal success reward, the second term gives net verified progress, the third term penalizes rejected state transitions, andη\\etais a step cost\. The constantsα,γ,η≥0\\alpha,\\gamma,\\eta\\geq 0are fixed\.

We train a compact policyπθ​\(ak∣ok,xt\)\\pi\_\{\\theta\}\(a\_\{k\}\\mid o\_\{k\},x\_\{t\}\)using standard clipped PPO over DOM\-grounded candidate actions\. During synthetic training rollouts, marker\-triggered simulator updates may use the constrained state writer in Eq\. \([11](https://arxiv.org/html/2608.21898#S4.E11)\); the learned policy itself performs action selection without LLM calls during evaluation\. More details are provided in Appendix[A\.6](https://arxiv.org/html/2608.21898#A1.SS6)\.

## 5Experiments

We design experiments to answer three questions\. First, does verification convert superficially plausible generated websites into executable training environments? Second, does training on verified environments improve compact policies beyond training on raw synthetic environments? Third, which components of the verification–repair–reward pipeline are responsible for the gains? We also discussed other questions regarding the mechanism of our method; see §[C](https://arxiv.org/html/2608.21898#A3)\.

### 5\.1Experimental Setup

##### Synthetic environment suite\.

We generate 500 synthetic web environments from domain\-level site specifications across six domains: e\-commerce, social media, banking, education, healthcare, and government\. Each environment contains 15–30 pages, a navigation graph, database records, state\-change markers, and a set of task instructions with programmatic completion constraints\. Unless otherwise stated, we split environments by site specification into 350 training environments, 75 validation environments, and 75 held\-out test environments, ensuring that held\-out environments do not share page templates or task constraints with training environments\.

##### Policy and training\.

We train a compact DOM\-grounded policy with fewer than 10M parameters using PPO\. At each step, the policy receives the task instruction and the rendered DOM observation, scores the current candidate action set, and executes one DOM\-grounded action\. The policy never observes backend states, completion predicates, or verifier outputs\. Unless otherwise stated, all policy results are averaged over three random seeds and reported with 95% confidence intervals\.

##### Environment\-construction baselines\.

We compare our verified construction pipeline with five baselines\.No Verificationdirectly uses raw LLM\-generated scaffolds\.Rule\-Basedapplies deterministic reachability, link, schema, and binding checks\.Single\-LLMuses one GPT\-4 verifier prompted to detect all defect categories\.Self\-Consistencysamples five independent verifier outputs and applies majority voting\.AutoGenadapts a general\-purpose multi\-agent verification framework to the same environment scaffold\. All methods start from the same scaffolds\.

##### Policy\-training baselines\.

To isolate the effect of environment quality and reward design, we train the same compact PPO policy under different synthetic training conditions: raw environments with terminal rewards, raw environments with dense rewards, rule\-checked environments with dense rewards, verified environments with terminal rewards, and our full verified environment with state\-grounded dense rewards\. For transfer evaluation, we also compare against GPT\-4 direct prompting and GPT\-4 with ReAct\-style prompting under the same task interface\.

Metrics\.For environment quality, we report average defects per environment \(Def\.\), task\-blocking defects per environment \(Block Def\.\), the percentage of tasks with at least one bounded executable trace \(Feasible\), human task success rate \(Human SR\), state\-invariant violation rate after marker\-triggered updates \(State Viol\.\), and average curation time per environment \(Time\)\. For policy learning, we report success rate \(SR\), average successful\-episode length \(Step\), rejected marker\-write rate \(Reject\), and sample efficiency\. For simulation efficiency, we report LLM calls, token cost, latency, state fidelity, and training throughput\.

Figure 4:Verification–repair convergence\.The repair loop rapidly removes defects and increases the fraction of tasks with bounded executable traces\. The gains saturate after three to four iterations, supporting the use of targeted verification and repair rather than repeated full regeneration\.

### 5\.2Main results

RQ1: Does verification improve environment executability?

Table[1](https://arxiv.org/html/2608.21898#S5.T1)shows that raw LLM\-generated environments are often invalid, with only 48\.6% of tasks admitting bounded executable traces\. Rule\-based checks remove simple structural errors but miss task\-blocking workflow defects and can reduce human success, while single\-pass LLM verification still leaves many blocking defects\. In contrast, our method achieves the fewest total and blocking defects, the highest feasible\-task rate, the lowest state\-violation rate, and lower curation time than self\-consistency and AutoGen\.

Fig\.[4](https://arxiv.org/html/2608.21898#S5.F4)further shows that repair converges quickly: within three iterations, defects drop from 12\.4 to 4\.2 and feasible tasks rise from 48\.6% to 90\.7%, after which gains saturate\.

Table 1:Environment executability and fidelity\.Verification should not merely reduce superficial defects; it should make generated tasks executable under consistent backend dynamics\. Our method reduces both total defects and task\-blocking defects\.RQ2: Does verified synthetic training improve compact policies?

We next evaluate whether verified environments improve downstream policy learning\. Figure[5](https://arxiv.org/html/2608.21898#S5.F5)compares PPO learning curves on held\-out synthetic environments under different training substrates and reward signals\. Training on raw environments gives weak performance because many failed episodes are caused by environment invalidity rather than policy errors\. Dense rewards help on raw environments, but the gains remain limited because progress predicates can be noisy when the underlying scaffold is inconsistent\. Verification alone improves learning under terminal rewards, while combining verified environments with state\-grounded dense rewards produces the strongest learning curve and the best final success rate\.

Figure 5:Verified synthetic training improves compact policy learning\.Raw environments provide noisy supervision, while verified environments make failures attributable to the policy\. State\-grounded dense rewards further accelerate learning and improve final success\.RQ3: Which components matter?

We ablate each major component using the same held\-out environments and PPO setup\. Fig\.[6](https://arxiv.org/html/2608.21898#S5.F6)reports environment quality, task executability, policy success, state violations, and curation cost, with colors indicating direction\-corrected degradation\. The feasibility verifier is most important for executable supervision, as removing it substantially reduces both feasible\-task rate and PPO success\. Marker validation mainly preserves backend fidelity by preventing state violations, while dense rewards primarily improve policy learning without changing environment quality\. Together, these results show that reliable synthetic web training depends on three complementary ingredients: task\-level feasibility verification, state\-safe marker updates, and dense state\-grounded rewards\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/rq3_component_ablation_matrix.png)Figure 6:Component ablation matrix\.Rows remove individual components and columns report metrics with 95% confidence intervals\. Colors denote direction\-corrected degradation\. Feasibility verification, marker validation, and dense rewards drive executability, state fidelity, and policy learning\.

## 6Conclusion

We studied reinforcement learning for web agents from the perspective of environment reliability, arguing that synthetic websites must be executable, state\-consistent, and auditable to provide useful supervision\. We introduced a verified environment\-construction framework that combines offline scaffold verification with event\-driven state updates, enabling compact policies to learn from state\-grounded synthetic interactions\. Experiments show that task feasibility verification, marker\-level validation, and dense backend\-grounded rewards jointly improve environment executability and PPO performance\. These findings highlight verified environments as a scalable training substrate, with future work extending this paradigm to richer multi\-site and multimodal web workflows\.

## References

- Branavan et al\. \[2009\]S\.R\.K\. Branavan, Harr Chen, Luke Zettlemoyer, and Regina Barzilay\.Reinforcement learning for mapping instructions to actions\.In Keh\-Yih Su, Jian Su, Janyce Wiebe, and Haizhou Li, editors,*Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP*, pages 82–90, Suntec, Singapore, August 2009\. Association for Computational Linguistics\.URL[https://aclanthology\.org/P09\-1010/](https://aclanthology.org/P09-1010/)\.
- Chae et al\. \[2025\]Hyungjoo Chae, Sunghwan Kim, Junhee Cho, Seungone Kim, Seungjun Moon, Gyeom Hwangbo, Dongha Lim, Minjin Kim, Yeonjun Hwang, Minju Gwak, et al\.Web\-shepherd: Advancing prms for reinforcing web agents\.*arXiv preprint arXiv:2505\.15277*, 2025\.
- Chen et al\. \[2025\]Zhaorun Chen, Zhuokai Zhao, Kai Zhang, Bo Liu, Qi Qi, Yifan Wu, Tarun Kalluri, Sara Cao, Yuanhao Xiong, Haibo Tong, Huaxiu Yao, Hengduo Li, Jiacheng Zhu, Xian Li, Dawn Song, Bo Li, Jason Weston, and Dat Huynh\.Scaling agent learning via experience synthesis, 2025\.URL[https://arxiv\.org/abs/2511\.03773](https://arxiv.org/abs/2511.03773)\.
- Chezelles et al\. \[2024\]De Chezelles, Thibault Le Sellier, Sahar Omidi Shayegan, Lawrence Keunho Jang, Xing Han Lù, Ori Yoran, Dehan Kong, Frank F Xu, Siva Reddy, Quentin Cappart, et al\.The browsergym ecosystem for web agent research\.*arXiv preprint arXiv:2412\.05467*, 2024\.
- Deng et al\. \[2023\]Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens, Boshi Wang, Huan Sun, and Yu Su\.Mind2web: Towards a generalist agent for the web, 2023\.URL[https://arxiv\.org/abs/2306\.06070](https://arxiv.org/abs/2306.06070)\.
- Drouin et al\. \[2024\]Alexandre Drouin, Maxime Gasse, Massimo Caccia, Issam H Laradji, Manuel Del Verme, Tom Marty, Léo Boisvert, Megh Thakkar, Quentin Cappart, David Vazquez, et al\.Workarena: How capable are web agents at solving common knowledge work tasks?*arXiv preprint arXiv:2403\.07718*, 2024\.
- He et al\. \[2024\]Hongliang He, Wenlin Yao, Kaixin Ma, Wenhao Yu, Yong Dai, Hongming Zhang, Zhenzhong Lan, and Dong Yu\.Webvoyager: Building an end\-to\-end web agent with large multimodal models\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 6864–6890, 2024\.
- Koh et al\. \[2024\]Jing Yu Koh, Robert Lo, Lawrence Jang, Vikram Duvvur, Ming Lim, Po\-Yu Huang, Graham Neubig, Shuyan Zhou, Russ Salakhutdinov, and Daniel Fried\.Visualwebarena: Evaluating multimodal agents on realistic visual web tasks\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pages 881–905, 2024\.
- Liu et al\. \[2018\]Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, and Percy Liang\.Reinforcement learning on web interfaces using workflow\-guided exploration, 2018\.URL[https://arxiv\.org/abs/1802\.08802](https://arxiv.org/abs/1802.08802)\.
- Pan et al\. \[2024\]Jiayi Pan, Yichi Zhang, Nicholas Tomlin, Yifei Zhou, Sergey Levine, and Alane Suhr\.Autonomous evaluation and refinement of digital agents\.*arXiv preprint arXiv:2404\.06474*, 2024\.
- Patel et al\. \[2024\]Ajay Patel, Markus Hofmarcher, Claudiu Leoveanu\-Condrei, Marius\-Constantin Dinu, Chris Callison\-Burch, and Sepp Hochreiter\.Large language models can self\-improve at web agent tasks, 2024\.URL[https://arxiv\.org/abs/2405\.20309](https://arxiv.org/abs/2405.20309)\.
- Putta et al\. \[2024\]Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov\.Agent q: Advanced reasoning and learning for autonomous ai agents\.*arXiv preprint arXiv:2408\.07199*, 2024\.
- Qi et al\. \[2024\]Zehan Qi, Xiao Liu, Iat Long Iong, Hanyu Lai, Xueqiao Sun, Wenyi Zhao, Yu Yang, Xinyue Yang, Jiadai Sun, Shuntian Yao, et al\.Webrl: Training llm web agents via self\-evolving online curriculum reinforcement learning\.*arXiv preprint arXiv:2411\.02337*, 2024\.
- Schulman et al\. \[2017\]John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov\.Proximal policy optimization algorithms, 2017\.URL[https://arxiv\.org/abs/1707\.06347](https://arxiv.org/abs/1707.06347)\.
- Shi et al\. \[2017\]Tianlin Shi, Andrej Karpathy, Linxi Fan, Jonathan Hernandez, and Percy Liang\.World of bits: An open\-domain platform for web\-based agents\.In Doina Precup and Yee Whye Teh, editors,*Proceedings of the 34th International Conference on Machine Learning*, volume 70 of*Proceedings of Machine Learning Research*, pages 3135–3144\. PMLR, 06–11 Aug 2017\.URL[https://proceedings\.mlr\.press/v70/shi17a\.html](https://proceedings.mlr.press/v70/shi17a.html)\.
- Yang et al\. \[2024\]Ke Yang, Yao Liu, Sapana Chaudhary, Rasool Fakoor, Pratik Chaudhari, George Karypis, and Huzefa Rangwala\.Agentoccam: A simple yet strong baseline for llm\-based web agents\.*arXiv preprint arXiv:2410\.13825*, 2024\.
- Yao et al\. \[2023a\]Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan\.Webshop: Towards scalable real\-world web interaction with grounded language agents, 2023a\.URL[https://arxiv\.org/abs/2207\.01206](https://arxiv.org/abs/2207.01206)\.
- Yao et al\. \[2023b\]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\.React: Synergizing reasoning and acting in language models, 2023b\.URL[https://arxiv\.org/abs/2210\.03629](https://arxiv.org/abs/2210.03629)\.
- Zala et al\. \[2024\]Abhay Zala, Jaemin Cho, Han Lin, Jaehong Yoon, and Mohit Bansal\.Envgen: Generating and adapting environments via llms for training embodied agents, 2024\.URL[https://arxiv\.org/abs/2403\.12014](https://arxiv.org/abs/2403.12014)\.
- Zhou et al\. \[2024\]Shuyan Zhou, Frank F\. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig\.Webarena: A realistic web environment for building autonomous agents, 2024\.URL[https://arxiv\.org/abs/2307\.13854](https://arxiv.org/abs/2307.13854)\.

## Appendix AAdditional Technical Details

### A\.1Details of the Preliminary Diagnostics

This subsection provides additional details for the motivating diagnostics in Section[3\.2](https://arxiv.org/html/2608.21898#S3.SS2)\. The goal of these diagnostics is not to serve as the main evaluation, but to empirically justify two design choices: \(i\) one\-shot generated scaffolds require offline verification, and \(ii\) runtime state evolution can be handled by sparse event\-driven updates rather than by calling a generative model at every step\.

#### A\.1\.1Raw Environment Pool

We construct a diagnostic pool of raw LLM\-generated web environments before any verification or repair\. Each environment is generated from a domain\-level site specification and contains page templates, navigation links, database records, state\-change candidates, and task specifications\. The environments cover six representative domains:

𝒟dom=\{e\-commerce,social media,banking,education,healthcare,government\}\.\\mathcal\{D\}\_\{\\mathrm\{dom\}\}=\\\{\\text\{e\-commerce\},\\text\{social media\},\\text\{banking\},\\text\{education\},\\text\{healthcare\},\\text\{government\}\\\}\.For each environmentEE, we record its page setPP, navigation graphLL, database schemaDD, initialized records, interactive elements, and task setT⁡\(E\)T\(E\)\. The diagnostic study reports statistics over 500 raw environments and 6,842 generated tasks\.

#### A\.1\.2Defect Categories and Detection Criteria

We use four defect categories\. A detected defect is represented as

d=⟨type,loc,obj,sev,ev⟩,d=\\langle\\mathrm\{type\},\\mathrm\{loc\},\\mathrm\{obj\},\\mathrm\{sev\},\\mathrm\{ev\}\\rangle,wheretype∈\{ΔS,ΔC,ΔX,ΔT\}\\mathrm\{type\}\\in\\\{\\Delta\_\{S\},\\Delta\_\{C\},\\Delta\_\{X\},\\Delta\_\{T\}\\\}is the defect category,loc\\mathrm\{loc\}is the affected page, DOM node, database field, or task,obj\\mathrm\{obj\}is the affected object,sev∈\[0,1\]\\mathrm\{sev\}\\in\[0,1\]is the severity score, andev\\mathrm\{ev\}is the supporting evidence\.

Table 2:Defect categories and detection criteria used in the preliminary diagnostics\.For each environmentEE, we count the number of detected defects in categoryccas

Nc\(E\)=∑d∈Δ⁡\(E\)𝟏\[type\(d\)=c\],N\_\{c\}\(E\)=\\sum\_\{d\\in\\Delta\(E\)\}\\mathbf\{1\}\[\\mathrm\{type\}\(d\)=c\],whereΔ⁡\(E\)\\Delta\(E\)is the full defect set ofEE\.

#### A\.1\.3Bounded Trace Analysis

To determine whether a task is executable, we perform bounded trace analysis\. Given a tasktt, an initial state distributionρt\\rho\_\{t\}, and a completion constraintCtC\_\{t\}, the analysis searches for an action sequence

a1:H=\(a1,…,aH\)a\_\{1:H\}=\(a\_\{1\},\\ldots,a\_\{H\}\)such that

s0∼ρt,sk\+1=𝒯⁡\(sk,ak\),ak∈A⁡\(ok\),Ct​\(sH\)=1,s\_\{0\}\\sim\\rho\_\{t\},\\qquad s\_\{k\+1\}=\\mathcal\{T\}\(s\_\{k\},a\_\{k\}\),\\qquad a\_\{k\}\\in A\(o\_\{k\}\),\\qquad C\_\{t\}\(s\_\{H\}\)=1,for some horizonH≤HmaxH\\leq H\_\{\\max\}\. If such a trace exists, the task is considered executable under the current scaffold\. Otherwise, the task is marked as blocked\. This trace search is used only for diagnostics, not for policy training\.

Algorithm 1Bounded Trace Analysis for Task Feasibility0:Environment

EE, task

tt, initial states

𝒮0\\mathcal\{S\}\_\{0\}, horizon

HmaxH\_\{\\max\}
0:Executable flag and blocking evidence

1:Initialize queue

Q←\{\(s0,\[\]\):s0∈𝒮0\}Q\\leftarrow\\\{\(s\_\{0\},\[\]\):s\_\{0\}\\in\\mathcal\{S\}\_\{0\}\\\}
2:Initialize visited set

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset
3:for

h=0,…,Hmaxh=0,\\ldots,H\_\{\\max\}do

4:Initialize next queue

Q′←∅Q^\{\\prime\}\\leftarrow\\emptyset
5:foreach

\(s,π\)∈Q\(s,\\pi\)\\in Qdo

6:if

Ct​\(s\)=1C\_\{t\}\(s\)=1then

7:return

\(Executable,π,∅\)\(\\textsc\{Executable\},\\pi,\\emptyset\)
8:endif

9:

o←Render⁡\(s\)o\\leftarrow\\mathrm\{Render\}\(s\)
10:Extract candidate actions

A⁡\(o\)A\(o\)
11:foreach

a∈A⁡\(o\)a\\in A\(o\)do

12:Execute

s′←𝒯⁡\(s,a\)s^\{\\prime\}\\leftarrow\\mathcal\{T\}\(s,a\)
13:Record transition evidence

ev⁡\(s,a,s′\)\\mathrm\{ev\}\(s,a,s^\{\\prime\}\)
14:if

s′∉𝒱s^\{\\prime\}\\notin\\mathcal\{V\}then

15:

Q′←Q′∪\{\(s′,π∘a\)\}Q^\{\\prime\}\\leftarrow Q^\{\\prime\}\\cup\\\{\(s^\{\\prime\},\\pi\\circ a\)\\\}
16:

𝒱←𝒱∪\{s′\}\\mathcal\{V\}\\leftarrow\\mathcal\{V\}\\cup\\\{s^\{\\prime\}\\\}
17:endif

18:endfor

19:endfor

20:

Q←Q′Q\\leftarrow Q^\{\\prime\}
21:endfor

22:Extract blocking evidence from failed expansions

23:return

\(Blocked,∅,ev\)\(\\textsc\{Blocked\},\\emptyset,\\mathrm\{ev\}\)

#### A\.1\.4Blocking Attribution

When a task is blocked, we attribute the failure to the earliest defect category that prevents progress along the attempted workflow\. LetReachh​\(E,t\)\\mathrm\{Reach\}\_\{h\}\(E,t\)denote the set of states reachable withinhhsteps from the task initial state\. A defectddis considered task\-blocking if it invalidates all outgoing progress transitions from the current reachable frontier\. We define

Blockc⁡\(E,t\)=1\\operatorname\{Block\}\_\{c\}\(E,t\)=1if at least one defect of categoryccis responsible for blocking all bounded traces for tasktt\.

If multiple defect categories are implicated, we apply the following priority order based on causal proximity to execution:

ΔT≻ΔS≻ΔX≻ΔC\.\\Delta\_\{T\}\\succ\\Delta\_\{S\}\\succ\\Delta\_\{X\}\\succ\\Delta\_\{C\}\.Feasibility defects are assigned first because they directly indicate missing workflow steps or inaccessible required controls\. Structural defects are next because they prevent reaching necessary pages\. Consistency and semantic defects are assigned when the task path exists but the required state or content is invalid\.

The task\-blocking rate reported in the main text is

Bc\(E\)=1\|T⁡\(E\)\|∑t∈T⁡\(E\)\[Blockc\(E,t\)=1\]\.B\_\{c\}\(E\)=\\frac\{1\}\{\|T\(E\)\|\}\\sum\_\{t\\in T\(E\)\}\\mathbf\{1\}\\\!\\left\[\\operatorname\{Block\}\_\{c\}\(E,t\)=1\\right\]\.The global blocking rate for categoryccacross environments is

B¯c=1\|ℰ\|​∑E∈ℰBc​\(E\)\.\\overline\{B\}\_\{c\}=\\frac\{1\}\{\|\\mathcal\{E\}\|\}\\sum\_\{E\\in\\mathcal\{E\}\}B\_\{c\}\(E\)\.

#### A\.1\.5State\-Change Markers and Runtime Statistics

A state\-change marker identifies a UI event that may modify persistent backend state\. Each marker is represented as

m=\(em,prem,Rm,Wm,Ωm\),m=\(e\_\{m\},\\mathrm\{pre\}\_\{m\},R\_\{m\},W\_\{m\},\\Omega\_\{m\}\),whereeme\_\{m\}is the triggering element,prem\\mathrm\{pre\}\_\{m\}is a precondition,RmR\_\{m\}andWmW\_\{m\}are the permitted read and write fields, andΩm\\Omega\_\{m\}is the operation signature\. Typical marker\-triggered events includeadd\-to\-cart,submit\-order,update\-profile,create\-post, andsubmit\-application\.

For a successful trajectory

τ=\(s0,a0,s1,a1,…,sH\),\\tau=\(s\_\{0\},a\_\{0\},s\_\{1\},a\_\{1\},\\ldots,s\_\{H\}\),we compute the marker\-trigger rate

M\(τ\)=1H∑k=0H−1\[μ\(pk,ak\)≠∅\],M\(\\tau\)=\\frac\{1\}\{H\}\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\],and the number of runtime state\-write calls

U\(τ\)=∑k=0H−1\[μ\(pk,ak\)≠∅\]\.U\(\\tau\)=\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\]\.Here,μ⁡\(pk,ak\)\\mu\(p\_\{k\},a\_\{k\}\)returns the marker triggered by actionaka\_\{k\}on pagepkp\_\{k\}, if such a marker exists\. Deterministic UI actions, including navigation, scrolling, menu expansion, and local text entry, do not trigger persistent state writes\.

For marker\-triggered operations, a candidate state deltaδ^k\\hat\{\\delta\}\_\{k\}is accepted only if it satisfies the marker precondition, schema constraints, and environment invariants:

δk=Validatemk​\(δ^k,sk,ak\)∈𝒰mk​\(sk,ak\)∪\{⊥\}\.\\delta\_\{k\}=\\mathrm\{Validate\}\_\{m\_\{k\}\}\(\\hat\{\\delta\}\_\{k\};s\_\{k\},a\_\{k\}\)\\in\\mathcal\{U\}\_\{m\_\{k\}\}\(s\_\{k\},a\_\{k\}\)\\cup\\\{\\bot\\\}\.The accepted\-delta rate is

A⁡\(τ\)=∑k=0H−1\[μ\(pk,ak\)≠∅\]\[δk≠⊥\]∑k=0H−1\[μ\(pk,ak\)≠∅\]\+ϵ,A\(\\tau\)=\\frac\{\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\]\\mathbf\{1\}\\\!\\left\[\\delta\_\{k\}\\neq\\bot\\right\]\}\{\\sum\_\{k=0\}^\{H\-1\}\\mathbf\{1\}\\\!\\left\[\\mu\(p\_\{k\},a\_\{k\}\)\\neq\\varnothing\\right\]\+\\epsilon\},whereϵ\\epsilonis a small constant used only to avoid division by zero for trajectories with no marker\-triggered event\.

#### A\.1\.6Confidence Intervals and Visualization Protocol

For each scalar statisticz1,…,znz\_\{1\},\\ldots,z\_\{n\}, we report the empirical mean and the normal\-approximation 95% confidence interval:

z¯=1n​∑i=1nzi,CI95=1\.96​std⁡\(z1,…,zn\)n\.\\bar\{z\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}z\_\{i\},\\qquad\\mathrm\{CI\}\_\{95\}=1\.96\\frac\{\\mathrm\{std\}\(z\_\{1\},\\ldots,z\_\{n\}\)\}\{\\sqrt\{n\}\}\.In Fig\.[2](https://arxiv.org/html/2608.21898#S3.F2), each point corresponds to one environment or one trajectory, depending on the panel\. Jitter is used only for visualization and does not affect the reported statistics\. Panel \(a\) shows per\-environment defect counts\. Panel \(b\) shows task\-blocking rates conditioned on detected defects\. Panel \(c\) shows marker\-trigger rates grouped by domain\. Panel \(d\) shows the relationship between episode length and the number of runtime state\-write calls, with the fitted line used only as a visual summary\.

These diagnostics are intended to motivate the method design\. The main experimental evaluation in Section[5](https://arxiv.org/html/2608.21898#S5)separately measures environment quality, repair effectiveness, and downstream policy performance\.

### A\.2Canonical Parsing and Symbolic Verification

##### Raw scaffold artifacts\.

Given a site descriptionqq, the generator produces raw artifacts

ℰ~=\(𝒫~,ℒ~,𝒟~,𝒬~\),\\widetilde\{\\mathcal\{E\}\}=\(\\widetilde\{\\mathcal\{P\}\},\\widetilde\{\\mathcal\{L\}\},\\widetilde\{\\mathcal\{D\}\},\\widetilde\{\\mathcal\{Q\}\}\),where𝒫~\\widetilde\{\\mathcal\{P\}\}contains page templates,ℒ~\\widetilde\{\\mathcal\{L\}\}contains declared links and menus,𝒟~\\widetilde\{\\mathcal\{D\}\}contains database schema and initialized records, and𝒬~\\widetilde\{\\mathcal\{Q\}\}contains task instructions with completion constraints\. The parser converts these artifacts into the canonical scaffoldℰ\(0\)\\mathcal\{E\}^\{\(0\)\}by extracting DOM nodes, interactive elements, database bindings, and state\-change markers\.

##### Page and binding representation\.

Each pagep∈𝒫p\\in\\mathcal\{P\}is represented as

p=\(τp,ℐp,Γp\),p=\(\\tau\_\{p\},\\mathcal\{I\}\_\{p\},\\Gamma\_\{p\}\),whereτp\\tau\_\{p\}is a DOM template,ℐp\\mathcal\{I\}\_\{p\}is the set of interactive elements, andΓp\\Gamma\_\{p\}maps DOM variables to database fields\. For an interactive elemente∈ℐpe\\in\\mathcal\{I\}\_\{p\}, the parser records its element type, admissible arguments, page\-level effect, and marker association\.

##### Marker schema\.

A markerm=\(em,prem,Rm,Wm,Ωm\)m=\(e\_\{m\},\\mathrm\{pre\}\_\{m\},R\_\{m\},W\_\{m\},\\Omega\_\{m\}\)is attached to a persistent state\-changing element\. The preconditionprem\\mathrm\{pre\}\_\{m\}specifies when the operation is valid\. The setsRmR\_\{m\}andWmW\_\{m\}specify database fields that the operation reads and writes\. The operation signatureΩm\\Omega\_\{m\}contains the operation name, target entity type, argument schema, output delta schema, and invariant checks\.

##### Symbolic checks\.

The symbolic verifier computes

Δsym=Δreach∪Δlink∪Δschema∪Δbind∪Δmark\.\\Delta\_\{\\mathrm\{sym\}\}=\\Delta\_\{\\mathrm\{reach\}\}\\cup\\Delta\_\{\\mathrm\{link\}\}\\cup\\Delta\_\{\\mathrm\{schema\}\}\\cup\\Delta\_\{\\mathrm\{bind\}\}\\cup\\Delta\_\{\\mathrm\{mark\}\}\.The individual defect sets are

Δreach\\displaystyle\\Delta\_\{\\mathrm\{reach\}\}=\{p∈𝒫:p∉Reach⁡\(phome,ℒ\)\},\\displaystyle=\\\{p\\in\\mathcal\{P\}:p\\notin\\mathrm\{Reach\}\(p\_\{\\mathrm\{home\}\},\\mathcal\{L\}\)\\\},Δlink\\displaystyle\\Delta\_\{\\mathrm\{link\}\}=\{\(pi,pj\)∈ℒ:pj∉𝒫\},\\displaystyle=\\\{\(p\_\{i\},p\_\{j\}\)\\in\\mathcal\{L\}:p\_\{j\}\\notin\\mathcal\{P\}\\\},Δschema\\displaystyle\\Delta\_\{\\mathrm\{schema\}\}=\{g:g​violates a type, key, range, or required\-field constraint in​𝒟\},\\displaystyle=\\\{g:g\\ \\text\{violates a type, key, range, or required\-field constraint in\}\\ \\mathcal\{D\}\\\},Δbind\\displaystyle\\Delta\_\{\\mathrm\{bind\}\}=\{\(p,g\):g∈Γp,field\(g\)∉Fields\(𝒟\)\},\\displaystyle=\\\{\(p,g\):g\\in\\Gamma\_\{p\},\\;\\mathrm\{field\}\(g\)\\notin\\mathrm\{Fields\}\(\\mathcal\{D\}\)\\\},Δmark\\displaystyle\\Delta\_\{\\mathrm\{mark\}\}=\{m∈ℳ:Rm∪Wm⊈Fields⁡\(𝒟\)​or​Ωm​has an invalid argument schema\}\.\\displaystyle=\\\{m\\in\\mathcal\{M\}:R\_\{m\}\\cup W\_\{m\}\\nsubseteq\\mathrm\{Fields\}\(\\mathcal\{D\}\)\\ \\text\{or\}\\ \\Omega\_\{m\}\\ \\text\{has an invalid argument schema\}\\\}\.Here,phomep\_\{\\mathrm\{home\}\}is the entry page,Reach\\mathrm\{Reach\}returns reachable pages under the navigation graph, andFields⁡\(𝒟\)\\mathrm\{Fields\}\(\\mathcal\{D\}\)is the set of valid database fields\. These deterministic checks are run before semantic verification and after each repair iteration on the affected subgraph\.

### A\.3Semantic Verifiers and Defect\-Triggered Coordination

##### Verifier roles\.

We use four semantic verifiers:

𝒥=\{str,sem,cons,feas\}\.\\mathcal\{J\}=\\\{\\mathrm\{str\},\\mathrm\{sem\},\\mathrm\{cons\},\\mathrm\{feas\}\\\}\.The structural verifier checks layout coherence, missing required elements, and navigation anomalies beyond link existence\. The semantic verifier checks content validity, content–type compatibility, placeholder text, and implausible values\. The consistency verifier checks entity attributes across pages and rendered states\. The feasibility verifier searches for bounded executable traces that satisfy task constraints\.

##### Structured defect report\.

Each verifierj∈𝒥j\\in\\mathcal\{J\}returns a set of reports

𝒜j​\(ℰ\(r\)\)→Δj\(r\)=\{dj,1\(r\),…,dj,nj\(r\)\}\.\\mathcal\{A\}\_\{j\}\(\\mathcal\{E\}^\{\(r\)\}\)\\rightarrow\\Delta\_\{j\}^\{\(r\)\}=\\\{d\_\{j,1\}^\{\(r\)\},\\ldots,d\_\{j,n\_\{j\}\}^\{\(r\)\}\\\}\.Each report has the schema

d=⟨type,loc,obj,sev,ev,c⟩,d=\\langle\\mathrm\{type\},\\mathrm\{loc\},\\mathrm\{obj\},\\mathrm\{sev\},\\mathrm\{ev\},c\\rangle,wheretype\\mathrm\{type\}is the defect category,loc\\mathrm\{loc\}is the page, DOM node, database field, marker, or task where the defect occurs,obj\\mathrm\{obj\}is the affected object,sev∈\[0,1\]\\mathrm\{sev\}\\in\[0,1\]is severity,ev\\mathrm\{ev\}is supporting evidence, andc∈\[0,1\]c\\in\[0,1\]is verifier confidence\.

##### Deduplication\.

Reports are merged by a canonical key

κ⁡\(d\)=\(type⁡\(d\),loc⁡\(d\),obj⁡\(d\)\)\.\\kappa\(d\)=\(\\mathrm\{type\}\(d\),\\mathrm\{loc\}\(d\),\\mathrm\{obj\}\(d\)\)\.All reports with the same key are grouped into one defect candidate\. The main text defines the aggregated confidence in Eq\. \([8](https://arxiv.org/html/2608.21898#S4.E8)\)\.

##### Defect\-triggered coordination\.

Verifier communication is routed by defect type:

B⁡\(type⁡\(d\)\)⊆𝒥,B\(\\mathrm\{type\}\(d\)\)\\subseteq\\mathcal\{J\},whereBBreturns verifiers that need to re\-check downstream effects ofdd\. We use the following routing rules:

B⁡\(structural\)\\displaystyle B\(\\mathrm\{structural\}\)=\{feas\},\\displaystyle=\\\{\\mathrm\{feas\}\\\},B⁡\(semantic\)\\displaystyle B\(\\mathrm\{semantic\}\)=\{cons\},\\displaystyle=\\\{\\mathrm\{cons\}\\\},B⁡\(consistency\)\\displaystyle B\(\\mathrm\{consistency\}\)=\{feas\},\\displaystyle=\\\{\\mathrm\{feas\}\\\},B⁡\(feasibility\)\\displaystyle B\(\\mathrm\{feasibility\}\)=\{str,cons\}\.\\displaystyle=\\\{\\mathrm\{str\},\\mathrm\{cons\}\\\}\.For a defectdd, the coordinator adds targeted requests

Q←Q∪\{\(d,j′\):j′∈B⁡\(type⁡\(d\)\)\}\.Q\\leftarrow Q\\cup\\\{\(d,j^\{\\prime\}\):j^\{\\prime\}\\in B\(\\mathrm\{type\}\(d\)\)\\\}\.The receiving verifier checks only the affected pages, database fields, markers, and tasks referenced in the report evidence\.

##### Accepted defect set\.

A defect is accepted for repair when

conf⁡\(d\)≥τcorsev⁡\(d\)≥τs,\\mathrm\{conf\}\(d\)\\geq\\tau\_\{c\}\\quad\\text\{or\}\\quad\\mathrm\{sev\}\(d\)\\geq\\tau\_\{s\},whereτc\\tau\_\{c\}is the confidence threshold andτs\\tau\_\{s\}is the severity threshold\. This rule preserves high\-severity single\-verifier defects while filtering low\-confidence reports\.

### A\.4Repair Operators and Termination

##### Dependency graph\.

Accepted defects form a dependency graph

GΔ\(r\)=\(Δacc\(r\),ℛΔ\(r\)\),G\_\{\\Delta\}^\{\(r\)\}=\(\\Delta\_\{\\mathrm\{acc\}\}^\{\(r\)\},\\mathcal\{R\}\_\{\\Delta\}^\{\(r\)\}\),where\(di,dj\)∈ℛΔ\(r\)\(d\_\{i\},d\_\{j\}\)\\in\\mathcal\{R\}\_\{\\Delta\}^\{\(r\)\}means thatdid\_\{i\}must be repaired beforedjd\_\{j\}\. Dependencies are added when a database schema defect affects page rendering, when a marker defect affects task feasibility, and when a structural defect blocks access to pages used by semantic and consistency checks\.

##### Ready set\.

At iterationrr, the ready set is

Ready\(r\)=\{d∈Δacc\(r\):PredGΔ​\(d\)⊆𝒮done\(r\)\},\\mathrm\{Ready\}^\{\(r\)\}=\\\{d\\in\\Delta\_\{\\mathrm\{acc\}\}^\{\(r\)\}:\\mathrm\{Pred\}\_\{G\_\{\\Delta\}\}\(d\)\\subseteq\\mathcal\{S\}\_\{\\mathrm\{done\}\}^\{\(r\)\}\\\},wherePredGΔ​\(d\)\\mathrm\{Pred\}\_\{G\_\{\\Delta\}\}\(d\)is the predecessor set of defectdd, and𝒮done\(r\)\\mathcal\{S\}\_\{\\mathrm\{done\}\}^\{\(r\)\}is the set of repaired defects\. The selected defect is

d⋆=arg⁡maxd∈Ready\(r\)⁡score⁡\(d\),d^\{\\star\}=\\arg\\max\_\{d\\in\\mathrm\{Ready\}^\{\(r\)\}\}\\mathrm\{score\}\(d\),wherescore⁡\(d\)\\mathrm\{score\}\(d\)is defined in Eq\. \([9](https://arxiv.org/html/2608.21898#S4.E9)\)\.

##### Repair operators\.

The repair operatorℛd⋆\\mathcal\{R\}\_\{d^\{\\star\}\}edits only objects referenced by the accepted report:

ℰ\(r\+1\)=ℛd⋆​\(ℰ\(r\)\)\.\\mathcal\{E\}^\{\(r\+1\)\}=\\mathcal\{R\}\_\{d^\{\\star\}\}\(\\mathcal\{E\}^\{\(r\)\}\)\.We use the following repair families\.

- •Structural repair\.Adds missing pages, repairs invalid links, restores required navigation elements, and reconnects orphaned pages to the navigation graph\.
- •Semantic repair\.Rewrites invalid content while preserving database bindings and task\-relevant entities\.
- •Consistency repair\.Selects a canonical value from the database and propagates it to all dependent DOM bindings\.
- •Feasibility repair\.Adds missing form fields, buttons, intermediate pages, marker signatures, and database writes required by a bounded task trace\.
- •Marker repair\.Corrects marker preconditions, argument schema, read–write sets, and invariant checks\.

##### Incremental re\-verification\.

After repairingd⋆d^\{\\star\}, we re\-check the affected subgraph

𝒩⁡\(d⋆\)=\{p:distℒ​\(p,loc⁡\(d⋆\)\)≤1\}∪Tasks⁡\(d⋆\)∪Markers⁡\(d⋆\),\\mathcal\{N\}\(d^\{\\star\}\)=\\\{p:\\mathrm\{dist\}\_\{\\mathcal\{L\}\}\(p,\\mathrm\{loc\}\(d^\{\\star\}\)\)\\leq 1\\\}\\cup\\mathrm\{Tasks\}\(d^\{\\star\}\)\\cup\\mathrm\{Markers\}\(d^\{\\star\}\),wheredistℒ\\mathrm\{dist\}\_\{\\mathcal\{L\}\}is graph distance in the navigation graph\. This prevents each repair iteration from re\-running all verifiers on the entire environment\.

##### Feasibility termination\.

For a tasktt, feasibility is accepted when the feasibility verifier finds a bounded executable trace

π1:H=\(a1,…,aH\)such thatsk\+1=F\(sk,ak\),ak∈𝒜\(ok\),Ct\(sH\)=1\.\\pi\_\{1:H\}=\(a\_\{1\},\\ldots,a\_\{H\}\)\\quad\\text\{such that\}\\quad s\_\{k\+1\}=F\(s\_\{k\},a\_\{k\}\),\\;a\_\{k\}\\in\\mathcal\{A\}\(o\_\{k\}\),\\;C\_\{t\}\(s\_\{H\}\)=1\.The repair loop terminates when all accepted critical defects are resolved and every task has at least one such bounded trace\.

### A\.5Event\-Driven Simulator Details

##### Deterministic transition\.

The deterministic transitionFdetF\_\{\\mathrm\{det\}\}handles navigation, local input editing, scroll state, menu expansion, client\-side field validation, and page rendering\. It does not modify persistent database records outside session\-local variables\.

##### Candidate delta generation\.

For a marker\-triggered action, the state writer receives

zk=Pack⁡\(pk,bk,Rm,σk,ak,Ωm\),z\_\{k\}=\\mathrm\{Pack\}\(p\_\{k\},b\_\{k,R\_\{m\}\},\\sigma\_\{k\},a\_\{k\},\\Omega\_\{m\}\),wherebk,Rmb\_\{k,R\_\{m\}\}is the subset of database records referenced by the marker read set\. The state writer outputs a candidate delta

δ^k=Gψ​\(zk\)\.\\hat\{\\delta\}\_\{k\}=G\_\{\\psi\}\(z\_\{k\}\)\.The output schema contains only field\-level writes, session updates, and a short justification tied toΩm\\Omega\_\{m\}\. Full\-page natural\-language regeneration is not accepted as a state update\.

##### Feasible update set\.

For markermm, the feasible update set is

𝒰m\(sk,ak\)=\{δ:prem\(sk,ak\)=1,RW\(δ\)⊆Rm∪Wm,bk⊕δ⊧𝒟,Inv\(sk⊕δ\)=1\}\.\\mathcal\{U\}\_\{m\}\(s\_\{k\},a\_\{k\}\)=\\left\\\{\\delta:\\mathrm\{pre\}\_\{m\}\(s\_\{k\},a\_\{k\}\)=1,\\;\\mathrm\{RW\}\(\\delta\)\\subseteq R\_\{m\}\\cup W\_\{m\},\\;b\_\{k\}\\oplus\\delta\\models\\mathcal\{D\},\\;\\mathrm\{Inv\}\(s\_\{k\}\\oplus\\delta\)=1\\right\\\}\.Here,RW⁡\(δ\)\\mathrm\{RW\}\(\\delta\)is the set of fields read and written by the delta,bk⊕δb\_\{k\}\\oplus\\deltais the database after applying the delta, andInv\\mathrm\{Inv\}contains environment invariants including schema validity, entity identity consistency, permission constraints, and task\-independent workflow constraints\.

##### Validation\.

The validation operator returns

Validatem​\(δ^k,sk,ak\)=\{δ^k,δ^k∈𝒰m​\(sk,ak\),⊥,δ^k∉𝒰m​\(sk,ak\)\.\\mathrm\{Validate\}\_\{m\}\(\\hat\{\\delta\}\_\{k\};s\_\{k\},a\_\{k\}\)=\\begin\{cases\}\\hat\{\\delta\}\_\{k\},&\\hat\{\\delta\}\_\{k\}\\in\\mathcal\{U\}\_\{m\}\(s\_\{k\},a\_\{k\}\),\\\\ \\bot,&\\hat\{\\delta\}\_\{k\}\\notin\\mathcal\{U\}\_\{m\}\(s\_\{k\},a\_\{k\}\)\.\\end\{cases\}If the result is⊥\\bot, the simulator returns the original state, setsϵk=1\\epsilon\_\{k\}=1, and exposes the rejected operation in the transition log\. Otherwise, the simulator appliessk\+1=sk⊕δks\_\{k\+1\}=s\_\{k\}\\oplus\\delta\_\{k\}, re\-renders the current page throughRender\\mathrm\{Render\}, and records the state delta for reward computation and debugging\.

### A\.6Reward Compilation and PPO Training

##### Predicate compilation\.

Each completion constraintCtC\_\{t\}is decomposed into predicates

Φt=\{ϕt,1,…,ϕt,Mt\}\.\\Phi\_\{t\}=\\\{\\phi\_\{t,1\},\\ldots,\\phi\_\{t,M\_\{t\}\}\\\}\.Predicates are implemented as database queries, session\-state checks, and DOM selectors\. Examples include checking that a required page has been visited, a field has a valid value, a target entity has been created, an attribute has been updated correctly, and a rendered page reflects the backend value\.

##### Candidate action scoring\.

The policy receives the task instructionxtx\_\{t\}, the rendered observationoko\_\{k\}, and the candidate action set𝒜⁡\(ok\)\\mathcal\{A\}\(o\_\{k\}\)\. It scores each candidate action by

ℓθ​\(a,ok,xt\),a∈𝒜⁡\(ok\),\\ell\_\{\\theta\}\(a;o\_\{k\},x\_\{t\}\),\\quad a\\in\\mathcal\{A\}\(o\_\{k\}\),and normalizes over the current candidate set:

πθ​\(a∣ok,xt\)=exp⁡\(ℓθ​\(a,ok,xt\)\)∑a′∈𝒜⁡\(ok\)exp⁡\(ℓθ​\(a′,ok,xt\)\)\.\\pi\_\{\\theta\}\(a\\mid o\_\{k\},x\_\{t\}\)=\\frac\{\\exp\(\\ell\_\{\\theta\}\(a;o\_\{k\},x\_\{t\}\)\)\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\(o\_\{k\}\)\}\\exp\(\\ell\_\{\\theta\}\(a^\{\\prime\};o\_\{k\},x\_\{t\}\)\)\}\.Since sampling is restricted to𝒜⁡\(ok\)\\mathcal\{A\}\(o\_\{k\}\), invalid DOM actions do not appear in the policy distribution\. Rejected transitions in the main reward arise from marker validation failures, not from selecting unavailable DOM elements\.

##### Trajectory collection\.

For each tasktt, PPO collects rollouts

τ=\(o0,a0,r0,o1,…,oH\)\\tau=\(o\_\{0\},a\_\{0\},r\_\{0\},o\_\{1\},\\ldots,o\_\{H\}\)by executingπθ\\pi\_\{\\theta\}in the event\-driven simulator\. The environment computes rewards using Eq\. \([13](https://arxiv.org/html/2608.21898#S4.E13)\); the policy does not observe the backend state, completion constraint, or progress predicates\.

##### Advantage estimation\.

We use generalized advantage estimation:

A^k=∑ℓ=0H−k−1\(ξ​λGAE\)ℓ​δk\+ℓV,δkV=rk\+ξ​Vθold​\(ok\+1,xt\)−Vθold​\(ok,xt\),\\hat\{A\}\_\{k\}=\\sum\_\{\\ell=0\}^\{H\-k\-1\}\(\\xi\\lambda\_\{\\mathrm\{GAE\}\}\)^\{\\ell\}\\delta^\{V\}\_\{k\+\\ell\},\\qquad\\delta^\{V\}\_\{k\}=r\_\{k\}\+\\xi V\_\{\\theta\_\{\\mathrm\{old\}\}\}\(o\_\{k\+1\},x\_\{t\}\)\-V\_\{\\theta\_\{\\mathrm\{old\}\}\}\(o\_\{k\},x\_\{t\}\),whereξ\\xiis the RL discount factor,λGAE\\lambda\_\{\\mathrm\{GAE\}\}controls the bias–variance trade\-off, andVθV\_\{\\theta\}is the value function\.

##### PPO objective\.

The probability ratio is

ρk​\(θ\)=πθ​\(ak∣ok,xt\)πθold​\(ak∣ok,xt\)\.\\rho\_\{k\}\(\\theta\)=\\frac\{\\pi\_\{\\theta\}\(a\_\{k\}\\mid o\_\{k\},x\_\{t\}\)\}\{\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(a\_\{k\}\\mid o\_\{k\},x\_\{t\}\)\}\.The policy is optimized with the clipped objective

ℒPPO​\(θ\)=\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{PPO\}\}\(\\theta\)=𝔼k​\[min⁡\(ρk​\(θ\)​A^k,clip⁡\(ρk​\(θ\),1−ϵ,1\+ϵ\)​A^k\)\]\\displaystyle\\mathbb\{E\}\_\{k\}\\left\[\\min\\left\(\\rho\_\{k\}\(\\theta\)\\hat\{A\}\_\{k\},\\mathrm\{clip\}\(\\rho\_\{k\}\(\\theta\),1\-\\epsilon,1\+\\epsilon\)\\hat\{A\}\_\{k\}\\right\)\\right\]−cv𝔼k\[\(Vθ\(ok,xt\)−R^k\)2\]\+ch𝔼k\[ℋ\(πθ\(⋅∣ok,xt\)\)\]\.\\displaystyle\-c\_\{v\}\\mathbb\{E\}\_\{k\}\\left\[\\left\(V\_\{\\theta\}\(o\_\{k\},x\_\{t\}\)\-\\hat\{R\}\_\{k\}\\right\)^\{2\}\\right\]\+c\_\{h\}\\mathbb\{E\}\_\{k\}\\left\[\\mathcal\{H\}\(\\pi\_\{\\theta\}\(\\cdot\\mid o\_\{k\},x\_\{t\}\)\)\\right\]\.whereϵ\\epsilonis the clipping threshold,R^k\\hat\{R\}\_\{k\}is the empirical return,cvc\_\{v\}weights the value loss,chc\_\{h\}weights the entropy bonus, andℋ\\mathcal\{H\}is policy entropy\.

##### Evaluation\-time policy\.

At evaluation time, the learned policy uses onlyoko\_\{k\},xtx\_\{t\}, and the DOM\-grounded candidate actions𝒜⁡\(ok\)\\mathcal\{A\}\(o\_\{k\}\)\. It does not call the generation model, semantic verifiers, repair operators, or constrained state writer\.

### A\.7Four agents design

Four specialized LLM\-based agents collaborate to detect complex defects requiring semantic understanding\. Each agent is implemented as a GPT\-4 instance with domain\-specific system prompts and structured output schemas\.

Structure Validator \(SV\):Analyzes page layouts and navigation flows to identify structural anomalies beyond simple link checking\. SV examines: \(1\) navigation consistency \(breadcrumb accuracy, menu completeness\), \(2\) page hierarchy adherence \(category→\\rightarrowsubcategory→\\rightarrowitem\), and \(3\) required element presence \(search bars, footers, headers\)\. Detection is based on embedding similarity using a fine\-tuned sentence transformer to identify outlier page structures\.

Content Auditor \(CA\):Examines content for semantic validity using GPT\-4’s world knowledge\. CA detects: \(1\) placeholder text patterns \(“Lorem ipsum”, “\[TODO\]”, “Example”\), \(2\) content\-metadata mismatches \(product description contradicting title\), \(3\) implausible content \(negative prices, future birthdates\), and \(4\) inappropriate content for page type \(technical jargon on consumer pages\)\.

Consistency Checker \(CC\):Cross\-references data across pages using an entity database\. For each entityeewith attributes\{a1,…,ak\}\\\{a\_\{1\},\\ldots,a\_\{k\}\\\}, CC tracks all occurrences across pages and flags whenai​\(pj\)≠ai​\(pk\)a\_\{i\}\(p\_\{j\}\)\\neq a\_\{i\}\(p\_\{k\}\)for any attribute\. Semantic equivalence is handled via embedding similarity \(threshold 0\.92\) for string attributes\.

Task Feasibility Analyzer \(TFA\):Traces task execution paths by simulating agent trajectories\. For each taskt∈𝒯t\\in\\mathcal\{T\}, TFA generates an action sequence using GPT\-4 and verifies: \(1\) all required pages exist, \(2\) all form fields are accessible, \(3\) all buttons are clickable, and \(4\) the goal state is reachable\.

Table 3:Defect Examples and Detection Complexity#### A\.7\.1Defect\-Triggered Communication Protocol

Rather than independent parallel execution, agents communicate through DTCP to enable cross\-agent defect correlation\. When agentAiA\_\{i\}detects a defectdd, it broadcasts a structured message to relevant agents:

msg​\(d\)=⟨type,location,severity,evidence⟩\\text\{msg\}\(d\)=\\langle\\text\{type\},\\text\{location\},\\text\{severity\},\\text\{evidence\}\\rangle\(14\)
Receiving agents use domain\-specific rules to determine follow\-up actions:

- •S​V→T​F​ASV\\rightarrow TFA: Structural defects trigger task re\-verification
- •C​A→C​CCA\\rightarrow CC: Semantic issues trigger consistency checks
- •C​C→T​F​ACC\\rightarrow TFA: Data conflicts trigger feasibility re\-analysis
- •T​F​A→S​VTFA\\rightarrow SV: Workflow gaps trigger navigation review

### A\.8Agent Configuration Details

##### Structural Verification Agent

The Structural Verification Agent \(𝒜S\\mathcal\{A\}\_\{S\}\) employs the following prompt template:

![Refer to caption](https://arxiv.org/html/2608.21898v1/fig/ws.png)Figure 7:Structural Verification Agent
##### Consistency Verification Agent

The Consistency Verification Agent \(𝒜C\\mathcal\{A\}\_\{C\}\) uses:

![Refer to caption](https://arxiv.org/html/2608.21898v1/fig/cv.png)Figure 8:Consistency Verification Agent
##### Cross\-Page Verification Agent

The Cross\-Page Verification Agent \(𝒜X\\mathcal\{A\}\_\{X\}\) configuration:

![Refer to caption](https://arxiv.org/html/2608.21898v1/fig/cross-agent.png)Figure 9:Cross\-Page Verification Agent
##### Task Flow Verification Agent

The Task Flow Verification Agent \(𝒜T\\mathcal\{A\}\_\{T\}\) prompt:

![Refer to caption](https://arxiv.org/html/2608.21898v1/fig/task-agent.png)Figure 10:Task Flow Verification Agent

### A\.9DTCP Protocol Specification

Algorithm[2](https://arxiv.org/html/2608.21898#alg2)presents the complete Defect\-Triggered Communication Protocol\.

Algorithm 2Defect\-Triggered Communication Protocol \(DTCP\)0:Agents

\{𝒜S,𝒜C,𝒜X,𝒜T\}\\\{\\mathcal\{A\}\_\{S\},\\mathcal\{A\}\_\{C\},\\mathcal\{A\}\_\{X\},\\mathcal\{A\}\_\{T\}\\\}, Environment

ℰ\\mathcal\{E\}, Thresholds

\{τ1,τ2\}\\\{\\tau\_\{1\},\\tau\_\{2\}\\\}
0:Aggregated defect reports

Δ\\Delta
1:Initialize message queue

Q←∅Q\\leftarrow\\emptyset
2:Initialize defect set

Δ←∅\\Delta\\leftarrow\\emptyset
3:foreach agent

𝒜i\\mathcal\{A\}\_\{i\}in paralleldo

4:

δi←𝒜i\.Verify​\(ℰ\)\\delta\_\{i\}\\leftarrow\\mathcal\{A\}\_\{i\}\.\\textsc\{Verify\}\(\\mathcal\{E\}\)
5:foreach defect

d∈δid\\in\\delta\_\{i\}do

6:if

d\.confidence<τ1d\.\\text\{confidence\}<\\tau\_\{1\}then

7:

Q\.Push​\(RequestVerification​\(d,𝒜i\)\)Q\.\\textsc\{Push\}\(\\textsc\{RequestVerification\}\(d,\\mathcal\{A\}\_\{i\}\)\)
8:elseif

d\.affects\_other\_domaind\.\\text\{affects\\\_other\\\_domain\}then

9:

Q\.Push​\(NotifyRelated​\(d,𝒜i\)\)Q\.\\textsc\{Push\}\(\\textsc\{NotifyRelated\}\(d,\\mathcal\{A\}\_\{i\}\)\)
10:endif

11:

Δ←Δ∪\{d\}\\Delta\\leftarrow\\Delta\\cup\\\{d\\\}
12:endfor

13:endfor

14:while

Q≠∅Q\\neq\\emptysetdo

15:

m​s​g←Q\.Pop​\(\)msg\\leftarrow Q\.\\textsc\{Pop\}\(\)
16:

𝒜j←GetTargetAgent​\(m​s​g\)\\mathcal\{A\}\_\{j\}\\leftarrow\\textsc\{GetTargetAgent\}\(msg\)
17:

r​e​s​p​o​n​s​e←𝒜j\.ProcessMessage​\(m​s​g\)response\\leftarrow\\mathcal\{A\}\_\{j\}\.\\textsc\{ProcessMessage\}\(msg\)
18:if

r​e​s​p​o​n​s​e\.type=Confirmresponse\.\\text\{type\}=\\textsc\{Confirm\}then

19:

Δ\[msg\.defect\]\.confidence\+=τ2\\Delta\[msg\.defect\]\.\\text\{confidence\}\\mathrel\{\+\}=\\tau\_\{2\}
20:elseif

r​e​s​p​o​n​s​e\.type=Rejectresponse\.\\text\{type\}=\\textsc\{Reject\}then

21:

Δ\.Remove\(msg\.defect\)\\Delta\.\\textsc\{Remove\}\(msg\.defect\)
22:elseif

r​e​s​p​o​n​s​e\.type=NewDefectresponse\.\\text\{type\}=\\textsc\{NewDefect\}then

23:

Δ←Δ∪\{response\.defect\}\\Delta\\leftarrow\\Delta\\cup\\\{response\.defect\\\}
24:endif

25:endwhile

26:return

Δ\\Delta

### A\.10PWRS Algorithm Details

The Priority\-Weighted Repair Scheduling \(PWRS\) algorithm considers defect dependencies and repair costs\.

Algorithm 3Priority\-Weighted Repair Scheduling \(PWRS\)0:Defects

Δ\\Delta, Dependency graph

GdG\_\{d\}, Weight function

ww
0:Ordered repair schedule

SS
1:

S←\[\]S\\leftarrow\[\]
2:Compute priority scores:

∀d∈Δ:p⁡\(d\)=w⁡\(d\)⋅downstream​\(d,Gd\)\\forall d\\in\\Delta:p\(d\)=w\(d\)\\cdot\\text\{downstream\}\(d,G\_\{d\}\)
3:Build dependency\-aware priority queue

P​QPQordered by

p⁡\(d\)p\(d\)
4:while

P​Q≠∅PQ\\neq\\emptysetdo

5:

d←P​Q\.PopMax​\(\)d\\leftarrow PQ\.\\textsc\{PopMax\}\(\)
6:if

DependenciesSatisfied​\(d,S,Gd\)\\textsc\{DependenciesSatisfied\}\(d,S,G\_\{d\}\)then

7:

S\.Append​\(d\)S\.\\textsc\{Append\}\(d\)
8:Update downstream priorities in

P​QPQ
9:else

10:

P​Q\.Push​\(d\)PQ\.\\textsc\{Push\}\(d\)with reduced priority

11:endif

12:endwhile

13:return

SS

## Appendix BExperimental Details

### B\.1Implementation Details and Hyperparameters

We implement the environment generator, canonical parser, symbolic verifiers, repair operators, event\-driven simulator, and PPO training pipeline in Python\. Each synthetic environment is stored as a structured scaffold containing page templates, navigation edges, database schemas and records, marker specifications, task instructions, and programmatic completion constraints\. All baselines use the same raw scaffolds and train the same compact DOM\-grounded policy unless otherwise stated\.

The policy contains fewer than 10M parameters and scores only DOM\-grounded candidate actions extracted from the current rendered observation\. We use Adam for optimization\. Unless otherwise stated, PPO uses discount factorξ=0\.99\\xi=0\.99, GAE parameterλGAE=0\.95\\lambda\_\{\\mathrm\{GAE\}\}=0\.95, clipping threshold0\.20\.2, value\-loss coefficient0\.50\.5, entropy coefficient0\.010\.01, learning rate3×10−43\\times 10^\{\-4\}, and gradient clipping threshold0\.50\.5\. Advantages are normalized within each PPO batch\.

The dense reward coefficients in Eq\. \([13](https://arxiv.org/html/2608.21898#S4.E13)\) are fixed across domains and selected on the validation split:α=0\.5\\alpha=0\.5,γ=0\.2\\gamma=0\.2, andη=0\.01\\eta=0\.01\. Here,α\\alphacontrols the contribution of verified progress shaping,γ\\gammapenalizes rejected marker\-triggered state updates, andη\\etais a small per\-step cost that discourages unnecessarily long trajectories\. The maximum episode horizon isHmax=40H\_\{\\max\}=40\. Each PPO update uses40964096rollout steps, minibatch size512512, and44optimization epochs\. We train each policy for1\.0×1061\.0\\times 10^\{6\}environment steps unless otherwise stated\.

For all reported policy experiments, we use the same train/validation/test environment split described in Section[5](https://arxiv.org/html/2608.21898#S5)\. Hyperparameters are selected using validation environments only and are then fixed for held\-out synthetic evaluation and transfer evaluation\.

### B\.2Compute Resources

All experiments were run on a shared Linux compute cluster using CPU rollout workers and single\-GPU training jobs\. Each PPO training job used one NVIDIA A10G GPU with 24GB memory, 16 CPU cores, 64GB system RAM, and approximately 200GB local scratch storage for rollout logs and checkpoints\. Synthetic environment generation and verification primarily used CPU workers plus LLM API calls, while PPO training used GPU workers for policy optimization and CPU workers for parallel environment rollout\.

A single PPO run for one training condition takes approximately 3\.2 hours on one NVIDIA A10G GPU, corresponding to about 3\.2 GPU\-hours\. The main learning\-curve experiments use five training conditions and three random seeds, for a total of approximately 48 GPU\-hours\. The component ablation experiments use seven ablated variants and three random seeds, requiring approximately 67 GPU\-hours\. The additional diagnostic experiments, including defect\-impact analysis, dense\-reward alignment, simulator tradeoff analysis, and failure attribution, require approximately 35 GPU\-hours in total\. Transfer evaluation on WebArena, WebShop, and MiniWoB\+\+ requires approximately 8 GPU\-hours and 90 CPU\-hours because the learned policy does not call an LLM at evaluation time\.

Environment construction uses 500 raw synthetic environments and invokes LLM\-based verifiers only during offline scaffold verification and repair\. For our full verification pipeline, the average curation time is 18 minutes per environment, as reported in Table[1](https://arxiv.org/html/2608.21898#S5.T1)\. This corresponds to approximately 150 CPU\-hours for the full synthetic environment suite, excluding parallelization overhead\. The event\-driven simulator cost and token usage are reported in Figure[11](https://arxiv.org/html/2608.21898#A3.F11)\. Across all reported environment\-construction runs, we used approximately 18 million LLM input/output tokens for scaffold generation, verification, and repair\.

## Appendix CAdditional Experimental Results

### C\.1Does the learned policy transfer beyond synthetic environments?

The main experiments evaluate whether verification improves learning on held\-out synthetic environments\. We additionally test whether the learned policy transfers to external web\-agent benchmarks under a unified DOM\-grounded action interface\. The goal of this experiment is not to claim that a small policy universally dominates frontier LLM agents under their native multimodal browser interfaces, but to test whether verified synthetic training produces reusable interaction skills when all methods are evaluated under the same observation and action protocol\.

##### Protocol\.

We evaluate on three external benchmarks: WebArena\-compatible tasks, WebShop, and MiniWoB\+\+\. For WebArena, we use a DOM\-compatible subset that does not require private credentials, file uploads, or visual\-only information unavailable to the compact policy\. Task goals are not rewritten, and benchmark success criteria are preserved\. All evaluated methods receive the same textual task instruction and the same serialized DOM observation\. All methods select from the same DOM\-grounded action set, including click, type, select, and navigation actions\. The compact policies do not call an LLM during evaluation\. GPT\-4 baselines use the same action interface and are evaluated with a fixed action budget\.

Table 4:Transfer\-evaluation protocol\. We use a unified DOM\-grounded interface for all methods\. WebArena results are reported on the DOM\-compatible subset described in the text; WebShop and MiniWoB\+\+ use their original success evaluators\.
##### Baselines\.

We compare against GPT\-4 direct prompting, GPT\-4 with ReAct\-style prompting, a small policy trained by behavior cloning on synthetic trajectories, PPO trained on raw synthetic environments, PPO trained on verified environments with terminal rewards only, and our full method\. GPT\-4 baselines use temperature00, a maximum of 20 actions per episode for WebArena\-compatible tasks, and the same DOM action schema as the compact policy\. For learned policies, no external benchmark fine\-tuning is performed\.

Table 5:Transfer beyond synthetic environments\. All methods are evaluated under the same DOM\-grounded observation and action interface\. The compact policy trained in verified environments transfers better than policies trained on raw synthetic environments, while requiring no LLM calls at evaluation time\. The comparison to GPT\-4 baselines should be interpreted under this constrained DOM\-only interface, not as a claim of general superiority under native multimodal browser use\.
##### Analysis\.

Verified synthetic training improves transfer on all three external benchmarks\. Compared with PPO trained on raw synthetic environments, our full method improves success by6\.26\.2points on WebArena\-compatible tasks,14\.214\.2points on WebShop, and16\.516\.5points on MiniWoB\+\+\. The largest gains appear on WebShop and MiniWoB\+\+, where the external environments share more structural similarity with the synthetic training tasks\. On WebArena\-compatible tasks, the gains are smaller but still consistent, suggesting that verification improves general interaction skills rather than only fitting synthetic layouts\. Importantly, the compact policy uses zero LLM calls at evaluation time\. We therefore interpret these results as evidence that verified synthetic environments provide reusable supervision for efficient policies under a common DOM\-grounded interface\.

### C\.2Does event\-driven simulation reduce cost while preserving state fidelity?

A central design choice of our framework is to execute ordinary interface transitions deterministically and invoke constrained state writing only at sparse marker\-triggered events\. To understand whether this design improves the cost–fidelity tradeoff, we compare our simulator against three alternatives: \(i\) aStep\-wise LLMsimulator that queries an LLM for every transition, \(ii\) aDeterministic\-onlysimulator that never performs backend writes, and \(iii\) anUnconstrained Marker LLMsimulator that invokes an LLM only at markers but does not validate the proposed state deltas against marker schemas and invariants\.

Instead of reporting a separate table and a separate Pareto plot, Fig\.[11](https://arxiv.org/html/2608.21898#A3.F11)summarizes the full comparison in one figure\. The left panel reports the mean and 95% confidence interval for six metrics: average LLM calls per episode \(LLM Calls\), token usage per episode \(Tokens\), end\-to\-end episode latency \(Latency\), state fidelity to the reference execution \(State Fidelity\), state\-invariant violation rate after writes \(State Viol\.\), and rollout throughput \(Throughput\)\. The right panel visualizes the rollout\-level Pareto tradeoff between token cost and state fidelity, where faint points show individual rollout\-batch observations and large markers show mean performance with 95% confidence intervals\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/rq4_simulation_tradeoff.png)Figure 11:Cost–fidelity tradeoff of simulators\.Left:metric summary matrix\. Each cell reports the mean and 95% confidence interval over rollout batches; color indicates metric\-wise degradation after accounting for whether higher or lower is better\.Right:rollout\-level Pareto plot of token cost and state fidelity\. Faint points denote individual rollout\-batch observations; large markers denote simulator means with 95% confidence intervals, and marker size is proportional to rollout throughput\. Our event\-driven simulator lies near the practical Pareto frontier: it preserves fidelity close to step\-wise LLM simulation while using far fewer tokens and achieving much higher throughput\.Figure[11](https://arxiv.org/html/2608.21898#A3.F11)shows that the step\-wise LLM simulator achieves the highest state fidelity \(97\.1%97\.1\\%\), but at a prohibitive cost: it requires17\.817\.8LLM calls and22\.422\.4K tokens per episode, resulting in the highest latency and the lowest rollout throughput\. At the other extreme, the deterministic\-only simulator is extremely cheap and fast, but its fidelity drops to71\.5%71\.5\\%, indicating that removing backend writes entirely makes the environment too unrealistic for stateful web interaction\.

The unconstrained marker simulator improves efficiency by reducing the number of LLM calls to2\.32\.3and the token cost to3\.63\.6K, but its lack of validation leads to a sharp increase in state violations \(10\.7%10\.7\\%\) and substantially lower fidelity \(88\.2%88\.2\\%\)\. Our event\-driven simulator achieves a better balance\. Compared with step\-wise LLM simulation, it reduces token usage by82\.6%82\.6\\%\(from22\.422\.4K to3\.93\.9K\) while preserving nearly the same fidelity \(96\.3%96\.3\\%vs\.97\.1%97\.1\\%\), and improves rollout throughput by about8\.7×8\.7\\times\(from210210to18201820episodes per hour\)\. Compared with the unconstrained marker simulator, our method retains a similar call budget but improves fidelity by8\.18\.1points and reduces state violations by more than3\.8×3\.8\\times\.

These results suggest that sparse marker triggering alone is not sufficient\. The key benefit comes from combining*event\-driven invocation*with*state\-safe validation*: the former removes unnecessary per\-step generation cost, while the latter prevents low\-cost simulation from drifting away from faithful backend dynamics\. This is precisely the regime needed for scalable PPO training in synthetic web environments\.

### C\.3Which defects most harm policy learning?

The previous results show that verification improves environment executability and downstream PPO success\. We next ask a more diagnostic question:*which types of scaffold defects are most harmful for policy learning?*This analysis is important because defect frequency alone may be misleading\. A common semantic defect may be visually noticeable but harmless for learning, whereas a rare feasibility defect can corrupt the reward signal by making a task impossible under any policy\.

##### Setup\.

Starting from verified environments, we construct controlled defect\-mixture variants by reintroducing localized defects into pages, database bindings, markers, and task workflows\. For each variant, we train the same compact PPO policy under identical hyperparameters and measure the drop in held\-out success rate relative to the fully verified environment:

Δ​SR​\(d\)=SRverified−SRd,\\Delta\\mathrm\{SR\}\(d\)=\\mathrm\{SR\}\_\{\\mathrm\{verified\}\}\-\\mathrm\{SR\}\_\{d\},wheredddenotes a defect subtype\. For each subtype, we also measure its occurrence frequency, task\-blocking rate, affected task fraction, and marker\-write rejection rate\. This produces a defect\-level impact profile that connects environment errors to downstream learning degradation\.

Figure 12:Defect impact on policy learning\.Each point denotes one defect subtype measured across domains and random seeds\. Thexx\-axis reports how often the defect occurs in raw scaffolds, while theyy\-axis reports the PPO success\-rate drop after injecting that defect into otherwise verified environments\. Marker size indicates task\-blocking rate and color denotes defect category\. Feasibility and structural defects occupy the upper\-impact region despite being less frequent than semantic defects\. This shows that the most damaging defects are those that invalidate executable workflows or corrupt backend\-grounded progress, rather than those that merely affect surface plausibility\.Figure[12](https://arxiv.org/html/2608.21898#A3.F12)reveals a clear mismatch between defect frequency and learning harm\. Semantic defects are the most frequent in raw scaffolds, but many of them have modest impact on PPO because they do not necessarily prevent state progress\. In contrast, feasibility defects such as missing submit actions, inaccessible forms, and unsatisfiable completion constraints produce the largest success\-rate drops\. Structural defects are also highly damaging when they disconnect required pages or remove navigation paths\. Marker defects occupy a second high\-risk regime: they may not block navigation, but they corrupt backend updates and therefore make dense progress rewards unreliable\.

These results provide a more fine\-grained explanation for the ablation trends in Section[5\.2](https://arxiv.org/html/2608.21898#S5.SS2)\. The feasibility verifier is critical not because feasibility defects are the most common, but because each such defect creates a large amount of misleading negative experience for PPO\. Similarly, marker validation matters because even sparse state\-write errors can poison the reward signal\. Therefore, verification should not be optimized only for reducing the total number of defects; it should prioritize defects with high task\-blocking and reward\-corrupting effects\.

### C\.4Is dense reward aligned with terminal success?

Dense rewards accelerate PPO training, but they are only useful if intermediate progress is aligned with final task completion\. A poorly designed reward may encourage local progress without completing the user instruction, leading to reward hacking\. We therefore evaluate whether our state\-grounded dense reward is statistically calibrated with terminal success\.

##### Setup\.

For each held\-out task, we collect rollouts from partially trained PPO checkpoints and record the final progress potentialΨt​\(sH\)\\Psi\_\{t\}\(s\_\{H\}\), cumulative dense rewardRdenseR\_\{\\mathrm\{dense\}\}, and terminal successCt​\(sH\)C\_\{t\}\(s\_\{H\}\)\. We compare three reward signals:Surface\-Heuristic, which rewards visible UI changes such as clicks and form edits;LLM\-Judge, which asks an LLM to score partial task completion from rendered observations; andState\-Grounded, our reward computed from verified backend predicates\. For each reward, we measure calibration between predicted progress and terminal success, the area under the ROC curve \(AUROC\), Spearman correlation, expected calibration error \(ECE\), and the high\-progress failure rate:

HPF=Pr⁡\(Ct​\(sH\)=0∣Ψt​\(sH\)\>0\.8\)\.\\mathrm\{HPF\}=\\Pr\\bigl\(C\_\{t\}\(s\_\{H\}\)=0\\mid\\Psi\_\{t\}\(s\_\{H\}\)\>0\.8\\bigr\)\.A well\-aligned reward should have high AUROC and Spearman correlation, low ECE, and low high\-progress failure rate\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/dense_reward_alignment.png)Figure 13:Alignment between dense reward and terminal success\.Left:calibration curves between final progress score and empirical terminal success\. A well\-aligned dense reward should lie close to the diagonal\.Middle:success rate by progress decile\. Our state\-grounded progress produces a monotonic success\-lift pattern, whereas surface and LLM\-based rewards assign high progress to many unsuccessful rollouts\.Right:reward\-alignment summary across domains, including AUROC, Spearman correlation, expected calibration error, and high\-progress failure rate\. State\-grounded dense reward is both more predictive and better calibrated with terminal success, indicating that PPO receives intermediate supervision consistent with the true task objective\.Figure[13](https://arxiv.org/html/2608.21898#A3.F13)shows that state\-grounded dense reward is substantially better aligned with terminal success than surface\-level or LLM\-judged alternatives\. The calibration curve of our reward stays close to the diagonal, suggesting that a progress score of0\.70\.7, for example, corresponds to an approximately70%70\\%empirical chance of success\. In contrast,Surface\-Heuristicis over\-optimistic: many trajectories receive high reward for clicking, typing, or navigating, even when backend constraints remain unsatisfied\.LLM\-Judgeimproves over surface heuristics but still overestimates progress in states where the rendered page looks plausible while hidden database fields are incorrect\.

The decile analysis further confirms this trend\. For our state\-grounded reward, terminal success increases almost monotonically with progress deciles, and the top decile has a much higher success rate than the bottom decile\. The high\-progress failure rate is also much lower for our method, showing that the reward is less vulnerable to reward hacking\. These results support the central design choice of compiling task constraints into backend\-state predicates: dense supervision should reward verified state progress, not merely plausible\-looking interaction behavior\.

### C\.5What are the failure modes of learned policies?

Success rate alone does not reveal whether a failed rollout is caused by the policy or by an invalid training environment\. This distinction is crucial for synthetic web\-agent training\. If an episode fails because the scaffold is broken, the task is infeasible, or the backend update is inconsistent, PPO receives misleading negative feedback\. In contrast, if failure is caused by wrong navigation, wrong DOM grounding, or insufficient exploration, the failure is attributable to the learned policy and can be improved through training\.

##### Attribution protocol\.

For each failed rollout, we assign one primary failure label using a deterministic diagnostic order\. First, we check whether the task admits a bounded executable trace under the current scaffold; if not, the failure is labeled asEnvironment Invalidity\. Second, if the rollout triggers a marker\-write rejection or produces a backend invariant violation, it is labeled asState\-Update Violation\. Third, if the rollout reaches high dense progress but fails the terminal constraint, it is labeled asReward Mismatch\. Remaining failures are attributed to the policy:Grounding Errorwhen the policy selects a wrong DOM element or fills a wrong field,Planning Errorwhen it visits valid pages in an invalid order or misses a required subgoal, andTimeout / Explorationwhen the rollout does not make sufficient progress before the horizon limit\.

Formally, for a failed trajectoryτ=\(s0,a0,…,sH\)\\tau=\(s\_\{0\},a\_\{0\},\\ldots,s\_\{H\}\), we assign

Attr\(τ\)=\{Environment Invalidity,∄π1:H′s\.t\.Ct\(sH′\)=1,State\-Update Violation,∑kϵk\>0​or​Inv​\(sH\)=0,Reward Mismatch,Ψt​\(sH\)\>τψ​and​Ct​\(sH\)=0,Grounding Error,∃k:ak∈𝒜⁡\(ok\)​but targets an incorrect DOM element,Planning Error,∃i:ϕt,i​\(sH\)=0​for an unmet required subgoal,Timeout / Exploration,otherwise\.\\mathrm\{Attr\}\(\\tau\)=\\begin\{cases\}\\textsc\{Environment Invalidity\},&\\nexists\\pi\_\{1:H^\{\\prime\}\}\\ \\text\{s\.t\.\}\\ C\_\{t\}\(s\_\{H^\{\\prime\}\}\)=1,\\\\ \\textsc\{State\-Update Violation\},&\\sum\_\{k\}\\epsilon\_\{k\}\>0\\ \\text\{or\}\\ \\mathrm\{Inv\}\(s\_\{H\}\)=0,\\\\ \\textsc\{Reward Mismatch\},&\\Psi\_\{t\}\(s\_\{H\}\)\>\\tau\_\{\\psi\}\\ \\text\{and\}\\ C\_\{t\}\(s\_\{H\}\)=0,\\\\ \\textsc\{Grounding Error\},&\\exists k:a\_\{k\}\\in\\mathcal\{A\}\(o\_\{k\}\)\\ \\text\{but targets an incorrect DOM element\},\\\\ \\textsc\{Planning Error\},&\\exists i:\\phi\_\{t,i\}\(s\_\{H\}\)=0\\ \\text\{for an unmet required subgoal\},\\\\ \\textsc\{Timeout / Exploration\},&\\text\{otherwise\}\.\\end\{cases\}We useτψ=0\.8\\tau\_\{\\psi\}=0\.8in all experiments\.

![Refer to caption](https://arxiv.org/html/2608.21898v1/policy_failure_attribution.png)Figure 14:Policy failure attribution\.Left:outcome decomposition over all evaluated episodes\. Raw synthetic environments contain many environment\-induced failures, making PPO feedback noisy\. Verification sharply reduces environment invalidity and state\-update violations\.Middle:failure attribution conditioned on failed episodes\. After verification, most remaining failures become policy\-attributable planning and grounding errors\.Right:domain\-level residual failures for our full method\. Harder stateful domains such as banking and healthcare retain more planning and grounding failures, suggesting where future policy improvements are needed\.
##### Results\.

Figure[14](https://arxiv.org/html/2608.21898#A3.F14)shows that raw synthetic environments produce a large fraction of non\-policy failures\. In particular,Environment InvalidityandState\-Update Violationdominate the failure distribution when PPO is trained on raw scaffolds\. This indicates that the policy is often penalized for tasks that are not executable or for backend transitions that are not faithfully simulated\. Adding dense rewards to raw environments does not fully solve this problem; it can even introduce additionalReward Mismatchfailures, because progress predicates are unreliable when the underlying scaffold is inconsistent\.

After verification and marker validation, the failure profile changes substantially\. Environment\-induced failures become rare, and most remaining failures are attributable to the policy itself\. The full method therefore produces a cleaner training signal: failed episodes mostly correspond to wrong navigation, wrong element grounding, or insufficient long\-horizon planning\. This shift is important because these are learnable policy errors, whereas broken scaffolds and invalid backend updates are not\. The domain\-level analysis further shows that banking, healthcare, and government tasks retain more residual failures, mainly because they contain longer workflows and more state\-dependent constraints\. These results suggest that verified environments do not merely improve average success rate; they also make failure feedback more interpretable and more useful for policy optimization\.

### C\.6Is executability improvement confirmed by an independent audit?

The feasible\-task metric in the main paper is computed by bounded trace analysis\. Because this analysis is also used during repair, a natural concern is that the reported executability improvement may be partly induced by the verifier itself\. We therefore perform an independent audit using two sources of validation that are not used by the repair loop\.

##### Setup\.

We sample 120 held\-out environments and 720 tasks after applying each environment\-construction method\. We evaluate executability using: \(i\) the internal feasibility verifier used in the main experiments, \(ii\) a held\-out bounded trace analyzer with a separately implemented action enumerator and a different search ordering, and \(iii\) author\-audited replay on a randomly sampled subset of 240 tasks\. The author audit is used only as a sanity check and is not used for model selection, repair, or hyperparameter tuning\. We also report the false\-feasible rate, defined as the percentage of tasks marked feasible by the internal verifier but judged infeasible by both the held\-out analyzer and the author audit\.

Table 6:Independent executability audit\. The feasible\-task improvement is confirmed by a held\-out trace analyzer and author\-audited replay\. The low false\-feasible rate indicates that our main feasible\-task metric is not merely an artifact of the repair\-time verifier\.
##### Analysis\.

The held\-out analyzer and author audit preserve the same method ranking as the internal metric\. Our method achieves92\.9%92\.9\\%held\-out feasible tasks and91\.7%91\.7\\%author\-audited executability, only slightly below the internal94\.8%94\.8\\%estimate\. The false\-feasible rate also drops from12\.4%12\.4\\%for raw environments to2\.3%2\.3\\%for our method\. This suggests that the repair loop does not merely optimize for the internal feasibility checker; it produces workflows that remain executable under an independently implemented analyzer and manual replay\.

### C\.7How reliable are the verifiers and repair operators?

The verification stage is useful only if detected defects correspond to real environment errors and repairs do not introduce new inconsistencies\. We therefore evaluate verifier reliability and repair reliability on an audited defect set\.

##### Setup\.

We sample 80 raw environments and construct an audited defect set by manually checking page graphs, database bindings, markers, and task workflows\. The audit contains 1,286 labeled defects across symbolic, structural, semantic, consistency, feasibility, and marker categories\. We evaluate each verification method by precision, recall, and F1 against this audited set\. For accepted defects, we additionally measure repair success rate, defined as the fraction of repairs that remove the target defect without creating another critical defect, and false repair rate, defined as the fraction of repairs applied to audit\-negative defect reports\.

Table 7:Verifier and repair reliability on an audited defect set\. Rule\-based checking is high precision but low recall\. Single\-pass LLM verification detects more defects but also produces more false repairs\. Our coordinated verifier improves recall while keeping precision high and false repairs low\.Table 8:Category\-level reliability of our verifier\. Feasibility defects have slightly lower precision but higher recall, which is desirable because missed feasibility defects are especially harmful for policy learning\.
##### Analysis\.

The results explain why simple rule\-based checking is insufficient: it rarely hallucinates defects, but it misses many semantic, consistency, and feasibility failures\. Single\-LLM verification improves recall but has a higher false repair rate, which can introduce unnecessary edits to otherwise valid scaffold components\. Our method obtains the best F1 and repair success rate because defect\-triggered coordination asks only the relevant verifier to re\-check downstream effects, while priority\-weighted repair scheduling avoids repairing low\-confidence isolated reports before high\-impact dependencies are resolved\. The category\-level results also support the design emphasis on feasibility and marker validation: these categories are detected with high recall and repaired with high success, reducing the chance that PPO receives misleading feedback from impossible tasks or invalid backend updates\.

### C\.8Are the gains due to a larger LLM verification budget?

Our verification pipeline uses LLM\-based semantic verifiers, so a natural question is whether its advantage comes from better coordination or simply from a larger LLM budget\. We therefore compare verification methods under measured LLM\-call and token budgets\. We also include anOurs\-Token\-Matchedvariant that uses the same average token budget as the Single\-LLM verifier by running only one targeted coordination round and disabling optional low\-severity re\-checks\.

Table 9:LLM\-budget comparison for environment verification\. Our full method uses fewer tokens and less curation time than self\-consistency and AutoGen while achieving higher executability\. Even when matched to the Single\-LLM token budget, our targeted coordination substantially improves feasible\-task rate, suggesting that the gain is not merely due to spending more LLM calls\.##### Analysis\.

Self\-consistency spends the largest token budget because it repeatedly queries independent verifiers, but it does not explicitly route downstream checks to the defect categories most likely to be affected\. AutoGen improves over self\-consistency but remains more expensive than our full method\. In contrast, our method uses targeted coordination and dependency\-aware repair scheduling, which reduces redundant re\-checks\. TheOurs\-Token\-Matchedvariant is particularly informative: with nearly the same token budget as Single\-LLM, it improves feasible\-task rate from70\.4%70\.4\\%to87\.4%87\.4\\%\. This indicates that the main benefit comes from structured verifier coordination and repair scheduling, rather than from a larger LLM budget\.

### C\.9Qualitative raw\-to\-verified case study

We provide a representative example to illustrate how scaffold verification changes the learning signal\. The raw environment is an e\-commerce website with the task: “Buy a wireless mouse under $30 and place the order\.” The raw pages look plausible, but the workflow is not executable because multiple scaffold components disagree\.

Table 10:Representative raw\-to\-verified repair example\. The raw scaffold contains multiple locally plausible but globally task\-blocking defects\. Verification and repair convert the same task into an executable workflow with backend\-grounded progress predicates\.After repair, the shortest verified trace is:

Home→SearchResults→ProductDetail→Cart→Checkout→Confirmation\.\\texttt\{Home\}\\rightarrow\\texttt\{SearchResults\}\\rightarrow\\texttt\{ProductDetail\}\\rightarrow\\texttt\{Cart\}\\rightarrow\\texttt\{Checkout\}\\rightarrow\\texttt\{Confirmation\}\.The corresponding progress predicates check whether the target product has been visited, whether its canonical price satisfies the task constraint, whether the correct entity has been inserted intocart\.items, whether the checkout form is valid, and whether the order state is updated toplaced\. In the raw environment, PPO failures on this task are not attributable to the policy because no policy can satisfy the completion constraint\. In the verified environment, failed rollouts are attributable to policy errors such as selecting the wrong product, omitting checkout, or timing out before submitting the order\.

## Appendix DLimitations

The event\-driven simulator reduces cost by invoking constrained state writing only at marker\-triggered operations\. This is effective when persistent state updates are sparse, as observed in our diagnostic study, but may be less efficient for applications where nearly every interaction changes backend state\.

## Appendix EBroader Impacts and Safeguards

This work may have positive impacts by making web\-agent training more reproducible, auditable, and less dependent on brittle live websites or expensive manual environment construction\. Verified synthetic environments can help researchers distinguish policy failures from environment invalidity and can reduce unnecessary LLM calls during evaluation\.

The same capability also has possible risks\. More capable web agents could be misused for spam, unauthorized automation, credential abuse, synthetic phishing workflows, or other harmful web\-scale actions if trained or deployed without safeguards\.

We can mitigate these risks in several ways\. The proposed environments are sandboxed and use synthetic data rather than real user records\. Persistent state changes are constrained by marker schemas, database invariants, and programmatic task constraints\.

## Appendix FDeclaration of LLM Usage

LLMs are used to generate raw synthetic web scaffolds from domain\-level site specifications, to support semantic verification of generated content and workflows, and to propose constrained state deltas for marker\-triggered backend updates during synthetic training rollouts\.

In addition, LLMs are mainly used to help check for grammatical errors in writing\.