Contextual Dynamic Pricing with Unknown Noise: Explore-then-UCB Strategy and Improved Regrets
Authors: Yiyun Luo
Will Wei Sun
Yufeng Liu
Venue: NeurIPS 2022 Accept (2022)

Abstract: Dynamic pricing is a fast-moving research area in machine learning and operations management. A lot of work has been done for this problem with known noise. In this paper, we consider a contextual dynamic pricing problem under a linear customer valuation model with an unknown market noise distribution $F$. This problem is very challenging due to the difficulty in balancing three tangled tasks of revenue-maximization, estimating the linear valuation parameter $\theta_{0}$, and learning the nonparametric $F$. To address this issue, we develop a novel {\it Explore-then-UCB} (ExUCB) strategy that includes an exploration for $\theta_{0}$-learning and a followed UCB procedure of joint revenue-maximization and $F$-learning. Under Lipschitz and 2nd-order smoothness assumptions on $F$, ExUCB is the first approach to achieve the $\tilde{O}(T^{2/3})$ regret rate. Under the Lipschitz assumption only, ExUCB matches the best existing regret of $\tilde{O}(T^{3/4})$ and is computationally more efficient. Furthermore, for regret lower bounds under the nonparametric $F$, not much work has been done beyond only assuming Lipschitz. To fill this gap, we provide the first $\tilde{\Omega}(T^{3/5})$ lower bound under Lipschitz and 2nd-order smoothness assumptions. 

