Spending the Safety Budget on Information: Boundary-Probing Exploration for Discrete-Action Safe RL

A reinforcement learning agent that must respect a safety limit faces a problem that does not go away as it gets better. The safer it becomes, the less often it goes near danger. So it collects less evidence about where danger actually starts, and its estimate of the safe boundary drifts. Breaking Safety Paradox with Feasible Dual Policy Iteration names this the safety paradox. Most safe-RL agents make it worse because one policy does two jobs. It must earn reward reliably, and it must also go looking for information. Any caution added for the first job suppresses the second.

We propose splitting these jobs between two policies that share one replay buffer. A task policy learns only from task reward and acts only through actions it is confident are safe. A second policy, the boundary prober, is rewarded for one thing: shrinking the agent's uncertainty about which actions are dangerous. It is the only part of the system allowed to spend the episode's safety budget, and it spends that budget on information rather than reward. We restrict attention to discrete action spaces. Although discrete actions are often seen as a limitation, they make this design exact. With finitely many actions, the agent can evaluate its uncertainty-aware cost estimate for every action in every state. It needs no linearization, no single-active-constraint assumption, and no hand-built formal model of the environment.

Core Claim

The claim is that in discrete-action constrained problems, one change fixes the safety paradox without adding violations or samples. A decoupled explorer, whose objective is to reduce uncertainty in the cost critic and whose risky actions are paid for out of the explicit safety budget, should keep the cost estimate calibrated as the task policy becomes safer. Here a constrained Markov decision process means maximizing return subject to expected discounted cost staying below a budget $d$. A cost critic is a learned estimate of future cost for each state-action pair.

The observable consequence is fewer environment steps to reach a given return and lower cumulative cost during training. The decisive check is that the cost critic's calibration should not degrade late in training, which is exactly when a monolithic agent's calibration should degrade.

What is new relative to the closest work is the explorer's objective and its budget accounting. Separate task and exploration policies already exist. So does masking unsafe discrete actions with a learned survival critic.

Mechanism

The agent keeps an ensemble of $K$ cost critics $Q_c^{(k)}(s,a)$, with mean $\bar Q_c(s,a)$ and disagreement $\sigma_c(s,a)$. Because the action set $\mathcal{A}$ is finite, it computes two exact per-state action sets by enumeration. The first is the set of actions that are certainly within budget. The second is the set of actions whose status is genuinely unknown:

$$\mathcal{A}_{\text{safe}}(s)=\{a\in\mathcal{A}:\bar Q_c(s,a)+\kappa\sigma_c(s,a)\le d\},\qquad \mathcal{A}_{\text{amb}}(s)=\{a:\bar Q_c(s,a)-\kappa\sigma_c(s,a)\le d<\bar Q_c(s,a)+\kappa\sigma_c(s,a)\}$$

Here $\kappa$ sets the confidence width. With several cost signals, the same test is applied to each, and the sets are intersected. This is how the design avoids the single-active-constraint assumption of Safe Exploration in Continuous Action Spaces.

The task policy is a double-Q learner with the same network capacity as all baselines. It trains off-policy on task reward alone and acts greedily within $\mathcal{A}_{\text{safe}}$. If that set is empty, it takes the action with the lowest upper-confidence cost, and we log the event as a dead end.

The boundary prober is a second Q-learner trained on an intrinsic reward, $r^{\text{probe}}_t=\sigma_c(s_t,a_t)-\sigma_c'(s_t,a_t)$. This is the drop in ensemble disagreement on the visited pair after the critic update, a cheap proxy for information gained about the cost function. The prober may choose from $\mathcal{A}_{\text{safe}}\cup\mathcal{A}_{\text{amb}}$, but only under a running budget constraint:

$$C_t+\bar Q_c(s_t,a)+\kappa\sigma_c(s_t,a)\le d$$

Here $C_t$ is the cost already incurred in the episode. Hard catastrophic events, such as episode-terminating crashes, get their own mask that the prober can never override.

