  In this work, we explore a framework for contextual decision-making to study
how the relevance and quantity of past data affects the performance of a
data-driven policy. We analyze a contextual Newsvendor problem in which a
decision-maker needs to trade-off between an underage and an overage cost in
the face of uncertain demand. We consider a setting in which past demands
observed under ``close by'' contexts come from close by distributions and
analyze the performance of data-driven algorithms through a notion of
context-dependent worst-case expected regret. We analyze the broad class of
Weighted Empirical Risk Minimization (WERM) policies which weigh past data
according to their similarity in the contextual space. This class includes
classical policies such as ERM, k-Nearest Neighbors and kernel-based policies.
Our main methodological contribution is to characterize exactly the worst-case
regret of any WERM policy on any given configuration of contexts. To the best
of our knowledge, this provides the first understanding of tight performance
guarantees in any contextual decision-making problem, with past literature
focusing on upper bounds via concentration inequalities. We instead take an
optimization approach, and isolate a structure in the Newsvendor loss function
that allows to reduce the infinite-dimensional optimization problem over
worst-case distributions to a simple line search.
  This in turn allows us to unveil fundamental insights that were obfuscated by
previous general-purpose bounds. We characterize actual guaranteed performance
as a function of the contexts, as well as granular insights on the learning
curve of algorithms.
