技術要約：外生的なコンテキストを持つMDPにおける学習のためのMinimax PAC境界

1. 問題設定

本論文は、**外生的なi.i.d.コンテキストを持つ表形式の割引マルコフ決定過程（MDP）**における学習のサンプル複雑性を調査している。モデルは、タプル $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$ によって定義される：

• $\mathcal{X}$ は有限の制御された状態空間である。
• $\mathcal{A}$ は有限のアクション空間である。
• $\mathcal{Z}$ は有限のコンテキスト空間である。
• $\gamma \in [0, 1)$ は割引因子である。
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ は遷移カーネルである。
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ は報酬関数である。
• $\mu$ は未知のコンテキスト上の分布である。

各タイムステップ $t$ において、コンテキスト $Z_t$ は $\mu$ から独立に抽出され、エージェントがアクションを選択する前に公開される。エージェントは $A_t$ を選択し、報酬 $r(X_t, A_t, Z_t)$ を受け取り、$X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$ へと遷移する。極めて重要な点は、次ステップのコンテキスト $Z_{t+1}$ はエージェントのアクションや現在の状態には依存せず、$\mu$ にのみ依存することである。

学習目標は、方策評価（Policy Evaluation: PE）、最良値推定（Best-Value Estimation: BVE）、および**最良方策抽出（Best-Policy Extraction: BPE）**である。サンプル複雑性は、オフライン学習フェーズで行われるオラクル呼び出しの数と、意思決定時（クエリ）フェーズで行われる呼び出しの数を示すペア $(n_{\text{learn}}, m_{\text{query}})$ によって測定される。本論文では以下の2つのレジームを検討する：

1. 既知のダイナミクス（Known Dynamics）: $P$ と $r$ は既知であり、$\mu$ のみが未知である。
2. 完全未知（Fully Unknown）: $\mu$ と $P$ の両方が未知である。

2. 手法

2.1 コアとなる洞察：平均化された価値関数

中心的な手法論的貢献は、問題を拡張された空間 $\mathcal{X} \times \mathcal{Z}$ から制御された状態空間 $\mathcal{X}$ へと削減することである。著者らは、平均化された価値関数 $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$ を定義する。
次のコンテキストは $\mu$ から独立に抽出されるため、平均化された $\bar{V}^\star$ に対するベルマン最適方程式は、$\mu$ で平均化された遷移カーネルのみに依存する：
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
この定式化により、学習者は $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$ ではなく $\mathbb{R}^{|\mathcal{X}|}$ のベクトルを推定することが可能となり、実質的にコンテキスト空間のサイズ $|\mathcal{Z}|$ からの複雑性を切り離すことができる。

2.2 アルゴリズムの枠組み：分散減少型ハルビング（Variance-Reduced Halving）

本論文では、平均化された価値関数を推定するために、**分散減少型価値反復（variance-reduced value iteration）**スキーム（Sidford et al., 2019を適応したもの）を採用している。アルゴリズムは以下の2つのフェーズで動作する：

1. オフラインフェーズ（アンカー推定）: アルゴリズムは、初期の価値推定値に適用されたベルマン作用素に対する高確率な下界（アンカー）を計算する。これは、経験平均の分散を制御するために、大規模なサンプルバッチを必要とする。
2. オンライン／反復フェーズ（分散減少更新）: 後続の反復では、現在のベルマンバックアップとアンカーとの「差分」のみを推定する。同じサンプルを差分項に対して再利用することで、分散が大幅に減少し、反復あたりのサンプルサイズを小さくすることができる。

アルゴリズムは、「ハルビング（半分にする）」戦略を用い、ターゲット精度 $\epsilon$ に達するまで誤差境界 $u$ を繰り返し半分にするサブルーチン（HALFERR）を呼び出す。

2.3 未知のダイナミクスの扱い

完全未知のレジームでは、アルゴリズムは、たとえサンプリングされたコンテキストがあったとしても、ベルマンバックアップを正確に計算することはできない。代わりに、サンプリングされた各コンテキスト $Z$ に対して、アルゴリズムは遷移サンプル $X' \sim P(\cdot | x, \pi(x, Z), Z)$ を引き、バックアップの不偏推定値を形成する。これにより、コンテキストと遷移のランダム性の両方を考慮した、遷移カーネルに関連する追加の分散項が導入されるが、これはマルチンゲール分解を用いて厳密にバウンドされる。

