テックカリキュラム

制約付きMDPを途中からも守る「S-CMDP」とは?

制約付きMDPを途中からも守る「S-CMDP」とは?

1. はじめに:制約付きMDPの「最初だけの保証」を見直す

強化学習や逐次意思決定の分野では、報酬を最大化しながらコストやリスクを一定以下に抑える問題を、制約付きMDP(Constrained Markov Decision Process、CMDP:制約付きマルコフ決定過程)として定式化するのが標準的です。エネルギー消費の予算、安全上のリスク、サービスレベルの違反回数など、報酬だけでは表しにくい要件を「コストの期待値に上限を設ける」形で扱えます。

ただし、通常の CMDP が保証するのは「初期状態から見た累積コストの期待値」だけです。運用の途中で危険な状態に入ってしまったときに、そこから先も制約を満たし続けるかどうかは保証されません。序盤にコストを抑えておけば後半で大きなコストを出しても全体の期待値は予算内に収まる、という抜け道があるためです。

本記事では、この問題に取り組んだ論文「Subprocess-Constrained Markov Decision Processes」(Jiarui Gan, Debmalya Mandal, 2026年11月 arXiv 公開、NeurIPS 2026 採択予定)を解説します。論文は、到達しうるすべての履歴の時点から先(部分過程、subprocess)についても制約を課す S-CMDP(部分過程制約付きMDP)を提案し、次の3点を示しています。

  • S-CMDP では、CMDP で十分だった定常方策(状態だけを見て行動を決める方策)が最適にならないことがある。しかも最良の定常方策を近似的に求めることさえ NP 困難である
  • 一方で、履歴に依存する方策を許すと、価値集合反復(Value-Set Iteration、VSI)によって、ほぼ最適で制約違反もわずかな方策を多項式時間で計算できる
  • 方策を表として持たず、「任意の履歴を渡すと行動分布を返すアルゴリズム」として暗黙的に表現することで、履歴の数が指数的に増える問題を回避している

応用レベルの記事として、MDP と強化学習の基本(価値関数、ベルマン方程式、価値反復)を学習済みの方を想定しています。

2. 前提知識:MDPとCMDP

2-1. マルコフ決定過程(MDP)

MDP は、状態集合 S、行動集合 A、遷移確率 p(s′ | s, a)、報酬関数 r(s, a)、割引率 γ ∈ (0, 1) で表される逐次意思決定のモデルです。エージェントは各時刻で状態 sₜ を観測して行動 aₜ を選び、報酬を受け取り、環境は確率的に次の状態へ移ります。目的は割引累積報酬の期待値を最大にする方策 π を見つけることです。

2-2. 制約付きMDP(CMDP)

CMDP は MDP にコスト関数 c(s, a) と上限 θ を加えたものです。一般的な定式化は次のとおりです。

maxπ 𝔼π[∑t=0∞γtr(st,at)]s.t.𝔼π[∑t=0∞γtc(st,at)]≤θ

左側が割引累積報酬の期待値、右側の制約が割引累積コストの期待値です。どちらの期待値も、初期状態 s₀ から方策 π に従って動いたときの値です。CMDP は線形計画法やラグランジュ緩和で解けることが知られており(Altman の教科書)、Constrained Policy Optimization(CPO)など現代の安全な強化学習(Safe RL)の多くの手法もこの定式化を引き継いでいます。

2-3. 定常方策で十分という古典的な結果

通常の MDP や CMDP では、定常方策(stationary policy:現在の状態だけから行動分布を決める方策)の中に最適方策が存在します。過去の経緯を覚えておく必要がないため、方策は「状態数 × 行動数」の表で書け、計算も効率的です。S-CMDP ではこの前提が崩れる、というのが本論文の出発点の一つです。

3. CMDPの制約が「弱すぎる」場面

3-1. 期待値による平均化と前倒しの問題

論文は、初期状態だけで評価する制約には次の2つの抜け道があると指摘しています。

  • 時間方向の相殺:序盤のコストが低ければ、後半でコストが高くなっても全体の期待値は上限内に収まる
  • 軌道間の平均化:コストの高い軌道が一部にあっても、コストの低い軌道と平均されて上限内に収まる

