Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

技術要約：ロバストな平均報酬マルコフ決定過程

問題定式化
本研究は、生成モデル設定における、分布ロバストな平均報酬マルコフ決定過程（AMDP）の$\epsilon$-最適方策を学習するための統計的複雑性を調査するものである。エージェントは、遷移カーネル$P^0$と報酬関数$r$によって定義される公称環境内で動作する。しかし、真の環境ダイナミクスは不確実であり、$P^0$を中心とする規定された不確実性集合$\mathcal{P}$内に存在する可能性がある。具体的には、本論文では、半径が最大で$\sigma$である$(s, a)$-矩形全変動（TV）不確実性集合を検討している。

目的は、ロバスト平均報酬を最大化することである。これは、$\mathcal{P}$内のすべての遷移カーネルに対する最悪の長期平均報酬として定義される：
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
学習の目標は、$N$個のサンプル（状態行動ペアあたり）を用いて、$\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$を満たす方策$\hat{\pi}$を計算することである。ここで、$\rho^{\star, \sigma}$は最適なロバスト平均報酬を表す。

主要パラメータと構造的仮定
解析は、以下の2つの重要な構造的パラメータに基づいている：

1. 公称最適バイアス・スパン ($H_0$): 公称ベルマン最適方程式を満たすバイアス関数のスパン。
2. ロバスト最適バイアス・スパン ($H_\sigma$): ロバスト・ベルマン最適方程式を満たすバイアス関数のスパン。

本論文は、$H_0$と$H_\sigma$が一般に独立しており、一方が他方を制御するわけではないことを確立している。重要な摂動スケールとして$\sigma H_0$が特定されており、これが学習問題を2つの異なるレジームに分離する：

• 高許容レジーム (High-Tolerance Regime) ($\epsilon \gtrsim \sigma H_0$): 不確実性による摂動が、目標精度に対して小さい場合。
• 低許容レジーム (Low-Tolerance Regime) ($\epsilon \lesssim \sigma H_0$): 摂動が顕著であり、公称最適化のみではロバスト最適性を保証するのに不十分な場合。

手法：還元に基づくプラグイン・プロシージャ
中核となる手法的な貢献は、困難なロバスト平均報酬問題を、より扱いやすいロバスト割引MDP（DMDP）問題へと変換する還元フレームワークである。著者らは、この還元に基づく2つのアルゴリズムを提案している：

1. スパン情報型プロシージャ (Algorithm 1): $H_0$および$H_\sigma$が既知であることを想定する。これは、公称還元（経験的カーネルを用いた標準的なDMDPを解く）と、ロバスト還元（不確実性集合上のDMDPを解く）の間を適応的に選択する。選択は、$H_0$と$H_\sigma$の順序および許容レジームに依存する。割引因子$\gamma$は、関連するスパンパラメータに基づいて校正される（例：$\gamma = 1 - \epsilon/(3H_\sigma)$）。
2. スパン非依存型プロシージャ (Algorithm 2): $H_0$または$H_\sigma$の知識なしに動作する。これは、割引因子の二分格子（dyadic grid）にわたる公称およびロバスト還元の両方から候補方策の集合を構築する。その後、別のデータバッチから計算された「アンカー証明書（anchor certificate）」を用いたロバスト平均報酬の下限信頼境界（LCB）を用いて、最適な方策を選択する。これにより、アルゴリズムはデータに基づいて正しい還元と割引因子を適応的に選択できる。

解析では、タイトな境界を得るために、以下の3つの主要な技術的洗練を活用している：

• 分散項をタイトにするために、ロバストな割引問題と公称参照解（アンカー）を比較すること。
• 有効ホライゾンではなく、そのスパン（$H_\sigma$）を通じて割引価値関数を制御すること。
• スパンによって制御される局所集中不等式を用いること。

主要な結果：ミニマックス・サンプル複雑性
本論文は、対数因子を除いて一致する、ミニマックス・サンプル複雑性$N_{SA}$（状態行動ペアあたりのサンプル数）の上界と下界を提供している。複雑性は、$H_0$と$H_\sigma$の順序および許容レジームに基づく4つのレジームの要約によって特徴付けられる：

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{if } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{if } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$$

• 高許容レジーム: 複雑性は線形スパン項$\min\{H_0, H_\sigma\}$によって支配される。$H_\sigma \leq H_0$の場合、ロバスト還元は公称還元よりもタイトな境界をもたらす。
• 低許容レジーム: 追加の「ロバスト性特有」の項$\sigma H_\sigma^2$が現れる。これは、高い精度が必要な場合に分布の不確実性を扱うためのコストを表している。
• 下界: 著者らは、上界と一致するミニマックス下界を証明し、低許容レジームにおいて$\sigma H_\sigma^2$の項が基本的であり、回避できないものであることを確立した。これは、分布ロバストAMDPの統計的限界を特徴付ける初の低界である。

意義と主張
本論文は、分布ロバストAMDPのサンプル複雑性に関する初のミニマックス最適な特性付けを提供することを主張している。主な貢献は以下の通りである：

• サンプル複雑性のギャップの解消: 従来のロバスト上界（例：Rochら、2025, 2026）は、高・低許容の区別なしに、ロバスト・スパンの二次的な依存関係（$H_{Roch}^2$または$H_{RHI}^2$）に依存していた。本研究は、高許容レジームにおける$\min\{H_0, H_\sigma\}$への精緻化を行い、低許容レジームにおける正確な$\sigma H_\sigma^2$のコストを特定した。
• 適応的アルゴリズム: 提案されたスパン非依存型プロシージャ（Algorithm 2）は、スパンパラメータの事前知識なしに、自動的にレジームと$H_0$および$H_\sigma$の相対的な大きさに適応して、これらの最適なレートを達成する。
• 汎用性: 結果は、$H_\sigma$のみが有界であると仮定されている場合でも成立し、複雑度は$\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$となる。

制御されたシミュレーションによる実験結果は、予測された$\min\{H_0, H_\sigma\}$への線形依存性と、低許容レジームにおける$\sigma H_\sigma^2$への二次依存性、およびスパン非依存型アルゴリズムの適応性を検証している。著者らは、今後の研究として結合された不確実性構造やオンライン（リグレットベース）の設定を探求できる可能性があると述べているが、現在の研究は厳密に生成モデルの設定に焦点を当てている。