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

arXiv:2602.16842 · cs.LG · Submitted 2026-02-18 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor".

Jane: The gist: The exact performance analysis for data-driven newsvendor policies under censored demand data involves reducing an infinite-dimensional, non-convex optimization problem to a finite-dimensional one,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper today called "What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor." It sounds pretty technical, but what it's about is figuring out how much value you get from demand data when that demand gets censored.

Jane: Right. Basically, it takes something we deal with every day—deciding how much stock to keep—and looks at the tricky situation where we only see sales, not actual demand. This paper tries to give us an exact way to figure out how good a policy is under those conditions.

Lu: What's interesting about the title is that it immediately sets up this challenge: valuing censored data exactly. It moves away from just guessing or using approximations and aims for something definitive about performance guarantees, even when you don't know the true demand distribution at all.

Meng: From an engineering standpoint, that means we’re not just looking at simulations anymore; they’re trying to find a mathematical guarantee on how bad things can get in the worst-case scenario. That's a big step for reliability.

Lalam: I think the core idea is taking something that seems infinite—all possible demand distributions—and reducing it down to something manageable, which is what they aim to do with this exact analysis of classical data-driven inventory policies.

The paper's summary: Tom: So, what they actually do in the paper is tackle that infinite-dimensional problem by showing you can reduce it down to a finite-dimensional one. That’s the main technical trick they use. They define worst-case regret as the biggest possible gap between what your policy does and what would be optimal, across every single demand distribution that could have produced your observed censored sales data.

Jane: That’s a heavy concept for driving, but it means they aren't just checking one scenario; they are checking the absolute worst scenario imaginable based on what you actually saw. They provide a general procedure for calculating this exact worst-case regret for any sample size and any level of censoring.

Lu: The way they achieve that reduction is by characterizing policies as piecewise-separable policies first. This means instead of worrying about the whole complex distribution, they summarize everything using a finite set of summary quantities at the places where you have those censoring points.

Meng: So, if you think of it like this: instead of needing to know the exact shape of the demand curve everywhere, you only need to know a few specific numbers at those key inventory levels and right next to them. That makes sense for computation.

Lalam: And they formalize this with Theorem one which collapses that whole problem into a finite-dimensional one whose dimension is at most two times K plus one, no matter how big your sample size n gets <ref:2602.16842#pg1>. That’s the crucial part for making it tractable.

The paper's improvements: Tom: Okay, so they show you can characterize the performance exactly for two specific policies. One is the Biased Sample Average Approximation or BSAA, and another is the Kaplan–Meier policy. They give us exact characterizations for both of those.

Jane: For BSAA, Theorem two shows that the worst-case demand distribution boils down to just a finite collection of K plus one two-dimensional optimization problems. It’s always a three-point distribution with mass at zero, one, and your historical inventory level x.

Lu: That's really sharp because it limits the complexity of the adversarial choice they have to make for BSAA. It doesn't need to be an infinitely complex distribution; it simplifies down to these specific scenarios involving just three points.

Meng: And then there’s the Kaplan–Meier policy. They show that because of how demand is censored by past inventory, it has this inherent non-local dependence on those past censoring points, but they summarize that dependence with a fixed set of scalars F(xone) through F(xk) and F(z).

Lalam: Theorem three gives the exact characterization for the Kaplan–Meier policy. It holds true for any finite sample size and any set of past inventory levels x. That means we get a concrete mathematical rule for how good that specific policy will do, regardless of how much data you have or how much you've seen before.

Tom: What this means practically is that they give us the tools to compare these policies directly using this worst-case regret metric rather than just relying on some asymptotic theory about what happens with a million samples.

Conclusion: Jane: So to wrap up, the main thing here is that this framework lets us compare data-driven inventory policies with an exact performance guarantee based on every possible demand distribution that fits our data. It moves us away from just hoping things work well asymptotically and gives us a principled way to see how much information we actually get from censored sales.

Tom: The paper really shows, for instance, that the Kaplan–Meier policy is robust, but its performance can improve dramatically with very little exploration. They suggest that introducing even a handful of uncensored observations substantially strengthens those worst-case guarantees rather than needing a huge experiment.

Lu: And they also point out something important about using simple heuristics like treating sales as demand when you don't have the censoring indicators. Aggregating more censored sales information can actually deteriorate the worst-case performance, suggesting we should prefer very few uncensored samples over combining a small set with a large censored dataset.

