Certified ambiguity study (Stage 2B)¶

Measures what the count-centred ambiguity sets cost and whether a shield built over them remains deployable.

This stage is independent of the Stage 1 outcome and runs whichever arm wins, and also if none does. The certified object is built from transition counts, and a confidence sequence about the empirical kernel does not transfer to a ball centred on a learned one — see ../shielding/anytime-ambiguity-sets.md. Stage 2A, the downstream campaign for a new nominal model, is the part that waits on the gate.

What it reports¶

Per (environment, seed, sample_budget, delta_cov):

• visited-row fraction and the fraction of rows still at radius one — a row at radius one is the whole simplex and is uncertified in practice, so this is the headline sparsity cost;
• radius mean, median, p95, max — certificate width;
• beta_bar(s_0), reset demand, and feasibility at p_shield = p_total - delta_cov;
• runtime and peak memory;
• diagnostic realised coverage against the exact graph.

Protocol rules¶

Three choices here are load-bearing rather than conventional.

Counts come from prefixes of one sequential stream. Each budget uses every observation genuinely available by that prefix. They are deliberately not the Stage-1 train/validation split: that split exists to keep the representation comparison fair, and reusing it here would understate what a deployment would actually have seen by the same point.

The centre is the plain maximum-likelihood row. Weissman's bound is a statement about the empirical distribution, so a Dirichlet-smoothed centre would predict better while invalidating the coverage claim. Smoothing belongs to the nominal model, not the certified one. On an unvisited row the radius is one, so the centre is irrelevant there anyway.

The oracle is diagnostic only. The exact graph is consulted after the sets are fixed, to report realised coverage. It never enters their construction or tuning; choosing a radius with reference to the truth would be circular.

Implementation¶

src/shield/ambiguity/certificate.py solves robust arbitrary-opponent reachability over per-row total-variation balls:

It reuses compile_exact_adversarial_outer_kernel and sits alongside src/true_shield/adversarial.py rather than inside it, because that module carries an independent validator and strict acceptance semantics that should not be perturbed. Following its approach, iteration runs in floating point and the reset demand is recomputed in exact rational arithmetic, so acceptance never rests on a favourable tolerance.

Least fixed point, not any fixed point¶

Minimal reachability is the least fixed point of that operator. The first implementation iterated down from one and converged immediately, because beta = 1 everywhere is also a fixed point and a descending iteration accepts it — Bertrand was reported infeasible with reset demand 1, against a published exact result of 0. The solver now brackets from below and above like the exact one, and eps = 0 reproducing the exact certificate is pinned as a regression guard.

Fast paths¶

Most rows sit at one extreme: a singleton or fully observed row has radius zero and reduces to the nominal expectation, while an unvisited row has radius one and the adversary places all mass on the worst successor in the support. Both are exact and are taken directly; only the rows genuinely in between run the transport. This matters because the solve loops over joint rows, of which Pursuit-2 has 48,400.

Support¶

The unsafe sink joins a row's support only where that row carries missing mass. Adding it unconditionally would make every row maximally pessimistic and the certificate vacuous on exactly the environments where it is most informative.

The row's support is the legal successor set, not the observed one. A maximum-likelihood row assigns probability zero to any legal successor not yet seen, and the kernel compiler drops zero-probability edges, so those coordinates have to be restored explicitly through legal_destinations. Without that the true kernel sits outside its own ambiguity set — measured coverage on Pursuit was 0.047 rather than 1.

Attributing an infeasible result¶

scripts/attribute_certificate_infeasibility.py answers why a certified shield is infeasible, which aggregate radius statistics cannot. It is analysis only: it changes no certificate and no allocation, and scripts/summarize_attribution.py renders it.

Three reference points separate three causes:

so certified - estimated is attributable to ambiguity, estimated - structural to centre estimation, and structural is a floor no amount of data can move. The measured controls make the point that this is not a formality:

Two of the three have no structural floor at all, so their infeasibility is entirely the construction's; Pursuit's floor is already infeasible before any statistics, and its 0.88632 reproduces the published figure to five decimals, which independently validates the robust solver.

Critical rows are those with positive radius in the witness closure reachable from reset — at the fixed point each safe state picks the action minimising its robust risk, and every opponent row of that action constrains the value because the envelope maximises over them. Rows outside that closure cannot move the reset demand.

Each critical row carries its visit count, which is the crux of whether reallocating the coverage budget could help. A row wide because it was never seen sits at radius one however the budget is split — visitation scarcity, not allocation. A row still wide after many visits is genuine statistical uncertainty. The radius is also split into its three additive terms,

eps = 1/2 sqrt( 2 (m ln2 + ln(pi^2 n^2 / 6) + ln(1/delta_row)) / n )

of which only the last depends on the split.

Contribution is measured by exact leave-one-radius-out re-solves on the highest-sensitivity rows, ranked by radius * (W_max - W_min), which bounds what a row's transport can inject in one step. Two structural counterfactuals then ask whether a smaller union bound would move anything at all: restricting it to rows with a safe source, and to rows reachable from reset through safe states. Both are a priori and data-free, so adopting either would be legitimate.

Running it¶

# local smoke check
uv run python scripts/certified_ambiguity_study.py --env bertrand --seeds 1 \
  --stream_steps 4000 --sample_budgets "500 2000 4000" --delta_cov "0.05"

# inspect the fan-out
DRY_RUN=1 bash notebooks/experiments/scripts/certified_ambiguity.sh

# cluster sweep
bash notebooks/experiments/scripts/certified_ambiguity.sh

Arguments use the runner's key=value form, which it translates into --key value; the script therefore accepts underscore spellings. Results land at exports/reports/<tag>/<env>/<agents>/seed<N>/certified_summary.json.

The exact reference, and why an infeasible result needs one¶

Every cell also reports an exact reference: the same robust reachability solved on the exact graph with every radius zero. That is the arbitrary-opponent certificate the paper already describes, and it is what makes an infeasible count-centred result interpretable.

Without it, infeasibility has two indistinguishable explanations — the data are too thin, or the opponent envelope was already binding and no amount of data would help. The paper reports Pursuit's exact certificate as infeasible at eps = 0 with reset demand 0.88632, so for that environment the second explanation was live from the start. Only the gap between the reference and the count-centred rows is attributable to statistical uncertainty.

A useful sanity property: a positive radius can only raise certified risk, never lower it, so the reference bounds what the count-centred rows could ever achieve.

Open question this is meant to answer¶

The completed sweep is best described as sound but not deployable at the tested budgets: realised coverage is 1.0 throughout, and all three stochastic environments are still infeasible at every sample budget and coverage budget tried.

Reset demand does not move with budget, staying at 1.0 from 10,000 to 250,000 observations. It is tempting to read that as showing statistical uncertainty to be irrelevant, and that reading is wrong: a single reachable high-leverage row at radius one pins the global fixed point while aggregate radii improve steadily around it. The zero-radius controls are what settle it, and they disagree across environments:

So the same symptom has opposite causes. Pursuit's arbitrary-opponent envelope is already infeasible at the target before any statistics enter, and only the increment from 0.8863 to 1.0 belongs to the sets. Gathering's envelope is perfectly feasible, so there the sets are the whole story.

One further observation worth keeping: Gathering has only 13.3% of rows uncertified and is still infeasible, because most of its rows have singleton support and are certified for free. A small uncertified minority is enough to pin the certificate when those rows are reachable — so aggregate radius statistics are the wrong thing to optimise, and which rows are uncertified matters more than how many. That is what scripts/attribute_certificate_infeasibility.py measures, by isolating the rows in the witness closure reachable from reset.