どちらも、初期時点の期待値という1つの数字では見えない、途中の時点での「この先の見通し」の悪さです。

3-2. ロボットとSLOの例

論文では2つの応用例が挙げられています。1つ目は自律移動ロボットです。人の近くの混雑した場所や狭い通路に入ったときには、出発時点から見た期待値として安全であるだけでは不十分で、その時点から先の衝突リスクが許容範囲に収まっている必要があります。

2つ目はオンラインサービスのサービスレベル目標(SLO)です。SRE の実務では、サービスレベル指標とエラーバジェットで信頼性を継続的に監視し、バジェットを使い切ると信頼性改善への注力やデプロイの凍結といった対応を取ります。運用開始時点の期待値が予算内でも、輻輳した状態に入り、そこから先のレイテンシや可用性の違反見込みが閾値を超えるような運用は受け入れられません。

どちらも「時刻 t で処理を新しく始めたとみなしても、同じ要件を満たしていてほしい」という要求です。これを形式化したのが S-CMDP です。

4. S-CMDP(部分過程制約付きMDP)の定式化

4-1. 履歴と継続価値

S-CMDP は組 (S, A, s₀, p, r, c, θ, γ) で与えられます。通常の CMDP との違いは、上限 θ が状態ごとの関数 θ(s) になっていることです。報酬とコストは [−1, 1] に収まると仮定します。

方策 π は、履歴 h = (s₀, a₀, …, sₜ) ごとに行動分布 π(h) を割り当てます。到達しうる履歴 h に対して、その時点から先の割引報酬の期待値(継続報酬価値)を次のように定義します。

Vrπ(h)=𝔼π[∑t′=t∞γt′−tr(st′,at′) | h]

ここで E^π[· | h] は、方策 π のもとで履歴 h が起きたという条件付きの期待値です。報酬 r をコスト c に置き換えたものを継続コスト価値 V_c^π(h) とします。

4-2. 最適化問題

S-CMDP の問題は次のように書けます。

maxπ Vrπ(s0)s.t.Vcπ(h)≤θ(st)  for all h=(s0,a0,…,st) with Pπ(h)>0

P^π(h) は方策 π のもとで履歴 h が観測される確率です。つまり、実際に起こりうるすべての履歴について、その時点から先のコストの期待値が、そのときの状態 sₜ で決まる上限 θ(sₜ) 以下であることを要求します。t = 0 の制約だけを残せば、通常の CMDP(ただし上限は θ(s₀))に戻ります。

4-3. 関連する定式化との違い

安全な強化学習には、制約を強める方向の研究がほかにもあります。論文の関連研究の整理をもとに、違いを表にまとめます。

定式化何を制約するか制約の範囲
通常の CMDP初期状態からの累積コストの期待値軌道全体(初期時点のみ評価)
ピーク制約・瞬時制約各時刻のコストや行動・状態の安全性1ステップ分(局所的)
状態ごとの制約(state-wise)訪れる各状態でのコスト局所的
Anytime-constrained MDP各時点までの累積コスト過去方向(それまでに使った量)
S-CMDP(本論文)各履歴から先の割引累積コストの期待値未来方向(その先の全体)

特に近いのが McMahan と Zhu の Anytime-constrained MDP で、こちらも「初期状態だけでは不十分」という問題意識を共有しています。ただし Anytime 制約はそれまでに積み上がったコストを毎時点で上限内に保つもので、累積コストを状態に追加して扱います。S-CMDP はこれから先のコストの見込みを制約するもので、後述する価値集合を使った別の手法が必要になります。

5. 定常方策では足りない理由

5-1. 定常方策が最適にならない例

論文は、次の小さな例で定常方策の限界を示しています。

  • 状態は s1、s2、s3 と終端状態。開始状態は s1 か s2 が確率 1/2 ずつ(説明のため初期状態をランダムにしている)
  • s1 と s2 からは s3 へ、s3 からは終端状態へ、行動によらず決定的に遷移する
  • 行動は a と b の2つ。報酬とコストは s3 で b を選んだときだけ r = c = 1、それ以外はすべて 0
  • 上限は θ(s1) = 0、θ(s2) = θ(s3) = 1

