OFF-POLICY EVALUATION AND LEARNING FROM LOGGED BANDIT FEEDBACK: ERROR REDUCTION VIA SURROGATE POLICY
When learning from a batch of logged bandit feedback, the discrepancy between the policy to be learned and the off-policy training data imposes statistical and computational challenges. Unlike classical supervised learning and online learning settings, in batch contextual bandit learning, one only has access to a collection of logged feedback from the actions taken by a historical policy, and expect to learn a policy that takes good actions in possibly unseen contexts. Such a batch learning setting is ubiquitous in online and interactive systems, such as ad platforms and recommendation systems. Existing approaches based on inverse propensity weights, such as Inverse Propensity Scoring (IPS) and Policy Optimizer for Exponential Models (POEM), enjoy unbiasedness but often suffer from large mean squared error. In this work, we introduce a new approach named Maximum Likelihood Inverse Propensity Scoring (MLIPS) for batch learning from logged bandit feedback. Instead of using the given historical policy as the proposal in inverse propensity weights, we estimate a maximum likelihood surrogate policy based on the logged action-context pairs, and then use this surrogate policy as the proposal. We prove that MLIPS is asymptotically unbiased, and moreover, has a smaller nonasymptotic mean squared error than IPS. Such an error reduction phenomenon is somewhat surprising as the estimated surrogate policy is less accurate than the given historical policy. Results on multi-label classification problems and a large-scale ad placement dataset demonstrate the empirical effectiveness of MLIPS. Furthermore, the proposed surrogate policy technique is complementary to existing error reduction techniques, and when combined, is able to consistently boost the performance of several widely used approaches.
The paper proposes to fit a model of the logging policy that generates bandit feedback data, and use this model's propensities when performing off-policy optimization. When the model is well-specified (i.e. the logging policy indeed lies within the parametric class of models we are fitting), and we use maximum likelihood estimation to fit the model, this approach can yield a lower error when evaluating a policy's performance using off-policy data. The paper then shows how this improved off-policy estimation can also yield better off-policy optimization, and demonstrate this in semi-synthetic experiments.
Specific Comments:
Eq2.4: Lambda is overloaded (context distribution vs. regularization hyper-parameter).
Eq3.3: E[.] is used before defining it (i.e., E[.] should be interpreted as E_(x,a)~mu(.|beta*) [.])
Eq3.5: I^-1(beta*) makes sense, but the second term E[ d/d beta (S(x,a; beta*)) ] uses a notation that needs to be introduced (you mean || (E[ d/d beta (S(x,a; beta)) ] |_at beta=beta* )^-1 ||).
After Eq3.7: It will be instructive to specify some examples of logging policies mu which satisfy these assumptions (and how big the O(.) constants are for those examples).
Section 3.2: In practical considerations, expected a discussion of how robust things are when the logging policy class is mis-specified (i.e. assuming there is a beta* such that mu(.|beta*) created the data is unlikely to be true).
For ML- approaches, was a clipping constant M still used? If so, was it crucial and why?
Lemma D.1: The lemmas in appendix should be accompanied by a proof. E.g. what is C_beta? I don't immediately see why D.3 suggests that the inverse of the Fisher matrix has bounded norm (for instance, if x=0 the inverse is undefined).
General Comments:
Clarity: Good. The paper is easy to follow. Some examples from the Appendix can be moved to the main text (especially to provide a firm grounding for the constants appearing in Section3.1)
Correctness: I did not step through Appendix A-C. In Appendix D, there was a questionable claim. The stated theorems in the main text are believable [not surprising that asymptotic bias vanishes when the logging policy model is well-specified].
Originality: This builds on several previous works on off-policy optimization in bandit settings, and proposes a simple addition to improve performance.
Significance: The paper seems to have missed an opportunity; it can be substantially stronger with a more careful study of when fitting the logging policy will help vs. hurt, and what kinds of regularization or alternatives to maximum likelihood estimation can yield similar improvements (e.g. regularizing propensities close to uniform, ensure no small propensities).