Beyond IID: data-driven decision-making in heterogeneous environments

How should one leverage historical data when past observations are not perfectly indicative of the future, e.g., due to the presence of unobserved confounders which one cannot "correct" for? Motivated by this question, we study a data-driven decision-making framework in which historical samples are generated from unknown and different distributions assumed to lie in a heterogeneity ball with known radius and centered around the (also) unknown future (out-of-sample) distribution on which the performance of a decision will be evaluated. This work aims at analyzing the performance of central data-driven policies but also near-optimal ones in these heterogeneous environments. We first establish, for a general class of policies, a new connection between data-driven decision-making and distributionally robust optimization with a regret objective. We then leverage this connection to quantify the performance that is achievable by Sample Average Approximation (SAA) as a function of the radius of the heterogeneity ball: for any integral probability metric, we derive bounds depending on the approximation parameter, a notion which quantifies how the interplay between the heterogeneity and the problem structure impacts the performance of SAA. When SAA is not rate-optimal, we design and analyze problem-dependent policies achieving rate-optimality. We compare achievable guarantees for three widely-studied problems -- newsvendor, pricing, and ski rental -- under heterogeneous environments. Our work shows that the type of achievable performance varies considerably across different combinations of problem classes and notions of heterogeneity.