Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

Mengxiao Zhang; Yingfei Wang; Haipeng Luo

cs.LGSep 26, 2026

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

Authors: Mengxiao Zhang, Yingfei Wang, Haipeng Luo

Organizations: University of Iowa · University of Washington · University of Southern California

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.

Figures & tables

Panel of Figure 1 — Figure 1: Mean cumulative expected regret over 30 held-out paths; shading indicates one sample standard deviation. Titles specify demand, inventory pattern, and noise type. Only A-1-U-Add matches C20CB’s conditions. Broad inventory violates its support conditions, nearly flat Demand B makes the admissible inventory interval empty, and multiplicative noise violates its common additive-noise assumption. C20CB is omitted for nonlinear Demand C. Threshold-UCB achieves the lowest final regret in all panels except A-1-U-Add , where fixed-horizon C20CB is slightly lower.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Code	Type	Exact configuration
1-U	Uniform	$\gamma_{t}\sim\mathrm{Unif}[0.86,1.29]$ .
2-U	Uniform	$\gamma_{t}\sim\mathrm{Unif}[0.02,1.75]$ .
1-G	Clipped Gaussian	$\gamma_{t}=\operatorname{clip}\{N(1.075,0.14^{2}),0.86,1.29\}$ .
2-G	Clipped Gaussian	$\gamma_{t}=\operatorname{clip}\{N(0.85,0.55^{2}),0.02,1.75\}$ .
3-U	Piecewise uniform	Cycle $[0.02,0.30]$ , $[0.86,1.29]$ , and $[1.45,1.75]$ .
3-G	Piecewise Gaussian	Cycle clipped $N(0.12,0.05^{2})$ , $N(1.075,0.14^{2})$ , and $N(1.60,0.06^{2})$ on the same three supports.

Appendix

Table 1: Inventory processes used in both noise suites. The codes combine support pattern with distribution: U denotes uniform and G denotes clipped Gaussian. Piecewise processes cycle through three regimes.

Method	Hyperparameters	Search ranges (reference values)
Threshold-UCB	$K,J,c_{\rm conf}$	$K,J\in\{11,\ldots,44\}$ ( $22$ each); $c_{\rm conf}\in[0.5,2]$ ( $1$ ).
C20CB	$s_{\tau},s_{M},c_{\rm conf}$	$s_{\tau},s_{M},c_{\rm conf}\in[0.5,2]$ ( $1$ each), with $\tau=\lceil s_{\tau}\sqrt{T}\rceil$ and $M=\lceil s_{M}T^{1/4}\rceil$ .
C20CB-doubling	$s_{\tau},s_{M},c_{\rm conf}$	Same as C20CB, with $T$ replaced by the epoch length $H\in\{1,2,4,\ldots\}$ and $\tau$ capped at $H$ .
KM-UCB	$K,\alpha$	$K\in\{11,\ldots,44\}$ ( $22$ ); $\alpha\in[1,4]$ ( $2$ ).
Naive-UCB	$K,\alpha$	Same as KM-UCB.

Appendix

Table 2: Hyperparameters tuned in the additive-noise experiments with

T=10{,}000

. Reference values, which are included among the initial configurations, are given in parentheses.

Figure 2: Additive-noise Demand A. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. Only A-1-U-Add and A-1-G-Add satisfy C20CB’s inventory conditions; the broad and piecewise processes test performance when those conditions fail.

Figure 3: Additive-noise Demand B. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively.

Figure 4: Additive-noise Demand C. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. C20CB is omitted because the mean demand is nonlinear.

Figure 5: Additive-noise Demand D. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. C20CB is omitted because the mean demand is nonlinear.

Demand	Low multiplier $\ell$	Low-state probability $q(p)$	Demand bound $D_{\rm exp}$
A	$0.20$	$2(p-0.65)_{+}$	$1.8$
B	$0.63$	$0.95\bigl(3x(p)^{2}-2x(p)^{3}\bigr)$	$9$
C	$0.20$	$2(p-0.65)_{+}$	$1.35$
D	$0.20$	$\min\{0.85,1.4p\}$	$2.25$

Appendix

Table 3: Multiplier distributions for multiplicative noise. The last column gives the demand bound

D_{\rm exp}\geq\max_{p\in[0,1]}\mu(p)h(p)

, which upper-bounds every realization of potential demand.

Figure 6: Multiplicative-noise Demand A. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. The mean matches additive Demand A, but the price-dependent noise violates C20CB’s common additive-noise assumption.

Figure 7: Multiplicative-noise Demand B. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. The nearly flat linear mean is combined with a price-dependent probability of low demand, which violates C20CB’s common additive-noise assumption.

Figure 8: Multiplicative-noise Demand C. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. C20CB is omitted because the mean demand is nonlinear.

Figure 9: Multiplicative-noise Demand D. Columns correspond to the central ( 1 ), broad ( 2 ), and piecewise-changing ( 3 ) inventory supports; the top and bottom rows use uniform ( U ) and clipped-Gaussian ( G ) inventory distributions, respectively. C20CB is omitted because the mean demand is nonlinear.

Explore similar work

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand
May 7, 2026Jianyu Xu, Yu-Xiang WangContextual Bandits UCB Algorithms
Carnegie Mellon University Pittsburgh, PA 15213
Learning to Price and Stock Under Contextual and Censored Demand
Sep 5, 2026Zean Han, Zezhen Ding, Jiheng ZhangDynamic Pricing Supply Chain Management
The Hong Kong University of Science and Technology
Nonparametric Contextual Pricing and Inventory Learning under Censored Demand
Aug 31, 2026Zean Han, Jing Liang, Ruihan Lin +2Inventory Control Learning with Missing Data
Department of Industrial Engineering and Decision Analytics The Hong Kong University of Science and Technology

May 7, 2026J/K move · Enter open · S save

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

Jianyu Xu, Yu-Xiang Wang

Carnegie Mellon University Pittsburgh, PA 15213

Contextual Bandits UCB Algorithms Dynamic Pricing

Open paper AskPDF arXiv

We study contextual dynamic pricing with linear valuations and bounded-support agnostic noise, whose induced demand curve may be non-Lipschitz with arbitrary jumps and atoms. Such discontinuities break the cross-context interpolation arguments used by smooth-demand pricing algorithms, while the best previous method achieved only

\tilde O(T^{3/4})

regret. We propose Conservative-Markdown Redirect-UCB Pricing, a polynomial-time algorithm that combines randomized parameter estimation, conservative residual-grid probing, and confidence-based one-step redirection. Our algorithm achieves

\tilde O(T^{2/3})

optimal regret, matching the known lower bounds of Kleinberg and Leighton (2003) up to logarithmic factors and improving over the previous upper bound of Xu and Wang (2022). Under stochastic well-conditioned contexts, this closes the long-existing open regret gap in linear-valuation contextual pricing under agnostic non-Lipschitz noise distribution.

Abstract

Explore similar work

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

Learning to Price and Stock Under Contextual and Censored Demand

Nonparametric Contextual Pricing and Inventory Learning under Censored Demand