It is proved that task-predictive equivalence induces the unique minimal sufficient quotient $\mathcal{H}/\!\sim_\tau$, leaving active observability complexity strictly invariant while eliminating superfluous distinctions.
Abstract
Before acting upon an unobservable physical system, an autonomous agent must determine which latent distinctions govern downstream tasks, how many active interventions are necessary to certify them, and when to abstain to prevent catastrophic errors. Classical observability treats state reconstruction as an unconditioned binary predicate, failing when passive observations cannot break latent degeneracies without perturbation, full microscopic inversion is prohibitively costly, and distinguishing task-irrelevant degrees of freedom wastes interaction budgets. We formalize task-conditioned active observability complexity: the minimum worst-case expected interaction cost required to identify task-relevant states under certified error and safe abstention guarantees. We prove that task-predictive equivalence induces the unique minimal sufficient quotient $\mathcal{H}/\!\sim_\tau$, leaving active observability complexity strictly invariant while eliminating superfluous distinctions. In deterministic regimes, this complexity is characterized by an optimal adaptive distinguishing tree and Bellman recursion; in noisy regimes, it obeys a stopped-transcript relative-entropy lower bound and adaptive martingale certificates that compose without independence assumptions. We instantiate a prospective certified observer with staged recovery: a nominal verifier defers candidate compilation, triggering active probing only upon evidence, while a history-measurable score shell prunes hypotheses without sacrificing risk bounds. Stress audits across high-dimensional physical systems and thousands of operational trials demonstrate certified state recovery with zero false acceptances and substantial reductions in sensor reads and model steps.
This minimal recurrent behavioral memory is characterized by a compatibility relation: under transitivity its classes attain the exact minimum, while the general case is an entropy minimization over closed compatible state assignments, with exact certificates on finite instances.
Runtime assurance pairs a verified fallback with an untrusted controller and a switching monitor, and is the leading route to admitting learned policies into safety-relevant network control. Its guarantee rests on a condition it assumes rather than requires: that the monitor's estimation error is zero, or at worst stoc...
A hidden-variable model can reproduce context-independent individual readouts while failing to preserve observable records when devices are connected or reused. We distinguish two composition requirements. For a finite family of nonnegative instrument matrices, an invariant space generated by normalization defects char...
The contribution is not a new fixed-point calculus, but a characterization of when proposal--history correlation at the model--tool boundary is necessary for certification, separating indefinite operational viability from finite worst-case verified progress.
A sound runtime admission gate executes only actions it can certify, and certifies only what its observations support. This paper asks how observations should be designed to maximize the set of actions that can be safely admitted, and shows the question is not a re-vocabulary of classical design problems. First, a proj...
Guang-Xi Wan, Hua-Long Du, Yu-Qi Liu et al.· 1 citation
FoSeRL, a framework for certifying deployed RL policies against precommitted, temporally sparse action attacks, is introduced, which achieves substantially larger certified budgets than policy smoothing, and reveals marked robustness differences among policies with comparable nominal performance.
Sara Taheri, D. Ganguly, Jan Křetínský et al.· 0 citations