Exploiting Similarities in A/B Testing with Off-Policy Estimation

技術要約：オフポリシー推定を用いたA/Bテストにおける類似性の活用

問題提起
A/Bテストは、新しい決定システム（$\pi_A$）の性能向上をベースライン（$\pi_B$）と比較するための標準的なプロトコルである。従来、これは平均差推定法を用いて行われ、両方のシステムをブラックボックスとして扱う。この手法は不偏ではあるものの、両方のポリシー間の構造的な類似性を無視しているため、統計的に最適とは言えない。現代のオンラインアプリケーション（広告やレコメンデーションなど）において、決定システムはしばしば確率的であり、かつ大きな構造を共有している。つまり、特定の決定を下すための「傾向（propensities）」が類似しているのである。本論文は、ポリシーが重なり合っている場合、古典的な推定法は不必要な分散を生じさせる一方で、標準的なオフポリシー推定（OPE）手法は、重要度重み付け（importance weighting）に依存しているために、A/Bテストを直接置き換えるにはバイアスが強すぎるか不安定になりやすいと主張している。

手法
著者らは、標準的な実験プロトコルを変更することなく、ポリシー間の重なりを利用するA/Bテスト推定法のファミリーを提案する。

1. フレームワーク: 問題は、ユーザーが軌跡 $\tau$ にわたってシステムと相互作用する拡張非マルコフ決定過程（NMDP）フレームワーク内でモデル化される。目標は、改善量 $I(\pi_A, \pi_B) = V(\pi_A) - V(\pi_B)$ を推定することである。
2. 推定量の構成: 提案された推定量 $\hat{I}_f$ は、以下の2つのコンポーネントを組み合わせる：
   • ベースライン・ポリシー（$D_B$）からのデータを用いた、$f$ 正則化逆傾向スコア（IPS）項。
   • ターゲット・ポリシー（$D_A$）からのデータを用いた、バイアス補正項。
   • 関数 $f: \mathbb{R}_+ \to \mathbb{R}$ は、重要度重み $w(\tau) = \pi_{target}(\tau) / \pi_{source}(\tau)$ を変換する。
3. 理論的条件:
   • 不偏性: $f(0) = -1$ であるとき、推定量は不偏となる。この条件は、ポリシーが互いに素な支持集合を持つ場合（重なりがない場合）、推定量が自然に標準的な平均差推定法へと回帰することを保証する。
   • 分散減少: 分散を低減するために、著者らは分散サロゲート $S_f$ を定義する。彼らは、$f$ に関する条件（具体的には $f(1)=0$ および $f(x)$ の境界）を導出し、ポリシーが類似している場合に、平均差推定法よりも低い分散を保証する。
4. 最適な変換:
   • サロゲート最適 ($f^*_{n_r}$): 著者らは、分散サロゲートを最小化する閉形式の関数 $f^*_{n_r}(x) = \frac{x-1}{n_r x + 1}$ （ここで $n_r = n_A/n_B$）を導出した。この推定量は、サンプル不均衡を考慮するために両方の集団のデータを効果的に再重み付けする。
   • 誤設定に配慮した設計 ($f^*_{\lambda, \Delta}$): 傾向（propensity）はデータから推定されることが多く、既知ではないという事実を認識し、著者らは、傾向の誤設定下でのバイアスと分散のバランスを取るための正則化パラメータ $\lambda$ を導入した。これにより、誤設定が増大しても緩やかに平均差推定法へと劣化する、堅牢な推定法が得られる。

主な貢献

• 新しい推定法ファミリーの導入: ポリシーの重なりを明示的に利用する、重要度重み付けに基づく柔軟なA/Bテスト推定法のファミリーを導入した。
• 理論的保証: 推定量が特定の $f$ の条件下で不偏であることを証明し、ポリシーが類似している場合に改善された収束特性（より低い分散）を示すことを実証した。
• 堅牢性: 傾向がデータから推定される場合の誤設定に対しても、高MSEを示す標準的なIPSや素朴な正則化推定法とは異なり、堅牢に機能する誤設定配慮型バリアントを開発した。
• 緩やかな劣化: 本推定法は、ポリシーが明確に異なる（重なりがない）場合や誤設定が深刻な場合に、自動的に標準的な平均差推定法へと回帰するように設計されており、不利なシナリオにおいて性能低下を招かない。

実験結果
著者らは、以下の3つの実験設定を通じて提案手法を検証した：

1. 重なり合うポリシーとデータの不均衡: 単純化されたバンディット設定において、提案された推定法は、ポリシーが近い場合、大幅な分散減少（特定のシナリオで最大27倍）を達成した。この減少は、標準的な差推定法が苦戦する不均衡なユーザー割り当て（$n_A \neq n_B$）において特に効果的であった。
2. 誤設定への感度: 誘導された傾向推定誤差があるシナリオにおいて、標準的なIPSおよび素朴な正則化推定法（$h_1$）は高い平均二乗誤差（MSE）を示した。対照的に、提案された誤設定配慮型推定法は、平均差推定法を一貫して上回り、中程度から高いレベルの誤設定下でも低いMSEを維持した。
3. 現実的なレコメンデーション問題: ユーザーの退屈（boredom）を伴う非マルコフ的なレコメンデーション環境をシミュレートし、ホライゾン $T \in \{1, \dots, 32\}$ についてテストを行った。分散最適化推定法（$f^*_1$）は、短・中程度のホライゾンにおいてMSEを大幅に減少させた。しかし、長いホライゾンでは、傾向推定の誤差の累積により性能が低下した。誤設定配慮型推定法は、すべてのホライゾンにわたって安定した緩やかな利点を提供し、標準的な差推定法やDiffQのような他のOPEベースのアプローチを上回った。

意義と主張
本論文は、オフポリシー推定のアイデアは単にA/Bテストの代替品としてではなく、A/Bテスト自体の統計的効率を高めるためのツールとして機能すべきであると主張している。既知または推定されたシステムの傾向を利用することで、実務者は同じサンプルサイズでより正確な改善推定を得ることができる。提案手法の重要性は以下の点にある：

• 標準的なA/Bテストのデータ収集プロトコルを変更する必要がない。
• 推定された傾向という実務上の現実に適応している。
• 「両者の最善」のシナリオを提供する：ポリシーが類似している場合（反復的なシステム更新における一般的なケース）には大幅な分散減少を提供し、ポリシーが異なる場合には安全性（標準的なA/Bテストより悪くならないこと）を保証する。

著者らは、本手法は重なり合うポリシーにおける分散の問題に対処しているものの、傾向のドリフトが顕著になる非常に長いホライゾンにおいては依然として課題が残っており、逐次的な構造や二重に堅牢な（doubly robust）手法を活用することが今後の課題であると結論付けている。