報酬を得る方法は s3 で b を選ぶことだけで、そのときコストも 1 かかります。定常方策が s3 で b を確率 q > 0 で選ぶとすると、s1 から見た継続コストは γq > 0 となり、θ(s1) = 0 を破ります。したがって実行可能な定常方策は s3 で必ず a を選ぶしかなく、価値は 0 です。

一方、履歴を見てよいなら「s1 から来たときは a、s2 から来たときは b」と選び分けられます。s1 からの部分過程のコストは 0、s2 からの部分過程のコストは γ ≤ 1 となり、すべての制約を満たしたうえで期待報酬 γ/2 を得られます。同じ状態 s3 でも、どの経路で来たかによって「この先使ってよいコスト」が違うことが本質です。論文の脚注によれば、この例では時刻に依存する方策にしても改善しません。

5-2. 定常方策の最適化はNP困難

最適性を少し犠牲にして定常方策に絞れば計算が楽になるかというと、そうではありません。論文はまず、近似の基準として (ε, δ)-最適方策を定義します。

  • δ-実行可能性:すべての部分過程制約の違反が δ 以内
  • ε-最適性:制約を厳密に満たす比較対象のどの方策と比べても、期待報酬の不足が ε 以内

そのうえで定理1として、任意の割引率 γ に対してある定数 ε, δ > 0 が存在し、定常方策の中で (ε, δ)-最適な定常方策を求めることは NP 困難であると示しています。制約を少し緩めても難しさは消えない、という強い結果です。

6. 達成可能価値集合と方策の「展開」

6-1. 報酬とコストを2次元ベクトルで扱う

履歴依存の方策は、そのまま表に書くと履歴の数(時間とともに指数的に増える)だけの領域が必要です。論文はここで発想を変え、「任意の履歴 h を渡されたら、その時点の行動分布を効率よく計算できるか」という問いを立てます。それができれば、方策を全部書き出さなくても実行できます。

鍵になるのが達成可能価値集合(achievable value set)です。各状態・行動の組が報酬とコストの2次元ベクトル x(s, a) = (r(s, a), c(s, a)) を生むとみなし、状態 s から実行可能な方策で達成できる (継続報酬, 継続コスト) のベクトル全体を V⋆(s) とします。V⋆ が分かれば、最適値は V⋆(s₀) の中で第1成分(報酬)が最大の点として求まります。

6-2. 目標値を分解して方策を作る(Expand と Achieve)

目標とするベクトル v ∈ V⋆(s) を達成する方策があるなら、ベルマン方程式と同じ形で次のように分解できます。

v=𝔼a~π¯[x(s,a)+γ𝔼s′~p(·∣s,a)w(a,s′)],w(a,s′)∈V⋆(s′)

π̄ は状態 s での行動分布、w(a, s′) は「行動 a を選んで s′ に移った後に達成すべき継続価値」です。右側の条件は、起こりうる (a, s′) の組すべてについて、次の目標もまた次の状態の達成可能集合に入っていることを要求します。

この分解を使うと、方策は次のように実行できます(論文の Algorithm 1, 2)。

  1. Expand(v, s):上の式を満たす (π̄, w) を求める
  2. π̄ から行動 a をサンプルし、次の状態 s′ を観測する
  3. 新しい目標を v′ = w(a, s′) として、s′ で同じ処理を繰り返す(Achieve)

次の目標は必ず次の状態の達成可能集合に入るので、分解は毎ステップ必ず存在し、処理は無限に続けられます。保持すべき情報は現在の目標値(2次元ベクトル)だけで、これが履歴を固定長に要約する役割を果たします。先ほどの例でいえば、s1 から来た場合は「残りのコスト予算 0」、s2 から来た場合は「予算 1」という目標値が s3 に引き継がれ、行動の選び分けが自然に実現します。

