Skip to content
aiqbenchAI & Quantum Intelligence
NewsInsightsBenchmarksSkillsAsk AILearnAbout
...Loading your session
NewsInsightsBenchmarksSkillsAsk AILearnAbout
Back to list
aiqbench takeAI Research

aiqbench analysis

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.
1
Source coveringarXiv

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

arXiv·October 21, 2026·3 min read

From arXiv

Full text

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<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.

Full text under the publisher's open licence · 371 words

Read at arXiv ↗Ask about this article

Article info

Source

arXiv

Published

October 21, 2026

Read time

3 min

Category

AI Research
aiqbench
AI & Quantum Intelligence© aiqbench. All rights reserved.

Feeds:RSS·JSON Feed

LanguageEnglish·Românăbeta
NewsAI & TechQuantumInsights
ExploreBenchmarksLearn
CompanyAboutTrustLegal noticeTerms of ServicePrivacy PolicyCopyright noticesData erasureReport content

The aiqbench take, the insights, the daily digest and Ask answers are written by AI models from the sources shown, without editorial review before publication. They may contain errors — check the source. How the model is used →

  • News
  • Insights
  • Ask AI
  • Benchmarks
  • Account