Off-Policy Evaluation of Bandit Algorithm from Dependent Samples under Batch Update Policy

Masahiro Kato and Yusuke Kaneko。2020年。プレプリント（arXiv:2010.13554）。 English

推薦や広告配信では、バンディットアルゴリズムが過去の観測をもとに配信方針を更新しながらログを貯めます。このログは独立同一分布ではないため、そのまま使うと別の方策を評価する推定量の性質が保証されません。この研究は、方策を一定期間ごとにまとめて更新する運用に着目し、その構造から漸近正規な推定量を構成しました。

研究が扱う問題

オフ方策評価は、過去のログだけを使って、まだ動かしていない方策の価値を見積もる問題です。既存の推定量の多くは標本が独立同一分布であることを前提にしていますが、バンディットは過去の結果を見て行動選択確率を変えるので、この前提が崩れます。標本が従属だと、漸近正規性も標本数の平方根の速さでの一致性も保証されません。

提案した方法

一定期間は同じ行動選択確率を使い、期間の切れ目でまとめて方策を更新する運用を前提にします。この構造のもとでは、各期間の推定誤差をマルチンゲール差分列として扱えるので、そこから中心極限定理を通して推定量の分布を導けます。

主な結果と成立条件

評価したい方策の価値について、漸近正規な推定量を得ました。先行研究との違いは、置く仮定の弱さにあります。行動選択確率が一つの値へ収束することを仮定せずに済み、ある期間に一部の行動がまったく選ばれなくても扱えます。撹乱母数の推定量に Donsker 条件を課さない点も、機械学習で撹乱母数を推定する場合には効いてきます。行動選択確率が 0 でもよいため、評価したい方策の行動がログ側でほとんど選ばれていないサポート不足の問題も、期間ごとに切って扱うことで同時に解けます。ベンチマークデータと実データを使った実験では、二乗誤差の平均が既存の推定量より小さくなる場合があることを確かめました。

先行研究との関係

標本が独立同一分布である場合のオフ方策評価では、Dudík、Langford、Li の二重頑健な推定量が標準的な出発点です（2011年、Doubly Robust Policy Evaluation and Learning）。従属な標本への対処は大きく三つに分かれます。行動選択確率が収束することを仮定してマルチンゲール差分列の中心極限定理を使う方向、Luedtke と van der Laan のようにマルチンゲール差分列を標準化する方向（2016年、Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy）、そして Hahn、Hirano、Karlan のようにバッチ単位の更新を前提に漸近理論を組み立てる方向です（2011年、Adaptive Experimental Design Using the Propensity Score）。この研究は三つ目に属し、方策の収束を仮定しないところまで条件を弱めたものです。適応的に集めたデータでの区間推定は、Hadad らも重みの取り方を工夫して扱っています（2021年、Confidence intervals for policy evaluation in adaptive experiments）。

利用できる状況

推薦や広告配信のように、バンディットで配信しながらログが貯まっていく現場を想定しています。方策の更新を日次やバッチ処理の単位で行っているなら、その区切りをそのまま推定の単位として使えます。

論文と資料

BibTeX

@misc{ope-bandit-dependent-samples-batch-update,
  author       = {Masahiro Kato and Yusuke Kaneko},
  title        = {Off-Policy Evaluation of Bandit Algorithm from Dependent Samples under Batch Update Policy},
  year         = {2020},
  eprint       = {2010.13554},
  archivePrefix = {arXiv},
  url          = {https://arxiv.org/abs/2010.13554},
}