At each step, a scheduler decides who acts. It hands control to the prober with probability proportional to the fraction of the remaining budget. It hands control back to the task policy whenever the ambiguous set is empty. This makes the handover depend on the state of uncertainty rather than on a fixed interval. It is a direct response to the sensitive reset intervals reported for Efficient Reinforcement Learning via Decoupling Exploration and Utilization.

Relation to Prior Work

The closest work is Decoupled Learning of Environment Characteristics for Safe Exploration. It splits a gridworld agent's value into a survival network and a task network, and it restricts ε-greedy exploration to actions the survival network deems safe. We keep its discrete masking. We differ in three ways. Its exploration is undirected and never probes the boundary. Its mask is a point estimate rather than an uncertainty-aware one. And it was tested only in an 11×11 grid, where the authors report high value variance and leave scaling open.

Safe Reinforcement Learning via Shielding obtains zero violations in discrete domains by synthesizing a shield from a formal model. We use it as an oracle upper bound where such a model exists, not as a competitor we must beat. Our learned mask needs no model.

Three decoupling methods supply our architecture and are all unconstrained. Decoupled Exploration and Exploitation Policies for Sample-Efficient Reinforcement Learning trains a task policy and a pseudo-count explorer and samples from their product. OPARL pairs optimistic and pessimistic actors. Bigger, Regularized, Optimistic separates an optimistic exploration policy from its target policy. All three explore toward novelty. All three were validated on continuous control, and the file flags discrete transfer as open. We change what the explorer seeks, from novel states to ambiguous safety status, and we change what it may spend, a budget rather than unbounded risk.

Safe Exploration via Policy Priors also balances optimistic reward seeking against pessimistic safety. It needs a safe prior policy and a calibrated world model, and it targets continuous control. We need neither a prior nor a dynamics model.

Several papers constrain the design rather than motivate it. Reward Prediction Error as an Exploration Objective in Deep RL and DEEP show that adding exploration bonuses to the task reward distorts the task value. This is why the probe reward lives in a separate learner. First Order Constrained Optimization in Policy Space and the Lagrangian methods are on-policy and discard data after each update. This is why we build off-policy.

Research Program

We would build the agent on a shared replay buffer with ensemble cost heads, $K=5$, and a dueling Q-network backbone. We would then study it along three axes.

The first axis is calibration over time. We track the expected calibration error of $\bar Q_c$ against realized discounted cost, on a held-out set of states that includes near-boundary states gathered by a fixed probing script. We plot it against training step. The safety paradox predicts that this error rises for monolithic agents as their violation rate falls. Our claim predicts that it stays flat.

The second axis is where the budget goes. We log what fraction of incurred cost is spent by the prober versus the task policy, and whether prober-spent cost leads to later reductions in $|\mathcal{A}_{\text{amb}}|$.

The third axis is scaling with action cardinality. Uniformly discretizing a $d$-dimensional control with $k$ bins gives $k^d$ actions. We therefore vary $k$ on two-dimensional controls, from 3×3 to 9×9, to find where exact enumeration stops paying off. We do not claim the method extends to high-dimensional discretizations.

Baselines

The naive reference point is an off-policy double-Q agent with ε-greedy exploration and a fixed reward penalty for cost. MetaDrive shows this design yields either absorbed violations or "safe but useless" behavior depending on the penalty. We sweep the penalty over the same tuning budget as every other method, reporting the best reward-feasible setting.

The standard constrained baseline is PPO-Lagrangian, run with the same environment-step budget. Its discrete-action version uses a categorical policy head. Safety Gymnasium reports that on velocity tasks PPO-Lag achieved "a 98% reduction in safety violations compared to standard PPO, with only a 45% drop in total reward." On discretized Safety-Gymnasium navigation tasks there is no reported result found on Lacuna for PPO-Lag, so we produce our own. We also run an off-policy DQN-Lagrangian, so that on-policy data waste is not the only difference.

The strongest competitor is a masked version of DEEP. It has DEEP's task policy and pseudo-count explorer, with the product behavior policy, and both are restricted to our uncertainty-aware $\mathcal{A}_{\text{safe}}$ mask built on the same cost ensemble. This is the baseline most likely to match us. It already has decoupling, directed exploration, off-policy reuse, and our exact discrete mask. It lacks only the boundary-probing objective and the budget accounting. No reported result was found on Lacuna for DEEP in any constrained setting.

