Discovering Milestones for Credit Assignment in Long-Horizon Robot Manipulation

Robots that must chain many skills (pick up a block, stack it, then sort the rest by color) usually learn from a single signal at the very end: success or failure. When a twenty-stage attempt fails at stage eighteen, that signal blames the seventeen good stages as heavily as the bad one. Text-based agents have found a way around this. They cut each attempt at "milestones", which are checkpoints such as "picked up the key". The agent then compares what it did after a milestone only against other attempts that reached the same milestone. The trouble is that those milestones are hand-written for each environment. We propose to discover milestones automatically in continuous visual manipulation. The discovery rule is statistical: a milestone is a recurring kind of moment after which the robot's earlier history stops helping to predict whether the attempt will succeed.

The bet behind this is that a milestone only has to be recognized consistently. Unlike a learned progress score, it does not have to be scored accurately. A progress critic that grades every frame can be fooled when the robot hesitates, backtracks, or repeats a motion. A discrete milestone label that is used only to decide which attempts get compared with each other carries far less risk of being exploited. If the bet holds, automatic milestones should close most of the gap between flat reinforcement learning and hand-labeled milestones on compositional manipulation tasks where current vision-language-action models are stuck near zero.

Where this sits

On the long-horizon side, ClevrSkills builds 33 compositional manipulation tasks on ManiSkill2. It shows that vision-language-action models, which map camera images and an instruction directly to arm commands, hit a "compositional wall". Their zero-shot success on multi-step levels L1 and L2 is near 0%. Even after fine-tuning, success on L2 is only 5.8% for Octo and 3.3% for StreamRoboLM, although the base skills (L0) reach 62.5%. This paper motivates the proposal: the individual skills exist, so what fails is chaining them. We read that as a credit-assignment problem, not a capacity problem.

On the sparse-reward side, BEACON supplies the method we reuse. It relies on what it calls the Milestone Markov Property: once a milestone is reached, the earlier history no longer matters for what comes next. Using that property, BEACON splits trajectories at milestones and computes two kinds of advantage. Its "segment-level" advantage compares a stretch of actions only against rollouts that reached the same milestone. This raised ALFWorld success from 53.5% under group-relative policy optimization (GRPO) to 92.9%, and ScienceWorld success from 21.1% to 45.3%. Its milestones, however, come from hard-coded environment text. We keep BEACON's advantage estimator and replace its milestone detector. We also turn the property BEACON assumes into a test we run on the data.

Two other lines of work compete with this approach rather than supplying parts of it. The first densifies the reward with learned critics. VLAC predicts progress between pairs of frames and uses it as reward, taking a real robot from 30% to 90% success in 200 episodes. Its authors report that the critic assumes progress rises steadily over time and breaks on hesitation, regression, and repeated motions. WCM trains a critic that also predicts future states and reports a 252% improvement over standard reinforcement learning on ManiSkill. Its benefit from history saturates at three frames. The second line is hindsight methods. HAL relabels failed attempts as successes at whatever was actually achieved, but it needs an oracle to describe that outcome. HCAPO reweights actions by how much more likely they become once the final outcome is known, but it works only in text. Our proposal differs from both lines in one respect: it never asks a model for a scalar judgment of how good a state is. It only asks which recurring kind of state has been reached.

Core Claim

Milestones for continuous manipulation can be discovered in three steps. The first step proposes candidate boundaries from cheap contact events. The second groups the images just after each boundary into recurring types. The third keeps only the types that pass a history-irrelevance test. The resulting milestones make segment-level advantages work nearly as well as oracle milestones, and they beat dense progress-critic rewards on long compositional tasks.

The history-irrelevance test works as follows. Let $c$ be a candidate milestone type, let $s$ be the current observation, let $h$ be the observation history before reaching $c$, and let $y$ be eventual success. Type $c$ is accepted if

$$\Delta_c = \mathcal{L}\big(f(s)\big) - \mathcal{L}\big(f(s,h)\big) < \epsilon,$$

where $f(s)$ and $f(s,h)$ are two success predictors, one without and one with history, fit on held-out states of type $c$. $\mathcal{L}$ is their log-loss, and $\epsilon$ is a small tolerance set by a permutation test. A small $\Delta_c$ is the empirical form of BEACON's Markov property, and it is what makes comparing rollouts that share a milestone a valid baseline.

Research Program

Candidate boundaries come from gripper open/close events and from contact onsets and offsets. These events come from the robot's own joint and gripper sensors, not from task-specific code. We embed the camera frame just after each event with a frozen vision encoder, together with the gripper state. We then cluster these embeddings across a pool of rollouts, aligning each cluster with the order in which events occur within a trajectory. After the test above, the surviving clusters become the milestone vocabulary. We re-estimate this vocabulary every few policy iterations, because the policy's behavior shifts during training.

