技術要約：マルチオブジェクティブ・マルチアームド・バンディットにおけるベイズ的エニタイム・パレート集合識別

問題定義

本論文は、マルチオブジェクティブ・マルチアームド・バンディット（MOMAB）問題、特にパレート集合識別（PSI）に焦点を当てている。単一目的のバンディット問題が累積報酬の最大化（後悔最小化）や単一の最良アームの特定を目指すのに対し、MOMABでは、複数の、潜在的に相反する目的を同時に最適化する必要がある。この設定では、すべての基準において最適な単一のアームは存在せず、代わりに最適なトレードオフを表すパレート最適アームの集合（$P^\star$）が存在する。

具体的な課題として取り組まれているのは、エニタイム（Anytime）PSIの定式化である。既存の文献では、固定予算（一定サンプル数後の誤差最小化）や固定信頼度（目標精度に達するためのサンプル数最小化）の設定が広く扱われてきたが、事前の停止ルールなしに、毎回の観測後に有効かつ継続的に更新される推定値を提供できるアルゴリズムには空白が存在する。これは、厳格なリソース制約ではなく、信頼度に基づいて実験を動的に終了させる必要がある現実世界のアプリケーションにおいて極めて重要である。

手法：Top-Two Pareto Front Thompson Sampling (TTPFTS)

著者らは、MOMAB PSI問題のための初のベイズ的エニタイム・アルゴリズムである**Top-Two Pareto Front Thompson Sampling (TTPFTS)**を提案している。TTPFTSは、単一目的の最良アーム識別におけるTop-Two Thompson Sampling (TTTS) の原理をマルチオブジェクティブ領域へと拡張したものである。

コアメカニズム

目的関数を選好ベクトルによってスカラー化する（これにより問題を単一目的へと還元してしまう）のではなく、TTPFTSはパレートフロントに対して直接作用する。各ステップ $t$ において：

1. 事後分布サンプリング: アルゴリズムは、履歴 $H(t-1)$ に条件付けられたそれぞれの事後分布から、全 $K$ 個のアームの平均報酬ベクトル $\tilde{\theta}^{(t)}_a$ をサンプリングする。
2. フロント識別: これらのサンプルに基づき、他のサンプリングされたアームによって支配されないアームからなる第1パレートフロント（$F^\star_1$）を特定する。
3. 確率的選択: ベルヌーイ試行（確率 $\rho$）により、どのフロントを探索するかを決定する：
   • 確率 $\rho$ で: 第1フロント（$F^\star_1$）から一様にランダムに選ばれたアームを選択する。これは、現在最適であると信じられているアームの検証に焦点を当てる。
   • 確率 $1-\rho$ で: アルゴリズムは $F^\star_1$ を除外し、残りのアームから第2パレートフロント（$F^\star_2$）を特定する。その後、$F^\star_2$ から一様にランダムに選ばれたアームを選択する。これは、最も有望な劣最適アーム（チャレンジャー）を探索し、それらが過小評価されていないかを確認するか、あるいは劣最適としての地位を固めることを促進する。
4. 更新: 選択されたアームがプルされ、報酬が観測され、履歴が更新される。アルゴリズムは常に推奨セット $\hat{P}^\star_t$（事後平均のパレート集合）を保持する。

理論的保証

本論文は、漸近的正当性（定理1）の証明を提供している。標準的な仮定（有限のアーム、一貫した事後分布、厳密なパレートギャップ、および十分な探索）の下で、アルゴリズムの推定値 $\hat{P}^\star_t$ は、$t \to \infty$ において確率1で真のパレート集合 $P^\star$ に収束する。この証明は、TTPFTSがほぼ確実にすべての探索を無限に行うことを保証し、どのアームもサンプリングプロセスから永久に「凍結」されることを防ぐことを確立する補題1に基づいている。

主な貢献

