Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

技術的概要：オフポリシー評価のための商 DAG

問題定義

オフポリシー評価（OPE）は、行動方策 $\beta$ によって収集されたデータを用いて、目標方策 $\pi$ の性能を推定する。標準的な重要度サンプリング（IS）は、ログ記録された軌跡を、目標方策と行動方策の行動確率比の積によって再重み付けする。しかし、このアプローチは、評価対象がそれらを無視する場合であっても、生成プロセスの詳細を意味のあるものとして扱う傾向がある。

この問題の主要な事例はスレート推薦において生じる。現代の生成モデルは、多くの場合、スレート（アイテムの集合）を自己回帰的に構築し、特定の順序に沿ってステップごとの確率を露出させる。しかし、報酬や下流の推定量は、しばしば順序を問わないスレートのみに依存する。標準的な軌跡 IS は、特定の順序付きパスに対して尤度比を割り当てるため、「結合傾向のギャップ」を生み出す。つまり、ログ記録者は順序付きの確率を露出するが、推定量は順序を問わないスレートの総確率を必要とする。この正確な順序を問わない傾向を計算するには、通常、すべての $K!$ 通りの生成順序にわたって合計する必要があり、中程度のスレートサイズに対しては計算的に非現実的である。さらに、順序を有意なものとして扱うことは、報酬が生成順序に対して不変である場合に、不要な分散（ニュアンス分散）を導入する。

手法

本論文は、これらの問題に対処するために商 DAG 視点を導入する。中核的なアイデアは、評価対象に対して十分である同値関係によって、履歴接頭辞のロールアウト木を商（quotient）することである。

1. 商 DAG と前方フロー:

   • ロールアウト木は、評価対象に対して同等である履歴接頭辞（例：順序に関係なく、選択されたアイテムの同じ集合を含む接頭辞）をマージすることで縮約される。
   • これにより、ノードが同値クラス（商状態）を表す層状の非巡回グラフ（DAG）が形成される。
   • 単一の実現されたパスの比率で重み付けするのではなく、この手法は前方フロー比 $F_\pi(z)/F_\beta(z)$ を用いて重みを割り当てる。ここで、$F_\mu(z)$ は方策 $\mu$ の下でノード $z$ に到達する確率質量である。
   • このアプローチは既存の手法を一般化する。決定ごとの IS、周辺化 IS、既知の抽象化 MIS は、異なる同値関係の選択に対応する特殊なケースである。

2. 前方フロー重要度サンプリング（FF-IS）:

   • 一般的な有限時間 OPE において、推定量は、決定ごとの IS（PDIS）におけるサンプリングされた接頭辞の比率を、商尤度比に置き換える。
   • 理論的解析により、終端の商測定可能リターンに対して、この重み付けは「クラス内」の目標 - 行動のミスマッチを除去し、不要な分散の削減を定量化する正確な分散ギャップ式を提供することが示された。

3. スレート OPE 向けの前方 DP:

   • 本論文は、この枠組みを集合十分なインターフェース（定義 1）の下での自己回帰的スレート生成に特化させる。方策が集合十分であるとは、次のアイテムを選択する確率が、コンテキストと既に選択されたアイテムの集合のみに依存し、その順序には依存しないことを意味する。
   • 集合十分性の下では、置換商は部分集合 DAGに対応し、ノードはカタログの部分集合を表し、エッジは選択されていないアイテムを追加する。
   • 前方 DP アルゴリズム: 動的計画法アルゴリズムは、置換ではなく部分集合にわたって合計することで、正確な順序を問わないスレート傾向 $F_\mu(S|x)$ を計算する。
     • 計算量: $O((M + K) \cdot 2^K)$。ここで、$M$ はカタログサイズ、$K$ はスレートサイズである。これは $K!$ による列挙を回避する。
     • 最適性: 本論文は、集合十分な方策に対する正確な順序を問わない傾向を計算する任意の決定論的アルゴリズムは、最悪の場合においてスレートのすべての真部分集合を照会しなければならないことを証明し、Forward-DP を定数因子まで照会最適であると確立した。

