【DL輪読会】Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR2025)

DEEP LEARNING JP [DL Papers] Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR2025) Toshinori Kitamura, Matsuo Lab http://deeplearning.jp/ 1

• http://deeplearning.jp/

自己紹介 北村 俊徳 （Toshinori Kitamura） • 松尾研博士３年 • 研究内容： • 強化学習（マルコフ決定過程）の理論 • 主に安全性やロバスト性など • 紹介する論文 Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR2025) https://openreview.net/forum?id=G5sPv4KSjR&noteId=kPGMvQckyn 2

• https://openreview.net/forum?id=G5sPv4KSjR&noteId=kPGMvQckyn

目次 １．問題設定：ロバスト制約付きマルコフ決定過程 • ロバストマルコフ決定過程 • 制約付きマルコフ決定 ２．提案手法：EpiRC-PGSアルゴリズム 貢献：ロバスト制約付きマルコフ決定過程で (近似)最適方策を求めるアルゴリズムを初めて提案した 重要性：ロボットなど，実世界での強化学習で重要な理論とアルゴリズム

目次 １．問題設定：ロバスト制約付きマルコフ決定過程 • ロバストマルコフ決定過程 • 制約付きマルコフ決定 ２．提案手法：EpiRC-PGSアルゴリズム 貢献：ロバスト制約付きマルコフ決定過程で (近似)最適方策を求めるアルゴリズムを初めて提案した 重要性：ロボットなど，実世界での強化学習で重要な理論とアルゴリズム

前提：シミュレータでの方策の設計 （ロボットの）方策の設計は二段階ある： １．シミュレータで方策を設計＆挙動を確認 ２．本番環境に方策をデプロイ＆調整 シミュレータで 方策を設計 方策を デプロイ 本番環境 （未知） 5

ロバスト設計：未知のデプロイ環境でも性能を保証する技術 シミュレータ 𝑃 本番環境 𝑃 ⋆ シミュレータと本番環境は一般に異なる（sim-to-real gap問題） → シミュレータで動く方策が実環境で動くとは限らない 6

ロバスト設計：未知のデプロイ環境でも性能を保証する技術 何が問題？→「シミュレータのみで方策を設計」するのが良くない ロバスト設計：単一の環境ではなく，環境の集合に対して設計しよう 環境の集合 𝒰 「集合𝒰内の全ての環境で80点の方策」が 作れたとしよう シミュレータ 𝑃 → もし「本番環境𝑃⋆ ∈ 環境の集合𝒰」 ならば，本番環境でも80点出せる → 環境の摂動にロバストな方策 本番環境 𝑃⋆ 7

ロバスト設計の前に準備：マルコフ決定過程（MDP） for ℎ = 0, 1, 2, … マルコフ決定過程 状態空間 𝒮 行動空間 𝒜 報酬関数 𝑟: 𝒮 × 𝒜 → ℝ 1. 行動をサンプル： 𝑎 ℎ ∼ 𝜋 ⋅∣ 𝑠 ℎ 2. 報酬が発生 ：𝑟 ℎ = 𝑟 𝑠 ℎ , 𝑎 ℎ 3. 次状態に遷移 ：𝑠 ℎ+1 ∼ 𝑃 ⋅∣ 𝑠 ℎ , 𝑎 ℎ 遷移関数 𝑃: 𝒮 × 𝒜 → 0, 1 |𝒮| 割引率 𝛾 ∈ [0, 1) 行動 𝑎 ℎ エージェント 行動 𝑎 ℎ+1 方策 𝜋: 𝒮 → 0, 1 𝒜 状態 𝑠 ℎ 報酬 𝑟 ℎ 状態 𝑠 ℎ+1 報酬 𝑟 ℎ+1 MDPでの最適方策：𝜋 ⋆ ∈ argmax 収益𝑟,𝑃 𝜋 ≜ 𝔼𝜋 𝑟 0 + 𝛾𝑟 1 + 𝛾 2 𝑟 2 + ⋯ 𝜋 (補足)↑は強化学習の背景にある数理 8

準備：ロバストマルコフ決定過程 MDPでの最適方策：𝜋 ⋆ ∈ argmax 収益𝑟,𝑃 𝜋 𝜋 単一の環境 𝑃 から 環境の集合 𝒰 に拡張しよう ロバストMDP：𝜋 ⋆ ∈ argmax min 収益𝑟,𝑃 𝜋 𝜋 𝑃∈𝒰 𝒰の中の最悪な環境でも動く方策を設計する 直観：台風で動くロボットは大体の環境で動くはず 9

