Budget-Aware Self-Improvement of Frozen Imitation Policies

A robot trained by imitation, meaning by copying demonstrations, can be no better than its demonstrators, and it has usually never seen how to recover near danger. The known way past this ceiling is to let the robot practice and learn a value function, a model that scores how good each action is. That practice is exactly what safety-critical settings forbid. We propose a method in which a frozen imitation policy only suggests actions. Those suggestions are widened onto a grid of discrete action choices, and two learned critics pick among them: one scores task reward, the other predicts future safety cost. A hard rule checks each choice against how much of the episode's safety budget has already been spent. The robot can then improve beyond its demonstrations while keeping every training episode within its cost budget.

The twist is how the method treats the budget. Existing safe-exploration methods either never approach the constraint boundary, so their safety model starves for boundary data, or they run a separate exploratory policy that deliberately violates constraints to collect that data. We instead let the agent spend only the unused part of each episode's budget on informative, near-boundary actions. This yields the boundary data a safety critic needs without any episode going over budget. Discretizing the action space is what makes the scheme tractable. The per-state constrained choice becomes a search over a finite candidate set. The critics become classifiers over value bins, and those bins give calibrated upper estimates of cost for free.

Core Claim

The claim has two parts. First, a frozen demonstration policy plus a discretized, locally expanded candidate set plus an episode-level budget check can exceed the demonstrator's return on constrained control tasks while keeping per-episode training cost under the limit. Second, deliberately spending the leftover budget on uncertain candidates keeps the cost critic accurate in the regime where purely conservative methods degrade. If that holds, the method breaks the imitation ceiling and resolves the "safety paradox" together, without the physical violations that current fixes require.

Where This Sits

Three results motivate the design. Beyond Imitation: Self-Improving Robot Policies via Off-Policy Q-Planning keeps a large imitation policy frozen and trains a separate critic, using binned (categorical) value regression, on successes and failures. At test time it selects among the policy's proposals, and it beats both the frozen policy and filtered fine-tuning. It has two limits we target: it has no cost or constraint of any kind, and it cannot choose an action the frozen policy never proposes. Breaking Safety Paradox with Feasible Dual Policy Iteration shows that as a policy becomes safe, it stops seeing violations and its safety critic degrades. Its remedy is a second exploratory policy that actively causes violations, which is unacceptable when violations damage hardware. We keep the diagnosis and replace the remedy with budget-limited exploration. Constrained Markov Decision Processes via Backward Value Functions turns an episode-level cost budget into a per-state check, cost-so-far plus expected future cost at most the budget, and solves the discrete-action case with a small linear program. It learns from scratch and is known to be conservative. We reuse its per-state check but apply it to realized cost-so-far and to a demonstration-anchored candidate set.

Two results constrain the design. RN-D: Discretized Categorical Actors for On-Policy Reinforcement Learning shows that binning each action dimension into roughly 11 to 101 categories trained with cross-entropy is stable, and that very fine grids (1000 bins and above) collapse. Its gradient variance for a categorical actor over $K$ bins is bounded by $1/K$. We therefore stay in that bin range and factorize by dimension to avoid the $B^D$ explosion, where $B$ is bins per dimension and $D$ the number of action dimensions. Counter-Strike Deathmatch with Large-Scale Behavioural Cloning shows that discrete heads commit to one mode where Gaussian heads average modes, sometimes straight into an obstacle. This is why we do not form candidates by averaging.

Algorithmic alignment is the lens we use for the critic, not the headline. That literature designs networks whose computation mirrors a classical algorithm. Graph Neural Networks are Dynamic Programmers and A Tropical View of Graph Neural Networks argue that replacing smooth soft-minimum operations with exact min/max ("tropical") operations improves extrapolation of dynamic-programming steps. Neural Algorithmic Reasoners are Implicit Planners runs value iteration with a pretrained graph network, but its tree search grows as $|\mathcal{A}|^K$ and it has no costs. Our finite candidate set lets the cost critic's backup use an exact minimum over discrete bins rather than a smooth surrogate. We test, as an ablation rather than an assumption, whether this aligned backup extrapolates better to states the agent rarely visits.