6-3. 任意の履歴の行動分布を計算する(ActProbs)

実行時にサンプリングする代わりに、与えられた履歴 h をたどって同じ分解を繰り返せば、その履歴での行動分布 π(h) を計算できます(Algorithm 3、ActProbs)。これが「方策をアルゴリズムで暗黙的に表現する」の具体的な意味です。目標値として V⋆(s₀) の中で報酬最大の点を選べば、最適方策が得られます。

残る課題は、V⋆ そのものをどう計算するかと、分解 (π̄, w) をどう効率よく求めるかの2つです。

7. 価値集合反復(VSI)の仕組み

7-1. 価値集合に作用する作用素

古典的な価値反復はベルマン作用素を繰り返し適用してスカラーの価値関数を求めます。VSI は同じことを「状態ごとの2次元ベクトルの集合」に対して行います。論文は作用素 Φ を次のように定義します。

Φ(𝒱)(s)={v∈ℝ2 | v=Bellman(s,π¯,w), (π¯,w)∈Onward(s,𝒱), v2≤θ(s)}

Bellman(s, π̄, w) は 6-2 の分解式の右辺、Onward(s, 𝒱) は「起こりうる遷移先 s′ について w(a, s′) ∈ 𝒱(s′) となる (π̄, w) の組」の集合です。最後の条件 v₂ ≤ θ(s) は、継続コスト(2番目の成分)がその状態の上限以下であることを表します。この条件が部分過程制約そのものです。論文の補題2により、達成可能価値集合 V⋆ は Φ の不動点(V⋆ = Φ(V⋆))になります。

7-2. 縮小写像ではないという難しさ

古典的な価値反復が収束するのは、ベルマン作用素が縮小写像であり、バナッハの不動点定理が使えるからです。ところが Φ は一般に縮小写像ではありません。不動点も一意ではなく、たとえば全状態に空集合を割り当てたものも自明な不動点になります。適当な初期値から反復すると、収束しないか、望まない不動点に収束するおそれがあります。

7-3. 単調性とタルスキの不動点定理による収束

論文が収束の根拠にしたのは単調性です。𝒱 ⊆ 𝒱′ なら Φ(𝒱) ⊆ Φ(𝒱′) が成り立ちます(補題4)。これはタルスキの不動点定理(完備束上の単調写像には最大不動点が存在する)と同じ構造で、V⋆ は Φ の有界な不動点の中で最大のものになります。

そこで、V⋆ を必ず含む大きな集合から反復を始めます。報酬とコストが [−1, 1] に収まるので、継続価値は各成分の絶対値が 1/(1−γ) 以下です。この正方形(L∞ 球)B を全状態の初期値にすると、Φ(B) ⊆ B かつ V⋆ ⊆ B が成り立ちます(補題5)。単調性から反復列は

V⋆⊆Vk+1⊆Vk⊆⋯⊆V0=B

のように外側から V⋆ に向かって縮んでいく入れ子の列になります(補題6)。V^k は第 k 回目の反復で得られる価値集合です。さらに、有界な不動点はすべて V⋆ に含まれること(補題7)と、コンパクト性の議論から、反復列は V⋆ に収束します(定理8)。

8. 近似VSIと多項式時間アルゴリズム

8-1. グリッドによる近似作用素

収束が示せても、それだけでは有限時間で終わるとは限りません。また、Φ を繰り返すと各状態の集合は凸多面体になりますが、その表現に必要な不等式の数が指数的に増えるおそれがあります。そこで論文は、2次元の価値空間を間隔 ξ のグリッドで離散化した近似作用素 Φ̂ を使います。

  • Φ(𝒱)(s) を L∞ 距離 ξ だけ外側に広げる(ξ-近傍)
  • その中に含まれるグリッド点の凸包を取る

この近似は Φ(𝒱)(s) を必ず含み、かつ ξ-近傍からはみ出しません。Φ̂ も単調なので、グリッドに沿って少し大きめに取った初期集合から反復すると、やはり外側から縮む入れ子の列になります。各集合はグリッド点で決まり、反復のたびに少なくとも1つのグリッド点が消えるので、グリッド点の総数を N_ξ とすると O(|S| N_ξ) 回で不動点に到達します。γ と ξ を固定すれば N_ξ は定数です。

