When People Change their Mind: Off-Policy Evaluation in Non-stationary Recommendation Environments

[usaito]

0. 論文概要

Rolf Jagerman, Ilya Markov, and Maarten de Rijke. When People Change their Mind: Off-Policy Evaluation in Non-stationary Recommendation Environments. In WSDM 2019: 12th International Conference on Web Search and Data Mining. ACM, February 2019.

** 図表は全て本論文からの引用です.

1. 要約

• Non-stationaryを前提としたOff-Policy Evaluationの新たな問題設定
• context-rewardの同時確率分布がtに依存して異なる状況だと, naive IPS Estimatorはtに依存して増加するbiasを持つ
• naive IPSが持つbiasの問題を解消する2つの推定量を提案し, 2つのデータセットを用いて性能を比較した

2. 背景

• 既存のOPEの研究は, stationary worldを前提としているがこれは現実的ではない.
• 実際は, context-rewardの同時確率分布がtに依存して異なるnon-stationary worldの方が現実的. （しかし, value functionはリプシッツ関数を仮定することで急激な変化は起きないとしている）
• non-stationaryだと, 既存のnaive IPS推定量は, リプシッツ定数とtに依存して増加するbias（の上界）を持ってしまう

3. 提案手法

• naive IPSが持つbiasが増加しつつげてしまう問題を解消する2つの推定量を提案

1. Sliding Window IPS

• tにおけるValueを推定するのにt以前のτ回のデータのみを用いて推定

• biasの上界がτに依存するが, tに非依存.
• τが小さいほどbiasの上界を小さくできるが, 小さすぎるとvarianceが大きい

2. Exponential decay IPS

• 観測された時刻が新しくなるほど大きくなるような重みを導入してIPSを補正

• biasの上界がαに依存するが, tに非依存.
• αが大きいとより昔の観測情報を重視, 逆に小さいと新しい情報を重視
• αが小さいほどbiasを小さくできるが, 小さすぎるとvarianceが大きい

さらに, 2つの推定量のハイパーパラメータをadaptiveに決める方法を提案している. （推定のMSEが小さくなるような基準）

4. 実験

概要

2つのデータセットに対して, 以下の3つの状況を想定してLinUCBを走らせた際のtごとのvalueを推定し, 精度をMSEで評価.

• Smooth Change: リプシッツ関数の仮定が満たされる緩やかな変化
• Abrupt Change: リプシッツ関数の仮定が満たされない急激な変化を伴う
• Stationary: 分布がtに非依存

結果

• SmoothやAbrupt(non-stationary)だと提案推定量がnaive IPSよりも有意に小さいMSEを達成
• 逆にstationaryだとnaive IPSが良い（提案推定量は観測情報をいくらか捨てるため分散が大きい）
• Adaptiveにハイパーパラメータを決めた方が精度よく推定できる場合がある

5. コメント

• OPEにおいてより現実に近い問題設定を唱えたところが評価されたと思われる
• 一方で, 提案推定量はとてもシンプル. 著者も述べているがこれからDR等のnon-stationaryへの応用研究が出てくると考えられる（ただし、分散の分析は追加的な仮定を置かないと難しそう？）
• ソースコードが公開されているので年内に追試やりたい

6. 関連論文ピックアップ

• 後続研究に期待