論文の概要: Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained Markov Decision Process
- arxiv url: http://arxiv.org/abs/2402.16324v2
- Date: Mon, 3 Jun 2024 02:37:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 16:28:21.065813
- Title: Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained Markov Decision Process
- Title（参考訳）: 制約マルコフ決定過程における$\tilde{O}(1/ε)$サンプル複素性の実現
- Authors: Jiashuo Jiang, Yinyu Ye,
- Abstract要約: マルコフ決定過程(CMDP)の強化学習問題について考察する。
これは$O(frac1Deltacdotepscdotlog2(1/eps))$ sample complexity boundとなる。
本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
- 参考スコア（独自算出の注目度）: 4.685121820790546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive a logarithmic regret bound, which translates into a $O(\frac{1}{\Delta\cdot\eps}\cdot\log^2(1/\eps))$ sample complexity bound, with $\Delta$ being a problem-dependent parameter, yet independent of $\eps$. Our sample complexity bound improves upon the state-of-art $O(1/\eps^2)$ sample complexity for CMDP problems established in the previous literature, in terms of the dependency on $\eps$. To achieve this advance, we develop a new framework for analyzing CMDP problems. To be specific, our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner, with \textit{adaptive} remaining resource capacities. The key elements of our algorithm are: i) a characterization of the instance hardness via LP basis, ii) an eliminating procedure that identifies one optimal basis of the primal LP, and; iii) a resolving procedure that is adaptive to the remaining resources and sticks to the characterized optimal basis.
- Abstract（参考訳）: 本稿では,制約付きマルコフ決定プロセス(CMDP)の強化学習問題について考察する。
この問題では、有限資源と未知の遷移確率を持つMDPが与えられる。
それぞれの段階で、私たちは行動をとり、報酬を集め、いくつかのリソースを消費します。
本研究は,CMDP問題に対する最適問題依存保証の導出に向けた第一歩である。
これは$O(\frac{1}{\Delta\cdot\eps}\cdot\log^2(1/\eps))$サンプル複雑性境界であり、$\Delta$は問題依存パラメータであるが$\eps$とは独立である。
我々のサンプル複雑性境界は、以前の文献で確立されたCMDP問題に対する最先端の$O(1/\eps^2)$サンプル複雑性を、$\eps$への依存性の観点から改善する。
そこで我々は,CMDP問題を解析するための新しいフレームワークを開発した。
具体的には,本アルゴリズムはプライマリ空間で動作し,各期間におけるCMDP問題に対するプライマリLPを,<textit{adaptive} の残量でオンライン的に解決する。
我々のアルゴリズムの鍵となる要素は次のとおりである。
一 LPベースによるインスタンス硬度の評価
二 原始LPの1つの最適な基礎を識別する除去手続、及び
三 残余の資源に適応し、特徴的最適基準に固執する解決手続
関連論文リスト
- Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
我々はロバストマルコフ決定過程(MDP)の解法を考える。
MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。
$(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
論文 参考訳（メタデータ） (2022-09-21T18:10:28Z) - A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP [12.37249250512371]
制約付きマルコフ決定プロセス(CMDP)は、安全な強化学習のための重要なフレームワークである。
本稿では,オフラインデータのみを利用できるCMDP問題に焦点をあてる。
単一政治集中係数$C*$の概念を採用することで、$Omegaleft(fracminleft|mathcalS||mathcalA|,|mathcalS|+Iright C*(fracminleft|mathcalS)を確立する。
論文 参考訳（メタデータ） (2022-07-13T12:13:38Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
論文 参考訳（メタデータ） (2022-06-13T15:58:14Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Settling the Horizon-Dependence of Sample Complexity in Reinforcement
Learning [82.31436758872715]
我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。
値関数と有限水平マルコフ決定過程の接続を確立する。
論文 参考訳（メタデータ） (2021-11-01T00:21:24Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討
LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。
鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
論文 参考訳（メタデータ） (2021-02-09T16:49:58Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - Exploration-Exploitation in Constrained MDPs [79.23623305214275]
拘束マルコフ決定過程(CMDP)における探索・探索ジレンマについて検討する。
未知のCMDPで学習している間、エージェントは、MDPに関する新しい情報を見つけるために、トレードオフ探索を行う必要がある。
エージェントは最終的に良い方針や最適な方針を学習するが、学習プロセス中にエージェントが制約に過度に違反することを望まない。
論文 参考訳（メタデータ） (2020-03-04T17:03:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。