Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

技術要約：$L^\infty$ 上のベルマン作用素を用いた CVaR MDP に対する報酬再分配

問題提起
安全性に敏感なアプリケーションにおいて、期待リターン（リスク中立）を最適化することは、稀ではあるが壊滅的な結果を許容してしまう可能性があるため、不十分な場合が多い。静的条件付き期待値（Static Conditional Value-at-Risk: CVaR）は、リターンの下側テイルを制御するために用いられる一貫したリスク尺度である。しかし、リスク中立的な目的関数とは異なり、静的 CVaR はリターンの分布に対して再帰的な分離性を欠いており、標準的なマルコフ的なベルマン分解を妨げる。

Bäuerle & Ott (2011) に代表される既存のアプローチは、累積報酬を追跡する連続的な「予算」変数を状態空間に拡張することでこれに対処している。この定式化は理論的には妥当であるが、実用面において以下の2つの決定的な制限がある：

1. 疎な報酬 (Sparse Rewards): CVaR に関する情報は、拡張された状態の終端関数に完全に集中している。これにより、拡張されたマルコフ決定過程（MDP）における各ステップの報酬はゼロとなり、フィードバックが遅延するため、特に無限ホライゾン設定において探索と時間的なクレジット割り当ての課題を悪化させる。
2. 限定的な収束性 (Restricted Convergence): Bäurele & Ott の定式化に関連するベルマン作用素は、高度に制限された非有界関数の集合に対してのみ縮小写像であることが保証されている。より実用的な有界関数（$L^\infty$）の空間においては、この作用素は退化した不動点（ゼロ関数）を許容するため、注意深い（しばしば実行不可能な）初期化制約なしには、標準的な価値反復法や Q 学習を適用できない。

手法
著者らは、価値関数の代数的な変換を通じて、これらの制限を解決する新しい静的 CVaR 目的関数の再定式化を提案する。

1. 変換された拡張 MDP: Bäurele & Ott (2011) の状態拡張に基づき、著者らはシフト項 $z^-$（予算の負の部分）を組み込んだ新しい価値関数 $\bar{v}^*(s, z)$ を定義する。この変換により、有界関数の空間 $L^\infty(\bar{S})$ 上で定義される新しいベルマン作用素 $\bar{T}$ の導出が可能となる。
2. 報酬の再分配: キーとなる革新は、新しいステップごとの報酬関数 $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$ の定義である。以前の定式化では中間報酬がゼロであったのに対し、この新しい報酬は各ステップで密かつ情報量が多く、CVaR に関する信号を軌道全体に効果的に再分配する。
3. 縮小特性: 著者らは、新しい作用素 $\bar{T}$ が全有界関数の空間における sup-norm に関して $\gamma$-縮小写像であることを証明している。これにより、前述の研究のような制限的な初期化条件を必要とせずに、価値反復法が唯一の不動点に収束することが保証される。
4. 離散化と近似: $z$ は連続値であるため、著者らは一様離散化スキームを採用する。エンベロープ関数を用いて、真の作用素を近似する下界および上界の作用素（$\bar{T}^l$ および $\bar{T}^u$）を定義する。真の CVaR と離散近似との間の誤差が、離散化の粒度および割引係数に比例してスケールすることを示す理論的境界を確立する。
5. アルゴリズム: このフレームワークに基づき、以下のアルゴリズムを開発する：
   • 静的 CVaR 価値反復法 (Static CVaR Value Iteration): すべての初期状態および予算レベルに対して最適な Q 関数を同時に計算するモデルベースのアルゴリズム。
   • 静的 CVaR Q 学習 (Static CVaR Q-Learning): ブロック更新戦略を利用するモデルフリーのアルゴリズム。拡張された状態遷移の決定論的な性質を利用し、単一の軌道を再ラベル付けすることで、複数の初期予算仮説に対する Q 値を更新し、データ効率を向上させる。収束は、標準的な Robbins-Monro ステップサイズ条件の下で証明される。

主な貢献

• 新しいベルマン作用座: 無限ホライゾンの静的 CVaR に対して、拡張された状態空間上で動作し、制御目的に対して厳密であり、疎ではないステップごとの報酬を提供し、有界関数上の縮小写像となる新しいベルマン作用素を導入した。
• 近似保証: 離散化された静的 CVaR に対する近似誤差の厳密な境界を提供し、グリッド解像度の関数としてパフォーマンスのギャップを定量化した。
• 収束の証明: 提案された Q 学習アルゴリズムが、離散化された拡張空間において最適な行動価値関数に収束するための十分条件を確立した。
• 大域的最適性: アルゴリズムは、個別のリスクパラメータごとに別途学習を行うのではなく、単一の実行で、すべてのリスクレベル（初期拡張状態）に対する大域的な最適解を与える。

実験結果
著者らは、エージェントが目標地点へ向かう一方で、クレーター（高いペナルティ）を回避しつつ燃料使用量（ステップペナルティ）を最小化する必要がある確率的グリッドワールド環境（"Crater Walk"）を用いて、提案手法を検証した。

• リスク感受性: 学習された方策は、リスクパラメータ $\alpha$ に基づいて行動を調整することに成功した。$\alpha$ が減少する（リスク回避度が高まる）につれて、リターンの下側テイルが縮小し、たとえ経路が長くなったとしても、エージェントはクレーターを避ける挙動を示す。
• パフォーマンス: 価値反復法と Q 学習の両アルゴリズムは、効果的なパフォーマンスと安全性のトレードオフを実現した。Q 学習アルゴリズムは 50,000 回のトレーニングイテレーション以内に収束した。
• 離散化の精度: 離散化解像度（100 から 5000 ビンまで）を変化させた実験により、上界および下界の作用素のパフォーマンス曲線が、解像度の増加とともに真の最適値に収束することが示され、理論的な誤差境界が経験的に検証された。

意義と主張
本論文は、静的 CVaR MDP における疎な報酬と制限された収束保証の限界は、問題固有のものではなく、先行文献における特定のモデリングの選択によるアーティファクトであると主張している。報酬を再分配し、有界関数上で動作する厳密な再定式化を提案することで、著者らは、標準的な動的計画法およびモデルフリー強化学習技術を、静的なリスク感受性問題に適用することを可能にした。本研究は、ヒューリスティックな報酬のキャップ（上限設定）や特殊なリスクカリキュラムに依存しない、スケーラブルなリスク回避型 RL アルゴリズムの基礎を築くものである。著者らは、経験的分析は表形式の設定に焦点を当てているものの、理論的枠組みは、報酬の符号制限なしに連続的な状態空間を扱うための関数近似（例：ディープニューラルネットワーク）への将来的な拡張をサポートしていると述べている。