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) against the best fixed order in hindsight over T periods. Under independent demand and suitable curvature of expected losses, the bound improves to O(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
Figure 1: Mean loss per period under synthetic demand. Panels (a)–(d) show bimodal surges with the piecewise-linear and quadratic costs, followed by gradual drift with the piecewise-linear and quadratic costs. Each horizon group contains OPT, LD, SAA, and FI-SGD, from left to right. Blue and yellow segments are excess-inventory and shortage loss; patterns identify policies. Dashed lines mark OPT’s mean total loss per period.
Figure 2: Mean regret per period under synthetic demand. Panel assignments and policy order are the same as in Figure 1 . The comparator is the best fixed order in hindsight for each demand sequence. Dashed segments mark OPT’s mean. Negative regret indicates lower cumulative loss than the fixed-order comparator, not negative loss.
Figure 3: Performance on real data, averaged over 100 trials. Within each cost group, policies appear as OPT, LD, SAA, and FI-SGD, from left to right. In panel (a), blue and yellow segments represent excess-inventory and shortage loss; annotations show the percentage increase in total loss of LD and SAA relative to OPT. In panel (b), annotations show their absolute regret differences from OPT. Dashed lines mark OPT’s mean. Error bars are approximate 95% Monte Carlo intervals conditional on the observed dataset.
Inventory control studies how to order, allocate, and position stock to balance service levels, operating costs, uncertainty, and capacity constraints.