余談：Domain-randomizationとの関係 Domain-randomizationはロバストMDPの期待値版 MDPでの最適方策：𝜋 ⋆ ∈ argmax 収益𝑟,𝑃 𝜋 𝜋 ロバストMDP：𝜋 ⋆ ∈ argmax min 収益𝑟,𝑃 𝜋 𝜋 𝑃∈𝒰 Domain Randomization：𝜋 ⋆ ∈ argmax 𝔼𝑃∼𝕌 収益𝑟,𝑃 𝜋 𝜋 環境の集合 𝒰 𝑷∼ 𝒰上のなんらかの 分布𝕌からサンプル 10

目次 １．問題設定：ロバスト制約付きマルコフ決定過程 • ロバストマルコフ決定過程 • 制約付きマルコフ決定 ２．提案手法：EpiRC-PGSアルゴリズム 貢献：ロバスト制約付きマルコフ決定過程で (近似)最適方策を求めるアルゴリズムを初めて提案した 重要性：ロボットなど，実世界での強化学習で重要な理論とアルゴリズム

制約付き制御のモチベ：収益の最大化以外のことがしたい 「収益関数の最大化」は様々なアプリケーションで不十分 例：自動運転は「目的地までの到着時間を最小化」が目標． ただし，「障害物と距離を保つ」制約が必要． 方策の集合 Π 制約を満たす 方策の集合 Πsafe 収益を最大にする方策 𝜋 ⋆ ∈ argmax𝜋 収益𝑟,𝑃 𝜋 Πsafe 内で最適な方策： 𝜋 ⋆ ∈ argmax𝜋∈Πsafe 収益𝑟,𝑃 𝜋 12

制約付きMDP 制約付きMDPは安全性に関する制約が追加された最適化問題 通常のMDP ：max 収益𝑟0 ,𝑃 𝜋 𝜋 制約付きMDP：max 収益𝑟0 ,𝑃 𝜋 𝜋 𝑟0 は目的用の報酬関数 制約 収益𝑟𝑛 ,𝑃 𝜋 ≥ 𝑏𝑛 ∀𝑛 ∈ 1, … 𝑁 𝑟1 ~𝑟𝑁 は制約用の報酬関数 13

問題設定：ロバスト制約付きMDP 現実ではロバスト性と制約のどっちも重要 通常のMDP ：max 収益𝑟0 ,𝑃 𝜋 𝜋 ロバストMDP：max min 収益𝑟,𝑃 𝜋 𝜋 𝑃∈𝒰 制約付きMDP：max 収益𝑟0 ,𝑃 𝜋 𝜋 制約 収益𝑟𝑛 ,𝑃 𝜋 ≥ 𝑏𝑛 ロバスト制約付き：max min 収益𝑟0 ,𝑃 𝜋 𝜋 𝑃∈𝒰 ∀𝑛 ∈ 1, … 𝑁 制約 min 収益𝑟𝑛 ,𝑃 𝜋 ≥ 𝑏𝑛 𝑃∈𝒰 ∀𝑛 ∈ 1, … 𝑁 環境の集合 𝒰 最適解 𝜋 ⋆ は任意の 𝑷 ∈ 𝓤 に対して制約を満足 → 𝑷 ∈ 𝓤 ならば実環境でも安全な方策 14

研究のモチベ：ロバスト制約付き制御の既存技術 研 究 １ LQRなど，制御理論の文脈で活発に研究されてきた ロバスト 制約付きLQR [Anderson+, 2019] 最適化： min max σ𝑇𝑡=0 𝑠𝑡⊤𝑄𝑡 𝑠𝑡 𝑠,𝑎 𝑤 2 ≤1 制約：𝑠𝑡+1 = 𝐴𝑠𝑡 + 𝐵𝑎𝑡 + 𝑤𝑡 & 𝐹𝑢 𝑠𝑡 ≤ 𝑏 ∀ 𝑤𝑡 ∈ 𝑤 𝑤 2 ≤ 1 累積コストの最小化 ＋何らかの安全性の制約 +システム誤差の最悪 ケースでも性能保証 基本のテーブルMDPですら，ロバスト安全方策の設計技術は未達成 論文で扱う未解決問題：テーブルMDPでロバスト安全方策は計算できるか？ [Anderson+, 2019] “System Level Synthesis” 15

目次 １．問題設定：ロバスト制約付きマルコフ決定過程 • ロバストマルコフ決定過程 • 制約付きマルコフ決定 ２．提案手法：EpiRC-PGSアルゴリズム

