Anytime ambiguity sets and the robust shield¶

src/shield/ambiguity/ gives the shield a statistically valid kernel set in place of a point estimate. This is what turns delta_cov from a reserved placeholder (see exact-anytime-adversarial.md) into a live quantity.

The organising idea is to stop asking one neural network to be both a good predictor and a formal confidence statement, and instead keep two objects:

Where the set is centred, and why it matters¶

A confidence sequence built from transition counts proves a statement about the empirical kernel:

It says nothing about a ball centred on \(\Gamma_\theta\). Centring the certified set on a neural kernel would silently void the coverage claim, so the default is

The neural kernel keeps its own job — imagination, opponent-model training, rewards, generalisation to barely-visited rows — and is not claimed to carry coverage.

tv_radius_around_nominal provides the valid alternative when a single kernel object is wanted, using the triangle inequality:

Since \(\mathrm{ball}(\hat P_{\mathrm{counts}}, \varepsilon) \subseteq \mathrm{ball}(\Gamma_\theta, \varepsilon_{\mathrm{eff}})\), this is never tighter, so it is a diagnostic rather than the default. On rows with few or zero counts \(\varepsilon \to 1\) and the ball is the whole simplex, where centring is irrelevant anyway.

The radius¶

For support size \(m\) and \(n\) i.i.d. successor draws, Weissman's \(L_1\) bound gives \(\Pr(\lVert \hat P_n - P \rVert_1 \ge \varepsilon) \le (2^m - 2)e^{-n\varepsilon^2/2}\). Applying it at every \(n\) with the summable schedule \(\delta_n = 6\delta_{\mathrm{row}}/(\pi^2 n^2)\) and union-bounding over \(n\) gives a time-uniform radius:

The paper already uses the same summable-schedule device for the credible floor, so the construction is stylistically consistent and provable in a few lines.

Three conventions are enforced in confidence.py:

• every radius is clipped to \([0,1]\);
• \(\varepsilon(0) \equiv 1\), the whole simplex;
• a singleton-support row gets \(\varepsilon \equiv 0\). With one legal successor the transition is structurally known and carries no epistemic uncertainty; it should not be inflated merely because the generic formula returns a positive number.
• \(\delta_{\mathrm{cov}} = 0\) is permitted and meaningful. It asks for a certificate that makes no probabilistic claim, so only structurally certain rows are certified and every other row is the whole simplex. On a graph whose rows all have singleton support this recovers the exact certificate at the full budget \(p_{\mathrm{shield}} = p_{\mathrm{tot}}\), which is what such a graph should use: the Stage 2B runs on Bertrand, Chicken and Congestion certify at \(\delta_{\mathrm{cov}} = 0.1\), but every radius there is already zero, so that choice lowered the deployed budget from \(0.2\) to \(0.1\) and bought nothing.

bernstein_tv_radius is an empirical-Bernstein alternative behind the same interface. It is much tighter on near-deterministic rows, where the empirical variance is close to zero — and near-deterministic rows are the common case here.

Two statements to keep precise¶

• \(\delta_{\mathrm{cov}}\) is chosen, not measured. It is a miscoverage budget the user picks; row_delta allocates it across rows and the summable schedule across times. The data then determine the resulting radii. What becomes live is p_shield = p_total - delta_cov with a non-placeholder budget, not a \(\delta_{\mathrm{cov}}\) estimated from data.
• Why i.i.d. applies. The simulator is a time-homogeneous Markov process whose represented public state is sufficient for the dynamics, and each step draws fresh transition randomness. Conditional on visiting \((s,a)\), successive successors are therefore i.i.d. draws from \(\Gamma(\cdot \mid s,a)\) whatever the behaviour policy. "Markovian" alone would not give identical distributions across time, so the homogeneity and sufficiency conditions are stated rather than assumed. Time-uniformity is what licenses rows whose visit counts were determined adaptively.

The robust Bellman step¶

The certified set is a ball within the simplex over the row's certified support:

Because the legal successor set is known and complete, \(\mathrm{Supp}(s,a) = \mathrm{Succ}(s,a)\) by default: the adversary moves mass among legal successors, and

\(W_{\max}\) is not hard-coded to \(1\). An unsafe sink joins the support only where the row genuinely carries missing mass — which is what oracle_row_mass establishes. Hard-coding the sink would make every row maximally pessimistic and destroy the feasibility results this machinery exists to produce.

The support must be the legal one, not the observed one¶

When the centre is an estimated row rather than an exact one, this distinction becomes an implementation trap. compile_exact_adversarial_outer_kernel drops edges whose probability is exactly zero, which is correct for an exact kernel and wrong for an empirical one: a maximum-likelihood row assigns zero to every legal successor that has not yet been seen.

