The Self-Normalized Estimator for Counterfactual Learning
This paper identifies a severe problem of the counterfactual risk estimator typically used in batch learning from logged bandit feedback (BLBF), and proposes the use of an alternative estimator that avoids this problem. In the BLBF setting, the learner does not receive full-information feedback like in supervised learning, but observes feedback only for the actions taken by a historical policy. This makes BLBF algorithms particularly attractive for training online systems (e.g., ad placement, web search, recommendation) using their historical logs. The Counterfactual Risk Minimization (CRM) principle [1] offers a general recipe for designing BLBF algorithms. It requires a counterfactual risk estimator, and virtually all existing works on BLBF have focused on a particular unbiased estimator. We show that this conventional estimator suffers from a propensity overfitting problem when used for learning over complex hypothesis spaces. We propose to replace the risk estimator with a self-normalized estimator, showing that it neatly avoids this problem. This naturally gives rise to a new learning algorithm -Normalized Policy Optimizer for Exponential Models (Norm-POEM) -for structured output prediction using linear rules. We evaluate the empirical effectiveness of Norm-POEM on several multi-label classification problems, finding that it consistently outperforms the conventional estimator.
- A question to clarify in the rebuttal: from Section 4.1 in [1], it is said that the CRM approach only makes sense for delta in [-1,0] (and thus they propose to rescale a general loss to [-1,0]). My guess is that it should be the same for NORM-POEM here -- i.e. (8) and (3) both uses the re-scale delta in [-1,0], correct? In this case, I do not understand what it means to use "delta > 0" in the experiment in Table 1. Please clarify.== Other comments ==- There is something I find missing in the setup for "batch learning from logged bandit feedback" of Section 3 (or from [1]): I feel the feedback should also be seen as a random variable, rather than a deterministic function as presented on line 110. Here is my rationale. Suppose that the partial feedback is coming from a classification problem where we just do not know the labels, we only get feedback by trying a prediction and seeing what is the loss. Suppose that there is a true classification loss Delta(y',y), and that the way the feedback is generated is, for a given input x, we make a prediction y using h_0; some god agent labels also the input to y'; and then tells us the loss Delta(y',y) that we incur (so here delta(x,y) is Delta(y',y) for the y' given to this example). On the other hand, often in classification, we suppose that the labeling can be noisy and so there is not necessarily a unique y' assigned to each x. This means that somewhere else in the log, we could have the same x as input, the same y that we played, but with a different delta(x,y) as the god agent just had given a different label for this one... This is why I think that in general delta(x,y) should be seen as a random number (in the classification example above the mean of this random variable for a fix x & played y should be the expectation of Delta(y',y) for y' distributed according to p(y'|x), the true noisy labeling distribution).This perhaps does not change anything about the risk estimator (2); but at least the setup in (1) with the true risk should be presented with an additional expectation over the randomness of delta, to be more general.- Line 170-171: I think it should be h(y|x) / h_0(y|x). Also, it might be worthwhile to mention that the lack of linearity was already pointed out in [1].- Line 276: you should probably put argmin instead of argmax given that you are minimizing the risk...- Line 319: replace bars with hats in the notation to be consistent with the previous convention. === Update after rebuttal ==Thanks for the clarifications.