技術的概要：コスト補助を伴う多腕バンディット問題におけるコスト順序付け可能性

問題定式化

本論文は、品質制約の下で累積コストを最小化することを目的としたコスト感受性のオンライン意思決定のための枠組みである「コスト補助を伴う多腕バンディット（MAB-CS）」問題に取り組みます。累積報酬を最大化する標準的な MAB と異なり、MAB-CS は、最小期待報酬閾値を満たす腕の中で最も安価な腕を探索します。

ここで調査される具体的な設定は、システム内の未知の最良報酬に相対的に定義される品質制約を含みます。期待報酬 $\mu_k$ と既知のサンプリングコスト $c_k$ を持つ腕の集合 $\mathcal{A} = \{a_1, \dots, a_K\}$ が与えられたとき、実行可能集合は $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$ です。閾値は $\mu_{CS} = (1-\alpha)\mu^*$ と定義され、ここで $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ は未知の最良報酬であり、$\alpha \in (0, 1)$ は補助係数です。最適腕 $a^*$ は、実行可能集合 $S$ に含まれる最も安価な腕です。

本論文は、2 つの後悔メトリックを定義します：

1. コスト後悔：最適腕 $a^*$ に対して生じる超過コスト。
2. 品質後悔：選択された腕の期待報酬が実行可能性閾値 $\mu_{CS}$ を下回った場合に生じるペナルティ。

核心的な課題は、$\mu^*$ の事前知識なしに、未知の閾値 $(1-\alpha)\mu^*$ を推定しつつ、最も安価な実行可能腕を特定しながら、これらの後悔を同時に最小化することにあります。

手法：COF アルゴリズム

著者は、MAB-CS 問題を解決するために「コスト順序付け可能性（COF）」アルゴリズムを提案します。COF は、既知のコストの昇順に腕を評価することで動作します。各候補腕 $a_\ell$ について、アルゴリズムは「ゲートング腕」（$a_\ell$ より高価な腕）の集合と比較することで実行可能性を判定します。

COF の主要なメカニズムには以下が含まれます：

• コスト順序付け評価：腕は最も安価なものから最も高価なものへと順次テストされます。実行可能と判断された最初の腕が、残りの地平線（horizon）における最適腕として選択されます。
• サンプルの結合（集約）：候補腕 $a_\ell$ が非実行可能かどうかを判定する際、COF は単一のペアワイズ比較に依存しません。代わりに、$a_\ell$ を失格させることができるすべての腕との比較からの証拠を集約します。各ゲートング腕に対する $a_\ell$ が実行可能である確率の上限を計算し、これらの確率の積が許容値 $\delta$ を下回ると、$a_\ell$ を非実行可能とみなします。
• 排他的サンプリング：候補腕のサンプル数が最も多くサンプリングされたゲートング腕のサンプル数に遅れをとっている場合、COF は候補腕を排他的にサンプリングして「追いつく」ことで、必要な非最適サンプルの総数を削減します。
• BAI フィルタ：候補の評価中に、COF は、あるゲートング腕の Upper Confidence Bound (UCB) が別のゲートング腕の Lower Confidence Bound (LCB) を下回るゲートング腕のサンプリングを停止させるフィルタを採用します。これにより、統計的に最良報酬腕（$i^*$）である可能性が低い腕へのサンプルの無駄遣いを防ぎます。

理論的貢献

本論文は、MAB-CS の厳密な理論分析を提供し、後悔に関する下限と上限の両方を確立します。

1. インスタンス依存の下限：

   • 著者は、安価な腕（コスト $< c_{a^*}$）と高価な腕（コスト $> c_{a^*}$）に対する期待サンプル数の下限を導出します。
   • 新たな貢献として、腕の集合に対する結合下限が提案されます。この下限は、ある腕の報酬が最良報酬腕 $i^*$ だけでなく、任意の腕の補助された報酬よりも悪い場合、その腕は非実行可能と認定され得るという洞察を反映しています。これは、$i^*$ を単独で扱う以前の限界を一般化したものです。

2. COF に対する後悔上限：

   • 本論文は、COF に対する累積コストと品質後悔の期待値に関するインスタンス依存の上限を確立します。
   • 安価な腕については、下限で見られる $O(\log T / \Delta_{Q,k}^2)$ の依存性と一致する順序最適性が示されています。
   • 高価な腕については、上限は 2 つの項の最大値に依存します。1 つは腕と最適腕のギャップに関連し、もう 1 つは最良の安価な腕を排除するために必要な結合ギャップに関連します。著者は、高価な腕に対する下限と上限の間にわずかな不一致があることに言及し、サンプル複雑性の理論分析には改善の余地があることを示唆しています。

実験結果

著者は、以下のシミュレーションを通じて COF を検証しました：

• 実世界データセット：ジャンルが多腕バンディットの腕として機能する Goodreads（書籍評価）と MovieLens（映画評価）。
• 合成インスタンス：特定のアルゴリズムの動作をテストするために手作業で設計された問題。

主要な知見：

• 性能：COF は、固定予算探索（ETC-CS）、ペアワイズ除去（PE-CS）、UCB-CS、TS-CS などのベースラインアルゴリズムを一貫して上回ります。
• 頑健性：誤って安価で非実行可能な腕を実験的に実行可能集合に含めることで線形後悔を招く可能性のある UCB-CS や TS-CS と異なり、COF は実行可能性を厳密にテストすることで部分線形後悔を維持します。
• 補助係数の感度：PE-CS は高サンプル領域でのより狭い信頼区間により、非常に小さな補助係数（$\alpha$）に対してわずかに良いパフォーマンスを発揮しますが、COF は $\alpha$ が増加するにつれて PE-CS で観察される性能の頭打ちを回避します。
• アブレーション研究：実験により、「サンプルの結合」と「排他的サンプリング」の機能がアルゴリズムの効率性に不可欠であり、これらのメカニズムを持たない変形と比較して後悔を大幅に削減することが確認されました。

意義と主張

本論文は、品質制約が未知の最良報酬に相対的なコスト感受性バンディット問題に対して、COF が質的に優れた理論的枠組みと経験的パフォーマンスを提供すると主張します。

• 理論的進展：この研究は、複数の腕のサンプル複雑性を共同で特徴づける最初のインスタンス依存の下限を提供し、MAB-CS の構造的課題に対する従来の最悪ケースまたは単一腕の分析よりも深い洞察を提供します。
• アルゴリズムの効率性：実行可能性をテストする前に $\mu^*$ を見つけるための専用の Best Arm Identification (BAI) フェーズを回避することで、COF は不要なサンプリングを削減します。「サンプルの結合」戦略により、アルゴリズムはペアワイズ比較手法よりも効率的に非実行可能な腕を排除できます。
• 実用的適用性：著者は、MAB-CS の実世界シナリオへの関連性を強調しています。例えば、LLM モデルルーティングでは、異なるモデルが異なるコストと未知の品質を持ち、システムは利用可能な最良モデルに対するパフォーマンスの床に対してコストをバランスさせる必要があります。同様に、この枠組みは広告モーダリティの選択やストリーミングサービスのコンテンツ配信に応用可能です。

著者は、COF が安価な腕に対して順序最適のパフォーマンスを達成し、強力な経験的結果を示している一方で、今後の研究では高価な腕に対する下限と上限のギャップに対処し、非常に不均一なコスト分布を持つアプリケーション向けのコストバイアス付きサンプリング変種を検討すべきであると結論付けています。