論文の概要: Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints

• arxiv url: http://arxiv.org/abs/2503.06751v1
• Date: Sun, 09 Mar 2025 20:10:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-11 15:46:46.976484
• Title: Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
• Title（参考訳）: 複数の制約を持つマルコフ決定過程の最小2次元複素境界
• Authors: Max Buckley, Konstantinos Papathanasiou, Andreas Spanopoulos,
• Abstract要約: 本稿では,遷移力学が不明な場合,CMDP(Constrained Markov Decision Processs)を$d > 1$制約で解くという課題に対処する。 複数の制約を持つ無限水平CMDPのモデルベースアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with $d > 1$ constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a model-based algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^3\epsilon^2} \right)$ samples to return $\epsilon$-optimal policy, while in the strict feasibility setting it requires $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^5\epsilon^2{\zeta_{\mathbf{c}}^*}^2} \right)$ samples.
• Abstract（参考訳）: 本稿では,遷移ダイナミクスが不明な場合,CMDP(Constrained Markov Decision Processs)を$d > 1$制約で解くという課題に対処するが,サンプルは生成モデルから引き出すことができる。 本稿では,表の設定に制約が複数ある無限水平CMDPのモデルベースアルゴリズムを提案する。 我々のアプローチでは、緩和された実現性はいくつかの制約違反を許容し、厳格な実現性はすべての制約に順守する必要がある。 主な貢献は、アルゴリズムの開発と、両方の設定に対するサンプル複雑性境界の導出である。 緩和された実行可能性設定のために、我々のアルゴリズムは $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^3\epsilon^2} \right)$ sample to return $\epsilon$-optimal policy を必要とする一方で、厳密な実行可能性設定では $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^5\epsilon^2\zeta{\mathcal{c}}^2} \right)$サンプルが必要であることを示す。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation [8.849815837266977]
  制約付きマルコフ決定プロセス(CMDP)は、多くのアプリケーションにおいてますます重要になっている複数の目的を持つシーケンシャルな意思決定のシナリオをモデル化する。 我々は,そのような仮定を必要とせず,しかも非常によく機能するSafe PSRL (posterior sample-based RL)アルゴリズムを提案する。 準線形$tildemathcal Oleft(H2.5 sqrt|mathcalS|2 |mathcalA|K right)$上界をベイズ賞の目的的後悔と、有界なイデアルとともに成立させる。
  論文  参考訳（メタデータ） (2023-01-27T06:18:25Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach [37.80609997145897]
  強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。 決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。 CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。 ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
  論文  参考訳（メタデータ） (2021-09-13T21:27:03Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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