Most safe reinforcement learning promises that cost stays below a limit on average over many runs. A robot can therefore satisfy its constraint while crashing in one run out of twenty, as long as the other nineteen are clean. Many deployments need something else: each individual run must reach the goal without exceeding its cost budget. Writing that requirement down is easy. The agent should earn 1 if it succeeds and spends at most $b$ units of cost in the episode, and 0 otherwise. Learning from it is hard for two reasons. Under this per-episode reward, standard averaged-cost methods optimize the wrong quantity. The reward is also sparse twice over, because success is rare and successes that stay within budget are rarer. Practitioners usually sidestep both problems by hand-tuning a penalty $r - \lambda c$ and shaping the reward, which is exactly the manual engineering we want to remove.
We propose that one trick resolves both problems. If the agent tracks how much budget it has left, the per-episode objective becomes an ordinary Bellman recursion. Because that remaining budget changes deterministically with observed cost, every transition the agent collects can be replayed under every possible budget. This is analogous to how hindsight relabeling replays a trajectory under different goals. A run that reaches the goal while overspending is a failure for the deployment budget but a success for every looser budget. That turns rare, wasted episodes into dense supervision for a single value function that covers all budgets. The user supplies only a success test, a cost signal, and a budget. There is no penalty weight and no shaping.
Core Claim
Researchers who study multi-objective decisions call this per-run objective the expected scalarised return (ESR): apply a utility function to each episode's outcome, then average. The usual alternative, the scalarised expected return (SER), averages first and then applies the utility. For the utility $u(\text{success}, C) = \mathbf{1}[\text{success} \wedge C \le b]$, with $C$ the episode's total cost, the ESR value admits an exact recursion over the augmented state $(s, \beta)$, where $\beta$ is the remaining budget:
$$Q(s,a,\beta) = \mathbb{E}_{s',c}\Big[\max_{a'} Q(s', a', \beta - c)\Big],$$
with value 1 at a goal state with $\beta \ge 0$ and value 0 as soon as $\beta < 0$. Here $Q(s,a,\beta)$ is the probability of succeeding within the remaining budget after taking action $a$. Since $\beta \mapsto \beta - c$ does not depend on the policy, any stored transition $(s,a,c,s')$ is a valid sample for every $\beta$. For a fixed $(s,a)$, $Q$ is non-decreasing in $\beta$: it is a cumulative distribution over the cost that a successful continuation incurs.
Our claim has three parts. First, off-policy learning with budget relabeling and a value network constrained to be monotone in $\beta$ will reach high per-episode success-within-budget faster than penalty methods and averaged-cost constrained methods under purely sparse rewards. Second, it will incur fewer over-budget training episodes than those methods. Third, it will do so with one network serving all budgets, including the zero-budget case where averaged-cost methods are known to struggle.
Where This Sits
Three ESR lines supply the theory but not the learning method. Monte Carlo tree search algorithms for risk-aware and multi-objective reinforcement learning show that non-linear utilities force the agent to condition on returns accrued so far, and it plans with a simulator. Solving General-Utility MDPs in the Single-Trial Regime proves that single-trial optimality is history-dependent and NP-hard in general, and needs a running tally of visited states and actions. Decision-Theoretic Planning for the Expected Scalarised Returns plans over discretized return distributions, which is exponential in the number of objectives. We use their key insight but give up their generality. For a threshold utility on a single cost, one scalar, the remaining budget, is a sufficient summary of history. That makes model-free, continuous-state learning possible where those methods need a simulator or tabular tallies.
On the safety side, Constrained MDPs via Backward Value Functions also tracks cost-so-far. It does so only to turn an expected cost constraint into local bounds, and it assumes dense rewards and a safe starting policy. Our recursion targets the per-episode probability directly. Breaking Safety Paradox with Feasible Dual Policy Iteration shows that safe agents starve their safety critic of violation data, and it fixes this by deliberately seeking violations with a second policy. Budget relabeling attacks the same data-starvation problem from the other side, without extra violations: an over-budget episode at one budget is clean data at another. FDPI still assumes dense task reward, however.
On sparse rewards, Reverse Curriculum Generation supplies our budget-scheduling idea. It trains from start states where success rates sit between 10% and 90%, but it needs arbitrary resets and ignores safety. We apply the same "Goldilocks" rule to the budget axis, which needs no resets. LS3 is the closest prior system, since it combines safe sets with sparse rewards. It learns from demonstrations, constrains plans to end in known-safe regions, and optimizes an ordinary expected objective with no per-episode budget. Its benchmark becomes one of ours. Finally, Quanyi Li et al. document why fixed penalties fail: agents either accept violations or freeze. This motivates removing $\lambda$ altogether.
Research Program
The method is a soft actor-critic agent whose critic and policy take $(s, \beta)$ as input, where $\beta$ is normalized by the maximum budget of interest. Each sampled minibatch transition is paired with $K$ budgets drawn from a mixture of the deployment budget $b^\*$, the budget actually used at collection time, and values near the hindsight cost of the episode it came from. Targets follow the recursion above, using the terminal rules for reaching the goal and for running out of budget.
The critic outputs $Q$ as a monotone function of $\beta$. We parametrize this as a cumulative sum of non-negative increments over budget bins, or as a monotone network. Monotonicity is a correct structural prior, and it lets a success observed at a loose budget lower-bound nothing while still informing the curve's shape. Because $Q$ estimates a probability, we train with a binary cross-entropy loss against bootstrapped targets.
The behavior budget used during data collection is the main lever for safe exploration, so we study it explicitly. We compare three schedules. The first always acts at $b^\*$. The second anneals from loose to tight. The third is adaptive: it acts at the tightest budget whose predicted success at the start state falls in the 10–90% band, clipped above at a user-set training-violation ceiling. We report the full trade-off between training-time violations and time to competence, rather than picking one schedule after the fact.
As an analysis component, we will prove that the recursion is exact for threshold utilities in the augmented state space. We will also verify that the relabeled targets are unbiased for deterministic cost transitions. In a stochastic gridworld, where exact per-episode values can be computed by dynamic programming over $(s, \beta)$, we will check that learned values match these exact values.
Baselines
The naive reference point is soft actor-critic on the sparse success reward minus a fixed penalty $\lambda c$. We sweep $\lambda$ over a log grid with the same total environment steps, and report the best $\lambda$ chosen per environment on the per-episode metric. That selection is generous to the baseline and represents the manual-tuning workflow we aim to replace. We beat it if our single untuned run matches or exceeds the best swept $\lambda$ at every budget.
The strongest existing constrained method is FDPI (Breaking Safety Paradox with Feasible Dual Policy Iteration), alongside PPO-Lagrangian and SAC-Lagrangian as standard references. FDPI reports the lowest constraint violations, near zero, across all 14 Safety-Gymnasium environments it tested, while matching or exceeding CPO, PPO-Lag, SAC-Lag, and SAC-FPI on return. For PPO-Lag, Safety Gymnasium reports a 98% reduction in violations versus PPO with a 45% drop in reward on velocity tasks. Both results use dense rewards. We found no reported result on Lacuna for any of these methods on sparse-reward Safety-Gymnasium variants, so we run them ourselves. Each gets the same sparse reward, the same expected-cost limit set to $b^\*$, the same step budget, and an equal hyperparameter-tuning budget of a fixed number of trials. Beating FDPI means higher per-episode success-within-$b^\*$ and fewer over-$b^\*$ training episodes at equal steps. We expect FDPI may win on average cost while losing on the per-episode metric, and showing that divergence is part of the point.
On the LS3 tasks, the reference is LS3 itself. It reports a 64.8% success rate on Sequential Pushing, against SACfD at 42.5% and AWAC at 0.6% (LS3). To keep the comparison fair, we give our agent the same demonstrations, loaded into its replay buffer and relabeled across budgets.
Two ablations isolate the key ingredients. The first keeps the budget-augmented state and the same recursion but trains only at the budget used during collection, with no relabeling. Any gap here measures relabeling alone. The second removes the monotonicity constraint. A third variant trains separate networks, one per budget, to test whether sharing across budgets matters.
Why not just…?
Why not just tune the penalty $\lambda$ and add curiosity for the sparse reward? Penalties fail in both directions, as Quanyi Li et al. document. Curiosity actively pulls agents toward uncertain, boundary-violating regions, as Escaping Offline Pessimism argues and illustrates with agents "parking" at the uncertainty frontier. More basically, any fixed $\lambda$ optimizes an averaged trade-off, not the probability that a single run stays under budget. In MetaDrive, PPO with reward shaping incurred an average episode cost of 14.1 versus 2.2 for constrained planning (SafeDreamer). Our penalty-sweep baseline, with and without a curiosity bonus, tests this alternative directly.
Why not just use a Lagrangian method with an expected-cost limit equal to the budget? An expected-cost limit lets occasional large violations average out, and the ESR literature shows that SER-optimal and ESR-optimal policies can differ sharply (Expected scalarised returns dominance). Lagrangian methods also only guarantee satisfaction at convergence (BVF), and they suffer late-training cost spikes when violation data dries up (FDPI). The honest risk is that, with a tight limit, a well-tuned FDPI already produces few over-budget episodes. We settle this by reporting the full distribution of per-episode cost, not just its mean, and by including the zero-budget case.
Why not just augment the state with remaining budget and train at the deployment budget? This is the real threat. If relabeling adds little, our contribution shrinks to a known modeling choice. The no-relabeling ablation answers it directly. Our prediction is that the gap is largest under sparse reward and tight budgets, where successes within budget almost never occur but successes slightly over budget do. If the gap is small there, we will report budget augmentation as sufficient and drop the relabeling claim.
Proposed Experiments and Decisive Checks
We will create sparse-reward variants of Safety-Gymnasium Goal, Button, and Push with Point and Car robots. In each, the default distance-based reward is removed so that the agent receives reward only on reaching the goal, and the existing hazard costs are kept. We test deployment budgets of 0, 5, and 25. We also run the LS3 suite (Pointmass, Reacher, Sequential Pushing), and a stochastic gridworld where exact values are available.
The primary metric is the per-episode rate of success within $b^\*$ at evaluation, averaged over 10 seeds. Secondary metrics are the number of over-$b^\*$ episodes during training, the steps needed to first exceed 20% success within budget, and conventional average return and average cost, so that SER–ESR divergence is visible.
Four results would be decisive. First, the gridworld values must match dynamic programming; otherwise the recursion or the relabeling is flawed. Second, the no-relabeling ablation must lag clearly on tight budgets in the sparse tasks; otherwise the central claim fails. Third, at a matched average cost, our method should show a lower fraction of over-budget episodes than FDPI and PPO-Lag, which is the per-episode distinction made concrete. Fourth, a single budget-conditioned network evaluated at $b = 0$ should outperform the Lagrangian methods trained specifically for a zero limit, the regime where they are reported to fail.
References
- Monte Carlo tree search algorithms for risk-aware and multi-objective reinforcement learning
- Solving General-Utility Markov Decision Processes in the Single-Trial Regime with Online Planning
- Decision-Theoretic Planning for the Expected Scalarised Returns
- Constrained Markov Decision Processes via Backward Value Functions
- Breaking Safety Paradox with Feasible Dual Policy Iteration
- Reverse Curriculum Generation for Reinforcement Learning
- LS3: Latent Space Safe Sets for Long-Horizon Visuomotor Control of Sparse Reward Iterative Tasks
- MetaDrive: Composing Diverse Driving Scenarios for Generalizable Reinforcement Learning
- Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark
- Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Exploration
- SafeDreamer: Safe Reinforcement Learning with World Models
- Expected scalarised returns dominance: a new solution concept for multi-objective decision making