1. MOMAB PSIにおける初のエニタイム・ベイズ・アルゴリズム: TTPFTSは、固定予算および固定信頼度アプローチに対する柔軟な代替案を提供することで、パレート集合識別に関する文献の空白を埋める。
2. 新規の不確実性定量化（UQ）指標: 著者らは、アルゴリズムの現在のパレート予測に対する信頼度を推定するための、真の値を必要としない指標を導入している。この指標は、推定された第1フロント（$\hat{P}^\star_1$）と第2フロント（$\hat{P}^\star_2$）の事後密度間の**バタチャリア・オーバーラップ（Bhattacharyya overlap）**を計算する。
   • オーバーラップが高いことは、不確実性が高いこと（最適と劣最適の区別が困難であること）を示す。
   • オーバーラップが低いことは、信頼度が高いこと（フロント間の明確な分離）を示す。
   • この指標は、アルゴリズムの性能のプロキシ（代理指標）として機能し、動的な停止基準を可能にする。
3. 分子探索への実世界応用: 本アルゴリズムは、極めて大規模な合成オンデマンド分子ライブラリ（9400万候補）の設定において検証されており、相反する特性（構造類似性とLogP）を最適化する分子を特定する有用性が示されている。

実証結果

合成ベンチマーク

TTPFTSは、様々なパレートフロントの形状と次元を持つ8つの合成環境において、最先端の固定予算アルゴリズム（Empirical Gap Elimination (EGE) の Successive Rejects および Successive Halving バリアント）と比較評価された。

• パフォーマンス: TTPFTSは、Uniform Sampling および EGE-SH アルゴリズムを一貫して上回った。より厳しいエニタイム制約があるにもかかわらず、すべての環境において EGE-SR（最強の固定予算ベースライン）と同等の性能を達成した。
• スケーラビリティ: アクション空間が大きい環境（例：$K=200$）において、TTPFTSは EGE バリアントを大幅に上回った。これは、TTPFTSの事後分布駆動型の割り当てが、大規模な問題における硬直的なギャップベースの排除よりも効果的であることを示唆している。
• 堅牢性: アルゴリズムは、弱い事前分布の仮定（一様事前分布）の下でも良好に動作した。

分子探索ケーススタディ

9400万個の化合物ライブラリの探索において：

• 効率性: TTPFTSは、データベースのわずか 0.05% を評価するだけで、真のパレートフロントと完全に一致する分子（52個）を特定した。
• 比較: ランダムサーチ（最適分子をゼロしか発見できなかった）および最先端のアクティブラーニング手法である MolPAL の両方を大幅に上回った。
• 不確実性の相関: 提案された UQ 指標は、Jaccard 指標（精度）と強い負の相関を示した。アルゴリズムがパレート集合の推定を改善するにつれて、不確実性指標は減少した。これは、この指標が収束の信頼できる、真の値を必要としないインジケーターであることを検証している。

意義と主張

本論文は、TTPFTSが、真のパレートフロントの知識を必要とせずに、複雑なマルチオブジェクティブ設定における学習進捗を監視するための堅牢な手法を提供すると主張している。エニタイム探索戦略と新規の不確実性定量化指標を組み合わせることで、本研究はパレート集合識別問題を、静的なサンプリングタスクから動的な意思決定支援システムへと変貌させている。

著者らは、このアプローチにより、意思決定者が以下のことが可能になると強調している：

• パレートフロントが十分に解明されたと判断し、実験を終了するタイミングを動的に決定する。
• 計算リソースと発見の信頼度の間のトレードオフを最適化する。
• 創薬のように、網羅的なスクリーニングが不可能であり、かつ好みが事前に判明していない現実世界のシナリオにこれらの利点を適用する。

本論文は、漸近的な正当性は証明されているものの、有限時間の誤差境界については、過去の標準的な Thompson Sampling が直面した課題と同様に、明示的な有限時間レートの導出は依然として困難であることを認め、控えめな姿勢を保っている。しかし、著者らは、漸近的な健全性、強力な実証的パフォーマンス、および不確実性指標の実用的な有用性の組み合わせが、TTPFTSをマルチオブジェクティブ意思決定における重要な進歩として確立していると主張している。