Learning the Safety Margin: Strict Constraint Satisfaction Without Knowing Slater's Constant

In safe reinforcement learning, an agent maximizes reward while keeping an expected cost, such as collisions or energy use, under a budget. Most algorithms, and all of the tightest sample-count guarantees, depend on one number the practitioner rarely knows. That number is the Slater margin $\zeta$: how far below the budget the safest possible policy can keep its cost. Theory says that guaranteeing zero violation takes on the order of $1/(\epsilon^2\zeta^2)$ samples, where $\epsilon$ is the allowed suboptimality. The same theory shows no algorithm can do better. But the algorithms that reach this rate tighten the budget by an amount set from $\zeta$. In practice $\zeta$ is guessed, and a guess that is too optimistic yields violations while one that is too pessimistic yields a timid, low-reward policy.

This note proposes that the agent should measure its own safety margin while it learns. It certifies a lower bound on $\zeta$ from data by searching over halving guesses, and uses that certificate to set both the budget tightening and the cap on the penalty weight. The central claim is that this costs only a logarithmic factor. Certifying a margin of size $\zeta$ needs about $1/\zeta^2$ samples, which is dominated by the $1/(\epsilon^2\zeta^2)$ that strict feasibility already requires. The agent can therefore match the known-$\zeta$ rate without knowing $\zeta$. When the margin is truly zero, it degrades gracefully to the Slater-free relaxed guarantee and reports that strict safety cannot be certified.

Core Claim

The strict-feasibility results in the file share a structure. Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs proves a matching $\widetilde{\Theta}(SA(B+H)/(\epsilon^2\zeta^2))$ bound with a generative simulator, reaching it by "artificially tightening the constraint threshold in the empirical model." Near-Optimal Sample Complexity for Online Constrained MDPs carries the $\widetilde{O}(SAH^5/(\epsilon^2\zeta^2))$ rate to online exploration. Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model gives the linear-feature lower bound. These papers motivate this proposal and supply its template: they establish that $1/\zeta^2$ is the right price.

As summarized, their tightening is expressed through $\zeta$. The first step of the project is to verify from the proofs whether $\zeta$ is a required input. If it is not, the theoretical contribution below shrinks to the deep-RL instantiation. The Slater-free line takes a different route and gives up zero violation. That line includes Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints (policy search over an estimated safe set), Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints (optimism in parameters, primal, and dual), and APMPO ($\widetilde{O}(K^{3/4})$ when $\zeta=0$). All three bound cumulative or positive violation rather than certifying a strictly feasible output. The proposal sits between the two lines: it keeps the strict guarantee and removes the oracle knowledge.

Formally, write $\zeta = c - \min_\pi V_C^\pi$, where $c$ is the cost budget and $V_C^\pi$ the expected cost of policy $\pi$. Guess $\zeta_j = 2^{-j}$ for $j = 0, 1, 2, \dots$. In round $j$, collect enough data to compute a pessimistic upper confidence bound $\overline{V}_C$ on the cost of the best cost-minimizing policy, accurate to $\zeta_j/4$. Accept $\hat\zeta = \zeta_j/2$ at the first round where

$$\overline{V}_C \le c - \zeta_j/2 .$$

Round $j$ costs about $1/\zeta_j^2$ samples, since a cost estimate accurate to $\zeta_j/4$ needs that many. These costs form a geometric series, so the search ends after $\widetilde{O}(1/\zeta^2)$ samples with $\zeta/4 \le \hat\zeta \le \zeta$ with high probability. Running the known-$\zeta$ strict algorithm with $\hat\zeta$ then gives $\widetilde{O}(1/(\epsilon^2\zeta^2))$ total, up to constants and logarithms. If the budget $N$ runs out before any certificate, the algorithm returns the relaxed-feasibility policy, whose cost does not depend on $\zeta$, together with the statement "strict feasibility not certifiable at margin above about $1/\sqrt{N}$". That statement is the honest output on the boundary case, where the lower bound says nothing better is possible.

Research Program

The theory has two parts. The first proves the adaptive bound in the tabular online episodic setting, building on the doubling-batch, optimism-plus-caution algorithm of Near-Optimal Sample Complexity for Online Constrained MDPs. The subtle point is data reuse. Samples collected during the margin search must be reusable in the main phase, or the geometric-series argument must absorb them. The certificate must also be pessimistic about cost (an upper bound), whereas the main algorithm is optimistic about reward. We will check that combining the two does not add a factor in $H$.

The second part extends the argument to linear CMDPs with a generative model, using the core-set and decoupled cost-evaluation machinery of Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model. That machinery is suited here because its separate cost-evaluation subroutine is exactly what a margin certificate needs.

