技術的概要：強化学習におけるバンドットフィードバックを用いた良質方策の純粋探索

1. 問題定式化

本論文は、強化学習（RL）の純粋探索の枠組み内における「良質方策同定（Good Policy Identification: GPI）」問題を取り扱います。高確率で（近）最適方策を同定することを目指す従来の「最適方策同定（Best Policy Identification: BPI）」目的とは異なり、GPI は特定の性能閾値を満たす方策を見つけることに焦点を当てています。

形式的には、未知の遷移ダイナミクス $P$ と初期分布 $p$ を持つエピソード型マルコフ決定過程（MDP）、有限な状態空間 $S$、行動空間 $A$、および時間地平 $H$ が与えられたとき、エージェントには報酬閾値 $\mu_0$ が提供されます。目標は、以下の条件を満たす $\delta$-確率的近似正解（$\delta$-PAC）アルゴリズムを設計することです：

• 陽インスタンス: 期待総報酬 $V^\pi_0(s_0) \ge \mu_0$ となる方策 $\pi$ が存在する場合、アルゴリズムは確率少なくとも $1-\delta$ でそのような方策を出力しなければならない。
• 陰インスタンス: 最適方策の値 $V^*_0(s_0) < \mu_0$ である場合、アルゴリズムは確率少なくとも $1-\delta$ で「なし（None）」を出力しなければならない。

性能指標は、正しい決定に至るために必要な期待サンプル複雑性（探索されたエピソード数の期待値、$\tau$ と表記）です。本論文は、$V^*_0(s_0) = \mu_0$ のケースを明示的に除外しており、これは過去の研究（Degenne and Koolen [2019]）において、この境界ケースではいかなる $\delta$-PAC アルゴリズムも無限のサンプルを必要とすることが確立されているためです。

2. 手法：BEE-GPI

著者は「良質方策同定のためのバランス型探索・活用（Balanced Exploration-Exploitation for Good Policy Identification: BEE-GPI）」と名付けられた新しいアルゴリズムを提案します。このアルゴリズムは $k=1, 2, \dots$ のフェーズで動作し、各フェーズは適応的探索ステージに続き、意思決定分岐メカニズムで構成されます。

主要コンポーネント：

1. 探索ステージ（ES-BPI-UCRL）:

   • このステージは、早期停止型 BPI-UCRL オラクルを利用します。これは、遷移カーネルと値関数を推定するために、BPI-UCRL と同様の楽観的サンプリング戦略を採用します。
   • 重要なのは、新しい早期停止メカニズムを導入している点です。オラクルは各ステップで以下の 2 つの条件をチェックします：
     • 条件 (3): 現在の楽観的方策の値に対する下側信頼区間が $\mu_0$ を超える（係数 $C$ で調整される）。これが満たされれば、候補方策が同定されます。
     • 条件 (4): 最適値関数に対する上側信頼区間が $\mu_0$ 未満である。これが満たされれば、インスタンスは陰と宣言されます。
   • いずれの条件も満たされず、探索予算 $T^{ee}_k$ を超過していない場合、アルゴリズムはサンプリングを継続します。

2. 意思決定分岐:

   • オラクルが「未完了」を返した場合、アルゴリズムはより厳密な誤差許容度 $\delta_k$ と増大した予算で次のフェーズに進みます。
   • オラクルが「なし」を返すが、信頼性が不十分（$\delta_k \ge \delta/10$）な場合、$\delta$-PAC の保証を確保するためにアルゴリズムは次のフェーズへ継続します。
   • オラクルが候補方策 $\hat{\pi}_k$ を返した場合、アルゴリズムは活用ステージに入ります。

3. 活用と検証:

   • このステージでは、候補方策 $\hat{\pi}_k$ を繰り返し実行して、その真の値を推定します。
   • アルゴリズムは経験平均報酬に対する信頼区間を構築します。特定のサンプル予算内で下側信頼区間が $\mu_0$ を超える場合、その方策が解として出力されます。
   • 予算が尽きても検証が完了しない場合、アルゴリズムは次のイテレーションの探索フェーズに戻ります。

3. 主要な貢献

本論文は、以下の 3 つの主要な理論的貢献を行います：

