TL;DR
ConCal (Continuation Calibration) is a novel recursive estimator that improves reinforcement learning for long-horizon agents by sharing "continuation evidence" across different trajectories. By matching similar transitions within a rollout batch and propagating calibrated values backward, it significantly reduces the noise in credit assignment, leading to more robust learning and higher success rates on complex tasks like web navigation and embodied AI.
What Problem Does This Paper Address?
In long-horizon Reinforcement Learning (RL), the "credit assignment" problem is a major hurdle. When an agent performs a sequence of dozens of actions, how do we know which specific action led to success or failure?
Existing methods like GRPO assign the same credit to every action in a trajectory, which is blunt. More advanced methods like GiGPO compare different actions at the same state, but they still estimate an action's value based on a single sampled "continuation" (the rest of that specific trajectory). This is highly noisy: a brilliant early move might be followed by a random late-game mistake, making the early move look bad. Conversely, a poor move might be "saved" by a lucky recovery later on.
The authors identify this as "credit conflict"—where the same decision receives both positive and negative feedback across different rollouts, confusing the learning process.
Methods
The core idea of ConCal is to use the entire rollout batch as a collective source of evidence. Instead of looking at just one path forward, it looks at all paths that reached the same state through the same action.
- Matching Visits: The algorithm identifies "matched visits" across different trajectories. Two visits are matched if they share the same task, preceding state, executed action, and resulting state.
- Recursive Calibration: For each visit, ConCal computes a "transition estimate" (immediate reward + value of the next state). It then blends this individual estimate with the mean estimate of all its matched "peers."
- Recursive Propagation: This calibration happens backward. Calibrated values from the end of a trajectory are used to refine the estimates of earlier actions. This allows even actions without direct matches to benefit from evidence shared later in the sequence.
- Partial Sharing: Crucially, ConCal doesn't just average everything. It retains a portion of the individual visit's original estimate, which helps maintain the unique context of that specific rollout.
- Batch-wise Normalization: To turn these values into training signals (advantages), the authors use batch-level scaling. This preserves the "preference strength"—ensuring that clear, high-confidence value gaps result in stronger updates than noisy, narrow ones.
Datasets
The authors evaluated ConCal using the Qwen2.5-1.5B-Instruct model on two challenging benchmarks:
- ALFWorld: A simulator for household tasks (e.g., "put a clean sponge in the fridge") requiring text-based interaction and long-term planning.
- WebShop: An e-commerce environment where agents must search for and purchase specific products based on complex user requirements.
Key Insights and Ideas
- The Batch is a Graph: While rollouts are collected as linear trajectories, the authors treat the batch as a structured set of overlapping transitions. This allows them to "borrow" future information from one trajectory to help evaluate an action in another.
- Reducing Credit Conflict: By averaging out the noise of individual continuations, ConCal drastically reduces the rate of conflicting signals. As shown in Figure 2, it reduces credit conflict by over 60% in WebShop and 72% in ALFWorld.
- Preference Strength Matters: Standard normalization often squashes value differences. ConCal’s use of batch-wise normalization ensures that when the model is "sure" about a good action (a large value gap), the gradient update is appropriately strong.
Key Results
ConCal achieved state-of-the-art performance among compared methods on both benchmarks:
- ALFWorld: Reached a 94.27% overall success rate, a 3.39 percentage point (pp) improvement over GiGPO.
- WebShop: Achieved a 79.69% success rate, outperforming GiGPO by 5.86 pp and surpassing the previous best method, GraphGPO.
- Efficiency: The matching and calibration steps are extremely fast, adding less than 0.04 seconds of overhead per batch, making it a "free" lunch in terms of computational cost compared to the heavy lifting of LLM rollouts.
Limitations and Future Work
- Strict Matching: The current matching rule requires exact state-action-state matches. This might be too restrictive for environments with very high-dimensional or continuous state spaces where exact matches are rare.
- History Neglect: The matching rule focuses on the immediate transition and doesn't account for the full interaction history or the agent's internal "hidden state."
- Future Directions: The authors suggest that future work could involve "fuzzy" matching using historical context or incorporating uncertainty estimates into the continuation values to further refine the calibration.
Summary updated