Sari la conținut
aiqbenchInformații despre AI & calcul cuantic
ȘtiriAnalizeBenchmark-uriSkill-uriÎntreabă AIÎnvațăDespre
...Se încarcă sesiunea
ȘtiriAnalizeBenchmark-uriSkill-uriÎntreabă AIÎnvațăDespre

Română · beta. Traducerea a fost făcută automat și este încă în curs de revizuire. Citește pagina în engleză

Înapoi la listă
perspectiva aiqbenchCercetare AI

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.
1
Sursă care acoperăarXiv

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

arXiv·21 octombrie 2026·3 min de citit·Articolul și perspectiva sunt în engleză.

De la arXiv

Text integral

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.

Text integral sub licența deschisă a publicației · 371 cuvinte

Citește pe arXiv ↗Întreabă despre acest articol

Article info

Source

arXiv

Published

21 octombrie 2026

Read time

3 min

Category

Cercetare AI
aiqbench
Informații despre AI & calcul cuantic© aiqbench. Toate drepturile rezervate.

Fluxuri:RSS·JSON Feed

LimbăEnglish·Românăbeta
ȘtiriAI & tehnologieCuanticAnalize
ExploreazăBenchmark-uriÎnvață
CompanieDespreÎncredereInformații legaleTermeni și condițiiPolitica de confidențialitateNotificări privind drepturile de autorȘtergerea datelorRaportează conținut

Perspectiva aiqbench, analizele, rezumatul zilnic și răspunsurile din Întreabă sunt scrise de modele AI din sursele afișate, fără revizuire editorială înainte de publicare. Pot conține erori — verifică sursa. Cum este folosit modelul →

  • Știri
  • Analize
  • Întreabă
  • Topuri
  • Cont