論文の概要: Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2605.03921v1
• Date: Tue, 05 May 2026 16:16:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-06 19:35:44.026271
• Title: Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes
• Title（参考訳）: 球状マルコフ決定過程における政策同定のための最適後部サンプリング
• Authors: Cyrille Kone, Kevin Jamieson,
• Abstract要約: 有限水平エピソードマルコフ決定における$(varepsilon, )$PAC-PACポリシー識別問題について検討する。 本稿では,後続サンプリングとオンライン学習アルゴリズムを組み合わせてMDPを誘導する,最適ポリシー識別のためのランダムで効率的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.2959629354399484
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the $(\varepsilon, δ)$-PAC policy identification problem in finite-horizon episodic Markov Decision Processes. Existing approaches provide finite-time guarantees for approximate settings ($\varepsilon>0$) but suffer from high computational cost, rendering them hard to implement, and also suffer from suboptimal dependence on $\log(1/δ)$. We propose a randomized and computationally efficient algorithm for best policy identification that combines posterior sampling with an online learning algorithm to guide exploration in the MDP. Our method achieves asymptotic optimality in sample complexity, also in terms of posterior contraction rate, and runs in $O(S^2AH)$ per episode, matching standard model-based approaches. Unlike prior algorithms such as MOCA and PEDEL, our guarantees remain meaningful in the asymptotic regime and avoid sub-optimal polynomial dependence on $\log(1/δ)$. Our results provide both theoretical insights and practical tools for efficient policy identification in tabular MDPs.
• Abstract（参考訳）: 有限水平マルコフ決定過程における$(\varepsilon, δ)$-PACポリシー識別問題について検討する。 既存のアプローチは、近似設定(\varepsilon>0$)の有限時間保証を提供するが、高い計算コストに悩まされ、実装が困難になり、また$\log(1/δ)$に対する最適以下の依存に悩まされる。 本稿では,MDPの探索を指導するオンライン学習アルゴリズムと後続サンプリングを組み合わせた,最適ポリシー識別のためのランダムで効率的なアルゴリズムを提案する。 提案手法は, 後部収縮率の観点からも, サンプルの複雑性の漸近的最適性を達成し, 標準モデルに基づくアプローチと一致して, 1回あたり$O(S^2AH)$で実行する。 MOCAやPEDELのような従来のアルゴリズムとは異なり、我々の保証は漸近的状態において意味を持ち続け、$\log(1/δ)$に対する準最適多項式依存を避ける。 本研究は,表型MDPの効率的な政策識別のための理論的知見と実践的ツールの両方を提供する。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• A safe exploration approach to constrained Markov decision processes [7.036452261968767]
  無限水平制約マルコフ決定過程(CMDP)について考察する。 目標は、期待される累積的制約を満たしつつ、期待される累積的報酬を最大化する最適なポリシーを見つけることである。 安全クリティカルなシステムに対するオンライン学習におけるCMDPの適用により、モデルフリーでエフェミュレータフリーなアルゴリズムの開発に焦点をあてる。
  論文  参考訳（メタデータ） (2023-12-01T13:16:39Z)
• Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling [23.989009116398208]
  一般非線形関数近似を用いた低スイッチングサンプリング効率ポリシ最適化アルゴリズム LPO を設計する。 提案アルゴリズムは,$widetildeO(fractextpoly(d)varepsilon3)$サンプルのみを用いて,$varepsilon$-optimal Policyを得る。
  論文  参考訳（メタデータ） (2023-06-15T23:51:46Z)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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