技術的サマリー：大規模離散行動空間における距離誘導強化学習

問題定義

強化学習（RL）は連続空間や小規模な離散領域において成功を収めてきたが、物流、スケジューリング、推薦システムなどの大規模意思決定問題における「基数の呪い」に直面している。これらの応用分野では、高次元の離散成分、カテゴリカル変数、またはハイブリッドな離散 - 連続パラメータを含む、基数が $10^{20}$ に達する行動空間を扱うことがよくある。

既存のアプローチは、以下の 3 つの主要なボトルネックに直面している：

1. 勾配分散: 標準的な方策勾配法は、大規模な行動空間において確率質量 $\pi(a|s)$ が消失するにつれて、分散の爆発に悩まされる。
2. 計算的実行可能性: 網羅的な列挙や事前計算されたルックアップテーブルに依存する手法（例：Wolpertinger）は、次元が増加するにつれて実行不可能となる。
3. 構造的硬直性: 動的近傍構築（DNC）のようなアプローチは、規則的なグリッド構造（例：数値的な隣接性）に依存しており、不規則に配置された領域や疎な実行可能領域では機能しない。さらに、ハイブリッド行動空間ではしばしば階層的なシーケンシングが必要となり、コミットメントのボトルネックを導入してトレーニングを不安定化させる。

手法：距離誘導強化学習（DGRL）

著者は、最大 $10^{20}$ 個の候補を持つ行動空間に拡張可能なオフポリシーのアクター - クリティックアルゴリズムである**距離誘導強化学習（DGRL）**を提案する。DGRL は、離散行動空間の連続緩和空間内で動作し、2 つの相乗的な構成要素からなる体積投影ループを利用する。

1. サンプリング型動的近傍（SDN）

SDN は、アクターによって生成された連続的な「プロトアクション」$\hat{a}$ の周囲で確率的な体積探索を行うことで、高次元離散空間における探索課題に対処する。

• メカニズム: 剛性のグリッド線や事前計算された最近傍テーブルに依存するのではなく、SDN はチェビシェフ（$L_\infty$）半径 $L$ によって境界付けられた動的近傍 $B(\hat{a})$ を構築する。
• 独立した座標サンプリング: ハイパーキュー内のすべての整数点を列挙する組み合わせ爆発を回避するため、SDN は各次元を独立してサンプリングする。$\hat{a}$ をサンプリング分布のモードとして解釈し、$K$ 個の候補アクションを抽出する。候補のサンプリング確率は、$\hat{a}$ からの距離が増すにつれて減少する。
• 次元不変性: $L_\infty$ 距離を用いることで、次元 $N \to \infty$ となっても探索体積は安定したままとなる。これにより、$\sqrt{N}$ に比例して必要な半径が増大するユークリッド（$L_2$）距離とは異なり、サンプリング確率が消失しないことが保証される。
• 計算複雑性: このアプローチにより、探索の計算複雑性は指数関数的な $O((2L)^N)$ から線形な $O(N \cdot K)$ に削減され、$N > 100$ の次元へのスケーラビリティが可能となる。

2. 距離ベース更新（DBU）

DBU は、方策最適化を安定した回帰タスクに変換することで、勾配分散と不安定性の問題に対処する。

• ターゲット構築: アルゴリズムはプロトアクション $\hat{a}$ を摂動させて $M$ 個の補助候補を生成する。これら候補をクリティックを用いて評価し Q 値を取得し、これらの候補のソフトマックス重み付き平均としてターゲットアクション $\bar{a}$ を構築する。これはノイズ除去フィルタとして機能し、クリティックの過大評価を緩和し、損失地形を滑らかにする。
• 回帰損失: アクターは、プロトアクション $\hat{a}$ とターゲット $\bar{a}$ の間の距離を最小化するように更新される（例：Huber 損失の使用）。
• 分散独立性: 理論的に、DBU の勾配分散は行動空間の基数 $|A|$ に依存しない。更新は、緩和された行動空間の幾何学と、固定されたサンプリング候補数 $M$ のみに依存し、勾配ノイズを行動空間のサイズから切り離す。

ハイブリッド空間の統一的扱い

DGRL は、ハイブリッド行動空間 $A \subset \mathbb{Z}^N \times \mathbb{R}^M$ を、結合プロトアクション $(\hat{a}_d, \hat{a}_c)$ を出力することで処理する。SDN と DBU の両方は、同時に対象ベクトル全体に対して動作する。これにより、離散成分と連続成分が共有表現層を通じて互いに情報を伝達する結合最適化が可能となり、高レベルの選択が低レベルの最適化を制約する階層的アプローチに典型的な「後悔の床」を回避できる。

主な貢献

1. アルゴリズム的枠組み: SDN と DBU を組み合わせ、最大 $10^{20}$ 個の行動を持つ空間における効率的な RL を可能にする DGRL の導入。
2. 理論的保証:
   • 次元が増加してもチェビシェフベースのサンプリングが安定した探索体積を維持することを証明（命題 4.1）。
   • DBU の勾配分散が行動基数 $|A|$ に依存しないことを証明（定理 4.2）。
   • リプシッツ連続性の仮定の下で構造化タスクにおける局所的な価値改善保証の確立（命題 4.5）。
3. スケーラビリティ: DGRL が基数 $|A|$ に対して指数関数的ではなく、次元 $N$ に対して線形的にスケーリングし、不規則な構造やハイブリッド行動空間にも自然に一般化することを示実。

実験結果

著者は、2D マズ、ジョブショップスケジューリング、共同在庫補充、推薦システムの 4 つの環境の 12 種類の変種において DGRL を評価した。これらには、規則的な構造と不規則な構造の両方のトポロジーが含まれ、行動空間は $5^4$ から $343^{10}$ の範囲であった。

• 性能: DGRL は、離散環境において最高で66%、ハイブリッド環境において129% まで、Wolpertinger、DNC、Cacla、LAR などの最先端ベンチマークを上回った。
• 頑健性: 高次元の不規則空間で崩壊した DNC と異なり、DGRL は安定性と性能を維持した。また、DDPG ベースのベースラインと比較して、分散が著しく低く、収束が速かった。
• 計算効率: DGRL は行動空間サイズに対してほぼ一定のステップ時間を示したのに対し、ルックアップテーブルに依存する手法（Wolpertinger、LAR）は計算的に実行不可能となり、DNC のステップ時間は次元の増加とともに劣化した。
• アブレーション研究: 結果は、体積探索のための SDN と、安定した回帰更新のための DBU の両方が不可欠であることを確認した。いずれかのコンポーネントを除去すると、性能の低下または不安定性が生じた。

意義と主張

本論文は、DGRL がメトリック認識型 RLのための基盤的アプローチを提供することを主張しており、大規模意思決定においてカテゴリカル表現に代わるものとして、問題構造と距離誘導サンプリングを活用できることを示唆している。

著者は、DGRL が以下の点によって RL のスケーラビリティギャップを成功裡に埋めると主張している：

1. 勾配分散を行動空間の基数から切り離すこと。
2. 不規則な行動空間構造に対して頑健な体積探索を可能にすること。
3. 階層的分解の不安定性なしに、ハイブリッド空間における結合最適化を促進すること。

この研究は、「基数の呪い」に対する解決策として提示されており、大規模な離散およびハイブリッド行動空間において、網羅的探索に対する計算的に実行可能な代替手段、および方策勾配法に対するより安定した代替手段を提供する。