Semi-Parametric Contextual Pricing with General Smoothness
Authors: Yuxuan Han
Xiaocong Xu
Yuxiao Wen
Yanjun Han
Ilan Lobel
Zhengyuan Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: Contextual pricing; online learning; semi-parametric models
Primary area: learning theory

Abstract: We study the contextual pricing problem, where in each round a seller observes a context, sets a price, and receives a binary purchase signal. We adopt a semi-parametric model in which the demand follows a linear parametric form composed with an unknown link function from a $\beta$-Hölder class. Prior work established regret rates of $\tilde{\mathcal{O}}(T^{2/3})$ for $\beta=1$ and $\tilde{\mathcal{O}}(T^{3/5})$ for $\beta=2$. Under a uni-modality condition, we propose a unified algorithm that combines the stationary subroutine of Wang & Chen (2025) with local polynomial regression, achieving the general rate $\tilde{\mathcal{O}}(T^{\frac{\beta+1}{2\beta+1}})$ for all $\beta \ge 1$. This recovers and strengthens existing results, while also addressing a gap in the prior analysis for $\beta=2$. Our analysis develops tighter semi-parametric confidence regions, removes derivative lower bound assumptions from earlier work, and offers a sharper exploration–exploitation trade-off. These insights not only extend theoretical guarantees to general $\beta$ but also improve practical performance by reducing the need for long forced-exploration phases.

Published as a conference paper at ICLR 2026
SEMI-PARAMETRIC CONTEXTUAL PRICING WITH GENERAL SMOOTHNESS
Yuxuan Han'
Xiaocong Xu"
New York University yh6061 @stern.nyu.ee..
University of Southern California
xuxiaoco@marrhha usc.sc edd
Yuxiao Wen, Yanjun Han, Ilan Lobel, Zhengyuan Zhou
New York University fyw3210, yanjunnan/enyu..... {ilobel, 2226 (
(Lbbe,,,,
ABSTRACT
We study the contextual pricing problem, where in each round a seller observes context, sets price, and receives binary purchase signal. We adopt semi- parametric model in which the demand follows a linear parametric form composed with an unknown link function from 3-HHölder class. Prior work established regret rates of ((22/3) for / = 1 and ((T3/5) for 3 Under uni-modality condition, we propose a unified algorithm that combines the stationary subroutine of Wang & Chen (2025) with local polynomial regression, achieving the general #+1 rate (TT for all 9 2 1. This recovers and strengthens existing results, while also addressing a gap in the prior analysis for 3 = 2. Our analysis develops tighter semi-parametric confidence regions, removes derivative lower bound assumptions from earlier work, and offers a sharper exploration-exploiatiin trade-off. These insights not only extend theoretical guarantees general / but also improve practical performance by reducing the need for long forced-exploration phases.
INTRODUCTION
Dynamic pricing addresses central problem in revenue management, where seller repeatedly interacts with users by offering personalized prices for the same product and collecting revenue from the resulting sales (Cournot, 1927; Den Boer, 2015). Across these interactions, users exhibit heterogeneous demand or private valuations, and the seller faces uncertainty in how demand responds the offered prices. This demand function effectively captures the market's valuation of the product. Consequently, the seller must learn the demand in real time while simultaneously aiming to maximize revenue, which gives rise the fundamental ppploration-cxploittatio tradeoff in dynamic pricing (Kleinberg & Leighton, 2003).
Recently, contextual dynamic pricing has gained significant traction in online retail, driven by the widespread availability of user-specific and contextual information (Cohen et al., 2020; Wang et al., 2021; Chen Gallego, 2021; Luo et al., 2024; Wang Chen, 2025). Modern platforms can conveniently access rich side information such as a user's account profile, browsing and purchase history, or relevant environmental factors-before deciding on a price. Incorporating such contextual signals enables sellers to move beyond static or aggregate demand models and tailor prices to individual users or market segments. To achieve this, firms need to find algorithms that learn how demand depends jointly on both price and context and determine optimal personalized price when a context is revealed.
Among various formulations for capturing the contextual dependence, the formulation with linear unility model and non-parametric noise is receiving increasing attention due to its flexibility compared with fully parametric model (Javanmard & Nazerzadeh, 2019) and simplicity between fully non- parametric models (Chen & Gallego, 2021). In this formulation, each user is associated with
Equual contribution, alphahetical order.

---

Published as a conference paper at ICLR 2026
Assumptions
This work: ÓT (774)
(A) Strong uni modality
(B) Context density LB
Fan et al. (2024): ( (-))
(C) -0=00
(D) d <
Result
Condition
Tullii et al. (2024): ((72/3)
ontc Exponent in T
Tullii et al. (2024)(3 1)
None
Wang & Chen (2025): @(77/5)
Fan (2024) (3 2
(BXCID)
Javanmard et al. (2019): é(vT)
Wang & Chen (2025) 2)
(A)())()
Our work
(AX())
Table 1:
Comparison of assumptions in semi and non- non- pan--aaamttiic demand models. The strong uni-modality condition is given in Assumption 3, and Σ Elc,c,", [. Fan et al. (2024) does not require (A), but in- stead assumes another shape condition on g(-). In both Wang & Chen (2025) and our work, condition (C) imposed only during the initial 241
1 2
+00
Smoothness parameter
exploration period of length Ö (TT)))1)
Figure 1: Exponent in T vs. smoothness 3.
context vector E Rdd upon arrival and derives a private utility we c. 0_ + É.. with 0_ E Rd being an unknown parameter and &. random noise. After offering price pt, the seller receives revenue feedback p; 1 {P: < uz} from the user, which indicates whether a purchase is made (i.e., revenue is generated) or not. denoting the tail distribution function PPG: 2 z) by g(z), the expected demand then reduces (p)) g(, 6. - p), this corresponds to the semi semi-parametric formulation (Ichimura, 1993; Hristache et al., 2001; Dalalyan et al., 2008).
As in the statistical estimation literature, the regularity of g(-) affects the difficulty of demand identification and thus decision making. Previous works have extensively studied the cemi-parametric pricing problem under different levels of regularity of g. For instance, Tullii et al. (2024) and Wang & Chen (2025) establish regret bound Ô(T3) and Ö(T²) respectively under first and second-order smoothness assumptions. In contrast, characterizing the general B-smooth regime for 3 E [1, +o0) plays an important role in understanding how regularity influences demand estimation and how the paraameeittic regime interpolates to the parametric rates (Hu et al., 2020). To the best of our knowledge, the only prior work that attempts to provide such a unified treatment is Fan al. (2024), 20-1
which establishes an Ó 48-1) regret bound. However, this result does not recover the Ö rate under the conditions of Wang & Chen (2025) and even degenerates to linear regret when = 1, leaving room for further improvement.
OUR CONTRIBUTIONS
Motivated by this gap, we explore the aami-parametric pricing setting in this work and provide the improved regret bounds, summarize contributions the following:
Improved Regret Bound for 3 2 1 Regimee Under strong uni-modality (Assumption 3) as in Wang 8-1 & Chen (2025); Chen & Gallego (2021), establish regret upper bound of Ö(T TT1) for all 3 2 1. For comparison, under uni-modality together with additional regularity, Fan et al. (2024) obtain (( ); under these distinct assumptions, our bound achieves smaller exponent in T. Our result matches the optimal contextual guarantees for | = 1 Luo et al. (2024); Tullii et al. (2024) and 3 = Wang & Chen (2025), and it interpolates to the parametric rate ((TT) as 3 + co. Moreover, coincides with the tight non-contextual bound Ô 25+1) for general I established in Wang et al. (2021). Hence, under strong uni-modality, semi-parametri contextual pricing is provably no harder than its non-contextual counterpart.
Unified Algorithm and Analysis. The proposed regret bound is achieved by developing unified joint estimation procedure and confidence bound analysis for the parametric and non- non-parametri parts via local polynomial regression for 1. particular, when 3 = the resulting confidence bound applies directly to yield ((T2/3) regret via the optimistic principle without strong uni-modality,
2

---

Published as a conference paper at ICLR 2026
matching Tullii et al. (2024). When 3 2 2, finer control of the parametric estimation error is required to exploit higher-order smoothness. We combine our procedure with elements of Wang & Chen (2025) to obtain the general bound, extending their algorithmic design from the case 3 2.
Improved Confidence Bound Analysis. Our confidence bound analysis generalizes Tullii et al. (2024); Wang & Chen (2025). In particular, when B 2 2. we encounter the same challenge of leveraging higher-order smoothness as in Wang & Chen (2025). While we adopt the idea of constrained least squares from their work, extending it to general / requires substantially more than straightforward calculation. First, the analysis in Wang & Chen (2025) heavily relies on a linear-time local exploration schedule. As we detail Section this works under uni-modality when 3 = but leads to degenerate regret rate as B increases. Second, although Wang & Chen (2025) pioneered the finite-sample analysis of constrained least squares, the complex dependency beyond martingale structure in such joint estimation procedure prevents the direct application of standard concentration inequalities such as Azuma-Hoeffdie cannot yield the claimed result'. These challenges motivate our improved analysis, which bypasses the dependence issue and significantly shortens the exploration period. As an additional contribution, our analysis also removes the strictly increasing CDF condition listed in Table 1, which has been assumed in prior smooth semi- mami-paramttrc settings Fan et al. (2024); Wang & Chen (2025), thereby broadening the applicability of the theory.
In their proof, this dependence is overlooked and therefore
Notation. For n E Σ4, we let [r]] == [L..... n and denote by || || the fo norm. For a positive definite matrix A E IRuxn and u E RR, write ||u]|a := VuT Au. For a matrix A, ||||| is the Frobenius norm; Amiu (A) and Amax (A) are its extremal eigenvalues; and A B means
B is
positive semidefinite. For E I. [a] is the greatest integer < a. We use a S b or = ( to mean
there exists C > such that la] S C|bb]: 2 b or a (b(b) to mean there exists c 0 such that
|a| 2 clbl; and a x b or (bb) to mean there exist C22 C1 >> O such that c/ S |a| s Cb all
those constants may only depend on B. We also use Ö, f2, θ to hide polylogarithmic factors.
2 PROBLEM FORMULATION
Dynamic Pricing with Linear Valuations. At each period E [T). a new customer arrives with observable feature vector c, E Ted drawn i.i.d. from an unknown distribution Pc and generates underlying valuation as
c, 0, + & for some 0, E Rd and &, i.i.d. drawn from distribution Ps with CDF Fz. After observing G,, the seller posts price Pt E [0, Pmaa]] and observes the binary purchase feedback V/ 1(u 2 pe} and the corresponding revenue Pitt- If we denote the tail function g(r) == (T),,, the conditional revenue is then given by
R(G. p.) = P, | Pr] = P,, 2 Pt - c. 0. G..P.) = Pig(p: - c, 0.).
The goal of the seller, without knowing 0, and Ps, is to determine adaptive policy for posting prices Pt to maximize the cumulative revenue E R(c,, Pt)]. The performance of the policy is evaluated by the cumulative revenue gap relative to the optimal policy:
T
Regret( (T)) = E
max R(c,, Pt),
For compactness we will use an augmented vector form: define = (c[, pT) E Rd+1 and 0. = 1)T E Rd++1, so that x. 0n = pt- c. 0. and Rlys C. g((r 0o)-
Smoothness Condition and Assumptions. For the parametric part of the model, we make the following boundedness assumption:
Assumption 1. There exist constants Ce, Co O such that ||ce]l S Ce almost surely and ||0_1| s Co. Let V == C.C. + Pmaxx Furthermore, the noise distribution Pz is supported on [-V, V).
Under Assumption 1, the value-price gap x 0o = c, 0_ pt lies in [-V.V] for all t, so g is only evaluated on a compact interval.
We note that, in the revised version of Wang & Chen (2025) after our submission, they independently addressed this issue using an argument different from ours.
3

---