Contextual Dynamic Pricing with Unknown Noise: Explore-then-UCB Strategy and Improved Regrets
Yiyun Luo
Will Wei Sun
Department of Statistics and Operations Research University of North Carolina Chapel Hill Chapel Hill, NC 27599 yiyun851@ee madd @ad. unc. edu
Krannert School of Management Purdue University West Lafayette, IN 47907
sun244@purdue. edu
Yufeng Liu
Department of Statisties and Operations Research
Department Genetics Department of Biostatistics
University of North Carolina at Chapel Hill Chapel Hill, NC 27599 yfl yfliußemail. unc unc.edu
Abstract
Dynamic pricing is a fast-moving research area machine learning and operations management. A lot of work has been done for this problem with known noise. this paper, we consider a contextual dynamic pricing problem under a linear customer valuation model with an unknown market noise distribution F. This problem is very challenging due to the difficulty in balancing three tangled tasks wweenuemaxxmizzene
estimating the linear valuation parameter 6g and learning the nonparametric F. To address this issue, we develop a novel Explore-ther UCB (ExUCB) strategy that includes exploration for fe-leann and followed UCB procedure joint revenue- aicenueemaximizationn and F-learning. Under Lipschitz and 2nd-order smoothness assumptions F, ExUCB is the first approach to achieve the (TT2/3) regret rate. Under the Lipschitz assumption only, ExUCB matches the best existing regret of ((13/4) and computationally more efficient. Furthermore, for regret lower bounds under the nonparametric F, not much work has been done beyond only assuming Lipschitz. To fill this gap, we provide the first (/(33/5) lower bound under Lipschitz and 2nd-order smoothness assumptions.
Introduction
Dynamic pricing a process of continuously adjusting the prices by learning from the customers' feedback. The feedback usually depends on the pricing action. To maximize the overall revenues in sales horizon, pricing policy should well balance between learning the customers' demands (exploration) and setting revenue- revenue-maxinn maximizing prices based on the current knowledge (exploitation). There a rich literature on this information-regre tradeoff under different settings
27 16 12
In this paper, we consider an important setting in dynamic pricing where some contextual information is available in each time period. It is interesting and challenging improve the revenues by well exploiting the sales-relevant contextual information such as product features and market environments.
To model the influence of the contextual information, we adopt binary feedback model which incorporates a comparison between the customer's 's valuation and the seller's price B 25 47
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Regret bounds under different smoothness assumptions on noise. Smoothness Assumplions on Unknown Noise CDF F
Upper Bound
Lower Bound
m(2 2 2) times continuously
1mst1 Ö(T
4m-1
20
differentiable
Arbitrary
Ö
48
44
Lipschitz
O(T (This work)
Lipschitz and 2nd-order smoothness
Ö(T 35
2(T3) (This work)
O(T5) (This work)
Specifically, in the selling time period t with the associated context 2t E IR,,, the customer's
valuation ot the product assumed to be linear with repect 2t, together with some noise 2t.
ie., = v((2)) x, 0o + Here the noises {=x heer across the time horizon [T] (1, (1, T)
are independent and identically distributed (i.i.d.) from a Cumulative Distribution Function (CDF)
F. Then under the seller's i price Pt, a binary feedback y/- 1 (p,2p.) representing the customer's s purchasing decision is observed by the seller. Namely, the purchase at time period t happens if and only if the customer's valuation is greater than equal to the seller's price pt. The seller then collects the current feedback 3/: which can help the pricing decision at the next time period. Note that the binary feedback structure y/ (p.2p. } is critical to this online pricing problem's ' bandit nature. We cannot observe the full information et at each time period. Instead, we can only observe the partial information y = 1 2v.2p)) which varies with different pricing action pt.
Thus, the optimal pricing depends on the distribution of the valuation v - v(x;,) ze 0g + z4. We assume both unknown parameter Gg and unknown noise CDF F at the beginning of the horizon. Therefore, the seller needs to gradually learn both &g and F for better pricing. In this paper. we investigate two different smoothness assumptions for the noise CDF F. The first one assumes Lipschitz continuity and 2nd-order smoothness, while the second only assumes Lipschitz.
At each time period the expected reward of any price p is IE (B
To tackle these two sub-problems under different noise smoothness assumptions, we propose two sub-policies unified under single pricing policy framework, namely Explore then Upper Confidence Bound (ExUCB). In particular, our proposed EXUCB first estimates 0, through some random pricing exploration phase, and then uses this estimate to drive a Upper Confidence Bound (UCB) procedure that well balances aevenue-maxiizzinn
and F-learning
The same pricing problem has been investigated in the literature B5
under variety of smoothness assumptions on the noise. The existing regret bounds are presented in Table I along with new regret results in this paper. In summary, our theoretical contributions are threefold.
20 48
1. Under the Lipschitz and 2nd-order smoothness assumptions, our proposed ExUCB policy is the first procedure to achieve ( regret rate. We prove valid O estimation accuracy and quantify its influence on the regret of the UCB procedure driven by the Ag egtesmmmtee. This helps us determine an optimal balance between random pricing exploration and the followed UCB phase. Our (T3333 regret improves the existing regret bound of Ó(T2/3v(1-a)) in 335 which has an indeterministic a. It also improves the Ö(T5/7) regret in [20] which assumes a stronger smoothness assumption of twice continuously differentiable F.
2. Under the Lipschitz and 2nd-order smoothness assumptions, we obtain the lower bound of ((T8/55 by constructing the instances such that any policy cannot perform well on all of them. To our limited knowledge, this is the first lower bound result under such smoothness assumptions. To construct instances that satisfy this smoothness assumption, the core step is to build "bump towers" by piling up an infinite series of "quadratically shrinking" basic bump functions. Note that the (2233 lower bound in [48) only applies the Lipschitz assumption since their constructed instances do satisfy the 2nd-order smoothness assumption.
3. Under the Lipschitz assumption, EXUCB can match the best existing upper bound of O(73/4) in [48] and is computationally more efficient. This shows the adaptivity of ExUCB to different noise smoothness levels.

---

Our improved regret over existing results in [35 20 demonstrates the methodological novelty of the proposed Explore-thens teaere-the--UCBBB strategy. In [35, the authors implemented the UCB idea but did not apply random pricing explorations. Thus they can only use adaptive data to estimate Oo. which results in an indeterministic in their regret of Ö(T2/3v(1-a)) In contrast, by using random exploration phase, ExUCB achieves the exact regret of ((T2/$). In (0).. the authors proposed an Explore- Saaeee-thh--Commii type of policy that first estimates Og and F in an exploration phase and then commits to these estimates for pricing in the exploitation phase. In comparison, ExUCB imposes a UCB procedure to adaptively balance between revenue-mad caanuu-mxx and F-leeaniig. The regret advantage of ExUCB indicates the importance of our UCB procedure after the exploration.
Related Works
In this section, we discuss how our work relates to the literature of dynamic pricing, bandits and contextual search..
Non-Cone Con-Contextual Dynamic Pricing. Extensive investigations have been conducted on dynamic pricing problems without contextual information 7
46 8 [4]. For mn-hh smooth demand functions,
44 applied the UCB idea with local-bin approximations achieve an (07(mm111((m+++) regret, and proved a matching lower bound. The UCB approach has also been adopted in [2]] 377. However, these methods are not able utilize the potential contextual information for better pricing.
Contextual Dynamic Pricing.
There are significant interests among researchers in contextual 38
dynamic pricing [1 24, 36
15 With nonparametric revenue functions, regret based on the adaptive binning idea from nonparametric contextual bandit [4]]. Note that their proved ((T3/5) regret lower bound for the one-dimensional case does not apply to our setting since their constructed revenue functions
6
43
5
18
45
26 13
13
designed a policy with ( 2)/ (do+))
beyond our revenue function class. In [43,, the authors adopted a log-linear valuation model and proposed a pricing algorithm with O(T regret, Some recent literature 25 22
35 20 48
adopted the same linear valuation model in this work. By assuming a known noise distribution, 225 47 designed algorithms with Oloo T') regret. For noise in known parametric family, (25)
proposed a policy with O(T)/2) regret. In [23], the authors assumed a known ambiguity set that contains the noise distribution and proposed an algorithm with a ((T2/3) regret with respect to robust benchmark. With unknown noise distribution, the ambiguity set would be extremely large and the robust benchmark can be far from the true optimal one. In [22). the authors considered unknown noise with "full information" feedbacks and proposed an algorithm with (2T)) regret.
The most related works to ours are [35] 20 48), which considered binary cencored feedback and unknown noise distributions under different smoothness assumptions. In (0). the authors proposed an Explore-thent
policy with an Ö 3m regret under m(2 2) times continuously differen- tiable F. The m = case would imply our Lipschitz and 2nd-order smoothness assumptions. Thus ExUCB can achieve a lower (T2333 regret than the ÖTT5/7) rate in (20 even under weaker smooth- ness assumptions. In 355. the authors proved an (TT2/3V(2-a)) regret. The value of a depends on the convergence rate of their Og estimates. However, is indeterministic and no rigorous justifications has been made. In comparison, the authors developed an adaptive pricing policy that achieved an O regret for adversarial contexts and arbitrary bounded noise distributions. Our ExUCB policy matches the (TT3/4) regret under a Lipschitz and can improve the regret to Ó(T2/3) with an additional 2nd-order smoothness assumption. In addition, since the EXP4-based policy in [48) requires exponential computations w.r.t. the covariate dimension dy ExUCB computationally more efficient with time complexity that polynomial with dg-
ExUCB policy achieves exact regret of Ö(T2/3). In (48),
Bandit Algorithms. Bandit-type feedback structure is natural in dynamic pricing 29 13 48). The bandit literature provides significant variety of methods to resolve the exploration-exploitaiii
tradeoff that arises with the bandit feedback [T] 31 A key tool we used in this paper is the perturbed
linear bandit (PLB) 35
is related to the misspecified linear bandits (3 39 and stationay
linear bandits 17 42 49
In addition, dynamic pricing is closely related to aantinuum-armed bandit
3

---

The lower bound we proved borrows the "needle in haystack" idea that is widely applied in aatinuum-armees bandits
2 28
28
Contextual Search.
Contextual pricing with binary feedback can be formulated into the contextual
search problem 34
However, different noises are considered other than our stochastic is noiseless and only small-variance noises are handled in (30]; ; A "flipping"
33
30
valuation ones. 34
noise on customers' decisions are investigated in 33
3 Preliminaries
Problem Setting. The sales time horizon is [T] = ......,T]... with the initial time period We present the online pricing procedure as follows.
1. At time period t, the seller observes a context 2t E IR
2. The customer valuates the product at 2i = _ 0g + 24. where 24 iid. F.
3. The seller sets price Pt based on 2, and the past sales data {(x,, Par Uo) be)s-s
4. The seller observes the binary feedback 1/2 = [er2p:) and collects the revenue Pttht-
5. Let + and go back to Step
Regret Definition. Given the context Tt, the probability of a purchase is 1 - F(pr - x 0o) and thus the expected reward of setting the price pe is Pe (1 Fpt 2, Bo)). Define the optimal price given the context æ as pz(x) = arg maxp20p( P(1 - F'p x 0o)). Then the regret r, at time period is defined as the expected revenue loss with respect to the optimal price P? = p (zz), iee.
Te = pt (1 Fpt - 0o)) - pt Fp: - z fo)).
Definition The cumulative regret across the horizon is defined as
Pr Σ r1 Σ
p1 Fly - _ 0n)) pr((1 F(p: x. 0a))
The expected cumulative regret R. [RT) obtained from taking expectation over the potential ran- domness of the data and the pricing policy. Our goal is to minimize ((Rr) by dynamically setting the price Pt under unknown On and F.
Technical Assumptions. We now present our main assumptions. Assumptions I 48
are standard
in dynamic pricing 25
B3 23
Assumption (Bounded contexts and parameter) The covariates 24 are bounded as ||æa||>o I 1. The l, norm [|6,]] [a of 0g is bounded by known constant W.
Assumption (i..d. contexts) The covariates It ~ P2 with the support X and the matrix > E((,,z)) (1,z,)) satisfies that coll is positive-definite for some positive constant co-
Assumption (Bounded valuations) The customers' valuations it E [0, Bor known constant B.
Assumption 3 assumes known upper bound for the customers' valuations 23 20 which is
reasonable for real-life products. Note that Assumption] indicates a known upper bound Pmax B for the optimal prices. In addition, Assumptions | and 3 imply an upper bound U W B
for the noise absolute value. In the following. we further introduce two smoothness assumptions.
The Lipschitz condition in Assumption assumes the 2nd-order smoothness the expected revenue functions around the optimal prices and
4 is basic and was considered in [35 48 Assumption 5
has also been imposed in [13 (35. It is satisfied with bounded second derivatives of F [35] but fits for a broader class of F. Both Assumptions differentiablility of F considered in (20)
are satisfied by m 2) times continuously
Assumption (Lipschitz Continuity) The noise CDF Lipschitz continuous with constant i.e., F()) F(y) L/z y), Vx, R.

---

Assumption (2nd-order Smoothness) Define the general expected revenue functions associated with the noise distribution as f/(p)= = F(p 9)). There exists positive constant C such that for any x E X and q = x Bg, we have fa(r" (x)) f4(p) S (x) - p)? Vp [0, Pmax)
In this paper, we investigate two smoothness levels on the unknown noise distribution F, i.e. Case (A): Lipschitz and 2nd-order smoothness; Case (B): Lipschitz-only. For these two scenarios, we design respective algorithms that are unified under a single ExUCB policy framework.
Algorithm
We first propose the general ExUCB policy in Algorithm Without the knowledge of the horizon length T. we utilize the doubling trick [3] to cut the horizon into episodes. Each episode consists of exploration phase and followed UCB phase. Denote the first episode length as or and the number of episodes as nTT, (1) 01). The schematic of ExUCB is displayed in Figure
Explore
UCB
Explore
UCB
Explore
UCB
Episnde
Episode 2
Episode
Figure I: Schematic Representation of Explore-then-Uee Policy.
Algorithm Explore-then--CCB (ExUCB)
1: Input: (at time Pmax: B, an Ci, C2, B, 7,
2: Input: (arrives over time) covariates {Iz (eer
3: For episodes = 1,2,.... n²= nTT, on )), do
4: Set the (projected) length of the k-th episode as la ===-1a1 a1.
5: (Exploration Phase)
6: For time E & = EE l + 1,.... Σ la [C1 1.
7: Set price uniformly randomly from (0, B).
8: Receive binary response yt-
9: Calculate the esttmmmt 0% by
(px. 0%) = arg min
(By- - (1. (H, )
Exl
LEE
10:
(UCB Phase)
For time E U4 == (Ek-1 4 [ + 1...., Ex= & + [x]. do
11:
12: Apply the Inner UCB Algorithm the coming sequential covariates {xtheu with the esttmmim Qz. the discretization number dę [C2(ex & the optimal price bound Pmax. the projected length (fg- [C1 (C11)) and the regularization parameter X.
In the exploration phase, we conduct random pricing and finally obtain 6 estimate. the followed UCB phase, we implement UCB procedure that uses the Oo estimate drive the balance between F-learning and revenue-maximizing We discuss the two components in the following.
Estimation of 6.- At the beginning of each episode, we impose random pricing exploration phase to generate data for On estimation. The exploration phase length [Ci ei is set as some 3 order the episode length &.. By uniformly random pricing in (0, B), there arises a linear regression structure 23 20 involving the signal of 6g. Specifically, we have
E B(Bygla.)) = (E(((1 Sxp0 21 =.)) = BE F. On
zt (xx)) = (1, (14, )T)T.
B
Thus we are able to provide guarantees for Oz using classical analysis techniques on linear regression. In contrast, (35] applied linear classification method on the adaptive data of the previous episode to obtain a -o-estmmaee, which lacks theoretical guarantees for the estimation accuracy.
5

---

0g-driven UCB Procedure. In the UCB phase of episode k, we use the obtained linear regression estimate 0g to drive UCB procedure that balances between F-learning and revenue-maximizing Different from [35), our UCB procedure does not start at the beginning of each episode. In addition, we offer a different source of Oo estimate that is independent of previous episodes and allow more general discretizations tuned by a parameter 7.
Algorithm 2 Inner UCB Algorithm
1: Input: (arrives over time) covariates {ax )re(T)) -stemmittte ê; discretization number d; optimal
price bound Pmaxi projected length To: regularization parameter À in the UCB formulation [
2: Cut the F-learning interval G(0) ||00| Pmax ||0]] [] into d same-length sub-intervals with their midpoints denoted as mi..... m.l
3: For time I, .,.., To. do
4: Construct the candidate price set St {m, + x. Ajj [d]. my + x. 0 E (0, Pimax)
5: Determine the available arm set B, = E [d] my + x. 0 E (0,Pmaxx)
6: Calculate UCB,(1 F(m,)) for
B, in
7: Calculate jt E arg max (m, + x (1- F(m)))
8: Set the price m.j + x, 0 and receive a binary response yt-
The Inner UCB Algorithm explicitly presented Algorithm 2 In summary, the knowledge of F is continuously updated and the prices are set accordingly. Since any potential optimal price p (0. Pmax). we only need to explore those F-values on the potential range of p z 0g. i.c..
|-110o|1,, Pmax + [[0o]]]]. Thus we first restrict our F-leeariig attention to the interval G(Ø) =
[-10[11, +110]1]- Now we borrow the discretization approach in [35] Specifically, we discretize G(O) into d sub-intervals and further focus the learning of F on their d midpoints {m, Jejd Note that we use da to refer to the covariate dimensionality, and use d, ds to refer to the discretization numbers. This discretization idea would enable mutual reinforcement procedure of the discretized price selection and the knowledge accumulation of F on these discretized points. They can repeatedly enhance each other in closed loop. To do so, at each time period t, construct the candidate price set S = {my x, θjj E [d], m. + x. i E (0, Pmmax) Then for any candidate price Pt = m, + x 0g S,, its associated purchasing probability (1 F(p x Bo)) would be close to (1 - F (m,)). Therefore, the knowledge accumulation of F on {mz}je(a) helps with the expected revenue evaluation of the candidate prices and thus the price selection from S, On the other hand, the selection of any candidate price pt = m, + x. 0g E St invokes a binary outcome with a probability close to F(my), thus helping with the knowledge accumulation of F on my. Denote
Di-1,j == {s 1 < s S t 1. = = as all past time periods s such that p. - 2. = mj. Then we construct the UCB of - F(m,)
Eveo 15 P.V.
9:
o for D, D. 1j # 0;
(083(1FF(mm) = X+ 12
X+E
X+
(I)
t00,
for D.-1.j = 0.
Note that for s D.-1.j-1 Ms Ber(1 F(p.-1 ~ Ber(1 - F(my)) Therefore, the first term in the hand side of (T) for D,-1.j + 0 is a regularized weighted average of those and thus an estimate of 1 F'(m;). The second term is an associated confidence interval length. Based on these upper confidence bounds for - Fmmy). we select the price pt = m, + x from the candidate set S, that maximizes the optimism expected revenue (m, + x. θ)UCB, -F(m))).
It remains to specify the choice of B& in Equation Cp. We will discuss its choice by the following perturbed linear bandit 35) formulation of the pricing problem in the Inner UCB Algorithm.
Perturbed Linear Bandit Formulation With the restriction on the candidate sets Se, we are able to formulate the pricing problem guided by as a perturbed linear bandit. The PLB is an extension of the linear bandit and we present its formal definition Appendix C. The expected reward of the PLB takes the form of (E,, At) at each time period I, where A, is the action vector. Different from the linear bandit, the linear parameters & the PLB can vary across time periods and are perturbations from central linear parameter e".

---

In our pricing problem. by specifying the linear parameter & = (1-F(m3 +
[ 0 2, 0.)......11
F F(ma+ + x- 0o)) I² and mapping each candidate price pt m, + 0 action vector Ag with a single non-zero j-th element pt. the expected revenue of setting price can be rewritten as
pr(1 Fp: - z, 86)) =
In addition, all linear parameters & are around the central parameter 8* (1 F(m1) (im1)......
F(ma)) and thus close to each other with a perturbation constant Cp = 2L Oull2. Namely, have [|ç. - fo I Cp. Vss E N+ This implies lower & estimation error of 0 would lead to less perturbations and probably incur less regret.
Under the PLB formulation, the Inner UCB Algorithm indeed equivalent to a modified version of the LinUCB algorithm
31
35). Thus we specify 3, in as St = B3 = Pmmaa (1 V
11 v Ad
Pmaxx
/ (T6) + dloog(
dA+ M ))
dA
Regret Analysis
In this section, analyze the regret of proposed Explore-then-UU algorithm. For both Case (A) and Case (B), we specify the parameters 3 and in Algorithm approprraael and prove the respective upper bounds. Furthermore, we prove the first regret lower bound for Case (A).
5.1 Upper Bounds
For upper bounds, we first analyze a single episode Algorithm and then extend it to the entire horizon. Firstly, we provide the ε estimation error of our 0o estimation procedure.
there exists positive constants čι 02, è3 such that for any episode k with the exploration phase length nu 2 E3(do + 1)3, we have with probability at least
Lemma Under Assumptions
7 -
2 Tie
(dg 132 nk
that
8(B + UW) +1)
log nh 71g
1 Boll <
Co
Therefore, with an exploration phase length ny that scales G. we obtain an estimate d, with high probability ei-error of ((( As this Og will guide the UCB procedure, need to investigate how the estimation error propagates into the UCB phase regret. lower error rate expected cause less regret. On the other hand, lower error rate requires larger /3 and costs a longer ex exploration phase with more regret. Therefore, besides the "inner" balance between revenue-mas maximmiiin and F -lllaannig in the UCB phase, there is an "outer" balance between the exploration phase regret and the UCB phase regret, both associated with fo-learning. This outer balance is regulated by the value of B, which should be set differently under Case (A) and Case (B) achieve the optimal balance.
Secondly, we analyze the regret for the Inner UCB Algorithm. By defining the discrete best prices pf == arg maxpes, p(1 (1- F(p x 0o)) in S,, the time t regret can be decomposed as
PT F(t 2 0o)) P1 F(p: x 0o)) + pl F(p x (T)) P (1 F x 0o))
Te.1
T
We refer to RT., To Tt, and RT. De Tt22 as the discrete-part and continuous-pan regrets. By the PLB formulation of the pricing problem, there is a correspondence between candidate prices and PLB actions. Thus the discrete-pan part regret is equivalent to the PLB regret. To bound the discrete-part regret of the Inner UCB Algorithm, prove the following Proposition T based Theorem [35].
Proposition 1 Under Assumptions and there exists positive constants C₁ C2 and C's such that with probability at least 1 To. the Inner UCB Algorithu yields discrete-part regret
RIo.1 S C,dy To log (2 C-Lll0 PolliTo
7

---

Table 2: Regret components" rates for Case (A) and Case (B).
UCB Phase
Exploration Phase
Discrete-par part
Go Estimation Error
F- F-Learning
Continuous- part
O(10 0o (T))
O(dvTo)
Case (A)
O(T))
O1T
Ö(TØ+2)
( = 0
Case (B)
O(T)))
O -)
Ö(Tg+*)
0 = 0
In Proposition the first (dy component is typical in linear bandit and attributes to the lack of knowledge for and the central parameter 5* the PLB formulation. The second L|J 0oll To component is proportional to the PLB perturbation constant 2L| Boll- demonstrates how estimation errors influence the regret upper bounds, which matches with the intuition that better estimation would incur a lower regret in the UCB phase.
The discretization number d plays critical role in balancing the discrete-part and continuous- regret. larger leads to a higher discrete-part regret as indicated by Proposition [ which is intuitive since more discretizations yield more candidate prices and hence more challenging search process. On the other hand, a larger and denser discretization would make the discrete best price "closer" to the overall best price and decrease the continuous part regret. Specifically, under Case (A) and regret with the order O (e and Ol 2e) respectively.
Case (B), we can bound the continuous-pan Namely, we could achieve a lower rate with the extra 2nd-order smoothness Assumption Since we choose the discretization number de in episode & to scale as (ux)7 where uy denotes the UCB phase length, 7 regulates the balance between the discrete-part and continuous-pal regret in the UCB phase and should be set differently for optimal balances in Case (A) and Case (B).
Now we are ready to present the two regret upper bounds for Case (A) and Case (B).
Theorem Under Assumptions
5
by choosing B = 2 and
ō in Algorithm 1 the expected
|
regret satisfies E ((Rr) Ödd]
(TT33))
Theorem 2 Under Assumptions
4
by choosing B 1 and = 1/2 in Algorithm O(T3/4).
1 the expected
regret satisfies R RT) Ódg T 3/4)
We illustrate the regret components' orders in Table T a single episode with a generic length To- explains the different choices of |3 and 7y in the two cases to minimize the overall regret rates. It demonstrates that 39 balances between the exploration phase regret and the discrete partt regret due to On estimation error; while y balances between the continuous-pat regret and the discrete-par parrt regret due to F-learning. As shown in Theorem [ through optimal balance, ExUCB improves the existing regret of ((72/3v(2-))) in (35] and ((T5/7 in 20 to Ó(T2/3) under Lipschitz and 2nd-order smoothness assumptions. addition, an optimal choice of / and y Theorem 2 helps ExUCB match the best existing regret ((73/4) 48 under the Lipschitz-only assumption.
5.2 Lower Bound
We next prove a regret lower bound of (((3/5 for Case (A). To our limited knowledge, this is the first lower bound result under the Lipschitz and 2nd-order smoothness assumptions. Note that there is a gap between our proved upper and lower bounds for Case (A). Indeed, such a gap also happens in other works (20 48 on the unknown noise pricing problems. This may be due the inherent difficulties of these problems, e.g., in learning both dg and F.
Theorem 3 For any ô > O, no policy can achieve an O(13/5-5) regret for the dynamic pricing problem under Assumptions 7
Remark In 48 the authors proved an 22(22/3) lower bound with constructed instances that can fit into Case (B) but does not apply to Case (A). Our proved lower bound rate is lower since our instances need to satisfy more assumptions and lie in a more benign class. Another similar lower bound (/13/55 is proved in (13) for 1- 1-dimensional nonparametric contextual expected
8

---

revenue functions. However, their instances are constructed in a local-bin fashion with respect to the covariate and thus are outside our revenue function class. Therefore, their lower bound does not apply to our setting.
Proof Sketch Theorem 3, We follow similar ideas 28 to construct the instances. Firstly we set Bg = O and relieve the difficulty from contexts. Secondly, we construct a series of "bump towers" and transform them to valid expected revenue functions the form of p(1 - F())), while still preserving the intended properties. We construct each bump tower from infinitely-nester interval series [o, 1] (do, bo] > (a), b1] > ? [ag, by] D .... Specifically, we divide (ax, by] with length wk = 3 into three same-length sub-intervals and further divide the middle one into we candidate intervals. Then each of the candidate intervals forms one case of [ax+1, be+1]. For
11
interval series, we add up bump functions the nested intervals to form the bump tower. Different from [48], to construct the expected revenue functions that satisfy the 2nd-order smoothness assumption, we adopt a different basic bump function and develop gquadratically-shrikinng adding pattern. Finally, we prove that any policy will miss the peaks of some revenue function instances often enough, thus accumulating inevitable amount of the regret.
each of these infinitely
Numerical Experiments
We conduct numerical experiments to support our theoretical regret bounds of ExUCB under both Case (A) and Case (B). We consider a total horizon length T = = 28+1 that is divided into 10 episodes with the first episode length = 29. For both cases, we specify the linear parameter 80 30 and sample the i.i.d. covariates as Ir Unif(1/2, 1). For Case (A), the noise distribution is set as Uniform mixture Unif( 15, 0) + 3 Unif((O, 15); while for Case (B), we adopt another Uniform mixture 4 Unnff--15, 0) + Unif((O, 15). It can be verified that the first distribution satisfies Lipschitz and 2nd-order smoothness assumptions while the second one only satisfies the Lipschitz assumption. We apply EXUCB with different choices of [3 7 specified in Theorems T 2-22 to these two instances. For both cases, we set the constants in Algorithm I as Pmax = 50, B = 50, = C, = 20, À = 0.1. With 100 replications, the time periods in Figure 2 along with the 95% confidence intervals. The linear fits extract a slope of 0.670 for Case (A) and slope of 0.724 for Case (B), which indicates that our proved regrets of (TT333) for Case (A) and (T744) for Case (B) are sharp.
plot the log-log scale of average accumulative regrets versus
EXUOB: Mean
EXUCB: Mean
ExUCB: 96% CI
ExUCB: 95% CI
Linear fit: Slope 0.670
Linear fit: Slope 0.724
Regret
Regret
2
2
2
2
2
2
2
2
2²
2
Time
Time
(a) Case (A): ExUCB with 3 = 2/3, = 1/6.
(b) Case (B): ExUCB with , == 3/4, = 1/4.
Figure 2: Regret rates of ExUCB for Case (A) and Case (B).
7 Conclusion
In this paper, we introduce a novel Explore-then-UCD strategy to tackle the contextual dynamic pricing problem with unknown linear valuation and unknown nonparametric noise distribution F. Under Lipschitz and 2nd-order smoothness assumptions on F. ExUCB policy improves the best- known regret upper bounds to 0(32/3). Under the Lipschitz-only assumption, ExUCB matches the

---

best existing regret of ((T3/4) with better computational efficiency. In addition, we prove first (((T/55) lower bound for our considered contextual dynamic pricing problem under the Lipschitz and 2nd-order smoothness assumptions.
Acknowledgments
The authors would like to thank the helpful and constructive comments from the reviewers which led to a much improved presentation of this paper. Will Wei Sun and Yufeng Liu acknowledge support from the National Science Foundation (Award SES 2217440) Any opinions, findings, and conclusions or recommendations expressed in this material are those the authors and do not necessarily reflect the views of National Science Foundation.
References
[1] Abbasi-Yadle Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances Neural Information Processing Systems, pages 2312-2320.
[2] Agrawal, (1995). The continuum-armed bandit problem. SIAM journal on control and optimization 33, 1926-1951.
[3] Amin, K., Rostamizadeh, A., and Syed, U. (2014). Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems 27,-
[4] Auer, P., Ortner, R., and Szepesvári, C. (2007). Improved rates for the stochastic continuum- armed bandit problem. In International Conference on Computational Learning Theory, pages 454-468. Springer.
[5] Ban, G.-Y. and Keskin, B. (2020). Personalized dynamic pricing with machine learning: High dimensional features and heterogeneous elasticity. Forthcoming, Management Science.
[6] Bastani, H., Simchi-Levi, D., and Zhu, R. (2019). Meta dynamic pricing: Transfer learning across experiments. Available at SSRN 3334629.
[7] Besbes, O. and Zeevi, A. (2009). Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research 57, 1407-1420.
[8] Besbes, O. and Zeevi, A. (2015). On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science 61, 723-739.
[9] Broder, J. and Rusmevichientong, (2012). Dynamic pricing under a general parametric choice model. Operations Research 60, 965-980.
[10] Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv: 1244.512
[11] Bubeck, S., Munos, R., Stoltz, G., and Szepesvari, C. (2010). X-armed bandits. arXiv preprint arXiv:1001.444
[12] Gesa-Bianchi, N., Cesari, T., and Perchet, V. (2019). Dynamic pricing with finitely many unknown valuations. In Algorithmic Learning Theory, pages 247-273. PMLR.
[13] Chen, and Gallego, G. (2021). Nonparametric pricing analytics with customer covariates. Forthcoming, Operations Research.
[14] Chen, Q., Jasin, S., and Duenyas, I. (2019). Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. Mathematics of Operations Research 44, 601-631.
[15] Chen, X., Owen, Z., Pixton, C., and Simchi-Levi, D. (2021). A statistical learning approach to personalization in revenue management. Forthcoming, Management Science.
[16] Cheung, W. C., Simchi-Levi, D., and Wang, H. (2017). Dynamic pricing and demand learning with limited price experimentation. Operations Research 65, 1722-1731.
10

---

[17] Cheung, W. C., Simchi-Levi, D., and Zhu, R. (2018). Hedging the drift: Learning to optimize under non-stationarity Available SSRN 3262050..
[18] Cohen, M. C., Lobel, I., and Paes Leme, R. (2020). Feature-based dynamic pricing. Management Science 66, 4921 1914...3.
[19] den Boer, A. V. and Keskin, N. B. (2020), Discontinuous demand functions: estimation and pricing. Management Science 66, 4516-4534.
[20] Fan, J., Guo, Y., and Yu, M. (2022). Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association pages 1-37.
[21] Foster, D. J., Gentile, C., Mohri, M., and Zimmert, J. (2020). Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems 33,.
[22] Golrezaei, N., Jaillet, P., and Liang, J. C. N. (2019). Incentive-aware contextual pricing with non-parametric market noise. arXiv preprint 1911..39
[23] Golrezaei, N., Javanmard, A., and Mirrokni, V. (2021). Dynamic incentive-aware learning: Robust pricing in contextual auctions. Operations Research 69, 297-314.
[24] Javanmard, A. (2017). Perishability of data: dynamic pricing under varying-coefffiient models. The Journal of Machine Learning Research 18, 1714-1744.
[25] Javanmard, and Nazerzadch, H. (2019). Dynamic pricing in high-dimensions. The Journal of Machine Learning Research 20, 315-363.
[26] Javanmard, A., Nazerzadeh, H., and Shao, S. (2020). Multi-product dynamic pricing in high- dimensions with heterogeneous price sensitivity. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2652-2657, IEEE.
[27] Keskin, N. B. and Zeevi, A. (2014). Dynamic pricing with an unknown demand model: Asymptotically optimal memi-myopie policies. Operations Research 62, 1142-1167.
[28] Kleinberg, R. (2004). Nearly tight bounds for the aantinuum-armens bandit problem. Advances in Neural Information Processing Systems 17,-
[29] Kleinherg, R. and Leighton, (2003). The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594-605. IEEE.
[30] Krishnamurthy, A., Lykouris, T., Podimata, C., and Schapire, R. (2021). Contextual search in the presence of irrational agents. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 910-918.
[31] Lattimore, T. and Szepesvári, (2020). Bandit algorithms. Cambridge University Press.
[32] Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning. pages 5662-5670. PMLR.
[33] Liu, A., Leme, R. P., and Schneider, J. (2021). Optimal contextual pricing and extensions. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1059- 1078. SIAM.
[34] Lobel, I., Leme, R. P., and Vladu, A. (2018). Multidimensional binary search for contextual decision-making. Operations Research 66, 1346-1361.
[35] Luo, Y. Sun, W. W., et al. (2021). Distribution- free contextual dynamic pricing. arXiv preprint 2rX1v:2109.0334..
[36] Mao, J., Leme, R., and Schneider, (2018). Contextual pricing for lipschitz buyers. In Advances in Neural Information Processing Systems, pages 5643-5651.

---

[37] Misra, K., Schwartz, E. M., and Abemnethy, J. (2019). Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science 38, 226-252.
[38] Nambiar, M., Simchi-Levi, D., and Wang, H. (2019), Dynamic learning and pricing with model misspecificatiin. Management Science 65, 4980-5000.
[39] Pacchiano, A., Phan, M., Abbasi Yadkori, Y., Rao, A., Zimmert, J., Lattimore, T., and Szepesvari,
C. (2020). Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems 33,,
[40] Perchet, V., Rigollet, P., et al. (2013). The multi-armed bandit problem with covariates. The Annals of Statistics 41, 693-721.
[41] Qiang. S. and Bayati. M. (2016). Dynamic pricing with demand covariates. Available at SSRN 2765257.
[42] Russac, Y., Vernade, C., and Cappé, O. (2019). Weighted linear bandits for non-stationary environments. In Advances in Neural Information Processing Systems, pages 12040-12049.
[43] Shah, V., Johari, R., and Blanchet, J. (2019). parammearetticccc dynamic contextual pricing, In Advances in Neural Information Processing Systems, pages 2363-2375
[44] Wang, Y., Chen, B., and Simchi-Levi, D. (2021). Multimodal dynamic pricing. Forthcoming, Management Science.
[45] Wang. Y., Chen, X.. Chang, X., and Ge, D. (2020). Uncertainty quantification for demand prediction in contextual dynamic pricing, Forthcoming, Production and Operations Management.
[46] Wang, Z., Deng, S., and Ye, Y. (2014). Close the gaps: A learning-while-donn while-doinie algorithm for single-product revenue management problems. Operations Research 62, 318-331.
[47] Xu, J. and Wang, Y.-X. (2021). Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems 34,.
[48] Xu, J. and Wang, Y.-X. (2022). 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.
[49] Zhao, P.. Zhang, L.. Jiang, Y., and Zhou, Z.-H. (2020). A simple approach for non-stationary linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS, volume 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We summarized our main contributions at the end of Section To support these results, rigorously specified the problem settings, pre- sented the algorithms and theoretical analysis, and conducted numerical experiments.
(b) Did you describe the limitations of your work? [Yes] In Section 5.2, we discussed the gap between our proved upper and lower bounds. It still an open problem to further close the gaps.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Appendix D, we discussed the issue of pricing discriminations. However, this issue naturally exists and algorithms would not worsen the cases. In fact, our proposed algorithms may help identify the right prices for both buyers and sellers, and thus improve the market efficiency.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? Yes] Our numerical experiments only used simulated data. The simulated data has no relations with natural sciences or human subjects. The numerical simulation only for validating our theoretical results.
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] full set of seven assumptions in Section "Technical Assumptions". In each of our lemma, proposition and theorems, we stated the exact assumptions it requires among these seven assumptions.
We stated a
(b) Did you include complete proofs all theoretical results? [Yes] In Appendix A, we completely proved all theoretical results we claim.
3. If you ran 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] We included all codes in the supplementary material. The codes are accompanied with instant explanations. We also provided "Readme" document with instructions running the codes to reproduce our results. There is no input data for our codes as we simulated the data in our codes.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] As we considered online learning problems, we did not pre-train the algorithms. However, we did specify the hyperparameters and the way they were chosen in Section 6.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We report all error bars with 0.95 coverage by using the 0.025 and 0.975 quantiles of the 100 replication results.
(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)? [Yes] We ran all numerical experiments on laptop. We reported the time consumed for each replication our codes.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We did not use existing assets.
(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 a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing or conduct research with human subjects.
(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]
13


Reviews:
[{"review_id": "wmO4zB1c2Sq", "reviewer": "Reviewer_oFR9", "summary": "This paper studies the learning of posted prices in a bandit setting with buyer valuations having a linear structure + noise. They provide regret guarantees under different sets of assumptions on the distribution of the noise. When the noise cdf F is only Lipschitz, it recovers the upper-bound guarantee $\\tilde{O}(T^{\\frac{3}{4}})$ of [48]. If the expected revenue function (under F) additionally satisfies a strong-concavity property locally at its maximum, this work provides a $\\tilde{O}(T^{\\frac{2}{3}})$ regret guarantee that improves over the $\\tilde{O}(T^{\\frac{2}{3}\\vee (1-\\alpha)})$ from [35]. Finally, it formalizes the $\\Omega(T^{\\frac{3}{5}})$ lower-bound hinted in [35] for the same assumptions.", "questions": "I'm not sure to understand why the knowledge of $T$ is so crucial to need to use a doubling trick:\n* Anytime concentration inequalities are usually used so UCB does not need the knowledge of $T$\n* The exploration can be done continuously over time by choosing to explore with proba $t^{-\\frac{1}{3}}$ at each time step $t$\n\nI know this remark also applies to [35] so I probably missed something.\n\n", "limitations": "I don't see an obvious limitation / negative impact that is relevant.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my opinion, the paper has mainly two contributions that concern the second set of assumptions where the expected revenue is \"locally strongly concave\":\n1. Improving the upper-bound of [35]\n2. Providing a lower-bound\n\nMy main critic is about the significance of the first contribution. Indeed, the algorithm follows a similar doubling trick period split as [35] and it feels like a strait-forward extension: \n1. It is possible to perform pure exploration on $O(\\ell_k^\\beta)$ samples per period without impacting the regret guarantee as long as $\\beta \\leq \\frac{2}{3}$ (so the additional regret is bounded by $\\tilde{O}(T^{\\frac{2}{3}})$)\n2. these $\\ell_k^\\beta$ can be used to estimate $\\hat{\\theta}_{k+1}$ which by Hoeffding concentration will lead to $\\|\\hat{\\theta}_k - \\theta_0\\|_1 = O(\\ell_k^{-\\frac{\\beta}{2}})$\n3. Remember the proof of [35] ensures that: If the estimate $\\hat{\\theta}_k$ is such that $\\|\\hat{\\theta}_k - \\theta_0\\|_1 = O(\\ell_k^{-\\alpha})$, then the regret is bounded by $\\tilde{O}(T^{\\frac{2}{3}\\vee (1-\\alpha)})$. \n4. Using $\\alpha = \\frac{\\beta}{2}$ and choosing $\\beta = \\frac{2}{3}$ leads to an upper-bound on the regret that is $\\tilde{O}(T^{\\frac{2}{3}})$\nExcept for this additional exploration, the algorithm is very similar to [35].\n\n\nThen, the paper is hard to follow. A couple of examples:\n* The perturbed linear bandit is introduced at the very beginning, at this point, it's hard to make the link with the problem. This link is only explained much later in the paper page 7.\n* It's a bit hard to understand the role of the discretization without reading [35]", "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": "bCxvrYzrJYU", "reviewer": "Reviewer_joW3", "summary": "This paper studies dynamic pricing with contextual information under linear customer valuation model. The paper considers two types of market noise distribution and proposes a unified algorithm for the two types. The proposed algorithm is nearly optimal for one type and improve existing algorithm for the other. The paper also establishes a new lower bound and conducts numerical experiments.", "questions": "How to configure the hyperparameters $C_1$ and $C_2$ of ExUCB in practice?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well written and well organized. For Lipschitz and concavity market noise, the paper improves the existing regret bound and provides a better lower bound. The theoretical result is also verified by numerical experiments.\n\nWeaknesses:\nThe time and space complexity of the proposed algorithm is unclear, which may hinder its practical applications.", "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": "XEkP3ZUotXe", "reviewer": "Reviewer_JM47", "summary": "This paper studied the problem of contextual pricing problem with the customer's evaluation is linear in the context, with an unknown market noise $F$. The paper proposed an ExUCB policy to tackle this setting, 1) with Lipshitz and concavity smoothness assumptions, the ExUCB algorithm achieves $\\tilde{O}(T^{2/3})$ regret. 2) with only Lipschitz smoothness assumptions, the ExUCB matches the best existing upper bound as $\\tilde{O}(T^{3/4})$. Additionally, the paper gives proof of the lower bound of $\\tilde{O}(T^{3/5}$ ) for the Lipschitz and concavity smoothness assumptions. ", "questions": "1. In Table 1, what is the range of $\\alpha$?\n\n2. How is this setting different from linear bandit?", "limitations": "If this paper can include a conclusion section in the end, that would be great. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The presentation of this paper is super clean, i.e., with table (Table 2) and figure illustration(Figure 1), and the descriptions of the algorithms are clean. \n\n2. The paper carefully analyzes the behavior of ExUCB under different settings with different algorithm parameters, which implies the generality of the proposed algorithm.\n\n3. The paper also provides a regret lower bound under the Lipshitz and Concavity smoothness, and clearly explain the intuition behind the proof of the lower bound. \n\n4. The paper clearly states their assumptions' generality with citations of recent literature.\n\n5. The paper illustrates the algorithm's empirical performance. \n\nWeakness:\n\nNo conclusion section. [Addressed in the rebuttal period. ]\n\nMinor Issues:\n1. Some of the theorem statement is incomplete:\n\n-- [line 252-253] proposition 1:it should be \"there exists positive $C_1', C_2'$ \\emph{and $C_3'$}'\"\n\n2. Section 3.1 lists many assumptions without connecting paragraphs between them.\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": "4eGaOUtBOHT", "reviewer": "Reviewer_jepC", "summary": "This paper studies an online contextual dynamic pricing problem with linear-noisy valuations and Boolean feedback.\n\nThe author introduces an algorithm, ExUCB, that is a combination of epsilon-greedy and Upper Confidence Bound algorithms.\n\nThey show that their algorithm would achieve an $\\tilde{O}(T^{\\frac23})$ regret upper bound under Lipschitz and \"concavity\"(see Strengths and Weaknesses session below) assumptions, which improves existing results substantially. They also show that ExUCB would achieve an $\\tilde{O}(T^{\\frac34})$ regret upper bound under a Lipschitz assumption only, which matches existing results but with a more efficient algorithm. They also have an $\\tilde{\\Omega}(T^{\\frac35})$ lower bound for the Lipschitz and concavity setting.\n\nThey finally presents numerical results that matches their theories.", "questions": "Questions:\n\n(0) Recall my question above regarding Assumption 7: is it really a concavity assumption, or smoothness instead?\n\n(1) What are the regret dependences on the feature dimentionality $d_0$? Are they still polynoimal, or they have to become exponential? To be optimal is not required, but this would contribute to the comparisons with other exisiting results on the same problem setting.\n\n\nSuggestions:\n\n(1) The discussions in Remark 1 on the $\\Omega(T^{\\frac35})$ lower bound of [35] should be earlier (i.e., in Introduction or Literature Review). This would cause misunderstandings as you also have a $\\tilde\\Omega(T^{\\frac35})$ lower bound.\n\n(2) It would make sense to highlight your ExUCB algorithm on the computational efficiency even it matches instead of improving the existing result of [48].\n\n(3) Notations $d_0$ and $d_k$ for $k=1,2,\\ldots, n$ are easy to confound. Maybe replace one of them instead.", "limitations": "Yes. They mentioned their limitations and discussed the ethic issues related to their paper. It would be better if a discussion/conclusion session occurs at the end of the main pages.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n (1) First of all, the theoretical result on this problem (especially Case (a)) is better than existing works. Two existing works [23] and [35] introduced \\epsilon-greedy and UCB methods for pricing sequentially, but each of them suffered suboptimality and is hard to improve. This work eases these suboptimalities by subtly combining them with each other! \n\n(2) They also improve the algorithm computational efficiency on Case (b) where their result matches existing best results (under additional assumptions) but not improve, which lets their algorithm more practical.\n\n(3) Their lower bound is developed based on existing methods but still meaningful.\n\n(4) Their numerical experiments matches their theoretical results very tightly.\n\n(5) Their writing quality is good.\n\n\nI think this work should be worth at least 7, as they indeed improve existing results in an interesting way. However, there are still some doubts on my side. I'll tentatively give a 6 and promise to rise my score as long as the authors address my concerns.\n\nWeakness: \n\n(1) (This is a question, but seems rather important.) What they claimed in Assumption 7 is actually a 2nd-order-smooth instead of  a concavity. See [15]: they have both upper and lower constant bound on the 2nd-order derivatives at p^* by assuming both smoothness and concavity, but you only have upper bound (i.e. smooth). Please check if this affects any of your claims or the fairness of any comparison with existing results (e.g., is your lower bound still unique).\n\n(2) Assumptions are slightly more than mild. E.g., Assumption 2 (especially the condition number lower bound $c_0$) is not assumed in some of [15,23,26,28,35,48]. Assumption 5 can be implied by 4. (P.S., Assumption 3 combining with Assumption 4 is indeed exactly a bounded noise assumption in [23,26,48].)\n\n(3) Missing of results and/or discussions in some related works. E.g., [44] has an $\\Omega(T^{\\frac{m+1}{2m+1}})$ lower bound that can fill in the blank of Table 1. E.g.2., Some works in contextual searching should also be briefly discussed, including:\n\n      [a.1] A. Liu et al. Optimal contextual pricing and extensions. (SODA-21)\n\n      [a.2] A. Krishnamurthy et al. Contextual search in the presence of irrational agents. (STOC-21)\n\nTheir various assumptions on the noise distributions need discussing.", "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