先行研究：ロバスト制約付きMDPを解くのは難しい ロバスト制約付きMDPでは理論保障のついたアルゴリズムが存在しなかった MDP 動的計画法 (e.g., 価値反復法) 最適解に 収束 使用不可 [Bellman+, 1957] 線形計画法 収束 ラグランジュ形式 ＋方策勾配法 収束 [Agarawal+, 2021] [Wang+, 2022], [Mankowitz, 2020], [Russel+, 2020] 制約付きMDP ロバストMDP 収束 収束 [Iyengar+, 2005] ロバスト制約付きMDP 使用不可 使用不可 使用不可 収束 収束 [Ding+, 2024] [Wang+, 2023] 実装は可能だが 理論保証なし [Altman+, 1999] [Bellman+, 1957] “Dynamic Programming” [Iyengar+, 2005] “Robust Dynamic Programming” [Altman+, 1999] “Constrained Markov Decision Processes” [Agarwal+, 2021] “On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift” [Ding+, 2024] “Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs” [Wang+, 2023] “Policy Gradient in Robust MDPs with Global Convergence Guarantee” [Wang+, 2022] “Robust Constrained Reinforcement Learning” [Mankowitz+, 2020] “Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification” [Russel+, 2020] “Robust ConstrainedMDPs: Soft-constrained Robust Policy Optimization under Model Uncertainty” 17

提案手法：制約付き最適化とエピグラフ形式 制約を目的に合体 目的を制約に合体 制約付き最適化問題 目的 max 𝑓 𝑥 𝑥 制約 ℎ 𝑥 ≥ 𝑏 エピグラフ形式[Boyd+, 2004] ラグランジュ形式 目的 max min 𝑓 𝑥 + 𝜆 ℎ 𝑥 − 𝑏 𝑥 [Boyd+, 2004] “Convex Optimization” 𝜆≥0 目的 max max 𝑏0 𝑏0 ≥0 𝑥 制約 𝑓(𝑥) ≥ 𝑏0 かつ ℎ 𝑥 ≥ 𝑏 max 𝑓 𝑥 エピグラフ形式の直観：「max 𝑓 𝑥 を解く」 x → 制約「 𝒇 𝒙 ≥ 𝒃𝟎 を満たす𝒙が存在する」 を満たす 𝑏0 のうち，最大の𝑏0 を見つける 𝑥 𝑓(𝑥) 𝑏0 𝑥 18

提案手法：エピグラフ形式のロバスト制約付きMDP ロバスト制約付きMDP ＝「 max 𝑏0 ここで，Δ𝑏0 𝜋 ≜ 𝑏0 ≥0 min 𝑛∈ 0…𝑁 制約 max Δ𝑏0 𝜋 ≥ 0 」 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 𝜋 𝑃∈𝒰 制約 0 … 𝑁 と環境𝑃 ∈ 𝒰の全組み合 わせで生じる最悪の制約違反 エピグラフの 部分問題と呼ぶ 部分問題 ≥ 0の領域 min 収益𝑟0,𝑃 𝜋 𝑏0 𝑃∈𝒰 ロバスト安全方策が存在する領域 𝜋 定理 2： エピグラフの最適解を 𝑏0⋆ とする．𝑏0⋆ における部分問題を解くと𝜋 ⋆ が求まる： 𝜋 ⋆ ∈ argmax𝜋 Δ𝑏0⋆ 𝜋 19

提案手法：エピグラフ形式のロバスト制約付きMDP ロバスト制約付きMDP ＝「 max 𝑏0 ここで，Δ𝑏0 𝜋 ≜ 𝑏0 ≥0 min 𝑛∈ 0…𝑁 制約 max Δ𝑏0 𝜋 ≥ 0 」 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 𝑃∈𝒰 (補題2) 部分問題は 「𝑏0 が大きすぎるか？」を教えてくれる 研 究 １ 𝜋 エピグラフの 部分問題と呼ぶ max𝜋 𝛥𝑏0 𝜋 最適解 𝑏0⋆ 1. max𝜋 𝛥𝑏0 𝜋 は 𝑏0 について単調減少 2. 最適解 𝑏0⋆ は max𝜋 𝛥𝑏0⋆ 𝜋 = 0 を満たす → エピグラフ形式は部分問題を解いて 𝑏0 を調整すれば解ける（次ページ） 20

提案手法：エピグラフ形式のロバスト制約付きMDP ロバスト制約付きMDP ＝「 max 𝑏0 ここで，Δ𝑏0 𝜋 ≜ 𝑏0 ≥0 min 𝑛∈ 0…𝑁 研 究 １ 制約 max Δ𝑏0 𝜋 ≥ 0 」 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 𝜋 エピグラフの 部分問題と呼ぶ 𝑃∈𝒰 𝑏0 max𝜋 𝛥𝑏0 𝜋 ≥ 0なら 𝑏0 を増やす max𝜋 𝛥𝑏0 𝜋 最適解 𝑏0⋆ 最適解 𝑏0⋆ min 収益𝑟0 ,𝑃 𝜋 𝑏0 𝑃∈𝒰 ロバスト安全方策が存在する領域 𝜋 21

