Search papers, labs, and topics across Lattice.
This paper addresses the challenge of ensuring that agents using compressed representations of their histories can accurately certify their decision-making adequacy to avoid irreducible losses. By developing a four-layer theory of self-certification, the authors establish a framework that includes decision-theoretic adequacy, an optimal-stopping approach to certification, and a method for determining certification complexity. Key results include a Certification Track-and-Stop policy that achieves asymptotic cost matching with established lower bounds for delta-correct strategies, providing a pathway for agents to verify their representations effectively.
Agents can now self-certify their decision-making adequacy, potentially avoiding costly errors due to misrepresented histories.
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.
