Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Loss

This paper studies how an agent can certify that a compressed representation of its history remains adequate for decision-making. It develops a four-layer theory: a static Bayes-risk characterization, an exact total-variation threshold for one-shot external verification, a sequential optimal-stopping formulation priced in task loss, and an environment-wise certification complexity defined by a covering linear program. The proposed Certification Track-and-Stop policy asymptotically matches the lower bound for every delta-correct strategy under a fixed representation kernel. The authors explicitly leave policy switching and representation repair outside the stated guarantees.