Robustness margin of the OmSh certificate¶

How much model error can the deployed OmSh certificate absorb before the anytime guarantee of the paper (thm:anytime_safety) stops being instantiable around it? This note covers the construction, the solver, and the results.

The construction¶

OmSh certifies each action against every retained level l >= f through that level's induced point kernel P_l(. | s, a): the learned world model composed with the imagined level policy. The padded certificate keeps exactly that set and adds a total-variation ball of radius eps around each level's row, inside the simplex over the row's listed (legal) support:

V_f(s) = min_a max_{l >= f} sup_{P in B_eps(P_l(.|s,a))} E_P[V_f].

At eps = 0 this is _build_floor_budget_lower_bounds, the deployed certificate, and the solver reproduces the cached bundle's bounds at reset to six decimals.

Coverage (as:anytime_coverage) needs the true next-state law inside the padded set at every step. That holds under two conditions:

• A1, world model: TV(learned kernel, true kernel) <= eps_WM on the joint rows used. It carries through each level's opponent mixture by convexity.
• A2, opponent: at each step some retained level l >= f_t has TV(real opponent action law, pi_l) <= eps_OM at the current state.

The shield side is worst case over all retained levels, and the assumption side needs only one level. So the radius pads every level, but coverage needs just one ball to contain the truth, and the matching level may change over time. The floor is where "all levels" bites: A2 fails if the opponent is near no level (misspecification) or if the floor rises past the level the opponent resembles (overshoot). Only overshoot can be controlled statistically, through an anytime-valid composite test that rejects a level only once the opponent is shown to be farther than eps from it.

By the triangle inequality, a uniform radius eps >= eps_WM + eps_OM suffices. The margin is the largest uniform eps whose reset demand still fits the campaign budget.

Mixtures of levels: at eps = 0, robustness to every level also covers mixtures, since the certificate is linear in the law. With slack, padding each level separately is not obviously equivalent to padding the mixtures, and nothing here relies on it.

Solver (src/shield/ambiguity/margin.py)¶

• compile_bundle flattens every level's focal kernel into one CSR over rows (level, state, action). Levels >= f are then a contiguous suffix.
• padded_row_values is the exact TV-ball supremum, vectorised. It moves at most eps of mass from the lowest-value entries into one argmax entry, with extended-precision prefix sums. It agrees with tv_ball_sup row by row (tests/test_robust_margin.py). The recipient never needs to spill, because the donors run out first.
• MarginSolver.demand is two-sided. The upper iterate starts at 1 and stays a super-solution, so upper <= p at reset certifies feasibility. The lower iterate starts at 0 and stays below the value, so lower > p certifies infeasibility. It stops as soon as either side decides. Warm starts are sound because the value is monotone in eps: an upper iterate at a larger radius bounds a smaller one, and a lower iterate at a smaller radius bounds a larger one.
• The almost-sure-safe set uses the full listed support when eps > 0, because a ball can move mass onto entries the point kernel gives about zero. At eps = 0 it uses the deployed mass_tol convention.
• margin brackets geometrically from 1e-3 by factors of 4, then bisects eight times. An undecided evaluation counts as refuted, so certified is conservative.
• level_tv gives the per-row TV between the learned and oracle bundles (same levels, exact versus learned world model), plus any exact-support mass the learned row does not list, which no radius could cover.

scripts/compute_robust_margins.py <env...> runs everything per shielded agent and writes exports/robust_margin/<env>.json. Run it from the repository root. The bundle staleness check compares content stamps only, because recorded paths are absolute cluster paths.

Cost: exact mode on Pursuit (403,575 entries) takes about 16 s per floor. A sort-free alternative is available if the large graphs need it: an operator that dominates the exact one, iterated from above, still bounds the value from above, because only the exact operator has to be monotone. Here that would be base + min(eps, 1 - m_max)(vmax - vmin). It has not been needed yet.

Padded runtime shield (src/shield/padding.py)¶

shield_padding_radius (notebook config, default 0) runs OmSh with the padded certificate. load_or_build_transition_shield_bundle(padding_radius=r) pads the cached point bundle in memory; the on-disk cache stays the point bundle. Three pieces change together, and all three must, or the certificate is not inductive:

1. pad_transition_shield_bundle replaces floor_budget_lower_bounds with MarginSolver.certificate(f, r) at every floor, iterated until no state moves by vi_tol. Every iterate is a super-solution, so any budget at least W_f(s) keeps an admissible action.
2. inspect_shield_state costs each level's action row as padded_expectation(beta, P_l(.|s,a), support, r), the TV-ball supremum on the row's listed successors. It keeps those supports in per_level_action_supports and sets padding_radius on the inspection.
3. inspect_shield_decision allocates successor budgets with padded_egalitarian_fill. It shifts successors uniformly, as in _robust_egalitarian_fill, but the shift is found by bisection on the padded inequality, which is monotone in the shift.

tests/test_shield_padding.py::test_padded_decisions_keep_the_runtime_certificate checks the invariant of def:anytime_runtime_certificate on random games: from any budget q >= W_f(s), the decision is feasible, successor budgets dominate W_f, and every retained level's padded expectation of them stays within q.

Other details:

• Bayesian mixing is rejected under padding, because the construction certifies against every retained level.
• Padded runs get the artifact stem ippo_shielded_padded_r<token>, with label suffix Padded (shield_experiment_spec). The campaign summarizer files them as omsh_variant, never as the primary OmSh row.
• build_shielded_env_factory_from_config reads the radius from the manifest config, so frozen re-evaluation rebuilds the same padded shield.
• Bertrand smoke test (radius 0.3): action 1's cost at reset rises from 0.565 to 0.865, and only action 0 fits the 0.2 budget either way. So padding leaves Bertrand's admissible set, and its training, unchanged.