Two ablations isolate our key ingredient. The first gives the probe reward to a single agent, added to its task reward, which is the inline version. The second keeps our prober but forbids it from using $\mathcal{A}_{\text{amb}}$, so it can only probe from certified-safe actions.

Where a formal model exists, the formal shield of Safe Reinforcement Learning via Shielding, on top of DQN, serves as the oracle. That paper reports "zero safety violations" and optimal learning in Pacman from episode 1.

Every method gets the same network size, 10 seeds, the same environment-step budget per benchmark, and a 20-configuration random search for hyperparameters. Beating a baseline means one of two outcomes at matched final cost. Either we reach 80% of the best final return with at least 30% fewer environment steps, or we reach equal return with lower cumulative training cost. In both cases the confidence intervals must separate across seeds.

Why not just…?

Why not just mask a single agent's actions with a learned safety critic, as Van Molle et al. did? This is the simplest system that is safe during exploration, and in small grids it may be enough. The file records that this approach showed high action-value variance and was never tested beyond an 11×11 grid. More fundamentally, its ε-greedy exploration within the mask never deliberately visits ambiguous actions, so it should suffer the safety paradox. The calibration-over-time measurement tests this directly. If its calibration error stays flat, the paradox is not biting in these domains and our explorer is unnecessary.

Why not just take DEEP or OPARL and bolt on the mask? This is the real threat, which is why masked DEEP is our primary baseline. A novelty-seeking explorer may visit boundary regions often enough by accident. Our argument that it will not is specific. Pseudo-counts reward any unvisited state, while most unvisited states in a navigation task are far from hazards. Under a pessimistic mask, the novelty explorer also cannot take ambiguous actions at all. If masked DEEP matches our return, cumulative cost, and calibration curves, the boundary-probing objective adds nothing. We would report that result, and the contribution would reduce to showing that DEEP transfers to discrete safe RL.

Why not just add a cost-uncertainty bonus to one agent's reward? It is one network instead of two. The evidence from Reward Prediction Error as an Exploration Objective in Deep RL and DEEP's "exploration tax" says that mixing exploration bonuses into task values biases the task policy. In a safe setting, that bias pulls the task policy toward the hazard boundary. The inline ablation measures this as higher task-policy cost at matched return.

Why not just use a Lagrangian method and accept some training violations? Lagrangian methods satisfy the budget only near convergence. The widely used ones are on-policy, and the file notes that FOCOPS discards rollouts after each projection. Both PPO-Lag and DQN-Lag are in the comparison, with cumulative training cost as a primary metric.

Proposed Experiments

The benchmarks follow the file. The first is Circle2D, all four levels, from Revisiting Safe Exploration in Safe Reinforcement learning. There we report Expected Maximum Consecutive Cost steps (EMCC), cost rate, and return. The paper's observation that CPO and WCSAC had equal cost rates but different EMCC shows EMCC captures exploration-time risk that averages hide. No numeric EMCC values were found on Lacuna.

The second is Safety-Gymnasium. We use PointGoal1, PointButton1, CarGoal1, and PointCircle1, with the two-dimensional action discretized into $k\times k$ bins and a 1M-step budget.

The third is the Pacman and gridworld domains of the shielding paper, for comparison against the oracle. The fourth is MetaDrive, with steering and throttle discretized by us, where we report crash rate and success rate on unseen maps.

The decisive checks come in order. First, cost-critic calibration error in the last third of training must be lower for our method than for masked DEEP and the single-agent mask. If it is not, the mechanism is wrong regardless of return. Second, the prober's spent budget must be followed by shrinkage of the ambiguous set, which shows the budget buys information. Third, at matched final cost, steps-to-80%-return must beat masked DEEP. On gridworlds, the gap to the formal shield indicates how much a learned mask costs relative to a perfect model. The $k$ sweep shows where exact enumeration stops being affordable. We expect that point to arrive well before the $k^d$ blow-up of high-dimensional control, which bounds the claim to low-dimensional discrete regimes.