Spending a Risk Budget Wisely: Importance-Weighted Probing for Adaptive Discrete Shields

A safety shield is a filter between a learning agent and the world. It inspects every discrete action the agent proposes, such as "turn left" or "stop", and blocks any action a model checker cannot certify as safe. When the shield is built from a learned model with uncertain transition probabilities, it blocks too much. Actions that are probably fine get refused because their uncertainty is large, and the agent never gathers the data that would shrink that uncertainty. The most direct attempt to fix this so far, Adaptive Probabilistic Shielding by Learning MDPs for Safe Reinforcement Learning, calls this the "conservativeness trap." It escapes the trap with ε-greedy unshielded exploration: every so often the agent bypasses the shield entirely. That works, but the risk it spends is spent blindly. Any blocked action can be tried, at a fixed rate, with no accounting of how much danger has been absorbed or what it bought.

We propose treating shield relaxation as a budgeted information-acquisition problem. The agent receives an explicit cumulative risk budget. At each step it decides whether to "probe", meaning execute one currently blocked but uncertain action, and which uncertain action class to probe. It makes these choices using an allocator that learns, from partial feedback, which probes most loosen the shield per unit of risk. Because the allocator only sees the outcome of the probe it actually made, it estimates the payoff of unprobed options with importance weighting, the standard bandit trick of dividing an observed outcome by the probability of having chosen it. The deliberate randomness of probing is also known exactly. The policy learner can therefore reuse probe transitions with exact likelihood ratios instead of discarding them or training on them as if they were on-policy. The core claim is that at equal accumulated safety violations, budgeted importance-weighted probing reaches the return of a perfect-model shield in fewer episodes than tuned ε-greedy unshielded exploration. It also comes with an upper bound on expected violations that ε-greedy lacks.

Core Claim and Why It Is Different

The closest work is the adaptive shielding paper above. It learns interval MDPs, meaning Markov decision processes whose transition probabilities are known only up to confidence intervals. It builds these intervals with maximum a-posteriori estimates, Hoeffding-style bounds that hold with high probability (PAC bounds), or linearly updating intervals, and synthesizes shields with the PRISM model checker. It explores outside the shield uniformly and at random. We keep its shield machinery and replace only the exploration rule, which isolates our contribution.

The second nearest work is Breaking Safety Paradox with Feasible Dual Policy Iteration. It trains a second policy that deliberately seeks constraint violations near the primal policy, and corrects the resulting replay-buffer shift with approximate importance sampling. That work motivates ours in two ways. It shows that safe agents starve their own estimators of violation data. It also shows that importance-corrected deliberate risk-taking can pay off. It differs from ours on three points. It works on continuous control with no formal shield. Its violation-seeking data collection has no explicit budget. Its importance weights are approximated, whereas ours are exact because the probe distribution is chosen by us.

The allocation idea borrows directly from The Cost of Information: Phase Transitions in Contextual Bandits with Paid Observations. In that paper a learner pays to observe feedback, and regret shifts from order $T^{1/2}$ to $\Omega(T^{2/3})$ unless the budget is large enough. In our setting the "payment" for an observation is risk rather than money. That result is a warning: when information is costly, how the budget is spent matters to first order, and a uniform rule like ε-greedy is unlikely to be the right shape.

Research Program

The system has three parts on top of an existing adaptive shield.

The first part is a probe-eligibility rule. An action blocked in state $s$ is eligible for probing only if its PAC upper bound on one-step violation probability, $\bar u(s,a)$, is below a per-probe cap $\kappa$. This means probes target uncertain actions, not known-dangerous ones, which is the key departure from unshielded ε-greedy.

The second part is the allocator. We group eligible actions into probe classes, for example by the interval MDP parameter whose width is blocking them. The allocator maintains an exponential-weights distribution $q_t$ over these classes. It also fixes a probe rate $\rho_t$, the chance of probing at step $t$. The rate is set so that expected worst-case risk stays within budget $B$:

$$\sum_{t=1}^{T} \rho_t \, \mathbb{E}_{c \sim q_t}\big[\bar u(s_t, a_c)\big] \le B.$$

Here $a_c$ is the action probed from class $c$. After a probe of class $c_t$, the allocator records a gain $g_t$: the reduction in the shield's blocked probability mass on the agent's recent state distribution after the next shield resynthesis, divided by the risk spent. It forms the importance-weighted estimate $\hat g_t(c) = g_t \mathbf{1}[c = c_t] / q_t(c_t)$ and updates exponential weights in the manner of Bubeck and Cesa-Bianchi's synthesis. The problem is non-stationary, because gains fall as intervals shrink and the agent's visitation shifts. Adversarial-bandit estimators, not stochastic ones, are the right tool for this. To control variance we mix $q_t$ with a uniform floor, the usual fix for division by small probabilities.

The third part is exact off-policy correction for the policy learner. The behavior at each step is a known mixture of three things: the policy's proposal, the shield's deterministic replacement of blocked proposals, and the probe distribution. We compute the exact probability of the executed action under this behavior. We also compute its probability under the target, which is the shielded policy with no probing. For probe transitions the target probability can be zero. Such transitions update the interval model and the value estimate of the probed action, but they do not enter the policy's return-based update. Following Conditional Importance Sampling for Off-Policy Learning, which shows that conditioning weights on coarser quantities removes variance caused by redundant actions, we compute ratios on the executed action rather than the proposed one. The shield maps many proposals to one executed action, which is exactly the kind of redundancy that paper removes.

