The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs

arXiv:2610.24345v1 Announce Type: new Abstract: Before a new policy replaces a deployed one, we often want a certificate, computed from logged episodes, that it is better. We ask how many episodes such a certificate needs when the logging policy is known but history-dependent, and the error probability must stay below $\delta$ in every environment consistent with the logs. The answer is an exponent $K^\star$: the smallest KL divergence from the logged law to a law with the same logged action probabilities under which the target does not improve. No sound certifier stops in fewer than $\log(1/\delta)/K^\star$ expected episodes, at any $\delta$, and whenever $0