Distributionally Robust Counterfactual Risk Minimization

This manuscript introduces the idea of using Distributionally Robust Optimization (DRO) for the Counterfactual Risk Minimization (CRM) problem. Tapping into a rich existing literature, we show that DRO is a principled tool for counterfactual decision making. We also show that well-established solutions to the CRM problem like sample variance penalization schemes are special instances of a more general DRO problem. In this unifying framework, a variety of distributionally robust counterfactual risk estimators can be constructed using various probability distances and divergences as uncertainty measures. We propose the use of Kullback-Leibler divergence as an alternative way to model uncertainty in CRM and derive a new robust counterfactual objective. In our experiments, we show that this approach outperforms the state-of-the-art on four benchmark datasets, validating the relevance of using other uncertainty measures in practical applications. Learning how to act from historical data is a largely studied field in machine learning [27, 8, 18, 17] , spanning a wide range of applications where a system interacts with its environment (e.g search engines, ad-placement and recommender systems). Interactions are materialized by the actions taken by the system, themselves rewarded by a feedback measuring their relevance. Both quantities can be logged at little cost, and subsequently used to improve the performance of the learning system. The Batch Learning from Bandit Feedback [28, 29] (BLBF) framework describes such a situation, where a contextual decision making process must be improved based on the logged history of implicit feedback observed only on a subset of actions. Counterfactual estimators [3] allow to forecast the performance of any system from the logs, as if it was taking the actions by itself. This enables the search for an optimal system, even with observations biased towards actions favored by the logger. A natural approach to carry out this search consists in favoring systems that select actions with high empirical counterfactual rewards. However, this initiative can be rather burdensome as it suffers a crucial caveat intimately linked with a phenomenon known as the optimizer's curse [4, 26, 30] . It indicates that sorting actions by their empirical reward average can be sub-optimal since the resulting expected post-decision surprise is non-zero. In real life applications where the space of possible actions is often extremely large and where decisions are taken based on very low sample sizes, the consequence of this phenomenon can be dire and motivates the design of principled robust solutions. As a solution for this Counterfactual Risk Minimization (CRM) problem, the authors of [28] proposed a modified action selection process, penalizing behaviors resulting in high-variance estimates.