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

Overview & Synopsis

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 $δ$ 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/δ)/K^\star$ expected episodes, at any $δ$, and whenever $0