Nonparametric Contextual Pricing and Inventory Learning under Censored Demand

N ONPARAMETRIC C ONTEXTUAL P RICING AND I N VENTORY L EARNING UNDER C ENSORED D EMAND Zean Han* Jing Liang* Ruihan Lin Zezhen Ding† Jiheng Zhang Department of Industrial Engineering and Decision Analytics The Hong Kong University of Science and Technology zhanax@connect.ust.hk jliangcd@connect.ust.hk zdingah@connect.ust.hk jiheng@ust.hk

rlinah@connect.ust.hk

arXiv:2608.30944v1 [cs.LG] 31 Aug 2026

A BSTRACT 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.

1

I NTRODUCTION

Online retailers must repeatedly decide how much to charge and how much inventory to make available, often while demand is still being learned. When a product sells out, the retailer typically sees only the units sold, not how many customers would have bought the product had inventory been available. The sales record is therefore incomplete precisely when demand is strongest. Moreover, inventory affects not only current revenue but also what the seller can learn for future decisions. This missing-demand problem is a familiar obstacle in lost-sales settings (Besbes & Muharremoglu, 2013; Chen et al., 2021; 2024). The problem becomes more realistic, and harder, when market conditions change. The same price may be attractive in one season, product category, or local market and unattractive in another. These market contexts arrive over time, and the seller cannot know in advance how customers in each context would respond to every possible price and inventory level. At the same time, the sales records available for learning are shaped by the seller’s own earlier stocking decisions: whenever inventory was too low, part of the demand was hidden. Prior work has addressed important parts of this problem. Censored pricing–inventory models have been studied when the seller repeatedly faces the same demand environment (Chen et al., 2021; 2024). Feature-based inventory models show how censored sales can guide stocking decisions (Ding et al., 2024). Recent contextual pricing–inventory studies also use rich market information, but often start from historical data available before the policy is deployed (Tang et al., 2025; Hu et al., 2026). The online case considered here is different: the seller must learn from the censored records produced by its own past price and inventory decisions. We study this problem in a nonparametric contextual setting, where demand may vary flexibly with both context and price. The seller cannot pool all past sales as if they came from the same market *

Equal contribution.

†

Corresponding author.

1

condition, but also cannot run a separate experiment to reveal the full demand curve at every context. This leads to the following central question: How can a seller learn a context-dependent pricing and stocking policy when demand is censored by inventory decisions and no parametric demand model is available? We answer this question through three contributions. 1. An observable learning signal under sales censoring. Sales-only feedback creates an identification problem: raw sales cannot be directly interpreted as either true demand or realized profit. We overcome this difficulty by constructing an observable learning signal from the sales record and end-of-period inventory. The signal uses stockouts and leftover inventory to guide stocking decisions, and uses the consistently visible part of sales as a reference for comparing prices. Intuitively, the seller need not recover the demand hidden by stockouts; it only needs the decision-relevant information that remains visible. 2. Context-aware learning with censored sales. Building on this observable signal, we develop the Mean-Calibrated Kernel UCB (MCK-UCB) algorithm for joint pricing and stocking. The algorithm pools observations only across nearby market contexts, profiles inventory where needed, and learns prices from the same censored sales collected while serving customers. This lets the seller adapt to changing market conditions without running a separate demand-revealing experiment for every context. 3. Minimax-optimal regret rates. We prove matching upper and lower  bounds  for the prod+2α e d+3α posed method. Under Lipschitz price values, the minimax regret is Θ T , while under  2d+3α  e T 2d+5α . These rates quantify the cost of contextual twice-smooth price values it becomes Θ variation: higher context dimension makes learning harder, while smoother variation across contexts allows faster information sharing.

2

P ROBLEM S ETUP

We now describe exactly what the seller knows and what remains hidden. Let X = [0, 1]d be the context space, let P = [pmin , pmax ] with pmin > 0 be the price range, and let A = P × [ymin , ymax ] be the set of price–inventory actions. The constants b ≥ 0 and hc ≥ 0 are the known per-unit lostsales and holding costs. A context can represent a customer, product, season, local market, or any other information available before the decision. Operational timing. Inventory yt is the quantity made available for the current selling period after observing xt . The formulation represents perishable stock or replenishment between periods: there is no leftover-inventory state and no constraint tying yt to the preceding period. The benchmark is therefore a contextual action applied repeatedly, rather than the state-dependent periodic-review benchmark in Chen et al. (2021). At period t, a context xt is drawn independently from a distribution µ. After observing xt , the seller chooses At = (pt , yt ) ∈ A. Potential demand is Dt = λ(xt , pt ) + ϵt , where λ : X × P → R is unknown and conditional on xt = x, ϵt has an unknown law Fx that does not depend on the chosen price. Given the context sequence, the noises are independent across periods and are fresh relative to past actions and observations. The seller observes only Ot = min{Dt , yt }. The one-period profit is r((p, y), D) = p min{D, y} − b(D − y)+ − hc (y − D)+ . The seller can compute the sales term and the stock level, but cannot compute the shortage term when demand exceeds inventory. This is the precise sense in which the reward is censored. It is useful to separate two kinds of information in the sales record. When Ot < yt , demand was low enough that the sale reveals the realized demand. When Ot = yt , the seller only learns that demand reached the stock level. The number of customers who would have bought the product is hidden, and so is the lost-sales part of the profit. Raising inventory can reveal more demand but may also create holding cost; lowering inventory limits holding cost but can hide exactly the observations needed for future pricing. The learner therefore has to use the inventory decision both as an operational choice and as a way of controlling what future data will reveal. 2

Context makes this feedback problem more realistic but also more delicate. Sales from one market condition cannot simply be pooled with sales from every other condition, because demand levels and residual variation may change with the context. At the same time, treating every context as unrelated would waste the repetition present in nearby customer, product, or seasonal states. The policy must borrow information locally while remembering that both the best price and the right inventory level move with the context. Define Qx (p, y) = E[r((p, y), D) | x, p], µx (p) = E[D | x, p], Gx (p) = maxy Qx (p, y), and Vx = maxp Gx (p). We take a measurable maximizer p∗x ∈ arg maxp Gx (p). The policy regret is " T # X RegT (π) = Eπ {Vxt − Qxt (pt , yt )} . t=1

For inventory profiling, define the stockout probability Sx (y | p) = P(D ≥ y | x, p) and the critical probability τ (p) = hc /(p + b + hc ). When the conditional demand law is continuous, ∂y Qx (p, y) = (p + b + hc ){Sx (y | p) − τ (p)}. Thus the stockout indicator gives an observable direction for inventory adjustment even though the full profit is censored. The location model implies µx (p) = E[D | x, p] = λ(x, p) under the conditional mean-zero normalization E[ϵt | xt = x] = 0. This equality is used only for analysis; the algorithm does not estimate λ from uncensored means. Structural assumptions. The assumptions support local information sharing, within-context price calibration, and inventory profiling from stockout events. Assumption 1 (Context distribution). The contexts x1 , . . . , xT are i.i.d. draws from an arbitrary distribution supported on [0, 1]d . No density or lower-mass condition is imposed. Assumption 2 (Contextual location surface). For some 0 < α ≤ 1 and finite Lx , Lp , |λ(x, p) − α λ(x′ , p)| ≤ Lx ∥x − x′ ∥ and |λ(x, p) − λ(x, q)| ≤ Lp |p − q|. The surface is uniformly bounded and keeps demand nonnegative almost surely. Assumption 3 (Context-conditioned shared noise and observable quantile). For every x ∈ X , the conditional noise law Fx is shared across all prices. It has mean zero, common compact support [z, z], continuous distribution function Fx , and density fx . For u ∈ (0, 1), write zu (x) = Fx−1 (u). Define p+b ϕ(p) = , zp (x) = zϕ(p) (x). p + b + hc There are a known ρ ∈ (0, inf p∈P ϕ(p)) and constants κ, K, mq , rq , LF > 0 such that the following hold uniformly in x, x′ . The density is bounded on its support and locally bounded away from zero around the calibration and critical quantiles: 0 ≤ fx (u) ≤ K,

fx (u) ≥ κ

if

|u − zρ (x)| ≤ rq or |u − zp (x)| ≤ rq for some p ∈ P.

The visible calibration quantile is separated from the critical quantile: zp (x) − zρ (x) ≥ mq

for all p ∈ P.

Finally, the noise family is Hölder in context in Kolmogorov distance: α

sup |Fx (u) − Fx′ (u)| ≤ LF ∥x − x′ ∥ . u∈R

Remark 1 (Role and scope of context-conditioned sharing). The seller is not required to face the same randomness in every context: Fx may differ from Fx′ . The key restriction is that, conditional on a context, changing the price shifts the demand location without changing the residual shape. This creates a common calibration reference across prices, but it does not cover an arbitrary family Fx,p . Remark 2 (No revealing cap). Compact support makes profit and regret bounded, but the support endpoint need not be known or feasible as inventory; in particular, we allow ymax < supx,p {λ(x, p) + z}. The algorithm uses neither this endpoint nor a demand-revealing action. 3

Assumption 4 (Inventory regularity and quantile visibility). For every x, p, the equation Sx (y | p) = τ (p) has a unique solution yx∗ (p) in the interior of the inventory interval. There are constants ry , cy , Cy > 0 such that cy |y − yx∗ (p)| ≤ |Sx (y | p) − τ (p)| ≤ Cy |y − yx∗ (p)| whenever |y − yx∗ (p)| ≤ ry . Moreover, Gx (p) − Qx (p, y) ≤ Cy |y − yx∗ (p)|2 on the same neighborhood. The visible-quantile condition requires ymin + ry ≤ qρ (x, p) := λ(x, p) + zρ (x) ≤ yx∗ (p) − mq ≤ ymax − ry . Assumption 5 (Price-value regularity). The optimized value is uniformly Lipschitz: |Gx (p) − Gx (q)| ≤ LG |p − q|. For the smooth-price specialization, we strengthen this condition to supx,p |∂pp Gx (p)| ≤ LG,2 . How to read these restrictions. The assumptions are meant to isolate the censoring issue rather than to make demand fully observable. Contexts may arrive from an uneven distribution, and some regions may be visited rarely. The learner is not promised a revealing inventory level that uncensors every demand realization. What is available is more modest: nearby contexts have related demand behavior, within a fixed context the residual shape is shared across prices, and a low quantile remains below the critical stocking level. These are exactly the ingredients needed to compare prices from sales records without reconstructing the whole demand distribution. This distinction matters for the interpretation of the model. The shared-noise condition is not saying that all contexts face the same demand shocks; the noise law may change with the context. It is saying that, once a context is fixed, changing the price shifts the demand location while preserving a common within-context reference. The visible-quantile condition then gives the algorithm a calibration mark that survives censoring. The rest of the paper uses these two facts to turn censored observations into a context-dependent price-learning signal. Knowledge boundary. The learner knows the horizon, context dimension, action ranges, cost parameters, smoothness exponent, visible quantile level, and kernel. It does not know the demand surface, the context-specific noise laws, the critical inventory levels, or the optimal prices. The fixed tuning convention and the technical consequences of the assumptions are stated in Sections B.1 and B.2. For ε > 0, let Γ(ε) denote the uniform price grid over P with mesh at most ε, including both endpoints.

3

M EAN -C ALIBRATED K ERNEL UCB