Method

At each step, the frozen imitation policy draws $N$ action samples. Each sample is snapped to a per-dimension grid of $K$ bins, and we add its neighbors one bin up and down in each dimension. This gives about $N(2D+1)$ candidates. The count grows linearly in $D$, and the set reaches actions the prior assigns little probability to, which addresses Q-Planning's coverage bottleneck. Two categorical critics are trained off-policy on all collected data. $Q_r(s,a)$ predicts task return. $Q_c(s,a)$ predicts future cost as a distribution over cost bins, from which we read an upper quantile $Q_c^{\uparrow}(s,a)$. Let $C_t$ be the cost actually incurred so far in the episode and $d$ the episode budget. The action is chosen by

$$a_t = \arg\max_{a \in \mathcal{A}_t} \; Q_r(s_t,a) + \beta\, u(s_t,a) \quad \text{subject to} \quad C_t + Q_c^{\uparrow}(s_t,a) \le d,$$

where $\mathcal{A}_t$ is the candidate set, $u$ is the spread (entropy) of the cost critic's predicted distribution, and $\beta \ge 0$ controls how much leftover budget is spent on uncertain actions. If no candidate satisfies the constraint, the agent executes the candidate with the smallest $Q_c^{\uparrow}$, which acts as a recovery mode.

Because the constraint uses realized $C_t$, slack accumulated early in a safe episode becomes permission to probe later. This probing is where boundary data comes from. The exploration bonus only acts inside the feasible set, so probing never knowingly plans past $d$. A per-state linear program with one constraint has an optimal solution mixing at most two actions, as in the backward-value-function approach. Over our finite set this reduces to sort-and-filter, so selection costs one batched critic pass. The cost critic's target uses an exact minimum of the upper quantile over the next state's candidates. The soft-minimum and expectation versions serve as the alignment ablation.

The guarantee is conditional. Episodes stay under budget to the extent the upper quantile truly upper-bounds future cost. We will measure how often it fails, not assume it doesn't.

Research Program

The first stage builds demonstration priors that are deliberately suboptimal but mostly safe. On each Safety-Gymnasium task we train a cost-conservative policy with CPPO-PID from Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark to a low-return checkpoint. We then collect demonstrations and fit a diffusion policy, a generator that turns noise into actions through repeated denoising, following Diffusion Policy: Visuomotor Policy Learning via Action Diffusion. A second prior family uses misaligned demonstrations: demonstrations toward the wrong goal, in the spirit of APC-RL's PointMaze setup.

The second stage runs online self-improvement with all methods sharing the same prior, environment steps, and budget.

The third stage is analysis. We track the fraction of near-boundary samples in the buffer over training, the cost critic's calibration near hazards, and how often the upper quantile under-predicts realized cost. This directly tests whether budget spending prevents the critic decay that the Feasible Dual Policy Iteration paper documents.

Baselines

The naive reference is the frozen imitation prior executed as is. It defines the ceiling to beat, and it is also the safety level any improvement must not fall below.

Filtered fine-tuning retrains the prior on self-collected episodes that were both high-return and under budget. This is the standard cheap self-improvement recipe. Q-Planning reports it stalling at 55% on real-robot stack-cups against 90% for value-guided selection, and at 30% against 80% on insert-wallet (Beyond Imitation). Those are hardware numbers from a different domain, so we rerun it here.

Unconstrained Q-Planning, and Q-Planning with a fixed scalar penalty on cost, isolate the value of a budget check over a reward penalty.

The strongest safe-exploration competitor is SAC with Feasible Dual Policy Iteration, initialized from the same prior's data. The file reports it reaching "lowest constraint violations (near-zero)" across 14 environments while matching or exceeding CPO, PPO-Lag and SAC-Lag returns. It also keeps boundary samples at roughly 10x the rate of SAC-FPI, whose rate falls below 1%. No reported per-task return found on Lacuna for it. PPO-Lag and CPPO-PID from scratch anchor the from-scratch safe-RL regime; the file reports PPO-Lag giving a 98% violation reduction at a 45% reward drop on velocity tasks. FOCOPS anchors the MuJoCo circle and velocity tasks, where it reports HumanoidCircle return 1106.1 against CPO's 671.0 under a cost limit of 50 (First Order Constrained Optimization in Policy Space). The backward-value-function method run from scratch isolates the value of the demonstration prior. APC-RL with a Lagrangian cost term represents prior-plus-RL composition.