Meng: From an engineering perspective, this means we need to be careful about how we gather data; it's not just about volume, but quality. The sample complexity for the Kaplan–Meier policy shows a sharp phase transition where collecting more samples suddenly becomes much less effective if you’re already at a certain level of censoring x.

Lalam: And for the BSAA policy, they show that the bias from treating censored sales as true demand actually becomes dominant when you aggregate more censored data, which reinforces that idea about needing high-quality observations. Overall, this work on "What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor" gives us a principled basis to know exactly when passive censored data is good enough and when we need to actively explore.

Carnegie Mellon University · New York University

cs.LG

Submitted: 2026-02-18

Updated: 2026-10-11

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: The gist: The exact performance analysis for data-driven newsvendor policies under censored demand data involves reducing an infinite-dimensional, non-convex optimization problem to a

Key concepts

Worst-Case Regret: This measures the largest possible expected performance gap between a chosen inventory policy and the best possible policy, considering all demand distributions that could have generated the observed censored sales data. It sets a rigorous upper bound on potential failure.
Piecewise-Separable Policies: This concept describes policies where the dependence on unknown demand distributions can be summarized by only a finite set of summary quantities at specific points (censoring points). This structure is key because it allows the researchers to simplify the infinite problem into a manageable, finite one.
Phase-Transition Behavior: This refers to a sharp change in sample complexity required to achieve a target performance level. In this context, it means that increasing the censoring point 'x' can cause the number of samples needed for the Kaplan-Meier policy to drop drastically, showing that deliberate exploration is highly effective.
Biased Sample Average Approximation (BSAA): BSAA is a specific data-driven policy analyzed in this paper. Its worst-case regret is characterized by a finite set of two-dimensional optimization problems, proving that the adversarial demand distribution can be simplified to three specific points for analysis.

Terminology

Regret — 1× in this paper · explained in 3 episodes

Summary

The gist: The exact performance analysis for data-driven newsvendor policies under censored demand data involves reducing an infinite-dimensional, non-convex optimization problem to a finite-dimensional one, enabling tractable computation of worst-case regret for any sample size and censoring levels.

Methodological Contribution

The main methodological contribution is the exact performance analysis through worst-case regret, defined as the largest possible expected out-of-sample optimality gap over all demand distributions that could have generated the observed censored sales data<ref:2602.16842#pg11>. The researchers provide a general procedure to compute this exact worst-case regret for classical data-driven inventory policies evaluated over all demand distributions. They show that this infinite-dimensional, non-convex optimization problem can be reduced to a finite-dimensional one, which allows for an exact characterization of policy performance for any sample size and censoring levels.

Policy Characterization and Reduction

The analysis builds on characterizing policies as piecewise-separable policies, which allows the dependence on the underlying demand distribution to be summarized by a finite set of summary quantities at the censoring points. This structure enables a finite-dimensional reduction of the worst-case regret problem which is crucial for tractable computation. Theorem 1 provides this master reduction theorem, collapsing the problem to a finite-dimensional optimization problem of dimension at most 2(K + 1), regardless of sample size n. The optimization variables are interpreted as free parameters describing the behavior of a candidate worst-case demand CDF at the selected inventory levels and immediately to their right, encoding the only degrees of freedom that matter for worst-case regret under piecewise-separable policies.

Analysis of Key Policies

The paper develops exact characterizations for two primary policies:

Biased Sample Average Approximation (BSAA): The worst-case regret of BSAA is characterized by Theorem 2, which reduces the adversarial choice of a worst-case demand distribution to a finite collection of K+1 two-dimensional optimization problems. This shows that the worst-case distribution for BSAA is always a three-point distribution with mass at 0, 1 and one of the historical inventory levels x.
Kaplan–Meier Policy (KM): The KM policy is shown to be piecewise-separable, exhibiting inherently non-local dependence on the past censoring points which is summarized by a fixed set of scalars (F(x1),..., F(xk), F(z)). Theorem 3 yields an exact characterization of the worst-case regret for the KM policy that holds for any finite sample size and past inventory levels x.

Insights and Implications

The analysis yields several key insights regarding data value and exploration.

