STeCa: Step-level Trajectory Calibration for LLM Agent Learning

1 Introduction

• Behavior cloning from successful demonstrations limits proactive self-correction, while terminal-state error signals can miss early deviations that accumulate over long-horizon tasks.Prior work also uses preference and reinforcement learning with explicit error signals or reward functions.Source: §1 · p. 1
• Timely calibration adjusts suboptimal actions as they occur; an early deviation can make subsequent actions drift from the optimal trajectory and increase task-failure risk.The introduction identifies dynamic, diverse environments and a lack of step-level calibration trajectory data as obstacles.Source: §1 · p. 2
• STeCa significantly outperforms existing methods, with higher success rates across varied tasks and more robust handling of long-horizon tasks.The framework reports higher success rates across a variety of tasks.Source: §1 · p. 2
• STeCa uses Monte Carlo sampling to estimate action-level rewards, compares adjacent actions to detect deviations, and uses LLM reflection to revise them and generate reflective thoughts.The revised action and thought, together with a subsequent expert trajectory, form calibrated training data.Source: §1 · p. 2
• Calibrated trajectories are combined with successful exploration trajectories for reinforced training.The framework is designed to improve agent decision-making during task execution.Source: §1 · p. 2

2 Preliminaries

• Agent tasks are formalized as POMDPs with instruction, state, action, observation, transition, and reward elements; instruction, action, and observation spaces are subsets of natural language.The transition function maps state-action pairs to states, and the reward function maps them to values in [0, 1].Source: §2 · p. 2
• An agent acts from its instruction and interaction history, receives observations, and stops when it completes the task or reaches the maximum step; an outcome reward scores the final trajectory.The final trajectory records the instruction and the sequence of actions and observations.Source: §2 · p. 2
• Step-level reward measures an action’s contribution to future success by averaging outcome rewards from Monte Carlo-sampled continuations generated from the current interaction history.The method uses expert trajectories as demonstrations and starts exploration from their states.Source: §2 · pp. 2–3
• Normalized Dynamic Time Warping uses dynamic programming to measure distance between multi-step trajectories, with normalization based on their lengths.The passage describes per-step action distances and defines the normalized distance over [0, 1].Source: §2 · p. 3

3.1 Warm-up via Supervised Fine-tuning

• Supervised fine-tuning on expert trajectories trains a base agent to generate ReAct-style rationales and actions from task interactions.The rationale and corresponding action are represented together as one action unit.Source: §3.1 · p. 4

3.2 Calibration Trajectory Construction

• Step-level rewards approximate task-completion probabilities; STeCa flags an explored action when its reward falls below the preceding expert action’s reward by more than threshold δ.The comparison estimates how an action changes the chance of task completion, accounting for sequential dependencies.Source: §3.2 · p. 4
• An off-the-shelf LLM uses the preceding expert sub-trajectory, deviated action, and ground-truth action to generate a reflective correction and calibrated trajectory.Calibration occurs at the first detected deviation, rather than after exploration ends, and the resulting trajectory is used in reinforced training.Source: §3.2 · pp. 4–5

3.3 Reinforced Training

• Calibration-only training may hinder recognition of correct actions, so STeCa adds independently explored successful trajectories and expert continuations from failed trajectories.The successful explored trajectories can include trial-and-error actions; the expert sub-trajectories provide guidance on challenging cases.Source: §3.3 · p. 5
• Trajectory deviation distance based on nDTW supplies a reward signal, increasing reward with deviation for calibration data but decreasing it for explored-successful trajectories.The rewards are integrated into reinforcement training with policy gradients.Source: §3.3 · p. 5

4.1 Experimental Settings

• Experiments use VirtualHome and ALFWorld, compare prompting- and tuning-based baselines, and measure task success with Average Final Reward.The reported implementation uses Llama-2-7B-Chat as its base model.Source: §4.1 · pp. 5–6

4.2 Main Results

• 70.9 average final reward exceeds IPR’s 68.6 by 3.4%; STeCa also beats E2CL by 4.0% without additional iterative training.Table 1 covers two agent datasets, with seen tasks present during training and unseen task variations held out.Source: Table 1 · p. 6, §4.2 · p. 6
• The SFT+DPO and w/o RT variants achieve average rewards of 70.0 and 69.6, respectively, and neither surpasses STeCa.The first variant trains on optimal and suboptimal trajectories; the second uses only optimal trajectories without reward tuning.Source: §4.2 · pp. 6–7
• On ALFWorld, Table 2 compares SFT, IPR, and STeCa with different base models.Source: Table 2 · p. 7

5.1 Effectiveness with Different Base Models

• Across Mistral-7B and Llama-3-8B-Instruct, STeCa consistently outperforms SFT and IPR on ALFWorld; on unseen Mistral-7B tasks, it improves 17.1% over SFT.Source: §5.1 · p. 7

5.2 Comparisons between Variants of STeCa

• MC sampling for step rewards outperforms alternative acquisition variants, while direct GPT-4o reward annotation performs comparably to STeCa.The comparison suggests step rewards may also be obtained through more computationally efficient approaches.Source: Table 3 · p. 7, §5.2 · p. 7
• Using the base agent to generate reflection thoughts significantly degrades performance, indicating that it lacks effective reflection capabilities.Source: Table 3 · p. 7, §5.2 · p. 7

5.3 Analyses of Deviated Action Detection

• MC step rewards monotonically increase as expert trajectories approach task completion in both environments; deviated actions reduce completion probability.Source: Figure 3 · p. 7, §5.3 · p. 8

5.4 Analyses of Calibration

• 14.8% relative improvement over IPR on unseen VirtualHome tasks; STeCa also varies minimally with deviated actions present versus absent, unlike other methods.Source: §5.4 · p. 8

