技術的概要：敵対的損失を伴う線形 CMDP に対する双対最適化

問題設定

本論文は、安全制約が敵対的摂動にもかかわらず満たされなければならない環境における**安全強化学習（RL）の課題に取り組む。具体的には、著者らは有限時間敵対的線形制約付きマルコフ決定過程（CMDP）**を考慮する。

この設定は、タプル $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$ によって定義される。ここで：

• 敵対的損失： 損失関数 $f^k = \{f^k_h\}$ は、各エピソード $k$ の開始時に敵対者によって任意に選択される（完全情報フィードバック）。これらの損失は固定分布から引き出されるものではない。
• 確率的コスト： コスト関数 $g^k = \{g^k_h\}$ は、安全制約を表す固定分布 $G$ から i.i.d. にサンプリングされる（バンディットフィードバック）。
• 線形構造： 遷移カーネル、損失関数、コスト関数は、既知の特徴写像 $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$ に関して線形構造を持つ。
• 目的： エージェントは、累積期待損失を最小化しつつ、累積期待コストが予算 $b$ を超えないことを保証する方策を求める。

性能はレジレット（最適方策との累積損失の差）と制約違反（予算を超える累積超過コスト）によって測定される。目標は、両方の指標に対して部分線形な上限を達成することである。

手法

著者らは、線形関数近似設定において敵対的損失と確率的制約の相互作用を処理するように設計された双対最適化アルゴリズム（アルゴリズム 1）を提案する。このアルゴリズムは、4 つの主要な構成要素を統合する。

1. エポック初期化と特徴縮約：
   アルゴリズムはエポック単位で動作する。エポックは、設計行列 $\Lambda^k_h$ の行列式が乗算因子だけ増加したときに開始される。初期化時、方策は一様方策にリセットされ、双対変数はゼロにリセットされる。重要なのは、アルゴリズムが特徴縮約を採用し、Q 関数の推定値が制御不能に拡大するのを防ぐためにシグモイド関数を用いて元の特性 $\phi$ を縮小することである。この技術は Cassel & Rosenberg (2024) から適応されたものであり、カバリング数に関する議論のために方策表現を単純化する。

2. 方策の実行と推定：
   各エピソードにおいて、エージェントは現在の方策に基づいて行動を実行し、敵対的損失と確率的コストを観測して設計行列を更新する。その後、損失関数とコスト関数のパラメータを推定し、縮約された特徴と楽観的ボーナスを用いて Q 関数推定値（$\hat{Q}$）と価値関数推定値（$\hat{V}$）を計算する。

3. 周期的方策混合：
   核心的な革新は周期的方策混合である。各エピソードごとに方策を混合（一様方策へ摂動）するのではなく、アルゴリズムは $K^B$ エピソード（ここで $B=3/4$）ごとにのみ混合を適用する。

   • 動機： 双対変数を有界にするためには（ドリフト分析を通じて）頻繁な混合が必要であるが、これは方策クラスのカバリング数を増大させる。周期的混合は、これらの競合する要件のバランスを取る。
   • メカニズム： 各 $K^{3/4}$ エピソードごとに、現在の方策 $\hat{\pi}^k$ は一様方策 $\pi_{unif}$ と凸結合によって混合される：$\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$。

4. 正則化された双対更新：
   双対変数 $Y^k$（コスト制約に関連する）は、正則化された勾配上昇ステップを用いて更新される：
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   正則化項（$-4\alpha\eta H^3 Y^k$ と定数）は、双対変数をゼロ方向に引き寄せ、敵対的設定では失敗する強双対性の仮定に依存せずに $Y^k$ を有界にするためのリャプノフ・ドリフト分析を可能にするように設計されている。

5. 重み付き LogSumExp ソフトマックス方策：
   結果として得られる方策クラスは重み付き LogSumExp ソフトマックスである。周期的混合により、方策は Q 関数の和の単純な指数関数ではなく、Q 関数推定値の部分的な和の指数関数の重み付き和となる。この構造により、方策は敵対的に選択された損失に適応しつつ、管理可能なカバリング数を維持できる。

主要な貢献

1. 敵対的線形 CMDP に対する最初の部分線形上限：
   本論文は、敵対的損失と確率的コストを伴う線形 CMDP の設定において、部分線形なレジレットと制約違反の上限を達成する最初のアルゴリズムを提示する。上限は $\tilde{O}(K^{3/4})$ であり、ここで $K$ はエピソード数である。

2. 新しいカバリング数議論：
   著者らは、重み付き LogSumExp ソフトマックス方策に対する新しいカバリング数議論を確立する。重みが均一な標準的なソフトマックス方策とは異なり、混合プロセスは変化する重みパラメータ $\zeta_i$ を導入する。著者らは、このクラスのカバリング数の対数が $\tilde{O}(n^2 d^2)$ として増加することを証明する。ここで $n$ は混合ステップ数、$d$ は特徴次元である。この結果は、重みパラメータが混合パラメータと Q 関数推定値の両方に依存するため、非自明である。

3. 制御のためのアルゴリズム的構成要素：
   本論文は、カバリング数と双対変数を共同で制御するための 2 つの新しい構成要素を導入する。

   • 周期的方策混合： 混合の頻度を調整して、カバリング数が大きくなりすぎるのを防ぐ（$O(K)$ 回の混合ステップでは起こりうる）一方で、双対変数を有界にするために十分に頻繁に発生させる。
   • 正則化された双対更新： ドリフトベースの分析を容易にするために正則化項を組み込んだ新しい更新規則。これにより、強双対性が存在しない場合でも双対変数を有界にできる。

結果

理論的保証：
Slater 条件（仮定 1）の下で、かつ $H^2 \leq K$ を仮定すると、確率 $1-\delta$ 以上で、アルゴリズムは以下の性能を達成する：

• レジレット： $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• 制約違反： $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

両指標は $K$ に対して部分線形（具体的には $K^{3/4}$）にスケーリングし、エピソード数が増加するにつれて平均レジレットと平均制約違反がゼロに収束することを示している。

数値実験：
このアルゴリズムは、敵対的損失を伴う修正されたジョブスケジューリング CMDP 上で評価された。100,000 エピソードにわたり：

• レジレット： 理論的限界を確認して部分線形に増加した。
• 制約違反： 初期には急速に増加したが、約 45,000 エピソード後にゼロに収束し、長期的に安全制約を満たすアルゴリズムの能力を検証した。

意義と主張

本論文は、敵対的設定における線形関数近似を伴う安全 RL に対する初めて証明的に効率的なアルゴリズムであると主張する。その意義は、以下の 2 つの間のギャップを埋める点にある。

1. 表形式の敵対的 CMDP： 以前の研究（例：Qiu et al., 2020）は敵対的設定を扱ったが、小さく有限な状態空間に限定されていた。
2. 線形確率的 CMDP： 以前の研究（例：Ghosh et al., 2022）は大きな状態空間を扱ったが、定常的（確率的）な環境を仮定していた。

重み付き LogSumExp ソフトマックス方策と周期的混合戦略を導入することで、著者らは、大きな状態空間（線形近似を通じて）と敵対的損失を同時に処理することが可能であることを実証する。本論文は控えめに、$\tilde{O}(K^{3/4})$ が達成されたものの、混合ステップとカバリング数のトレードオフに関して、この特定の設定における最適な $\tilde{O}(\sqrt{K})$ 上限は未解決の問題であると指摘している。また、この研究は、敵対的線形 CMDP において占有測度に基づく双対更新を方策ベースの手法に拡張することの難しさを強調し、提案された双対最適化アプローチの正当性を裏付けている。