The Kaplan–Meier policy is robust, but its performance can improve dramatically with very little exploration, suggesting that introducing even a handful of uncensored observations substantially strengthens worst-case guarantees rather than sustained experimentation.
When censoring indicators are unavailable (sales-as-demand heuristic), aggregating more censored sales information can deteriorate worst-case performance, implying one should prefer to use very few uncensored samples rather than combining a small uncensored set with a large censored dataset.
The sample complexity for the KM policy exhibits a phase-transition type behavior, where the number of samples needed to reach a target worst-case regret drops sharply as the censoring level x increases, suggesting that deliberate and limited exploration can dramatically improve worst-case guarantees even under heavy censoring.

Optimal Exploratory Design

The paper addresses the meta problem of inventory design for exploration by defining the problem P(B) as minimizing Reg(π BSAA n x) subject to a global inventory budget B. Lemma 9 shows that an optimal design exists whose unit-count expansion has N⋆ ≤ Nmax(B, q), and therefore it suffices to enumerate N = 1, 2,..., Nmax(B, q) when solving P(B). This provides an implementable recipe for efficiently computing the optimal exploratory inventory design.

Performance Behavior of Exploration

Experiments show that for the KM policy, increasing the inventory level x at which demand is censored reduces the worst-case regret, and a small amount of exploration goes a very long way, with limited exploration leading to performance guarantees within 50%, 25%, and 12.5% of the fully uncensored benchmark. For the BSAA policy, the bias induced by treating censored sales as demand becomes dominant when aggregating more censored data, suggesting that performance is driven primarily by a small number of high-quality, uncensored observations rather than large volumes of censored sales data.

Sample Complexity for KM Policy

The sample complexity required to achieve a target worst-case regret level under the Kaplan–Meier policy exhibits a sharp phase transition, where the target performance is either achievable or unachievable, and increasing the censoring point x becomes the most reliable way to improve performance when learning from censored demand information. For q = 0.9, increasing x from 0.78 to 0.80 reduces the required number of samples from 159 to 58, a reduction by nearly a factor of three in sample complexity. The analysis provides an explicit reduction of the original worst-case evaluation problem to a finite-dimensional optimization problem whose dimension depends only on the number of distinct historical inventory levels and not on the sample size n.

Conclusion

The exact performance characterization provides a principled basis for comparing data-driven policies across varying degrees of censoring. The framework offers a general tool for providing exact performance characterizations in data-driven operational problems by avoiding reliance on asymptotic or concentration-based arguments. It demonstrates that while censoring fundamentally constrains what can be learned from passive data, deliberate and limited exploration can dramatically improve worst-case guarantees. The results translate the exact regret analysis into concrete guidance on when passive censored data suffices, when minimal exploration is highly leveraged, and when naively aggregating censored sales can be actively harmful.

Improvements for AI systems

Inferred Demand Distribution Characterization: The system can derive exact characterization of worst-case regret for any sample size and censoring levels by reducing an infinite-dimensional optimization to a finite-dimensional one, enabling sharp insights on the achievable performance of standard inventory policies under demand censoring.
Robust Policy Comparison Under Censoring: The AI can rigorously compare data-driven inventory policies using worst-case regret, specifically showing that the Kaplan–Meier policy is robust to censoring and that even minimal exploration can unlock near-uncensored performance guarantees, while policies that ignore censoring may suffer persistent performance losses.
Optimal Exploratory Inventory Design: The system can solve the meta problem of inventory design for exploration by finding an optimal budget allocation, specifically using a finite linear program (the epigraph LP with variables x, t, (αi, βi) N i=0 and constraints αi ≥ Ai,N (x, v) for v ∈ V, βi ≥ Bi,N (x, w) for w ∈ W, and t ≥ αi + βi) to achieve an ε-optimal design.
Sales-as-Demand Heuristic Assessment: The system can identify when relying on simple heuristics is detrimental by showing that when censoring is substantial, the bias induced by treating censored sales as true demand can overwhelm the limited high-quality signal contained in the uncensored observations, suggesting a preference for very few uncensored samples (or prioritize their collection) rather than combining a small uncensored set with a large censored dataset.
Sample Complexity Guidance: For the Kaplan–Meier policy, the system can determine if target performance is achievable by analyzing the sharp phase transition in the sample complexity of the Kaplan–Meier policy, providing concrete guidance on when collecting additional samples alone is ineffective and increasing the censoring point becomes the most reliable way to improve performance.