論文の概要: PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure
- arxiv url: http://arxiv.org/abs/2603.01309v1
- Date: Sun, 01 Mar 2026 22:33:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 19:50:56.62093
- Title: PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure
- Title（参考訳）: 強化学習のためのPAC保証:サンプル複雑度,被覆度,構造
- Authors: Joshua Steier,
- Abstract要約: ほぼすべてのPACサンプルの複雑さを3つの要因に分解するCoverage-Objective-Structure(CSO)フレームワークを提案する。
CSOは定理ではなく、ボトルネックを特定し、クロスセット比較を即座に行う解釈テンプレートである。
我々は、CSO座標でインデックス付けされたレート・ルックアップ・テーブル、ベルマン残差診断、配置ゲートによるカバレッジ推定、エポソードごとのポリシー証明書を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When data is scarce or mistakes are costly, average-case metrics fall short. What a practitioner needs is a guarantee: with probability at least $1-δ$, the learned policy is $\varepsilon$-close to optimal after $N$ episodes. This is the PAC promise, and between 2018 and 2025 the RL theory community made striking progress on when such promises can be kept. We survey that progress. Our organizing tool is the Coverage-Structure-Objective (CSO) framework, proposed here, which decomposes nearly every PAC sample complexity result into three factors: coverage (how data were obtained), structure (intrinsic MDP or function-class complexity), and objective (what the learner must deliver). CSO is not a theorem but an interpretive template that identifies bottlenecks and makes cross-setting comparison immediate. The technical core covers tight tabular baselines and the uniform-PAC bridge to regret; structural complexity measures (Bellman rank, witness rank, Bellman-Eluder dimension) governing learnability with function approximation; results for linear, kernel/NTK, and low-rank models; reward-free exploration as upfront coverage investment; and pessimistic offline RL where inherited coverage is the binding constraint. We provide practitioner tools: rate lookup tables indexed by CSO coordinates, Bellman residual diagnostics, coverage estimation with deployment gates, and per-episode policy certificates. A final section catalogs open problems, separating near-term targets from frontier questions where coverage, structure, and computation tangle in ways current theory cannot resolve.
- Abstract（参考訳）: データが不足したり、ミスがコストがかかる場合、平均ケースメトリクスは不足する。
少なくとも1-δ$の確率では、学習したポリシーは$\varepsilon$-closeで、$N$のエピソードの後に最適である。
これはPACの約束であり、2018年から2025年の間に、RL理論のコミュニティは、そのような約束をいつ維持できるかを著しく前進させた。
私たちはその進捗を調査します。
ここで提案したCoverage-Structure-Objective(CSO)フレームワークは,ほぼすべてのPACサンプルの複雑さを分解して,カバレッジ(データの取得方法),構造(固有のMDPあるいは関数クラスの複雑性),目的(学習者が提供しなければならないもの)という3つの要因に分解する。
CSOは定理ではなく、ボトルネックを特定し、クロスセット比較を即座に行う解釈テンプレートである。
技術的中核は、厳密な表層ベースラインと一様PACブリッジ、構造的複雑性尺度(ベルマンランク、証人ランク、ベルマン・エルダー次元)、関数近似による学習可能性の制御、線形、カーネル/NTKおよびローランクモデルの結果、事前カバレッジ投資としての無報酬探索、継承されたカバレッジが束縛制約である悲観的なオフラインRLをカバーしている。
我々は,CSO座標でインデックス付けされたレート・ルックアップ・テーブル,ベルマン残差診断,配置ゲートによるカバレッジ推定,エポソードごとのポリシー証明書を提供する。
最終節はオープンな問題をカタログ化し、現在の理論では解けないような範囲、構造、計算の絡み合いがあるフロンティア問題から、短期的な目標を分離する。
関連論文リスト
- CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction [49.09876340754804]
conformsctextCoVeRは、探索効率と多目的軌跡の必要性のバランスをとるモデルフリーデコード戦略である。
本研究では,conformsctextCoVeRがコンパクトな検索空間を同時に維持し,所望の軌跡に対して高いカバレッジの確率を保証することを示す。
論文 参考訳（メタデータ） (2025-09-05T01:07:12Z) - What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning? [6.908972852063454]
Policy-Aware Matrix Completion (PAMC)は構造的報酬学習フレームワークに向けた最初の具体的なステップである。
その結果,PAMCは構造報酬が存在する場合の実用的で原則化されたツールであり,より広い構造報酬学習の観点からの具体的な第1のインスタンス化であることがわかった。
論文 参考訳（メタデータ） (2025-09-04T00:53:02Z) - Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
本稿では,$ell_p$-normと汚染モデルにより特徴付けられる遷移不確実性を持つロバストなマルコフ決定過程(MDP)を設計した新しいアルゴリズムを提案する。
我々のアルゴリズムは、頑健なMDPの事前知識を必要とせずに動作する。
我々の研究は、ロバスト平均報酬RLのサンプル効率の基本的な理論的理解を提供する。
論文 参考訳（メタデータ） (2025-05-18T15:34:45Z) - When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Active Coverage for PAC Reinforcement Learning [24.256960622176305]
本稿では,エピソードマルコフ決定過程(MDP)におけるアクティブカバレッジの問題を定式化する。
我々は,異なるPAC RLタスクを解くために,CovGameをビルディングブロックとして使用できることを示す。
論文 参考訳（メタデータ） (2023-06-23T16:39:37Z) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳（メタデータ） (2023-02-05T14:22:41Z) - PAC Verification of Statistical Algorithms [0.10878040851637999]
本研究では,PAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証する,PAC検証の設定を開発する。
我々は、$mathbbR$を超える間隔の和のPAC検証のためのプロトコルを提案し、そのタスクの提案したプロトコルを改善し、より低い境界の$d$への依存と一致させる。
最終結果は,クエリの制約を満たす統計的アルゴリズムの検証のためのプロトコルである。
論文 参考訳（メタデータ） (2022-11-28T23:57:27Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive
Privacy Analysis and Beyond [57.10914865054868]
垂直ロジスティック回帰(VLR)をミニバッチ降下勾配で訓練した。
我々は、オープンソースのフェデレーション学習フレームワークのクラスにおいて、VLRの包括的で厳密なプライバシー分析を提供する。
論文 参考訳（メタデータ） (2022-07-19T05:47:30Z) - The Fundamental Price of Secure Aggregation in Differentially Private
Federated Learning [34.630300910399036]
我々は、$varepsilon$ Central DPの下で最高の精度を得るために必要な基本的な通信コストを特徴付ける。
我々の結果は、$tildeOleft( min(n2varepsilon2, d) right)$ bits per client が十分かつ必要であることを示している。
これにより、最先端のSecAgg分散DPスキームに対して大幅に改善される。
論文 参考訳（メタデータ） (2022-03-07T22:56:09Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。