Policy learning starts from a fine-tuned Octo checkpoint on ClevrSkills. It uses PPO (proximal policy optimization, a standard on-policy algorithm) with groups of rollouts launched from the same initial state. The advantage has two parts. The first is the trajectory-level group advantage from the final success signal. The second is a segment-level advantage: each segment's outcome is whether it reaches the next milestone, compared against other rollouts in the group that started that segment from the same milestone. The weighting and the within-segment discount follow BEACON.

The analysis has three parts. First, we measure how well discovered milestones match ClevrSkills' ground-truth predicates, the physical and logical conditions the benchmark checks. Second, we measure how the milestone count changes with task level. Third, we measure the fraction of rollouts that contribute a non-zero learning signal. BEACON reports this fraction rising from 23.7% to 82.0% in text, and we test whether the same happens in manipulation.

Baselines

The naive reference point is the fine-tuned Octo policy with no reinforcement learning. On ClevrSkills L2, the paper reports 5.8% success for this policy. We re-run it under our evaluation seeds so that every other number is measured against the same starting checkpoint.

Flat PPO with group-relative advantages from the sparse final reward is the direct ablation of our contribution. It uses the identical initialization, rollout group size, environment-step budget, and tuning budget, with no segmentation. Beating it by a clear margin on L1 and L2, and not only on L0, is the minimum bar. No reported result found on Lacuna for flat RL on ClevrSkills. For a sense of the size of such gaps, BEACON beat GRPO 92.9% to 53.5% in text.

The strongest existing competitor is dense progress reward from a pair-wise critic in the style of VLAC, added to the sparse reward in the same PPO setup. It is the strongest competitor because it already reports 30% to 90% on a real robot and needs no task structure at all. We use the released critic if it is available; otherwise we train a pair-wise progress critic on ClevrSkills demonstrations with a matched parameter count. The critic's tuning budget matches ours. A WCM-style critic (WCM) serves as a second dense baseline. No reported result found on Lacuna for either on ClevrSkills L1/L2.

Oracle milestones taken from ClevrSkills' ground-truth predicates give a BEACON-style upper bound. Two ablations isolate the key ingredient. The first uses the same contact-event boundaries without the history-irrelevance filter. The second uses boundaries placed at fixed time intervals. Beating these ablations shows that the test itself matters, and that simply chopping trajectories is not enough. Success means matching or exceeding dense-critic PPO on L2, recovering at least most of the oracle-milestone gain over flat PPO, and beating both ablations.

Why not just…?

Why not just use a dense progress critic, since VLAC already works? This is the real threat. On short tasks it may well win, because dense reward gives signal at every step. Our claim is narrower: on L2 tasks with regressions (stacking, then unstacking to reorder), a critic that assumes steady progress will reward the wrong motions, and its own authors report this failure mode. The dense-critic baseline, with success broken down by whether a task contains a non-monotonic stage, settles this. If the critic matches us on the non-monotonic tasks, the proposal's central bet is wrong.

Why not just ask a vision-language model whether each subgoal has been reached? A model that answers yes/no questions about the image could, in principle, label milestones from the instruction. ClevrSkills, however, shows that these backbones fail at compositional reasoning over these same scenes. Inconsistent labels would also corrupt the grouping of rollouts by milestone. We include this judge as a further baseline, measure its agreement with the ground-truth predicates, and compare it with our clusters.

Why not just run flat RL with many more rollouts? BEACON reports that over 40% of GRPO updates carried contradictory signals, and adding samples does not remove that contradiction. As a test, we run flat PPO at a budget four times larger. If it catches up, the method is only a sample-efficiency trick, and we will report it as one.

Why not just relabel failures in hindsight? HAL needs an oracle to describe the outcome, and HCAPO needs text descriptions of states. Neither is available for continuous contact states without the very labeling problem we are trying to remove.

Decisive Checks

The main evaluation measures success on ClevrSkills L0, L1, and L2 at matched environment steps, over five seeds. For transfer, we also test on LIBERO-Long (LIBERO), which has no predicate oracle. Three results would falsify the proposal. The first is if the history-irrelevance test rejects almost every cluster, or accepts clusters that do not match predicates. The second is if the no-filter ablation performs as well as the full method. The third is if dense-critic PPO matches us on tasks with regressions. A positive result would be a large L2 gain over the 5.8% starting point, recovery of most of the oracle-milestone gain, and a rise in the fraction of rollouts that produce learning signal comparable to what BEACON reported in text.