Hindsight Budget Relabeling for Safe Sparse-Reward Exploration

Hindsight relabeling is the trick that makes sparse-reward robot learning work. When an arm fails to push a block to its target, the method pretends the place the block actually ended up was the target all along, and so turns a failure into a success to learn from. The trick has no notion of safety. A trajectory that reached its relabeled goal by slamming through a forbidden zone becomes a "successful demonstration" just like a careful one. We propose to relabel two things in hindsight: the goal, and also the safety budget the agent was operating under. Any stretch of experience that reached state $s'$ while spending cost $C$ is a success for "reach $s'$ with budget at least $C$". It is a constraint violation for "reach $s'$ with any smaller budget". A single safe trajectory therefore yields both positive and negative safety-labelled examples, and no Lagrange multiplier has to be tuned.

This matters because the two halves of the problem currently defeat each other. Safe reinforcement learning (RL) methods keep cumulative cost under a budget during training, but they need a reward signal to climb. Sparse-reward methods find rewards by broad exploration, which in hazardous environments means incurring cost. Safe RL also has its own data-starvation problem: once the policy is safe it stops seeing violations, and its estimate of where the danger boundary lies decays. Budget relabeling attacks both problems with one supervised-style mechanism: goal relabeling densifies reward, and budget relabeling densifies constraint data.

Core Claim

We treat the problem as a constrained Markov decision process (CMDP), meaning an RL problem where each step yields a task reward $r$ and a separate safety cost $c \ge 0$, and the agent must keep accumulated cost under a budget $\epsilon$. We make it goal-conditioned with a sparse objective: reach goal $g$ before the remaining budget $b$ runs out. The agent's input is the triple $(s, g, b)$. The budget evolves deterministically as $b_{t+1} = b_t - c(s_t, a_t)$, and the episode counts as failed the moment $b_t < 0$.

Because the budget's dynamics are known and deterministic, $b$ can be rewritten after the fact exactly as $g$ is in standard relabeling. We learn a single critic

$$Q(s, a, g, b) \approx \Pr\big[\text{reach } g \text{ with cumulative future cost} \le b \mid s, a\big],$$