1. GPI の定式化: 著者は、固定信頼度設定における良質方策同定問題を $\epsilon$-BPI と区別して正式に定義します。標準的な $\epsilon$-BPI への帰着が GPI に対して最適でないことを強調しています。その理由は、$V^*_0(s_0) - \mu_0$ というギャップが事前に未知であるため、$\epsilon$ の選択が困難になるからです。
2. アルゴリズム設計と上限: 彼らは BEE-GPI を提案し、陽インスタンスと陰インスタンスの両方に対するサンプル複雑性の理論的根拠のある上限を導出します。
   • 陽インスタンス: サンプル複雑性は $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$ によって有界です。
   • 陰インスタンス: 境界は状態空間と行動空間のサイズと結合した項を含み、具体的には $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$ です。
3. 下限と準最適性: 著者は、「一様インスタンス（陽の場合）」と「ツリーインスタンス（陰の場合）」を用いて GPI 問題の下限を確立します。
   • 彼らは、陽インスタンスに対して、いかなる $\delta$-PAC アルゴリズムも $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$ のサンプル複雑性を負う必要があることを証明します。
   • 陰インスタンスに対して、下限は $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$ です。
   • これらの結果は、BEE-GPI が準最適であることを示しており、上限と下限の間のギャップは $S, A, H$ の多項式因子に限定されています。

4. 結果と分析

理論的洞察

• 対数項の分離: 重要な発見として、陽インスタンスにおいて、サンプル複雑性における $\log(1/\delta)$ 項の係数は $O(H^2)$ であり、状態空間サイズ $S$ や行動空間サイズ $A$ に依存しないことです。これは、通常 BPI への帰着では係数が $S$ や $A$ と多項式的にスケーリングすることに比べて劇的な対照をなします。
• 非対称性: 陽インスタンスと陰インスタンスの間には本質的な非対称性があります。陽インスタンスでは、状態 - 行動空間全体を探索することなくある良質方策を効率的に同定できますが、陰インスタンスでは、どの方策も閾値を満たさないことを証明するためにグローバルな探索が必要となるため、$\log(1/\delta)$ 項において $S$ と $A$ に依存することになります。

数値実験

著者は、シングルチェーンおよびダブルチェーン MDP という 2 つの古典的な環境を用いてアプローチを検証しました。

• 設定: 彼らは、BEE-GPI を最先端の BPI-UCRL アルゴリズム（Kaufmann et al. [2021]）と比較しました。公平な比較を確保するため、BPI-UCRL にはオラクルパラメータ $\epsilon = V^*_0 - \mu_0$ が提供され、これにより大幅な事前知識が与えられました。
• 知見: さまざまな閾値 $\mu_0$ において、BEE-GPI は BPI-UCRL に比べて、合格する方策を同定するために一貫して著しく少ないエピソード数を必要としました。経験的結果は、$\log(1/\delta)$ 項を状態空間および行動空間のサイズから分離することの理論的優位性を確認しました。

5. 意義と主張

本論文は、絶対的な最適方策を見つけることが不要か計算的に不可能であるが、「十分良い」方策（ベンチマークを超える方策）を見つけることが重要な、実用的な RL シナリオに対して、BEE-GPI がより効率的な解決策を提供すると主張しています。

• 実用性: 著者は、医療情報学（標準治療を超える治療法の同定）、クラウドコンピューティング（サービスレベル合意の達成）、金融（ROI ベンチマークの達成）などの応用例を挙げており、これらの分野では最適性ではなく閾値の満足が目標となっています。
• 理論的進展: GPI を定式化し、準最適な境界を提供することで、この研究は理論的な純粋探索と実用的な閾値ベースの要件の間のギャップを埋めています。特に陽インスタンスの場合、目的を最適性から閾値の満足へと緩和することで、サンプル複雑性を大幅に削減できることを示しています。
• 将来の方向性: 著者は控えめに、将来の研究ではよりtightなインスタンス依存境界を導出し、関数近似を用いてこの枠組みを大規模 MDP に拡張することが考えられると提案しています。

要約すると、本論文は、報酬閾値を満たす方策を同定することは、最適方策を同定することと根本的に異なり、この相違点を利用することで、特に最適値と閾値の間のギャップが難易度の主要な駆動力である場合に、優れたサンプル効率を達成するアルゴリズムを提案していることを確立しています。