Agent Learning via Early Experience

TL;DR

Today’s LLM agents are mostly trained by copying expert demonstrations (supervised fine-tuning / imitation learning). That’s brittle: the agent only ever sees the “golden path” and never learns what happens when it screws up. The clean fix — reinforcement learning — is blocked in most real environments because there’s no reliable reward signal (a website doesn’t tell you “you filled the form wrong”). This paper proposes a middle ground called early experience: at each expert state, the agent proposes its own alternative actions, executes them, and records the resulting next states. Those next states are free, reward-free supervision. They study two ways to use that data — Implicit World Modeling (predict the next state) and Self-Reflection (explain why the expert action beat your alternative) — and show consistent wins over imitation learning across eight environments and three model sizes (3B/7B/8B, plus 70B), with gains up to +18 points. Crucially, when reward-based RL does become available, models warm-started with early experience reach higher final ceilings than imitation-only starts.

Problem & Motivation

The pain in one sentence: we can’t train agents the way we’d like (RL) because real environments rarely give usable rewards, so we fall back on copying experts — which teaches agents nothing about their own mistakes.

Unpack that:

• RL needs a reward. AlphaGo-style success came from environments with crisp, verifiable rewards (you won the Go game or you didn’t). Most agent environments aren’t like that. A web form may look submitted but you have no ground-truth signal that each field was right. Multi-turn tool use has long horizons with delayed, ambiguous outcomes, so credit assignment is a nightmare and training is unstable. On top of that, the infrastructure (simulators, reset mechanisms, scalable evaluators) mostly doesn’t exist yet.
• So everyone uses SFT / imitation learning. You collect expert trajectories (state, expert_action) and train the model to reproduce the expert action. It’s cheap and stable. But it has three structural problems:
  1. No consequence awareness. The agent never observes what happens when it deviates. It memorizes the golden path.
  2. Distribution shift / compounding error. At deployment the policy inevitably drifts off the expert path into states it never trained on, and errors snowball (the classic DAgger/behavior-cloning failure mode).
  3. Expert data doesn’t scale. High-quality human demonstrations are expensive, narrow, and cap the agent at the imagination of whoever wrote them.

The authors frame this as three eras (their Figure 1): Era of Human Data (imitation, reward-free but not scalable) → Early Experience (their middle ground, scalable and reward-free) → Era of Experience (full RL, scalable but needs rewards). Early experience is the bridge you can build today, before your environment has rewards.

What’s New (Core Contribution)

1. The early-experience paradigm itself. Before: supervision was either human expert actions (imitation) or environment rewards (RL). Now: supervision comes from the future states caused by the agent’s own non-expert actions — reward-free, but grounded in what the environment actually did. This is the conceptual move. The agent generates its own data and the environment’s reaction is the label.
2. Implicit World Modeling (IWM) as an auxiliary objective on the policy itself. Before: world models were separate simulators bolted onto a planning pipeline. Now: the same policy network is trained to predict next states s' | (s, a) as a next-token task, internalizing environment dynamics without a standalone simulator. It’s a warm-up that grounds the policy in how the world responds.
3. Self-Reflection (SR) trained on grounded contrasts. Before: reflection (Reflexion, Self-Refine) was an inference-time prompting trick, or STaR-style rationales that were never tested against reality. Now: the model writes a chain-of-thought explaining why the expert action beat a specific alternative, given the actual observed next states of both, then trains on (reflection + expert action). The rationale is grounded in real outcomes, not hallucinated.
4. Empirical demonstration that early experience is a strong RL warm-start. Before: nobody had shown a reward-free pre-stage that measurably raises the post-RL ceiling. Now: across WebShop / ALFWorld / SearchQA, GRPO from an early-experience checkpoint beats GRPO from an imitation checkpoint, and the gap often widens during RL.

How It Works (Technically)

The shared data-construction step (this is the whole trick)

Start from a normal expert dataset D_expert = {(s_i, a_i)}. For each expert state s_i:

1. Sample K alternative actions {a_i^1, ..., a_i^K} from the current policy (the off-the-shelf instruct model). These are deliberately not the expert action.
2. Execute each alternative in the environment to get the resulting next state s_i^j ~ T(s_i, a_i^j). T is the transition function — i.e., you actually click the button and read the new DOM, error message, or tool output.
3. Collect D_rollout = {(s_i, a_i^j, s_i^j)}. In practice this is ~an order of magnitude larger than D_expert because you generate K alternatives per state.

No reward is ever queried. The supervision lives entirely in the next states s_i^j — the environment’s honest reaction to a non-expert move.

