論文の概要: Truly No-Regret Learning in Constrained MDPs

• arxiv url: http://arxiv.org/abs/2402.15776v1
• Date: Sat, 24 Feb 2024 09:47:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-27 17:02:02.742078
• Title: Truly No-Regret Learning in Constrained MDPs
• Title（参考訳）: 拘束型MDPにおける完全非回帰学習
• Authors: Adrian M\"uller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, Niao He
• Abstract要約: 未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
• 参考スコア（独自算出の注目度）: 66.28706907897285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constrained Markov decision processes (CMDPs) are a common way to model safety constraints in reinforcement learning. State-of-the-art methods for efficiently solving CMDPs are based on primal-dual algorithms. For these algorithms, all currently known regret bounds allow for error cancellations -- one can compensate for a constraint violation in one round with a strict constraint satisfaction in another. This makes the online learning process unsafe since it only guarantees safety for the final (mixture) policy but not during learning. As Efroni et al. (2020) pointed out, it is an open question whether primal-dual algorithms can provably achieve sublinear regret if we do not allow error cancellations. In this paper, we give the first affirmative answer. We first generalize a result on last-iterate convergence of regularized primal-dual schemes to CMDPs with multiple constraints. Building upon this insight, we propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
• Abstract（参考訳）: CMDP(Constrained Markov decision process)は、強化学習における安全性制約をモデル化する一般的な方法である。 CMDPを効率的に解くための最先端の手法は、原始双対アルゴリズムに基づいている。 これらのアルゴリズムでは、現在知られているすべての後悔のバウンダリがエラーのキャンセルを許す - 1ラウンドで制約違反を補うことができ、もう1ラウンドで厳格な制約満足度を補うことができる。 これにより、オンライン学習プロセスは、最終(混合)ポリシーの安全性のみを保証するが、学習中は安全ではない。 Efroni et al. (2020) が指摘しているように、原始双対アルゴリズムが誤りのキャンセルを許さない場合、確実にサブ線形後悔を達成できるかどうかという未解決の問題である。 本稿では,最初の肯定的な回答を与える。 まず、複数の制約を持つCMDPに対する正規化原始双対スキームの終点収束に関する結果を一般化する。 この知見に基づいて、未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。

関連論文リスト

• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization [37.24692425018]
  Emphconstrained MDPs(CMDPs)におけるオンライン学習の研究 提案アルゴリズムは, 対向型MDPに対して, 最先端のポリシー最適化アプローチを採用するプリミティブ・デュアル・スキームを実装している。
  論文  参考訳（メタデータ） (2024-10-03T07:54:04Z)
• 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)
• Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes [24.51454563844664]
  有限水平CMDPのためのモデルベース2元アルゴリズムOptAug-CMDPを提案する。 提案アルゴリズムは誤りのキャンセルを必要とせずに後悔を実現する。
  論文  参考訳（メタデータ） (2023-06-12T10:10:57Z)
• 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)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Learning and Planning in Average-Reward Markov Decision Processes [15.586087060535398]
  我々は,平均回帰MDPの学習と計画アルゴリズムを導入する。 全てのアルゴリズムは,平均報酬の推定値を更新する際に,従来の誤差よりも時間差誤差を用いている。
  論文  参考訳（メタデータ） (2020-06-29T19:03:24Z)
• Excursion Search for Constrained Bayesian Optimization under a Limited Budget of Failures [62.41541049302712]
  本稿では,所定の予算の失敗の関数として探索において許容されるリスクの量を制御する制御理論に基づく新しい意思決定者を提案する。 本アルゴリズムは, 種々の最適化実験において, 故障予算をより効率的に利用し, 一般に, 最先端の手法よりも, 後悔度を低くする。
  論文  参考訳（メタデータ） (2020-05-15T09:54:09Z)
• 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)

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

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