Counterfactual risk minimization: Learning from logged bandit feedback

We develop a learning principle and an efficient algorithm for batch learning from logged bandit feedback. This learning setting is ubiquitous in online systems (e.g., ad placement, web search, recommendation), where an algorithm makes a prediction (e.g., ad ranking) for a given input (e.g., query) and observes bandit feedback (e.g., user clicks on presented ads). We first address the counterfactual nature of the learning problem through propensity scoring. Next, we prove gen-eralization error bounds that account for the vari-ance of the propensity-weighted empirical risk estimator. These constructive bounds give rise to the Counterfactual Risk Minimization (CRM) principle. We show how CRM can be used to derive a new learning method – called Pol-icy Optimizer for Exponential Models (POEM) – for learning stochastic linear rules for struc-tured output prediction. We present a decomposi-tion of the POEM objective that enables efficient stochastic gradient optimization. POEM is eval-uated on several multi-label classification prob-lems showing substantially improved robustness and generalization performance compared to the state-of-the-art. 1