Then the two methods diverge on how they consume D_rollout.

Method 1 — Implicit World Modeling (IWM)

The objective (their Eq. 3) is simply next-state prediction:

L_IWM = − Σ log p_θ(s_i^j | s_i, a_i^j)

In plain English: feed the model the state and the action it took, and train it to predict the text of the resulting next state. Because everything is natural language, “predict the next state” is just ordinary next-token prediction — no special architecture. The key design choice: same parameters θ for both world-modeling and the policy. So the act of learning “if I enter an invalid date, the page shows this error” lives in the same weights that later decide what to click. The model internalizes coarse dynamics — common transitions, side effects, what invalid actions do.

Pipeline: train one epoch on L_IWM to absorb dynamics, then fine-tune on D_expert (standard imitation loss L_IL = −Σ log π_θ(a_i | s_i)). Total update budget is held equal to the imitation baseline — so the gains aren’t from “more training,” they’re from what the model trained on.

Method 2 — Self-Reflection (SR)

For each state, execute the expert action a_i (→ s_{i+1}) and the alternatives a_i^j (→ s_i^j). Then prompt an LLM: “Here’s the situation, the expert action and its outcome, and these alternatives and their outcomes. Explain why the expert action is better.” That produces a grounded chain-of-thought c_i^j.

The objective (their Eq. 4) trains the policy to jointly emit the reflection and the expert action:

L_SR = − Σ log p_θ(c_i^j, a_i | s_i)

In plain English: condition only on the state, and train the model to first reason (the contrastive explanation) and then output the expert action. At inference the model produces that reasoning itself before acting. The reflections are mixed with the original D_expert and trained with one standard next-token loss.

Why this generalizes: the worked example from the paper — in WebShop, expert clicks “$15 blue shirt,” alternative is “$30 red shirt.” The reflection says “the red shirt matches the color but exceeds the $20 budget; the blue shirt satisfies both style and budget.” That teaches “prioritize the budget constraint,” a transferable decision principle, not a memorized click.

One concrete trace

Task: book a flight. State s = the booking page. Expert action = “select valid return date.” Policy proposes alternative a^j = “enter a past date.” Execute it → next state s^j = page now shows “Error: return date must be after departure.”

• IWM trains: given (page, “enter past date”) → predict that error text. The policy now knows past dates error out.
• SR trains: given the page → generate “a past return date triggers a validation error and wastes a step; the valid date advances the booking” → then output the valid-date action.

Same raw rollout, two different lessons extracted.

Architecture & data flow

flowchart TD
  E[Expert trajectories<br/>s_i, a_i] --> S[For each state s_i]
  P[Initial policy LLM] -->|sample K alt actions| S
  S --> X[Execute alternatives a_i^j<br/>in the ENVIRONMENT]
  X -->|transition T| R[Rollout data<br/>s_i, a_i^j, s_i^j]
  R --> IWM[IWM objective:<br/>predict next state s_i^j]
  R --> SR[Reflection: LLM explains<br/>why expert beat alternative]
  SR --> SRT[SR objective:<br/>predict reflection + expert action]
  IWM --> POL[Single policy θ]
  SRT --> POL
  EXP2[Then fine-tune on expert D_expert] --> POL
  POL --> RL[Optional: GRPO when rewards exist<br/>higher ceiling]

Schematic of the early-experience data-construction step: hover the expert state to fan out K alternative actions, each leading to its own next state. Those next states (green = informative environment reactions) are the free, reward-free supervision the two methods consume.

The algorithm, simplified

# Early experience: turn one expert dataset into grounded, reward-free training data.
# llm(prompt) -> str ; env.step(state, action) -> next_state (the real environment reaction)

def build_early_experience(expert_pairs, policy, env, K=4):
    rollout, refl = [], []
    for s, expert_a in expert_pairs:
        s_expert_next = env.step(s, expert_a)          # what the GOLDEN path produces
        for _ in range(K):
            alt_a = policy.sample_action(s)            # the agent proposes its OWN move
            if alt_a == expert_a:
                continue                               # we want NON-expert actions
            s_alt_next = env.step(s, alt_a)            # environment reacts -> free label
            rollout.append((s, alt_a, s_alt_next))     # IWM target: predict s_alt_next

            # SR target: a grounded contrast, not a hallucinated rationale
            c = llm(f"Expert did {expert_a} -> {s_expert_next}. "
                    f"You did {alt_a} -> {s_alt_next}. Why is the expert action better?")
            refl.append((s, c, expert_a))
    return rollout, refl

