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

Masahiro Kato and Yusuke Kaneko. 2020. Preprint (arXiv:2010.13554). 日本語版

In recommendation and ad delivery, a bandit algorithm updates the delivery policy from what it has already observed, and the logs accumulate as it runs. Those logs are not independent and identically distributed, so an estimator applied to them directly carries no guarantee when it is used to evaluate another policy. This study looks at systems that update the policy in batches at fixed intervals and uses that structure to construct an asymptotically normal estimator.

The problem

Off-policy evaluation estimates the value of a policy that has never been run, using logged data alone. Most existing estimators assume the sample is independent and identically distributed. A bandit breaks that assumption by design, since it reads past results and changes the action selection probabilities in response. Once the sample is dependent, neither asymptotic normality nor consistency at the rate of the square root of the sample size is guaranteed.

The proposed method

The setting assumes that the same action selection probabilities hold for a fixed period and that the policy is updated in one go at the period boundaries. Under that structure the estimation error within each period can be treated as a martingale difference sequence, and a central limit theorem then delivers the distribution of the estimator. Convergence of the action selection probabilities to a single value over time is not assumed.

Main results and conditions

The result is an asymptotically normal estimator of the evaluation policy's value. What separates it from earlier work is how little it assumes. Nothing requires the action selection probabilities to converge to a single value, and an action that goes entirely unselected during some period is still allowed. No Donsker condition is imposed on the estimator of the nuisance parameters, which matters once those parameters are estimated by machine learning. Because a zero action selection probability is permitted, a second problem is solved at the same time: when the logging policy hardly ever chooses the actions the evaluation policy would choose, support is deficient, and cutting the data by period handles that case. Experiments on benchmark data and on real data show that the mean squared error is smaller than that of existing estimators in some cases.

Relation to earlier work

For off-policy evaluation with independent and identically distributed samples, the doubly robust estimator of Dudík, Langford, and Li is the standard starting point (2011, Doubly Robust Policy Evaluation and Learning). Work on dependent samples falls into three groups. One assumes that the action selection probabilities converge and applies the central limit theorem for martingale difference sequences. A second standardizes the martingale difference sequence, as Luedtke and van der Laan do (2016, Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy). A third builds the asymptotic theory on batch updates, as in Hahn, Hirano, and Karlan (2011, Adaptive Experimental Design Using the Propensity Score). Our work belongs to the third group and weakens its conditions far enough to drop convergence of the policy. Interval estimation from adaptively collected data is also treated by Hadad and coauthors through a careful choice of weights (2021, Confidence intervals for policy evaluation in adaptive experiments).

Where it applies

The intended setting is a live recommendation or advertising system where a bandit serves traffic and the logs pile up. If the policy is updated daily or on some other batch schedule, those boundaries can serve directly as the unit of estimation.

Paper and materials

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},
}