On the Hardness of Learning from Censored Demand

We consider a repeated newsvendor problem where the inventory manager has no prior information about the demand, and can access only censored/sales data. In analogy to multi-armed bandit problems, the manager needs to simultaneously "explore" and "exploit" with her inventory decisions, in order to minimize the cumulative cost. Our goal is to understand the hardness of the problem disentangled from any probabilistic assumptions on the demand sequence – importantly, independence or time stationarity – and, correspondingly, to develop policies that perform well with respect to the regret criterion. By combining concepts and results from partial monitoring and bandits with graph-structured feedback, we show that the simple Exponentially Weighted Forecaster, coupled with a carefully designed cost estimator, achieves optimal scaling of the expected regret (up to logarithmic factors) with respect to both the number of time periods and available actions. This result also leads to an important insight: the benefit from "information stalking" as well as the cost of censoring are both negligible, at least in terms of the regret. We demonstrate the flexibility of our technique by combining it with the Fixed Share Forecaster to provide strong guarantees in terms of tracking regret, a powerful notion of regret that uses a large class of action sequences as benchmark. Numerical experiments suggest that the resulting policy outperforms other existing policies (that are tailored to, or facilitated by time stationarity) on nonstationary demand models. Finally, we consider the "combinatorial" version of the repeated newsvendor problem, that is, single-warehouse multi-retailer inventory management of a perishable product. We extend the proposed approach so that, again, it achieves near-optimal performance in terms of the regret