The construction has three moving pieces: an observable sales-based score, an inventory profiler that makes a low quantile visible, and a contextual UCB rule that compares calibrated prices. The next paragraphs define these pieces before Algorithm 1 records the full policy. Sales proxy and contextual calibration. The seller needs a score that can be computed from the sales record, even when the lost-sales penalty cannot be computed directly. We construct such a score in two steps. First, we choose the coefficient on leftover stock so that the observable score points toward the same inventory decision as true profit. For Zc (p, y, O) = pO − c(p)(y − O), matching the stockout and nonstockout inventory slopes gives c(p) = phc /(p + b). After normalization, the observable score is Y (p, y, O) = (p + b)O − hc (y − O). This score satisfies the sample-path identity Y (p, y, O) = r((p, y), D) + bD. Thus, with Qx (p, y) = E[Y (p, y, O) | x, p, y], we have Qx (p, y) = Qx (p, y) + bµx (p); the proxy preserves inventory maximizers and inventory regret gaps. Price comparison still needs one correction: defining Gx (p) = maxy Qx (p, y) and qρ (x, p) = λ(x, p) + zρ (x), the calibrated target satisfies Gx (p) − bqρ (x, p) = Gx (p) − bzρ (x). At a fixed context, the remaining offset is common to all prices. Formal statements are collected in Section B.2. The intuition is an accounting one. The observable score is not the profit; it differs from profit by bD, a demand term the seller does not observe in stockout periods. For inventory choice at a fixed 4

