BAGEL: Bootstrapping Agents by Guiding Exploration with Language

1. Introduction

• Digital environments have ambiguous dynamics, so an agent may need to type a date or use a complex date picker without knowing the website in advance.Human demonstrations can supply this knowledge, but collecting them for every environment is laborious and requires anticipating possible instructions.Source: §1 · p. 1
• Unlike settings where an agent already understands environment dynamics, zero-shot digital agents typically encounter those dynamics only when asked to follow instructions.Prior synthetic-demonstration work retroactively labeled trajectories from embodied agents whose environment dynamics were assumed to be understood.Source: §1 · pp. 1–2
• BAGEL iteratively relabels trajectories with synthetic instructions and uses a zero-shot policy to refine them into demonstrations, which are retrieved as in-context examples at test time.A prompted LM filters instruction–trajectory pairs; demonstrations can also be used for fine-tuning.Source: §1 · p. 2
• BAGEL improves the base LM policy by over 13% on MiniWoB++ and 2% on ToolQA, with up to 13× fewer execution failures.The authors attribute the reduction in execution failures to better understanding of environment dynamics.Source: §1 · p. 2

2. Background

• The full interaction is represented as a trajectory alternating observations and actions, ending with the final observation.The notation is τ = {o1, a1, o2, …, oT, aT, oT+1}.Source: §2 · p. 2
• An agent is a language-conditioned policy that selects actions from the interaction history so far and a natural-language instruction.The history contains prior observations and actions.Source: §2 · p. 2
• An environment-specific low-level controller maps generated action strings to executable commands, such as web-driver actions or API calls.Source: §2 · p. 2

3.2. Generating Demonstrations

• BAGEL alternates trajectory exploration, instruction labeling, and instruction-conditioned trajectory generation, then adds pairs that pass a filter to its demonstration set.It can begin from an unconditioned trajectory or a sampled instruction.Source: Figure 2 · p. 3, §3.2 · pp. 3–4

3.1. Model Components

• The component prompts provide unconditioned exploration, trajectory-to-instruction labeling, instruction-conditioned action generation, binary demonstration filtering, and optional instruction generation.Every component uses the same underlying language model with different prompts.Source: §3.1 · p. 3
• An instruction generator can initialize exploration by sampling plausible instructions from the initial observation and action space.Source: §3.1 · p. 3

3.2. Generating Demonstrations

• Iterative refinement seeks instruction–trajectory pairs that satisfy the instruction without sacrificing the diversity of the initial exploration, stopping when a pair passes the filter or the step limit is reached.Source: §3.2 · p. 4

3.3. Discussion

• Each round shapes the previous trajectory distribution toward trajectories that can be assigned a feasible instruction and executed under valid environment dynamics.The paper contrasts BAGEL with HER: BAGEL relabels using the full trajectory and iteratively reduces noise, whereas HER replaces a goal to create positive examples for policy updates.Source: §3.3 · p. 4

4. Inference

• At test time, the agent receives the top-k demonstrations most relevant to the test instruction, prepended to its context as in-context examples.Source: §4 · p. 4
• A T5-XXL dual encoder embeds each demonstration instruction and the test instruction, ranking demonstrations by embedding dot product.Source: §4 · p. 4
• The paper adapts agents through retrieval-augmented in-context learning and leaves fine-tuning for future work.Source: §4 · p. 4

5.1. MiniWoB++

• MiniWoB++ comprises web interfaces with shared mouse and keyboard actions, evaluated on the 10 hardest of 55 tasks across 50 random seeds.The hardest tasks are selected because the zero-shot agent has average reward below 0.95; raw reward is mapped from [-1, 1] to [0, 1].Source: §5.1 · pp. 4–5
• BAGEL demonstrations improve results on both datasets against a zero-shot ReAct baseline without synthetic demonstrations.Figure 3 reports mean reward for MiniWoB++ and F1 score for ToolQA.Source: Figure 3 · p. 5

5.2. ToolQA

• ToolQA evaluates question answering across eight domains by chaining calls to tools such as databases, SQL interpreters, calculators, and text retrievers.Performance is measured by F1 against ground-truth answers.Source: §5.2 · p. 5

6.1. Baselines and Ablations

• The zero-shot baseline uses the base policy directly at test time, while non-iterative variants generate demonstrations through sample-and-filter procedures.Trajectory-first labels explored trajectories; instruction-first generates instructions from the initial observation, then creates and filters trajectories.Source: §6.1 · p. 5

6.2. Implementation Details

• Exploration starts from 60 trajectories or synthetic goals for MiniWoB++, and 200 for ToolQA, depending on the BAGEL variant.Trajectory-first samples trajectories; instruction-first samples synthetic goals.Source: §6.2 · p. 5
• Experiments use instruction-tuned PaLM-2 at temperature 1.0, with maximum episode length T=15 and T_iter=5 for iterative BAGEL.The iteration count is fixed to remain zero-shot rather than tuned on a development set.Source: §6.2 · p. 5
• When an action raises an exception, the agent resamples with the error in context until it produces a syntactically correct action or reaches five failed steps.Episodes terminate if the agent cannot correct the action within m=5 steps.Source: §6.2 · pp. 5–6
• Table 1 ablations report that multiple relabeling iterations improve performance for both instruction-first and trajectory-first variants.The caption describes the comparison as the effect of multiple rounds of relabeling.Source: Table 1 · p. 6

