Occupancy-Based Certificates for the Relative Safety of Reinforcement Learning Agents
We study how to upper-bound the expected episodic cost of a candidate reinforcement-learning policy A relative to a trusted baseline B, using rollouts but no environment model. On a finite observation alphabet where expected per-step cost is policy-invariant given the symbol, J(A) ≤ J(B) + T TV(d_(A), d_(B)), with no i.i.d. assumption over time. For nondecreasing costs in an ordinal risk level, a one-sided Kolmogorov–Smirnov certificate restricted to cost-onset thresholds can be sharper; its finite-sample empirical-Bernstein slack has no $\sqrt K$ term. We show that cost sufficiency is necessary, cost labels on candidate symbols do not help, and a K-dependent sampling term is necessary for the total-variation certificate at T = 1. On Constrained CartPole, where cost sufficiency holds exactly, no finite-sample certificate was violated in 405 evaluations. At 2,000 episodes, the monotone empirical-Bernstein bound is 4.3–8.8 cost units for policies with realised cost below 0.8 (ceiling 200). On Safety-Gymnasium, a cost-relevant alphabet approximately restores sufficiency on PointGoal1, while a generic k-means alphabet does not. In a retrospective 24-cell validation split, no bound falls below the independent reference mean’s 95% lower confidence limit; the median bound is 4.53 times reference cost, so this is a robustness check rather than a preregistered validation. On one additional PointGoal1 training seed held out from rule development, the candidate mean was 70.96 and the bound was 273.80; this is a case study, not a coverage validation. Across five candidates on that seed, all-threshold bounds were 288--500 and exceeded each independent reference interval; they were looser than pilot-selected bounds. Pilot-size bootstraps on CarGoal1 show that the selected window matches the 100-episode fit in all resamples with 25–100 episodes, but onset selection varies and 50-episode bounds exceed the cost ceiling. CartPole bootstrap screening flags all agents exceeding margins of 1, 5 or 10 cost units, with high false-rejection rates at small sample sizes. A variance-adaptive empirical-Bernstein importance-sampling bound, like the range-only bound, is vacuous at horizon 200 for the policies studied.