BEACON: Solving the Credit Assignment Crisis in Long-Horizon Language Agents

TL;DR

Training LLM agents to perform tasks spanning dozens of steps often leads to "performance collapse." This paper introduces BEACON, a framework that uses semantic milestones to break long tasks into manageable segments. By assigning rewards for partial progress and isolating local action quality from future failures, BEACON achieves a 92.9% success rate on long-horizon ALFWorld tasks, nearly doubling the performance of standard GRPO.

The "Flat Trajectory" Trap

Most current reinforcement learning methods for LLMs (like GRPO or PPO) treat a sequence of actions as a "flat" list. If an agent performs 20 perfect steps but trips up on the 21st, the entire trajectory is marked as a failure. This leads to two catastrophic issues:

1. Credit Misattribution: The agent is punished for the 20 correct steps just because of one late-stage error.
2. Sample Inefficiency: In complex tasks, success is rare. If only 10% of attempts succeed, 90% of the expensive training data provides zero learning signal, even if the agent completed several sub-goals (milestones) before failing.

The authors found that in ALFWorld, over 40% of gradient updates in standard GRPO contained contradictory signals where the same action was rewarded and punished in different contexts.

Methodology: The Milestone-Anchored Approach

BEACON leverages the compositional structure of tasks. Think of it like a video game with checkpoints: you shouldn't lose all experience points just because you died at the boss after clearing three levels.

1. Trajectory Partitioning

BEACON uses a milestone indicator ($\Phi$)—usually based on environment feedback like "object picked up" or "page transition"—to divide a trajectory into segments. This is based on the Milestone Markov Property: the idea that once a milestone is reached, the history of how you got there matters less than the current state.

2. Dual-Scale Advantage Estimation

This is the "secret sauce" of the paper. Instead of one global score, it calculates two:

• Trajectory-Level Advantage: Did the agent finish the whole task?
• Segment-Level Advantage: How did this agent perform in this specific segment compared to others who reached the same checkpoint?

By comparing segments only among "peers" who reached the same milestone, BEACON isolates local quality from the noise of later mistakes.

Experiments: Superior Signal Utilization

The researchers tested BEACON on ALFWorld, WebShop, and ScienceWorld. The results were definitive:

• Sample Efficiency: BEACON increased effective sample utilization from 23.7% to 82.0%. It "recycled" partial successes that were previously ignored.
• Horizon Robustness: While GRPO's performance plummeted as tasks got longer, BEACON remained stable.

Why It Works: Visualizing Credit

In a case study, an agent made an unnecessary detour during a successful run.

• GRPO gave every action a high positive score (+7.50), effectively reinforcing the mistake.
• BEACON correctly identified the detour segment as inefficient and gave those specific actions a negative score (-1.10), while still rewarding the overall success.

Critical Insight & Future Outlook

The heavy reliance on a milestone detector is BEACON's primary limitation. Currently, these detectors are hand-coded or based on environment signals. The next frontier in this research will likely be Automated Milestone Discovery—where the LLM itself learns to identify what constitutes a "checkpointer" without human help.

Conclusion: BEACON proves that for agents to master long-horizon tasks, we must move away from "flat" rewards and embrace the inherent hierarchy of complex behavior.