Fugu-MT 論文翻訳(概要): Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes

論文の概要: Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes

arxiv url: http://arxiv.org/abs/2306.07001v2
Date: Wed, 30 Aug 2023 15:58:45 GMT
ステータス: 処理完了
システム内更新日: 2023-08-31 16:42:25.196892
Title: Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes
Title（参考訳）: 制約マルコフ決定過程におけるラグランジアンアプローチのためのキャンセラフリーレグレト境界
Authors: Adrian M\"uller, Pragnya Alatur, Giorgia Ramponi, Niao He
Abstract要約: 有限水平CMDPのためのモデルベース2元アルゴリズムOptAug-CMDPを提案する。提案アルゴリズムは誤りのキャンセルを必要とせずに後悔を実現する。
参考スコア（独自算出の注目度）: 24.51454563844664
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Constrained Markov Decision Processes (CMDPs) are one of the common ways to model safe reinforcement learning problems, where constraint functions model the safety objectives. Lagrangian-based dual or primal-dual algorithms provide efficient methods for learning in CMDPs. For these algorithms, the currently known regret bounds in the finite-horizon setting allow for a "cancellation of errors"; one can compensate for a constraint violation in one episode with a strict constraint satisfaction in another. However, we do not consider such a behavior safe in practical applications. In this paper, we overcome this weakness by proposing a novel model-based dual algorithm OptAug-CMDP for tabular finite-horizon CMDPs. Our algorithm is motivated by the augmented Lagrangian method and can be performed efficiently. We show that during $K$ episodes of exploring the CMDP, our algorithm obtains a regret of $\tilde{O}(\sqrt{K})$ for both the objective and the constraint violation. Unlike existing Lagrangian approaches, our algorithm achieves this regret without the need for the cancellation of errors.
Abstract（参考訳）: CMDP(Constrained Markov Decision Processs)は、制約関数が安全目標をモデル化する安全な強化学習問題をモデル化する一般的な方法の1つである。ラグランジアンベースの双対あるいは原始双対アルゴリズムはCMDPで学習するための効率的な方法を提供する。これらのアルゴリズムでは、有限ホリゾン設定の現在知られている後悔の限界は「誤りのカプセル化」を可能にし、あるエピソードで制約違反を補うことができ、別のエピソードでは厳密な制約満足度を保証できる。しかし,このような行動は実用上安全とは考えていない。本稿では,この弱点を,表層有限水平CMDPのための新しいモデルベースデュアルアルゴリズムであるOptAug-CMDPを提案する。本アルゴリズムは拡張ラグランジアン法に動機付けられ,効率的に実行可能である。 CMDPを探索する際の$K$のエピソードにおいて、このアルゴリズムは目的と制約違反の両方に対して$\tilde{O}(\sqrt{K})$の後悔を得る。既存のラグランジアンアプローチとは異なり、本アルゴリズムは誤りをキャンセルすることなくこの後悔を達成する。

関連論文リスト

Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints [34.7178680288326]
制約付きマルコフ決定プロセス(CMDP)では、逆の報酬と制約があり、よく知られた不合理性の結果、任意のアルゴリズムがサブリニア後悔とサブリニア制約違反を達成できない。非定常的な報酬や制約のあるCMDPでは、非定常性の増加とともに性能がスムーズに低下するアルゴリズムを提供することで、この負の結果が緩和できることが示される。
論文参考訳（メタデータ） (2024-05-23T09:48:48Z)
Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
本研究では,制約付き意思決定プロセスにおけるオンライン学習問題について,対向的損失と厳しい制約を伴う検討を行った。我々は,各エピソードの制約を高い確率で満たしながら,サブ線形後悔を実現するアルゴリズムを設計する。
論文参考訳（メタデータ） (2024-03-06T12:49:08Z)
Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文参考訳（メタデータ） (2024-02-24T09:47:46Z)
A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文参考訳（メタデータ） (2022-09-15T16:59:19Z)
Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文参考訳（メタデータ） (2022-01-31T23:52:34Z)
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)
Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文参考訳（メタデータ） (2021-11-09T09:00:02Z)
A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。深層パラメタライズされたラグランジアン法を提案する。
論文参考訳（メタデータ） (2021-05-20T13:08:06Z)
Exploration-Exploitation in Constrained MDPs [79.23623305214275]
拘束マルコフ決定過程(CMDP)における探索・探索ジレンマについて検討する。未知のCMDPで学習している間、エージェントは、MDPに関する新しい情報を見つけるために、トレードオフ探索を行う必要がある。エージェントは最終的に良い方針や最適な方針を学習するが、学習プロセス中にエージェントが制約に過度に違反することを望まない。
論文参考訳（メタデータ） (2020-03-04T17:03:56Z)
Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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