The deep instantiation targets the practical failure described in Safety Gymnasium: Lagrangian agents are "reckless" when the penalty is too low and "too scared to move" when it is too high. We add a second critic to an off-policy constrained actor-critic. This critic is trained on the same replay buffer, so it needs no extra environment interaction, and it estimates the minimal achievable cost with a pessimistic ensemble upper bound. Its certified margin $\hat\zeta$ sets two quantities. The first is the budget tightening, set to a constant times $\hat\zeta$. The second is the penalty-weight cap, set to $O(1/\hat\zeta)$, following the duality bound $\lambda^* \le O(1/\zeta)$. The certificate is refreshed periodically and can only move down, never up, unless new evidence survives a confidence test. This addresses the concern in the file that off-policy estimation errors near the boundary can label unsafe behavior as safe.

Baselines

The naive reference point is a Lagrangian method with an untuned default penalty learning rate and no tightening: PPO-Lag from the SafePO library shipped with Safety Gymnasium. That paper 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." This is the anchor figure for the deep experiments, and we will reproduce it before comparing.

The strongest competitor is the known-$\zeta$ oracle: the same strict-feasibility algorithm given the true margin. In synthetic MDPs we can compute the true margin exactly; in Safety-Gymnasium we approximate it by an expensive offline cost-minimization run. The oracle is the right bar because our claim is to match it. We beat the naive reference if we match the oracle's samples-to-certified-policy within a small constant factor across a sweep of $\zeta$.

The tuned-practice competitors are CPPO-PID and a grid search over the tightening amount. The grid search is charged the samples of every grid point, since that is what tuning costs in deployment. We also include APMPO and WC-OPS on the synthetic tabular and linear environments ($|S|=5,|A|=3$ and $|S|=100,|A|=3,d=5$) from the APMPO evaluation. The file gives only rates for these methods, with no reported trajectory numbers on Lacuna, so we will rerun them ourselves.

Two ablations isolate the key ingredient. The first uses a fixed wrong guess of $\zeta$, both too large and too small. The second uses the certified $\hat\zeta$ for the tightening only, with an uncapped penalty weight, to separate the two uses of the margin. All methods share environment seeds, interaction budgets, network sizes, and an equal hyperparameter-tuning budget counted in environment steps.

Why not just…?

Why not just accept small violations, since relaxed feasibility is free of $\zeta$? For many applications this is the right answer, and our algorithm returns exactly that policy when it cannot certify a margin. But Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs proves that zero violation needs $\Omega(1/\zeta^2)$ samples, so relaxation does not solve the strict problem; it changes it. Our experiments report both regimes and will show where relaxed policies' deployed cost actually exceeds the budget.

Why not just tune the tightening by grid search? This is the real threat. With a coarse logarithmic grid, it costs roughly a log factor more samples, which is close to what we claim. The difference is that grid search needs the full $1/(\epsilon^2\zeta_j^2)$ run at each grid point, while our margin search spends only $1/\zeta_j^2$ per guess. The predicted gap is therefore a factor near the grid size. If the measured gap is under 1.5x across the $\zeta$ sweep, the deep contribution is not worth its complexity, and we will say so.

Why not just use a PID-controlled or bandit-selected penalty weight? Evidence in Truly No-Regret Learning in Constrained MDPs shows that unregularized primal-dual methods can suffer linear strong regret, and PID adds no guarantee as $\zeta \to 0$. O3SRL selects the penalty weight from discrete arms using EXP3. It works offline and keeps cost at or below the limit across DSRL tasks at $\kappa=5$, but it provides no online sample guarantee, and the range of its arms implicitly encodes a guess about $\zeta$. In the synthetic sweep, CPPO-PID and an online bandit-over-penalty variant are run under the same step budget. We expect them to fail specifically at small $\zeta$, where the needed penalty grows as $1/\zeta$.

Proposed Experiments

The decisive check uses the synthetic hard instances of the CAMDP paper and the APMPO tabular and linear environments, with $\zeta$ swept over $\{0.2, 0.1, 0.05, 0.02, 0.01, 0\}$. We measure the number of samples until the algorithm outputs a policy that is both strictly feasible, meaning its true cost is at most the budget, and $\epsilon$-optimal. On a log-log plot against $\zeta$, the adaptive method should show a slope near $-2$ and sit within a constant factor of the oracle. At $\zeta=0$ it should never certify, and its relaxed output should match the Slater-free baselines.

In Safety-Gymnasium velocity and navigation tasks, we vary $\zeta$ by moving the cost budget toward the minimum achievable cost. We then report normalized reward, the fraction of evaluation episodes above budget, and environment steps to first certified policy, against PPO-Lag, CPPO-PID, grid-searched tightening, and the approximate oracle.

A secondary check tests the off-policy certificate itself. We compare $\hat\zeta$ with the approximate true margin over training and count how often it ever overestimates the margin, which is the failure that would cause violations. The proposal fails if the certificate overestimates in more than a small fraction of seeds, or if grid search matches it within 1.5x.