---
title: 【DL輪読会】Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR2025)
tags: 
author: [Deep Learning JP](https://www.docswell.com/user/DeepLearning2023)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/VEP2NQ3XE8.jpg?width=480
description: 【DL輪読会】Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR2025) by Deep Learning JP
published: March 27, 25
canonical: https://www.docswell.com/s/DeepLearning2023/Z4VRDN-2025-03-27-135448
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/VEP2NQ3XE8.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/27VDK5437Q.jpg)

自己紹介
北村 俊徳 （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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/5JGYQ61YJL.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/47QMK4D6EP.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/KE4VPQZM71.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/L7139PRYEG.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/G7WPQ211E2.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4JZKWDPXJ3.jpg)

ロバスト設計の前に準備：マルコフ決定過程（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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/YE6QG1MPEV.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/GE5RV4ZPJ4.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/972D3VRZ7R.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/DJY213DNJM.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/V7N82V6VE8.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/YJ9K16LVJ3.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/GJ8R4ZX47D.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/LJLK6D8V7R.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/47M25P6N7W.jpg)

先行研究：ロバスト制約付き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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/P7RM31P4J9.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/PJXV4Y3ZEX.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/3JKQZ3YVJD.jpg)

提案手法：エピグラフ形式のロバスト制約付き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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/LE3PDGVQJ5.jpg)

提案手法：エピグラフ形式のロバスト制約付き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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/8EDLP18WJG.jpg)

提案手法：エピグラフ形式のロバスト制約付き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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/V7P2NQ8X78.jpg)

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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/2JVDK5N3JQ.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/5EGYQ6KYEL.jpg)

提案手法の全体
研
究
１
提案手法：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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/4JQMK4N67P.jpg)

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