analiza aiqbench
This research establishes a theoretical lower bound on the sample efficiency required to certify policy improvements from history-dependent logs, introducing an "exponent" metric that quantifies certification difficulty across different environments. By leveraging convex duality and importance-weighted advantages, the proposed plug-in Kelly certifier achieves near-optimal stopping times, demonstrating that estimator choice does not alter this fundamental limit while structural assumptions can be explicitly priced in exponent units.
The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
De la arXiv
Text integralarXiv: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<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $\delta\to0$. Coverage, computed by one backward induction, decides whether certification is impossible ($K^\star=0$), possible at a finite rate, or possible in a constant number of episodes ($K^\star=\infty$). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators.
As a consequence, no choice of off-policy estimator changes $K^\star$, a coverage ceiling explains the curse of memory, and structural assumptions can be priced in exponent units. A cushion certifier extends the approach to trees too large to enumerate. In experiments the plug-in's median stopping time is 1.13-1.43x the lower bound on memory tasks, 1.13-1.51x on Tiger ($H\le5$) and 1.17-1.64x on random trees. The best scalar betting baselines need up to 2.65x (memory) and 4.1x (Tiger) the plug-in's episodes; only on a few shallow random trees is a doubly robust bet faster, by at most 18%.
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<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $\delta\to0$. Coverage, computed by one backward induction, decides whether certification is impossible ($K^\star=0$), possible at a finite rate, or possible in a constant number of episodes ($K^\star=\infty$). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators.
As a consequence, no choice of off-policy estimator changes $K^\star$, a coverage ceiling explains the curse of memory, and structural assumptions can be priced in exponent units. A cushion certifier extends the approach to trees too large to enumerate. In experiments the plug-in's median stopping time is 1.13-1.43x the lower bound on memory tasks, 1.13-1.51x on Tiger ($H\le5$) and 1.17-1.64x on random trees. The best scalar betting baselines need up to 2.65x (memory) and 4.1x (Tiger) the plug-in's episodes; only on a few shallow random trees is a doubly robust bet faster, by at most 18%.
62 pages, 8 figures. Submitted to the Journal of Machine Learning Research
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2610.24345 [cs.LG]
(or arXiv:2610.24345v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.24345 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 371 cuvinte