Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization

技術的概要：Prescribe-then-Select（PS）

問題設定
本論文は、文脈的確率最適化（Contextual Stochastic Optimization: CSO）という問題クラスを取り扱います。これは、意思決定者が行動 $z$ を実行可能な集合 $Z$ から選択する前に、共変量（文脈）$X$ を観測し、不確実な確率変数 $Y$ に対して期待コスト $E[c(z, Y) | X=x]$ を最小化する問題です。本研究で扱われる設定における重要な制約は、意思決定が、文脈のすべての実現値に対して厳密な実行可能性制約（整数性制約を含む場合もある）を満たさなければならないことです。

著者は、多くの CSO 設定において、単一の候補ポリシーが共変量空間全体で一様に優位性を示すことはないという重要な課題を特定しています。異なるモデリングパラダイム（例えば、点予測対分布推定）は、不均質な性能を示すことが多く、特定の領域（例えば、低分散領域対高分散領域）では卓越する一方で、他の領域では性能が劣ります。既存のポリシー選択手法は、実行可能なポリシーの平均化が実行可能な結果を保証しないため、制約付き設定では失敗しがちです。また、エンドツーエンドのトレーニングアプローチは、計算負荷の増大や後悔の収束の遅延という問題に直面することがあります。

手法：Prescribe-then-Select（PS）
著者は、実行可能性制約を違反することなく、与えられた文脈に対して最適なポリシーを適応的に選択するためのモジュール型、2 段階フレームワークである**Prescribe-then-Select（PS）**を提案します。

1. Prescribe（ライブラリ構築）:
   第一段階では、異なるモデリング仮定の下で共変量を実行可能な意思決定にマッピングする、多様な実行可能な候補ポリシーのライブラリ $\Pi_M = \{\pi_1, \dots, \pi_M\}$ を構築します。本論文では、以下の 3 つの手法ファミリーを利用します。

   • サンプル平均近似（SAA）: 共変量を無視し、過去のシナリオに対する決定論的最適化を解きます。
   • 点予測ポリシー（PPt）: $E[Y|X]$ を推定するために予測モデル（kNN、ランダムフォレスト、ニューラルネットワークなど）を適合させ、この点推定値を用いて決定論的最適化を解きます。
   • 予測処方ポリシー（PP）: 予測モデル（kNN、ランダムフォレストなど）を用いて重み付きサンプル平均近似のための重みを生成し、条件付き分布 $f_{Y|X}$ を実質的に近似します。

2. Select（メタポリシー学習）:
   第二段階では、特定の観測された共変量 $x$ に対して最適な候補ポリシーを選択するメタポリシーを学習します。

   • メカニズム: メタポリシーは、**最適ポリシー木（Optimal Policy Trees: OPT）**のアンサンブルを用いて実装されます。パラメトリックな決定則とは異なり、OPT は共変量空間を軸に平行な領域に分割し、各領域に特定のポリシーインデックスを割り当てます。
   • トレーニング: OPT はK フォールド交差検証を通じてトレーニングされます。各フォールドにおいて、候補ポリシーはトレーニング分割上でトレーニングされ、そのホールドアウトフォールドにおけるアウトオブサンプルコストが計算されて「コストテーブル」が作成されます。その後、OPT はこのテーブルに基づいて経験的コストを最小化するようにトレーニングされ、共変量空間のどの領域でどのポリシーが最も優れているかを学習します。
   • 推論: 推論時には、フォールドおよびランダムシード全体でトレーニングされた木のアンサンブルが投票し、最終的なポリシーインデックスを選択します。その後、そのインデックスを適用して意思決定を生成します。

主な貢献

1. 形式化: 本論文は、標準的なアンサンブル平均化がしばしば実行不可能である、厳密な実行可能性制約下での CSO におけるポリシー選択の問題を形式的に定義しました。
2. フレームワーク: ポリシー生成とポリシー選択を分離するPrescribe-then-Selectフレームワークを導入しました。これにより、最終的な意思決定が実行可能であることを保証しつつ、多様で潜在的に互換性のないモデリングパラダイムの統合が可能になります。
3. データ駆動型選択: このアプローチは完全にデータ駆動型であり、交差検証されたコストテーブルを用いてメタポリシー（最適ポリシー木）をトレーニングします。これにより、共変量空間を分割し、各領域に最も効果的なポリシーを割り当てることを学習します。

実験結果
著者は、PS を 2 つのベンチマーク問題、すなわち多製品ニューズボーイ問題と2 段階出荷計画問題で評価しました。両タスクとも、不均質性を誘発するために、異なる需要セグメント（例：休暇期間の急増、季節的傾向）を持つ合成データを利用しています。

• 不均質性: 実験により、単一のポリシーが一様に優位性を示さないことが確認されました。性能はセグメントやトレーニングサイズによって大きく変動します（例えば、点予測手法は低分散セグメントで卓越する一方、予測処方手法は高分散または不連続な領域で優位性を示します）。
• 性能向上: 不均質な領域において、PS は一貫して最良の単一候補ポリシーを上回ります。この性能向上は統計的に有意であり、特にトレーニングデータが限られている場合や、共変量空間に異なるポリシーが最適となる明確な領域が存在する場合に顕著です。
• 収束: 単一のポリシーが一様に優位である領域（またはトレーニングサイズ $N$ が非常に大きくなり、あるポリシーが明確に優位となる場合）において、PS はその優位なポリシーに収束し、最良の単一ポリシーに対して無視できる程度の後悔しか生じません。
• 計算効率: メタポリシーのトレーニングに伴うオーバーヘッドは、候補ポリシーの基礎となる最適化問題を解くコストと比較して最小限です。

意義と主張
本論文は、PS が、複数の高品質な処方モデルが利用可能な意思決定環境において、実用的でリスクの低いアプローチを提供すると主張しています。各インスタンスに対して最も適したポリシーを選択するために文脈情報を活用することで、PS は不均質性を活用し、複雑なエンドツーエンドトレーニングを必要とせず、実行可能性制約を違反することなく、最良の単一ポリシーを上回る性能を実現します。このフレームワークは、モジュール型ソリューションとして提示されており、多様なポリシーを柔軟に統合し、「すべてに通用する」モデルが最適ではない複雑な意思決定環境に適応できます。著者は、いくつかのベースポリシーが漸近的に最適である一方で、PS は有限サンプル設定において、文脈を最も効果的なモデルに動的にルーティングすることで、顕著な利益をもたらすと指摘しています。