cs.LGNov 1, 2026

Overcoming Demand Censoring through Randomization for Risk-Sensitive Newsvendor Learning

Authors: Zhengchao Wang, Nam Ho-Nguyen

Organizations: The University of Sydney

Abstract

We study online newsvendor learning with bounded demand, censored observations, and convex nonlinear shortage costs. Because stockouts can conceal the shortage magnitudes needed by gradient-based algorithms, we use randomized ordering to construct unbiased subgradient estimates. We characterize admissible randomization distributions within this framework and develop an online inventory policy that combines the resulting subgradient estimates with gradient-based updates. Our regret analysis quantifies the cost of randomization via the estimation variance and an additional loss term. We characterize the randomization distributions that minimize this objective. For piecewise-linear shortage costs, the optimal distribution is computed through a linear-time recursion; for costs with bounded curvature density, it is characterized by a scalar ordinary differential equation. The policy achieves expected regret of O(T2/3)O(T^{2/3}) against the best fixed order in hindsight over TT periods. Under independent demand and suitable curvature of expected losses, the bound improves to O(T)O(\sqrt{T}). Matching minimax lower bounds establish rate optimality over the corresponding classes with a fixed marginal-cost bound. Both rates extend to nonperishable inventory under uniformly positive conditional expected demand. Numerical experiments on synthetic and retail data show improvements over alternative policies using censored observations.

Figures & tables

Explore similar work

Feb 18, 2026

What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor

We study the offline data-driven newsvendor problem when historical demand is censored by past inventory levels. We introduce a class of policies for which worst-case expected regret over all bounded demand distributions admits an exact finite-dimensional characterization, valid for any sample size and historical inventory design. The dimension depends on the number of distinct inventory levels, rather than the number of observations. This framework yields exact analyses of the sales-as-demand heuristic, the Kaplan-Meier policy, and recent policies from the censored-newsvendor literature. We leverage this reduction to derive sharp insights on the achievable performance of standard inventory policies under demand censoring. In particular, our analysis of the Kaplan-Meier policy shows that while demand censoring fundamentally limits what can be learned from passive sales data, just a small amount of targeted exploration at high inventory levels can substantially improve worst-case guarantees. Finally, we further leverage our reduction to design new policies that push the frontier and substantially improve upon the worst-case regret of known policies, reducing it by up to 40%.
Sep 30, 2026

Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach

We study data-driven multi-period lost-sales inventory control under censored demand, where a stockout reveals only that demand exceeded the stocking level. We develop a unified, model-based framework for policy learning from censored data, built on a new cost decomposition for base-stock policies and a biased sample-average approximation (SAA) approach. The cost decomposition allows us to propose a new coverage condition under which censored observations are informative enough for sample-efficient policy learning. Guided by this coverage condition, we design two biased SAA algorithms: an upper-biased one that achieves near-optimal sample complexity under the offline coverage condition, and a lower-biased one that actively generates the required coverage and achieves near-optimal regret online. More broadly, this biased SAA approach provides a general principle for implementing pessimism and optimism under censored feedback, which may be of independent interest.
Sep 26, 2026

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

We study online dynamic pricing with censored demand, where an arbitrary inventory level is revealed before pricing and may adapt to past observations, while demand follows an unknown, price-dependent distribution that is stationary over time. For a horizon of TT rounds, Xu et al. [2026] achieved O~(T)\widetilde{\mathcal{O}}(\sqrt{T}) regret under restrictive structural assumptions including linear demand, price-independent additive noise, and conditions relating inventory levels to the noise support. Our first contribution is to extend this framework to a substantially more general and statistically harder nonparametric setting, requiring only the natural assumption that expected sales are nonincreasing in price and allowing nonlinear demand curves and price-dependent noise. For this model, we first propose a simple baseline, Double-Grid-UCB, which discretizes both price and inventory and achieves O~(T3/4)\widetilde{\mathcal{O}}(T^{3/4}) expected regret using separate revenue estimates for each price-inventory grid pair. Then, we develop Threshold-UCB, which improves the expected regret to O~(T2/3)\widetilde{\mathcal{O}}(T^{2/3}). Unlike Double-Grid-UCB, Threshold-UCB reuses sales observations across inventory levels through shared estimates of demand-tail probabilities, allowing the same data to support revenue upper bounds for multiple inventories rather than a single inventory bin. We also complement this upper bound with an Ω(T2/3)Ω(T^{2/3}) lower bound via a reduction from stochastic posted pricing, establishing its minimax optimality. Finally, extensive experiments across inventory processes, demand functions, and noise models demonstrate consistently superior performance of Threshold-UCB over benchmark algorithms.