Context-Based Dynamic Pricing with Partially Linear Demand Model
Authors: Jinzhi Bu
David Simchi-Levi
Chonghuan Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Partially linear model
contextual dynamic pricing
online learning

Abstract: In today’s data-rich environment, context-based dynamic pricing has gained much attention. To model the demand as a function of price and context, the existing literature either adopts a parametric  model or a non-parametric model. The former is easier to implement but may suffer from model mis-specification, whereas the latter is more robust but does not leverage many structural properties of the underlying problem. This paper combines these two approaches by studying the context-based dynamic pricing with online learning, where the unknown expected demand admits a semi-parametric partially linear structure. Specifically, we consider two demand models, whose expected demand at price $p$ and context $x \in \mathbb{R}^d$ is given by $bp+g(x)$ and $ f(p)+ a^\top x$ respectively. We assume that $g(x)$ is $\beta$-H{\"o}lder continuous in the first model, and $f(p)$ is $k$th-order smooth with an additional parameter $\delta$ in the second model. For both models, we design an efficient online learning algorithm with provable regret upper bounds, and establish matching lower bounds. This enables us to characterize the statistical complexity for the two learning models, whose optimal regret rates are $\widetilde \Theta(\sqrt T \vee T^{\frac{d}{d+2\beta}})$ and $\widetilde \Theta(\sqrt T \vee (\delta T^{k+1})^{\frac{1}{2k+1}})$ respectively. The numerical results demonstrate that our learning algorithms are more effective than benchmark algorithms, and also reveal the effects of parameters $d$, $\beta$ and $\delta$ on the algorithm's empirical regret, which are consistent with our theoretical findings. 

Montext-Based Dynamic Pricing with Partially Linear Demand Model
Jinzhi Bu David Simehi-Levi 18, Chonghuan Wang
Department of Logisties and Maritime Studies, Faculty of Business,
The Hong Kong Polytechnic University
Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, Operations Research Center, MIT
Laboratory for Information and Decision Systems, MIT muizzi.bu@polyu edu hk, dslev isleviimit..o edu, chwang9@mit. edu
Abstract
In today's ' data-rich environment, context-based dynamic pricing has gained much attention. To model the demand function of price and context, the existing literature either adopts parametric model or con-paraettric model. The for- mer is easier implement but may suffer from model mis-specification, whereas the latter is more robust but does not leverage many structural properties of the underlying problem. This paper combines these two approaches by studying the context-basedd dynamic pricing with online learning, where the unknown expected demand admits caimmerretr partially linear structure. Specifically, we con- sider two demand models, whose expected demand at price pC R* and context o Rd is given by bp + g(x) and f'() + respectively. We assume that g(ar) is 3-Hölder continuous in the first model, and f' [p) is kth-order smooth with additional parameter 8 in the second model. For both models, we design an efficient online learning algorithm with provable regret upper bounds, and establish matching lower bounds. This enables us to characterize the statistical complexity for the two learning models, whose optimal regret rates are θ V T and θ(VTV v (8T*+1) कांh) respectively. The numerical results demonstrate that our learning algorithms are more effective than benchmark algorithms, and also reveal the effects parameters B and on the algorithm's 's empirical regret, which are consistent with our theoretical findings.
1 Introduction
The recent success of online retailing has provided data-rich environment for sellers to take better advantage of contextual information to dynamically improve their pricing strategies. Examples of such contextual information include products' characteristics, seasonality, festival information, economic indicators, etc. fundamental question stemming from the presence of contexts is how to select predictive model capture the relationship among demand, price, and context.
In the current literature, there are two modeling approaches. The first approach is adopt parametric model, among which the linear model, i.e., demand = b x price (a, context), is arguably the most fundamental one. The parametric assumption brings great convenience to practical implementation. and inspires many efficient learning algorithms. However, it may also lead to a serious issue of model miissspecificatinn, as discussed in (25). The second approach is to employ a fully non non-parametric model, i.c., demand #(price, context) for some unknown function μu(-) without any parametric assumption. The non- parammeatt model can be quite robust to different application contexts. However,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

it does not leverage many structural properties of the underlying problem that may have been detected from huge amounts of historical data, resulting in much complexity for learning the function ju()).
Motivated by the idea of combining these two approaches, in this paper, we study context-based dynamic pricing with online learning where the unknown expected demand admits semi- semi-parametrie partially linear structure. Such a structure preserves the advantages of simple interpretability from linear models and great flexibility from non-parametric models. Thus, it has also attracted significant attention in many other fields, especially when there exist high-dimensional contexts, such as statistics (13) econometrics (3)),, and biomedicines
Formally, consider a seller selling products over a finite selling horizon of periods. At the beginning of each period t, the seller observes independently and identically distributed (i.i.d) context vector It E [0, 1] E IRd encoding the product's 's characteristics and other exogenous information in period t. The seller then chooses a price Pt. from the feasible price range [p. p] (0, oo) and customers observe the posted price pt- The random demand D, is then generated according to the following function: De(P:) - u(P;, 2t) + St. where p(pr, zz) is an unknown function and { is sequence of i.i.d.
nab-Gaussian random variables (r.v's) with zero mean and variance proxy o², i.e., Blccss] s <e- 2g0 for any E R. We consider two models for p(Pt, Tt)::
Dynamic Pricing with Linear Pricing Effect (DPLPE): p(pt, bpt + g(xz) for unknown price elasticity b < 0 and 3-Hölder continuous function [0, 1] + R with smoothness parameter < (see Assumption []]:
Dynamic Pricing with Linear Contextual Effect (DPLCE); p(pt, xr) = f(x) + Ie for unknown
parameter a E Ied and kth-order smooth function f: [p. P] + R with degree & 2 1 and parameter
6 >>0 0 that capture how tightly f can be approximated by a polynomial function (see Assumption 2
The seller observes demand D, and collects revenue Dr. The expected revenue at price p and context is denoted by r(p, zz) = pH(p, 22) for any p E [p.p]. An admissible pricing policy и is defined as sequence of functions (T)(-) t 2 1}, where each TT(-)) maps the historical infor- mation (11, P1,
1 Pt 1. D xz4) observed up to period and possibly some external randomness to a feasible price in [g. pj. A clairvoyant optimal policy is assumed to know function d(-) and therefore always chooses the optimal price p == arg max (El.p ((), in each period
The performance of a pricing policy is measured by regret R (T), defined as the difference between the -'-period expected revenues generated by the clairvoyant optimal policy and by the pricing policy т. That is, R (7) Eí= Bir(pī, 2x) r(Pt, #:)]. where the expectation is taken over all the randomness associated with the environment and the algorithm.
1.1
Main results
Our main contributions lie in systematically characterizing the statistical complexity of the context- based dynamic pricing with partially linear demand models DPLPE and DPLCE. Throughout the paper, we use notations O-)). (?-) and O(-) to hide constant factors, and use O(-) (i-) and 6(-) to hide both constant and logarithmic factors.
Statistical complexity for DPLPE. For the first model DPLPE, we design online learning algorithm that integrates the ideas of random shock pricing in (25) and contextual space binning and approximation. We prove that our algorithm achieves the theoretical regret upper bound Ö ( v T ). We also establish the information theooretic lower bound 22 VTVTa442 for any admissible policy, which matches the regret upper bound up to logarithmic factors. The key novelty in our lower bound analysis is the construction of a family of nigh-dimensiooal 3-Hölder continuous functions. To the best of our knowledge this is also the first model that generalizes the commonly used Lipschitz continuous assumption to Hölder continuity in context- dynamic pricing, with tight characterizations on the regret upper and lower bounds.
Statistical complexity for DPLCE. For the second model DPLCE, we devise a different learning algorithm based on the biased linear contextual bandit borrowed from (32) and our new idea of being more optimistic chase the context-dependent optimal price. We prove that our algorithm achieves the regret upper bound Ö(vT (/p(++))m)) ), and also establish a matching lower bound Ω D(VTVV V (8I*+1) a++)) ). Since 8 is a parameter that depends the specific problem instance f(-).

