論文の概要: Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual

• arxiv url: http://arxiv.org/abs/2610.39524v1
• Date: Thu, 29 Oct 2026 07:20:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.472893
• Title: Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual
• Title（参考訳）: 拘束型MDPにおけるLast-Iterate Convergence:Dual Descent から Primal-Dual へ
• Abstract要約: 無限水平・割引制約付きマルコフ決定過程に対する政策最適化について検討する。 内ループを除去するためにエントロピー規則化自然政策勾配と二重正則化を用いる。 提案手法は,既存手法と比較して,最終項目収束保証の改善を実現していることを示す。
• 参考スコア（独自算出の注目度）: 7.237620866644061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study policy optimization for infinite-horizon, discounted constrained Markov decision processes. While primal-dual ($\texttt{PD}$) methods are widely used in practice, their theoretical guarantees typically hold for an impractical mixture policy. In contrast, dual descent ($\texttt{DD}$) methods output a single policy ("last iterate") with guarantees on its performance. However, such methods require iteratively solving entropy-regularized MDPs in an inner-loop, limiting their practical effectiveness. Moreover, existing analyses rely on strong coverage assumptions that are difficult to satisfy in practice. Consequently, we first provide a new analysis of $\texttt{DD}$ methods that does not require coverage assumptions. We then employ entropy-regularized natural policy gradient and dual regularization to eliminate the inner loop, resulting in an efficient $\texttt{PD}$ algorithm. We develop a novel tracking analysis which shows that, compared to existing methods, the proposed algorithm achieves improved last-iterate convergence guarantees. Furthermore, our theoretical framework allows us to analyze a truncated bilevel method that interpolates between $\texttt{DD}$ and $\texttt{PD}$ methods. Finally, we generalize our analysis to handle linear function approximation. Compared to prior last-iterate methods, we prove stronger guarantees under less restrictive assumptions.
• Abstract（参考訳）: 無限水平・割引制約付きマルコフ決定過程に対する政策最適化について検討する。 原始双対(\texttt{PD}$)法は実際は広く用いられているが、理論上の保証は典型的には非現実的な混合政策に当てはまる。 対照的に、dual descent$\texttt{DD}$)メソッドは、そのパフォーマンスを保証する単一のポリシー("last iterate")を出力する。 しかし、そのような手法では、エントロピー規則化されたMDPをインナーループで反復的に解く必要があり、その実用性は制限される。 さらに、既存の分析は、実際に満たすのが難しい強いカバレッジの仮定に依存している。 したがって、まず、カバレッジの仮定を必要としない$\texttt{DD}$メソッドの新しい分析を行う。 次に、エントロピー規則化自然ポリシー勾配と双対正規化を用いて内部ループを排除し、効率の良い$\texttt{PD}$アルゴリズムを得る。 提案手法は,既存手法と比較して,最終項目収束保証の改善を実現していることを示す。 さらに、我々の理論フレームワークは、$\texttt{DD}$と$\texttt{PD}$メソッドの間を補間する、切り詰められた双レベルメソッドを分析することができる。 最後に、線形関数近似を扱うために解析を一般化する。 従来手法と比較して、制約の少ない仮定でより強力な保証を証明している。

関連論文リスト

• Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs [7.237620866644061]
  無限水平・割引制約付きマルコフ決定過程(CMDP)の政策最適化について検討する。 制約付き最適化から古典的不正確な拡張ラグランジアン(textttAL$)法を用い,CMDPの最終的な収束性を示す汎用フレームワークを提案する。 ログ線形ポリシーを扱うためにこれらの結果を一般化し、より効率的な$textttPQA$の投影版が最終項目収束を実現することを実証する。
  論文  参考訳（メタデータ） (2026-05-12T07:51:18Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  政策学習における強化学習について検討する。 目的は、特定の種類の利害関係において最高の政策と競争力のある政策を見つけることである。
  論文  参考訳（メタデータ） (2025-07-06T14:40:05Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
  オフライン強化学習(RL)は、他のポリシによって収集されたトランジションの固定データセットから、ほぼ最適なポリシを学ぶことを目的としている。 本稿では,RLの線形プログラミング定式化に基づく原始双対最適化手法を提案する。
  論文  参考訳（メタデータ） (2023-05-22T11:45:23Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Stochastic first-order methods for average-reward Markov decision processes [10.023632561462712]
  平均回帰マルコフ決定過程(AMDP)について検討し,政策最適化と政策評価の両面において理論的確証が強い新しい一階法を開発した。 政策評価と政策最適化の部分を組み合わせることで、生成的およびマルコフ的ノイズモデルの両方の下で、AMDPを解くためのサンプル複雑性結果を確立する。
  論文  参考訳（メタデータ） (2022-05-11T23:02:46Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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