論文の概要: Q-Learning for Reachability in MEC-Free MDPs

• arxiv url: http://arxiv.org/abs/2610.01781v1
• Date: Thu, 01 Oct 2026 14:32:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.19312
• Title: Q-Learning for Reachability in MEC-Free MDPs
• Title（参考訳）: MECフリーMPPの到達性に関するQラーニング
• Abstract要約: 非末端最大端成分(MEC)を含まないMPPのフラグメントへの到達性を保証する最初のモデルフリーアルゴリズムであるQuasarを提案する。 我々のアルゴリズムは、時間差更新を用いて、遷移確率を学習することなく最適なポリシーに収束する古典的なQ-ラーニングアプローチに従っている。 標準化された量集合では、我々のアルゴリズムは、以前のモデルに基づく最先端モデルよりも、桁違いに少ないサンプルで最適ポリシーに収束する。
• 参考スコア（独自算出の注目度）: 5.784674822125978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning (RL) for reachability specifications is fundamental to sequential decision-making. Prior work establishes asymptotic convergence to optimal policies, but only through model-based methods that must explicitly estimate the transition probabilities of the underlying Markov Decision Process (MDP). We present Quasar, the first model-free algorithm with asymptotic guarantees for reachability on the fragment of MDPs free of non-terminal maximal end components (MECs), a building block to which every MDP reduces by the standard MEC quotient. Our algorithm follows the classical Q-learning approach, using temporal-difference updates to converge to an optimal policy without ever learning the transition probabilities. The resulting learner reduces the memory footprint from the O(|S|^2|A|) that model-based methods require to O(|S||A|). On the standardized Quantitative Verification Benchmark Set, our algorithm converges to the optimal policy with orders of magnitude fewer samples than the previous model-based state-of-the-art. Together these results are a concrete step toward the practical deployment of reachability learning and, with it, of specification-guided RL.
• Abstract（参考訳）: 到達可能性仕様のための強化学習(RL)は、シーケンシャルな意思決定に不可欠である。 先行研究は、最適ポリシーへの漸近収束を確立するが、基礎となるマルコフ決定過程(MDP)の遷移確率を明示的に見積もるモデルベースの方法によってのみ成立する。 非終端成分 (MEC) を含まない MDP フラグメントの到達性を漸近的に保証する最初のモデルフリーアルゴリズムである Quasar は、標準 MEC の商によって全ての MDP が減少するビルディングブロックである。 我々のアルゴリズムは、時間差更新を用いて、遷移確率を学習することなく最適なポリシーに収束する古典的なQ-ラーニングアプローチに従っている。 結果として得られる学習者は、O(|S|^2|A|)がO(|S||A|)に必要なO(|S|^2|A|)からメモリフットプリントを減らす。 標準化された量的検証ベンチマークセットでは、我々のアルゴリズムは、以前のモデルに基づく最先端モデルよりも、桁違いに少ないサンプルで最適ポリシーに収束する。 これらの結果は、リーチビリティ学習の実践的な展開に向けての具体的なステップであり、それとともに仕様ガイダンスRLも実現している。

関連論文リスト

• Exact Model-Free Policy Iteration for Co-safe LTL Planning [2.5735476569508995]
  本研究では,有限マルコフ決定過程における共安全線形時間論理のモデル自由強化学習について検討する。 そこで我々は,まずディスカウントされたサロゲートを用いてクランプ集合を同定する2段階のモデルフリー強化学習法を開発した。 我々は、政策評価ステップのほぼ確実に収束と、政策反復アルゴリズムの有限終了を最適ポリシーで証明する。
  論文  参考訳（メタデータ） (2026-08-05T16:58:25Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice [54.03076395748459]
  メタラーニング文学の中心的な疑問は、目に見えないタスクへの一般化を保証するために、いかに正規化するかである。 本稿では,Rothfussらによって最初に導かれたメタラーニングの一般化について述べる。 PAC-Bayesian per-task 学習境界におけるメタラーニングの条件と程度について,理論的解析および実証事例研究を行った。
  論文  参考訳（メタデータ） (2022-11-14T08:51:04Z)
• Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs [13.922754427601491]
  我々は,安全性の制約と,所望の精度を確保するために必要なサンプル数との関係を特徴付ける。 我々の主な発見は、制約のない状態の最もよく知られた境界と比較して、制約されたRLアルゴリズムのサンプルは制約の数に対数的な因子によって増加することである。
  論文  参考訳（メタデータ） (2020-08-01T18:17:08Z)

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

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