論文の概要: Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained
Markov Decision Process
- arxiv url: http://arxiv.org/abs/2402.16324v1
- Date: Mon, 26 Feb 2024 06:08:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 14:22:34.804751
- Title: Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained
Markov Decision Process
- Title(参考訳): 制約マルコフ決定過程における$\tilde{O}(1/\epsilon)$サンプル複素性
- Authors: Jiashuo Jiang and Yinyu Ye
- Abstract要約: CMDP問題に対する最適問題依存保証の導出に向けた第一歩を踏み出す。
本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
- 参考スコア(独自算出の注目度): 5.534850785702479
- 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{\kappa}{\epsilon}\cdot\log^2(1/\epsilon))$ sample complexity bound,
with $\kappa$ being a problem-dependent parameter, yet independent of
$\epsilon$. Our sample complexity bound improves upon the state-of-art
$O(1/\epsilon^2)$ sample complexity for CMDP problems established in the
previous literature, in terms of the dependency on $\epsilon$. 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). an eliminating procedure that characterizes one optimal
basis of the primal LP, and; ii) a resolving procedure that is adaptive to the
remaining resources and sticks to the characterized optimal basis.
- Abstract(参考訳): 逐次学習や意思決定において安全性や資源制約を満たす上で中心的な役割を果たす制約付きマルコフ決定プロセス(cmdp)に対する強化学習問題を考える。
この問題では、有限資源と未知の遷移確率を持つMDPが与えられる。
それぞれの段階で、私たちは行動をとり、報酬を集め、いくつかのリソースを消費します。
本研究は,CMDP問題に対する最適問題依存保証の導出に向けた第一歩である。
o(\frac{\kappa}{\epsilon}\cdot\log^2(1/\epsilon))$ サンプル複雑性境界に変換され、$\kappa$ は問題依存パラメータであるが$\epsilon$とは独立である。
我々のサンプル複雑性境界は、以前の文献で確立されたCMDP問題に対して、$O(1/\epsilon^2)$サンプル複雑性を$\epsilon$への依存性の観点から改善する。
そこで我々は,CMDP問題を解析するための新しいフレームワークを開発した。
具体的には,本アルゴリズムはプライマリ空間で動作し,各期間におけるCMDP問題に対するプライマリLPを,<textit{adaptive} の残量でオンライン的に解決する。
我々のアルゴリズムの重要な要素は次のとおりである。
私)。
一次lpの1つの最適な基底を特徴づける除去手順,及び
二 残余の資源に適応し、特徴的最適基準に固執する解決手続
関連論文リスト
- Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - 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) - 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) - 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) - Model-Free Algorithm and Regret Analysis for MDPs with Long-Term
Constraints [38.2783003051101]
本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。
本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
論文 参考訳(メタデータ) (2020-06-10T17:19:29Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳(メタデータ) (2020-03-11T23:23:29Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。