論文の概要: Fast Global Convergence of Policy Optimization for Constrained MDPs
- arxiv url: http://arxiv.org/abs/2111.00552v1
- Date: Sun, 31 Oct 2021 17:46:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-02 14:28:12.830994
- Title: Fast Global Convergence of Policy Optimization for Constrained MDPs
- Title(参考訳): 拘束型MDPにおける政策最適化の高速グローバル収束
- Authors: Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, Chao Tian
- Abstract要約: 勾配法は最適性ギャップと制約違反の両方に対して$mathcalO(log(T)/T)$大域収束率が得られることを示す。
スレーターの条件が満たされ、事前条件が知られているとき、十分大きなT$に対してゼロ制約違反がさらに保証される。
- 参考スコア(独自算出の注目度): 17.825031573375725
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the issue of safety in reinforcement learning. We pose the problem
in a discounted infinite-horizon constrained Markov decision process framework.
Existing results have shown that gradient-based methods are able to achieve an
$\mathcal{O}(1/\sqrt{T})$ global convergence rate both for the optimality gap
and the constraint violation. We exhibit a natural policy gradient-based
algorithm that has a faster convergence rate $\mathcal{O}(\log(T)/T)$ for both
the optimality gap and the constraint violation. When Slater's condition is
satisfied and known a priori, zero constraint violation can be further
guaranteed for a sufficiently large $T$ while maintaining the same convergence
rate.
- Abstract(参考訳): 我々は強化学習における安全性の問題に取り組む。
我々はこの問題を、無限水平制約付きマルコフ決定プロセスフレームワークで解決する。
既存の結果は、勾配に基づく手法は最適性ギャップと制約違反の両方で$\mathcal{o}(1/\sqrt{t})$大域収束率を達成できることを示した。
最適性ギャップと制約違反の両方に対して、より高速な収束率$\mathcal{O}(\log(T)/T)$の自然ポリシー勾配に基づくアルゴリズムを示す。
スレーターの条件が満たされ事前条件が知られているとき、同じ収束率を維持しながら十分大きなT$に対してゼロ制約違反がさらに保証される。
関連論文リスト
- Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳(メタデータ) (2023-10-02T08:07:36Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳(メタデータ) (2023-07-04T16:55:41Z) - Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm [42.83837408373223]
連続状態-作用空間におけるマルコフ決定過程(CMDP)の問題点を考察する。
本稿では,ゼロ制約違反を実現するために,新しい保守的自然ポリシーグラディエント・プライマル・ダイアルアルゴリズム(C-NPG-PD)を提案する。
論文 参考訳(メタデータ) (2022-06-12T22:31:43Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳(メタデータ) (2022-06-03T16:26:38Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳(メタデータ) (2022-01-18T17:24:20Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳(メタデータ) (2021-10-29T06:35:44Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。
制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-12T06:13:33Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳(メタデータ) (2021-02-22T18:56:26Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。