論文の概要: A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
- arxiv url: http://arxiv.org/abs/2207.06147v1
- Date: Wed, 13 Jul 2022 12:13:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-14 21:14:07.953070
- Title: A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
- Title（参考訳）: CMDPにおけるオフポリティ学習のための準最適プリマル双対法
- Authors: Fan Chen, Junyu Zhang, Zaiwen Wen
- Abstract要約: 制約付きマルコフ決定プロセス(CMDP)は、安全な強化学習のための重要なフレームワークである。
本稿では,オフラインデータのみを利用できるCMDP問題に焦点をあてる。
単一政治集中係数$C*$の概念を採用することで、$Omegaleft(fracminleft|mathcalS||mathcalA|,|mathcalS|+Iright C*(fracminleft|mathcalS)を確立する。
- 参考スコア（独自算出の注目度）: 12.37249250512371
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: As an important framework for safe Reinforcement Learning, the Constrained
Markov Decision Process (CMDP) has been extensively studied in the recent
literature. However, despite the rich results under various on-policy learning
settings, there still lacks some essential understanding of the offline CMDP
problems, in terms of both the algorithm design and the information theoretic
sample complexity lower bound. In this paper, we focus on solving the CMDP
problems where only offline data are available. By adopting the concept of the
single-policy concentrability coefficient $C^*$, we establish an
$\Omega\left(\frac{\min\left\{|\mathcal{S}||\mathcal{A}|,|\mathcal{S}|+I\right\}
C^*}{(1-\gamma)^3\epsilon^2}\right)$ sample complexity lower bound for the
offline CMDP problem, where $I$ stands for the number of constraints. By
introducing a simple but novel deviation control mechanism, we propose a
near-optimal primal-dual learning algorithm called DPDL. This algorithm
provably guarantees zero constraint violation and its sample complexity matches
the above lower bound except for an $\tilde{\mathcal{O}}((1-\gamma)^{-1})$
factor. Comprehensive discussion on how to deal with the unknown constant $C^*$
and the potential asynchronous structure on the offline dataset are also
included.
- Abstract（参考訳）: 安全な強化学習のための重要な枠組みとして,近年,CMDP(Constrained Markov Decision Process)が広く研究されている。
しかし、様々なオンライン学習環境下での豊富な結果にもかかわらず、アルゴリズム設計と情報理論サンプルの複雑さの両面において、オフラインCMDP問題に対する基本的な理解はいまだに欠けている。
本稿では,オフラインデータのみ利用可能なcmdp問題を解決することに焦点を当てる。
1-policy concentrability coefficient $c^*$ の概念を採用することで、$\omega\left(\frac{\min\left\{|\mathcal{s}||\mathcal{a}|,|\mathcal{s}|+i\right\} c^*}{(1-\gamma)^3\epsilon^2}\right)$ オフラインcmdp問題に対して、$i$ は制約の数を表す。
単純だが斬新な偏差制御機構を導入し,DPDLと呼ばれるほぼ最適の主対数学習アルゴリズムを提案する。
このアルゴリズムはゼロ制約違反を確実に保証し、そのサンプル複雑性は$\tilde{\mathcal{o}}((1-\gamma)^{-1})$因子を除いて上記の下限に一致する。
未知の定数 $c^*$ と、オフラインデータセット上の潜在的非同期構造を扱う方法についての包括的な議論も含まれている。
関連論文リスト
- 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) - Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained Markov Decision Process [4.685121820790546]
マルコフ決定過程(CMDP)の強化学習問題について考察する。
これは$O(frac1Deltacdotepscdotlog2(1/eps))$ sample complexity boundとなる。
本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
論文 参考訳（メタデータ） (2024-02-26T06:08:25Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - 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) - 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) - Locally Differentially Private Reinforcement Learning for Linear Mixture
Markov Decision Processes [78.27542864367821]
強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。
ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。
線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-19T17:44:09Z) - 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) - 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) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。