Published as a conference paper at ICLR 2026
For the non non-parametric part, make the following assumption on g(-), which is equivalent to making an assumption on Fs due to the relation g(-) = Fz(.).
Assumption 2 (S-Hölder smoothness of g) There exist constants Lg 0 and B such that g: g:[-V.V] + [0, 1] is [3] times continuously differentiable and, for all u, u' E [-v,
[,8]
1) 9 (2) (w) S L'gl'' -u ul
g((())
h!
This is a standard notation for describing smoothness in nonparametric estimation (Györfi et al., 2002; Tsybakov, 2008). It unifies previous assumptions in the sense that / 1 corresponds to the Lipschitz setting studied in Tullii et al. (2024); Luo et al. (2024), and / = 2 corresponds to the "2nd-order smooth" setting studied in Wang & Chen (2025); Luo et al. (2022). In this work, provide unified treatment for all 3 2 1.
For the revenue function, make the following assumption. Assumption 3 (Strong uni-modality). For any lu| S. CcCs, under the shorthand notation r(u, p) pg(p u), the maximizer p" (u) = argmax, (u. p) unique and lies in the strict interior (0, Pmax). Moreover, there exist constants 0 < o, Lop OG such that for all [u] C.Co and all p E (m,x))
L, Tr P (u) S <r(u,," p(u,p) S - 1p 2
Assumption says that, given any valuation u fixed, the revenue function r(u, -) is locally strongly convex around its maximizer. Such conditions has appeared in various pricing models (Broder & Rusmevichientong, 2012; Wang et al., 2014; Chen & Gallego, 2021; Wang & Chen, 2025).
It is worth to note that while moaddyyaccceped. the strong uni mii-modlltty is tend be believed relative strong assumption in non-contextual pricing setting, in sense that ((VT) regret can be achieved even under the Lipschitz condition (6 1) of F= (Kleinberg Leighton, 2003; Wang et al., 2021). In sharp contrast, for the contextual setting, the (2(79/5) regret lower bound under the and Assumption 3 developed in Wang & Chen (2025) shows clear separation between the contextual and non-contextual cases, indicating that even under Assumption 3, the pricing problem is not overly simplified in setting.
Organization. In the remaining contexts, we divide our presentation into four parts. In Section recall an initialization guarantee and discuss the potential trade-off incurred for general 8. In Section 4, we describe a joint estimation procedure for semi semi-parametric estimation and its statistical guarantee. Finally, combine these procedures with policy improvement oracle introduced in Section 5 to present the complete algorithm and its regret guarantee in Section 6.
3 INITIAL EXPLORATIOON PHASE
In the initial exploration, phase, our goal is to obtain pilot estimator 0 Rd such that 100-011: for certain error level 7).
0-112 S
As discussed in Wang Chen (2025), such a pilot estimator may be obtained through initial access to offline data. However, suitable offline data is not al always available. In this section, we recall an initial exploration guarantee under the diverse context distribution assumption from Fan et al. (2024):
Assumption 4. There exists some positive constant Cmin that E((cT 1)T (cT 1)] Z Smin I.
Under Assumption 4, Fan et al. (2024) showed that by posting uniform exploration prices pt ~ Unif V] for -2) rounds, one can obtain the desired estimator through suitable parametric estimation procedure. The procedure is summarized in Algorithm 1, and we present the main result below; its proof is provided in Appendix for completeness.
Lemma 5. Suppose Assumption I and 4 hold. Fix 8 E (0, 1). Algorithm I with On log(1 1 1/6) rumning time can output parametric estimator 0 with ||@ 0_ll S n with probability at least 8.
In particular, every price posted in the exploration phase incurs a constant sub-optimality gap, so the total regret from exploration scales -2) To match the desired ((TT#)) regret bound under
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Pilot estimation (adapted from Fan et al. (2024))
1: Input: Running time t;
2: for the next time periods do
3: Offer price pt Unif[O, Pmax] and let (D(t)= = {cr, (r,,Pr, hejj be the collected data;
4: Compute +- arg mingeR" t- E'Eeej (Pmax C 0)
5:
return 0
the 3-Hölder condition, we require 17 17 2,न,, thus the pilot estimator accuracy must be restricted to O(T 43-2). When / 1, as discussed later in Section 4.1, with 1) T even a linear level perturbation bound ((Tr) is sufficient to achieve the optimal Õ(T2/3) regret. As 3 increases, the required regret rate decreases while the pilot error increases, calling for a sharper approach to exploiting smoothness information-this is precisely the challenge we attempt to address in this work. For convenience, we fix the level of 1) for a given 3 throughout the remaining discussion: When discussing the setting with a specific / 2 1, we set the corresponding pilot estimation error to 1) = 7 8-1
4312 As noted in the earlier discussion, this choice is the sharpest possible rate under 4+1
Lemma 5 without violating the desired O 2341 regret.
Finally, we note that Assumption is used only obtain the pilot estimator and is therefore needed 2+1
only during the initial exploration period of length ÖTT ((---T) While careful readers may find the phrase "needed only" unusual since our setting assumes i.i.d. contexts, here we allow the context distribution to be two-phased: after the initial exploration period, the contexts may follow any distribution that satisfies Assumption I, not necessarily Assumption 4.
4
SEMI-PARAMETRIC ESTIMATION SUB-ROUTINE
4.1 PILOTTDD LOCAL POLYNOMIAL. REGRESSION
Given a pilot estimate 8, := (-0T,1) of 0.. introduce piloted local polynomial regression subroutine, with an input dataset collected through a sub-routine conducted during a sub-interval of the total horizon (T). as the following.
In Algorithm 2. The input dataset 'D is first binned into different intervals I,.j E [M] based on the pilot estimator 6. then a local non conaamamtttrcc estimation is performed for every candidate parameter 9 over interval I to obtain (- 0). L, [Tyl- Now present the following deterministic
estimation error guarantee of ()(- () without any requirement on the input dataset D:
Proposition 6. Fix j E [M] and h Z T T'T.. Under Assumptions 1 and 2, for any with |10 0oll < n and any x with | < Ce + Pmax and x. Ou E I, if (0) invertible then
(z 0) g(x (1,(x, 0) (,( + Uz 0)
Σ
- -1z 0o) AJ (O)U
LET,
+0 VTy [|, (11)))))))) (0))),
where, with () = ((x - (x) ..... A(x - T0)e-1 (x " E ERR, we define
(, 0) = (, - U2 0) A (0) Σ
iET, Uy(Ti, 0) (x,
60 = (z'( (0) 0b) (0) (a. 8o) (0 - 0o) T ER.
In Proposition 6, the estimation error is decomposed into three terms. The first term, which arises from the mismatch between the pilot estimator Op and the underlying truth fn. creates central difficulty in the analysis for general 3 > 1, as discussed in Remark Due to the 0 term
tte existence of such ē, is straightforwardly ensured by T, + 0.
Note that when 3 1, the 2 0) (0) term does not appear since = 0.
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 Piloted Local Polynomial Regression
1: Inputs: pilot estimator 8g with |10g - Boll I n/ smoothness 8 2 1, dataset D = {ci, Ps, yoh- precision of partition h.
2: Initialization: partition [-V, V] into M = [1/h] equal bins J, JM- For j E [M], set
T = {i E [n] (c. .P:)', 2. 0o E 13}
and the polynomial degree c [8].
3: for j 1....... .M do
4: if T, * then
5: Pick arbitrary 2z I, with | S Ce + Pmax- For any 0 with ||0 Poll I n and any with x 8g Ij. define
6:
(2 0) (x =,) 0z (L.
and the Gram matrix A,(0) = EiET, Uz 0) (z 0)T. Set the local estimator
(x 0) (A,,)))))((0-1333)) A iET,
if A, (0) is invertible, else.
0,
7: else
8: Set (- (-())])) (0) = 0 for all
9:
Output (ā 0)) 1M
appearing in dj. we can only obtain an O(n) upper bound on (x) [o())l in general. On the other hand, carrying such an O(v) bound yields an overall rate of (TT)) = O(T 4013 far above the desired (T 2011 result.
3013
This suboptimal (1)) -order term in Proposition 6 is the main motivation for using refined estimator of 0o beyond the initial pilot estimation, leading to the constrained least-squares estimator for refining the parametric estimates in Section 4.2.
Remark (An O(T ) regret via Proposition without the first term). Since Proposition is quite general and requires no assumption how D is collected, in Appendix J we show that, when combining Algorithm 2 with an Cooper-Coniieenee-ee Boatreeee--uud-aeeeee algorithm design, an Ö regret can be achieved if the right-hand side of Proposition 6 does contain the vy(ar, 0) (0) term. While the omission of this first term is in general impossible, this discussion mainly illustrates how the problem can be simplified without it.
We also note that there are two special cases where such an omission can rigorously hold. First, when 3 = 1,, we have 8 0, and this analysis recovers the ÓTT2/3) rate in Tullii el al. (2024)², which minimax optimal. Second, the non-contextual setting studied Wang et al. (2021), where с = O and x = (0.p) only depends on price, one can show that v,((0,p) p). 0) 8,(0) = 0.
8+1 In this case, our discussion recovers the general OT ())) regret in Wang el al. (2021), which also minimax-optimal. We also note that throughout this discussion we do not need the strong uni mni-modality condition in Assumption 3, and in the second setting we do not need the diversity condition Assumption 4 for exploration. This matches the minimal assumptions used prior work.
Notation for Convenience: While Algorithm is described with flexible precision 2 T उ2-1 for
generality, throughout the main text we by default set h = n उтनт when inputted [D] n.
'It is worth noting that the algorithm in Tullii al. (2024) can work even in adversarial context setting with adaptive initial exploration, as discussed in Appendix J.

---