提案手法：エピグラフ形式のロバスト制約付きMDP ロバスト制約付きMDP ＝「 max 𝑏0 ここで，Δ𝑏0 𝜋 ≜ 𝑏0 ≥0 min 𝑛∈ 0…𝑁 制約 max Δ𝑏0 𝜋 ≥ 0 」 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 𝑃∈𝒰 研 究 １ 𝜋 エピグラフの 部分問題と呼ぶ 𝑏0 max𝜋 𝛥𝑏0 𝜋 < 0なら 𝑏0 を減らす max𝜋 𝛥𝑏0 𝜋 最適解 𝑏0⋆ 𝑏0 最適解 𝑏0⋆ min 収益𝑟0 ,𝑃 𝜋 𝑃∈𝒰 ロバスト安全方策が存在する領域 𝜋 22

提案手法：部分問題 max𝜋 Δ𝑏0 𝜋 をロバスト方策勾配法で解く 部分問題：max 𝜋 Δ𝑏0 𝜋 ≜ max min 𝜋 𝑛∈ 0…𝑁 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 研 究 １ 𝑃∈𝒰 ＝「 𝑛 ∈ 0 … 𝑁 」×「 𝑃 ∈ 𝒰 」における最悪ケースでの最適方策を求める問題 23

提案手法：部分問題 max𝜋 Δ𝑏0 𝜋 をロバスト方策勾配法で解く 部分問題：max 𝜋 Δ𝑏0 𝜋 ≜ max min 𝜋 𝑛∈ 0…𝑁 min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 研 究 １ 𝑃∈𝒰 ＝「 𝑛 ∈ 0 … 𝑁 」×「 𝑃 ∈ 𝒰 」における最悪ケースでの最適方策を求める問題 ＝「制約なしのロバストMDP」なので，ロバスト方策勾配法で解ける. 1. 最悪ケースの制約と遷移を計算： 𝑛 𝑡 , 𝑃 𝑡 ∈ arg min min 収益𝑟𝑛 ,𝑃 𝜋 − 𝑏𝑛 2. 方策勾配で更新： 𝜋 𝑡+1 = Proj方策 𝜋 𝑡 + 𝛼 ∇収益𝑟 ,𝑃 𝑡 𝑛∈ 0…𝑁 𝑛 𝑡 𝑃∈𝒰 𝜋 (𝑡) ロバスト方策勾配法は部分問題の大域的最適解*に収束する 定理5：上記のロバスト方策勾配を繰り返すと， ෩ ≤ 𝜀 を満たす値 Δ ෩ が𝑂 𝜀 −4 の更新で求まる． max Δ𝑏 𝜋 − Δ 𝜋 0 * 初期状態分布が全ての状態をカバーする仮定が必要（𝜇 𝑠 > 0）．ただし，この仮定は方策勾配法を使用する際に外すことが不可能 24

提案手法の全体 研 究 １ 提案手法：Epigraph Robust Constrained Policy Gradient Search アルゴリズム (EpiRC-PGSアルゴリズム) 𝑘 1. 𝑏0 について，エピグラフの部分問題をロバスト方策勾配法で解く： ෩ 𝑘 とする． max 𝜋 𝛥𝑏(𝑘) 𝜋 の解を𝜋 (𝑘) ，最適値を𝛥 0 (𝑘+1) 2. 𝑏0 ←「𝛥෩ 𝑘 ≥ 0なら 𝑏0 を増やす．𝛥෩ 𝑘 < 0なら 𝑏0 を減らす．」 𝛥෩ 𝑘 𝑏0⋆ 系 1：𝜋 (𝐾) は 𝑂෨ 𝜀 −4 回の方策評価で次の𝜀-最適方策に至る min 収益𝑟0 ,𝑃 𝜋 𝐾 + 𝜀 ≥ min 収益𝑟0 ,𝑃 𝜋 ⋆ 𝑃∈𝒰 かつ min 収益𝑟𝑛 ,𝑃 𝜋 𝐾 𝑃∈𝒰 𝑃∈𝒰 + 𝜀 ≥ 𝑏𝑛 ∀𝑛 ∈ 1, … 𝑁 25

まとめ：エピグラフ＋方策勾配法ならロバスト制約付きMDPが解ける MDP 制約付きMDP ロバストMDP ロバスト制約付きMDP 動的計画法 (e.g., 価値反復法) 最適解に 収束 使用不可 収束 使用不可 線形計画法 収束 収束 使用不可 使用不可 ラグランジュ形式 ＋方策勾配法 収束 収束 収束 理論保証なし EpiRC-PGS (本研究) 収束 収束 収束 収束 研 究 １ 26