論文の概要: Certifying Almost-Sure Reachability in Unknown MDPs

• arxiv url: http://arxiv.org/abs/2610.18119v1
• Date: Tue, 13 Oct 2026 10:33:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.591682
• Title: Certifying Almost-Sure Reachability in Unknown MDPs
• Title（参考訳）: 未知のMDPにおけるほぼ安全な到達可能性の証明
• Abstract要約: 本研究は,RSM(Em Rank Supermartingale)証明書によって正当性が確認されたほぼ確実な到達性特性について検討する。 非ゼロ遷移確率の既知下限$p_min$で、PACスタイルの保証で正しい証明書を学習できることが示される。
• 参考スコア（独自算出の注目度）: 7.946210248166534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: {\em Specification-Guided Reinforcement Learning (RL)} has largely concerned itself with \emph{learning} an optimal policy against a formal specification in an unknown {\em Markov Decision Process (MDP)}. We take up the dual question. Given a policy already in hand, can one \emph{verify} that it is correct against a formal specification in an unknown MDP, using sampling access alone? Such a question arises naturally in safety-critical systems. We investigate it for the {\em almost-sure reachability property}, whose correctness is witnessed by a {\em ranking supermartingale (RSM)} certificate. Our first finding is negative. In the absence of any further information about the MDP, one can neither learn such a certificate nor verify a candidate one with probabilistic guarantees. On the positive side, we show that, under a mild restriction, a known lower bound $p_{\min}$ on nonzero transition probabilities, a correct certificate \emph{can} be learned with PAC-style guarantees. To the best of our knowledge, this is the first study of learning and verifying certificates for almost-sure reachability in unknown MDPs from sampling access alone. Finally, our experiments show that the $p_{\min}$-based sufficient condition, while sound, is conservative: the learned certificate often remains valid on the true MDP even when the condition fails.
• Abstract（参考訳）: {\em Specification-Guided Reinforcement Learning (RL) は、未知の {\em Markov Decision Process (MDP) における形式的仕様に対する最適なポリシーである 'emph{learning} に大きく関係している。 私たちはその2つの質問に答える。 既に手元にあるポリシーを考えると、未知のMDPの正式な仕様に対して、サンプリングアクセスのみを使用して正しいと判断できるだろうか? このような問題は、安全クリティカルなシステムで自然に発生する。 本稿では,その正しさをRSM証明書で確認した,ほぼ確実な到達性特性について検討する。 最初の発見は否定的です。 MDPに関するこれ以上の情報がない場合は、そのような証明書を習得したり、確率的保証のある候補を検証できない。 正の面では、緩やかな制限の下で、非ゼロ遷移確率上の既知の下限$p_{\min}$が、PACスタイルの保証で正しい証明書 \emph{can} を学習できることが示される。 我々の知る限りでは、未知のMDPがアクセスをサンプリングすることだけでほぼ確実に到達可能な証明書を学習し、検証する最初の研究である。 最後に、実験の結果、$p_{\min}$ベースの十分な条件は、健全ではあるが保守的であることが明らかとなった。

関連論文リスト

• Learning Chance-Constrained MDPs with Bellman Distributional Certificates [0.15960546024967323]
  安全強化学習(RL)は、期待されるコスト制約を強制するが、そのような期待は、高コスト軌道の確率を制御できない可能性がある。 本稿では,モデルに基づくモデルに基づくオラクルを構築する。
  論文  参考訳（メタデータ） (2026-09-25T06:03:03Z)
• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
  マシンが学習した予測は、オフラインNPハード最適化を高速化するが、予測者にその問題を解決するために何をすべきかを尋ねる。 CASP (Certificate-Augmented Solution Pruning) は代わりに、どの部分の検索空間を無視するかを尋ね、サウンドタイム検証器がチェックした後のみ、各回答を受け入れる。 トレーニングされた予測器では、未検証プルーニングは配布シフト時の最適値の最大26%を失うが、検証された同じ予測のデプロイでは、何も失われることはない。
  論文  参考訳（メタデータ） (2026-07-16T04:02:15Z)
• Proof-Carrying Numbers (PCN): A Protocol for Trustworthy Numeric Answers from LLMs via Claim Verification [0.0]
  我々は,機械的検証により数値忠実度を強制するプレゼンテーション層プロトコルであるtextbfProof-Carrying Numbers (PCN) を提案する。 PCNは軽量でモデルに依存しず、既存のアプリケーションにシームレスに統合され、暗号的なコミットメントで拡張できる。
  論文  参考訳（メタデータ） (2025-09-08T17:20:16Z)
• Quantum Hamiltonian Certification [12.536652791069576]
  この研究はハミルトン認証のための直接的で効率的なフレームワークを導入している。 正規化Schatten $inftyco-norm に対する認証問題は $mathco-norm であり、それゆえに効率的な解が得られないことを示す。 実用性を高めるため,補助量子ビットの必要性を排除しつつ,逆精度のスケーリングを維持するアンシラフリー認証手法を開発した。
  論文  参考訳（メタデータ） (2025-05-19T15:00:58Z)
• MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs [50.41998220099097]
  トレーニング中のデータエラー、汚職、中毒攻撃は、現代のAIシステムの信頼性に大きな脅威をもたらす。 混合整数双線形プログラミング(MIBP)に基づく新しい認証手法MIBP-Certを紹介する。 摂動データや操作データを通じて到達可能なパラメータの集合を計算することで、可能なすべての結果を予測することができ、堅牢性を保証することができる。
  論文  参考訳（メタデータ） (2024-12-13T14:56:39Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Proof-of-Learning is Currently More Broken Than You Think [41.3211535926634]
  本稿では,Proof-of-Learning(PoL)検証の異なる構成で再現できる最初のスプーフィング戦略を紹介する。 我々はPoLの重要な脆弱性を特定し、証明の堅牢な検証に必要な前提条件を体系的に分析する。 我々は,ディープラーニングにおける最適化のさらなる理解なしに,実証可能な堅牢なPoL検証機構を開発することはできないと結論づける。
  論文  参考訳（メタデータ） (2022-08-06T19:07:07Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。