Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

技術要約：QUBO最適化によるモンテカルロ強化学習のための量子着想型エピソード選択

問題提起
モンテカルロ（MC）強化学習は、特に疎な報酬、広大な状態空間、および時間的に相関のある軌跡を特徴とする環境において、サンプル効率に関する重大な課題に直面している。標準的なMC手法は、データサンプルが独立同一分布（i.i.d.）であるという仮定に依存しているが、マルコフ的なRLの軌跡においてはこの仮定は崩れている。その結果、MC推定値は以下の問題に苦しむ：

1. 分散の伝播： 収益は累積的な分散を示し、推定誤差を減少させるために必要なエピソード数（$N_s$）は $O(\epsilon^{-2})$ に比例してスケールする。
2. 不適切な軌跡の希釈： 報酬が疎な領域では、推定値が低報酬の軌跡によって希釈されるため、最適なパスを十分にカバーするためにサンプルサイズの指数関数的な増大が必要となる。
3. 組合せ爆発： 理論的には、$N$ 個の候補から $m$ 個の最適なサブセットを選択して価値推定の精度を最大化する問題は、特徴量選択や集合被覆（set cover）と同型であり、NP困難な問題である。その解空間は $\binom{N}{m}$ となる。

手法
著者らは、エピソード選択プロセスを二次無制約バイナリ最適化（QUBO）問題として再定式化するフレームワークである MC+QUBO を提案している。すべてのサンプリングされたエピソードを使用して方策を更新する代わりに、本手法はバッチ内の軌跡をフィルタリングし、累積報酬を最大化しつつ状態空間の被覆度（多様性）を促進するサブセットを選択する。

• QUBO 定式化： 選択問題は以下のようにエンコードされる：
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  ここで：

  • $x_i = 1$ はエピソード $\tau_i$ が選択されたことを示す。
  • $R_i$ はエピソード $i$ の累積報酬である。
  • $w_{ij}$ はエピソード間のペアワイズ類似度（例：訪問した状態集合のジャカード類似度）を表す。
  • $\alpha$ は報酬スケーリング係数であり、$\gamma$ は類似度ペナルティの重みである。
  • 線形項（$-\alpha R_i$）は高報酬のエピソードを優先し、二次項（$\gamma w_{ij}$）は冗長性をペナルティとして課すことで、多様な軌跡の選択を促す。

• 量子着想型ソルバー： QUBO問題は、ブラックボックス型の量子着想型サンプラー、具体的には 量子アニーリング・シミュレーション（SQA） および シミュレーテッド・ビファーケーション（SB） を用いて解かれる。

  • SQA は、古典的な確率的更新と経路積分モンテカルロを用いて、量子トンネル効果を模倣する。
  • SB は、連続変数が分岐現象を通じてバイナリ状態へと進化する古典的な力学系アプローチを利用する。
  • 著者らは、これらのソルバーを、実用的な計算予算内で高品質な近似解を提供するオラクルとして扱う。

• 統合： ワークフローは、エピソードのバッチ生成、報酬と類似度の計算、QUBOの定式化、ソルバーへのディスパッチ、そして得られた最良の観測解（バイナリベクトル $x^*$）を用いて、ファーストビジットMCにより行動価値テーブル $Q(s, a)$ を更新するために使用されるエピソードを決定するという手順を含む。

主な貢献

1. エピソード選択の再定式化： 本論文は、MCエピソード選択と組合せ最適化の間の正式な関連性を確立し、選択問題がQUBO定式化にマッピング可能であることを示している。
2. アルゴリズムの統合： 標準的なMC学習における軌跡サンプリングと方策評価の間に、QUBOベースのフィルタリングステップを挿入する具体的なパイプライン（アルゴリズム2）を導入している。
3. 実証的検証： 本研究では、様々なサイズ（$3\times3$ から $20\times20$）の有限ホライゾンGridWorld環境を用いて、MC+QUBOをバニラMCベースラインと比較評価している。

結果
GridWorld環境における実験では、MC+QUBOが収束速度および最終的な方策の質において、バニラMCを一貫して上回ることが示された。

• スケーラビリティ： より大きな環境（$\ge 10\times10$）において性能差が拡大する。これは、標準的なMC評価を阻害する疎な報酬と指数関数的な状態空間の増大が顕著になるためである。
• 収束： MC+QUBOは、情報量が多く多様な軌跡に学習を集中させることで、より少ないバッチ数で収束し、冗長なエピソードを効果的に排除する。
• 設計上の洞察： 著者らは、報酬の重みの影響をゼロに近づけて状態空間の被覆を優先することが、報酬駆動型の選択よりもバランスの取れた学習と優れた汎化をもたらすことを指摘している（報酬駆動型の選択は、収束は早まるものの安定性に欠ける傾向がある）。
• ソルバーの性能： 量子着想型ソルバー（SQAおよびSB）は、この文脈において古典的なヒューリスティック（Tabu SearchやSimulated Annealingなど）よりも優れた性能を示した。計算のレイテンシは、ソルバー自体の実行時間（$n \le 200$ の場合は無視できる程度）ではなく、クラウド通信によって支配されていた。

意義と主張
本論文は、量子および量子着想型最適化を強化学習の意思決定サブルーチンとして統合することが、特に報酬が疎で相関のある軌跡を持つ問題に対して、MC手法の実用的な強化策となることを主張している。強化学習と組合せ最適化を橋渡しすることで、本研究は、量子および量子着想型の手法が学習プロセスを能動的にガイドし、サンプル効率の問題を克服するための道筋を示唆している。

著者らは、本フレームワークの範囲について謙虚な姿勢を保っており、Grid世界では有望な結果が得られたものの、連続制御、階層型RL、マルチエージェントシステムへの拡張、および実際の量子ハードウェアへの展開については今後の課題であるとしている。現在の研究は、物理学に着想を得たソルバーを用いて、強化学習におけるデータ選択フェーズを最適化するための概念実証（PoC）として位置づけられている。