2025-11-20T12:37:14.096690

Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs

Ding, Zhang, Duan et al.

We study the sequential decision making problem of maximizing the expected total reward while satisfying a constraint on the expected total utility. We employ the natural policy gradient method to solve the discounted infinite-horizon optimal control problem for Constrained Markov Decision Processes (constrained MDPs). Specifically, we propose a new Natural Policy Gradient Primal-Dual (NPG-PD) method that updates the primal variable via natural policy gradient ascent and the dual variable via projected subgradient descent. Although the underlying maximization involves a nonconcave objective function and a nonconvex constraint set, under the softmax policy parametrization, we prove that our method achieves global convergence with sublinear rates regarding both the optimality gap and the constraint violation. Such convergence is independent of the size of the state-action space, i.e., it is~dimension-free. Furthermore, for log-linear and general smooth policy parametrizations, we establish sublinear convergence rates up to a function approximation error caused by restricted policy parametrization. We also provide convergence and finite-sample complexity guarantees for two sample-based NPG-PD algorithms. We use a set of computational experiments to showcase the effectiveness of our approach.

academic

制約付きMDPに対する自然政策勾配主双対法の収束性とサンプル複雑度

基本情報

論文ID: 2206.02346
タイトル: Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs
著者: Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, Mihailo R. Jovanović
分類: math.OC cs.AI cs.LG cs.SY eess.SY
掲載誌: Journal of Machine Learning Research 26 (2025) 1-76
論文リンク: https://arxiv.org/abs/2206.02346

要約

本論文は、期待総効用制約を満たす条件下で期待総報酬を最大化する逐次意思決定問題を研究している。著者らは自然政策勾配法を用いて制約付きマルコフ決定過程(constrained MDPs)の割引無限時間最適制御問題を解く。具体的には、新しい自然政策勾配主双対(NPG-PD)法を提案し、主変数を自然政策勾配上昇により、双対変数を投影部分勾配下降により更新する。基礎となる最大化問題が非凹目標関数と非凸制約集合を含むにもかかわらず、ソフトマックス政策パラメータ化の下で、本手法は最適性ギャップと制約違反の両方において全域収束の準線形率を達成する。この収束性は状態-行動空間の大きさに依存しない、すなわち無次元依存である。さらに、対数線形および一般的な滑らかな政策パラメータ化に対して、制限付き政策パラメータ化に起因する関数近似誤差までの準線形収束率が確立される。

研究背景と動機

問題定義

本論文が解決する中核的な問題は、制約付きマルコフ決定過程(Constrained MDPs)における最適政策学習問題である：

目標：期待総報酬 $V^π_r(ρ)$ を最大化する
制約：期待総効用制約 $V^π_g(ρ) ≥ b$ を満たす
課題：目的関数が非凹、制約集合が非凸

重要性

制約付きMDPは安全関連アプリケーションにおいて重要な意義を持つ：

自動運転：性能最大化と同時に安全制約を保証する必要がある
ロボット工学：タスク実行時に物理的および安全上の制限を満たす必要がある
ネットワークセキュリティ：システム性能最適化と同時にセキュリティ政策を維持する
金融管理：収益追求と同時にリスクを制御する

既存手法の限界

理論的保証の不足：ほとんどの既存手法は漸近収束または局所収束保証のみを提供する
次元依存性：収束率は通常、状態-行動空間の大きさに依存する
関数近似誤差：関数近似下での厳密な分析が不足している
サンプル複雑度：有限サンプル複雑度の理論的保証が不足している

核心的貢献

NPG-PDアルゴリズムの提案：自然政策勾配と主双対法を組み合わせた新しいアルゴリズムフレームワークを設計
全域収束保証：ソフトマックスパラメータ化の下で次元無関の全域収束性を証明
関数近似理論：対数線形および一般的な滑らかな政策パラメータ化に対する収束理論を確立
サンプル複雑度分析：2つのサンプルベースのNPG-PDアルゴリズムの有限サンプル複雑度保証を提供
実験検証：ロボット制御シミュレーションタスクを通じて手法の有効性を検証