where the probability is over the environment and the policy. For a stored segment from time $t$ to $t'$ with accumulated cost $C_{t:t'} = \sum_{k=t}^{t'-1} c(s_k,a_k)$, we relabel with goal $g' = \phi(s_{t'})$, where $\phi$ maps a state to goal space. We pair that goal with a budget $b'$ sampled on both sides of $C_{t:t'}$. Budgets with $b' \ge C_{t:t'}$ give success labels. Budgets with $b' < C_{t:t'}$ give violation labels at the step where the relabeled budget goes negative.

The claim we will test has two parts. First, one budget-conditioned policy trained this way should match or beat separately tuned Lagrangian agents with hindsight relabeling at every budget level. Second, it should incur fewer constraint violations during training. The reason is that the critic learns per-goal, per-budget feasibility, where a Lagrangian method uses one global price on cost.

Budget-augmented states are a natural construction on their own. What we add is relabeling the budget in hindsight, together with the two consequences we study: synthetic violation data drawn from safe experience, and safe goal selection during exploration.

How It Departs From Prior Work

Hindsight relabeling supplies the core method. Hindsight Experience Replay relabels replayed transitions with goals reached later in the episode. On Fetch push, slide and pick-and-place it took DDPG from near-zero success to near-perfect. It is entirely safety-blind, and that blindness is the gap we close. Generalized Hindsight relabels trajectories to whichever reward parameters make them look expert, including speed-versus-energy trade-offs. That is a scalarized multi-objective weighting, not a hard per-trajectory budget, and it creates no violation examples. Curiosity-Driven Multi-Criteria HER cracks Stack-3 (0% to 95%) by adding a surprise-seeking explorer. That explorer is precisely what we must avoid in hazardous settings, since unmodeled dynamics often mean collisions.

Safe exploration both motivates and constrains the design. Backward Value Functions show that trajectory constraints become local once you track cost-so-far plus cost-to-go. Our budget variable is exactly cost-so-far subtracted from $\epsilon$, but BVF is on-policy and relies on dense reward. FOCOPS and other primal-dual methods such as NPG-PD are also on-policy, and they constrain expected cost rather than per-episode cost. Off-policy relabeling cannot be bolted onto them without reformulation. We sidestep this by folding the constraint into an off-policy reachability critic.

Breaking Safety Paradox with Feasible Dual Policy Iteration motivates our second claim. It shows that safe policies starve their own feasibility estimates of violation data. Its remedy is a second policy that deliberately probes unsafe boundaries in the live environment, which keeps the violation-sample ratio about 10x above a baseline that falls below 1%. We ask whether tightening budgets in hindsight can supply that boundary data from experience that was collected safely.

One constraint must be faced directly. Understanding Hindsight Goal Relabeling Requires Rethinking Divergence Minimization argues that relabeling is better understood as divergence minimization than as unbiased RL. The known optimism of hindsight relabeling in stochastic environments becomes a safety hazard here. A lucky low-cost trajectory relabeled as success at a tight budget makes the critic overconfident that tight budgets are feasible. We treat this as a first-class risk rather than a footnote.

Research Program

The method is built on soft actor-critic (an off-policy algorithm that adds an entropy bonus to keep exploring) with replay. The actor and critic are conditioned on $(s, g, b)$.

The replay sampler draws a segment and relabels its goal with the "future" strategy from HER. It then draws $b'$ from a mixture with three parts. The first is uniform on $[0, \epsilon_{\max}]$. The second is concentrated just above $C_{t:t'}$, giving the tightest feasible successes. The third is concentrated just below it, giving the tightest violations. The proportion going to the third part is the knob that controls how much synthetic boundary data the critic sees.

We will enforce that $Q$ is non-decreasing in $b$, because more budget can never hurt. We will compare enforcing this through the network architecture against enforcing it through a penalty. To address the optimism risk, the critic for the budget dimension will use a lower-quantile (distributional) target, so feasibility at tight budgets is estimated pessimistically.

During data collection, the agent conditions on its true remaining budget $\epsilon - \sum c$. It picks commanded goals from a frontier: candidate goals whose estimated feasibility at the current budget lies in a middle band, say 0.3 to 0.7. This replaces curiosity with a curriculum that is safety-aware by construction.

The analysis has three threads. First, we characterize when budget relabeling produces any negative data at all. If training cost is exactly zero, then $C_{t:t'} = 0$ and no synthetic violations exist. So the method helps when the agent incurs small, within-budget costs, which is the regime of Safety-Gymnasium cost limits. It does not help in strict zero-cost regimes, and we will state this boundary explicitly. Second, we measure how relabeling optimism scales with environment stochasticity, by injecting action noise. Third, we measure whether the learned feasibility surface is calibrated: predicted success probability against empirical success across budgets.

Baselines

The naive reference point is HER on the sparse task with costs ignored. It shows how much cost unconstrained hindsight learning incurs and gives an upper reference for task success. We expect it to approach the near-perfect Fetch success reported by Hindsight Experience Replay while violating budgets freely. Plain SAC without relabeling sets the floor; HER reports DDPG without relabeling near 0% on push, slide and pick-and-place.

The strongest competitor is SAC-Lagrangian with HER and a goal-conditioned cost critic. It relabels goals, learns a separate cost-to-go critic over relabeled goals, and adapts one Lagrange multiplier per run toward budget $\epsilon$. It is the obvious simple combination, and it may be enough. We will train it separately at each budget level we evaluate, with the same network sizes, replay ratio and environment steps as our method. Its tuning budget for multiplier learning rate and initialization will equal our tuning budget for the relabeling mixture. Beating it means, on the sparse benchmarks below, two things together: success that matches or exceeds it at every budget level, from a single policy, and lower cumulative training-time violations. Matching it on success alone would leave our contribution as convenience rather than capability.

The second strong competitor is a goal-conditioned port of FDPI, which adds the dual probing policy to that Lagrangian agent. It tests whether live boundary probing beats synthetic boundary data. The file reports FDPI's near-zero violations across 14 Safety-Gymnasium environments and its elimination of late cost spikes, but only qualitatively and only with dense rewards. There is no reported result on Lacuna for FDPI on sparse-reward goal tasks.

PPO-Lagrangian from the SafePO library in Safety Gymnasium is the on-policy reference. On dense velocity tasks it is reported to give a 98% reduction in violations at a 45% reward cost. There is no reported result on Lacuna for it under sparse binary goal reward, which we expect to break it.

Two ablations isolate the key ingredient. The first conditions on budget but never relabels it, always using the true remaining budget. It separates budget conditioning from budget relabeling. The second removes the below-cost portion of the mixture. It separates the value of synthetic violation data from the value of positive budget labels.

Why not just…?

Why not just add a cost penalty to the sparse reward? Hand-tuned penalties are known to be brittle. Safety Gymnasium documents agents that ignore small penalties and freeze under large ones. Under sparse reward the freezing failure is worse, because there is no task gradient to counterbalance the penalty. We will include a sweep over penalty weights to show where the frontier between unsafe and useless falls on our tasks, but we do not expect it to be competitive.

Why not just run HER with a Lagrangian cost critic? This is the real threat, and we treat it as the main baseline rather than arguing it away. Our reasons to expect a gap are specific. One multiplier prices cost identically across all goals, whereas goals near hazards need tight caution and far-from-hazard goals need none. The method also has no mechanism to manufacture violation data once the policy becomes safe, which is exactly the starvation described in Breaking Safety Paradox. If the per-budget comparison shows no gap in either success or training violations, the honest conclusion is that budget relabeling is a convenience: it gives one policy for all budgets. We would report it as such.

Why not just relabel only with goals reached at zero cost? Cost-filtered relabeling is the cheapest safety patch for HER. It throws away every trajectory that touched cost, which is most early experience near hazards, and it teaches the critic nothing about where the boundary is. We include it as a baseline. Its expected signature is safe but slow learning, with low success on goals that require passing near hazards.

Why not just put a safety shield in front of HER? A shield such as Adaptive Probabilistic Shielding blocks unsafe actions during data collection, but it leaves the replay data shaped by interventions the learner does not see. It also intensifies the starvation of violation data. It also needs a model of the hazards, which we do not assume. Where a shield is available it is complementary, and we will report HER-plus-shield on the toy domain where an exact shield is easy to build.

Proposed Experiments

Three testbeds are used. The first is Bit-Flipping from Hindsight Experience Replay, where DQN fails beyond 13 bits and HER solves 50. We add a per-step cost for flipping designated "fragile" bits, which gives an exact, enumerable setting for checking critic calibration and optimism. The second is Fetch push and pick-and-place with binary reward. We add a forbidden table region and a gripper-velocity limit, each incurring per-step cost. The third is Safety-Gymnasium PointGoal1 and CarGoal2, with their dense distance reward replaced by binary goal reach and their native hazard costs kept. This sparse variant does not exist in the benchmark, so there is no reported result on Lacuna for any method on it.

Metrics are reported at budgets spanning tight to loose. They are final success rate; the per-episode cost distribution together with the fraction of evaluation episodes exceeding budget; cumulative violations over training; the violation-sample ratio in late-training replay, for comparison with FDPI's diagnostic; and calibration error of $Q$ against empirical success at each budget.

Four checks decide the outcome. The first is a success-versus-budget curve: our single policy against separately trained Lagrangian-HER agents, where the proposal wins only if it is at or above them at every budget. The second is training-time violations and late-training cost spikes, compared against Lagrangian-HER and goal-conditioned FDPI. If synthetic violations really substitute for live probing, we should match FDPI's stability without its deliberate unsafe rollouts. The third is the two ablations, which tell us whether relabeling the budget, and specifically the below-cost labels, is what produces any gain. The fourth is a noise sweep on Bit-Flipping and Fetch that measures how often the policy violates budgets it predicted as feasible. It compares the pessimistic quantile critic against a mean critic. If optimism from relabeling cannot be controlled at realistic noise levels, the method is unsafe in exactly the setting it targets, and we will say so.