Been heads-down lately, but I finally had a couple of days to catch up on some recent papers. Sharing one of them here.
Milestone-Guided Policy Learning for Long-Horizon Language Agents
Zhejiang University (ZJU-REAL) · arXiv:2605.06078 · github.com/ZJU-REAL/BEACON
It tackles a very concrete and fairly painful problem: when you train an agent on long tasks with RL, it doesn’t just get a bit worse — it falls off a cliff as the horizon grows.
TL;DR
- Trajectory-level RL (GRPO and friends) fails on long horizons for two measurable reasons: contradictory gradients and wasted partial successes.
- BEACON splits trajectories at milestones (verifiable state transitions), shapes rewards within each segment, and estimates advantages at two scales.
- ALFWorld long tasks: 53.5% → 92.9%. Effective sample utilization: 23.7% → 82.0%.
- The gains grow with horizon length — which is a much stronger claim than a higher average score.
- There’s a metric in the paper (CCR) that appears to contradict the method’s own design. It doesn’t — but working out why is the most interesting part of the paper.
1. First, look at how cleanly they diagnose the problem
What I appreciate most is that they don’t open with the method. They open with an empirical autopsy: Qwen2.5-1.5B + GRPO on ALFWorld, breaking “long-horizon training collapses” into two quantifiable failure modes.
Failure mode 1: credit misattribution
GRPO treats a trajectory as a flat action sequence. Every action shares one terminal score.
The consequence: the same correct action gets a positive gradient in a successful trajectory and a negative gradient in a failed one. Whether it was “right” depends on what happened afterwards.
They define CAR (Contradictory Action Ratio) — the fraction of actions that receive opposite-sign advantages across trajectories despite being executed at identical states.
It peaks above 40%. Nearly half the gradient updates for repeated state-action pairs point in conflicting directions. After cancellation, effective learning signal drops below 20%.
Failure mode 2: sample inefficiency
Bucket trajectories three ways: full success, partial success (completed at least one subgoal but failed the task), and total failure.
- Partial successes hold steady at 39–47% of samples throughout training
- Full successes stay below 27%
Under GRPO, a partial success and a total failure both get a reward of 0. That means over 73% of samples produce no learning signal at all.
Both problems compound as horizons extend: longer tasks have lower success rates (more partial successes) and more opportunity for downstream stochasticity to corrupt credit.
The number that makes it concrete: ALFWorld short tasks 76.7%, long tasks 53.5%.
2. The core insight
Long-horizon tasks have structure. Flat trajectory optimization just throws it away.
They naturally decompose into phases bounded by milestones — verifiable state transitions marking subgoal completion.
The authors formalize this as the Milestone Markov Property: once you reach a milestone state, the distribution over the remaining trajectory depends mostly on which subgoals are left, not on the full history of how you got there.
In plain terms: once you have the key, what happens next depends on what you do with it — not on how you found it.
That approximate Markov property is what makes credit decoupleable across segments.
3. The method: three steps
Step 1 — partition at milestones
A detector Φ flags milestone timesteps and splits the trajectory into segments.
Here’s the design decision I think is underrated: Φ requires no learned model and no human annotation. It reads observable state changes straight from environment feedback.
- ALFWorld: object state transitions (successful pickup, heating complete)
- WebShop: page transitions toward the target product
- ScienceWorld: the environment emits explicit subgoal signals
Zero extra models, zero extra rollouts. That’s the whole cost advantage over process reward models and Monte Carlo value estimation.
Step 2 — temporal reward shaping inside segments
r_t = R_ms * γ^(t_k − t) if segment k ends in a completed milestone
= 0 otherwise
Enter fullscreen mode Exit fullscreen mode
Only segments that terminate in a milestone get positive reward. Within such a segment, actions closer to the milestone get more.
Two effects: every action in a completed segment now carries positive signal (partial successes stop being wasted), and there’s an implicit push toward efficient execution.
Step 3 — dual-scale advantage (the crux)
Trajectory level — standard GRPO normalization over terminal rewards. Captures global task performance.
Segment level — the trick is in how the comparison group is defined:
G_k = { i : K_i ≥ k } # only trajectories that ALSO reached milestone k
A_seg(i,t) = r_t − (1/|G_k|) · Σ_{j∈G_k} R_k(j) / |Seg_k(j)|
└── group-average PER-STEP return ──┘
Enter fullscreen mode Exit fullscreen mode
Actions in segment k are compared only against trajectories that also reached milestone k. From this the authors prove a variance isolation property: whether later segments succeed or fail cannot mathematically contaminate credit for the current segment.
Final advantage is A_traj + λ · A_seg, optimized with a standard PPO clipped surrogate.
Hyperparameters γ=0.95, λ=1.0 are fixed across all benchmarks — no per-task tuning. Worth noting.
4. Results
ALFWorld, Qwen2.5-1.5B:
Method Short Medium Long Avg GRPO 76.7 73.9 53.5 72.8 GiGPO 90.7 84.3 79.5 86.1 BEACON 96.8 87.0 92.9 91.4Success rate on the other two:
Method ScienceWorld WebShop GRPO 21.1 56.8 GiGPO 25.8 65.0 BEACON 45.3 75.6A few things worth calling out:
The 1.5B model beats GPT-4o. ALFWorld 91.4 vs 48.0, WebShop 75.6 vs 23.7. (Fair caveat: the closed models are prompted with ReAct, not trained. And on ScienceWorld it’s a tie — 45.3 vs 45.4. Still, a 1.5B model reaching parity is not nothing.)
Sample utilization goes from 23.7% to 82.0% — a 3.5× increase in trajectories that produce useful gradient. Zero-advantage sample ratio drops from ~55% under GRPO to ~10%.
Convergence is faster too: 60% success rate by iteration 50, where GRPO needs iteration 120.
But the most convincing result is that the gains scale with horizon. On 7B, relative improvement over GRPO goes from +13% on short tasks to +39% on long tasks. GiGPO only goes from +11% to +22%.
The reason is interesting. GiGPO builds step-level comparison groups by finding repeated states across trajectories. But as the policy improves and trajectories diversify, state recurrence gets sparser — its own signal source erodes. Milestone anchors don’t decay as the policy gets stronger.
A method whose benefit grows as the problem gets harder is a much stronger claim than a higher average score.
5. What’s actually novel here
Four things look like real contributions rather than assembly:
5.1 Redefining the comparison group
Process reward models need expensive annotation and carry reward-hacking risk. Monte Carlo value estimation needs multiple rollouts per decision point. GiGPO leans on state recurrence — incidental structure.
BEACON swaps in semantic milestones, which are intrinsic to the task, essentially free to detect, and become more reliable as horizons grow rather than less. That’s a methodological switch, not an increment.
5.2 Variance isolation has a formal guarantee
Most reward shaping work stops at “it’s denser, therefore better.” This one actually proves why cutting here works.
5.3 Dual-scale isn’t redundancy — the ablation proves both are load-bearing
Variant ALFWorld WebShop BEACON 91.4 75.6 w/o segment-level advantage 72.8 56.8 w/o trajectory-level advantage 23.4 67.9Drop the segment level and you get GRPO back exactly. Drop the trajectory level and ALFWorld craters to 23.4%.
That second row deserves thought: with only segment-level signal, the policy reinforces behaviors that hit intermediate milestones but are doomed to fail overall. Every subtask executed beautifully, the whole thing drifting off target.
The divergence between environments is also telling. WebShop still manages 67.9% without the trajectory level, because its milestones align more directly with final success. ALFWorld collapses. So how much terminal verification you need is a function of task structure.
5.4 A counterintuitive finding — CCR
This one deserves its own section.
6. CCR: the number I assumed was a typo
The authors define CCR (Credit Concentration Ratio) = average advantage magnitude for milestone actions ÷ that for non-milestone actions. CCR > 1 means credit concentrates on milestones.
Measured:
Method CCR GiGPO 2.36 GRPO 1.37 BEACON 0.84So the best-performing method is the one that concentrates credit on key steps the least.
My first reaction: this directly contradicts “actions closer to the milestone get more reward.” I had to work through the math to see that the two statements measure different quantities, with two transformations in between.
Transformation 1 — shaped reward
Within a segment, reward is monotonically increasing toward the milestone. ✅ This part is exactly as advertised.
With γ=0.95 and segment length 5, the five actions get 0.8145, 0.857, 0.9025, 0.95, 1.0.
But this is reward, not the credit that reaches the gradient.
Transformation 2 — subtract the group baseline
The baseline is the group-average per-step return (segment return ÷ segment length). For a segment of length L, per-step return is (1−γ^L) / (L(1−γ)):
So if your segment took 8 steps while the group averaged 5, your per-step return sits below the baseline and the entire segment’s advantage skews negative.
Note what this means: the penalty for wandering doesn’t come from the decay itself — it comes from the decay acting through the per-step baseline. I initially attributed it to the decay alone, which is wrong. Decay alone only orders actions within a segment.
At this point, CCR inside a completed segment is still greater than 1.
Transformation 3 — add the trajectory-level advantage
This is where CCR falls below 1, via two asymmetric effects:
(a) The tail segment of a failed trajectory enters no comparison group at all. Since G_k = {i : K_i ≥ k} and the incomplete tail has index K_i + 1 > K_i, trajectory i is excluded. That tail gets no segment-level advantage — only the trajectory-level term, at full magnitude. And every one of those is a non-milestone action, inflating the denominator.
(b) In failed trajectories, the negative trajectory-level term cancels against the positive segment-level credit on milestone actions, squeezing their magnitude toward zero.
Figure 8 confirms it numerically
On a failed trajectory that completed milestones S3 and S4:
go to toilet put soapbar (S3✓) go to counter (S4✓) go to counter go to holder GRPO −2.50 −2.50 −2.50 −2.50 −2.50 BEACON −0.92 +0.51 +0.32 −2.20 −2.20The last two values are identical — the fingerprint of “tail segment gets only the trajectory-level term,” which lets you read off A_traj ≈ −2.20. The two milestone actions are positive, but their magnitude is only ~0.5 because the negative trajectory term ate most of the segment-level credit.
CCR for this trajectory: 0.23. For a successful trajectory: 2.95. The global 0.84 is the mixture.
So what does CCR < 1 actually mean
CCR measures the concentration of gradient magnitude, not “who got rewarded.” The positive credit milestones are supposed to receive within a segment is fully intact.
The more precise framing: low CCR isn’t a design goal, it’s a byproduct of dense in-segment allocation plus dual-scale stacking.
But the authors’ conclusion still holds, and it’s a good one: don’t dump all your gradient energy on the key steps. GiGPO’s 2.36 means the preparatory actions in between get almost no signal — and those are exactly what makes reaching the milestone possible.
7. Something the paper doesn’t spell out
There’s an odd cell in the ablation table: γ=1 (uniform in-segment credit) scores 71.8, worse than no shaping at all (γ=0, 81.2), and even below GRPO’s 72.8.
The paper’s explanation: “assigning equal credit to all actions obscures the distinction between critical and preparatory actions, producing misleading gradients.”
Work through the math and the real answer is sharper.
With γ=1, every action in a completed segment gets the same reward R_ms. Then every completed segment, regardless of length, has a per-step return of exactly R_ms — so the baseline is R_ms too, and:
A_seg(i,t) ≡ R_ms − R_ms = 0 for every action
Enter fullscreen mode Exit fullscreen mode
It’s not that the gradients are misleading. The segment-level channel vanishes identically, and the method reduces exactly to GRPO.
Check it against the table: 71.8 vs GRPO’s 72.8. One point apart — run-to-run noise. It lines up perfectly.
Which means temporal decay isn’t just “differentiating actions within a segment.” It’s a necessary condition for the segment-level signal to exist at all. Without decay, the per-step baseline cancels it out on the spot.
The paper doesn’t say this.
8. Three experiments that shut down the obvious objections
Credit where due — they proactively close three holes:
“Isn’t this just behavior cloning in disguise?”
SFT on oracle trajectories gets 43%. BEACON gets 91.4%. The policy discovers execution strategies better than the oracle, so it isn’t imitating.
“Are the gains just from chunking the trajectory?”
Random partitioning (5 arbitrary split points) scores 74.2% — only 1.4 points above GRPO’s 72.8. Real milestones score 91.4%, a 17.2-point gap. The benefit genuinely comes from task-intrinsic structure. Clean control.
“What if the detector is unreliable?”
Randomly dropping 50% of milestones still yields 82.8%, 10 points above GRPO. Degradation is graceful, not a cliff.
9. Limitations, stated honestly
The biggest bottleneck is whether Φ is even obtainable.
All three benchmarks get milestones from rules: pattern matching on environment responses, page transitions, or explicit subgoal signals from the env.
Real open-ended settings — browser automation, codebase refactoring, deep research — have no such ready-made verifiable state transitions. The authors themselves list automated milestone discovery as an open problem in the appendix.
So this reads as a paradigm validated in structured environments, not an engineering recipe you can lift as-is.
Also: milestone granularity is sensitive (too sparse degenerates to GRPO, too dense makes segment advantages noisy); the Markov property is only approximate, and variance isolation rests on it; experiments stop at 7B with discrete text action spaces — continuous control and multi-agent settings are untested.
Closing thought
The ideas in this paper matter for anyone designing agents that take on long-horizon tasks — even if you’re not training a policy. The transferable part isn’t the advantage formula; it’s the claim that long tasks have exploitable compositional structure, and that structure should be a first-class runtime object rather than something you hope the model tracks in context.
We’ve been working on long-horizon task support in Orkas recently, and I’ll keep sharing our design thinking on that as it develops.
If you’re building agents for long tasks — how are you handling intermediate progress signals? Genuinely curious what’s working in production.
답글 남기기