• LLM agents interact iteratively with environments, but long-horizon planning can make them prone to suboptimal actions and failure.Source: §6 · p. 8
• Prior work improves optimal-action generation, uses preference learning to mitigate suboptimal actions, or explores self-correction after errors occur.Source: §6 · p. 8
• Process-supervision research has not addressed constructing step-level reflection data to detect, explain, and calibrate suboptimal actions.Source: §6 · pp. 8–9

• STeCa is designed to enhance LLM-agent performance on long-horizon tasks.Source: §7 · p. 9
• It identifies deviated actions through step-level reward comparisons and constructs calibration trajectories through reflection.Source: §7 · p. 9
• The calibrated trajectories serve as training data, and experiments report that STeCa outperforms baselines with robust calibration capabilities.Source: §7 · p. 9

• Monte Carlo step-reward construction requires many sampling iterations, creating significant computational overhead.Source: Limitations · p. 9
• STeCa uses step rewards to identify and evaluate deviations but does not fully exploit them for broader decision-making or optimization.Source: Limitations · p. 9
• The framework focuses on immediate correction after a deviated action and does not explicitly address multi-step calibration for multiple deviations.Source: Limitations · p. 9

• The work develops LLM agents in simulated environments and conducts experiments using VirtualHome v2.3.01 and ALFWorld.Source: Ethics Statement · p. 9
• The authors state that fine-tuned models are open-source and that they followed their academic-use licenses, and they acknowledge GitHub Copilot and ChatGPT assistance.Source: Ethics Statement · p. 9

A Datasets and Preprocessing

• ALFWorld provides seen and unseen household-task sets, while VirtualHome contributes filtered executable plans with lengths of 3–20 steps; the datasets are enriched with generated thoughts before actions.The datasets are organized in a thought-action format, and their statistics are summarized in Table 4.Source: A Datasets and Preprocessing · p. 13, Table 4 · p. 13

B Baseline Methods

• Baselines include SFT (Chen et al., 2023), PPO (Schulman et al., 2017), RFT (Yuan et al., 2023), ETO (Song et al., 2024), E2CL (Wang et al., 2024a), and IPR (Xiong et al., 2024).Source: B Baseline Methods · p. 13

C Additional Implementation Details

• Base agents are trained for 3 epochs, reinforced training for 1 epoch, and inference uses ReAct-style rationales, greedy decoding, and vLLM acceleration.Fine-tuning uses 8 NVIDIA A6000 GPUs and includes Llama-2-7B-Chat, Mistral-7B, and Llama-3-8B-Instruct.Source: C Additional Implementation Details · pp. 13–14

D.1 Variants of Step-level Reward Acquisition

• Reward-acquisition alternatives use GPT-4o annotations or a Llama-2-7B-Chat reward model trained for 3 epochs with LoRA; testing uses random seed 42.Source: §D.1 · p. 14

D.2 Detailed Settings for Calibration Analysis

• Calibration evaluation samples 100 trajectories from seen and unseen test sets in both environments, then tests whether an agent can complete the task from the resulting state.A second setting traverses the history without the deviated action.Source: §D.2 · p. 14

E.1–E.3 Prompt Templates

• Inference prompts combine instructions, a one-shot example, task instructions, and history; reflection prompts include a deviated-action history, while reward prompts request a 0–1 action score.Source: §E.1 · p. 14, Figure 6 · p. 15, §E.2 · p. 15

F Case study

• In the ALFWorld case study, STeCa identifies deviated actions, reflects, and completes the task, while two other agents do not achieve the same performance.Source: F Case study · p. 15, Figure 9 · p. 16

G.1 Additional Evaluation on ScienceWorld

• On ScienceWorld tasks averaging 14.4 steps, STeCa outperforms SFT and IPR on seen and unseen test tasks.Source: §G.1 · p. 17, Table 5 · p. 17

G.2 Affordance Analyses for LLM Agents

• Across VirtualHome and ALFWorld, STeCa has higher affordance rates, indicating more generated actions are executable and satisfy environmental constraints.Source: Figure 10 · p. 17, §G.2 · p. 17

G.3 Ablation Studies

• Removing any of the calibration, exploration, or success-guided losses reduces unseen-task performance, with the losses supporting complementary capabilities.Source: §G.3 · p. 17, Table 6 · p. 17

G.4 Hyperparameter Analyses

• At δ = 0, unseen-task success reaches 76.1% on ALFWorld and 63.6% on VirtualHome; positive δ may over-filter calibration opportunities, while negative δ may tolerate too many suboptimal actions.Source: §G.4 · pp. 17–18, Table 7 · p. 18

G.5 Discussions on Long-horizon Tasks

• VirtualHome tasks often require intricate action sequences, such as writing emails using a laptop or performing household cleaning, within environments where long-horizon tasks involve many sequential interaction steps.Source: §G.5 · p. 18
• ALFWorld and VirtualHome require 10.1 and 11.5 average interaction steps, respectively, making them suitable benchmarks for long-horizon evaluation.The paper describes their tasks as involving complex sequences of subtasks.Source: §G.5 · p. 18, Table 8 · p. 18
• On unseen VirtualHome tasks, STeCa scores 48.9% on long-horizon tasks, versus 40.0% (SFT) and 42.2% (IPR), with a narrower advantage on medium-horizon tasks.For short-horizon tasks, STeCa’s 76.2% matches the best baseline, SFT.Source: Table 9 · p. 18, §G.5 · p. 18
• The performance gap widens as task horizon increases, and the authors interpret this pattern as evidence of STeCa’s robustness in long-horizon scenarios.They emphasize calibration capability for maintaining trajectory adjustments in more complex, extended tasks.Source: §G.5 · p. 18