3. 主な結果

3.1 既知のダイナミクス、未知のコンテキスト分布（$P, r$ は既知、$\mu$ は未知）

遷移カーネルと報酬が既知の場合、本論文はサンプル複雑性がコンテキスト空間のサイズ $|\mathcal{Z}|$ に依存しないことを確立している。

• 複雑性: アルゴリズムは、$(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$ （ここで $\beta = (1-\gamma)^{-1}$）の目的を達成する。
• 最適性: $\Omega(\beta^3/\epsilon^2)$ のミニマックス下界が証明されており、上界が対数因子を除いてタイトであることを示している。
• 示唆: 学習者はすべての $(x, z)$ ペアに対して値を推定する必要はなく、平均化された価値 $\bar{V}$ を推定するだけで十分である。既知の $P$ と $r$ を用いた決定論的なベルマンバックアップによって $\bar{V}$ から $V(x, z)$ へのリフトが可能であるため、クエリフェーズでは追加のサンプルを必要としない（$m_{\text{query}}=0$）。

3.2 完全な1ステップ・ルックアヘッドへの適用

このフレームワークは、完全な1ステップ遷移ルックアヘッドの設定（エージェントが行動する前に、考えられるすべてのアクションに対して考えられるすべての次状態を観察できる設定）に適用される。

• この設定は、コンテキスト空間がすべての可能な遷移テンソルの集合である外生的なコンテキストMDPの特殊なケースであることが示されている。
• この結果、$\tilde{O}(\beta^3/\epsilon^2)$ のルックアヘッドサンプルというサンプル複雑性が得られる。
• 個別の表形式の遷移という観点では、これは $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$ に相当し、Lu et al. (2025) による以前の境界を $\beta$ の因子分改善している。

3.3 完全未知のレジーム（$P$ と $\mu$ は共に未知）

ダイナミクスとコンテキスト分布の両方が未知の場合、本論文は方策評価（PE）に焦点を当てている。

• 複雑性: アルゴリズムは、$(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$ を達成する。
• トレードオフ: オフラインフェーズでは平均化された価値 $\bar{V}^\pi$ を学習し（コンテキストサンプルあたり $|\mathcal{X}|$ 個の遷移を要する）、クエリフェーズでは、実現された $(x, z)$ における最終的な1ステップ遷移期待値を新鮮なサンプルを用いて推定する。
• 下界: 本論文は一致する下界を証明しており、以下を示している：
  • 意思決定時の精度には $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ が必要である。
  • オフライン学習には $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ が必要である。
• 重要性: 完全未知のレジームであっても、複雑性は $|\mathcal{Z}|$ に依存しないままである。未知のダイナミクスは、拡張された空間上での推定を強制するのではなく、$\bar{V}$ から $V(x, z)$ への意思決定時の「リフト」における確率性を導入するに過ぎない。

4. 意義と主張

本論文は、外生的なコンテキストMDPにおける学習のための、初のミニマックス最適なPAC境界を提供することを主張している。その主な貢献は以下の通りである：

1. コンテキストサイズからのデカップリング: コンテキスト空間の大きな統計的代償を回避可能であることを示している。サンプル複雑性は制御された状態空間 $|\mathcal{X}|$ には依存するが、コンテキスト空間 $|\mathcal{Z}|$ には依存しない。
2. 最適なレート: 導出されたレート（既知のダイナミクスでは $\tilde{O}(\beta^3/\epsilon^2)$、完全未知では $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$）は、対数因子を除いてミニマックス最適であることが示されている。
3. 統一されたフレームワーク: 既存の完全な1ステップ・ルックアヘッドの結果を包含し、改善しており、オフライン/オンラインのサンプル・トレードオフに関する厳密な分析を提供している。

著者らは、下界が純粋なオンライン・ポイント（$n_{\text{learn}}=0$）および再利用可能なオラクル・ポイント（提案アルゴリズム）においてタイトである一方で、中間的なトレードオフにおける境界のタイトさについては未解決の課題として残っていると述べている。また、遷移サンプルからアクションの最大値（maximum over actions）を推定する際の選択バイアス（selection bias）の扱いが困難であるため、完全未知のレジームにおける最良方策抽出（BPE）への拡張は今後の課題とされている。