Published as a conference paper at ICLR 2026
4.2 CONSTRAINED LEAST SQUARED REFINEMENT
Using the local fits (- f) from Algorithm 2. we refine the parametric estimate via a constrained saus-squares (LSE) subroutine, a standard device semi comipparametric estimation, cf. Härdle al. (1993); Wang & Chen (2025). For each J E [M] (with T, defined in Section 4.1), define
02
arg min 5-
Σ (y. (x, 0))²
(2)
We have the following statistical guarantee for such constrained LSE under additional conditional independence assumption on D:
Proposition 8. Fix any E (). Suppose Assumptions 1,2 hold and {yiYi= are mutually independent conditioned on {zi]i=n Then under the condition that A5(0) is invertible and Ç x d-1
n 22341 = Odd log" (1/8)) /n), we have with probability at least 1 - (nő), uniformly for all with x TTo 0u I and [M]. the solution 8, to (2) satisfies
[0,(0| 0,) g(x T 00)l - Erry (x) + म VjE E [M] and Ve such that x =Tog E EI..
(3)
Where Erry(x) == (V (o/ll//(/)))))))) Aaj 2)T). (1, (2))) +1, and E,(0) EieT, (5 (v, 0)T.
Proposition 8 describes an error bound on the glued estimator
[(x) == Σ
jE[M] 1xT0 6. E 11)0, 05(2 10,)
which relies on characterization for the parametric minimizer (2). A key difficulty is the dependence: during the analysis of the constrained least squared estimator, the all samples in TT are used compute 8, and (-(- .),, this together with the non non-linearity introduced in the squared loss, creating complicated dependency structure. With the unified local polynomial approach, a key observation in our analysis is that such complicated joint-lease squared form can be reduced to the concentration analysis of a quadratic form involving observation noises, which then can be tackled via the standard Hanson- Hanson-Wright inequality.
To see why Proposition 8 refines Proposition 6 and yields improved regret, we argue in aggregate rather than pointwise. The right-hand side of Proposition has a self-normalized vector form, which implies the following bound under suitable distributional assumptions on æ and D:
Theorem 9. Fix j E [M]. Assume in additional to Proposition that T, allows disjoint decompo- sition T, = =T UT, with:
Samples from Tja² are i.i.d. from a stationary distribution Q, and 17, 2 [ng/2]. ii) For any 9 with ||0 Pull < 7, Amiu (HA)(H)))))) 2 yng with H = diag(1, (1, M M......MM- [((++)x((++1) and (0) == EiETTO Ug(X,, (),, 0)
M M-)) E
Then it holds with probability at least 1 - 8 that
EawQ, EEr, (x) S d log (1 - + n -nfr).
(4)
Theorem 9 states that under the distribution collecting subset of) D. one attains a parametric rate in n, and a (--dependent parammaettticc rate in n that matches the usual manimax-opptmml rate under /-- Hölder smoothness (Tsybakov, 2008). In particular, when is linear in T, which the scenario in our 28
subsequent regret analysis, the second term of (4) scales as n 8+1 improving the linear dependency rate as we discussed in Section 4.1.
Remark 10. In Theorem 9, we assume an (V(T)) eigenvalue lower bound condition on normalized version of (0),), mainly to carry out the perturbation analysis involving the inverse of the empirical matrix. By contrast, Lemma EC.11 of Wang & Chen (2025) states similar result for 3 == 2, but under the stronger condition (2) m nyI. As we note in the subsequent Remark 12, relaxing the
eigenvalue condition is key to extending the analysis to 3 2 2 while maintaining the T 20T regret.
7

---

Published as a conference paper at ICLR 2026
utility under row Pa
Texp (1,4,9,
This work: Ö 2+1
utility under rounded pi.
Lg
Wang & &Chenn (2025): 6(T 2541
Exponent in T
8,
Me = Pr
0
59 do 13
14 c.
1
2
12
+00
0j
bj
Smoothness parameter B
1 = lag. by]
Figure Total Regret incurred by linear versus sub-linear times of local exploration. The total cost of the local exploration operation (lines 11-13 of Algo- rithm 3) plotted. cach bin j and epoch т, the total exploration time of Wang & Chen (2025) ((n+s), 29 whereas ours is @((Trs), resulting in O(T re- d+1
Figure 2: Forced exploration via price round- ing. At the sy-th time that a raw price ps de- termined utility is piloted to interval J,. If the T.ytth element in Texp: the raw price will be rounded so that the piloted utility lies at the (Lş mod [&]))th equi-partiiin points of Iy. This figure illustrates the case sj = 4, 6, which corresponds to L,- 2-nd element of Texp-
gret and @ 2N+T regret, respectively, discussed in Remark 12.
HANDLING POLICY-INDUCED DISTRIBUTION SHIFT
Theorem 9 is stated under a stationarity assumption: the distribution of used to evaluate the expected gap matches the distribution of DD used to fit the joint estimator. This is generally hard to for regret-minimizing policies, which update adaptively and thus induce nonstationary distributions. To address this, we adopt the distribution-iie shift subroutine from the recent advance of Wang & Chen (2025) to design an epoch-wer wise algorithm, where the distribution mismatch between epochs is well controlled. that Theorem can be upplied to the regret analysis.
Similar to Section 3, since the design of the algorithm is fully credits to Wang & Chen (2025), we present only the key properties needed for our application here and defer the full algorithm to Appendix C for completeness.
Proposition 11 (Wang & Chen (2025)). Suppose Assumptions 1 and 3 hold. Consider a stochastic policy II containing all conditional uniform stochastic policies:
I {T:CC >(00, Punas)
(c)) Unif(T(c), (c)) some x(c) S F(c),
Then there exists an policy improvement oracle A (see Algorithm 4 in Appendix C for details), so that with any input tuple स E 11, x [0, Pmax] + IR, CB(.) : x (0,pmax] + R satisfying
(S1) p² (cT).) E (u)p(=(c)) for all c C
(S2) 7(x) - g(r 0o) S CB(c, for all x == (cT, TP)T with and E [0, Pmax):
Its output n² A(T, Ø. CB) E πI satisfies:
(i) (c E Supp( (up all e
(ii) E Ee-Perrt [8
(BCC, p' (c 0.)) R(c,p)) < [e BBC,, O.)) R(c,p))
181. Bew [B(c,)))
Proposition 11 guarantees the existence of a policy improvement oracle A so that its output policy improves upon the input policy in the sense that it discounts the regret of the input policy by factor of 1/4, and adding an expectation of the confidence bounds evaluated under the input policy distribution. This makes possible to apply Theorem 9 for regret analysis.
8

---

Published as a conference paper at ICLR 2026
6 THE LPSP ALGORITHM AND REGRET RESULTS
In this section, we put all components introduced from Section 3 to into an epoch-wise design to present our main algorithm in Algorithm 3. In Algorithm 3, after initial phase for calculating the pilot estimator Oo. the algorithm then enters an epoch-wise" phase to balance exploration and exploitation. At each epoch т, the algorithm posts prices based on a fixed stochastic policy x x(r-1) determined by the previous epoch, with portion of prices rounded for exploration. With such design, Theorem 9 can be applied to analyze the regret incurred by unrounded prices based on Proposition 11, and the key is to ensure the conditions in Theorem holds, which relies on the localized exploration procedure we introduced in line 11-13 (see also Figure 2), as detailed below:
Localized Exploration. The goal of the localized exploration procedure in lines 11-13 is to construct the 7700 part so that condition ii) in Theorem is satisfied. This procedure plays a key role on keep the design matrix of local polynomial regression cell-conditioned even without diverse context assumption in Assumption 4. To see how this works, we provide a high-level analysis for dg and leave the full details to Appendix Note that the normalized matrix HAP (0)) H admits a Vandermonde decomposition HA (0o) H = Zr Z with
Zr = [(1, A, hh, ..... (1,( (o)/1)9) EE [.9] ((++))(())
The lower bound on its singular values depends on the separation between A (Tz, 0o) for different t (Gautschi, 1963). The equi-partition rounding procedure then creates constant-level separations, which ensures that Amiu [HAR, ( H) = 8 (Z.,) 2 LB] Moreover, basic calculation based on the definition of Texp yields that L, = O Rr.j), which leads to the eigenvalue lower bound co /Tr.j for H (o) provided that nt,j exceeds constant depending only co B.
Remark 12 (Cost of Localized Exploration). From our exploration schedule, we have the total #+11
exploration step at the T-th epoch is given by O(EjE(M.) vTr5) O(,N,M,) ONN77T
Since Algorithm 3 stops after Oloo T) epochs, the total exploration steps amount to ④TT This
2+1
leads the ( total costs. In contrast, as discussed in Remark 10, Wang & Chen (2025)
8+1
requires linear-in-T number of exploration steps to sutisfy their eigenvalue lower bound conditions. They use uni-modality to control the local exploration cost, which results in a per-epoch exploration
29
regret of (, = O(N,
20-1 leading to a total exploration cost of iTTis While this rate matches their O(T3/5) regret when 3 = 2, it deteriorates when 3 > 2. This shows that shortening 5+1
the local exploration length to M, is crucial for attaining the desired Ö 2811) regret for general B, we illustrate the comparison of total exploration costs in Figure 3.
We provide the implementation details of Algorithm 3 in Appendix K.1 and claim the regret guarantee of Algorithm 3 as the following:
Theorem 13. Suppose Assumptions 1-4 hold for some 3 > 1, Algorithm 3 with hyper-parameters co No. C1 larger than some constant depending on 3 satisfies
Reg S 1og (TYT Poly(d T).
On the dependency on d. Our regret bound stated Theorem 13 has d dependency in the leading order term and Poly(d dependency in the second order term.
The source of the d' term in the leading order the in-distribution prediction error result in Theorem which is the consequence on using reff-normalized argument for bounding the E[||,,, 0,)11
and the union bound taken over æ and 0. On the other hand, the additive Poly log 2') term is a technical by-product of the covariance regularization used in analysis. Specifically, invoke Proposition 8, we require the matrix regularization level satisfy ( 2 d' 7/ so that the regularized empirical covariance dominates its population analogue, as required in Lemma 18.
'Epoch-wise convention. Throughout epoch we use the same constructions as in the subroutines but computed from the epoch-r dataset D, and partition [[]]a[M,,] for any quantity (,(+) defined earlier, write (+) () for its epoch-7 version (e.g., Ar.j Br CB,,,, Tr.))
9

---

Published as a conference paper at ICLR 2026
Algorithm 3 Local Polynomial regression-basee Semi-parametric Pricing(LPSP) Algorithm
1: Inputs: Smoothness parameter 3, total time horizon T, hyer-parameter co, No. Ci.
2: Initialization: лr (7( t- Unif[O, Pmax] for all c, pilot error level 1j = T
941
and exploration
length tg specified in Lemma 5. Epoch length schedule N, 2" No. T 2
3: // Initialization Phase as described in Section 3
4: Estimate the pilot estimator 0 and 0n (-0", ,1)T using t time-steps through Algorithm 1.
5: for = 2...... until meets / > T do
6: // Decision Making & Data Collection
7: initialize D-
Texp = [k² k #2 13, partition [-V, V] into M, == [N
equal bins
1,, 1,..... M, set I.j = 8. 0, vj E [M.].
8:
for ...................... Nr do
9:
Meets the t-th customer with context c, and sample pt (T)))) Compute u, : Pt c and compute Jr so that u, E Lie 8j. + 8/ +1 if Sj. is the L,-th element in Texp then
10:
11:
12:
Pt p. with p. c 0 is the (L, mod [8])-th [@] Sequi-partition point of Ij.
13:
L Lj b +1
14:
Present Pt to the customer and receive feedback yı- Add (c,, Pt. v1) to D,. +
15:
Compute T == {t D, xx To E [
17:
II Joint Estimation Phase as described in Section 4
18:
Obtain joint estimators (- (f using D, with Algorithm 2 and (2).
19:
Compute the glued estimator (x)) EyE[as11 1x:To, 0o [))ōr((1 0z.) and the glued confidence bound
(B) = Σ 1(x 0o E L} (BMT.))( N, 1
if (r,)) ea eo N otherwise.
JE[M,]
with Erry defined as in right-hand-side of (3) and Nr. |Trjl- // Policy Improvement via A described in Section 5
20:
21:
Update (r) + ((x(r-1), Gr. CB,)
Since our algorithm ties Ç to the pilot accuracy via Ç = x= 1 x T the above condition may fail for T S d², resulting in finite burn-in phase of T whose contribution is summarized by the (d log T) term.
A+1
We would note that, despite the heavy d-dependency is included due to artificial reasons as explained above, during the running of algorithm only O ((d))leevel confidence radius and (d2/Cmin) /Cmin)- level initialization period used, this may leads to much better empirical performance regarding d, as provided in our simple simulation in Appendix K.2. We believe that more careful analysis can either improve the leading-orde order d' depeendenccc or remove this burn-in without worsening the polynomial dependence on in the leading term, and we leave this refinement as an interesting future direction.
Finally, we would note that there are several future directions opened by our result, including:
Removing the Strong Uni-modality Assumption 3. While strong uni-modality does not drastically simplify the contextual pricing problem, we believe that the final step in this line of work will eventually match our regret upper bound without relying on this condition. In our analysis and algorithm design, the only part requiring Assumption 3 is the stationary subroutine we called from Wang & Chen (2025). Technically, we believe we have already moved a bit forward from Wang & Chen (2025) in the forced-ext eeccedeepploration by removing the need for strong uni-modality in theirs argument via sharper analysis, which might be a foundation fully removing this condition.
Achieving Adaptivity on the Smoothness Parameter 3. Another promising direction building on our work is to study adaptivity to the smoothness parameter 3. Following the progression seen in non-parametris bandits and pricing, where adaptive methods (Gur et al., 2022: Ye & Jiang, 2024; Gong & Zhang, 2025) build on earlier adaptitt algorithms (Hu et al., 2020: Wang et al., 2021), we believe similar adaptivity can be achieved in our setting under additional self similaiiyl assumptions.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work supported by NSF (CCF-2312205, ECCS-2411564) ONR-13983263 and 2027 New York University Center for Global Economy and Business grant.
DETAILS OF LLM USAGE
In writing this paper, the LLM was applied to polish our sentences and correct potential typos. In the experimental section (Appendix K.2), we also used an LLM to help organize the code structure and implement the benchmark algorithms.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Amine Allouah, Achraf Bahamou, and Omar Besbes. Optimal pricing with single point. Manage- ment Science, 69(10):5866-53 5882, 2023.
Gah-Yr Yi Ban and N Bora Keskin. Personalized dynamic pricing with machine learning: High- dimensional features and heterogeneous elasticity. Management Science, 67(9):559--5568, 2021.
Daniele Bracale, Moulinath Banerjee, Yuekai Sun, Kevin Stoll, and Salam Turki. Dynamic pricing in the linear valuation model using shape constraints. arXiv preprint arXiv:2502.05776, 2025.
Josef Broder and Paat Rusmevichientong. Dynamic pricing under general parametric choice model. Operations Research, 60(4):965-99) 2012.
Jinzhi Bu, David Simchi-Levi, and Yunzong Xu. Online pricing with offline data: Phase transition and inverse square law. In international conference on machine learning, pp. 1202-1210 1210. PMLR. 2020.
Raymond J Carroll, Jianqing Fan, Irene Gijbels, and Matt P Wand. Generalized partially linear single-index models. Journal of the American Statistical Association, 92(438):477-448 1997.
Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covariates.
Operations Research, 69(3):974-984, 2021.
Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, (6(11):499) 4943, 2020.
Antoine Augustin Cournot. Researches Into the Mathematical Principles of the Theory of Wealth. New York: Macmillan Company, 1927 [c1897], 1927.
Arnak S Dalalyan, Anatoly Juditsky, and Vladimir Spokoiny. A new algorithm for estimating the effective dinmension-reducttion subspace. The Journal of Machine Learning Research, 9:1647-1678, 2008.
Arnoud V Den Boer. Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys in operations research and munagement science, 20(1):1-18, 2015.
Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association. 119(545):552-5666 2024.
Sarah Filippi. Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
Walter Gautschi. On inverses of vandermonde and confluent vandermonde matrices. ii Numerische Mathematik, 5:425-430, 1963.
Xueping Gong and Jiheng Zhang. Parameter-adaptive dynamic pricing. arXiv preprint arXiv:2503.00922, 2025.
11

---

Published as a conference paper at ICLR 2026
Yonatan Gur, Ahmadreza Momeni, and Stefan Wager. Smoothhess- addaptee contextual bandits. Operations Research, 70(6):3198-3211 2022.
László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. A distribution-free theory of nonparametric regression. Springer, 2002.
Wolfgang Härdle, Peter Hall, and Hidehiko Ichimura. Optimal smoothing in single-index models. The Annals of Statistics, pp. 157-178, 1993.
Joel L Horowitz. Semiparametric and nonparametric methods in econometrics, volume 12. Springer, 2009.
Joel L Horowitz and Wolfgang Härdle, Direct semiparametric estimation of single-index models with discrete covariates. Journal of the American Statistical Association, 91(436): 1632-66063, 1996.
Marian Hristache, Anatoli Juditsky, and Vladimir Spokoiny. Direct estimation of the index coefficient in single-index model. Annals of Statistics, pp. 9955-63,,0 2001.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes. In Conference on Learning Theory, pp. 2007-2010. PMLR, 2020.
Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sls estimation of single-index models. Journal of Econometrics, 58(1-2):71-120, 1993.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9):1-49, 2019.
Adel Javanmard, Hamid Nazerzadeh, and Simeng Shao. Multi-product dynamic pricing in high- dimensions with heterogeneous price sensitivity. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2652-2657. IEEE, 2020.
Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi- semi-myopic policies. Operations research, 62(5):
Roger W Klein and Richard H Spady. An efficient semiparametric estimator for binary response models. Econometrica: Journal of the Econometric Society, pp. 387-421, 1993.
Robert Kleinberg and Tom Leighton. The value of knowing demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp. 594-605. IEEE, 2003.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Contextual dynamic pricing with unknown noise: Explore- then-ucb strategy and improved regrets. Advances in Neural Information Processing Systems, 35: 37445-37457, 2022.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution-fiet contextual dynamic pricing. Mathematics of Operations Research, 49(1))599-618 2024.
Sentao Miao and Xiuli Chao. Dynamic joint assortment and pricing optimization with demand learning. Manufacturing Service Operations Management, 23(2):525-555, 2021.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
James L Powell. James H Stock, and Thomas M Stoker. Semiparametric estimation of index coefficients. Econometrica: Journal of the Econometric Society, pp. 1403-1430, 1989.
Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates. arXiv preprint arXiv:1604.07466 074460 2016.
David Ruppert, Matt P Wand, and Raymond Carroll. Semiparametric regression. Number 12. Cambridge university press, 2003.
12

---

Published as a conference paper at ICLR 2026
Charles J Stone. Optimal global rates of convergence for nonparametric regression. The Annals of statistics, pp. 1040-1053, 1982.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
Matilde Tullii, Solenne Gaucher, Nadav Merlis, and Vianney Perchet. Improved algorithms for contextual dynamic pricing. Advances in Neural Information Processing Systems, 37:126088- 126117, 2024.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arX1v:1011.3027, 2010.
Yining Wang and Boxiao Chen. Tight regret bounds in contextual pricing with semi-parametric demand learning. Available at SSRN 5133677, 2025.
Yining Wang, Boxiao Chen, and David Simchi-Levi. Multimodal dynamic pricing. Management Science, 66660),616--112, 2021.
Zizhuo Wang, Shiming Deng, and Yinyu Ye. Close the gaps: A learning-while-doingg algorithm for single-produce revenue management problems. Operations Research, 62(2):318-33 2014.
Geoffrey Watson. Smooth regression analysis. Sankhya: The Indian Journal Statistics, Series A, pp. 359-372, 1964.
Yingcun Xia and Wai Keung Li. On single-index coefficient regression models. Journal of the American Statistical Association, (4(448):1275-122) 1999.
Jianyu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. In International Conference Artificial Intelligence and Statistics, pp.
PMLR, 2022.
Zeqi Ye and Hansheng Jiang. Smoothness-adapiiee dynamic pricing with nonparametric demand learning. In International Conference Artificial Intelligence and Statistics, pp. 1675-1683. PMLR, 2024.
13

---

Published as a conference paper at ICLR 2026
A OTHER RELATED WORKS
Dynamic Pricing. There are extensive studies in dynamic pricing (Kleinberg & Leighton, 2003;
Den Boer, 2015; Wang al., 2014; Filippi et al., 2010; Broder & Rusmevichientong, 2012: Qiang
Bayati, 2016; Cohen al., 2020). In the contextual setting with a linear demand model, O ((T))
regret can be obtained when the noise distribution is either fully known (Filippi et al., 2010; Ban & Keskin, 2021; Qiang & Bayati, 2016; Broder & Rusmevichientong 2012) or assumed to belong to a parametric family (Javanmard & Nazerzadeh, 2019). The cemi-paramttric setting considered in our work and Fan et al. (2024); Tullii et al. (2024); Bracale et al. (2025); Wang & Chen (2025); Luo al. (2022; 2024); Xu & Wang (2022) generalizes this framework by allowing the noise distribution to be fully unknown. Among these works, apart from those listed in Table I, Bracale et al. (2025); Luo et al. (2022) consider the 3 = case and achieve Ó(T3/4) regret, while Luo et al. (2024) achieves ((12/3) regret but additionally assumes an online estimation oracle. Finally, there also exist works that consider pricing with fully non-parametric demand (Chen & Gallego, 2021; Tullii et al., 2024; Javanmard et al., 2020) or other additional structures (Bu et al., 2020; Allouah et al., 2023: Keskin & Zeevi, 2014; Miao Chao, 2021), which are beyond our scope.
Semi-Parametric Regression and Single-Index Models. Our setting is closely connected to semi- parametric single-index models, where an unknown -indeimnnionall index is coupled with non- parametric link (Powell et al., 1989; Härdle et al., 1993; Ichimura, 1993). Classical work establishes root-n estimation of the index under regularity and recovers the link via -ieddimeniional smoothing (Klein & Spady, 1993; Ichimura, 1993; Carroll et al., 1997). Foundational kernel procedures- these analyses, with well-understood
Nadaraya-Watson and local polynomial regression-underyy uniform convergence and optimal-rate properties (Nadaraya, 1964; Watson, 1964; Stone, 1982). The literature also covers binary responses and generalized or partially linear single-index structures (Klein & Spady, 1993; Carroll et al., 1997), setting with discrete irregular covariates (Horowitz & Härdle, 1996), and single-index coefficient models under strong mixing (Xia & Li, 1999). Compre- hensive expositions and survey treatments Tsybakov, 2008; Horowitz, 2009). Despite this extensive theory, many results assume smooth design densities and emphasize asymptotics, assumptions that need not hold in contextual pricing where prices are policy-drice driven and the induced design can be irregular; hence the classical guarantees are informative but not directly applicable without further adaptation.
be found in (Györfi al., 2002; Ruppert al., 2003;
B PILOT ESTIMATION
In this section we introduce a simple pilot estimation stage under mild diversity assumption on covariates Amia [E]c 2 co/d. We estimate 0, by least squares. This procedure appeared Fan et al. (2024); we include it here for completeness.
Theorem 14. Let 0 be the output of Algorithm 1. Suppose that Xusin ( 2 co/d for some C O. Then there exists some constant Co > O such that for t 2 Cod, the following holds with probability at least Cop 2e -tColf.
d log(1/0)
||0 0.1 S Cop
Remark 15. For any target error level rJ, we may chooset = (dd (2)/ to guarantee that |10, 110-0ol1 S which results in regret of order (dd (dd3/// /
Proof of Theorem 14. Let H Pmax and for any 0 E Rd
[())
Σ (Hy - c. 2T2
tE(t)
We may compute the gradient and Hessian of [()) as follows:
2 Σ
VoL(O)
(c
Hyx) c, ERR,
tE(t]
14

---

Published as a conference paper at ICLR 2026
Vic(O) = - Σ act E Rddd
tE/t]
A second order expansion yields that for some 0 lying between 0 and 0..
0 (()) -(0.) (VoC(O.), 0.) (0- O2, V2 0.))
(VoC(O.), - 0.) 10 Pn, E
Gc. (0 -0,)).
re|t
This implies that
[.ae]] LE(t]
110 0.11 - 1 (0 0., Σ
Amiu
c.c (6 0.)) & (VoL(O.), - -0)
EEit]
Vol 110 0.1l-
Lower bounding Amiu( (: Elefe Gc.)). By the matrix concentration in (Vershynin, 2010, remark 5.40), there exists some constant > such that for t 2 ci d, we have with probability at least
1 2e -0t//d
Amin
1 Σ cc7
Amin (EcIc)
1 Σ oc.
Ecic
2
Ci
rE[t]
.E(t)
Upper bounding [/ Note that for any E [t] and i E [d], we have (c_] 0o Hy))
c.al S 1 and
E(c 8, Hyt) Cτ,i
E|c 0, Ct HBly c.] ct.
B 0. Ct HE|1(p: c. 0. + {.} q] ..,]
EEcc 0. Ct,; - FFcT 0. + |c] a.vl 0.
Therefore, by applying Hoeffding's 's inequality and union bound argument, there exists some constant G1 > such that for 2 Cid, we have with probability least C, that
log(1/8)
Ve S Ci
Combining the above estimates, have for 2 (G Gi)d,
C₁
d3 log(1/8)
110 - 0.11 5
holds with probability at least - C 2c -itt/d The claim follows by adjusting constants.
C DISTRIBUTION SHIFT SUBROUTINE
For completeness, we include Algorithm (adapted from Wang & Chen (2025)). Given a prior range (I()), [c))]. estimator g. and an envelop A, the subroutine returns renewed range (c), for uniform pricing.
D PROOF OF PROPOSITION 6
Recall that for any æ with x T 0. E 1z.
(x 0) = U,(2,0) T) (,,,0))7;'000 A Σ Y.U, 0).
(5)
3ET,
15

---

Published as a conference paper at ICLR 2026
Algorithm 4 A subroutine for handling distribution shift (adapted from Wang & Chen (2025))
1: Inputs: (<I(c), (EC), A(:-), ((..), = /2/,//r, & - T
Input parameters: prior policy that offers price p (ni [())) error quantification (ss )) estimated model I C x Pmax] + [0, 1].
2: for every с < do
3: Partition J = (c), [(c)] into K intervals of equal lengths, denoted as J1....,JK' write Juul for length and Jn [p(k). p(k)..
4: for k: = 1, ..., K do
...., Estimated average reward F(J&) and uncertainty quantification (J)k)
5:
F(J+) |Jx| Sr, PO( p)dp; A(Ja) < [ Sr, p)dp. Find the optimal price for context together with its uncertainty A
6: k + arg max f(Ju); Á + / max A(Jx)².
Update the pricing range for context c, by stretching out Á from the price interval Jg
7: (r) (c)) < [p(k) A, p(k) + A] n [0, Pmax]
8:
return (c))cE
& renewed policy p (ni((
and = (0s--,)) 22) ...., (
(x- ((;o=zz)T)) =²))))² Recall also that uy (z, 0) = X 0 (x, ( A, Ei)EieT, Uz(2;, 0) X, 0) and 2,(0) = Eier, (2 f)0, (2, O)T. For any 8 with ||0 Boll $ we set
(2 0o) (A - 0n) 7))
8, (0) = ( 6o) -00
Let h
We first decompose the error as follows: for any x such that x 0u E Is.
5x (x 0) g(x TaT) 0o) 3y(2 0) 0) (z 0o) + 9 (a 0o) g(xTo)) 0o)
(6)
Estimating Σ, We begin by expressing the response as 1/: - ( 0o) + e.. where E[s, [.]] O. Then based on the closed form (5), we can further decompose I, as follows:
I 0) 0)
E LET,
g( (0), - Uz(2, 0o) T
g( (00)
LET
==
+ {U,((e,0) Σ e.A (0),((0) -U, 0o)
(0)
BET;
IET;
Z10
Consider the [odder expansion of g(-) at x To for each I, we have by B-Hölder continuity and 17 $ h,
g(x, [) U,(, +
for some & = (..). Then we have
In (2,2, T) Σ (2)00 - Σ (7
IET,
IET,
+ +U,(z,0) 0)
(01,, U, Σ 1 (8,)U;(I1,00)
TET,
@ U21 Σ
00 Uz)
Σ
SET,
tET,
16

---

Published as a conference paper at ICLR 2026
Ux; 0)
Σ E,A7 0) U,,,000) Σ (O)U,
BET,
LET,
-U,(2, 8) Σ A (I,
U2(2, 8)) Dj
TE
+U,(t,, U, 0o))
EIET, AJ (0) (s,, Dj
+ U2((2, 0) T (0), 0) - U,(2, 00)
Σ SAj (o,) 0o).
(7)
tET
TET;
Here, in (i) we have used the identity EIET, U,(,, (,U;(r,, 0)T A,) for all 0. Now noticing
that for any 1 S S [8].
(j 0o) - A5(x, 0) = ((x - xz)) 00)* - ((x 82) To)²
=((2 ,z)) / 00)=- (x 5z)) T(00 - +0+++00 0
we have
D
Dj
g'(:J0o)
(A) 0) - (2)
(z) 0) - - (z, (0)) (x)
LA (5) Bu)
g' (a) J (0) 000
[B](( - T)) xx))
+0(17),
(LA (z 0o)
=x] (x.0)
(0 0o) [+]
(6)
we can further writing Zi as
In (x, (0) =x(((,)))),(()+++0)))) - () - A7) Σ ()) 0()2))
TET;
-(l,,))-U((z,,0) A7 Σ IET Uz(22,0) Xx( 0)
6,(0)
(2,0)
+ +0 (1 01l,, )(0))),
where we have used the Cauchy-Schwarre ineuuaaassssssseuliiiiy inequality:
TE
1/2
S 12 ()
Σ
LE
-0)
This completes the estimation for Z₁
Estimating Iz. For Iz, have
Iz ==,(x;00)
Σ
y.77 (8)7 (0,)U, 00) g(x=To))
IET,
= =(U,(1,00) 00)
Σ
(ve- g( (00)000))11111 (00)U, ( 00)
1ET,
17