8-2. (ε, δ)-最適性の保証

近似の不動点 V̂⋆ は V⋆ を含むので、真の最適値を取りこぼしません。逆に V⋆ の外側の点も含みえますが、それらも「δ-実行可能で、目標から ε 以内の値を達成する方策」で近似的に達成できることが示されています(補題10)。このとき分解は厳密ではなく、毎ステップ ξ 以内の誤差を許す Expand_ξ を使います。誤差は割引で減衰するので、累積しても ξ/(1−γ) 以下に収まります。グリッド間隔は次のように選びます。

ξ=(1−γ)·min{ϵ, δ/2}

ε は報酬の許容誤差、δ は制約違反の許容量です。グリッドを細かくするほど精度は上がりますが、グリッド点の数が増えて計算量も増えます。

8-3. 線形計画法への帰着

各グリッド点が Φ̂(𝒱)(s) に入るかどうかの判定と、Expand_ξ での分解の計算は、どちらも線形計画(LP)に帰着できます。素直に書くと π̄(a) と w(a, s′) の積が現れて非線形になりますが、次の状態の集合を頂点の凸結合で表し、積を補助変数に置き換えることで線形化しています(補題11)。

これらをまとめた主定理(定理12)は、γ を固定したとき、V⋆ を含む近似不動点 V̂⋆ を入力サイズ、1/ε、1/δ の多項式時間で計算でき、さらに任意の履歴 h での (ε, δ)-最適方策の行動分布を、それらと履歴の長さ |h| の多項式時間で計算できる、というものです。定常方策では近似すら NP 困難だった問題が、履歴依存を許すことで多項式時間になるという逆転が、本論文の中心的なメッセージです。論文では、履歴依存を許すことで最適性と計算効率の両方の問題が解けることを「一石二鳥」と表現しています。

9. 実装:MILPによる頂点計算とPythonコード

9-1. 全グリッド点を調べずに凸包を求める

理論上のアルゴリズムは有界な領域内のグリッド点をすべて調べますが、凸多面体の内部にある点の大半は頂点表現に不要です。そこで実装では、混合整数線形計画(MILP)を使った分離手続き(Algorithm 7)で、凸包を広げるグリッド点だけを探します。

  1. まず LP で Φ(𝒱)(s) の点を1つ見つける(見つからなければ空集合を返す)
  2. その点を含むグリッドの1マスを初期の多面体とする
  3. 現在の凸包の各面について、外向き法線方向に最も遠い実行可能なグリッド点を MILP で求める
  4. 面の外側に点が見つかれば追加して凸包を作り直し、どの面でも見つからなくなったら終了する

全次元の多面体の外にある点は必ずどこかの面の不等式を破るので、すべての面で「外側に点がない」と確認できれば、それが求める凸包であると保証されます。

9-2. 公開コード

著者の GitHub リポジトリ jrgan/VSI に Python 実装が公開されています。README によると、グリッドベースの表現を使って多目的 MDP やマルコフゲームの達成可能価値集合を計算する VSI のフレームワークで、LP・MILP のソルバーには Gurobi を使います。Φ̂(𝒱)(s) は状態ごとに独立に計算できるため、状態をまたいだ並列計算にも対応しています。

論文の図2〜4は、状態数4・行動数5の例での結果です。価値集合が反復のたびに外側から縮み、この例では37回の反復で収束する様子や、方策を実行したときの目標値の動き、コスト上限を 5.0 から −1.0 へ下げていくと達成可能集合が小さくなる様子が示されています。

10. 実務での考え方とよくある誤解

10-1. 「途中から見ても安全」を要件として書く

