  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 and understanding key drivers of performance. We establish a first
result which allows to upper bound the asymptotic worst-case regret of a broad
class of policies. Leveraging this result, for any integral probability metric,
we provide a general analysis of the performance achieved by Sample Average
Approximation (SAA) as a function of the radius of the heterogeneity ball. This
analysis is centered around the approximation parameter, a notion of complexity
we introduce to capture how the interplay between the heterogeneity and the
problem structure impacts the performance of SAA. In turn, we illustrate
through several widely-studied problems -- e.g., newsvendor, pricing -- how
this methodology can be applied and find that the performance of SAA varies
considerably depending on the combinations of problem classes and
heterogeneity. The failure of SAA for certain instances motivates the design of
alternative policies to achieve rate-optimality. We derive problem-dependent
policies achieving strong guarantees for the illustrative problems described
above and provide initial results towards a principled approach for the design
and analysis of general rate-optimal algorithms.
