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 problem of Batch Learning from Bandit Feedback (BLBF) involves training a decision-making policy using historical logs of interactions. This is a common scenario in recommender systems and online advertising, where deploying a new policy for exploration is costly or risky. Counterfactual Risk Minimization (CRM) typically employs Inverse Propensity Scoring (IPS) to estimate the performance of a target policy. However, IPS estimators are prone to high variance, leading to the "optimizer's curse"—where a policy appears optimal due to noise but performs poorly in practice.
Existing approaches, such as the POEM algorithm, mitigate this by incorporating empirical variance penalization. This work seeks to provide a more rigorous mathematical foundation for such heuristics by framing CRM within the context of Distributionally Robust Optimization (DRO).
Theoretical Framework: Unifying CRM and DRO
The core contribution of this work is the mathematical unification of CRM and DRO. DRO addresses uncertainty by minimizing the worst-case expected cost over an uncertainty set (a "ball" of distributions) around the empirical data.
The authors demonstrate that the standard sample-variance penalization used in algorithms like POEM is a specific instance of DRO where the uncertainty set is defined by the $\chi^2$ divergence. This insight allows for the generalization of CRM to other divergence measures.
Proposed Method: KL-CRM and aKL-CRM
By utilizing the Kullback-Leibler (KL) divergence instead of $\chi^2$, the authors derive the KL-CRM objective. This approach is equivalent to training against a "Boltzmann adversary" that re-weights samples, focusing the learning process on "hard" examples with higher costs.
To further improve performance, the authors introduce aKL-CRM (Adaptive KL-CRM). This variant dynamically adjusts the temperature parameter ($\gamma$), which controls the aggressiveness of the adversarial re-weighting, based on the empirical variance of the policy's risk. As variance increases, the algorithm becomes more conservative, effectively tying the "hardness" of the adversary to the policy's uncertainty.
Experimental Evaluation
The proposed methods were benchmarked against state-of-the-art baselines using four multi-label classification datasets converted into bandit feedback logs: Scene, Yeast, RCV1-Topics, and TMC2009.
As shown in Table 1, aKL-CRM demonstrates superior performance, outperforming the POEM baseline on three of the four datasets. Notably, on the RCV1-Topics dataset, aKL-CRM reduced the loss to 0.783 from POEM's 0.918.
Furthermore, the robustness of the proposed approach is particularly evident in small data regimes. By varying the "replay count" (the amount of logged data), the authors observed that aKL-CRM maintains a significant performance advantage when data is scarce, which is the most realistic and challenging scenario in real-world applications.
Conclusion
This work demonstrates that Distributionally Robust Optimization provides a principled and effective framework for Counterfactual Risk Minimization. By bridging these two fields, the authors have grounded existing heuristics in robust theory and introduced a superior KL-based algorithm. Future work will focus on scaling these methods using Stochastic Gradient Descent and applying the DRO framework to more complex estimators like Doubly Robust or Self-Normalized IPS.
Summary updated