論文の概要: The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
- arxiv url: http://arxiv.org/abs/2610.24345v1
- Date: Sat, 17 Oct 2026 00:25:45 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-10-20 11:52:22.555326
- Title: The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
- Title（参考訳）: 認証指数:履歴依存ログからの政策改善のインスタンス・最適シークエンシャル認証
- Abstract要約: 指数$Kstar$は、ログ化された法則から、ターゲットが改善しない同じログ化された作用確率を持つ法則への最小のKL分岐であることを示す。
サウンド証明器は、$log(1/)/Kstar$期待のエピソードで停止せず、任意の$で、0Kstarinfty$でプラグインのKelly認証器が$to0$でこのレートを達成する。
- 参考スコア（独自算出の注目度）: 3.744103474408833
- License:
- 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 $δ$ 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<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $δ\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（参考訳）: 新しいポリシーがデプロイされたものを置き換える前に、ログ化されたエピソードから計算された証明書が望ましいことを望んでいます。
ログポリシが分かっているが、履歴に依存している場合、このような証明書に必要なエピソードがいくつあるか尋ねると、エラー確率はログと整合したすべての環境において$δ$以下でなければならない。
答えは指数$K^\star$: 対数法則から対数法則への最小のKL分岐は、目標が改善しない同じ対数作用確率を持つ法則である。
音証明器は$\log(1/δ)/K^\star$期待のエピソードに留まらず、任意の$δ$で、また、$0<K^\star<\infty$が$δ\to0$となると、プラグインのKelly認証器はこのレートを$δ\to0$とする。
1つの後ろ向き帰納法で計算されたカバレッジは、認証が不可能(K^\star=0$)か、有限レートで可能か、一定回数のエピソードで可能かを決定する(K^\star=\infty$)。
凸双対性により、最適な証明書は重み付けされた優位性に賭け、またログ化された行動に公正な賭けをする。
その結果、政治外推定器の選択はK^\star$を変更せず、カバー天井は記憶の呪いを説明し、構造的仮定は指数単位で価格を下げることができる。
クッション認証は、列挙するには大きすぎる木へのアプローチを拡張する。
実験では、プラグインの停止時間は1.13-1.43倍、メモリタスクは1.13-1.51倍、タイガーは1.13-1.51倍、ランダムツリーは1.17-1.64倍である。
最高のスカラーベッティングベースラインは、プラグインのエピソードの最大2.65倍(メモリ)と4.1倍(タイガー)である。
関連論文リスト
- Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization [55.29259818039367]
支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。
明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。
値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
論文 参考訳（メタデータ） (2026-10-02T20:52:38Z) - Signed Sensitivity of Expected Hitting Time to Mutation Rate in the (1+1) EA: Per-State Sign Theorems and Verifiable Certificates for Non-Lumpable Families [0.0]
本研究は, 予測打撃時間$H_p=mathbbE_x T$の変異率に対する感度について検討した。
2つのフィットネス関数は1ステップの成功率曲線全体を共有するが、期待されるヒット時間は2つの正確な有理数である。
論文 参考訳（メタデータ） (2026-09-11T07:14:28Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
大規模言語モデルの記憶は、形式的関係が不明な定義の動物園を通じて測定される。
差分プライバシー(DP)は,これらすべてに対して同時にプロキシとして扱われることを示す。
論文 参考訳（メタデータ） (2026-08-27T23:28:08Z) - Partially Correlated Verifier Cascades in LLM Harnesses: Concave Log-Odds, Polynomial Reliability, and Blind-Spot Ceilings [0.5076419064097734]
シリアル検証ゲートはLLMハーネスのコア信頼性プリミティブである。
候補の答えが返されるのは、$k$検証者が全てそれを受け入れた場合に限られる。
このノートはそのような理論を最小限にしている。
論文 参考訳（メタデータ） (2026-07-15T14:58:37Z) - Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization [5.232247961914376]
不正なデータを削除した証明書は、その低度な瞬間を通じてのみデータを見ることができる。
我々はこれを、悪意のある雑音の下で$$$marginのハーフスペースを堅牢に学習する、再重み付けアプローチの組織原理に転換する。
論文 参考訳（メタデータ） (2026-06-15T18:56:27Z) - Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。
本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
論文 参考訳（メタデータ） (2026-06-02T10:05:23Z) - Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
KL正規化目標に対するオンライン学習の統計的効率について検討する。
我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
論文 参考訳（メタデータ） (2026-03-02T18:17:33Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Depth Dependence of $\mu$P Learning Rates in ReLU MLPs [72.14317069090407]
我々は、最大更新(mu$P)学習率の$n$と$L$に依存することを研究する。
我々は、$L3/2.$のように、$L$の非自明な依存があることを発見した。
論文 参考訳（メタデータ） (2023-05-13T01:10:49Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳（メタデータ） (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。