論文の概要: Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

• arxiv url: http://arxiv.org/abs/2605.11586v1
• Date: Tue, 12 May 2026 06:13:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:56.621668
• Title: Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
• Title（参考訳）: 平均逆CMDPの弱いコミュニケーションを学習する: 強い双対性と改善されたレグレット
• Authors: Kihyun Yu, Beomhan Baek, Dabeen Lee,
• Abstract要約: 私たちの貢献は2倍です。 まず、弱い平均逆CMDPに対して強い双対性を適用する。 第2に、平均逆線形CMDPを弱い通信で学習するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.7646713951724009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of $\widetilde{\mathcal{O}}(T^{2/3})$, improving upon the best known bounds, where $T$ denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.
• Abstract（参考訳）: 本稿では, 無限水平平均逆制約マルコフ決定過程(CMDP)について, 弱い通信仮定の下で検討する。 私たちの貢献は2倍です。 まず,有限状態および作用空間を持つ定常ポリシーに対して,平均逆CMDPを弱通信する強い双対性を確立する。 線形プログラミングの定式化が存在しないことと、弱通信環境下での結果として生じる非凸性にもかかわらず、占領測度集合の幾何学的構造を慎重に活用することによって、強い双対性が保たれていることを示す。 第二に、この結果に基づいて、平均逆線形CMDPを弱い通信で学習する原始二重クリッピング値反復アルゴリズムを提案する。 我々のアルゴリズムは、$\widetilde{\mathcal{O}}(T^{2/3})$の後悔と制約違反境界を達成し、最もよく知られた境界を改善し、$T$は相互作用の数を表す。 提案手法はクリッピングされた値反復を制約された設定に拡張し,それを有限水平近似に適応させる。 これを分析するために, 複合ラグランジアン後悔を, 後悔と制約違反の分離境界に分解することのできる, 強い双対性に基づく新しいアプローチを開発した。

関連論文リスト

• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins [31.581870065866568]
  制約付きマルコフ決定過程(CMDP)における安全なオンライン強化学習を,強い後悔と違反の指標の下で研究する。 サブリニアの強い報酬を後悔させる既存の原始二重法は、強い制約違反の増大を招いたり、あるいは固有振動による平均点収束に制限されたりしている。 本稿では,マルチ正規化探索(FlexDOME)アルゴリズムによるフレキシブルセーフティドメイン最適化を提案する。
  論文  参考訳（メタデータ） (2026-02-11T14:54:26Z)
• AL-CoLe: Augmented Lagrangian for Constrained Learning [79.45233551350152]
  現代の機械学習のパラメータ化がほとんどないにもかかわらず、ラグランジアン双対性は制約付き学習問題に対処するための一般的なツールとなっている。 制約付き分類タスクにおいて,その有効性を示す。
  論文  参考訳（メタデータ） (2025-10-23T20:46:49Z)
• Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
  我々は,制約付きマルコフ決定過程(CMDP)におけるオンライン学習について,敵対的損失と厳しい制約を伴って検討した。 我々の研究は、敵の損失と厳しい制約の両方にかかわるCMDPを初めて研究した。
  論文  参考訳（メタデータ） (2024-03-06T12:49:08Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction [18.95829896746939]
  目的と制約の両方を状態行動占有度尺度の凹凸関数として定義したコンケーブCMDPについて検討する。 本稿では, 基本変数をポリシー勾配の上昇により更新し, 二次変数を予測下次降下により更新する, 可変生成プライマル・デュアルポリシー勾配を提案する。
  論文  参考訳（メタデータ） (2022-05-22T02:50:16Z)
• 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)

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

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