Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Loss
2026-08-03 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors study the problem agents face when they use a simplified summary of past experiences to make decisions, which can sometimes mix up situations needing different best actions. They develop a layered theory to check if this summary is good enough, starting from a one-time test to detect problems, then moving to a step-by-step method to decide when to trust or question the summary based on task performance. They prove limits on how efficiently such self-checking can be done and provide a method that nearly meets these limits. Finally, they explore an example involving switching decision rules but note that extending their results to changing the summaries themselves remains an open problem.
representation adequacyBayes risktotal variationoptimal stoppingcertification complexitylinear programinformation-task-loss boundpolicy switchingrepresentation repair
Authors
Zijie Huang
Abstract
Agents that act on a compressed representation of their history face a structural risk: if the representation aliases histories with different optimal actions, no rule measurable with respect to the representation can avoid an irreducible per-round loss, and the agent may be unable to detect this from its own transcript. This paper develops a four-layer theory of self-certification of representation adequacy. The static layer defines decision-theoretic adequacy through a Bayes-risk grouping identity and prices a one-shot external verification by an exact total-variation threshold. The sequential layer poses certification as an optimal-stopping problem in the currency of task loss: we define an environment-wise certification complexity constant through a covering linear program, prove an information-task-loss lower bound for every delta-correct strategy, and give a Certification Track-and-Stop policy whose cost matches the bound asymptotically. A final boundary layer gives an explicit kernel-switching example and identifies the open theorem needed to cover policy switching or representation repair; it does not claim that the fixed-kernel guarantees extend to representation revision. The proofs of the two main theorems are given in full in the appendices.