# IWM loss: next-state prediction (same weights as the policy)
def iwm_loss(model, rollout):
    return -sum(model.logprob(s_next, given=(s, a)) for (s, a, s_next) in rollout)

# SR loss: emit reflection THEN expert action, conditioned only on the state
def sr_loss(model, refl):
    return -sum(model.logprob(seq=(c, a), given=s) for (s, c, a) in refl)

Built on Prior Work

Results & Evidence

Setup: 8 environments (ALFWorld, ScienceWorld, TravelPlanner, BFCLv3, Tau-Bench, SearchQA, WebShop, WebArena-Lite) spanning embodied, scientific, planning, multi-turn tool use, and web. Models: Llama-3.2-3B, Qwen-2.5-7B, Llama-3.1-8B (and a 70B scale study). Training budget held equal to the imitation baseline. At most 8×H100.

Headline numbers (success rate, gain over imitation learning):

• WebShop: IWM up to +18.4, SR up to +11.3 (e.g., 41.8 → 60.2).
• TravelPlanner: SR +12.8 to +15.0 (constraint-heavy long-horizon planning is where reflection shines).
• ScienceWorld: SR +13.3; IWM steady +2.3 to +5.5.
• BFCLv3: SR +8.0 on the 3B model.
• Tau-Bench: SR +4.4 to +5.8.
• Harder/open action spaces (WebArena +1.2 to +3.6; SearchQA +0.6 to +3.3) — still positive but smaller.

The pattern that matters: IWM wins when dynamics are stable and predictable (structured simulators, transactional sites). SR wins when failures are reasoning/constraint errors (planning, multi-domain APIs). This is a usable heuristic, not noise.

Out-of-domain: gains persist and sometimes exceed in-domain gains (notably SearchQA, ALFWorld) — strong evidence the supervision generalizes beyond the demonstration distribution rather than overfitting.

RL bridge (the strongest result): Under identical GRPO recipes on WebShop/ALFWorld/SearchQA, early-experience starts reach higher final performance than imitation starts; on ALFWorld the gap widens during RL. GRPO from the raw pretrained model (no SFT stage) performs worst and trains unstably.

Data efficiency & scale: Early experience matches imitation performance with half or less the expert data, and the advantage holds up to 70B (and under LoRA-only updates).

Honest baselines (Table 4, Llama-3.1-8B): This is the part that earns trust. Two cheaper alternatives were tried and failed:

• Long CoT (test-time scaling): forcing longer reasoning on imitation-trained models collapsed performance (WebShop 47.3 → 0.0; ALFWorld 80.5 → 25.8) — models fine-tuned only on rationale-free expert data can’t sustain coherent long chains.
• STaR-style ungrounded rationales: low expert-match rate left little data, and the kept rationales hallucinated tools/facts, degrading results (WebShop 47.3 → 25.0).

Caveats / what it does NOT establish:

• All models are small-to-mid (3B–8B headline; 70B only a scale sweep). No frontier-model results.
• Environments are mostly simulators or gyms — clean transition functions that you can actually env.step() cheaply. Real production websites with no reset, rate limits, and side effects are harder.
• Short-horizon only — the authors explicitly flag long-horizon credit assignment as unsolved. The “consequences” are one step deep.
• SR depends on an LLM to write good reflections; reflection quality and cost aren’t deeply ablated.
• Gains in the hardest open-action regimes (WebArena) are small.

How You’d Use It

This is unusually well-suited to an AI-services shop, because it manufactures training data from environments you already operate without needing to build a reward function or RL infra.

• Agent fine-tuning offering, without rewards. When a client has a sandbox/staging environment (an internal tool, a test instance of their app, an API simulator) but no labeled “good vs bad” signal, you can still improve their agent. Collect a modest set of expert trajectories, then fan out alternative actions and harvest next states. You’re selling “we made your agent 10–18 points better and more robust to edge cases” using data you generated.
• Robustness / edge-case hardening. The whole value is the agent learning what failure looks like. For a customer-service or form-filling agent (cf. Tau-Bench, WebShop), SR-style grounded reflections directly attack the “agent confidently does the wrong thing off the golden path” problem clients complain about.
• A staged roadmap with a client. Phase 1: imitation (you have today). Phase 2: early experience (reward-free, cheap, ships now). Phase 3: GRPO once you’ve built reward/eval infra. The paper shows Phase 2 raises the ceiling of Phase 3 — so it’s not throwaway work.
• In a multi-agent system (your ARC MAS world): use one agent as the “explorer” that proposes alternatives and a critic/LLM to generate reflections, then distill into the worker policy. The data-construction loop maps cleanly onto a producer/critic/learner role split.
• Data efficiency as a sales point: matching imitation quality with half the expert data means less expensive human annotation for the client — a concrete cost argument.