7. Main Results

• Over 13% points on MiniWoB++ and over 2% on ToolQA are the best BAGEL variant’s improvements over the zero-shot agent.On MiniWoB++, gains reach 20% absolute on choose-date, tic-tac-toe, and use-autocomplete; trajectory-first significantly outperforms instruction-first, which the authors hypothesize reflects a misaligned LM prior.Source: §7 · p. 6
• 4–8% average reward on MiniWoB++ and 1.3–4.5% on ToolQA are the improvements from multiple round trips over non-iterative baselines.The reported iterative relabeling improvement holds across the compared variants.Source: §7 · p. 6

8.1. In-context Learning with Synthetic Demonstrations

• Ours improves performance by a further 0.8% over Shuffled, while Shuffled already improves over the zero-shot baseline.The authors suggest valid action examples provide some benefit, with instruction–trajectory pairing adding conditional signal.Source: Table 2 · p. 6, §8.1 · p. 6

8.2. Synthetic demonstrations reduce execution failures

• BAGEL reduces average execution failures on MiniWoB++ and ToolQA, with fewer resampling calls leading to faster inference.Resampling retries invalid actions using the environment’s error message and can require multiple LM calls.Source: Table 3 · p. 6, §8.2 · pp. 6–7

8.3. Correctness of Synthetic Demonstrations

• Filtering demonstrations that fail to achieve their instructions improves performance by 7% absolute on all 10 MiniWoB++ tasks.The authors manually verify demonstration correctness before filtering.Source: §8.3 · p. 7

8.4. Diversity of Synthetic Demonstrations

• Demonstrations span semantic categories but skew toward modes such as graph-tool use in ToolQA and starring in email, with a long tail of use cases.The authors identify improving diversity during exploration as a remaining failure mode.Source: §8.4 · p. 7, Figure 4 · p. 7

8.5. Error Analysis

• Error analysis identifies long-horizon planning, seed-diversity mismatch, and test-instruction mismatch as remaining challenges.On book-flight, BAGEL raises average reward from 5% to 15%; SciRex still yields no correct answers, and search-engine improves only 5%.Source: §8.5 · p. 7

• Instruction-following digital-agent work commonly relies on expert demonstrations and appropriately shaped rewards, whereas this paper assumes neither and bootstraps synthetic demonstrations.Source: §9 · pp. 7–8
• BAGEL uses synthetic demonstrations to adapt LM agents without human supervision or reward, and bootstraps a learning signal without reinforcement learning.Source: §9 · p. 8
• Unlike self-training approaches that may filter LM-generated data with external verifiers, BAGEL treats environment interactions as a critical part of its learning signal and uses no external verifier.Source: §9 · p. 8

• BAGEL demonstrations used as in-context exemplars improved results by 2–13% and significantly reduced execution failures across two domains.Source: §10 · p. 9

• Models were evaluated only in offline environments, so online deployment risks remain outside the evaluated setting.Source: Impact Statement · p. 9
• The authors identify potential online harms such as terms-of-service violations and call for behavior constraints and secure-deployment work on spam detection and privacy.Source: Impact Statement · p. 9

A.1. Retriever

• The retriever mean-pools T5-XXL word embeddings for each instruction, then returns the three demonstrations with the highest cosine similarity to the test instruction.Source: §A.1 · p. 12

A.2. Re-sampling action strings

• When a low-level controller raises an exception, its message is passed to the LM policy, which resamples a valid action until success or a maximum of five tries.The resampling prompt asks the model to consider the cause of the error before choosing a different action.Source: §A.2 · p. 12

B.1. MiniWoB++

• MiniWoB++'s listed action space includes clicking or hovering over elements matching descriptions, typing a single character or all words of text into matching elements, and clearing previously typed text from an element.The trajectory relabeler is given initial and final webpages as HTML, plus summaries of each subtask's changes to the starting HTML. The demonstration filter scores task execution from 1 to 5; a score of 5 requires perfect completion and a final webpage with no errors.Source: §B.1 · pp. 12–14

B.2. ToolQA

• The listed actions include database filtering with comma-separated conditions, DBLP graph operations, SQLite queries, Python execution whose result must be stored as ans, and a finish action that returns the answer.The trajectory relabeler describes a question answered through tool-using subtasks, each producing tool output. The demonstration filter is given the sequence of tool outputs and attempted subtasks, with the final tool output as the agent’s answer.Source: §B.2 · pp. 14–16

C. Converting LM Action space into API calls

• For MiniWoB++, a prompt converts LM action strings into API calls by using references into the webpage HTML to specify actions on selected elements.The prompt describes four kinds of actions, though the supplied passage does not enumerate them.Source: C. Converting LM Action space into API… · p. 16
• The LM outputs an action, element reference, and text when needed; these are combined into Selenium calls for click, move-mouse, type, or clear.The required output format specifies click/move-mouse/type/clear, an integer element reference, and text only for type.Source: C. Converting LM Action space into API… · p. 16

D. Comparing BAGEL Agents with other Few-shot agents

• BAGEL’s MiniWoB++ agents are compared with Flat Zero-Shot and SteP Zero-Shot from Sodhi et al. (2023) and RCI (Kim et al., 2023), but differing language models make results not entirely comparable.The comparison is presented as a reference; Table 5 gives its scope but the supplied passage does not provide cell values.Source: D. Comparing BAGEL Agents with other… · p. 16, Table 5 · p. 17