Distributionally Robust Counterfactual Risk Minimization

Louis Faury, Ugo Tanielian, Flavian Vasile, Elena Smirnova, Elvis Dohmatob

Abstract

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.

Introduction

The challenge of Batch Learning from Bandit Feedback (BLBF) is central to modern interactive systems. In scenarios like recommender systems or ad placement, we often have historical logs of system-environment interactions. The goal is to train a new, improved policy using this logged data without the risks of live deployment.

Traditional Counterfactual Risk Minimization (CRM) typically employs Inverse Propensity Scoring (IPS) to estimate the performance of a candidate policy. However, IPS estimators are notorious for high variance. Naive optimization often leads to the "optimizer's curse," where a policy appears optimal on historical data but fails in production due to post-decision surprise. While methods like the POEM algorithm address this with sample-variance penalties, this paper proposes a more principled approach through Distributionally Robust Optimization (DRO).

Methodology: A Unified Framework

The authors reframe CRM by assuming the empirical distribution of logged data is imperfect. Instead of optimizing for the average case, DRO optimizes the worst-case expected cost over an uncertainty set (a "ball" of possible distributions).

The Theoretical Bridge

A key contribution of this work is proving that Sample-Variance Penalization (SVP)—the mechanism behind algorithms like POEM—is mathematically equivalent to a DRO problem where the uncertainty set is defined by the $\chi^2$ (chi-square) divergence. This insight allows CRM to be generalized using various probability distances.

The aKL-CRM Algorithm

By replacing $\chi^2$ divergence with Kullback-Leibler (KL) divergence, the authors derive a new objective. In this setup, the worst-case distribution behaves like a Boltzmann distribution, acting as an adversary that re-weights training samples to focus on "hard" examples (those with high propensity-weighted costs). To improve stability, the authors introduce an adaptive temperature parameter that updates dynamically based on the policy's empirical variance.

Algorithm 1: The aKL-CRM optimization procedure.

Experimental Evaluation

The proposed methods were evaluated on four standard multi-label classification datasets converted for bandit feedback: Scene, Yeast, RCV1-Topics, and TMC2009.

Key Results

The adaptive algorithm, aKL-CRM, demonstrated superior performance across the board. As shown in the results table below, it achieved the lowest expected Hamming loss on three of the four datasets and remained highly competitive on the fourth.

Performance comparison across four benchmark datasets showing Hamming loss.

Beyond overall performance, the KL-based methods showed significant advantages in "small data" regimes. When logged data is scarce, aKL-CRM and KL-CRM significantly outperform POEM. As the data volume increases, all robust methods converge toward similar performance, supporting the theoretical claim that different $\phi$-divergences are asymptotically equivalent.

Conclusion and Future Work

This work provides a powerful theoretical bridge between CRM and DRO, offering a principled way to handle uncertainty in counterfactual learning. While the current implementation uses L-BFGS, future iterations could benefit from Stochastic Gradient Descent (SGD) for better scalability to industrial-scale datasets. Additionally, extending this framework to Doubly Robust (DR) or Self-Normalized (SN) estimators presents a promising avenue for further performance gains.

Summary updated

Abstract

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.
BibTeX
@inproceedings{faury2020distributionally,
  author = {Louis Faury and Ugo Tanielian and Flavian Vasile and Elena Smirnova and Elvis Dohmatob},
  title = {{Distributionally Robust Counterfactual Risk Minimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=F1LW5Sb2mmS},
}

Loading related content...

Figure