Build Your Own (Minimal Recipe)

Smallest version that captures ~80% of the value (do Self-Reflection first — it gave the biggest jumps and needs no architecture changes):

1. Pick an environment you can step() cheaply and deterministically-ish. A gym wrapper around a tool API, a sandboxed web app, or something like WebShop/ALFWorld. This is the one genuinely hard prerequisite — you need to execute non-expert actions and read the result.
2. Collect a small expert set (state, expert_action) — even a few hundred to a few thousand pairs.
3. Generate K alternatives per state from your base instruct model (K≈4), drop any that equal the expert action, and execute them to capture next states.
4. Self-Reflection data: prompt a capable LLM with the expert action+outcome and each alternative+outcome to write the contrastive “why expert is better” rationale (use their prompt template). Store (state, reflection, expert_action).
5. Train with standard SFT next-token loss on the concatenation reflection + expert_action, mixed with your expert set. Any HF transformers + trl/peft (LoRA works per the paper) stack does it.
6. Add IWM if dynamics matter: one epoch predicting next_state | (state, action) on the rollout data, then fine-tune on experts — keeping total steps equal to your imitation baseline so you’re measuring the method, not extra compute.
7. (Later) GRPO once you have any verifiable reward, starting from the early-experience checkpoint.

The two hard parts: (a) the executable environment / reset mechanism, and (b) reflection quality — bad rationales add noise, so spot-check and constrain the prompt to stay grounded in the provided states.

How to Improve It

1. Multi-step / long-horizon consequences. Current rollouts are one step deep. Extend to short sequences of alternative actions and predict/reflect over the mini-trajectory — attacks the credit-assignment limitation the authors admit. Testable: measure gains on TravelPlanner vs. depth-1 SR.
2. Value-weight the alternatives without rewards. Use the world model’s own surprise (high next-state prediction loss) or a learned discriminator to prioritize informative alternatives instead of uniform K sampling. Should improve data efficiency further.
3. Self-consistency on reflections. Generate several reflections per contrast and keep only those that agree or that the policy can act on correctly — a grounded analog of STaR’s filter, fixing SR’s dependence on a single (possibly wrong) rationale.
4. Combine IWM + SR explicitly. The paper studies them separately; a joint objective (predict next state and reflect) on shared weights might compound — IWM grounds dynamics, SR grounds decisions.
5. Cross-environment transfer. Train early experience on several environments and test zero-shot on a held-out one. The OOD results hint this should work and would be a strong “general agent prior” claim — and a differentiated services offering.
6. On-policy / continual loop. Re-run data construction with the improved policy (DAgger-style) so alternatives reflect current failure modes, then iterate — closing the gap toward full experience-driven learning.

Glossary

• Imitation learning / SFT / behavior cloning — train the model to copy expert (state → action) pairs; reward-free but blind to consequences.
• Reinforcement learning (RL) — train by maximizing expected cumulative reward from the environment; needs a usable reward signal.
• Reward-free supervision — learning signal that comes from observed outcomes (next states) rather than a numeric reward.
• Transition function T(s, a) — the environment’s rule for “given state s and action a, what’s the next state.” Here, executing an action and reading the result.
• MDP — Markov Decision Process; the formal (states, actions, transitions, reward, discount) tuple for sequential decision problems.
• Policy π_θ — the agent’s mapping from state to an action distribution; the thing being trained (the model weights θ).
• Distribution shift — at deployment the agent drifts into states absent from training data, where imitation-trained models break.
• World model — a learned model of environment dynamics; here it’s implicit, folded into the policy as a next-state-prediction task instead of a separate simulator.
• Chain-of-thought (CoT) — intermediate reasoning text the model generates before its answer/action.
• Self-reflection (here) — a grounded CoT explaining why the expert action beat a tried alternative, used as a training target.
• STaR — prior method that bootstraps reasoning by keeping self-generated rationales that lead to correct answers (ungrounded in environment outcomes).
• GRPO — Group Relative Policy Optimization; an RL algorithm that compares a group of sampled outputs to compute relative advantages (no separate value network), used for the downstream RL stage.
• OOD (out-of-domain) — test conditions not seen in training (new tools, arguments, retrieval distributions); a robustness test.
• LoRA — Low-Rank Adaptation; parameter-efficient fine-tuning that updates small adapter matrices instead of all weights.