All methods receive identical demonstration data, environment step counts, cost budgets, and an equal hyperparameter search budget of the same number of configurations, with five or more seeds each.

The key ablations remove one ingredient at a time. We drop the neighbor expansion so candidates are prior samples only. We set $\beta=0$ to remove budget spending. We use the mean instead of the upper quantile. We use a soft-minimum backup instead of the exact minimum. We replace the bins with a continuous Gaussian residual around prior samples.

Beating the field means three things at matched steps. Our method must exceed the prior's return by a clear margin. It must match or exceed SAC-FDPI's return. And it must have fewer training episodes over budget than SAC-FDPI, whose exploratory policy violates by design, with the over-budget count near that of the $\beta=0$ ablation.

Why not just…?

Why not just add a large cost penalty to Q-Planning's reward? Folding safety into a scalar reward is documented to fail in both directions. Small penalties allow catastrophic failures and large ones produce standing-still policies (Quanyi Li et al.). A penalty also has no notion of episode-level budget, so it cannot let an agent that has been careful spend its slack. The penalized Q-Planning baseline, swept over penalty values, will show whether any single penalty reaches our return-cost frontier.

Why not just filter the demonstrations and self-collected data to safe, high-return episodes and fine-tune? Supervised imitation on filtered data cannot combine pieces of different trajectories. It stays capped near the best single trajectory, as argued in Curriculum Offline Imitating Learning and seen in Q-Planning's hardware comparison. It also discards the near-violation data a safety critic needs. It is included as a baseline. If it matches us on tasks where the prior's best episodes are already near-optimal, we will report that as the regime where our method is unnecessary.

Why not just initialize SAC or PPO-Lag from the imitation policy and fine-tune with a Lagrangian or FDPI? This is the real threat, because it is simpler and can in principle reach any action. Our argument is empirical. Gradient fine-tuning of a Gaussian actor tends to move away from the prior's modes early. Safety Gymnasium documents Lagrange multipliers oscillating during training, and FDPI buys its accuracy with deliberate violations. The matched-budget comparison of training-time over-budget episodes against SAC-FDPI and prior-initialized PPO-Lag settles this. If prior-initialized FDPI matches both our return and our training-time cost, the budget-spending mechanism adds nothing and we would say so.

Why not just keep continuous actions and add a small Gaussian correction to the prior's samples? This avoids grids entirely. However, it reintroduces the variance growth as $\sigma \to 0$ shown in RN-D's Proposition 4.1 and the mode averaging shown in the Counter-Strike study. It also removes the finite set that makes the constrained choice exact. The continuous-residual ablation tests this directly.

Decisive Checks

We run on Safety-Gymnasium navigation (Point and Car robots on the Goal, Button and Push tasks) and velocity-constrained locomotion, plus the MuJoCo circle tasks used by FOCOPS and the backward-value-function method. Metrics are final return and episodic cost relative to the budget. For training we record cumulative training cost, the number of training episodes exceeding the budget, and the boundary-sample fraction in the buffer, comparable to FDPI's reported 10x ratio. We also record how often the cost critic's upper quantile underestimates realized cost.

Three outcomes would falsify the proposal. The first is if the $\beta=0$ ablation matches the full method on return and critic calibration, meaning budget spending is unnecessary. The second is if the prior-only candidate set matches the expanded one, meaning coverage was never the bottleneck. The third is if over-budget training episodes are not clearly fewer than SAC-FDPI's. A secondary check targets the alignment lens. We train on small arenas with few hazards and evaluate the cost critic's calibration on larger, denser arenas, comparing exact-minimum to soft-minimum backups. A null result there removes the alignment claim without affecting the rest.