---

Published as a conference paper at ICLR 2026
+ +(Us(e,B0)) Σ
g(x,
g(x g00
IET,
-(()(2,000)
Σ (6))
1ETg
+(Ug(e, Bu)
Σ
g(0) 00)A, (zo)) (100)d6))))))))))(((x))) 1(x -(xxoo)
TET;
-0) T Σ
, (6o) (8)0(())))
1ET,
+ +(,)(e, Bb)
Σ (7 D - g(x 6b)
g(xT6n)
LET,
0o)
Σ (6))
1ET,
= -,,(0, 0o) T Σ (66)U, (2e, 00) + (2 (o)
Σ (60))(00)
IET
TET
+U,((,,0)) Dj -0-gle g(x To(T00)) 00)
=0(ha)
This completes the estimation for Iz.
Combining two expansions and canceling red colored terms and blue colored terms, we have
(x 0) g(x T00) (xx +, 0)T EA (0),((0),(
KET
+ Uz, Σ (0),, + (1) + ( 0)],, (0))
TET
Finally, by Cauchy Schwartz's inequality, we have the third term can be further bounded by
O) Σ (,), //2 0)1,, '(0)>
TET
This concludes that proof.
E
PROOF OF PROPOSITION 8
The proof of Proposition 8 relies on the following two lemmas, whose proofs are deferred to Appendix
H. Recall that h n 2341
Lemma 16. For any 0 with 1|0 0 || S n, it holds that
(x 0) g(x To.Ton 0o) 2, (x. 0) 5,(0) + (x( Σ (0),
BET,
+ (1 (1 + 011xx
uniformly for all with T 0g I and E [M].
Lemma 17. For any 0 with ||0 Bull Σ n, it holds with probability at least 1 - O(n,5) that
(,) Σ (v: (M: 10)) Σ Et ((0000000)) 1T
IET,
+ (Tg((118) (00661)))66,000010 (00(00)T,,,00,000)+++, + log(1/5) + -nnh2))
We now prove Proposition 8.
18

---

Published as a conference paper at ICLR 2026
Proof of Proposition 8. In the proof below, consider such that x Bp Iz. Recall that 8, arg minlje- (0) and we write 0 0g for simplicity.
follows from Lemma 17 and standard s-net argument over lelednnng to an multiplicative factor before log(1/6) that
())
Σ LET
E +
+ + (VVllog(1/0) [,,,0,,,,00),,00 + tngh20) + dlog(1/6) + n,h2
holds with probability at least log As () - (0))) we can derive that
(0) (0)5 ( n
S dllog(1/0) 6, 2, (0) 6 (0) + nzh22 + d log((//)) + +n
Using the facts that a² ba b Va, Va, 0 and ())) 1 O(1), we obtain
+ $ /llog(1/8) + (d [o ( n, h2h 1/2
V [0,000,
V (T, (,) S dloo(118)) vn,h?.
On the other hand, by Lemma 16, we have
(z 0) g(xx 0o)) s v,(x,0)T8,(0
+ U,(tr, Σ (,),(00,,(EE,0))
LET,
Vi
+ +o(n'( (1 (n, (0)
Term V1: Using Cauchy-Schwarz together with (8) yields that
S (Vdlog(1/8) + vishh
Term D2: Applying Hoeffding's inequality with an s-net argument, we have with probability at least
1 (() that
V/2 x V /loggL/0)Usxxz0))11 (z, (,),,,,
Combining the estimates for V1 and V/2 concludes the proof.
F PROOF OF THEOREM 9
For any j E [M], let a,a be the index set that collects the samples that are sampled i.i.d. from stationary distribution Q, and T := T, T, Let n. |7,a| and n = (T.o). Then we have T, = T7a U THo and ny n n.. The population level quantities are defined as
Vy(0) = E,nq, (2
Σ 0,(
n TET
1
1,(0) = Ez~q, (U,(2,0),5(z 0
Σ
TE
1²(x,0) 0) = X, UJ
(c. (), (0),((0,
Eg( := Σ
(Ie, (1) T)T.
19

---

Published as a conference paper at ICLR 2026
Lemma 18. Assume the same conditions as in Theorem 9. It holds with probability at least - O())
that uniformly for all such that x' 0g 1g and 0 such that 110 Boll 7/
(i) [10)(2.)) - 01(2,,0)12 d log 3/2 (1/6)) (n5
(1--11 (1, 0) x7))) + / (1)1((6))))
(ii) Moreover, = log 7/2 (1/8) m1). we have
12(2, (I, + (1) 0) S (2, (1)
+ log (1/0) ( 0|1 (()) ( 011 (0))
The proof of Lemma 18 is deferred to Appendix I.1. Now we prove Theorem 9,
Proof of Theorem 9. Recall that h n कगनर and Exr,(x) = (v log((11))) + v,,h") (1l,
(
With Lemma 18 and the fact ( ス " 1/2 we can now define the population-Ievel confidence bound as
Exr == (Vllo 16) + vu,h²) (1 (z. B2) (1) + (r, 0, 0,)11 '(0,))
+ / Log
3/2 (1/6) (15 |1; (2, 0, || (0,) + (1 my [1, 0,) 1, 1/2
follows that for any x ~ 2j if ( = 17 2 l(dd log 7/2 /T))
Ez-q, [x)r S Ez-o, [rrr
Let
(xr,a(x) = V (0,
Exr,2(z)) = n1] ||0, 0,) 8,)1 (1 + nzh28) 1|,, (2,((,,))) 010)((2,)))))
We then have
Bx Eir, = (Vdlog(1/5) + vRr E Erry, (x))
+ 122 log 3/2 1og (1/6)) (z)),
Bounding Ex~Q, EET₁ (x)]- As in proof of Lemma 18, we decompose En into
(, = Σ (1,, (Zx, + Enery 0 ((lx,0,),, 0, (z 0,) + +CT 2 (,)
IET
Then by Jensen's 's inequality,
E [Err, (x)] < / (b,- 0,) (0)0 (xr) 0,]]
V B (ū (I. 0,) (1(9)) 0,)
1 (Z,) -(T) + (())) (Ep(() (T)) 1/2
(155)) (0,), Ey Eg,a, (2, (z, 8
(z. 0,)
n,
n
=00/103)
1/2
Son (5-vvdlog((/0)) + 1/ng)
2 / dlog(1/6)//g
with probability least - 8. Where (i) is by matrix Hoeffding's inequality and simple union
bound, (ii) is by (0) = <I 2 n 21 and n x nj. Therefore, we have with probability at least 1 8,
(Vdlog(1/8) + 2 Err,,1 (x) & d 2/2 n 1122 + 1 Vd Vdlog(1/0)
20

---

Published as a conference paper at ICLR 2026
Bounding 2
ErT (2)).
By Jensen's inequality, for every j with n, 0,
Q (x))
(1 kn)h))
n3 E ( 02)11 (/)(0)) + Rn- [,),,
1/2
=(1+ vnzh(). (A7 (1, -/2 -T
(AT())))7' =un (11)
n
-0(1)
Sun V /log (1/6(1/))/ng + h / /dlog(1/8)
with probability at least 1 - 8. Where (i) is by matrix's Hoeffding's 's inequality and a simple union bound, (ii) is by
(A (AT(0)))7710))))-
= DUlan (0,,,,
TE7
- Σ
Uz(t, (0,,((,,,,, O(1),
TET
(iii is by 3 3 (0,)
Now we arrive at the same bound as in Erry.1:
1 log 3/2 2/2
(Br, & d log (ogg((1/) nz + d log (1/5) -h9,
thus the same argument leads to the desired result.
Combining above bounds, we have the desired result.
G PROOF OF THEOREM 13
Let Пz. = |T>pl- According to the algorithm design, the regret splits into the contribution from uniform sampling and the rounding term:
[log
(egrety(T) S
N En Few Per (c, 0.)) r(c_ r(cT0.,)) 0),
Mog, T
Mr
E
1 (x
Oo E [
The first sum is the uniform sampling regret. The second sum is the rounding regret. Bounding the rounding regret. By Cauchy-Schware inequality,
Doga T
Mr
[log T
2T
E
1 fx T 0o E [s)rnn
N No
/2 2 VT.
Bounding the sampling regret. For any 2 0, recall that
Exr,y(x) (VVdlog(11/)) + Nr कهना)
x (11 (z, ,r, (0.))( + (,,(z,0,)) (1:01:11)))
For any T 2 O, we define the event
T 0o E (r)))r,(()) N, x
27 = (x) g(x
0o)1 (x)Tl
Σ
jE[M,]
21

---

Published as a conference paper at ICLR 2026
p" (c (c) Vc E C, E Pmaxx] and (c .p) Tp]T.
It follows from Proposition 8 that PP
P(N
Dog 21 9)
87 log2 T.
On the other hand, by the definition of the rounding samples, for any unit vector R n HA, (0r,))
Σ
u u Z Z
A
min kelLymra//(01+1)
min (Zx) 2 T
[ +1
where 2g is (13]+1) dimensional Vandermonde matrix with ((1) separation and in the penultimate step we have used (Gautschi, 1963, Theorem 1) to derive that min (7x) Z 1. Similarly, we have
u A (0rg) Hu Reng
(10)
So when (= x 17- 2nd log" (1) Theorem 9 is applicable and with Proj being the distribution of (c p)T such that Pe,p (c) 7-th epoch condition such that x 00 Ij. we have ((, Blog, T
25 2 - 8T logg T, where for 2 O,
23 = ( (Ez-r., [Err,, (x)) S d log (1) 1/2 + N₂ IITI, Vj E [M+]]
Let P. be the distribution of x = (c p) such that c ~ Pe,p ~ x (c) at T-th epoch. The Chernoff's bound yields that IP( (PN (N
Dog. 1'l 2g)) 2 - 87 log T, where for 2 0,
22 = iints + 1 1 max [B[n..] v E (lg.)loo(1/0))00) + +1, Vj [M]]].
Therefore, on the event N,20 T (22 n 22),, we can derive that
EgPP:
Σ
1fx 1 Bu 1j} EIT,, ErT+,(a))
Σ
Pr Bo E 1z)Be~Pr, [E)),
JE[M-]
SE[M+]
$ dt log (lgg))1/)
Σ
P. 8. E (m 1/2 + N₂" )
jE
Pr 0o E 13)
$ <d log" (d'1o22(1/8)
Σ
+ N₂ 20FT
nt +
jELM-
(1
N Σ (
= =o"log" 1086)))))
+ Nr 2847
(N
MTi + -1
JE(M,]
(
(V..
Mr Nr
S dt log
log 5/2 5/3(118)
+ N 2F4T
(11)
where in (i), we have used the elementary inequality
max (a- Vac, 0} +1 Se+1, Va,e> 0.
a
Write Ω Blog 17 1(2 0ig n (g). By Proposition 11, for 2 1,
Egy Be- (r(c" 0.,p' (c 0.)) - r(c r(c pi]
= E Bew to o., p (c 0.)) r(c e., p)] 1 1
+ Ex E Ear Boro (c 0,, (cT 0.)) - r(c ((CTT.,,00) 0.,p)) p 1(099
22

---

Published as a conference paper at ICLR 2026
$ - Ex
te p,, r(cT00,) 0., p)] 1[2}]
+ Ex Eawp, Σ
1x 0o 1,} Errr,( 1[03] Pmax
JEIM-1
< Ex Bew Pe-rore Me
0n,p"(c' Me. r(c' S(cTTo.001 0., 0..
+ + lo 5/2 1o (1/0)) (V /M + Nr .847 )
Mr
+ 8T logg T
N
By choosing å sufficiently small, i.e. 8 = T arrive
Eg E Pe Ir(c (c. 0.)) r(c [C....]]]
((TT(ooo Σ Bn Per "o]l(( 0., 0. (c 0.)) r(c" 0.. 0r. +0(ct 1og"/((1) 20(2log"/((1)) -N= 2olI
Iterating the above bound, we have
[log 77
(c)) Er Pe Po 02, p' 0.)) - 0r, p..
S No + dt log" (TT) T T S dt log 5/2 (T) 2+1
Combining the rounding regret and the sampling regret, we have if qf ((d log" 2 = T = ad loddlog" (T))
T T
Regret((T) x d log (T) (T) Adding the burn-in time term completes the proof.
H PROOFS OF LEMMAS IN APPENDIX
H.1 PRELIMINARY NOTATIONS
For each j E [M]. we denote Dj = (Djo...., E RIø1+1 with Dja (x]] for
s!
E (0, 1..., [ under which the local polynomial expansion of æ.. 0 to (3] order can be written Dj (x, 8).
H.2 PROOF LEMMA 16
The claim follows from Proposition With n O(n - we have n?2 0(h(+11) O(h²).
H.3 PROOF OF LEMMA 17
Noticing that
()) =
Σ (yi - (z 10))= > (o(o) 0b) -2, ()) + =2)
TET
TET,
Σ
2
+2 Σ
( (I' () g T Bu) + Σ
[9(0, T Oo)
2) (are [0)]
ct
TET
TET;
TET
independent
E2(0)
Lemma 19 (Bounds on E,), With probability at least - 0()), we have
(0) 0(
(v (
+1))
+ n2,220 +2,0+++,222
23

---

Published as a conference paper at ICLR 2026
Lemma 20 (Bounds on Eg). With probability at least 1 (nzz)), we have
( (,,,(()),, + (10g((1))) + n,h22).
The proof' for the above lemmas are defered to Section H.3.1. Combining the bounds for E2) we get the desired result.
H.3.1 PROOFS OF LEMMAS 19 AND 20
Proof of Lemma 19. By Lemma 16,
(0) = Σ
(x 0) (0) Σ 2...000 ((h)) +
Σ e (1,, 0(19) NET,
LET
IET,
+ Σ ()) Σ (
PET,
:=E12(0)
Term (0); Noticing that condition on {-a)i= {e) are mutually independent and zero-mean random variables. By Hoeffding's inequality, with probability at least (
(0) S vlog(1/8). (V0,10)T2,00)) + vT,h + Σ
nzU,(Er:0) ()) 1/2 129
TET;
Using the fact that
Σ 0)( EE,
ir (A7'(0) Σ
[,(0,,00(((,000] = -18] + -18 (12)
LET,
we arrive at
(1) z Vlog(1/6). (V6,00)),((06600)) + )
Term (z)( For j E [M]. let
E₁ = (E))TTT 12*,00 N,,, O2 (U,(,,, (, 0)), E x
Then (l) can be rewritten as
(2) = = C,e,
Applying the standard Hanson-Wright inequality leads to P((E12(0) - ( > u
S 2xxp ( -imimnn | I
u
for some absolute constant > 0. On the other hand, using the facts that
max JE(M)]
||C|ll V max ||C]|r= max
Σ
JE(M]
JE(M/]
1/2
Σ 0,(0,,)TAT7( Σ
( 0) A
1E
PET,
=A,(0)
1/2 (12)
0) 01
V +1
1E
24

---

Published as a conference paper at ICLR 2026
and |1, (1), may then select u 2 v /log(1/5) + log(1/6) obtain that with probability at least 1 - (d),
[12(()) R812(0)) v Vlog(1/6).
Finally, as
10)
z
max BE,,
R|c2] (M7',A) O(1),
BET,
we have with probability at least (6))
(0) 2 vlog(1/6)
This completes the proof of Lemma 19.
Proof of Lemma 20. It follows from Lemma 16 and the elementary inequality _a²² 262 s (a+b)² S
2a² + 21 that
(2() - -0,,00]2,0008000)) + O
Σ IET,
U,(oe,
0)T
Σ
AvA Ee (0),
VET,
:E2(())
+ +
1
nih Ug (1))))))
LET
LET,
(22
Term (e)) By Hoeffding's inequality, we have with probability at least 1 - O(n8).
(12)
(0) S log(1/8)
Σ ( $ log(1/8).
IET;
Term E2)( It can be directly bounded that
(12)
(e) S n2hh2 + +nyh
28
Σ U)(
0) S ngh20
TET;
This completes the proof of Lemma 20.
I PROOF OF LEMMA IN APPENDIX F
I.1 PROOF OF LEMMA
(i) Recall that H = diag(1 (1 h (h....,h) h²) (((+))x(+++) and h n z5-1
Note that
(5 0) u1,(0, 0)
(HU
-1, Σ
HU,( 0)
TE
R
+ (HUU)(,,))
Σ
HU -U
EE
:=
Term R2: For any unit vector w. let Y. ==
(U, 0) O)w.
Then we have
R2w
Σ
(Yi Ex,n, [Y)))
n2 IET
25

---

Published as a conference paper at ICLR 2026
As Amin ( A Amin (H), vnj, have |Yl E mi 1111, 1)7,, Using
further
0),, ",,
$ {U,(I,0) 1,, (100)sennel
Σ U,(,,, (2), (1))000 " TET
=x, A,
together with matrix Bernstein's inequality, we can obtain that with probability at least -((6),
log(1/6) Vma
R2w
(x, x
Now taking union bound over w in the unit ball, we can get with probability at least 1 - -0)),
dllo((1/))
R S
(1, (),0s,)) '00)"
Term R1: We first decompose the term as follows:
R1 = (HU,(I, (
Σ
O)
IET,
R11
(HU, (1 (
+ -(HU)(z,0)
Σ
LET
For R12, for any unit vector w. by Bernstein's 's inequality, we have with probability at least O
A - ) (7) Σ
R12w = (, 0) A
O) O)w
1/7
1ET,
log(1/6)
[1,
0))7
1/4
nj
where we have also used the condition that Amia (n) Ami (HA,(0)H) 2 vnj.
For R11, we have for any unit vector w. with (0) = E (x
Ruw = (HU,(x,)) 07) (
(HU) 0) HV
Rmn
+ ((30)))))0((,,000--~00000
Σ HV,(0)w.
TET
R
As Amin (n. (0)H) A Amin (HA Z Mrg.
|Rmll S ni 1/2 (x, 01) ;10) || HTHHA, (0) HA)(0)H1) -1 Σ ()(,,, - BRren - (1
TET,
where Yz(x2,,0 0) = ( EIET HU; (,xx( Oyw. Using (xt, Exi~Q, (x,, 0]1 Ex,~Qy 110 X(xr, 0) (HHU ( () 0)m]
26

---

Published as a conference paper at ICLR 2026
x Bur
E. Q (2, 00 - nj
n2
and (x 0)1 S o 1/2
min (n (A) S n 1/4 together with the Bernstein's 's inequality, we have
with probability at least - 0()),
1/4 Σ () Ez, ( 0)1 - (Vooo((100) + n4 log(1/))) A
Moreover, by the matrix Bernstein's inequality, we have with probability at least - (6) that
|n ( - HA,(0)HI2 x ny log(1/)).
Combining the estimates in the above displays, we have with probability at least 1 - O()) that
|Rnll & (og(1/0)]U,((,))) 0l1,7,
Next, we consider the bound for R112- Note that
R112 (1)) (0))) 1 n3 (A, HA,0H (,00:0000~~00000000000,,0"111111 huap://:1.....aaaaaaa.aaaaaa1a.0 (1,,0))))A,,)))))>>H)>) HV
(1 || HH,
1ET,
Let Z, := R f)w () can be rewritten as
the above term
R112 = (HU, 0)) (HA, (HA, (0)H)) 1 Σ (Z. - -E Z,)
TE
= (HU,((z,) (n (n 1
Σ (Z: - Buing 2+
TET
R1121
(HU,(,;))) - Σ (Z. Ex Zt).
IET?
R1122
For R1121, note that
Ž,
(z,
Vhg
and
E|ž?] = E,,
f)w (2) (4 11 1
So Er, [,, 1,000:/00000000/"/""0"0""0""""00 (,
< (,, 1() E, (U, 0) (0), 0))
Se n IU (z. 0| (0) R. (1U, (I2, 0) 11 1(0)) San " U (I. 0)1 1(0)
(13)
where (i) is by Jensen's inequality and (2, = 0(1): is E. |1 U, 0]1 [(,) 0(1),
(iii) is by
Auii (H),
Ex, (2,, 0)11 2109
max [|, 0)1 2())
TTJ.
2:2 del,
27

---

Published as a conference paper at ICLR 2026
Then may use Bernstein's 's inequality to obtain that with probability at least 06))
R1121 & Vlog(1/8)n | M)) + 1og(1/8)n,1/2113 (2,0))),,'(00)
For R1122, note that
RR122l s <1U,((,;0)AA7100)
with probability at least 1-0(6), S /vlog(1/0)
(1) 1/2
Σ (Ze ER,, 2,)
TET
It can be easily bound that
2 1 and by the same reason as in (i) of (13),
Bill(nAA, 1/22
< ElUJ (z.
1 Elur ()U,,,)UU,(() 0) 1000
ny
(EI )111 "13"" 1/2
Then we may use Bernstein's 's inequality to obtain that with probability at least 1 (8),
R1122 S (n//4 1og(1/5) + log (1/5)) (ogg/2(1/55)
(1, (1l,7))0)))))
Combining all of the above estimates, for any unit vector w, we have with probability at least 1 1- (O))
R2 w S log (1(/6) (1U,, (0) + +n//4lU,(z ))))))))))
Standard g-net argument then leads to, with probability least 1 0
||a 2 83/2
3/2 2/ (nj |U, ())a, + + ////|1U, 8) (0))
Therefore, with probability at least (6))
+ (2, 0) 0,,2,0)11 S 8/2 log" 3/2 (1/0) (n, 1/4 1U, 1 (1''115(0:00ll55>))))
The claim in (i) follows by further taking union bounds on x and 0.
(ii). With the bound in (i), we have with probability at least 1 - (()).
(z, 0) (0) 11,,, 8z oz -000 21
+ +,000000000000000000000000000010
(T) (6,7))))"_(()) 10,(,,0) 0)
2 - |, (z,
S dd log"
12 1,,00 + 8 (z. 8) (E, (0) + (,,
//2//////// 0) ())
where in (i) we have used ab S a² + 12. It remains to replace E, + by E, + ÇI. Note by the bound in (i), it holds with probability at least 1 - O68) that
Σ (u (z,, 0) - (x,, ()) (2,, 0) - 0, 0, 0)) TET
S d log (1/5)
> (m 11, 011,, :10 + 1),, (())
AET
28

---

Published as a conference paper at ICLR 2026
I d (1g/))))
Σ
1/2 (0;;;;;0000;; + +n)
"
1ET)
d' dolog2(1/0)
1/2
B,,) (Ze, (2,,,)) 210) + 1/2 Σ
Ex, (1,,, 0) :(o) + +n n3/2)
tET;
SET,
S dl (1/0)
1/2 Σ
E,, Bx, (0, 011 (00) + =n)/²)
tET
(ze, As max TōEI, (2, 0)],, (()) X vnj and R.,, (1t, 0]13, 2 '108 S 1, we may apply Hoeffd-
ing's inequality to obtain that with probability at least 1 - O()),
Σ ()) By(2,, (1) (z 0)) | FET,
S d log 7/2 (1/6) n//²
Then using the fact that b6 = 2aa + + b)(a - 6 holds for any vectors a, b, we have
+10 = Σ
0z(3e, 000 0) + CT
LET
2
Σ Uy (5 ()0 0)T + Σ (1y( 0) Üz( ()) oz(2):0)) C7
IET;
TET;
2 Σ
d= log (1))) vnj) 1. 1y (2t (1) CT 0
IET,
By the choice of ñ, we arrive at
(1
This concludes the proof.
J PROOF OF REMARK 7
In this section, we provide detailed algorithm design and regret guarantee with the first term of high--hand-side in Proposition is omitted. Throughout the analysis, we only use ge(- (o), thus we simplify the notation via
U,(), A₂ = A,
Moreover for the quantities (c.g. A,, Tr) defined in Algorithm 2 when it is called at t-th step, we use the notation Ar.g, Te,j to denote them..
Initial Exploration. the line 3-7, we first computing the rounded prices for every fine intervals (1g)ee(r))
discussed in Section 6 and rigorously proved in Appendix G. we have this ensures that when computing Ar,5 over each j E [MM] invertible and has the eigenvalue lower bound ((1/T)) for all subsequent t. The total regret incurred in this phase is bounded by the total exploration steps, which is given by
= ((VT/) O(Ta5+) 25+1).
thus suffices to bound the regret incurred over line to 13.
UCB Phase. In the UCB phase, we first compute a confidence bound on ÿe based on Proposition 6: when the first term omitted, we have the output 9r,( | 0o) satisfies
(x 0v) g(x g(x (b) =
[x) Σ (0,)) 2 (1 /t (1,
TE
for E, := - - g0x 06) and t, = |T.ll. Now for Aj, we have the following self normalzzdl martingale concentration result:
29

---

Published as a conference paper at ICLR 2026
Algorithm 5 Piloted UCB Algorithm with Local Polynomial Regression
1: Inputs: pilot estimator & with ||0b Boll & y, smoothness 2 L,
a >
2: Initialization: fix the polynomial degree level l [ D 0, set = T उ84ा partition
[-V. into M = [1/h] intervals {TyhSεM, =1
3: for j 1, M do
4:
for == ..... [vTh]] do
5:
After observing Ct, selecting a price ps so that x. 0o is the (L mod E)-th E-equi-partition point of Iz. //Forced Exploration for every Ij-
6:
Add Iy and the feedback to D.
7:
1+
8:
while << T do
Compute (- (b) for E [M] via Algorithm with input and precision T 25-11
9:
Glued Estimator:0,. (x)
Σ JE[M]
1( T 0o E 1,) (a (0)
Glued Confidence (o
Σ JE[M]
1(x 8o E [,),,,(()),
with CBr,, defined as in (14). Computing 91
10:
CBB (x) == (x) + (CB,(r) pull the UCB price so that for observed c, and
(p) = (c. P))
LCB (z+(p) To))
Pr = argmax pe Pmmaa) P
11:
Observe the feedback and add (2e())), v1) to D.
Lemma 21 (Theorem and 2 of Abbasi-Yadkori et al. (2011)). For any 8 > O, with probability at least 1 8, it holds that
Σ U Vlog(T/5), At [7].
SET,
Thus we have with probability at least 1 5,
A [U,(()) (To(T))))), Vj e [M].
And by T 284I, we can give the confidence bound as
CB,( = Σ Hl Go 1;} [1,(())] ( [og(T)) + 20t1
(1)(111()))))
(14)
JE[M]
it then holds that with probability at least 1 0((/T)
(x) g0x 0n) s (CB,(x)
uniformly for all at UCB phase and x for some large enough a depending only on 3.
As result, we have with probability at least 1 - O(1/T), for 24 := (cT,pe)'
Σ R(cr,pp' (cT 0.))
R(c,, pt) S Σ
UCB (U)B piot
(x.) - pig(z, Bu)
appmax Σ CB.
Σ Σ
1fx By E I1} (1U3(())la3 Vlogl Vlg((T) + T 2547
I Capmax
t. JE[M]
OPPmax Vlog T
8-1 T
+ Σ Σ
[1,(())lAa))
JE(M TET
30

---

Published as a conference paper at ICLR 2026
So o'max logT Thttt + log(T)
E
VT,
Sm oxpmax T T loga/2 T.
JE[M]
Where in (i) we have used the elliptic potential lemma (see e.g. Lemma 11 of Yabkki-Yadkori et al. (2011)) and in (ii) we have used
ΣV S VTM < TTT
A+1
desired.
Remark 22 (Adversarial Context Setting and Adaptive Exploration.). We note that throughout our algorithm and analysis, the only component that requires a stochastic context assumption is the initial construction of pilot estimator with error (n)), which is needed satisfy the conditions of Proposition On the other hand, in 3 = 1 setting, Tullii et al. (2024) propose an adaptive exploration procedure for estimating Og that works even under adversarial contexts. We believe their approach could also be incorporated here. However, since this discussion is intended solely to illustrate the difficulty created by the first term in Proposition 6-a ferm deliberately omit in our malysiss-we we keep our algorithmic design simple and aligned with the main paper's 's structure for clarity.
K NUMERICAL EXPERIMENTS
K.1
IMPLEMENTATION DETAILS OF ALGORITIM
In this section, we discuss several details in implementing Algorithm 3. Note that in the description of the algorithm, we frequently use quantities {r,()10) and {T(C))<EC for continuous spaces O,C. However, from a computational perspective, maintaining these quantities would require keeping parameterized functions simultaneously for all possible values of or over continuous range, which requires a discretization over θ, C, leads to computational inefficiency In the following, we provide details on how to efficiently bypass the operations that would seem to require maintaining these quantities.
K.1.1 CONSTRAINED LEAST SQUARED SOLUTION IN EQUATION (2).
Note that the only procedure in the algorithm that requires querying 7(100) for continuously varying 0 is when solving (2). An important observation is that, given the data {(x,, v1}} collected within each epoch, we can compute ((2,(6) for any 6. This allows us to rewrite the objective function in (2) purely in terms of 0, which can be evaluated directly using the collected data. As result, solving (2) becomes feasible using standard black-box continuous constrained-opimiizaioon methods.
We also note that, function of f, the objective in (2) is generally non-convex even when 9 (as in the setting of Wang & Chen (2025) and in earlier statistical literature such as Härdle et al. (1993); Ichimura (1993); Horowitz & Härdle (1996)). Following the approach of Wang & Chen (2025), we apply general interior-point method for this continuous optimization problem during the experiment. While this method only guaranteed return a local minimum, it already demonstrates good empirical performance in our implementation.
K.1.2 SAMPLING OF THE CONTEXT-WISS PRICING POLICY INTERVAL.
Another subtle challenge in efficiently implementing Algorithm 3 is that the context-wise pricing policy interval must queried at every round. Since this interval defined separately for each context over continuous space of dimension d, even an approximate tabulation would require storage that scales exponentially d. In this section, we describe a "lazy update" approach that stores only the historical datasets and computes the pricing interval solely for those contexts e that actually appear during online decision making. This procedure can be implemented efficiently by repeatedly calling the iilly--ipproemmet procedure (Algorithm 4) for Ollog T') iterations, thereby eliminating the exponential storage cost in exp(d).
NNte that both θ, are d-dimensional, and find its minimum s-covering requires 0( storage
31

---

Published as a conference paper at ICLR 2026
Roughly speaking, we treat the policy-imn inlloy-ippovemmett procedure used epoch É, denoted by Ae, an operator and store only the data required to evaluate Ar in future rounds. When a context e arrives in epoch T, compose the previously saved operators:
[x (c),, (c)]
(A.-10.... (c)
which exactly matches the interval that would have been obtained had we maintained and updated it epoch-by-epocte yet without requiring any per-context storage.
Data Required for Evaluating As. At the end of each epoch e, we store the dataset V that contains:
1. The pilot estimator and per-bin constrained least-squares estimators: do and (0e,s beJMan
Bin-wise local polynomial design matrices under Ōz.j:
{ (Ac,, (Oea):
Σ Ye U, (eil)
JE[ME
TET
This information sufficient for computing each (ūr, (I }r and the glued estimator ge(z) and its confidence bound (B) for any x (c.
Computing x (c) for given Suppose context is observed at epoch We now describe how to compute (c) from the stored datasets Uecr Ve. For each step & 1,2,..... 1, given the input context and the current policy interval (r) (c), 7 the algorithm evaluates the integrals appearing in F(Jx) and (J)k) for each sub-interval Jj using numerical integration with discretization length 1/s for E = 1/vT.3 This requires O(VT) queries to CBe(-) and ğe(-), both of which are computable from V/.
K.2 EXPERIMENT SETUP
In this section, we present numerical simulations under several setups to illustrate the performance of our algorithm and compare with previous work Fan et al. (2024). In the following sections, we describe the setup and purpose of four different experiments, including:
1. Illustration of the effect of B regret: given underlying smooth environment, whether using a larger 33 parameter in the algorithm input leads to better regret.
2. Illustration of the effect of on regret, especially whether the Poly(d") term in the main theorem significantly influences the empirical results.
3. Comparison with the algorithms Fan al. (2024).
8-smooth Tail Function Generation. Before describing more details of setup in each setting, we first recall the noise sampling procedure proposed in Fan et al. (2024) for generating a fm-smooth g. which we will frequently call in each setup: Given any smoothness factor 3o, we set the density function of & as
fz(2) x (1/4- 22)/2 1f $ 1/2].
(15)
can be verified that fa(-) is (B 1)-smooth function, thus its corresponding CDF( and g) is 3-smooth.
K.2.1 EFFECT OF ON REGRET
In Figure 4, we test our algorithm under a 2 environment with underlying smoothness 3n = 6, with the underlying parameter On = (0.25, 0.25), coordinate-wise i.i.d. context distribution with the density function
fm (z) x (2/3 22) m+1
1|10l S 22/3
(16)
By initialization, (0), x00)]= = Pmna]]
This contributes at O(1/VT) error the calculation, which is dominated by the CB(-) term.
32

---

Published as a conference paper at ICLR 2026
$2:00
6071
600
600
6001
600
Ciine 2010
(a) Relative regret( the regret normalized by 7) under 80 = 6, d = 2 environment with algorithm parame- ters 3 E {2, 4, 6). T < (50, 200, 500, 1000}.
(b) Same results as in Figure 4a with the starting point of cach curve aligned to illustrate the regret decay rate.
Figure 4: Illustration of 3 effect in regret.
Figure 5: Regret under f. = T 1000 environment, with changing d E {2,5, 10, 10,20) and algorithm parameters 3 E {2, 4,6),
We test the LPSP algorithm under this environment with input smoothness parameters 2, 2,4.6 4,6 and time horizons T (50, 200, 500, 1000}, and we report the relative regrets (regret divided by 7) in Figure (a)). To further compare the regret rates while reducing the influence of absolute constants, we additionally align the starting y-axis values in Figure 1(b).
From Figure 4a, we observe that larger values (3 4, 6) do necessarily lead smaller regret compared with 3 = when 7 is relatively small, likely due to the 3-dependent constants hidden in the regret bound. However, T increases, the performance of the larger-5 algorithms begins to match or outperform the 3 = 2 setting. Figure 4b provides more direct evidence of better long-run regret: after aligning the starting regrets for each 8, so that only the decay rate matters, we see that larger 3 generally leads to sharper decay rate, consistent with our theoretical findings.
K.2.2 EFFECT OF d ON REGRET
In Figure 5, we report the regret of our algorithm for 3 E (2,4.6) with 7 = 1000 under different dimensions d. As in the previous setup, the demand noise is generated with smoothness 3%0 using (15). The underlying parameter is chosen (1/ 1/Vd) RR and the context distribution follows (16) without additional normalization. Hence Assumption 4 is satisfied with
Gmin d, which implies an exploration length of order (VdT 2011
The figure illustrates that although the regret increases at least linearly in d, the choice of B does not appear to affect the growth rate significantly. This suggests that the Poly(d" factor appearing in our second-order regret bound may be an artifact of the analysis rather than fundamental barrier. The empirical trend also indicates the possibility of further improving the dt dependence in the leading-order term.
33

---

Published as a conference paper at ICLR 2026
(a) 30
(b) 30
(c) 90
Figure 6: Comparison with the explore-then-commit algorithm Fan et al. (2024) under different smoothness parameters.
K.2.3 COMPARISON TO FAN ET AL. (2024).
In Figure 6, compare the cumulative regret for T {50, 200, 500, 1000} of our algorithm with Fan et al. (2024) under different environments, with d = 2, 0o and context distribution described same in Section K.2.1, and noise distribution under different Bn generated as in (15).
While our algorithm achieves consistently smaller regret than Fan et al. (2024) in both experimental settings, emphasize that this comparison is not fully fair. The primary message aim convey simply that both algorithms are able to exploit the underlying smoothness: as the true smoothness parameter Bo increases, the regret curves decrease accordingly.
The key subtlety lies in the computational scale of the two methods. The algorithm of Fan et al. (2024) simple implement and computationally lightweight, which enables them run experiments with very large time horizons (e.g., up to T ss 12,000 in their paper). In contrast, our method involves several computationally intensive steps- such as the constrained least-qquars refinement and repeated distribution shift corrections as discussed in Section K.I. These components significantly increase runtime. which limits our experiments relatively small horizons (up T 1000). This difference in feasible scale may disadvantage Fan et al. (2024) in our plots: in their original setup, the initial exploration length is fixed 500, whereas in our smaller-7 regime we can only afford an initial phase of roughly 20-100 rounds. Consequently, their algorithm may not reach its typical performance regime under the smaller horizons we are able to simulate, We also emphasize that the primary focus of this work is theoretical: our goal is to push the boundary of regret guarantees for semi commmearaettric pricing by showing that improved rates are achievable -albeit through a relatively complicate algorithm that may yet be practical. Developing simpler, more efficient, and easy-to- implement algorithms that attain the same theoretical regret remains an important direction for future work.
34


Reviews:
[{"review_id": "pvWimJsbHS", "reviewer": "Reviewer_wC3A", "summary": "This paper studies a contextual dynamic pricing problem, where the demand function is semiparametric (as single-index model) and Holder smooth. The key demand assumptions are: (1) strong uni-modality (2) positive definite covariate matrix (3) monotonicity of the link fucntion $g(\\cdot)$. This paper claims the algorithm enjoys an optimal regret rate for general smoothness level $\\beta$, which directly generalizes previous result of Wang and Chen (2025) with $\\beta=2$.\n\nI am generally positive about this paper in terms of the problem setup and claim contributions, but did not check the key technical proofs line by line, and therefore have limited assessment on the correctness, e.g., specific critique of prior proofs (Appendix K).", "questions": "- The algorithm relies on the knowledge of $\\beta$. There is recently work on achieving smoothness-adaptive dynamic pricing in the non-contextual and linear-contextual case [1][2]. Can their approaches be potentially adopted here?\n- Can the authors comment more on the regret dependence on the context dimension $d$? Currently the dependence is $d^4$. One would expect the performances might deteriorate quickly as $d$ increases.\n- I understand that this work is mainly of theoretical nature. However, more detailed discussion on the numerical implementation or even including numerical simulations would strengthen the work. \n\n\n\n[1] Ye Z, Jiang H. Smoothness-adaptive dynamic pricing with nonparametric demand learning. InInternational Conference on Artificial Intelligence and Statistics 2024 Apr 18 (pp. 1675-1683). PMLR.\n\n[2] Gong X, Zhang J. Parameter-Adaptive Dynamic Pricing. arXiv preprint arXiv:2503.00929. 2025 Mar 2.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The studied contextual pricing model is fundamental and the regret bound result is strong.\n- The authors clearly articulates the difference compared to the prior work Wang and Chen (2025). Therefore, if correct, the result provides a solid contribution and fills the gap.\n- The writing is good overall with clear explanation on the algorithm design and proof ideas.", "weaknesses": "- The numerical feasibility of the proposed algorithm is not very clear and no numerical study is shown. \n   - The LPSP algorithm (Algorithm 2) relies on key smoothness parameter.\n   - In particular, Algorithm 1 produces an estimate $\\hat{g}(\\cdot | \\theta)$ for $\\theta$ lying in a continuous range. How is this facilitated in computation? Note that Algorithm 1 is called routinely in Algorithm 2.\n- The strong uni-modality assumption is still relatively strong, even if given the fact that several prior works also invoked it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZGnzsYM62y", "reviewer": "Reviewer_a8PW", "summary": "This paper considers the contextual pricing problem with binary purchase feedback, where a buyer’s valuation is modeled as a linear function of the context plus an arbitrary noise term whose CDF is $\\beta$-Hölder continuous. Depending on the smoothness parameter $\\beta$ of the CDF, this semi-parametric contextual pricing problem exhibits varying levels of difficulty, resulting in different regret exponents as functions of $\\beta$.\n\nWith an improved confidence bound analysis, the authors present a universal algorithm for semi-parametric contextual pricing with general $\\beta$, achieving a regret bound of $\\widetilde{O}(T^{\\frac{\\beta+1}{2\\beta+1}})$, which constitutes a uniform improvement over prior universal algorithms (previously $\\widetilde{O}(T^{\\frac{2\\beta+1}{4\\beta-1}})$ by Fan et. al.) and matches the optimal rates for specific cases such as $\\beta = 1, 2$.", "questions": "As mentioned in the weaknesses: where exactly does the $\\mathrm{poly}(d^\\beta, \\log T)$ term come from? If it originates from the burn-in time, where is that proved? Or is it considered a standard knowledge in this line of work?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Their upper bound is a uniform (i.e., over all $\\beta$) improvement over the previous universal bound by Fan et al. (2024) (although there is a difference in assumptions between this work and Fan et al.). In particular, the new bound matches the optimal rates for $\\beta = 1, 2$, where the previous bound had a gap.\n\n- The technical contribution through an improved confidence bound analysis is solid. While the framework builds upon the analysis of Wang & Chen, the extension of the analysis to general $\\beta$, especially $\\beta \\ge 2$, is non-trivial due to intricate dependency issues overlooked in Wang & Chen. The authors resolve this by directly using the analytical form of the local polynomial regression estimator and the Hanson–Wright inequality.", "weaknesses": "- While the bound matches the optimal rate in specific cases, there is no uniform (over all $\\beta$) lower bound for this setting. Although a non-contextual lower bound of $\\widetilde{\\Omega}(T^{\\frac{\\beta+1}{2\\beta+1}})$ exists and matches the claimed rate of this paper, that result does not rely on a strong unimodality assumption.\n\n- The regret bound’s dependence on the feature dimension $d$ is quite large, $\\mathrm{poly}(d^\\beta, \\log T)$ (Theorem 13), leading to exponential dependence on $\\beta$. It is not clear how this dependency compares with previous works on semi-parametric contextual pricing. Moreover, the origin of this term is not well explained in either the main text or the proof of Theorem 13. The proof suggests that it stems from the burn-in time, but it is unclear where this burn-in time is formally established. It would be helpful for the authors to discuss the origin of this term and potential ways to mitigate this dependency.\n\n- It would also be useful to provide numerical simulations supporting that this dependence is likely an artifact of the analysis rather than a fundamental limitation of the algorithm design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D9Kzaz3jyX", "reviewer": "Reviewer_tEP9", "summary": "This paper investigates the dynamic pricing problem, where a seller determines the price based on users’ contextual features (such as user information, time, and region) and learns the optimal pricing strategy from the observed purchasing behavior. The authors propose a semi-parametric model that combines a linear component with an unknown smooth function component to describe the variation of user demand with respect to price. They further develop a pricing algorithm that achieves a unified optimal regret bound across different smoothness levels β. Specifically, the study provides a unified treatment of contextual pricing problems under varying smoothness conditions β, overcoming the limitations of prior works restricted to β=1 and β=2. In algorithmic design, the method refines parameter estimation through local polynomial regression and constrained least squares, thereby improving convergence rates. The paper also reexamines the work of Wang & Chen (2025), identifies gaps in their proof, and provides stricter dependence control and theoretical analysis. Overall, the work demonstrates clear novelty in both theoretical depth and algorithmic design. By establishing a unified analytical framework across different smoothness levels β, it fills the theoretical gap in prior studies that only addressed specific values of β without a general analysis.", "questions": "See Weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Relevance: The paper focuses on a contextual dynamic pricing problem of significant research value. By introducing semi-parametric estimation into dynamic pricing, it contributes to balancing model interpretability and flexibility.\n\nTheoretical Work: The paper presents a unified upper bound on regret that continuously covers the entire range from β=1 to infinity. The theoretical analysis is rigorous, and the derivations are logically structured and well-organized.", "weaknesses": "Assumptions: The practical validity of assumptions is limited. (a) The strong uni-modality assumption (Assumption 3) may not hold in real pricing scenarios. The authors are advised to discuss the economic meaning, applicability, and necessity of this assumption in the main text. (b) The initial diversity assumption (Assumption 4) depends on the distribution of contexts, which may be difficult to guarantee in real-world deployments. The paper should discuss the potential effects when this assumption is violated.\n\nExperiments: The experimental section is weak. (a) There is a lack of comparative baselines; the proposed method should be evaluated against representative approaches. (b) Purely theoretical results are insufficient to demonstrate robustness. It is recommended to include empirical comparisons under different smoothness levels β to strengthen the persuasiveness of the framework.\n\nValidation: (a) While the research topic is practically meaningful, the paper mainly discusses theoretical pricing models, leaving a noticeable gap from real-world platform settings. (b) The absence of empirical or simulation-based validation makes it difficult for readers to assess the practical usability and robustness of the proposed algorithm on real data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gfer9xcgZC", "reviewer": "Reviewer_dJDh", "summary": "This paper studies the contextual dynamic pricing problem under a semi-parametric reward model. The authors propose a unified algorithm that achieves a regret bound of  $\\tilde{\\mathcal{O}} (T^{(\\beta+1)/(2\\beta+1)})$ for general smoothness levels $\\beta \\ge 1$. The general setting with arbitrary $\\beta \\ge 1$ has previously been explored only by Fan et al. (2024), whose method attains a much slower rate of  $\\tilde{\\mathcal{O}} (T^{(2\\beta+1)/(4\\beta-1)} )$. The proposed rate therefore improves upon prior work and, in particular, matches the minimax-optimal rates for the special cases $\\beta = 1$ and $\\beta = 2$ established in the literature. \n\nThe paper’s main theoretical contribution lies in an improved analysis that bypasses the dependence issue in the joint estimation procedure and relaxes the eigenvalue lower bound condition, thereby significantly shortening the required exploration period.", "questions": "1. What is the performance of the proposed method under adversarial settings as studied in recent works such as Fan et al. (2024), Wang et al. (2021) and Tullii et al. (2024).\n    \n2. The theoretical results assume that the smoothness parameter $\\beta$ is known.  Can the algorithm be adapted automatically to unknown $\\beta$?\n    \n3. Could the authors provide simulation results or comparisons with existing algorithms to clarify the empirical performance of the proposed method?\n    \n4. Please clarify how the proposed analysis bypasses the dependence issue between $\\widehat{\\theta}_j$ and $\\widehat{g}_j(\\cdot \\mid \\cdot)$. \n\n\n**Minor Comments**\n\n1. Table 1: Wang et al. (2021)  $\\to$  Wang \\& Chen (2025).\n\n2. Line 102: $\\tilde{\\mathcal{O}}(T^{1/3}) \\to \\tilde{\\mathcal{O}}(T^{2/3})$.\n\n3. Line 147: $theta0 \\to \\theta_0$.\n\n4. Algorithm 2, line 9: $p_t \\sim \\pi^{(0)}(c_t) \\to p_t \\sim \\pi^{(\\tau-1)}(c_t)$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper makes a strong theoretical contribution to the study of semi-parametric dynamic pricing, extending sharp regret guarantees to general smoothness levels $\\beta \\ge 1$.\nThe theoretical analysis is ambitious and technically nontrivial, especially the part dealing with the dependence structure and the weaker eigenvalue lower bound condition.", "weaknesses": "1. The paper includes no numerical experiments, either simulations or real data. Adding such experiments and comparing the results with existing methods would help demonstrate the practical advantages of the proposed algorithm, especially for smoother settings with $\\beta > 2$.\n    \n2. The authors emphasize in the Contributions section that they address a key challenge: the dependence caused by reusing the same samples $\\mathcal{T}_j$ to compute both $\\widehat{\\theta}_j$ and $\\widehat{g}_j(\\cdot \\mid \\cdot)$. However, the main text does not clearly explain how this dependence is theoretically handled. \n\n3. Section 5 is hard to follow. For instance, Proposition 11 is not sufficiently motivated or explained and only becomes understandable after reading Section 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "psjJc16JVg", "reviewer": "Reviewer_TBPD", "summary": "The paper studies contextual dynamic pricing with binary purchase feedback under a semi-parametric single-index model: the expected demand takes the form $g\\left(c_t^{\\top} \\theta-p_t\\right)$, where $g$ is unknown and $\\beta$ Hölder smooth, for some known $\\beta \\geq 1$. They design an algorithm based on local polynomial regression that achieves regret $\\bar{O}\\left(T^{(\\beta+1) /(2 \\beta+1)}\\right)$ for all $\\beta \\geq 1$, matching previous works for $\\beta=1,2$. Assumptions include bounded contexts, a strong unimodality/curvature condition around the revenue maximizer, and a context diversity condition only during the short exploration phase.", "questions": "1. I find the content of the paper really interesting, but it could be arranged better; for example, by finding some space for the related works and conclusions, and by retaining only the essential material in the main text. In particular, I think that Algorithm 4 in Appendix C is important enough to be at least mentioned or summarized in the main part, since it plays a role in the exploitation phase.\n\n2. It would be helpful to include an explicit remark in the main text explaining how the boundedness assumption on the covariance of the context can be avoided. If I am not mistaken, the key point lies in Equation (12), which essentially shows that the ``transformed'' $U$-based covariance matrix is controlled (specifically, equal to $[\\beta] + 1$).\n\n3. I am not sure about Footnote 3. It would be clearer if you specified which sub-results hold under the adversarial case and which do not. For instance, Theorem 9 (and subsequent results) hold under the stochastic setting (i.i.d. and stationary covariates). The sentence ``we keep our discussion in the stochastic setting mainly for clarity'' makes the scope somewhat confusing.\n\n4. The usage of the term \"uniformly\" is somewhat confusing. For example, in Proposition 9, the uniformity over all $x$ appears to relate to $\\sup_x \\|\\hat{g} - g\\|$, but the upper bound itself depends on $x$. This made me think that you might instead be referring to the intersection of events over all $x$ as in (3). If that is the case, perhaps the phrase \"simultaneously for all $x$'' would be less ambiguous. The same clarification applies to other results, such as Lemma 16.\n\n5. In Proposition 8, do you mean that the sequence $\\{\\xi_i\\}$ (instead of $y_i$) is mutually independent given $x$?\n\n6. In Theorem 9, you use the notation $\\mathcal{T}_j^{ro}$, but I could not find where it was defined.\n\n7. Line 147: $\\theta_0$", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Overall, the paper's primary strength is that it achieves the semiparametric optimal regret rate uniformly for all $\\beta \\geq 1$, addressing a long-standing challenge since Fan et al. (2024). Two additional notable contributions are: \n\n(1) the demonstration that the use of local polynomial regression effectively shortens the exploration phase, achieved without imposing a boundedness assumption on the covariance of the context, and \n\n(2) the establishment of joint convergence of $(\\theta, g)$, which I believe is of independent interest to the statistical literature.", "weaknesses": "The main limitation is that a similar result has already been achieved by [1]. Their approach is closely related, and their parameter $\\mathrm{\\beta}$ can also lie in $(0,1)$, not only on $[1,\\infty)$. Additionally, $\\beta$ might be unknown. In this latter case, they propose an algorithm that maintains the same lower bound $\\Omega(T^{\\frac{\\beta+1}{2\\beta+1}})$. It would strengthen the paper to clarify how your contribution differs from or improves upon this prior work. A good position on this would raise my score.\n\n## References\n[1] Ye, Zeqi, and Hansheng Jiang. \"Smoothness-adaptive dynamic pricing with nonparametric demand learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)