S-CMDP の考え方は、強化学習を直接使わない場合でも要件定義の観点として役立ちます。たとえば次のような問いを立てられます。

  • 「平均で予算内」と「どの時点から見ても予算内」のどちらが本当の要件か
  • 状態ごとに許されるリスク θ(s) は同じでよいか(混雑時、障害時、人の近くなどで厳しくする必要はないか)
  • 序盤の余裕を後半で使い切る運用を許してよいか

SLO とエラーバジェットの例のように、実運用ではすでに「途中時点からの見通し」で判断していることが多く、S-CMDP はそれを最適化問題として書き下したものといえます。

10-2. よくある誤解

  • 誤解1:制約を強めると状態だけ見ればよくなる。実際は逆で、残りのコスト予算のような情報を持ち越す必要があり、履歴依存の方策が必要になります。
  • 誤解2:履歴依存の方策は計算が爆発するので実用にならない。方策を表で持つと爆発しますが、本論文のように「目標値」という固定長の要約を持ち回り、必要な履歴についてだけ行動分布を計算すれば効率的に扱えます。
  • 誤解3:瞬時制約やピーク制約を入れれば同じ効果がある。それらは1ステップの安全性を見るもので、複数ステップ先まで続く累積的なリスクは捉えられません。

11. 論文に対する評価と限界

11-1. 論文が主張していること

論文の主張は、S-CMDP という新しい定式化の提案、定常方策の非最適性と NP 困難性、履歴依存方策を VSI で多項式時間に (ε, δ)-最適に計算できること、そして MILP を使った実装の提供です。結論では、次の課題として複数のコスト関数への拡張と、モデルが既知でない設定(モデルフリー)への拡張を挙げています。d 個のコスト関数には価値空間を d+1 次元に広げれば対応できるものの、グリッド点の数が d について指数的に増えると著者自身が述べています。

11-2. 解説者による補足

以下は論文の記述をもとにした解説者の見解です。

  • モデルベースの前提:アルゴリズムは遷移確率 p と報酬・コストが既知であることを前提にしています。環境モデルを学習しながら使う強化学習にそのまま適用できるわけではなく、論文でも今後の課題とされています。
  • 規模の問題:多項式時間とはいえ、計算量は 1/ε、1/δ に依存し、γ が 1 に近いと価値の範囲 1/(1−γ) が広がってグリッド点が増えます。論文で示されている数値例は状態数4・行動数5の小規模なもので、大規模な問題での計算時間の評価はありません。
  • 期待値の制約であること:S-CMDP は各時点からの「期待値」を制約するもので、確率1での安全性や最悪ケースを保証するものではありません。安全性が致命的な用途では、ほかの手法との組み合わせを検討する必要があります。
  • ゲーム理論との接点:価値集合反復は、すべての部分ゲームで誘因制約を満たす均衡を求める手法として発展してきたもので、部分過程制約との対応は自然です。同じ道具が意思決定と均衡計算の両方に使えるという点は、理論的に興味深い視点です。

12. まとめ:S-CMDPが示した「履歴を使うと簡単になる」構造

本記事では、到達しうるすべての履歴から先のコストに制約を課す S-CMDP(部分過程制約付きMDP)を解説しました。要点は次のとおりです。

  • 通常の CMDP は初期状態からの期待値しか制約しないため、時間方向の相殺や軌道間の平均化によって、途中で危険な見通しに入る方策を許してしまう
  • S-CMDP では定常方策が最適にならないことがあり、最良の定常方策を近似的に求めることすら NP 困難である
  • 履歴依存の方策を許し、達成可能価値集合と「目標値」の持ち回りで方策を暗黙的に表現すると、価値集合反復(VSI)とグリッド近似・LP によって (ε, δ)-最適な方策を多項式時間で計算できる
  • VSI の作用素は縮小写像ではないが、単調性により外側から縮む反復で収束が保証される
  • モデル既知の前提、複数コストへの拡張時の計算量、大規模問題での評価が今後の課題である

安全な強化学習や制約付き最適化の設計で「どの時点から見ても制約を満たすべきか」を考えるとき、本論文の定式化と結果は有力な理論的な土台になります。

13. 参考文献・関連研究

本記事は2026年11月時点で公開されている文献・情報に基づく解説です。