price and context, this extra term is harmless because it does not depend on the stock level. The same sales record can therefore tell the seller which way to move inventory without revealing the missing tail of demand. The difficulty is price comparison. A price that produces larger mean demand also produces a larger bµx (p) shift in the observable score, so optimizing the raw score can rank prices differently from optimizing profit. Calibration removes precisely this price-dependent shift. Once the profiler makes a lower demand quantile visible, subtracting bqρ (x, p) leaves only the common context term −bzρ (x). That common term can vary from one context to another, but within the same context it is shared by all prices, so it does not change the price ranking. Inventory profiling. Before comparing prices, the seller needs an inventory level that makes qρ (x, p) visible. The profiler searches for this level using only stockout indicators. Once the profiled inventory is safely above qρ (x, p), the lower ρ-quantile of sales equals the corresponding demand quantile. Let K : Rd → [0, 1] be a compactly supported Lipschitz kernel √ with K(u) = 0 for√∥u∥ > 1 and K(u) ≥ k0 > 0 for ∥u∥ ≤ 1/2. Set hprof := ε1/(2α) = h and Γprof := Γ( ε). Partition [0, 1]d into a deterministic collection {Czprof : z ∈ Zprof } of axis-aligned cells with diameter at most hprof . We use z for a representative point of Czprof . Then |Zprof | ≤ Ch−d prof . These profiler cells are deliberately coarser than the bandwidth-h cells used only in the kernel counting proof. The asynchronous policy and its profiling-action bound do not require a lower bound on the probability of any cell. Profiler implementation. For each profiler cell and anchor price a ∈ Γprof , the profiler maintains a bisection interval for the root of Sx (y | a) = τ (a). At a candidate stock level it asks whether a stockout occurred, and then moves the interval up or down. After a batch of observations it stops when the remaining inventory uncertainty is small enough to cause only O(ε) value loss. Profiling is asynchronous across cells: a context only advances the unfinished cell it actually belongs to, and a completed cell can immediately start using UCB. For a fine-grid decision price p, the policy reuses the profile at the nearest anchor instead of running a new inventory search. This is why the algorithm pays for inventory profiling on a coarse grid, while retaining a fine grid for price learning. The oneα round profiler update is given in Algorithm 2. √ The guarantee in Lemma 2 shows that, at ε = h , completed cells return inventories within O( ε) of the critical level, keep the inventory value loss e −d/2 ε−3/2 ) profiling rounds. at O(ε), make qρ (x, p) visible, and use only O(h Contextual UCB layer. Once a context cell has a safe inventory profile, the seller can return to price learning. The UCB layer combines two kernel estimates from the same sales history: one for the observable proxy and one for the visible quantile used to calibrate it. The raw proxy is not optimized directly because its price-dependent shift could favor the wrong price. Throughout the UCB concentration and counting analysis, write Γ := Γdec ; the profiler grid is always denoted separately by Γprof . Let Tt (p) be the UCB rounds before t on which price p was played. The kernel effective sample size, proxy estimate, weighted sales CDF, and empirical calibration quantile are X Wt (x, p) = K((xs − x)/h), s∈Tt (p)

P b (x, p) = G t Fbt (u | x, p) =

s∈Tt (p) K((xs − x)/h)Ys

, Wt (x, p) P s∈Tt (p) K((xs − x)/h)1{Os ≤ u}

Wt (x, p) qbρ,t (x, p) = inf{u ∈ [0, ymax ] : Fbt (u | x, p) ≥ ρ}.

,

The ratio-based estimates are used only when Wt (x, p) > 0. For Wt (x, p) > 0, the weighted empirical CDF is a right-continuous step function determined by finitely many observed triples. The displayed infimum is therefore a measurable statistic of the history. At zero weight the estimate 5

Algorithm 1 Mean-Calibrated Kernel UCB (MCK-UCB) Require: horizon T , context smoothness α, visible quantile level ρ, price mode s ∈ {Lip, smooth}, fixed tuning constants Ctune , hvis 1: Fix afb = (pmin , ymin ) and set δ = T −2 2: if s = Lip then 3: Set h = (log(eT )/T )1/(d+3α) , ε = hα , and ∆dec = ε 4: else √ 5: Set h = (log(eT )/T )2/(2d+5α) , ε = hα , and ∆dec = ε √ 6: Set Γdec = Γ(∆dec ), Γprof = Γ( ε), and hprof = ε1/(2α) ; construct Zprof with cell diameter at most hprof , and initialize the persistent anchor-profiler states in Algorithm 2 7: if h > hvis then 8: Play afb on all T rounds and stop 9: for round t = 1, . . . , T do 10: Observe context xt and let z = zprof (xt ) 11: if cell z is not profiled then 12: Execute the one-round update in Algorithm 2 and continue 13: Compute Ut (xt , p) = +∞ if Wt (xt , p) = 0, and otherwise use s log(T |Γdec |/h) b cal Ut (xt , p) = G + Ctune (ε + hα ) t (xt , p) + Ctune max{1, Wt (xt , p)} Choose pt ∈ arg maxp∈Γdec Ut (xt , p), let at = π(pt ) and yt = yez (at ), play (pt , yt ), and observe Ot 15: Append (xt , Ot , Yt ), where Yt = (pt + b)Ot − hc (yt − Ot ), to the history of pt 14:

is left undefined and the algorithm uses the infinite index directly. Define the corrected estimate b (x, p) − bb b cal (x, p) = G G qρ,t (x, p). t t

MCK-UCB implementation. For price mode s = Lip, the decision grid has spacing hα ; for s = smooth, it has spacing hα/2 . In both modes, the context bandwidth is√h, the target value accuracy is ε = hα , and inventory is profiled on the coarser resolution hprof = h. On every round, the policy first checks whether the arriving context belongs to an unfinished profiler cell. If so, that round advances the cell’s inventory search. Otherwise the policy computes a calibrated optimistic value for each decision price, chooses the largest one, and reuses the profiled inventory at the nearest anchor. It then stores the observed sale and proxy in that price’s history. Design choices. The policy is not a separate explore-then-exploit scheme. Each context cell keeps its own profiling state, and a cell switches to price learning as soon as its anchor inventories are certified. This matters when the context distribution is uneven: frequently visited cells should not wait for rare cells, while rare cells should not be forced into price learning before the sales quantile is visible. The two resolutions also serve different roles. Inventory is profiled on a coarser price grid because the profiler only needs to make the calibration quantile safely observable and keep inventory loss small. Price learning uses a finer decision grid because price comparison is the final optimization problem. Sharing inventory profiles from nearby anchors reduces the number of rounds spent on profiling without changing the calibrated target used by UCB. The startup fallback makes the policy well defined before the certified visibility resolution is available. Otherwise the policy never waits for global profiler completion: sparse cells remain in profiling mode, while completed cells accumulate UCB observations. The deterministic number of profiling −1 e −d/2 ε−3/2 ); all other rounds are UCB rounds. actions is of order O(|Γprof |h−d log2 T ) = O(h prof ε For all sufficiently large T , h ≤ hvis . The finitely many earlier horizons are covered by bounded regret and a larger theorem constant. Remark 3 (Concentration and counting). Once a context cell is profiled, the UCB rule behaves like a local price learning problem. The effective sample size is Wt (x, p), so the statistical uncertainty 6

decreases at the usual O(Wt (x, p)−1/2 ) scale. The remaining O(ε + hα ) terms come from price resolution and contextual smoothing. Summed along the realized trajectory, the local uncertainp ties contribute O( T |Γ|h−d ). The formal concentration and counting statements are collected in Section F.

4

M AIN R ESULTS

Let ILip denote the instance class satisfying Assumptions 1 to 5 with Lipschitz price values, and let Ism be its twice-smooth specialization. The formal upper and lower statements, including the fixed numerical envelopes and tuning constants, are given in Section B. Theorem 1 (Minimax rates for contextual censored sales). For fixed b, hc > 0, MCK-UCB achieves the minimax regret rate, up to logarithmic factors, in both price classes:    2d+3α  e T d+2α e T 2d+5α d+3α inf sup RegT (π; I) = Θ , inf sup RegT (π; I) = Θ . π I∈ILip

π I∈Ism

The rates quantify the cost of contextual variation. Larger d spreads observations across more local neighborhoods, while larger α allows stronger sharing across nearby contexts. The twice-smooth price class improves the exponent because a coarser price grid is enough to achieve the same approximation accuracy. Where the rates come from. The upper bound has three visible sources. First, the policy spends rounds profiling inventory in coarse context cells and at coarse price anchors. This is the cost of making the calibration quantile observable. Second, after a cell is profiled, the policy runs a contextual optimistic search over prices; nearby contexts share observations through the kernel, but the effective sample size is still local. Third, the continuous price interval is replaced by a finite grid, which creates approximation error. Suppressing logarithms and constants, the regret accounting has the form q h−d/2 ε−3/2 + T ε + T |Γ|h−d . Here h is the context bandwidth, ε = hα is the target value accuracy, and |Γ| is the number of decision prices. The first term is profiling, the second is local approximation and inventory error, and the third is the accumulated statistical uncertainty from contextual price learning. For Lipschitz price values, |Γ| ≍ ε−1 , and balancing the last two terms gives the exponent (d + 2α)/(d + 3α). When the optimized value is twice smooth in price, the grid can be coarser, |Γ| ≍ ε−1/2 , giving (2d + 3α)/(2d + 5α). The profiling term is designed to remain lower order at these choices. The matching lower bound says that these costs cannot all be avoided. Censored sales do not contain enough information to reveal the hidden tail for free, and context variation prevents all observations from being pooled into one global pricing problem. The theorem therefore reflects the intrinsic cost of learning from censored contextual demand, not only the design of MCK-UCB.

5

E XPERIMENTS

The experiments ask whether the main pieces of the theory behave as expected in finite samples. We instantiate the model with a controlled homoskedastic specification Fx ≡ Unif[−a, a], which isolates the effects of context dimension, Hölder smoothness, inventory profiling, and contextual pooling while preserving the within-context sharing structure used by the algorithm. Complete environment definitions, tuning parameters, baseline specifications, and additional diagnostics are given in Section C. We vary the horizon, context dimension, and contextual smoothness. For T ∈ {1000, 3000, 10000, 30000, 100000}, we run five independent repetitions for each pair (d, α) ∈ {(1, 0.5), (1, 0.75), (1, 1), (2, 0.5), (2, 0.75), (2, 1)}. Figure 1 reports mean cumulative regret with 95% confidence bands. The dashed reference in each panel is T β(d,α) log T , where β(d, α) = (d + 2α)/(d + 3α). 7

d = 1, = 1

MCK-UCB, fit = 0.885 T 0.769logT

MCK-UCB, fit = 0.893 T 0.750logT

103

Cumulative regret

d = 1, = 0.75 Cumulative regret

Cumulative regret

d = 1, = 0.5 MCK-UCB, fit = 0.886 T 0.800logT

103

103

102

102

102

104 Horizon T

105

103

104 Horizon T

105

104 Horizon T

d = 2, = 0.75

d = 2, = 1

MCK-UCB, fit = 0.832 T 0.824logT

MCK-UCB, fit = 0.824 T 0.800logT

Cumulative regret

d = 2, = 0.5 103 102

102

104

Horizon T

105

105

103

103

103

103

MCK-UCB, fit = 0.842 T 0.857logT

Cumulative regret

Cumulative regret

103

102

103

104

Horizon T

105

103

104 Horizon T

105

Figure 1: Cumulative-regret scaling of the paper-aligned MCK-UCB policy for different context dimensions d and Hölder exponents α. Solid curves are means over five exogenous trajectories, shaded regions are 95% confidence intervals, and dashed curves give representative T β(d,α) log T guides. The fitted log–log slopes, ordered by the panels, are 0.886, 0.885, 0.893, 0.842, 0.832, and 0.824. The corresponding pure-power exponents are 0.800, 0.769, 0.750, 0.857, 0.824, and 0.800. All six finite-sample fits are sublinear. The dashed guides should be read as a scaling diagnostic rather than an estimate of the asymptotic minimax exponent: the experiment is deliberately narrower than the theory, but it shows that the policy can learn from sales-only feedback in a context-dependent environment. Appendix C reports the context geometry, baseline comparisons, smoothness-mismatch diagnostic, and implementation details.

6

R ELATED W ORK

This paper sits at the intersection of four literatures: censored inventory learning, online pricing and inventory control, contextual bandits, and partial monitoring. Table 1 highlights the main distinction. Prior work typically has context without online joint pricing– inventory learning, or joint pricing–inventory learning without context. Our setting requires both: the same censored sale must guide inventory, price comparison, and local information sharing across market conditions. Censored pricing and inventory learning. Besbes & Muharremoglu (2013) show that sales-only feedback changes the exploration problem even when inventory is the only decision. The closest pricing–inventory papers are Chen et al. (2021) and Chen et al. (2024). They study nonparametric learning with lost sales and censored demand, but in a context-free setting. The former uses high-inventory exploration and spline estimation, while the latter estimates reward differences from censored data and uses structured search. We retain their useful within-context location-modeling convention, but add contextual pooling and a decision-equivalent calibration target. Ding et al. (2024) study feature-based inventory control with censored demand and construct an inventory-oriented stochastic subgradient. Our setting also needs the same censored sale to support price comparison, which creates the price-calibration step. 8

Table 1: Setting comparison with closely related work. Work

Context

Decisions

Feedback and deployment

Besbes & Muharremoglu (2013) Chen et al. (2021; 2024)

No context

Inventory only

No context

Price and inventory Inventory only

Online lost-sales feedback; no price decision. Online sales-only feedback; nonparametric but context-free. Online censored-demand inventory control; no price calibration. Historical data are available before deployment, rather than collected only online. Abstract censored-feedback models, not lost-sales profit with an endogenous inventory threshold. Online sales-only feedback; learns by locally calibrating censored sales.

Ding et al. (2024)

Features or context Tang et al. (2025); Hu et al. Features or (2026) context

Pricing or pricing–inventory

Abernethy et al. (2016); Verma et al. (2019)

Model dependent

Threshold or resource actions

This paper

Nonparametric Price and context inventory

Contextual and offline pricing–inventory learning. Tang et al. (2025) study feature-based pricing with finite inventory and censored demand using an offline data set of historical features, prices, inventory, and sales. Hu et al. (2026) study contextual joint pricing and inventory control from historical data using a conditional generative model. These works use rich context information but study historical data available before policy deployment. Gundem & Qi (2025) also studies offline sequential pricing and inventory with censored, dependent demand. Partial monitoring and contextual bandits. Abernethy et al. (2016) analyze threshold bandits in which feedback is revealed only on one side of a threshold, and Verma et al. (2019) study censored semi-bandits for resource allocation. The nonparametric contextual bandit literature studies how nearby contexts can share information (Rigollet & Zeevi, 2010; Perchet & Rigollet, 2013; Qian & Yang, 2016; Guan & Jiang, 2018; Reeve et al., 2018), while Krishnamurthy et al. (2020); Gur et al. (2022) consider continuous actions and smoothness. These papers generally assume that an unbiased reward or loss is available after the action. Here the inventory threshold is endogenous, the reward is a continuous lost-sales profit, and neither the reward nor its gradient is observed. Contextual dynamic pricing. Qiang & Bayati (2016) and Wang et al. (2025) study pricing with observed covariates under parametric or partially specified demand models. Wang et al. (2021) study nonparametric continuous-action pricing when the observed-reward function may be multimodal. These papers clarify the value of contextual information and of avoiding global concavity, but they do not jointly model an endogenous inventory level that censors the reward. Our contribution is the interaction of these ingredients, together with matching upper and lower bounds under the stated shared-noise subclass.

7

C ONCLUSION

We studied a seller who must make two decisions at once: how much to charge and how much to stock. The seller sees the context and the resulting sales, but not the demand that was turned away. We showed that, under a nonparametric contextual location model, the visible part of censored sales can still support joint pricing and stocking. MCK-UCB combines inventory profiling, local contextual pooling, and calibrated price learning, and achieves matching minimax rates for the stated Lipschitz and twice-smooth price classes. The result remains a per-period model without inventory carryover or lead times, and the sharednoise location structure does not cover arbitrary price-dependent noise distributions. Extensions to dynamic inventory states, weaker feedback, or a more general conditional demand law are natural directions for future work.

9

R EFERENCES Jacob D. Abernethy, Kareem Amin, and Ruihao Zhu. Threshold bandits, with and without censored feedback. In Advances in Neural Information Processing Systems, volume 29, pp. 4889–4897, 2016. Omar Besbes and Alp Muharremoglu. On implications of demand censoring in the newsvendor problem. Management Science, 59(6):1407–1424, 2013. doi: 10.1287/mnsc.1120.1654. Boxiao Chen, Xiuli Chao, and Cong Shi. Nonparametric learning algorithms for joint pricing and inventory control with lost sales and censored demand. Mathematics of Operations Research, 46 (2):726–756, 2021. doi: 10.1287/moor.2020.1084. Boxiao Chen, Yining Wang, and Yuan Zhou. Optimal policies for dynamic pricing and inventory control with nonparametric censored demands. Management Science, 70(5):3362–3380, 2024. Jingying Ding, Woonghee Tim Huh, and Ying Rong. Feature-based inventory control with censored demand. Manufacturing & Service Operations Management, 26(3):1157–1172, 2024. doi: 10. 1287/msom.2021.0135. Melody Y. Guan and Heinrich Jiang. Nonparametric stochastic contextual bandits. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pp. 3119–3125, 2018. doi: 10. 1609/aaai.v32i1.11749. Korel Gundem and Zhengling Qi. Offline dynamic inventory and pricing strategy: Addressing censored and dependent demand. arXiv preprint arXiv:2504.09831, 2025. Yonatan Gur, Ahmadreza Momeni, and Stefan Wager. Smoothness-adaptive contextual bandits. Operations Research, 70(6):3198–3216, 2022. doi: 10.1287/opre.2021.2215. Xiangbin Hu, Xianghua Jiang, Zhisheng Ye, and Xun Zhang. Conditional generative learning for joint pricing and inventory control. Working paper, minor revision at Manufacturing & Service Operations Management, 2026. Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Journal of Machine Learning Research, 21(137):1–45, 2020. Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693–721, 2013. doi: 10.1214/13-AOS1101. Wei Qian and Yuhong Yang. Kernel estimation and model combination in a bandit problem with covariates. Journal of Machine Learning Research, 17(149):1–37, 2016. Sheng Qiang and Mohsen Bayati. arXiv:1604.07463, 2016.

Dynamic pricing with demand covariates.

arXiv preprint

Henry Reeve, Joseph Mellor, and Gavin Brown. The k-nearest neighbour ucb algorithm for multiarmed bandits with covariates. In Proceedings of Algorithmic Learning Theory, pp. 725–752, 2018. Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. In Proceedings of the 23rd Annual Conference on Learning Theory, pp. 54–66, 2010. Jingwen Tang, Zhengling Qi, Ethan Fang, and Cong Shi. Offline feature-based pricing under censored demand: A causal inference approach. Manufacturing & Service Operations Management, 27(2):535–553, 2025. doi: 10.1287/msom.2024.1061. Arun Verma, Manjesh K. Hanawal, Arun Rajkumar, and Raman Sankaran. Censored semi-bandits: A framework for resource allocation with censored feedback. In Advances in Neural Information Processing Systems, volume 32, 2019. Hanzhao Wang, Kalyan Talluri, and Xiaocheng Li. Technical note: On dynamic pricing with covariates. Operations Research, 73(4):1932–1943, 2025. Yining Wang, Boxiao Chen, and David Simchi-Levi. Multi-modal dynamic pricing. Management Science, 67(10):6136–6152, 2021. 10

A

A LGORITHM L ISTINGS

Algorithm 2 One-Round Two-Resolution Inventory Profiler Update Require: horizon T , coarse profiler partition Zprof , current context xt , its cell z = zprof (xt ), persistent profiler state for z, value accuracy ε, anchor grid Γprof , confidence level δ, fixed tuning constant Ctune √ 1: At initialization, set η = ε and      ymax − ymin By = 1 + log2 1 + , my = Ctune η −2 log(T |Γprof ||Zprof |By /δ) Ctune η 2: At initialization, for every (z, a) ∈ Zprof × Γprof , initialize [Lz,a , Uz,a ] = [ymin , ymax ] 3: Select the next unfinished anchor a in the round-robin schedule of cell z 4: Set pt = a and yt = (Lz,a + Uz,a )/2, play (pt , yt ), observe Ot , and append It = 1{Ot ≥ yt }

to the current batch of (z, a) 5: if the current batch contains my indicators then

Let Sb be their average if Sb > τ (a) + 2η then Set Lz,a = yt 9: else if Sb < τ (a) − 2η then 10: Set Uz,a = yt 11: else 12: Mark (z, a) finished and set yez (a) = yt 13: if (z, a) is unfinished and Uz,a − Lz,a ≤ Ctune η then 14: Mark (z, a) finished and set yez (a) = (Lz,a + Uz,a )/2 15: Clear the completed batch 16: if all (z, a′ ), a′ ∈ Γprof , are finished then 17: Mark cell z profiled and define yex (p) = yez (π(p)) for x ∈ Czprof , p ∈ Γdec , where π(p) ∈ arg mina∈Γprof |p − a| 6: 7: 8:

B

F ORMAL S TATEMENTS AND T UNING

B.1

T UNING C ONVENTION

The learner knows the horizon, context dimension, action ranges, cost parameters, smoothness exponent, visible quantile level, and kernel. It does not know the demand surface, the contextspecific noise laws, the critical inventory levels, or the optimal prices. Fix numerical constants Ctune , hvis > 0. The analysis is stated for fixed choices that dominate the constants needed in batch sizes and confidence radii, including −1 −1 −1 Lx , Lp , LF , Lloc , K, Cy , Ymax , Rmax , c−1 , ry , rq , m−1 y ,κ q and fixed action/kernel constants. The visibility condition requires, for every h ≤ hvis , √ Ctune ( hα + hα ) ≤ min{ry , rq /2, mq /2}, (Lx + LF /κ)hα ≤ min{mq /8, rq /4}, √ Ctune hα ≤ 14 hα . where Ymax and Rmax are certified bounds on proxy magnitude and one-period regret. Any fixed admissible choices change only multiplicative constants and finite-horizon transients, not the regret exponent. The latent functions, quantiles, and optimizers remain unknown and are never policy inputs. B.2

AUXILIARY S TATEMENTS

Proposition 1 (Location-model separation). Under Assumptions 2 to 4, yx∗ (p) = λ(x, p) + zp (x) 11

and Gx (p) = pλ(x, p) + Cx (p), where Cx (p) = pEFx [min{ϵ, zp (x)}] − bEFx [(ϵ − zp (x))+ ] − hc EFx [(zp (x) − ϵ)+ ]. Moreover, there is a fixed Lloc < ∞ such that, uniformly in p, each of yx∗ (p), qρ (x, p), Gx (p), and α Gx (p) changes by at most Lloc ∥x − x′ ∥ between contexts x, x′ . Proposition 2 (Uniform price discretization). Under Assumption 5, |Γ(ε)| ≤ 2 + and

pmax − pmin ε

  sup max Gx (p) − max Gx (q) ≤ LG ε. x

p∈P

q∈Γ(ε)

√ Under the smooth-price specialization, the grid Γ( ε) has cardinality O(ε−1/2 ) and approximation error O(ε). Proposition 3 (Exact proxy identity). For every demand realization, Y (p, y, O) = r((p, y), D) + bD. Consequently, with Qx (p, y) = E[Y (p, y, O) | x, p, y], one has Qx (p, y) = Qx (p, y) + bµx (p). In particular, arg maxy Qx (p, y) = arg maxy Qx (p, y), Gx (p) := maxy Qx (p, y) = Gx (p) + bµx (p), and Gx (p) − Qx (p, y) = Gx (p) − Qx (p, y). Lemma 1 (Mean calibration up to a within-context common shift). Under Assumptions 2 and 3, define qρ (x, p) = λ(x, p) + zρ (x). Then Gx (p) − bqρ (x, p) = Gx (p) − bzρ (x). For a fixed x, the rightmost offset is independent of p and y. Hence an upper confidence bound for the left-hand side orders prices exactly as an upper confidence bound for Gx (p). Lemma 2 (Two-resolution asynchronous profiling guarantee). Under Assumptions 1 to 4, take ε = hα . Let Nprof (T ) be the number of rounds up to horizon T on which the asynchronous policy performs a profiling update. Deterministically, ! −d CT |Γ |h prof prof −1 Nprof (T ) ≤ C|Γprof |h−d log2 prof ε δ and, with probability at least 1−δ, every completed cell has returned estimates satisfying, uniformly in p ∈ Γdec and x in that cell, √ |e yx (p) − yx∗ (p)| ≤ C ε and Gx (p) − Qx (p, yex (p)) = Gx (p) − Qx (p, yex (p)) ≤ Cε. Under the certified resolution h ≤ hvis , yex (p) ≥ qρ (x, p) + mq /2, so the ρ-quantile of min{D, yex (p)} equals qρ (x, p). No completion guarantee for cells that have −d/2 not received enough arrivals is needed. Since |Γprof | = O(ε−1/2 ) and h−d , prof = h   e h−d/2 ε−3/2 . Nprof (T ) ≤ O B.3

U PPER AND L OWER B OUNDS

Theorem 2 (Lipschitz-price contextual upper bound). Under Assumptions 1 to 5, with s = Lip, and with the certified tuning inputs in Section B.1, MCK-UCB satisfies d+2α

RegT ≤ CT d+3α polylog(T ). 12

Corollary 1 (Twice-smooth price upper bound). Under the smooth-price specialization in Assumption 5, invoke MCK-UCB with √ s = smooth, using the same fixed tuning constants and fallback rules. Its price mesh is ∆p = ε, with h = (log(eT )/T )2/(2d+5α) , Then

ε = hα .

2d+3α

RegT ≤ CT 2d+5α polylog(T ). Theorem 3 (Context-conditioned shared-noise lower bounds). Assume b > 0 and hc > 0, and let 0 < α ≤ 1. There exist fixed nondegenerate compact price and inventory ranges and a contextconditioned shared-noise location subclass satisfying Assumptions 1 to 5 such that every policy obeys, under Lipschitz price regularity, d+2α

sup RegT (π; I) ≥ cT d+3α . I

Under the twice-smooth price specialization, the lower bound is 2d+3α

cT 2d+5α . Corollary 2 (Context-conditioned shared-noise minimax rates). Fix common numerical envelopes for all constants in Assumptions 1 to 5 and the fixed tuning constants, as well as fixed action ranges containing the subclass in Theorem 3. Let ILip be the resulting context-conditioned shared-noise class with Lipschitz price values, and let Ism be its twice-smooth specialization. For fixed b, hc > 0, the upper and lower bounds yield  d+2α  e T d+3α . inf sup RegT (π; I) = Θ π I∈ILip

Under twice-smooth price values the corresponding rate is   e T 2d+3α 2d+5α inf sup RegT (π; I) = Θ . π I∈Ism

C

E XPERIMENTAL D ETAILS

Experimental environment and feedback. All experiments use p ∈ [0.1, 1], y ∈ [0, 2.2], shortage cost b = 0.4, holding cost hc = 1, and visible quantile level ρ = 0.2. Contexts are i.i.d. uniform on [0, 1]d and Ot = min{Dt , yt },

Dt = λ(xt , pt ) + ϵt ,

where we specify the context-conditioned residual family as Fx ≡ Unif[−a, a] for every x. Thus the residual law is the same across prices at each context and, in this controlled design, also does not vary with context. The learner receives only Ot and updates the observable proxy Yt = (pt + b)Ot − hc (yt − Ot ). For the scaling and mismatch experiments, a = 0.5. The constant residual family has Hölder modulus zero, so the environmental exponent α0 is introduced through the location surface. To make this smoothness explicit, define the centered cusp ψc,α0 (u) = |u − c|α0 −

cα0 +1 + (1 − c)α0 +1 . α0 + 1

For d = 1, the location surface is λα0 (x, p) = 1.55 − 0.58ψ0.35,α0 (x) + 0.22ψ0.78,α0 (x) − 0.42p + 0.16pψ0.62,α0 (x). For d = 2, it is 13

λα0 (x, p) = 1.55 − 0.42ψ0.32,α0 (x1 ) + 0.28ψ0.79,α0 (x1 ) − 0.36ψ0.41,α0 (x2 ) + 0.24ψ0.73,α0 (x2 ) − 0.42p + 0.10pψ0.61,α0 (x1 ) − 0.08pψ0.27,α0 (x2 ). Each surface is α0 -Hölder and contains an α0 -order cusp, so changing α0 changes the environment rather than only the algorithmic bandwidth. The two-dimensional baseline comparison uses a = 0.1 and the instance

w(x) = 0.58 + 0.40 sin(2πx1 ) + 0.07 sin(2πx2 ), m(x) = 1.42 + 0.14 cos(2πx2 ) + 0.08 sin(2π(x1 + x2 )), m(x) λ(x, p) = 0.10 + . 1 + exp(10(p − w(x))) Paper-aligned MCK-UCB implementation. At declared horizon T ,  h=

log(eT ) T

1/(d+3α) ,

We use the Lipschitz-price mode of Algorithm 1.

ε = hα ,

hprof = ε1/(2α) .

√ The decision-price mesh is ε, the profiler-anchor mesh is ε, and a decision price uses the completed inventory estimate of its nearest anchor. Profiler cells have diameter at most hprof . Within every unfinished cell, anchors are visited round-robin; each midpoint threshold is held fixed for a batch of   my = Ctune ε−1 log(T |Γprof ||Zprof |By /T −2 ) √ observations and is compared with τ (p) ± 2 ε. Completed cells switch immediately to calibrated kernel UCB, while unfinished cells continue profiling on their own arrivals. Only UCB rounds enter the price-specific proxy and sales-quantile histories. We set Ctune = 0.1 and hvis = 1 before running any simulation and do not select either value by seed, horizon, environment, or observed reward. Ctune is a fixed scale factor in batch lengths and confidence radii; fixed admissible choices affect multiplicative constants and finite-sample transients but not the regret exponent. The value hvis is only a technical startup cutoff. Every experimental bandwidth satisfies h ≤ 1, so this cutoff never changes an action in the reported experiments. The scaling grid contains T ∈ {1000, 3000, 10000, 30000, 100000} and five repetitions for each of (d, α) ∈ {(1, 0.5), (1, 0.75), (1, 1), (2, 0.5), (2, 0.75), (2, 1)}. The top row of Fig. 1 fixes d = 1 and the bottom row fixes d = 2. In this experiment the algorithm input equals the environmental smoothness, α b = α0 = α. Smoothness-mismatch diagnostic. We separately fix T = 8000 and cross α0 ∈ {0.5, 0.75, 1} in the cusp environment with the algorithm input α b ∈ {0.5, 0.75, 1}. Each cell uses six repetitions. For fixed (d, α0 , r), all three values of α b receive the same pre-generated context and residual-shock arrays. Figure 4 shows that α b = 1 has the lowest mean regret for every tested (d, α0 ), including the two rough α0 = 0.5 environments. Thus matching α b to α0 is not empirically necessary on this benchmark. This is a finite-sample robustness diagnostic, not a general smoothness-adaptation guarantee. Common random numbers and baselines. Our benchmark comparison is designed to isolate the online feedback contribution. The closest available online methods handle joint inventory and pricing with censored demand in the noncontextual setting: the CWZ trisection method of Chen 14

(a) Optimal reward surface

(b) Context-optimal price

1.0

0.85 0.75 0.65 0.55 0.45 0.35 0.25 0.15

0.8

1.00 1.00 0.75 0.75 0.50 0.25 0.50 0.25 1.00 0.75 0.000.25 0.50 0.50 0.25 x 2 x1 0.751.00 0.00

p * (x)

x2

Gx*

0.6 0.4 0.2 0.0 0.0

0.2

0.4

x1

0.6

0.8

1.0

Figure 2: Geometry of the two-dimensional instance used in the baseline comparison. Left: optimized reward G∗x = maxp Gx (p). Right: context-optimal price p∗ (x). The substantial price variation makes context information decision relevant.

5000 4000 3000 2000 1000 0

(b) Per-round decay

MCK-UCB CWZ SALA

0

2000

Average regret Rt/t

Cumulative regret

(a) Two-dimensional comparison

4000 6000 Round t

8000

MCK-UCB CWZ SALA

1.4 1.2 1.0 0.8 0.6 0.4 0

2000

4000 6000 Round t

8000

Figure 3: Two-dimensional comparison with neighboring online joint pricing–inventory methods under common exogenous context and residual-shock trajectories. Curves are means over eight repetitions and shaded regions are 95% confidence intervals. CWZ and SALA are noncontextual prior-work baselines and pool away the context, whereas MCK-UCB uses contextual kernel estimates. et al. (2024) and a SALA-style implementation based on Chen et al. (2021). They provide relevant pricing–inventory benchmarks rather than model-identical competitors; both implementations pool away the context, whereas MCK-UCB uses contextual kernel estimates. Recent feature-based censored-pricing work is offline and is therefore not a drop-in online baseline for the present experiment. Before any policy starts, each seed generates a complete context array and a complete residual-shock array from two independent child random streams. MCK-UCB, CWZ, and SALA receive the same pair (xt , ϵt ) on every calendar round, so their actions cannot change later contexts or shocks. The two-dimensional comparison uses T = 8000 and eight repetitions. The CWZ implementation uses minimum epoch size 8, sample scale 0.006, and final exploitation fraction 0.35. The SALA-style implementation explores seven prices, uses exploration scale 1.1, estimates a pooled demand curve and residual distribution, and then exploits one price-inventory pair. Both baselines deliberately ignore the context. We use a two-dimensional instance in which the context changes both willingness to pay and market size. At T = 8000, over eight repetitions, the mean cumulative regrets of MCK-UCB, CWZ, and SALA are 2570.1, 4957.7, and 5482.1, respectively. 15

Cumulative regret

true 0 = 0.5 true 0 = 0.75 true 0 = 1

480 460 440

Cumulative regret

(a) d = 1 500

420 0.50

0.75 Algorithm input

1.00

(b) d = 2

720 700 680 660 640 620 600

true 0 = 0.5 true 0 = 0.75 true 0 = 1

0.50

0.75 Algorithm input

1.00

Figure 4: Sensitivity to smoothness mismatch at T = 8000. Each curve fixes the true cusp exponent α0 and varies the algorithm input α b; points are means over six common-random-number repetitions and error bars are 95% confidence intervals. Left: d = 1. Right: d = 2. For reproducibility, the scaling seed (d, α0 , T, r) and the mismatch seed (d, α0 , T, r) are both 20260824 + 7919d + 1000α0 + 9176T + 1009r, independently of α b in the mismatch experiment. The comparison seed (T, r) is 20260824+9176T + 1009r. The regret benchmark maximizes Gx (p) on an 801-point price grid over [0.1, 1]. One-round regret is the expected-value gap G∗xt − Qxt (pt , yt ), not realized-profit noise or price distance. Reported curves are means across repetitions; shaded bands are mean plus or minus 1.96 standard errors.

16

D

P ROOF ROADMAP AND C OMMON N OTATION

The main text carries the intuition; this appendix records the technical reasons the intuition is correct. The proofs separate identification, estimation, regret accounting, and hardness. This separation is useful because the learner never observes the true reward. Define the calibrated value Hx (p) := Gx (p) − bqρ (x, p) = Gx (p) − bzρ (x). The first equality identifies a target that can be estimated from sales, and the second shows that its maximizers are exactly those of Gx . The upper-bound proof then follows the same story as the main text: first make inventory safe, then calibrate the proxy, then use contextual optimism. The formal dependency chain is: 1. Proposition 3 and Lemma 1 establish that a censored observation supplies a bounded proxy sample and a visible quantile correction for Hx (p). √ 2. Lemma 2 profiles only coarse context cells and ε-spaced price anchors, then transfers the √ nearest anchor estimate to each decision price. The resulting inventory is within O( ε) of the critical inventory. Its value loss is O(ε), and its positive separation above qρ (x, p) makes the calibration quantile uncensored. 3. Lemmas 3 and 4 give a simultaneous confidence interval for Hx (p) under adaptive price choices. The radius contains a stochastic term Wt (x, p)−1/2 and the two bias terms ε and hα . 4. Lemma 5 sums the stochastic radii. Price discretization and profiling supply the remaining deterministic regret terms, producing the three-term decomposition used in Theorem 2 and Corollary 1. For the lower bound, we restrict to the admissible subfamily Fx ≡ F0 , and that noise law is even revealed to the learner. A value bump g(x, p) is implemented by the location shift g(x, p)/p; Lemma 7 verifies that these shifts remain inside the model class. The square-root density of the fixed noise law has finite translation energy, so a location shift of size O(∆) contributes only O(∆2 ) squared Hellinger information. The complete proof in Section I averages this information over disjoint price supports inside every context cell and then applies a product prior over cell labels. This is the direct-sum step responsible for the factor h−d . The common compact support of ϵ, boundedness of λ, and compact action sets imply constants Ymax , Rmax < ∞ such that |Yt | ≤ Ymax and one-round regret is at most Rmax on every instance considered below. Constants denoted by C, c may change from line to line and depend only on the fixed model constants, never on T, h, ε, or the packing labels.

E

P ROOFS FOR THE P ROXY AND P ROFILING R ESULTS

Proof of Proposition 1. Fix x, p, abbreviate λ = λ(x, p), and write y = λ + z. By Assumption 4, the optimizer is the unique interior solution of the inventory first-order condition. Using Section 2, this condition is   hc . 0 = ∂y Qx (p, y) = (p + b + hc ) P(ϵ ≥ z) − p + b + hc Since Fx is continuous and 1 − hc /(p + b + hc ) = ϕ(p), its unique solution is z = Fx−1 (ϕ(p)) = zp (x). Hence yx∗ (p) = λ(x, p) + zp (x). At this inventory, the following identities hold sample by sample: min{λ(x, p) + ϵ, λ(x, p) + zp (x)} = λ(x, p) + min{ϵ, zp (x)}, (λ(x, p) + ϵ − λ(x, p) − zp (x))+ = (ϵ − zp (x))+ , (λ(x, p) + zp (x) − λ(x, p) − ϵ)+ = (zp (x) − ϵ)+ . Substitution into the definition of Qx gives Gx (p) = pλ(x, p) + pEFx [min{ϵ, zp (x)}] − bEFx [(ϵ − zp (x))+ ] − hc EFx [(zp (x) − ϵ)+ ] = pλ(x, p) + Cx (p). 17

It remains to prove the asserted context regularity. Put dxx′ = ∥x − x′ ∥. For u ∈ {ρ} ∪ {ϕ(p) : p ∈ P}, put δxx′ = LF dα xx′ . When δxx′ < κrq , the two quantiles must be within rq : were, say, zu (x′ ) > zu (x) + rq , integrating fx ≥ κ from zu (x) to zu (x) + rq would give Fx′ (zu (x) + rq ) ≥ Fx (zu (x) + rq ) − δxx′ > u, contradicting the definition of zu (x′ ). Inside that neighborhood, the same integration argument gives κ|zu (x) − zu (x′ )| ≤ δxx′ . When δxx′ ≥ κrq , compact support gives |zu (x) − zu (x′ )| ≤ z − z ≤

(z − z)LF α dxx′ . κrq

Thus both zρ (x) and zp (x) are uniformly Hölder in x, and the same is true of qρ (x, p) and yx∗ (p) after adding the location bound from Assumption 2. For completeness, let Px,p denote the law of λ(x, p) + ϵ. In one dimension, W1 (Px,p , Px′ ,p ) ≤ |λ(x, p) − λ(x′ , p)| + W1 (Fx , Fx′ ) ≤ {Lx + (z − z)LF }dα xx′ , R where the last step uses W1 (Fx , Fx′ ) = R |Fx (u) − Fx′ (u)| du. For fixed (p, y), the profit is Lipschitz in demand with constant at most Lr := max{pmax + hc , b}. The Kantorovich–Rubinstein inequality therefore bounds |Qx (p, y) − Qx′ (p, y)| by a constant times dα xx′ , uniformly in y. Taking maxima over the common inventory interval proves the same bound for Gx (p). Finally, Gx (p) = Gx (p) + bλ(x, p), so Gx (p) is Hölder as well. Choosing one constant that dominates these four bounds proves the last claim. Proof of Proposition 2. The displayed cardinality bound follows directly from the construction of Γ(ε). A maximizer p∗x has a grid point within distance ε; the Lipschitz bound then gives Gx (p∗x ) − max Gx (q) ≤ LG ε. q∈Γ(ε)

Under the bounded-second-derivative condition, Taylor’s theorem around an interior maximizer gives a loss at most 21 LG,2 |p − p∗x |2 . The same order follows at a boundary maximizer because both endpoints themselves belong to the grid, and hence the discretization loss is then zero. A grid √ of mesh ε therefore incurs O(ε) loss and contains O(ε−1/2 ) points. Proof of Proposition 3. The elementary identity D = min{D, y} + (D − y)+ gives r((p, y), D) + bD = pO − b(D − y)+ − hc (y − D)+ + b{O + (D − y)+ } = (p + b)O − hc (y − O), because y − O = (y − D)+ . This is exactly Y (p, y, O). Taking conditional expectations proves Qx (p, y) = Qx (p, y) + bµx (p). The added term is independent of y, so maximizers and inventory gaps agree. Proof of Lemma 1. Mean-zero noise gives µx (p) = λ(x, p), while the location family gives qρ (x, p) = λ(x, p) + zρ (x). Substitute both identities into Gx (p) = Gx (p) + bµx (p). √ Proof of Lemma 2. Put η = ε and hprof = ε1/(2α) . We first construct a single event on which every anchor-price bisection decision is correct. Fix a profiler cell Czprof with positive context probability and an anchor a ∈ Γprof . Define its conditional-average stockout curve S z (y | a) := E[Sxt (y | a) | xt ∈ Czprof ]. 18

Cells of zero probability receive no arrivals and contribute no profiling rounds. Every individual root in the cell equals yx∗ (a) = λ(x, a) + za , and therefore sup x,x′ ∈Czprof

|yx∗ (a) − yx∗′ (a)| ≤ Lloc hα prof = Lloc η.

Continuity and monotonicity place a root y ∗z (a) of S z (· | a) = τ (a) between the smallest and largest individual roots. Consequently sup |y ∗z (a) − yx∗ (a)| ≤ Lloc η.

x∈Czprof

The visibility condition keeps this entire root interval inside the region where every conditional density is bounded below. Hence the averaged curve is strictly decreasing there with slope magnitude at least a fixed multiple of κ, so the displayed root is unique in the relevant neighborhood. The within-cell scheduler depends on the cell index and the past, but not on the exact location of the current context inside the cell. Conditional on an arrival to the cell, the context therefore retains the fixed conditional law used in S z . During a fixed threshold batch, each stockout indicator is a bounded martingale difference after subtracting S z (y | a). Hoeffding’s inequality gives stochastic error at most η from   |Γprof ||Zprof |By −2 my ≥ Cη log δ samples, where    ymax − ymin By := 1 + log2 max 1, Ctune η bounds the number of thresholds queried by one bisection. Taking the union bound over the at most |Γprof ||Zprof |By adaptive batches yields an event Ebis of probability at least 1 − δ/2 on which |Sb − S z (y | a)| ≤ η for every queried batch. The union bound is valid for adaptive thresholds because the conditional tail bound holds at every batch given its starting history. We next verify the bisection invariant. Initially y ∗z (a) ∈ [Lz,a , Uz,a ]. The averaged stockout curve is nonincreasing. On Ebis , Sb > τ (a) + 2η implies S z (y | a) > τ (a) + η, hence y < y ∗z (a) and replacing the lower endpoint by y preserves the invariant. The symmetric statement holds when Sb < τ (a) − 2η. In the remaining case, |S z (y | a) − τ (a)| ≤ 3η. The startup check h ≤ hvis and the definition of Ctune keep the relevant neighborhood inside the density-lower-bound region. The averaged-curve slope bound therefore gives |y − y ∗z (a)| ≤ Cη. Outside that neighborhood monotonicity gives a fixed stockout gap, so the ambiguous branch cannot terminate there once h ≤ hvis . A width-based termination also has error at most half the final bracket width. Consequently every cell–anchor output satisfies |e yz (a) − y ∗z (a)| ≤ Cη. We now transfer the anchor estimate to a decision price p ∈ Γdec . Since ϕ has bounded derivative and fx ≥ κ along the quantile curve {zq (x) : q ∈ P}, κ|zp (x) − za (x)| ≤ |Fx (zp (x)) − Fx (za (x))| = |ϕ(p) − ϕ(a)| ≤ C|p − a|. Here the first inequality follows by integrating the density between the two quantiles; every intermediate quantile is zq (x) for a price between p and a. Thus p 7→ zp (x) is uniformly √ Lipschitz under the context-conditioned shared-noise assumption. With a = π(p), |p − a| ≤ ε. Since Proposition 1 gives yx∗ (p) = λ(x, p) + zp (x), for x ∈ Czprof , |e yz (a) − yx∗ (p)| ≤ |e yz (a) − y ∗z (a)| + |y ∗z (a) − yx∗ (a)| + |λ(x, a) − λ(x, p)| + |za (x) − zp (x)| √ ≤ C{ ε + hα prof + |p − a|} √ ≤ C ε. 19

It remains to count the rounds that actually perform profiling. Each cell–anchor pair uses at most By batches, and each batch uses my arrivals assigned to that cell. Hence every cell uses at most   T |Γprof ||Zprof | Rprof ≤ C|Γprof |ε−1 log(1/ε) log δ profiling actions. Since |Zprof | ≤ Ch−d prof , summing this deterministic cap over cells gives, for every arrival realization and every horizon, ! CT |Γprof |h−d prof 2 −d −1 . Nprof (T ) ≤ C|Γprof |hprof ε log δ An unfinished cell cannot create waiting loss elsewhere: each arrival to an unfinished cell is one of the actions counted above, and each arrival to a finished cell is a UCB round. On Ebis , every cell that does finish has the accuracy guarantees in Section E. Cells that have not received enough arrivals remain in profiling mode and never supply an uncertified inventory to the UCB history. Under h ≤ hvis , the certified bound on Section E lies inside the radius in Assumption 4. Its quadratic loss condition and ε = hα ≤ 1 give Gx (p) − Qx (p, yex (p)) ≤ Cε. The equality of the proxy and true inventory gaps follows from Proposition 3. Finally, yx∗ (p) − qρ (x, p) ≥ mq , and the definition of hvis makes the right-hand side of Section E at most mq /2. Hence yex (p) ≥ qρ (x, p) + mq /2. At every u ≤ qρ (x, p), censoring is therefore inactive, so the ρ-quantile of sales equals the ρ-quantile of demand.

F

P ROOFS FOR K ERNEL C ONCENTRATION AND C OUNTING

Lemma 3 (Sequential kernel proxy and quantile concentration). Let ℓT (δ) = log(CT 4 |Γ|h−d /δ). There is an event Eker with probability at least 1 − δ such that, on its intersection with the profiling event, uniformly over UCB queries with Wt (x, p) > 0, s ! ℓ (δ) T b (x, p) − G (p)| ≤ C + ε + hα , |G t x Wt (x, p) s ! ℓT (δ) α |b qρ,t (x, p) − qρ (x, p)| ≤ C +h . Wt (x, p) Lemma 4 (Kernel calibrated-value confidence). On the intersection of the profiling event and Eker , uniformly over UCB queries with Wt (x, p) > 0, s ℓT (δ) cal b t (x, p) − {Gx (p) − bzρ (x)} ≤ C G + C(ε + hα ). max{1, Wt (x, p)} Lemma 5 (Kernel counting). Let UT be the set of UCB rounds. For every predictable interleaving rule and price sequence pt ∈ Γ on those rounds, q X 1 p ≤ C T |Γ|h−d . max{1, Wt (xt , pt )} t∈UT Proof of Lemma 3. We first make the sequential measurability explicit for the interleaved policy. Include the policy’s internal random seed and initialized profiler state in F0 , and let Fs−1 = σ(F0 , (xr , pr , yr , Or ) : r < s) ,

Gs = Fs−1 ∨ σ(xs ).

The decision whether round s is a profiling or UCB round, and then the action (ps , ys ), are Gs measurable. The fresh noise ϵs ∼ Fxs , and hence the outcome Os , is generated afterward and is conditionally independent of the past given (xs , ps , ys ). Write As = 1 when round s is a UCB round. 20

Fix a query time t, a price p ∈ Γ, and condition on xt = x. For s < t, enlarge the pre-outcome sigma-field to Gs(t) = Gs ∨ σ(xt ). This is legitimate because the contexts are i.i.d.: xt is independent of Ft−1 , which already contains each past context and its context-conditioned noise outcome. In particular, adjoining xt does not change the conditional law of the period- s outcome. Set mYs = E[Ys | Gs ].

ws = K((xs − x)/h)1{As = 1, ps = p}, (t)

(t)

The weight is Gs -measurable, and E[Ys − mYs | Gs ] = 0. Hence ws (Ys − mYs ) is a bounded (t) martingale difference in the filtration that reveals Os after Gs . Since |Ys − mYs | ≤ 2Ymax and 0 ≤ ws ≤ 1, Hoeffding’s conditional lemma gives, for every θ ∈ R, i h  2 E exp θws (Ys − mYs ) − 2θ2 Ymax ws2 Gs(t) ≤ 1. Thus the product of the factors in Section F is a nonnegative supermartingale. Also, X X ws2 ≤ ws = Wt (x, p). s<t

s<t

Applying the exponential supermartingale inequality on the dyadic events 2j−1 < Wt (x, p) ≤ 2j , and assigning failure probability δ/(2CT |Γ| log(eT )) to each query and dyadic level, gives X

ws (Ys − mYs ) ≤ C

p

Wt (x, p)ℓT (δ)

s<t

for this conditional query. The same argument applies pto the negative martingale. After division by Wt (x, p) > 0, the stochastic proxy error is at most C ℓT (δ)/Wt (x, p). This derivation handles the data-dependent effective sample size; no deterministic lower bound on Wt (x, p) is used. On the profiling event, every observation with As = 1 comes from a cell whose profile was already completed before choosing the action. Hence Proposition 3 and Lemma 2 give |mYs − Gxs (p)| = Gxs (p) − Qxs (p, yexs (p)) ≤ Cε. Moreover, the context-regularity conclusion of Proposition 1 implies, whenever ws > 0, |Gxs (p) − Gx (p)| ≤ Lloc hα . The weighted average of Section F, combined with Section F, proves ) (s ℓT (δ) b α +ε+h . |Gt (x, p) − Gx (p)| ≤ C Wt (x, p) We now control the weighted empirical quantile. Put rρ := min{rq , mq /4, ry /2}, Ux,p = [qρ (x, p) − rρ , qρ (x, p) + rρ ]. When ws > 0, context smoothness gives |qρ (xs , p) − qρ (x, p)| ≤ (Lx + LF /κ)hα . Together with the profiling margin yexs (p) ≥ qρ (xs , p) + mq /2 and the certified inequality (Lx + LF /κ)hα ≤ mq /8, this shows that u ≤ qρ (x, p) + rρ ≤ qρ (xs , p) + rρ + mq /8 < yexs (p) throughout Ux,p . Thus censoring does not alter the lower-tail indicators: 1{Os ≤ u} = 1{Ds ≤ u},

u ∈ Ux,p .

Let VT be a deterministic grid of [0, ymax ] with mesh at most T −2 , so |VT | ≤ CT 2 . Conditional on xt = x, augment the grid points lying in Ux,p by the two endpoints of that interval. This queryspecific grid still has at most CT 2 + 2 points, all inside the uncensored neighborhood. Fix one such point v and set ξs (v) = 1{Os ≤ v} − Fxs (v − λ(xs , p)). 21

(t)

The visibility calculation in Section F applies and E[ξs (v) | Gs , ps = p] = 0. Consequently ws ξs (v) obeys the same exponential-supermartingale bound as the proxy sequence. Allocate failure probability δ/(2CT |Γ||VT | log(eT )) to every (t, p, v) and dyadic weight level. A union bound gives the desired inequality at all relevant grid points. For an arbitrary u ∈ Ux,p , take adjacent grid points v− ≤ u ≤ v+ . Monotonicity gives Fbt (v− | x, p) ≤ Fbt (u | x, p) ≤ Fbt (v+ | x, p), while the population CDF changes by at most KT −2 between adjacent points. Absorbing this deterministic term into the radius yields, simultaneously over u ∈ Ux,p , s P w F (u − λ(x , p)) ℓT (δ) s x s s s<t Fbt (u | x, p) − ≤C . Wt (x, p) Wt (x, p) The upper density bound, the Hölder condition on Fx , and |λ(xs , p) − λ(x, p)| ≤ Lx hα imply |Fxs (u − λ(xs , p)) − Fx (u − λ(x, p))| ≤ sup |Fxs (v) − Fx (v)| + K|λ(xs , p) − λ(x, p)| v

≤ (LF + KLx )hα . Consequently, (s sup |Fbt (u | x, p) − Fx (u − λ(x, p))| ≤ et ,

et = C

u∈Ux,p

ℓT (δ) + hα Wt (x, p)

) .

The target CDF equals ρ at qρ (x, p). On the fixed neighborhood from Assumption 3, its density is at least κ. Suppose first that 2et ≤ rρ . κ Integrating the density lower bound on both sides of zρ (x) gives Fx (qρ (x, p) + 2et /κ − λ(x, p)) ≥ ρ + 2et and Fx (qρ (x, p) − 2et /κ − λ(x, p)) ≤ ρ − 2et . Both evaluation points lie in Ux,p , so Section F implies that the empirical CDF is below ρ at the lower point and above ρ at the upper point. The defining crossing property of the measurable weighted empirical quantile then yields |b qρ,t (x, p) − qρ (x, p)| ≤ 2et /κ. Outside the regime in Section F, κ rρ > 0. 2 Both quantiles lie in the fixed bounded sales interval, so enlarging the universal radius constant by that interval’s diameter divided by e0 gives the same order Cet there as well. et ≥ e0 ,

e0 :=

Finally, every bound above was conditional on an arbitrary value xt = x, and its failure probability does not depend on x. Taking conditional expectations therefore removes this conditioning. A union bound over at most T |Γ| realized time–price queries, at most 1 + ⌈log2 T ⌉ dyadic weight levels, and |VT | ≤ CT 2 CDF grid points has total failure probability at most δ. The logarithm of this cardinality is bounded by ℓT (δ), completing both simultaneous claims without a union bound over the uncountable context space. Proof of Lemma 4. By Lemmas 1 and 3, b cal G t (x, p) − {Gx (p) − bzρ (x)} b (x, p) − G (p) + b |b ≤ G qρ,t (x, p) − qρ (x, p)| , t x which is the stated radius after enlarging C. 22

Proof of Lemma 5. Use a deterministic partition of [0, 1]d into M ≤ Ch−d cells of diameter at most h/2, and let j(t) denote the cell containing xt on a UCB round. Two contexts in the same cell are at distance at most h/2. Hence every earlier UCB observation in cell j(t) at price pt has kernel weight at least k0 . Let Nj,p (t) be the number of such UCB observations strictly before t. Pathwise, Wt (xt , pt ) ≥ k0 Nj,pt (t). Order the visits to a fixed pair (j, p) by r = 1, . . . , Nj,p (T ). On its r-th visit, the preceding count is r − 1. The first visit contributes one because the denominator in the lemma is truncated at one, and Nj,p (T )

1

X p r=1

max{1, r − 1}

≤C

q Nj,p (T ).

−1/2

After absorbing k0 , summing this bound and applying Cauchy–Schwarz gives Xq X 1 p ≤C Nj,p (T ) max{1, Wt (xt , pt )} j,p t∈UT s X ≤ C M |Γ| Nj,p (T ) j,p

≤C

q

|UT ||Γ|h−d ≤ C

q T |Γ|h−d .

This argument is deterministic once the context and price sequences are fixed, so it applies to every predictable adaptive interleaving policy.

G

C OMPLETE P ROOFS OF THE C ONTEXTUAL U PPER B OUNDS

Complete proof of Theorem 2. Let r = (d+2α)/(d+3α) < 1 and Kdec = |Γdec |, Kprof = |Γprof |. The tuning constants are fixed problem constants. Since hT → 0 and −1 Kprof h−d polylog(T ) = o(T ), prof ε

there is a finite T0 such that hT ≤ hvis for every T ≥ T0 . For T < T0 , every branch of Algorithm 1 has regret at most Rmax T ≤ Rmax T01−r T r , so increasing the theorem constant covers these horizons. We henceforth take T ≥ T0 ; the deterministic startup fallback is then inactive. Run the interleaved profiler–UCB policy with δ = T −2 , and let Eprof and Eker denote the events from Lemmas 2 and 3. By definition, Ctune dominates the constants in the profiler and confidence radii. For fixed d, the logarithm in the index is equivalent up to a constant to ℓT (T −2 ). A union bound gives P(E c ) ≤ 2T −2 , E := Eprof ∩ Eker . c On E , total regret is at most T Rmax , so its expected contribution is at most 2Rmax /T . For every arrival and outcome realization, Lemma 2 bounds the number of profiling rounds by −1 Nprof (T ) ≤ CKprof h−d polylog(T ). prof ε

Every one of these rounds costs at most Rmax , so −1 Regprof ≤ CKprof h−d polylog(T ). prof ε

For the stated bandwidth this quantity is o(T ); arrivals to already completed cells are not included in this charge and are UCB rounds. Consider a UCB round with xt = x. Let pΓx maximize Gx over the grid. By Proposition 2, Vx − Gx (pΓx ) ≤ LG ε. Recall Hx (p) = Gx (p) − bzρ (x), and define (s βt (x, p) = C

ℓT (T −2 ) + ε + hα max{1, Wt (x, p)} 23

) .

On E, whenever both relevant effective sample sizes are positive, Γ Γ b cal Hx (pΓx ) ≤ G t (x, px ) + βt (x, px ) ≤ Ut (x, pΓx ) ≤ Ut (x, pt ) ≤ Hx (pt ) + 2βt (x, pt ). The middle inequality is the defining UCB choice. When Wt (x, pt ) > 0, a candidate with zero effective sample size has infinite index, so pΓx cannot have zero weight; hence the displayed chain indeed covers this case. When Wt (x, pt ) = 0, boundedness gives Gx (pΓx ) − Gx (pt ) ≤ C, which is absorbed by the same right-hand side because max{1, Wt (x, pt )} = 1 and ℓT (T −2 ) ≥ 1. Since the common shift cancels, Section G therefore yields for every UCB round s ℓT (T −2 ) Gx (pΓx ) − Gx (pt ) ≤ C + C(ε + hα ). max{1, Wt (x, pt )} The period regret decomposes exactly as Vx − Qx (pt , yex (pt )) = {Vx − Gx (pΓx )} + {Gx (pΓx ) − Gx (pt )} + {Gx (pt ) − Qx (pt , yex (pt ))}. The first term is controlled by Section G, the second by Section G, and the third is at most Cε by Lemma 2. Thus s Vx − Qx (pt , yex (pt )) ≤ C

ℓT (T −2 ) + C(ε + hα ). max{1, Wt (x, pt )}

Summing Section G over the UCB rounds, applying Lemma 5, adding Section G, and then adding the failure-event contribution gives n o p −1 RegT ≤ C polylog(T ) Kprof h−d + T Kdec h−d + T (ε + hα ) . prof ε −d/2 For the Lipschitz price class, Kdec ≤ Cε−1 , Kprof ≤ Cε−1/2 , and h−d . With ε = hα , prof = h Section G becomes n o √ RegT ≤ C polylog(T ) h−(d+3α)/2 + T h−d−α + T hα .

Ignoring logarithmic factors, the choice h = T −1/(d+3α) is equivalent to T = h−(d+3α) , and consequently √ √ T h−d−α = T hα = T (d+2α)/(d+3α) . h−(d+3α)/2 = T , Since (d + 2α)/(d + 3α) > 1/2, the profiling term is lower order. The logarithmic modification in Algorithm 1 changes only the polylogarithmic factor, completing the proof. Complete proof of Corollary 1. Let rsm = (2d + 3α)/(2d + 5α) < 1. With the smooth bandwidth and grid, hT → 0 and the profiling-action bound below is o(T ), so there is a finite T0,sm after which the deterministic visibility fallback is inactive. Earlier horizons satisfy Rmax T ≤ 1−rsm rsm Rmax T0,sm T . For later horizons, the good-event, profiling-action, optimism, and counting argument from Section G through Section G is unchanged. Under the bounded-second-derivative √ condition, Proposition 2 permits a mesh of width ε. It has Kdec = O(ε−1/2 ) and price approximation loss O(ε). Therefore Section G becomes n o p RegT ≤ C polylog(T ) h−d/2 ε−3/2 + T h−d ε−1/2 + T (ε + hα ) . Substitute ε = hα . Ignoring logarithms, the bandwidth h = T −2/(2d+5α) satisfies T = h−(d+5α/2) , so h−d/2 ε−3/2 = h−(d+3α)/2 , p T h−d ε−1/2 = h−d−3α/2 , T ε = h−d−3α/2 . The profiling exponent (d + 3α)/2 is strictly smaller than d + 3α/2. Finally, h−d−3α/2 = T (2d+3α)/(2d+5α) . The logarithmic factor in the stated bandwidth is again absorbed by polylog(T ). 24

H

P ROOFS FOR THE L OWER B OUND C ONSTRUCTION

Lemma 6 (Slack flat-value baseline). There exist a smooth compactly supported mean-zero density f0 , intervals P0 ⋐ int(P1 ) ⋐ P, a smooth λ0 , and C0 , s0 > 0 such that the constant family Fx ≡ F0 satisfies Assumption 3, Z 2 dp IH := 4 f0 (z) dz < ∞, R dz G0 (p) = pλ0 (p) + CF0 (p) equals C0 on P0 , is smaller outside P0 , and is at most C0 − 4s0 outside P1 . The baseline can be chosen so that, uniformly in p, λ0 (p) + z,

(ymax − ry ) − y0∗ (p),

q0,ρ (p) − (ymin + ry ),

zp0 − zρ0 − mq ≥ 4s0 ,

with 0 < ry ≤ rq , and G0 , λ0 have uniformly bounded first two price derivatives. Definition 1 (Normalized context–price packing). Fix the baseline and the interval P0 from Lemma 6. Let ζ(t) = e−1/t 1{t > 0},

ϑ(u) =

ζ(1/2 − |u|) . ζ(1/2 − |u|) + ζ(|u| − 1/4)

Then ϑ ∈ C ∞ (R; [0, 1]), it equals one on [−1/4, 1/4], and its support is [−1/2, 1/2]. Define the normalized context bump d Y ϑ(vℓ ), v ∈ Rd . Ψ(v) = ℓ=1

For 0 < h ≤ 1/4, put mh = ⌊(2h)−1 ⌋, index the multi-indices r ∈ {0, . . . , mh − 1}d by j = 1, . . . , Mh , where Mh = mdh , and set cj,ℓ = (2rℓ + 1)h,

ℓ = 1, . . . , d,

Bj = cj + [−h/2, h/2]d , Bj◦ = cj + [−h/4, h/4]d ,   x − cj ψj (x) = Ψ . h Thus the cells Bj ⊂ [0, 1]d are pairwise disjoint, supp(ψj ) = Bj , and ψj = 1 on Bj◦ . Choose once and for all a closed interval J = [pL , pR ] ⋐ int(P0 ), and write L0 = pR − pL . For 0 < w ≤ L0 /4, let   L0 , pk = pL + (2k − 1)w, k = 1, . . . , K∆ , K∆ = 2w and define φ0 ≡ 0,

  p − pk φk (p) = ϑ , w

Sk = {p : φk (p) > 0}.

The sets Sk are pairwise disjoint and contained in J. Finally, let Ω0 = {0, 1, . . . , K∆ }Mh ,

Ω = {1, . . . , K∆ }Mh ,

and, for every label vector ω ∈ Ω0 , define gω (x, p) = ∆

Mh X

ψj (x)φωj (p).

j=1

The augmented set Ω0 contains the zero-label reference experiments; the final hard prior is supported on Ω. 25

Proposition 4 (Properties of the normalized packing). For the construction in Definition 1, constants depending only on d, L0 , and the fixed bump ϑ satisfy ch−d ≤ Mh ≤ Ch−d , Under the uniform context distribution,

cw−1 ≤ K∆ ≤ Cw−1 .

P(xt ∈ Bj ) = hd , P(xt ∈ Bj◦ ) = 2−d hd . Moreover, uniformly over ω ∈ Ω0 , ∥gω ∥∞ ≤ ∆, ∥∂p gω ∥∞ ≤ C∆/w, ∥∂pp gω ∥∞ ≤ C∆/w2 , α

|gω (x, p) − gω (x′ , p)| ≤ C∆h−α ∥x − x′ ∥ . For x ∈ Bj◦ , the perturbation reduces exactly to gω (x, p) = ∆φωj (p). Consequently, when ωj = k ≥ 1, its maximum over P0 is ∆, attained on the plateau of φk , while it is zero for every p ∈ / Sk . Lemma 7 (Stability of lower-bound perturbations). There are h0 , ∆0 , c∆ > 0 and a baseline from Lemma 6 such that, for h ≤ h0 , ∆ = c∆ hα ≤ ∆0 , the packing in Definition 1 with w = ∆, and every ω ∈ Ω0 , λω (x, p) = λ0 (p) + gω (x, p)/p is nonnegative, satisfies all assumptions, and has an optimal√price in int(P0 ). The twice-smooth construction satisfies the same claim for the packing with w = ∆ and uniformly bounded ∂pp Gω,x . Proof of Lemma 6. Let  fe(u) = cf exp −

 1 1{|u| < 1}. 1 − u2 This density is symmetric and hence mean zero, is positive on every compact subset of (−1, 1), q and vanishes to all orders at the endpoints. Therefore fe ∈ H 1 (R). A fixed rescaling f0 (u) = a−1 fe(u/a) retains these properties and has finite IH . Since ρ < inf p∈P ϕ(p) and ϕ is continuous, after taking the price interval sufficiently small around an interior p0 > 0, all relevant probability levels lie in one compact subset of (0, 1). Their quantiles therefore lie in a compact subinterval on which f0 admits uniform positive lower and finite upper bounds. Choose rq , κ, K from this compact 0 , and let CF0 denote the residual-value functional in subinterval. Write zu0 = F0−1 (u), zp0 = zϕ(p) Proposition 1 for F0 . Choose mq strictly below inf p (zp0 − zρ0 ). Choose a location level λ̄, and fixed inventory endpoints, so that λ̄ + z > 0 and both λ̄ + zρ0 and λ̄ + zp0 lie strictly inside the inventory interval. This is possible by first taking the noise scale a small and then centering the inventory interval at λ̄. Define C0 − CF0 (p) C0 = p0 λ̄ + CF0 (p0 ), λflat (p) = . p The function CF0 is C 2 on the chosen price interval: the quantile map p 7→ zp0 is C 2 there by the density lower bound, and the truncated expectations defining CF0 may be differentiated under the integral. Hence λflat is C 2 , equals λ̄ at p0 , and remains inside all strict feasibility margins after shrinking the price interval. Choose P0 ⋐ int(P1 ) ⋐ P around p0 and a smooth cutoff χ : P → [0, 1] that is zero on P0 and one outside P1 , and is strictly positive on P \ P0 . For a sufficiently small fixed s0 > 0, set G0 (p) − CF0 (p) G0 (p) = C0 − 4s0 χ(p), λ0 (p) = . p Continuity on the compact price interval and the strict margins of λflat permit choosing s0 and the interval widths so that all four inequalities in part (iii) hold. The cutoff construction gives part (ii), while p ≥ pmin > 0 and smoothness of G0 , CF0 give the derivative bounds in part (iv). This proves every item of the lemma. 26

Proof of Proposition 4. For h ≤ 1/4, (4h)−1 ≤ mh ≤ (2h)−1 , which yields the first cardinality bound. Similarly, w ≤ L0 /4 gives L0 /(4w) ≤ K∆ ≤ L0 /(2w). The cells and their cores have Lebesgue volumes hd and (h/2)d , respectively, proving Proposition 4 under the uniform context law. The centers of distinct context cells differ by at least 2h in one coordinate, whereas every Bj has side length h. Hence their supports are disjoint. Likewise, adjacent price centers are 2w apart and each price support has width w, so the sets Sk are pairwise disjoint. The first three bounds in Proposition 4 now follow from 0 ≤ Ψ, ϑ ≤ 1, the disjoint context supports, and the fixed finite quantities ∥ϑ′ ∥∞ and ∥ϑ′′ ∥∞ . It remains to verify the context Hölder bound, including pairs of points in different cells. Since Ψ is smooth and compactly supported, α

|ψj (x) − ψj (x′ )| ≤ C min{1, h−1 ∥x − x′ ∥} ≤ Ch−α ∥x − x′ ∥ . When x, x′ lie in the same cell, or one of them lies outside every cell, this proves the claim directly. When they lie in distinct cells, the separation of the supports gives ∥x − x′ ∥ ≥ h; boundedness by one then gives the same inequality. Multiplication by ∆ proves the last bound in Proposition 4. Finally, ψj = 1 on Bj◦ , all other context bumps vanish there, and maxp φk (p) = 1. This proves Proposition 4 and the final assertion. Proof of Lemma 7. We now verify the five assumptions uniformly over the packing. Assumption 1: context process. The context distribution is uniform on [0, 1]d , so the i.i.d. requirement in Assumption 1 holds. Common perturbation bound and slack choice. δλω = gω /p, ∥δλω ∥∞ ≤ A0 ∆,

By Proposition 4, |gω (x, p)| ≤ ∆, and, with A0 := p−1 min .

Fix  ∆0 ≤ min

 s0 , s0 , 1 , A0

Choose c∆ > 0 small enough that the context Hölder constant below is at most the prescribed Lx . Then choose h0 ≤ 1/4 so that, for every h ≤ h0 , √ ∆ = c∆ hα ≤ ∆0 , ∆ ≤ L0 /4. This also guarantees w ≤ L0 /4 in both price-regularity regimes, so every object in Definition 1 is well defined. Assumption 2: location surface and nonnegative demand. The baseline margin and Section H give λω (x, p) + z ≥ 4s0 − A0 ∆ ≥ 3s0 > 0. The same inequality and compactness give uniform boundedness of demand. The context bound in Proposition 4, together with p ≥ pmin and ∆ = c∆ hα , gives α

|λω (x, p) − λω (x′ , p)| ≤ Cc∆ ∥x − x′ ∥ . For price regularity of the demand surface,   gω (x, p) ∂p gω (x, p) gω (x, p) = − . ∂p p p p2 By Proposition √ 4, the Lipschitz packing has |∂p gω | ≤ C∆/w√≤ C because w = ∆. In the smooth packing, w = ∆, and the same first derivative is even O( ∆). Combining these bounds with the fixed smooth baseline proves the price-Lipschitz part of Assumption 2 uniformly over the two families. 27

Assumption 3: context-conditioned shared noise and calibration separation. Set Fx ≡ F0 for every context and every packing instance. This constant family has Hölder modulus zero. Its mean-zero normalization, compact support, bounds K, κ, rq , and quantiles zρ0 , zp0 are identical across contexts and across the packing. In particular, Lemma 6 gives zp0 − zρ0 ≥ mq + 4s0 ≥ mq uniformly in p, proving Assumption 3. Assumption 4: inventory root, loss, and visibility.

The stockout probability is

Sω,x (y | p) = 1 − F0 (y − λω (x, p)). Its root is

∗ yω,x (p) = λω (x, p) + zp0 ,

and the calibration quantile is

qρ,ω (x, p) = λω (x, p) + zρ0 . Both quantities shift from their baseline values by the same δλω (x, p). Hence the explicit slack choice gives qρ,ω (x, p) − (ymin + ry ) ≥ 4s0 − A0 ∆ ≥ 3s0 , ∗ (ymax − ry ) − yω,x (p) ≥ 4s0 − A0 ∆ ≥ 3s0 , ∗ yω,x (p) − qρ,ω (x, p) = zp0 − zρ0 ≥ mq + 4s0 .

The lower density bound around zp0 gives the local two-sided slope condition in Assumption 4; the upper density bound gives the matching upper slope. More explicitly, for y in the fixed root neighborhood, the mean-value theorem gives ∗ ∗ κ|y − yω,x (p)| ≤ |Sω,x (y | p) − τ (p)| ≤ K|y − yω,x (p)|.

Integrating ∂y Q = (p + b + hc )(S − τ ) from y to the root yields pmax + b + hc ∗ 0 ≤ Gω,x (p) − Qω,x (p, y) ≤ K|y − yω,x (p)|2 . 2 This is the required quadratic inventory-loss condition after enlarging Cy . Positivity of f0 on the radius-rq neighborhood of zp0 also makes the critical root unique. Together with Section H, this proves every part of Assumption 4. Optimal-price interiority.

By Proposition 1, for every price,

Gω,x (p) = pλω (x, p) + CF0 (p) = G0 (p) + gω (x, p). All price bumps are supported in J ⋐ int(P0 ). For a context with positive bump amplitude, a point on the corresponding price-bump plateau attains C0 + ∆ψj (x) > C0 , whereas every price outside P0 has value at most C0 . With zero bump amplitude, every point of P0 , hence some interior point, is a baseline maximizer. Thus every perturbed instance has an optimal price in the required interior interval, and no price-monotonicity property is used. Assumption 5: optimized price value. In the Lipschitz construction, Proposition 4 gives |∂p gω | ≤ C∆/w = O(1), yielding the uniform√Lipschitz value bound after adding the fixed smooth baseline G0 . In the smooth construction, w = ∆, so |∂pp gω (x, p)| ≤ C∆/w2 = O(1), which proves the bounded-second-derivative specialization. Outside P0 , the perturbation vanishes and G0 has fixed bounded derivatives. This completes the uniform verification of Assumptions 1 to 5. R √ √ Lemma 8 (Location-family information bound). With H 2 (P, Q) = 21 ( dP − dQ)2 , shifts of the baseline density satisfy IH H 2 (f0 (· − u), f0 (· − v)) ≤ |u − v|2 . 4 Thus neighboring bump instances have one-round squared Hellinger distance O(∆2 ) on the affected context–price region and zero elsewhere. The same bound holds for censored sales under every adaptive inventory action. 28

Proof. Let s =

√

f0 . The fundamental theorem of calculus gives

1 IH |u − v|2 ∥s′ ∥22 = |u − v|2 . 2 8 For the neighbors used below, ω and ω ′ agree outside one cell j, while their labels in that cell are 0 and k. By Definition 1, their locations agree unless x ∈ Bj and p ∈ Sk , and everywhere differ by at most |gω (x, p) − gω′ (x, p)|/pmin ≤ C∆. Censoring is a measurable image of demand, so data processing proves the claim. H 2 (f0 (· − u), f0 (· − v)) ≤

I

C OMPLETE D IRECT-S UM P ROOF OF THE L OWER B OUND

Complete proof of Theorem √ 3. Fix one of the two price-regularity regimes, set w = ∆ in the Lipschitz regime and w = ∆ in the twice-smooth regime, and use the family Ω in Definition 1. By Lemma 7, every member of this family belongs to the claimed model class. It remains to show that no adaptive policy can learn all context-cell labels quickly enough. We give the argument for a deterministic policy; conditioning on a randomized policy’s internal seed and then applying Yao’s principle gives the stated conclusion for randomized policies. All objects below are those formally constructed in Definition 1; in particular, the price supports Sk are pairwise disjoint and ψj = 1 on Bj◦ . We use the three counts N j,k =

T X

1{xt ∈ Bj , pt ∈ Sk },

t=1

Nj◦ =

T X

1{xt ∈ Bj◦ },

t=1 ◦ Nj,k =

T X

1{xt ∈ Bj◦ , pt ∈ Sk }.

t=1

The first count includes the transition shell Bj \ Bj◦ . This inclusion is essential because observations in that shell also carry information about the label. The core counts will be used only to lower-bound regret. Fix a cell j. Put an independent uniform prior on the labels of all other cells. Let P(j,0) be the resulting mixture history law when cell j has no bump, and let P(j,k) be the mixture law when its label is k. The no-bump instance is a reference experiment only; it need not receive positive mass under the final prior. Conditional on a fixed configuration of the other labels, adaptive Hellinger tensorization and Lemma 8 give (j,k) 2 (j,0) H 2 (P(j,0) ω−j , Pω−j ) ≤ C∆ Eω−j [N j,k ].

To see why, condition on the history immediately before round t. The policy uses the same action kernel in the two experiments. Their conditional observation laws differ only when xt ∈ Bj and pt ∈ Sk ; on such a round their locations differ by at most C∆. Censoring at the adaptively chosen inventory is a measurable map of demand, so data processing preserves the C∆2 one-round bound. Summing these conditional bounds under the reference law proves Section I. Squared Hellinger distance is jointly convex. Averaging Section I over the other labels and then over k gives "K # K∆ ∆ 1 X C∆2 (j,0) X 2 (j,0) (j,k) H (P ,P )≤ E N j,k K∆ K∆ k=1

k=1

d

2

Th ∆ . K∆ The second inequality uses disjointness of the price supports and P(xt ∈ Bj ) = hd , as established in Proposition 4. Choose the fixed packing constant c∆ and the bandwidth so that ≤C

T hd ∆2 ≤ cinf K∆ 29

p for a sufficiently small numerical cinf . Since TV(P, Q) ≤ 2H 2 (P, Q), Jensen’s inequality and Section I yield K∆ 1 X TV(P(j,0) , P(j,k) ) ≤ ctv , K∆ k=1

where ctv can be made smaller than 1/8. We next convert indistinguishability into regret. Define ◦ Aj,k = {Nj◦ > 0, Nj,k ≥ Nj◦ /2},

Ej,k = Acj,k ∩ {Nj◦ ≥ cB T hd }.

Because the price supports are disjoint, on every sample path with Nj◦ > 0, at most two of the events Aj,k can occur. Therefore K∆ 2 1 X P(j,0) (Aj,k ) ≤ . K∆ K∆

k=1 By Proposition 4, the random variable Nj◦ is binomial with mean 2−d T hd , independently of the

policy. Under Section I, this mean diverges along the hard sequence; a Chernoff bound gives, for all sufficiently large T , 3 P(j,0) (Nj◦ ≥ cB T hd ) ≥ . 4 Equations Section I imply K∆ 1 X P(j,k) (Ej,k ) ≥ cE > 0. K∆ k=1

Indeed, the average reference probability is at least 3/4 − 2/K∆ , and changing from the reference to the alternatives reduces it by at most the average total-variation distance. By Proposition 4, on Bj◦ under label ωj = k and for p ∈ P0 , the optimized value is Gω,x (p) = C0 + ∆φk (p). Its maximum is C0 + ∆. Every price in P0 but outside Sk has gap exactly ∆; every price outside P0 has gap at least ∆, because the baseline extension is at most C0 and all price bumps are supported in P0 . On Ej,k , at least Nj◦ /2 core visits use prices outside Sk . Inventory suboptimality is nonnegative, so X Regj := {Vxt − Qxt (pt , yt )} t:xt ∈Bj◦

∆ ◦ N 1{Ej,k }. 2 j Combining this inequality with Section I proves the cellwise Bayes bound ≥

K

∆ 1 X E(j,k) [Regj ] ≥ cT hd ∆. K∆

k=1

Now draw ω uniformly from Ω = {1, . . . , K∆ }Mh ; equivalently, all cell labels are independent and uniform. For fixed j, integrating out the other labels gives exactly the mixture experiment above. The conditional observation kernel can depend directly on ωj only on rounds with xt ∈ Bj , which is precisely the localization used in Section I. The core cells are disjoint, so summing Section I yields Bayes regret Eω∼Unif(Ω) [RegT ] ≥ cMh T hd ∆ ≥ cT ∆. Yao’s principle turns Section I into a worst-instance lower bound for every randomized policy. It remains to solve the information balance. In the Lipschitz construction, w = ∆ and K∆ ≍ ∆−1 , so Section I is tight at T hd ∆3 ≍ 1. α Together with ∆ = c∆ h , this gives h ≍ T −1/(d+3α) ,

T ∆ ≍ T (d+2α)/(d+3α) . 30

In the twice-smooth construction, w =

√

∆ and K∆ ≍ ∆−1/2 . Hence

T hd ∆5/2 ≍ 1, and

h ≍ T −2/(2d+5α) ,

T ∆ ≍ T (2d+3α)/(2d+5α) .

This proves both lower bounds. Enlarging the constants covers the finitely many horizons preceding the hard-sequence regime.

31

Related documents

• Semiparametric pricing of multivariate contingent claims#942404
• Learning by Creating and Justifying Transfer Frames#239451
• Non-Discriminatory Personalized Pricing#302998
• Pricing Multivariate Contingent Claims Using Estimated Risk-neutral Density Functions#942528
• Pricing Multivariate Contingent Claims using Estimated Risk-neutral Density Functions#942472