技術要約：$Q^\star$-近似と部分的カバレッジにおけるオフライン強化学習の複雑性について

問題提起

本研究は、$Q^\star$-実現可能性（$Q^\star$-realizability）および部分的カバレッジ（partial coverage）の下での**オフライン強化学習（RL）**の理論的限界を調査するものである。このパラダイムでは、エージェントは環境とのさらなる相互作用なしに、固定された事前収集データセットから方策を学習する。このデータセットは、状態行動空間全体をカバーしていない可能性のある行動方策（部分的カバレッジ）によって生成される。

対処すべき中心的な未解決問題は、$Q^\star$-実現可能性（真の最適Q関数が既知の関数クラス内に存在する）と、ベルマン完全性（Bellman completeness：ベルマン演算子が関数クラスをその上位集合へと写す）を組み合わせた条件が、サンプル効率的な学習を保証するために十分であるかどうかである。これらの条件は、真の $Q^\star$ を含む信頼集合（confidence set）の構築を可能にするが、本論文は、それが堅牢な方策選択を保証するのに十分であるかどうかを疑問視している。

手法

1. 情報理論的下界

著者らはまず、上述の条件がサンプル効率的な学習には不十分であることを示す。彼らは以下の性質を持つマルコフ決定過程（MDP）のファミリーを構成した：

• $Q^\star$-実現可能性とベルマン完全性が成立している。
• 最適方策のカバレッジが定数（$\Theta(1)$）である。
• 真の値関数は関数クラス内で良好に局在化しているにもかかわらず、学習者は破滅的なエラーにつながる方策と、安全な方策を区別することができない。
• 必要なサンプル複雑性は $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$ にスケールする。ここで $\Delta$ は値のギャップである。これは、ギャップが小さい場合でもサンプル複雑性が極めて高くなる可能性があり、困難の本質は単なる $Q^\star$ の推定ではなく、曖昧な集合内での堅牢な意思決定にあることを示唆している。

2. 意思決定・推定分解フレームワーク

特定されたギャップに対処するため、著者らはオンラインRLにおける決定推定係数（DEC）に着想を得た、一般的な意思決定・推定フレームワークを導入する。彼らはオフラインRLの劣最適性を、以下の2つのモジュール成分に分解する：

1. 意思決定の複雑性（Decision Complexity）: 妥当なモデルの信頼集合から堅牢な方策を選択することの難しさ。
2. 推定誤差（Estimation Error）: オフラインデータから価値関数またはモデルパラメータを推定する際に生じる誤差。

彼らは、**オフライン堅牢意思決定・推定係数（$Ordec$）**を以下のように定義する：
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
ここで：

• $F_{conf}$ は、妥当な $Q^\star$ 関数の信頼集合である。
• $\mathcal{M}_{conf}$ は、それによって誘導される妥当なモデルの集合である。
• $\rho$ は方策の分布である。
• $D_\pi(f \| M)$ は、関数とモデルの間の不一致尺度（例：ベルマン誤差）であり、オンラインDECとは異なり、候補モデルの最適方策 $\pi_M$ の下で評価される。

このフレームワークは、混合方策 $\hat{\pi}$ を出力するアルゴリズム（E2D.OR）を提案しており、以下を満たす：
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Estimation Error}$$

主な貢献

1. 十分性に関する否定的な結果

本論文は、$Q^\star$-実現可能性、部分的カバレッジ、およびベルマン完全性は、サンプル効率的なオフラインRLにとって十分ではないことを証明する情報理論的な下界を提供している。これは、部分的カバレッジの設定における核心的な課題が、単なる「推定」の問題ではなく、信頼集合内での「意思決定」の問題（安全な方策と安全でない方策を区別すること）であることを浮き彫りにしている。

2. 統一フレームワークと改善された境界

提案された $Ordec$ フレームワークは、既存の結果を統合し、改善する：