---

we refer to the regret bounds we derive as the mustance-dependee bounds. To our knowledge, this is the first tight instance-dependent regret bound in context- based dynamic pricing with online learning. To achieve this, in the regret lower bound analysis, we need to construct family of kth-order smooth functions that are adapted to parameters and 6, which also new to dynamic pricing literature.
1.2 Related work
Non-contextual dynamic pricing. There is a vast literature on dynamic pricing with online demand learning without context. These works can be classified into two categories: parametric models (see,
e.g.. 77, 18] (88) and non parammetei models (see, e.g.. 44) [5]. (3). (23). We refer the
reader to 12 for a comprehensive review on this stream of literature. Among these studies, [32 is
the most relevant to our paper. 32] study dynamic pricing without context, and assume the expected
demand is kth-order smooth in price for some integer k. They design a learning algorithm by applying the Optimism-in-the- Pace---------------------------- wwwp-tee-aaace-o-----ntttttnnii Uncertainty (OFU) principle borrowed from bandits, and prove the
optimal regret is ((7 1+1 ). The idea of algorithmic design in our DPLCE model is inspired by 32) but there are two major differences. First, the optimal price stationary in [32], but can change over time in our setting. Therefore, the idea of multi-armed bandit protocol proposed in their paper for learning the stationary optimal price does not work. To overcome this difficulty, we propose a novel idea of being more optimistic over OFU in price selection to chase the context-dependent optimal price. Second, our notion of kth-order smoothness is more general than theirs by allowing k not necessarily to be an integer and 5 not necessarily to be constant independent of T. The general values of k and require a more careful selection of the parameters used by the algorithm, and a more sophisticated construction for the hard instances in the lower bound analysis.
Context-based dynamic pricing. There is a growing body of literature on context- based dynamic pricing (e.g.. [27]. [16). [22], (3. (24). We refer to 3 for a recent review and briefly discuss the works related to this paper. [27 consider the demand model a T x + bp in an mncumeent-rrcce setting, i... the expected demand for some given price is exactly known, and show that the greedy algorithm achieves the regret (log T). [25] study the same demand model as our DPLPE, and prove that the regret of a random price shock (RPS) algorithm compared with the clairvoyant who knows the best linear approximation to g(x) is O(VT). We borrow their RPS idea to design the learning algorithm for our DPLPE model, but analyze the regret of our algorithm relative to the optimal policy [ consider non-parametric demand model in context-based dynamic pricing. For the Lipschitz continuous and locally concave revenue function, they prove that the optimal regret is O (+ ). This regret rate is strictly higher than Õ( D(vTVV T (+F)) in our DPLPE model with B = 1 due to the separated effects of the price and context on demand we assume.
that knows the true demand model.
There is also a stream of works formulating demand using binary choice model (see, e.g., [6]. (2I] [0], (30] [34,, [4], [35], (20). Every customer buys the product with probability 1 F (p:- 0 Je). where F-) is the CDF of random noise. [4] 335 and (20) are the closest to our work. They also consider a semi- parametric form where F--) is unknown non non-parametric and @ is unknown parametrie. Conceptually, one can transform our demand model into the one where each customer buys the product with probability by; (a:x) (for DPL.PE) or I (p:) + a." xt (for DPI.CE), assuming bp: + g (Iz) and ff (pt) + a Ie fall in [0, 1]. Since the modelling approaches are different, we are also facing different challenges. Different from the binary model, we need to estimate and the non- non--onnnn paraamerreicc function g (-) at the same time for DPLPE (or and the non- non-parametric function ff (-) for DPLCE). Despite that we have an additive structure, it is still challenging to decouple bp: and g (xr)) for DPLPE (or (pt) and a x,, for DPICE) with only a muying/not-buying feedback. In our model, the distribution of random shock makes no difference to the optimal pricing strategy. Thus, whether the distribution is parametric/known or not not important in our formulation.
TTx,
Bandits with contextual information. The most studied model in contextual bandit is the linear 29.. 9 [.) where the expected reward is linear combination of
model (see, e.g.. 22 contexts. The algorithms developed in these works are mostly built upon the celebrated idea of the OFU principle. In our DPLCE model, we borrow the OFU idea to design learning algorithm. There are also a substantial amount of literature considering non-parametric reward feedback under Hölder continuous assumption (see, e.g., (28) (31) (26. (1)). Among these studies, (31] assuming a continuous action space is the most relevant to this work. For the general Lipschitz reward function,
31 proves that the optimal regret is ④ d-dp+1 42 where d and dp are the dimensions for the context
3

---

space and action space respectively. Letting d, 1 leads the optimal regret rate ( for dynamic pricing problem. This rate is strictly higher than the optimal regret ①( T in our DPLPE model with 3 1, and higher than (TT') in our DPLCE with A = 1 and ò (1).
Table T provides a summary for the main results of this work and the mostly related literature.
Table 1: Summary of the main results in this work and existing results in literature
Paper
Demand model
Regret upper bound
Regret lower bound
Key assumption
Dynamic pricing without context
18
+
O(VT)
((vT)
Linear demand model
f(0)
O(T5)))
R( (1T
f: kth-order smooth
Dynamic pricing with context
27
ar bp
OllogT T))
ftllog T)
Known incumbent price
25
bp g(x))
O(vT)
Q(vTT)
Benehmark: the best lanear model
X1
d(p,ar)
d: Lipschitz continuous
d: I. Lipschitz continuous,
d(p,a))
Oillog (((
A(T#))
smooth locally concave revenue
14
Ö(Ti+))
N.A.
c's CDF; ith kth-order smooth 2
35
O(TE)
STT5)
No distributional assumptions
This work
g(x)
ÖlvT (T=TT))
R(vT v T=
g: f 3-Höller continuous in [0, 1/4,
(Sec.
and Sec.
3
((p) +
Ö(VT v 1
D(VT v (8T*+))
Jt kth order smooth with parameter
2 Dynamic Pricing with Linear Pricing Effect (DPLPE)
In this section, we study the semi-parametric demand model with linear pricing effect, i.e., (r)) = bp: + (x+e). We assume that the unknown price elasticity b belongs to some known interval [b S 0). and the optimal price p. = g(arr) [p. Pl for any b E [b. b] and xt E [0, 1jd. We now formally introduce our assumption on function g(-).
26
The function g R2d + R is 3-Hölder continuous for some parameter < 3 S 1, denoted by E G(3 d), meaning that there exists constant L > 0, such that for any I 22 [0, 1]4. 19(x1) g(02) ) S ||=1 x2
Assumption
When 3 1, G(3,d) d) is the class of Lipschitz continuous functions, which is usually assumee in dynamic pricing literature (see, e.g., (8). We consider more general class of Hölder continuous
functions with arbitrary < 1.
We first propose Algorithm for our DPLPE model. Our algorithm combines two main ideas: (i) context space binning and approximation; and (ii) pricing with random shock.
Context space binning and approximation. To learn function g(-), the 3-Hölder continuous assumption guarantees that it cannot change dramatically in local area. This inspires a natural idea of dividing the context space Jo, 1]d into different small bins and using a constant to approximate g(-) in each bin. Specifically, we divide each coordinate of [0, 1]d into M equally sized segments and get Md small bins. We then estimate [[g((>)< E M,] (and (xxe) for any He E M2) using the sample average approximation (SAA) from the residuals {d. p.b. 15 S t-ttll 1, E Mý}. }, where 6, is an estimate for b to be discussed in the next paragraph. It's worth noting that there exists an important trade-off for the choice of M. If M is large, the amount of data collected for each bin will be limited, discouraging the success of learning g(-). If M small, we may incur larger approximation error of g(-) by using constant conditional expectation in each bin, leading to suboptimal pricing strategy and a greater revenue loss. The specific choice of M is given in Theorem |
Pricing with random shock. The idea of pricing with random shock is adopted from 25 In each period t, the algorithm first computes a greedy price p by plugging in the estimates for g(æx) and b, and then charges price Pt by adding a random shock A. which takes the value of o, or -8, with equal probability, to the greedy price pÝ. Following (25]. instead of regressing d, against the true price Pt, we estimate by regressing d, against the price shock A, Noting that
5 A.d. Σi (bp. (g(x))tt))))) b+
Σt 4. (b(.))))))) Since A, is independent of
ΣT A3
2 Σ.-1
Σ1 83

---

ميمر Σ.- 23
b + g(zx) + Eg for each and has zero mean, This also explains the necessity of regressing di against the random shock A..
is an unbiased estimate for b.
Algorithm 1: Algorithm for Dynamic Pricing with Linear Price (ADPLP)
Input: price range lp: p). bounds on the price coefficient and number of bins M 2 Initialization:
3 Partition each coordinate of [0, 11 into M segments of equal length, denoted as M, for
j j= 1, ,M
Initialize D1, for each j E [MI'] and bj b+b 2
Main Steps:
6 for f = 1,2, 2....... do
Set 6e +- 4-
Observe 2t and find j E [M such that 24 Mj:
de (di ppbb) P
If Dt. set āt. = (p + p): otherwise, set de.j
10 Set unconstrained greedy price: p." + #e.1;
2b.
Project greedy price: pt + Proj(pe lp + 5e.p-56]):
12
Generate an independent random variable A, t 62 w.p. 3 and A, + 67;
13
Set price pt < pt + A
Observe realized demand de:
15
Update D.+1,j +- Dr.; U {xt, d and D241.5 t Dr, for i i $j;
Update b < Proj( Ee A,d,
16
(A.)² 16, b));
17
end for
The following theorem shows the regret upper bound of Algorithm
1
whose proof is in Appendix A.
Theorem Let Algorithm I run with M
[
J. Under Assumption and the known bound
L. b) of the unknown the regret of Algorithm
δ Ö(VTVTaie)
The bound in Theorem I consists of two terms Õ(VT) and Ö(T ). The first term Ö( arises from our introduction of random shocks reflecting the complexity of learning b. For the simplest linear demand model without context, the squared estimation error incurred by an asymptotically optimal policy is in the order of 1/2 (see [18). Therefore, a cumulative regret ((VT) is in general unavoidable. The second term Ö(T ) is incurred by the inaccuracy of approximating the non- parametric function g (-) with constant in each small bin. captures the complexity for learning the non-parametric function 9(.). This bound is monotonically increasing in dimension d, which agrees with the intuition that a higher dimension of the context space leads to a more challenging task of learning the function g()). In addition, this bound decreases in B. This consistent with the fact that if g(-) is smoother (i.c., 3 is larger), it can be more accurately approximated by constant in local bins. We also note that only when d 1 and 1 is Ö(VT) larger than O(T=42s) ). Otherwise. the regret upper bound always ÖTT
We then establish the regret lower bound. We denote the regret of policy æ as R demand function bp + g(x) + e, and the distributions and e are P and respectively. We use E(or to denote the class of aub-Gaussian distributions with variance proxy o²
Rgb. (T) when the
Theorem 2
For any ((3,d), 0 < l < and 2 O, there exists constant K₁ independent of T, such that for any admissible policy
RTT (.P.P.D((T) (T) kn (VTVVTTT
sup 4) D)EE
5

---

Theorem 2 shows that the regret upper bound achieved by Algorithm I in Theorem Tis is unimprovable in terms of the dependency on the learning horizon T. The first lower bound Q ((VT) can be directly obtained from the existing literature, e.g., 17 To prove the second lower bound (T ) we construct a series of Hölder continuous functions in [0, 1] that are difficult distinguish from each other. We then apply the Bretagnolle-Hin bound the regret of any algorithm from below. See our construction and detailed proof in Appendix B.
inequality (see [6]) and KL divergence arguments to
We next compare our result with two relevant papers [25] and 8 In [25,, the same demand model bp + g(x) is considered, but the performance of their learning algorithm is benchmarked with the optimal policy for the "best" linear demand function. In this case, they show that the optimal regret is (vT)). By contrast, our regret notion is defined against the optimal policy for the true demand function, and thus, our optimal regret has an extra term ( capturing the complexity of d-2
learning the function 9(-). In [8, the authors prove the optimal regret (TT'a for general Lipschitz continuous demand functions (in both context and price) assuming local concavity of the revenue function. When B = 1, the demand function we consider here is a special case of theirs. For this case, our optimal regret becomes @(vT V T' ), which is strictly lower than theirs. This reduction of the optimal regret benefits from the separated effects of the price and context assumed in our model. In terms of the algorithmic design, the algorithm in { divides both the price space and context space into bins, and treats the learning problem in each small bin as independent ones. In our setting, we leverage all the historical data to estimate the price sensitivity and achieve information sharing among different bins in the context space.
3 Dynamic Pricing with Linear Contextual Effect (DPLCE)
In this section, we study the semi parameereetticc demand model with linear contextual effect, i.e., p(pr, x,) = f(.) + a It. We assume ||a|| I a for some constant a > 0. We now introduce our assumption function f(-).
Assumption The function f 1p + IK is kth-order smooth with degree 2 and parameter 8, denoted by f E Fk (p, 8), meaning that f is b(k)-times differentiable on [p.P] and
((b(t))) (p)
s 5 8pp pp'ppp"" x b(k) Vp. p/ E (p.p),
(1)
where blk) si :N:ie < k} is the maximal integer that is strictly less than k.
Eq. | requires that the b(k))th-orde th-order derivative of f(-) is (k - -Hölder continuous. This assumption also implies that all the ith-order derivatives are bounded for i < b(k) (i.e., Co :-
( (p) < oo). When & is integer, i.e., b(k)) = k - 1, Eq. 1 becomes the Lipschitz-continuous condition and Assumption 2 reduces to Assumption in [32]. Different from 32 that sees as a constant, we allow the order of ō to depend on T. e.g., 5 = OTT for some
SUPosisb(R) SUPpE|p.p]
0. As will be seen later, 8 shows how tightly (p) can be approximated by a polynomial function, and will have impacts on both the regret upper bound and lower bound.
We propose Algorithm@]for DPLCE. The key ideas are three-fold: (i) local polynomial approximation; (ii) biased linear contextual bandit and OFU; and (iii) optimism over OFU for price selection.
Local polynomial approximation. The idea of local approximation for smooth parameeriic functions through polynomial functions is borrowed from (32]. Specifically, we partition the price interval [p. pi into N segments of equal size, denoted as I .I. For each price segment I, := b(A)
(p (p-aa a;)', , to locally approximate the true function f()). To learn the the coefficients of (p), we apply the ridge regression method. By our assumption that ((b(A))()) (k b(k))) continuous, it can be
(o,. we use a polynomial function of degree bkk): Pt, (p) := b(()) (()
i!
verified from Taylor expansion that (f(p) - (p) S (1--0,)00)) )o())
(a() ((b())) s
b(k)
(#-p)*
8 b(K = O S where af E [a,,p] p]. Therefore, 5 reflects how tightly f can be approximated by local polynomial function of degree 6kk). Moreover, the number of price segments N needs to be carefully selected to balance the accuracy of local polynomial approximation and the learning efficiency for each price segment. The specific choice of N is given in Theorem 3

---

Algorithm 2: Algorithm for Dynamic Pricing with Linear Context (ADPLC)
Input: time horizon T, price range (p.p), degree k; parameter Co. context dimension d, upper bound a, number of price segments N, error control terms A, noise variance proxy 2 Initialization:
Partition [p.p] into N segments of equal length, denoted as 1; for i 2,2, ,N;
Initialize for all i [M]: D, 0.
5 Main Steps:
for / 1.2.... do
7 Observe Tc;
for 1,2, do
9
A,, Co. fr. maxpel; p ((1). + ( + ni ((p, Vi. o(, xz) + A):
(0 (1,, Vi,)) =
10
Pr,1 arg maxpel: p x ((0,.: (i) + te, p(p, mn) T VV o(p, A):
end for
13 Select i, = arg maxig fr.s and charge pt = P156
Observe realized demand de;
15
Update D., +- Di, u ((Fr,P(;d))
16 end for
Algorithm 3: Regression with Linear Context (RLC)
Input: polynomial degree k. context dimension d, domain [1, u], history D, bias A, probability e, smoothness parameter C, noise variance proxy upper bound ā
(u-1)ak 2 Compute À= [u 12= + +d;
3 Compute 7 = V (d - 13)
[4+++1D) 21ne (² + a2) + A VDD; d+h
Compute V (((x+d)x(
+ (Z.Dd)) x(p,x) xT), where Φ(p, x) = (4(() (a T)
and (p) = (1, (p (),..... ........ (p T)
5 Compute Ridge estimate
(0,a) = arg min Σ (a.D.)eD (d (0, (()) (a, 2(11012 ||al();
Output: 0, à 7, V
Biased linear contextual bandit and OFU. To suggest good price for each segment, we borrow the biased linear contextual bandit from [32] Specifically, for each 2 1 and pt E I,, we can rewrite Dr(pt) as follows: De(p.) = Pt, (p:) + x2 + 3. = 0J p(p.) + a 2z + St. where B. = f(.)) Pr, (pt) + Ex. ((p)) = (1, (pr - 03), (p: 1.p--ay) ay) and 0g b(4++ whose
ith element is (a;) for sis b(k) + 1. This model is similar to the linear contextual bandit [i-1)) in the literature (see, e.g., M. () where the OFU idea that selects actions in an optimistic way is commonly adopted. The key difference is that Be contains biased term that is not mean-zero and depends on the pricing decision. We adapt the idea of adding an additional term A when implementing the OFU principle to compute an optimistic price and optimistic revenue from K2)
Optimism over OFU for price selection. In the absence of context, the optimal price in 332 fixed. To learn this fixed optimal price, (32] propose the idea of embedding the biased linear contextual bandit into a multi-armed bandit protocol that treats each price segment an arm. The segment to which the fixed optimal price belongs is regarded as the "best" arm. By contrast, in our context- based setting, the optimal price depends on the random context revealed in each period and changes over time. Thus, our "best" arm in each period also changes, and the idea of multi-armed bandit protocol in [32] does not work. To overcome this challenge, we propose a new idea of optimism over OFU, which proceeds as follows. We first implement the OFU principle to each price segment I; and compute an optimistic price Pt.: and optimistic revenue Pr..- Then we choose the most optimistic price from the N candidate prices pr. PP.N that achieves the highest optimistic revenue.
7

---

The following theorem presents the regret upper bound for Algorithm 2 whose proof is in Appendix C.
Theorem Let Algorithm run with N = प म
+ 1 and A = ó(p - /N². Under
Assumption and ||a|| I a, the regret of Algorithm is
δ (d(VTv (8TH+)))
First, when 5 is a constant and is an integer, the regret upper bound becomes OdT ((dTztt) 2t-T) ) recovering Theorem 1 in 2 for the setting without contexts (i.e., d 1 and is constant). As k becomes +1l larger while keeping a constant, the upper bound decreases according to (dd (77T) ). In the extreme case of A = the upper bound becomes (dvV)) which coincides with the optimal regret rate for the linear model d(p, z) bp + a x: (see, e.g., 3 Second, when is not constant whose order can shrink
til
increases, Theorem shows an instance- deependddd bound which further differenniates s+1 our result from that in 32 We can see that when 5 = 22(T +), the regret bound is Ö महं T )
and when ó decreases to (T }) the regret bound is always (VT). This shows that the magnitude of 5 greatly affects the regret upper bound, and the smaller is, the lower the regret bound will be. This is because when becomes smaller, the approximation error using local polynomial function O NT becomes smaller, leading to more accurate estimates for f()). Since the polynomial function
differentiable infinitely many times, its regret is (VVT) from Section 3.4.1 in 33). Therefore, as decreases, the regret upper bound decays to (vTT), which is attained when 8 = O(T 4). To prove Theorem 3 by the idea of optimism over OFU, we can upper bound the regret by the length of the confidence interval which can be controlled by the well-known concentration inequality in [I]
We then establish the regret lower bound. Similar to Theorem 1 denote the regret of policy by R7, p. (T' k, 5) when the demand function is f(p) + a x + E, where f E (Fp. (ip.P: 6)), and the distributions of x and E are P and D respectively.
Theorem For any F ((p. P))), 2 O, and o 2 O, there exists a constant K₂ > 0 independent of T and 8, such that for any admissible policy
R (T. K2. (VTV (6T xit) ( P.CE()
sup (p.7.))))))))
Theorem/ shows that the regret upper bound achieved by Algorithm 2 in Theorem 3 is unimprovable in terms of its dependency the learning horizon T and parameter o. Note that the upper bound in Theorem 3 grows linearly in d, but the lower bound in Theorem is independent of d. This is because in the lower bound analysis, we simply consider O. We leave the problem of analyzing the more complicated dimension-dependeee
lower bound future research. The first lower bound 22( ((VT) in Eq. (2) directly follows from the existing literature (e.g., (17). The proof of the second lower bound (((TT*+1)2 22==)) ) relies constructing series of keth-order smooth functions with parameter 8 and applying Pinsker's inequality to bound the total variation of two probability measures through their KL divergence. See our construction and detailed proof in Appendix D.
4 Numerical Study
In this section, we conduct a numerical study to test the empirical performances of our algorithms. We measure the performance of learning algorithm æ by the relative regret defined as follows:
Elp A(p].... .xx) -ped(pp))
100%. For both models, compare our algorithms with the linear greedy algorithm that estimates the demand function by linear function and myopically selects the optimal price that maximizes the proxy revenue in each period f. For DPLPPE model, also compare our algorithm with the random price shock (RPS) algorithm proposed by (25). For each instance, we repeat our experiments for 50 independent runs, and approximate the relative regret by the empirical relative regret averaged over 50 runs.
Σx pogdd(n?..m .n:))
Note that the linear model is special of DPLCE by letting co.

---

Numerical results for DPLPE model. For our DPLPE model with demand function d(p, = [1, 19), Uniform((0. 1)
bp + g(zz), we set b = -5, (O 5), [b. bj = [-8, -3). p.pl
and consider the following form of function g(x):
100 x (D(x, 0 1)9) + 100
if (a, 00,,,010,111 109.1))= z 7:
g(x))
100 (1) 300 (D(a, 0,0, 115) - 100 otherwise,
where (rr, 000, 1) denotes the Euclidean distance between and the boundary of [0. 1j2. In Figure [[a] we compare the empirical relative regret of our ADPLP with those of RPS algorithm and the linear greedy algorithm. The figure shows that our algorithm performs much better than both algorithms. In Figure l(b) we investigate the effect of d on the empirical relative regret of ADPLP by varying d in the set {I.3, 10} while keeping 3 As shown in the figure, as d decreases, the regret decreases, which is consistent with our theoretical results. In Figure [cc) we test the effect of , on the empirical relative regret of ADPLP by varying / in the set (0.2, 0.6, 1} while keeping When f is relatively small, slight increment of B3, e.g., 8 0.2 to B = 0.4, will lead to significant are very close, which indicates that
speed-up of the convergence. The results of B = 0.6 and when 3 is relatively large, increasing 3 may only bring limited improvement.
Ortarto "gpe
Pered
(a) Regret under d 2,
(b) Effect of d on ADPLP
(c) Effect B on ADPLP
Figure 1: Empirical relative regret for DPLPE model
Numerical results for DPI.CE model. For our DPLCE model, we consider the following demand: Dr(p:) = 5pp 30 + La + St, where 1, denotes (1, 1,... ,1 Rdd is uniformly distributed on 0o. 1 independently and Ea (N 0.12). It be verified that A: 2.5 in this In Figure Z(a) we fix d = 2, 5 = 3.75 and [p.7] | [2.6, 3.8), and compare the empirical relative regret of our ADPLC with that of the linear greedy algorithm. The linear greedy algorithm has almost a constant empirical relative regret, showing that it fails to identify the optimal solution. By contrast, the empirical relative regret of ADPLC decreases empirical relative regret of ADPLC by varying 3 E (3.75, 2.5, }]. As shown in Figure 2(b) as becomes smaller, the empirical relative regret decreases, which consistent with our theoretic results.
increases. We also test the effect of on the
Uneu Soea Dy Agennee
Paradd
Perii:
(a) Regret under 3.75
(b) Effect of 5 on ADPLC
Figure 2: Empirical relative regret for DPLCE model
5 Conclusion
In this paper, we study the bossext-based dynamic pricing with online learning, where the unknown expected demand admits partially linear semi-parametric structure. For both models DPLPE and DPLCE, we develop efficient learning algorithm and characterize the optimal regret by proving matching upper and lower bounds. We note that our algorithms need to have the preliminary knowledge about the smoothness parameters 3 in DPLPE model and & and ó in DPLCE model.

---

One important direction for future research is to explore whether parameter-free free algorithms can be developed and still achieve the optimal regret rate for both models.
References
[1] Yasin Abbasi-Yadkond Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256, 2002.
[3] Gah-Yi Ban and Bora Keskin. Personalized dynamic pricing with machine learning: High- dimensional features and heterogeneous elasticity. Management Science, 67(9):5549-5555 -56688 2021.
[4] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6):107-11200, 2009.
[5] Omar Besbes and Assaf Zeevi. Blind network revenue management. Operations research, 60(6):1537-1550 2012.
[6] J Bretagnolle and C Huber. Estimation des densités: risque minimax. Zeitschrift für Wahrschein- lichkeitstheorie und verwandte Gebiete, 199)):11-137, 1979.
[7] Josef Broder and Paat Rusmevichientong Dynamic pricing under general parametric choice model. Operations Research, 60(4):965-980, 2012.
[8] Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covari- ates. Operations Research, 69(3)-974-984, 2021.
[9] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 214. JMLR Workshop and Conference Proceedings, 2011.
[10] Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing, Manage- ment Science, 66(11):499 4-444, 2020.
[11] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21 Conference on Learning Theory, 2008
[12] Arnoud V den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1-18, 2015.
[13] Robert F Engle, Clive WJ Granger, John Rice, and Andrew Weiss. Semiparametric estimates of the relation between weather and electricity sales. Journal of the American statistical Association, 310393):30,-32, 1986.
[14] Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Available at SSRN 3922825, 2021.
[15] Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the paramet- ric and dindifferentiabee regret regimes. In Conference Learning Theory, pages 2007-2018 PMLR, 2020.
[16] Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. The Journal of Machine Learning Research, 20(1):315-36) 2019.
[17] N Bora Keskin. Optimal dynamic pricing with demand model uncertainty: A squared-coefficient- of-variation rule for learning and earning. Available SSRN 2487364, 2014.
[18] N.B. Keskin and A. Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal mymic policies. Operations Research, 1245)1114211167, 2014.
10

---

[19] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[20] Yiyun Luo, Will Wei Sun, et al. Distribution-free contextual dynamic pricing. arXiv preprint arXiv:2109.07340, 2021.
[21] Jieming Mao, Renato Leme, and Jon Schneider. Contextual pricing for lipschitz buyers. Advances in Neural Information Processing Systems, 31, 2018.
[22] Sentao Miao, Xi Chen, Xiuli Chao, Jiaxi Liu, and Yidong Zhang. Context-based dynamic pricing with online clustering. arXiv preprint arXiv:1902.06/99, 2019.
[23] Sentao Miao and Yining Wang. Network revenue management with nonparametric demand learning: (sqrt {Terregret and polynomial dimension dependency. Available at SSRN 3948140, 2021.
[24] Jonas W Mueller, Vasilis Syrgkanis, and Matt Taddy, Low-rank bandit methods for high- dimensional dynamic pricing, Advances in Neural Information Processing Systems, 32, 2019,
[25] Mila Nambiar, David Simchi-Levi, and He Wang. Dynamic learning and pricing with model misspecification. Management Science, 65(11) 6500000990--000, 2019.
[26] Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693-721, 2013.
[27] Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates. Available at SSRN 2765257, 2016.
[28] Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. arXiv preprint urXiv:1003, 1630, 2010.
[29] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35 2010.
[30] Virag Shah, Ramesh Johari, and Jose Blanchet. Semi-parametric dynamic contextual pricing. Advances in Neural Information Processing Systems, 32, 2019.
[31] Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th anmual Conference On Learning Theory, pages 679-702. JMLR Workshop and Conference Proceedings, 2011.
[32] Yining Wang, Boxiao Chen, and David Simchi-Levi. Multimodal dynamic pricing. Management Science, 67(10))61366615, 2021.
[33] Zizhuo Wang, Shiming Deng, and Yinyu Ye. Close the gaps: A learning-while-dinng algorithm for single-produee revenue management problems. Operations Research, 62(2):318-33 331, 2014.
[34] Jianyu Xu and Yu-Xiang Wang- Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems, 34, 2021.
[35] Janny Xu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. In International Conference on Artificial Intelligence and Statistics, pages 9643-9662. PMLR, 2022.
[36] Adonis Yatchew and Joungyeo Angela No. Houschold gasoline demand in canada. Economet- rica, 1996)116771 2001.
[37] Scott Zeger and Peter Diggle. Semiparametrie models for longitudinal data with application to cd4 cell numbers in hiv seroconverters. Biometrics, pages 689-699, 1994.
[38] Feng Zhu and Zeyu Zheng. When demands evolve larger and noisier: Learning and earning in growing environment. In International Conference on Machine Learning, pages 11629-11638. PMLR, 2020.
11

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section 0.
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] See the last paragraph of Section
3 and Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sections
3
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Section
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "vK_7fkv4bs", "reviewer": "Reviewer_pEPr", "summary": "This paper studies the context-based dynamic pricing, where the unknown expected demand admits a semi-parametric partially linear structure. Two special cases of semi-parametric partially linear models (Linear Pricing Effect and Linear Contextual Effect) are considered. Two new algorithms (DPLPE and DPLCE) are proposed and their regret upper bounds and matching lower bounds are established. \n", "questions": "(1) It is important to discuss the technical novelty of this paper beyond existing semi-parametric dynamic pricing papers. \n\n(2) It is important to provide some guidance on how to choose the unknown parameters (bounds of $b$, $\\beta$, etc) in a data-driven way. It is also helpful to study the sensitivity of the choice of these parameters in experiments. \n\n(3) It is helpful to list all assumptions used for the theorems. When discussed with regret bounds in the literature, it is important to also mention the difference in the assumptions. \n\n(4) It is important to study the model misspecification case, e.g., when the true model is linear or purely nonparametric, in the experiments. \n\n\n", "limitations": "No potential negative societal impact was discussed in the checklist. No limitation was discussed in the paper. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n(1) In spite of a theoretical paper, it is well written and easy to follow. \n\n(2) The proved matching lower bound is useful to understand the limit of the considered problem. \n\n\nWeaknesses\n\n(1) Technical novelty: The proposed partially linear demand model is a natural extension of existing linear demand model and nonparametric demand model. On the other hand, a similar partially linear demand model has been proposed in dynamic pricing literature, see below. None of them was mentioned in the paper. In fact, these papers consider a binary choice model which is arguably more challenging than the one considered in this paper. \n\nJianqing Fan, Yongyi Guo, Mengxin Yu (2021), Policy Optimization Using Semi-parametric Models for Dynamic Pricing, https://arxiv.org/abs/2109.06368. \n\nJianyu Xu, Yu-Xiang Wang (2022), Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise, AISTATS 2022. \n\n(2) The proposed algorithm and theoretical analysis require the knowledge of some true parameters, e.g., the upper and lower bounds of price, the upper and lower bounds of the true price coefficient, The continuous parameter $\\beta$ of the unknown function $g$. In practical pricing applications, knowing upper and lower bounds of price is arguable and a mild assumption. But it is less justifiable to know the bound of $b$ and $\\beta$ in practice. \n\n(3) It is unclear what assumptions were assumed in the main Theorems (Theorems 1-4). In addition, when the authors compare the proved regret bounds with those in the literature, it is also important to discuss if their model assumptions are comparable. It would be more convincing if the faster regret bound is not obtained under much stronger assumptions.\n\n(4) The experiments of this paper only study the performance when the true model is the proposed partially linear demand model. No model misspecification was studied. It is unclear if it is always safe to use the proposed algorithm in practical pricing applications. \n\n~~~~~~~~~~~~~\nAfter rebuttal: Thanks the authors for carefully addressing all my concerns. My last three comments have been nicely addressed. I have raised my rating to Borderline Accept. On the other hand, while I understand the difference (e.g., nonparametric on noise v.s. nonparametric on covariates; binary feedback v.s. continuous feedback) of this paper compared to existing pricing literature with partial linear demand model, I am not fully convinced by the \"technical novelty\" beyond them. So I choose to only increase the rating to Borderline Accept.\n\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "sj6nd52yf78", "reviewer": "Reviewer_1rnn", "summary": "This paper studies two online contextual dynamic pricing problem settings: DPLPE where demand is linear wrt price, and DPLCE where demand is linear wrt context. For DPLPE problem, they assume the realized demand $D_t = bp_t+g(x_t) + \\epsilon_t$ with $g(x)$ being $\\beta$-Holder continuous and $\\epsilon_t$ being a subGaussian noise. They propose an ADPLP algorithm that adopts a space binning and a random shock techniques. With ADPLP, they achieve an optimal $\\tilde{O}(\\sqrt{T}\\vee T^{\\frac{d}{d+2\\beta}})$ regret up to logarithmic factors by proving both the upper and the lower regret bounds, where $d$ is the dimentionality of features. For DPLCE problem, they assume the realized demand $D_t = f(p_t) +a^{\\top}x_t + \\epsilon_t$, with $f(p)$ being $k^{\\text{th}}$-order smooth with a small parameter $\\delta$ that could be $T$-dependent. They present an ADPLC algorithm that adopts a local polynomial approximation and a biased linear contextual bandit with an optimistic OFU strategies. With ADPLC, they achieve an optimal $\\tilde{O}_d(\\sqrt{T}\\vee(\\delta T^{k+1})^{\\frac1{2k+1}})$ regret up to logarithmic factors, by proving both the upper and the lower regret bounds. Finally, they conduct numerical experiments and show that the simulation results of ADPLP and ADPLC ourperform all benchmarks.", "questions": "Questions:\n\n(1) See the related work issue I mentioned above. Maybe a good idea is to list these key properties/assumptions in categories (like what they did in [30] Table 1).\n\n(2) Notice that ADPLC require knowledge on the noise std $\\sigma$. Does ADPLP require it as well? It is sometimes decisive to assume a parametric or non-parametric noise in an online learning problem, so I suggest the authors to specify these properties in detail, and briefly discussion how they contribute to your analysis and results.\n\nMinor suggestions:\n\n(1) Avoid notation repeatance: e.g., $d$ for feature dimension and also for expected demand.\n\n(2) A few typos: e.g. line 42: $x_t\\in[0,1]^d$.\n", "limitations": "Limitations and potential extensions of this work are well discussioned. \nThere is no discussions on social impact as it is a work of theory. However, I indeed suggest the authors to consider any potential ethic issue that might occur in a pricing problem with these assumptions you have specified.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) This work generalizes the problem settings of both linear demand and linear context problems. For DPLPE, they consider $\\beta$-Holder class instead of only Lipschitz that was broadly assumed by previous works, and they improve the comparison by replacing the linear benchmark with the true demand function in [8] and [23]. For DPLCE, they consider $k$-th-order smooth with not only integer but also non-integer $k$'s, and they also emphasize the role that $\\delta$ plays instead of treating it as a constant as previous works did.\n\n(2) For both DPLPE and DPLCE, they design algorithms with provable optimal regret bounds. These results are significant as they not only match the order of $T$ but also those of $\\beta$ and $\\delta$. Moreover, for DPLCE, their upper and lower bound match those in [30], indicating that a linear context added on the demand curve might not require substantially more information to learn.\n\n(3) Their numerical experiments are comprehensive and the results are well-displayed.\n\nWeaknesses:\n\n(1) Some related literatures should be discussed with more details. For example, the stream of binary demand model. As this work also assume a noisy feedback, the only difference of binary feedback is that the noise distribution is dependent on $p$ and $x$ while this work assumes iid. Since the closely-related work [30] also assumes a binary feedback, the results of this work do not actually cover those in [30]. Overall, the binary feedback is an important property in many pricing problem settings, and I suggest the authors to be aware of this issue and place this paper in the related literatures with more precision.\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D6BGwpXZave", "reviewer": "Reviewer_JfvX", "summary": "This paper studies the contextual dynamic pricing problem under partially linear structural assumptions. In particular, the authors consider two demand models **DPLPE** and **DPLCE**. The former assumes a linear term in the price with an additive $\\beta$-Holder continuous function of the context. The latter assumes a linear term in the context with an additive $k$-th order smooth function of the price.\nThe authors present two online algorithms and provide regret upper bound as well as lower bound guarantees for each of the models:\n1. **DPLPE**:\n   - upper bound of $\\mathcal{O}\\left(\\sqrt{T} + \\ln T\\cdot T^{\\frac{d}{d+2\\beta}}\\right)$.\n   - lower bound of $\\Omega\\left(\\max(\\sqrt{T}, T^{\\frac{d}{d+2\\beta}})\\right)$.\n2. **DPLCE**:\n   - upper bound of $\\mathcal{O}\\left(d\\ln T(\\sqrt{T} + (\\delta T^{k+1})^{\\frac{1}{2k+1}}))\\right)$.\n   - lower bound of $\\Omega\\left(\\max(\\sqrt{T},(\\delta T^{k+1})^{\\frac{1}{2k+1}}))\\right)$.", "questions": "As this paper presents theoretical results I find the Numerical Study section redundant and would suggest providing more background on the proof techniques used in the paper.", "limitations": "I don't see any potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strenghts**:\n- The paper in general is well written and its contribution over previous works is presented clearly by the authors.\n- The models considered in the paper are more general compared to known works and they provide new results on the problem of dynamic pricing.\n- I find the algorithm design of both algorithms to be interesting and novel as it combines multiple ideas from previous works.\n- The authors also provide lower bound guarantees which enhances the main results of the paper.\n\n**Weaknesses**:\n- As stated by the authors the lower bound in Theorem 4 is missing the dependence in $d$ which makes this lower bound less significant compared to the lower bound in Theorem 2.\n- I believe that the problem setup can be presented more clearly for the reader with better formatting.\n- I feel like the main text could benefit from a more comprehensive technical overview.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4gkKhNYgmgr", "reviewer": "Reviewer_JA1m", "summary": "The paper studies an online learning and contextual pricing problem with semi-parametric partially linear demand models, where the demand function is the sum of a linear function with an unknown coefficient(s) of price (or context, resp.) and an unknown function of the context (or price, resp.). For the above two demand models, the paper develops two corresponding online pricing algorithms with provable regret upper bounds and matching lower bounds with respect to the horizon $T$.", "questions": "I hope the author can address in the rebuttal the two points mentioned in the weakness above and I may adjust my final rating based on the response. ", "limitations": "NA.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nOverall, the paper is well-written. \nFormulation-wise, the paper generalizes the commonly used Lipschitz continuous assumption to Holder continuity. Importantly, the results show that the additional structure of linearity indeed improves the regret bound. \nAlgorithm-wise, the paper combines several online learning techniques, including binning and approximation, random shock in pricing, and upper confidence bound algorithm, so as to estimate the non-parametric part of the demand functions. \nAnalysis-wise, the paper gives a comprehensive analysis of the statistical complexity/regret of the formulated problems.\n\nWeakness: \n 1. In Algorithm 2, when solving the UCB optimization problem in line 10, what is its complexity? And in general how to solve it (efficiently)?\n 2. The algorithms seem to require the knowledge of $\\beta$ and $k$, the authors should state these explicitly in the assumptions and discuss how to estimate these quantities when there is no such prior knowledge. \n\nMinor comment:\nUpon reviewing the literature, the paper misses one stream of works related to semi-parametric dynamic pricing (see below). The author should discuss the contribution against these works.\n- Policy optimization using semiparametric models for dynamic pricing (Fan et al. 2021)\n- Distribution-free contextual dynamic pricing (Luo and Sun, 2021)\n- Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise (Xu and Wang, 2022)\n\nAlso, the authors should mention that the matching of lower bounds refers to the dependency on $T$ but not with respect to $d$. As in the discussion of Theorem 4, one of the lower bounds doesn't meet the corresponding upper bound in the context dimension.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept