Despite the wide availability of data, when considering a decision-making problem of interest, “relevant” data may be limited in practice due to the heterogeneity of market characteristics: datasets are usually constructed in certain spatio-temporal contexts and have to be used in other ones. For instance, the demand for a given product may vary significantly over time or in different geographic locations. How should one leverage such data for decision-making and what performance can one expect as a function of the data at hand?

In this work, we propose a framework to understand the interplay between relevance of past data and performance of data-driven algorithms across all sample sizes, small and large. We demonstrate this framework by anchoring our analysis around the contextual Newsvendor problem in which the decision-maker observes past demands and associated contexts, and needs to make a decision in a new context. In our model, closeness of contexts is indicative of closeness in distributions but the distribution of past or future demands is unknown to the decision-maker. We analyze the performance of data-driven algorithms through a notion of context-dependent worst-case expected regret. Our analysis significantly departs from classical concentration-based arguments. In particular, our central methodological contribution is to characterize, in an exact fashion, for any given configuration of contexts, the worst-case regret of any policy belonging to a broad class that includes most common algorithms for the Newsvendor problem (Sample Average Approximation (SAA), k-NN, Kernel methods,…). This result in turn allows us to unveil fundamental insights on the actual learning behavior of these central policies, and the economics of data sizes. In particular, we show that, for the Newsvendor problem, very few samples go a long way towards good operational decisions.