Gap found in the existing radius plumbing¶

build_transition_shield_bundle(joint_row_radius=...) pads each level's own value iteration, but _build_floor_budget_lower_bounds ignores the radius for floors with two or more levels. Only the single-level last floor inherits it, through budget_lower_bounds. No deployed run uses joint_row_radius, since the count-centred study went through certificate.py. src/shield/padding.py pads the floor iteration and the runtime instead; joint_row_radius remains a per-level diagnostic only.

Results (successor_campaign_v1 bundles)¶

Reading:

• Bertrand, Chicken and Congestion have a surely-safe action from reset under every listed successor, so the guarantee holds at any radius. Any probabilities on the legal support, and any opponent behaviour on it, keep reset demand at 0. This matches the exact arbitrary-opponent audit. Their learned world model is exact (TV 0), so A1 is free there.
• Gathering is the same case, even though its learned kernel is inexact: every one of its 1,796 graph start keys has a surely-safe action under the listed support, and no exact-support mass is missing from the learned rows. The certificate covers the reset support as enumerated in the graph, which the environment registry classes as sampled for Gathering. "Feasible at any radius" says the padded certificate exists. It does not say what padding costs in reward: a padded runtime shield admits fewer actions, and only training with it would measure that.
• In Pursuit the margin at floor 0 is about 0.0022, against reachable-row world-model errors up to 0.43 (p95 0.13). A uniform padded certificate around the learned kernel is infeasible by roughly two orders of magnitude. Even with the exact kernel, only 0.0022 of slack remains for the opponent. The margin grows with the floor (0.0059, then 0.021), so a raised floor is much less fragile. At the audited radii, the padded certificate needs budgets of 1.0 (max error), 0.71 (p95) and 0.38 (mean), so a uniform radius around the learned kernel is not a usable instantiation.

Markov Stag Hunt (177,253 states, 22.5M entries; 6 min and 15.5 GB on amd24) matches Gathering. All 1,425 start keys have a surely-safe action under the listed support, and no exact-support mass is uncovered.

What "feasible at any radius" does and does not give¶

Five of the six environments have reset demand 0 under the listed legal support. The anytime certificate therefore exists at any radius, up to 1, the whole simplex over the support. That is exactly the arbitrary-opponent certificate on the learned support, consistent with these environments having no structural floor (Gathering and Markov Stag Hunt in tab:certificate_width's discussion, plus the matrix games and Congestion).

The certificate is a property of a padded runtime shield. The deployed OmSh shield certifies against the unpadded level kernels and spends budget up to q, so it does not inherit the guarantee. The guarantee covers what is run only if the runtime shield checks the padded sets at radius eps >= eps_WM + eps_OM. The audited eps_WM alone is 0.13 (Gathering) and 0.41 (Markov Stag Hunt) on reachable rows. At radius 1 the padded shield is the worst-case support shield. The open question is therefore the reward cost of running the padded shield at the required radius, not its feasibility. Measuring it needs:

1. the runtime floor iteration and successor-budget allocation padded too (see the gap above);
2. a training condition with eps set from the audit plus an opponent slack;
3. the closest-retained-level opponent gap, which the campaign did not log, to set that slack.

Pursuit is the exception: even its exact-world-model certificate leaves only 0.0022 of slack at the 0.16 budget.

Pursuit per-row radii and the paper¶

pursuit-rate-radii.md replaces Pursuit's uniform radius with per-row world-model radii from a time-uniform box on the two slip rates ("known rules, unknown rates"). Around the parametric centre, level-row radii are at most 0.0028. Floor-0 demand is 0.1588, leaving 3.2e-4 of opponent slack at shield budget 0.16. Around the learned kernel the certificate is infeasible at every floor.

The paper states the construction as cor:padded_omsh, after thm:anytime_safety, with its proof in appsec:padded_omsh. The proof passes through the level's mixture of true rows, so per-row radii weighted by the level's opponent policy are covered. Results are in appsec:padded_margins (tab:padded_margins, generated by scripts/summarize_robust_margins.py).

Risk dominance: the weaker condition the theorem actually needs¶

The supermartingale in thm:anytime_safety uses coverage only through the step inequality E_true[W_t] <= q_t, where W_t is the certificate the runtime commits to (successor budgets, and 1 off the listed successors) and q_t the carried budget. With eta_t = max(0, E_true[W_t] - q_t), P(tau_U <= T) <= p + E[sum_{t<T} eta_t]. The paper states this as cor:risk_dominance and proves it in appsec:risk_dominance.

scripts/audit_certificate_dominance.py, with its maths in src/shield/ambiguity/dominance.py, evaluates eta_t on the campaign's frozen evaluation. It uses the exact graph, the opponents' frozen policies within their masks, and each role's controller._last_decision. It also checks that the runtime carries W_t(s_{t+1}). --kernel learned swaps in the learned world model, to separate world-model from opponent error. excess_over_all_levels admits levels the floor has dropped.

This is an audit (simulator and real opponent), not a certificate known before deployment, and it covers the frozen evaluation only, where opponents are fixed. The expectation is a sample average over evaluation episodes, so zero observed excess does not establish eta_t = 0 almost surely. scripts/summarize_dominance_audit.py writes the paper's tab:dominance_audit.

Corrected-reward bundle (8 Oct 2026)¶

With the opponent models retrained on successor-conditioned rewards, the Pursuit floor-0 margin r* is 0.0076 on the learned kernel and 0.0088 on the exact kernel (before: 0.0022 and 0.0022). The reset demands are 0.1321, 0.1233 and 0.1044 (before: 0.1515, 0.1398, 0.0939). The per-row parametric version is in pursuit-rate-radii.md.