We will also derive a simple accounting result. Under the eligibility rule, expected cumulative violations from probing are at most $B$ with probability $1-\delta$, where $\delta$ is the confidence level of the PAC intervals. The bound follows from a union bound over the intervals plus the budget constraint above. We state it as a guarantee about what ε-greedy exploration cannot promise, not as a deep theorem.

Baselines

The do-nothing reference is the fully robust adaptive shield with no exploration outside it, as in Adaptive Probabilistic Shielding with probing disabled. It should show the conservativeness trap: low violations and a return plateau below the oracle.

The strongest existing method is the same paper's adaptive shield with ε-greedy unshielded exploration. We run it with the authors' interval estimators and shield resynthesis schedule. We tune ε, including decaying schedules, on the same grid and seed budget we give our method, and we match its total violations to ours by adjusting ε so that comparisons are made at equal risk. That paper reports that its adaptive agent outperformed a perfect-model "Oracle" shield on Aircraft collision avoidance, and that the largest gains came after the first model update at roughly 1,000 episodes. We found no reported numeric return or violation count for it on Lacuna. We will therefore reproduce it on the same environments before claiming anything. Beating it means reaching oracle-shield return in fewer episodes at matched cumulative violations, or reaching equal return with fewer violations, across five seeds with non-overlapping confidence intervals.

The perfect-model oracle shield gives an upper reference for safe return.

Two ablations isolate the key ingredients. The first keeps our eligibility rule and budget but allocates probes uniformly across classes. It tests whether the importance-weighted allocator matters beyond simply restricting probes to uncertain actions. The second keeps our full exploration scheme but trains the policy on executed actions with no ratio correction, or with ratios on proposed actions. It tests whether the exact executed-action correction matters. A Lagrangian method run with only a reward-side cost signal (PPO-Lag, the constrained baseline in Safety-Gymnasium, which reports a 98% violation reduction over PPO on velocity tasks at a 45% reward cost) gives an unshielded reference point.

Why not just…?

Why not just use action masking and skip importance weights? Renormalizing the policy over the shield's safe set is the standard remedy for training on shielded actions, and for the part of the problem without probing it is essentially correct. We concede this, and our claim does not rest on it. Once probing is added, the behavior policy is no longer the masked policy, and probe transitions must either be discarded or reweighted. Our second ablation measures how much is lost by discarding them. If masking plus discarding matches our full method, the correction component is unnecessary and the contribution reduces to the allocator.

Why not just use a less conservative shield, for example MAP intervals instead of PAC bounds? This is a real threat. An optimistic shield loosens itself without any explicit probing. The adaptive shielding paper already offers MAP estimation. Its cost is that nothing bounds the risk: violations occur wherever the point estimate is wrong, unaccounted for. We will run the MAP-interval shield as an additional baseline at matched violations. If it matches our return at equal risk, budgeted probing adds value only through its guarantee, and we will report that plainly.

Why not just tune ε-greedy more carefully? A decaying ε tuned per environment might approximate a good allocation. The paid-observations lower bound suggests that under costly information the allocation shape matters, and ε-greedy is blind to which blocked action it tries, known-dangerous ones included. The matched-risk comparison with a tuned ε grid settles this directly.

Why not just penalize violations in the reward? Reward shaping produced significant training violations and sometimes failed to converge in Safe Exploration in Continuous Action Spaces. Penalties also produce "safe but useless" behavior when set large, as noted by Quanyi Li et al.. Penalties also act only after the damage is done, so we include them only as a reference.

Proposed Experiments

The primary testbed is the five shielding environments from the adaptive shielding paper: Aircraft ($|S|=1665$), Antlion, Sinkholes, Crossroads and Gravity well. These have known topology, unknown probabilities and PRISM-synthesizable shields, so we inherit the setting exactly. Metrics are episode return relative to the oracle shield, cumulative violations over training, Expected Maximum Consecutive Cost steps (the exploration-severity measure from Revisiting Safe Exploration in Safe Reinforcement learning), and the fraction of the oracle's permitted actions the learned shield allows over time. As a secondary test of scale, we apply the method to the multi-agent gridworlds of Shield Decentralization for Safe Multi-Agent Reinforcement Learning. There, centralized shields permit an average of 23.3 joint actions and decentralized ones 22.07. We add transition uncertainty to test whether probing recovers the permissiveness of a full-knowledge shield.

The decisive check is a risk–return frontier. We sweep the budget $B$ for our method and ε for the baseline, then plot episodes-to-oracle-return against cumulative violations. The proposal succeeds if our frontier dominates the tuned ε-greedy frontier and the uniform-probe ablation on at least four of five environments. A second decisive check tests the budget guarantee: realized probe violations should stay under $B$ in at least a $1-\delta$ fraction of seeds, while ε-greedy's violations at matched return should vary widely across seeds. If the MAP-interval shield alone traces the same frontier, we will conclude that the conservativeness trap is better handled by estimation than by exploration.