CS Paper Radar

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

Mengxiao Zhang, Yingfei Wang, Haipeng Luo

cs.LG ·submitted 2026-09-26 21:20 UTC · v1
benchmarktheory

Abstract

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 $T$ rounds, Xu et al. [2026] achieved $\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 $\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 $\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 $Ω(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.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning to Price and Stock Under Contextual and Censored Demand

cs.LG ·2026-09-05 ·Zean Han, Zezhen Ding, Jiheng Zhang
top venue similarity 0.72
Abstract · 9 pages, 3 figures

To make optimal joint pricing and inventory control decisions is a critical challenge for modern retailers. In practice, retailers face changing market conditions where demands are influenced by various contextual factors, while simultaneously dealing with the difficulty of lost sales that obscure true demand information. However, existing approaches often fail to account for both contextual information and censored demand observations. We address this gap by presenting a framework where we model demand as a linear combination of basis functions with unknown coefficients, allowing for adaptive pricing and inventory decisions that respond to changing contexts. We propose an efficient algorithm to achieve regret bound $\mathcal{O}(K\sqrt{T}\log T)$ under concave revenue conditions and $\mathcal{O}(K^{2/3}T^{2/3}(\log T)^{1/2})$ for the general case, with matching lower bounds confirming optimality. Extensive numerical experiments across diverse scenarios demonstrate our algorithm's effectiveness.

0.60

Nonparametric Contextual Pricing and Inventory Learning under Censored Demand

cs.LG ·2026-08-31 ·Zean Han, Jing Liang, Ruihan Lin, Zezhen Ding, Jiheng Zhang
theory similarity 0.70
Abstract · 31 pages, 3 figures

In online retailing, when a product sells out, a retailer often sees only the units sold, not how many customers would have bought it had inventory been available. However, the inventory level determines how much demand is revealed, and this information can influence subsequent decisions and future profits. We study an online selling problem in which, in each round, the seller observes a market context and then makes pricing and stocking decisions based on censored sales data from previous rounds. The challenge is to learn a context-dependent pricing and stocking policy without assuming a particular formula for demand or observing realized profit. To overcome this difficulty, we propose a Mean-Calibrated Kernel UCB (MCK-UCB) algorithm that turns each incomplete sales record into a reliable guide for both inventory and price decisions, using data from past rounds with similar market conditions. This design allows us to learn while serving customers, without a separate exploration phase or the need to recover all demand hidden by stockouts. We prove the minimax optimality of the proposed algorithm, with strictly faster rates when expected profit varies more smoothly with price. Comprehensive numerical experiments have been conducted to confirm the effectiveness of the proposed algorithm.

0.22

Dynamic Run-Out Pricing for Perishable Goods

cs.GT cs.DM ·2026-10-12 ·Farbod Ekbatani
similarity 0.70
Abstract

I study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. I propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, I show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, I extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, I introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and I prove that it restores asymptotic optimality with a strict polynomial convergence rate.

0.20

Overcoming Demand Censoring through Randomization for Risk-Sensitive Newsvendor Learning

cs.LG math.OC ·2026-11-01 ·Zhengchao Wang, Nam Ho-Nguyen
similarity 0.70
Abstract · 30 pages of main text and 4 figures

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(T^{2/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(\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.

0.21

Information Limits of Multistage Inventory Control: Learning, Valuation, and Censoring

eess.SY math.OC ·2026-09-29 ·Hanzhang Qin, David Simchi-Levi, Ruihao Zhu
theory similarity 0.69
Abstract

Learning how to replenish inventory and estimating the cost of doing so require different information. We establish information-theoretic lower bounds for offline multistage inventory control with independent bounded demand. For fixed additive error in total expected cost, policy learning requires cubically many scalar observations in the horizon in the worst case, even under full observation and adaptive sample allocation. This matches the known empirical-risk upper order. Stationarity permits a quadratic policy-learning guarantee, yet valuation with inherited stock can remain cubically difficult even when the optimal policy is known. Censoring sharpens this distinction: optimal decisions can be learnable while absolute costs remain unidentified. We give a carrysafe coverage condition under which truncation preserves inventory transitions and policy gaps exactly. Combining this reduction with a matching lower bound yields the sharp censored-learning rate, with raw sample requirements inversely proportional to the usable fraction of sales logs. The same qualified observations can check coverage and fit the policy under a joint error guarantee. The results isolate information limits for decisions and valuation under an explicit conditionally independent logging protocol.

0.42

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

cs.LG stat.ML ·2026-09-30 ·Yuxuan Han, Xiaoyu Fan, Jiawei Zhang, Zhengyuan Zhou
similarity 0.68
Abstract

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.

0.26

An $O(n\log n)$ Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

cs.CE ·2026-11-17 ·Kleitos Papadopoulos
similarity 0.67
Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold $Q > 0$ for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of $Q$. We give an exact $O(n\log n)$-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using $O(n)$ working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in $O(n\log n)$ time and $O(n\log n)$ space.

0.20

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.66
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31