• 値ギャップ設定: Chen and Jiang (2022) の結果を回収するが、ギャップの値を知る必要や追加のオンライン相互作用を必要としない。この境界は、真のギャップに自動的に適応する。
• 正則化設定: 部分的カバレッジ下でのソフトQ学習のサンプル複雑性の境界を、$\epsilon^{-4}$ (Uehara et al., 2023) から $\epsilon^{-2}$ へと改善する。これは、正則化されたMDPのための新しい二次の性能差レマ（performance difference lemma）を通じて達成される。
• 曲がった決定境界: 連続的な行動空間における決定境界の曲率に基づく、新しい学習可能な設定を導入し、厳密な値ギャップ仮定に関する実用的な懸念に対処している。

3. 推定誤差のための新しい学習可能領域

本論文は、推定誤差を制御するための構造的仮定の役割を特徴づけている：

• ベルマン完全性: 一般的な関数近似下での**保守的Q学習（CQL）**に対する初のサンプル複雑性解析を提供する（これまではテーブル形式に限定されていた）。
• 低ベルマンランク: 低ベルマンランクMDP（典型的なオンラインRLの設定）のオフライン学習可能性を調査する。著者らは、標準的なデータ仮定の下では、低ベルマンランクはオフライン学習には不十分であることを示している。彼らは、この領域での学習可能性のために2つの必要な条件を導入した：
  1. ダブル方策サンプリング（Double Policy Sampling）: データが、ある方策をサンプリングした後、2つの独立した遷移を行うことによって生成されている必要がある。
  2. 方策特徴量カバレッジ（Policy Feature Coverage）: 方策の特性空間に関する特定のカバレッジ条件。
     これらの条件のいずれかを緩和すると、多項式的なサンプル複雑性の保証が崩れる。

結果の要約

• 下界: $Q^\star$-実現可能性 + ベルマン完全性 + 部分的カバレッジ $\nRightarrow$ サンプル効率的な学習であることを示した。
• 上界: $Ordec$（意思決定の複雑性）と推定誤差に分解された、一般的な劣最適性の境界を確立した。
• 具体的な境界:
  • 非正則化（値ギャップ）: $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$。未知のギャップに適応する。
  • 正則化: $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$ を与え、$\epsilon^{-2}$ のサンプル複雑性を実現する。
  • CQL: 部分的カバレッジ下での一般の関数近似に対する最初の保証。
  • 低ベルマンランク: 標準的な仮定の下での不可能性を証明し、学習可能性にはダブル方策サンプリングと方策特徴量カバレッジが必要であることを特定した。

意義と主張

本論文は、$Q^\star$-近似および部分的カバレッジの下でのオフラインRLの可能性と限界について、より包括的な理解を提供すると主張している。その意義は以下の点にある：

1. 困難さの源泉の明確化: 理論的な焦点を純粋な推定誤差から、部分的カバレッジ設定に固有の意思決定の複雑性へとシフトさせ、追加の構造的仮定がなければ、完璧な推定があっても堅牢な意思決定が不可能であることを示した。
2. 統一: 意思決定の複雑さと推定の複雑さを分離することで、既存の結果（Chen and Jiang, 2022; Uehara et al., 2023）を回収、改善、拡張するモジュール型のフレームワークを提供する。
3. 実用的な関連性: 一般的な関数近似下での CQL を分析し、低ベルマンランクの問題に必要な特定の構造的要件を特定することで、本研究は、これまで捉えにくい、あるいは理解が不十分であった設定における実用的なアルゴリズムと理論的保証の架け橋となる。
4. 設定の新規性: 低ベルマンランクMDPにおける初の学習可能性条件を確立し、部分的カバレッジ下での正則化されたソフトQ学習に対する初の $\epsilon^{-2}$ 境界を提供した。

著者らは、フレームワークは理論的には健全であるが、ミニマックスアルゴリズムを正確に解くことは計算量的に困難であり、アクター・クリティック法によって近似可能である可能性があると述べている。本研究の主な目的は、新しい学習可能な領域を特定し、それらに必要な構造的条件を特徴づけることにある。