If those coordinates are dropped, the ball lives on \(\Delta(\text{observed})\) rather than \(\Delta(\mathrm{Succ}(s,a))\), and the true kernel — which places mass on the unobserved successors — is outside its own ambiguity set at any radius. The alphabet size feeding the radius shrinks at the same time, tightening the radius precisely on the rows where data is thinnest.

Both were live bugs. Measured realised coverage on Pursuit was \(0.047\) at 10,000 observations where it should have been essentially one; after passing the legal successor set through, it is \(1.0\) across 14,463 compared rows with zero excess. The deterministic environments could not have caught it, because every row there has singleton support and nothing is ever unobserved.

build_row_supports and row_radii_for_kernel therefore both take legal_destinations, built by legal_destinations_for_kernel from the group scaffolding, and it must be supplied whenever the kernel was compiled from an estimate.

Two modes behind one interface:

• bellman="exact" (default) — two-ended transport. Sort by \(W\); for the supremum, move at most \(\varepsilon\) total probability from the lowest-\(W\) entries into the highest-\(W\) entries, advancing the donor pointer when a donor's mass is exhausted and the recipient pointer when a recipient reaches capacity. The infimum is the mirror image, obtained exactly as \(-\sup(-W)\) so the two directions cannot drift apart.

  Depositing everything at the argmax is wrong as soon as \(\varepsilon > 1 - \hat P(s'_{\max})\): the excess must spill to the next-highest entry. Recipient capacity is part of the algorithm, not an edge case, and is pinned by test_transport_respects_recipient_capacity.

• bellman="bound" — the conservative closed form \(\mathbb E_{\hat P}[W] \pm \varepsilon(W_{\max} - W_{\min})\), clipped to \([0,1]\). This is an outward bound, not an equality: it presumes \(\varepsilon\) of mass sits at the relevant extreme, which need not hold. It is the only mode whose lower side is a symmetric subtraction. Useful as a cross-check; the exact path is materially tighter, which matters because certificate width drives feasibility.

Integration with value iteration¶

sound_value_iteration_min_reach_upper takes an optional row_radius ({(state_key, action): eps} or an [N, A] array) and robust_mode. Omitting it is the default and reproduces the point-estimate iteration exactly — pinned by test_absent_row_radius_reproduces_point_estimate_iteration_exactly.

Convergence changes meaning under a radius¶

Without a radius the lower and upper sequences converge to a common value, and max_gap is a numerical residual that shrinks below tol.

With a radius they are the fixed points of two different operators — the optimistic and pessimistic Bellman maps — so max_gap is the certified interval width and does not close. A gap-based stopping criterion would spin to max_iter. Iteration therefore stops on successive-approximation convergence of each bound separately. The nominal path still stops on the gap and is untouched.

This is easy to regress, so it is pinned by test_robust_iteration_converges_on_bound_movement_not_on_the_gap.

Marginalising radii over the opponent¶

Radii are computed on joint rows but value iteration runs on focal rows. By convexity of total variation, if \(P = \sum_{a^{-i}} \mu(a^{-i}) G_{a^{-i}}\) then

so the induced focal row inherits the \(\mu\)-weighted average of the joint radii. induce_row_radius computes this from an augmented joint graph carrying opp_prob. A joint row absent from the radius map contributes default_radius, which defaults to the whole simplex so an unmodelled row can never look certain.

build_transition_shield_bundle accepts joint_row_radius and applies this per level. build_iop_induced_graph can return its augmented joint graph, so the marginalisation costs no extra policy forwards. This composes with the existing max over retained levels in inspection.py: each level's row is inflated before the max.

Relationship to the exact adversarial certificate¶

src/true_shield/adversarial.py takes the convex hull of opponent-action extremes over a singleton graph kernel. That is the \(\varepsilon = 0\) special case of this construction: exact transitions, so the world-dynamics outer set is a singleton, with all conservatism coming from the arbitrary-opponent envelope.

Status¶

Implemented and unit-tested, including empirical coverage on a simulated categorical stream and the property that the true kernel stays inside its set when legal successors go unobserved. The downstream evaluation is Stage 2B in goal.md, which runs regardless of the Stage 1 world-model outcome: this workstream fixes the certification gap independently of which nominal model wins.

Settled: how delta_cov is allocated across rows¶

row_delta currently splits the coverage budget uniformly over every state-action row of the serialised graph. That is sound but wasteful: the union bound charges every row whether or not it is ever queried.

Whether it is also the binding constraint is not yet established, and the Stage 2B numbers do not settle it. Pursuit's zero-radius certificate is already infeasible at the target, so reallocation could not rescue it; Gathering's is feasible at zero radius, so there the sets are responsible — but responsibility could lie with visitation scarcity rather than with allocation, and a row never visited is at radius one however the budget is split.

scripts/attribute_certificate_infeasibility.py is the analysis that separates these, and it has now run. Allocation is not materially responsible, so the uniform split stays.

Three findings, none of which allocation can address:

1. The centre, not the sets, dominates. For Gathering and Markov Stag Hunt the count-centred kernel is infeasible at zero radius. No property of the confidence sequences is needed to explain them.
2. No individual row matters. Exact leave-one-radius-out on the twenty highest-sensitivity critical rows moves the reset demand by exactly zero in every environment. The infeasibility is diffuse, not carried by a small high-leverage set.
3. Most binding rows were never visited — 80% in Gathering, 88% in Markov Stag Hunt, 44% in Pursuit. A row never seen sits at radius one however the budget is split, so this is visitation scarcity by definition.

A fourth line confirms it quantitatively. Restricting the union bound to rows with a safe source, or to rows reachable from reset through safe states, produces exactly zero reduction in reset demand in all three environments. Pursuit is the most favourable case — roughly half its rows are dropped, since 924 of its 1,936 states are already unsafe — and still buys nothing. The arithmetic is the reason: halving the row count moves the union term by ln 2 = 0.69, against a schedule term ln(pi^2 n^2 / 6) of about 25.4 at 250,000 observations. The union bound is not the dominant term in the radius, so shrinking it changes the radius by one or two percent.

Two caveats belong with that conclusion. Reset demand is capped at one, so once the zero-radius count-centred reference saturates, the ambiguity contribution is forced to zero by arithmetic rather than measured; only Pursuit, at 0.728, is informative. And in Pursuit the maximum-likelihood centre is optimistic relative to the true kernel — 0.728 against a structural 0.886 — which is exactly why a count-centred kernel at zero radius is not a certificate at all and must never be reported as a weaker alternative.

The finding redirects attention to the estimator rather than the certification: an unsmoothed maximum-likelihood centre falling back to uniform on unvisited rows is the dominant problem, which is a nominal-model question.

The construction permits any a priori weighting \(w_r > 0\) with \(\sum_r w_r \le 1\), setting \(\delta_r = w_r\,\delta_{\mathrm{cov}}\). Uniform is just the choice that needs no justification. Three observations, recorded rather than acted on, because each changes what the proposition must say:

1. An unvisited row makes no probabilistic claim. Its radius is one, and \(\mathrm{TV} \le 1\) holds surely, so its failure event is empty and it consumes no budget in truth. Formalising this is delicate, because which rows are unvisited is data-dependent and the weights must be predictable.
2. Rows whose source state is already unsafe need no coverage. Unsafe states are absorbing with \(\bar\beta = 1\), so no certificate depends on their rows. This restriction is structural and a priori. In Pursuit-2 it is 924 of 1,936 states, close to a factor of two on the union bound — though only a log factor in the radius, so the practical gain is modest.
3. Reachability under the shield is a stronger a priori restriction than reachability in the graph, but it depends on the shield being certified, which depends on the radii. Breaking that circularity needs care.

None of these is a bug fix and none should be made while a sweep is in flight. They are the natural next question the Stage 2B numbers raise, and the honest reading of those numbers today is that the count-centred certificate is practical on small graphs and sample-starved on Pursuit-scale ones.

The study resolves each prefix once¶

scripts/certified_ambiguity_study.py sweeps sample budgets as prefixes of one sequential stream, and for each budget it needs two things from the same prefix: the counts the radii are computed from, and the maximum-likelihood centre the ball is placed on. Those are the same table — the centre is the aggregation with alpha = 0 — but the study originally built them from two independent resolve_transitions passes with identical arguments. At 250,000 transitions across four budgets and six environments that is a real cost, and it was deferred rather than fixed while the Stage 2B sweep was in flight, since the study is inside that sweep's closure.

StreamCounts now carries the SuccessorCounts it aggregated, and the centre is CountSuccessorModel(stream.aggregated, alpha=0.0). One pass per budget instead of two, with no change to any number: tests/test_certified_ambiguity.py asserts the carried aggregation equals a fresh resolve-and-aggregate per group, on counts and reward sums, rather than merely in total. An end-to-end run on Bertrand after the change reproduces the published result — visited fraction 1.000, no row at radius one, reset demand 0.0000, feasible, and the exact eps = 0 reference agreeing — which is the check that matters, since Bertrand's singleton-support rows make it the case where any error in the centre would show up immediately as a non-zero radius.

A further reduction is available and deliberately not taken. Because the budgets are nested prefixes and resolve_transitions treats rows independently, the whole buffer could be resolved once and sliced per budget through ResolvedTransitions.row_source, giving one pass rather than one per budget. The obstacle is that diagnostics["unresolved_reasons"] is an aggregate over the rows it was given, so the per-budget outside_legal_set and unusable counters would have to be rebuilt from per-row reasons to stay exact. That is worth doing if the study is ever rerun at more budgets; it is not worth changing a completed sweep's code for a stage that is closed.