主要な貢献

• 理論的枠組み: より粗い標本空間上の前方フロー比として正確な尤度比を導出する、OPE に対する統合された商 DAG 視点。
• アルゴリズム的革新: コンテキスト依存かつ集合十分な自己回帰的ログ記録者に対する正確な順序を問わないスレート傾向を、カタログサイズに対して多項式時間かつスレートサイズに対して指数時間（$K$ における固定パラメータ実用性）で計算するForward-DPアルゴリズム。
• 分散削減: 商重み付けが、生成順序（スレート推薦における生成順序など）の無関係な詳細に起因する分散成分（順序ニュアンス分散）を除去することを示す形式的証明。特に、報酬がスレートの生成シーケンスに対して不変である場合に有効である。
• スレート OPE へのプリミティブ: 固定スコアのプラケット・ルース式が適用できないコンテキスト依存ログ記録者に対して、トランスフォーマーベースのスレート推薦者に対する正確な傾向ベースの評価とモデル選択を可能にするプリミティブとしての Forward-DP の導入。

実験結果

著者は、有限時間 MDP ベンチマークおよびスレート推薦タスクにおいて本手法を評価した。

1. 有限時間 MDP（敗血症 & ICU-敗血症）:

   • 前方フロー IS（FF-IS）は、標準的な軌跡 IS および他のベースライン（DualDICE、GenDICE など）と比較して、二乗平均平方根誤差（RMSE）を大幅に削減した。
   • 敗血症ベンチマークにおいて、FF-WIS は RMSE を 0.291（WIS）から 0.0568 に削減した。
   • これらの改善は、遷移モデルを適合させることなく、ログ記録された軌跡のみを用いて達成された。

2. KuaiRec スレート実験:

   • 計算効率: Forward-DP は、$K!$ による列挙よりも桁違いに速く正確な傾向を計算する。$K=8$ の場合、列挙には約 97,108 秒を要したが、Forward-DP は約 8.94 秒で完了した。$K=12$ の場合、列挙は非現実的であるのに対し、Forward-DP は約 13.7 秒で完了する。
   • 下流 OPE: Forward-DP 重みを用いた推定量（FF-OIS、FF-DR）は、すべてのスレートサイズ（$K \in \{4, 6, 8\}$）において、RMSE の観点から軌跡重み付けの対応する手法（OIS、DR）を一貫して上回った。
   • モデル選択: 自己回帰的トランスフォーマー推薦者間のオフポリシーモデル選択において、Forward-DP を活用した推定量（Tree-DR、DP-OPCB-DR など）は、軌跡ベースの手法と比較して、優れた Top-1 精度、スピアマン相関係数、および低い後悔を達成した。

意義と主張

本論文は、提案された枠組みが決定ごとの IS に対するラオ・ブラックウェル化を提供すると主張する。十分な同値関係の下でロールアウト木を商することにより、この手法は（スレート推薦における生成順序など）無関係な履歴の詳細に付随する不要な分散を排除する。

特にスレート推薦に関しては、本論文は Forward-DP がコンテキスト依存の自己回帰的ログ記録者に対する欠落した OPE プリミティブを提供すると主張している。アイテムのスコアが部分的なスレートに応じて変化しないという固定スコア仮定やモンテカルロ近似に依存する以前の手法とは異なり、Forward-DP は次のアイテムのソフトマックスが部分的なスレートに依存するケースを処理し、階乗的な列挙なしに正確な結合傾向を計算する。これにより、現代のトランスフォーマーベースの推薦者に対する実用的かつ正確な傾向ベースの評価とモデル選択が可能になる。

著者は、セット十分性の仮定（展開において選択された集合を正規化する必要がある可能性がある）およびスレートサイズ $K$ に対する指数関数的なスケーリングという制限に言及しているが、$K!$ が非現実的な典型的なスレートサイズ（$K \le 10$）においては実用的であると論じている。