方法の詳細

タスク定義

制約付きMDPは7つ組 $(\mathcal{S}, \mathcal{A}, P, r, g, b, γ, ρ)$ として定義される：

$\mathcal{S}$ ：有限状態空間
$\mathcal{A}$ ：有限行動空間
$P$ ：遷移確率
$r, g$ ：報酬および効用関数
$b$ ：制約閾値
$γ$ ：割引因子
$ρ$ ：初期状態分布

最適化問題： $\max_{π ∈ Π} V^π_r(ρ) \quad \text{s.t.} \quad V^π_g(ρ) ≥ b$

モデルアーキテクチャ

1. ラグランジュ双対化

制約付き最適化問題を鞍点問題に変換する： $\max_{π ∈ Π} \min_{λ ≥ 0} V^π_r(ρ) + λ(V^π_g(ρ) - b)$

2. NPG-PDアルゴリズムの中核更新

主変数更新（自然政策勾配）： $θ^{(t+1)} = θ^{(t)} + η_1 F^†_ρ(θ^{(t)})∇_θ V^{θ^{(t)},λ^{(t)}}_L(ρ)$

双対変数更新（投影部分勾配下降）： $λ^{(t+1)} = P_Λ\left(λ^{(t)} - η_2(V^{θ^{(t)}}_g(ρ) - b)\right)$

ここで：

$F^†_ρ(θ)$ ：フィッシャー情報行列のムーア・ペンローズ逆行列
$P_Λ$ ：区間 $[0, 2/((1-γ)ξ)]$ への投影

3. ソフトマックス政策パラメータ化下の簡略形

ソフトマックスパラメータ化 $π_θ(a|s) = \frac{\exp(θ_{s,a})}{\sum_{a'} \exp(θ_{s,a'})}$ の下で、更新は以下のように簡略化される：

$θ^{(t+1)}_{s,a} = θ^{(t)}_{s,a} + \frac{η_1}{1-γ}A^{(t)}_L(s,a)$

乗法的重み付け更新と等価： $π^{(t+1)}(a|s) = \frac{π^{(t)}(a|s)\exp\left(\frac{η_1}{1-γ}A^{(t)}_L(s,a)\right)}{Z^{(t)}(s)}$

技術的革新点

次元無関収束：ソフトマックス構造を利用して状態-行動空間の大きさに無関な収束率を実現
非凸制約処理：新しい主双対分析を通じて非凸制約集合を処理
関数近似誤差分解：推定-伝播誤差分解フレームワークを導入
後悔型分析：オンライン学習における後悔分析技術を採用

理論的結果

主要収束定理

定理10（ソフトマックスパラメータ化の全域収束）：スレーター条件の下で、 $η_1 = 2\log|A|$ 、 $η_2 = 2(1-γ)/\sqrt{T}$ を選択すると、NPG-PDアルゴリズムは以下を満たす：

最適性ギャップ： $\frac{1}{T}\sum_{t=0}^{T-1}(V^*_r(ρ) - V^{(t)}_r(ρ)) ≤ \frac{7}{(1-γ)^2}\frac{1}{\sqrt{T}}$

制約違反： $\left[\frac{1}{T}\sum_{t=0}^{T-1}(b - V^{(t)}_g(ρ))\right]_+ ≤ \frac{2}{ξ} + \frac{4ξ}{(1-γ)^2}\frac{1}{\sqrt{T}}$

関数近似の場合

定理16（対数線形パラメータ化）：関数近似設定の下で、収束率は以下の通り： $E\left[\frac{1}{T}\sum_{t=0}^{T-1}(V^*_r(ρ) - V^{(t)}_r(ρ))\right] ≤ \frac{C_3}{(1-γ)^5}\frac{1}{\sqrt{T}} + \text{関数近似誤差}$