Logarithmic Regret in Feature-based Dynamic Pricing
Authors: Jianyu Xu
Yu-Xiang Wang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: dynamic pricing
online learning
adversarial features
optimal regret
affine invariant
distribution-free.

Abstract: Feature-based dynamic pricing is an increasingly popular model of setting prices for highly differentiated products with applications in digital marketing, online sales, real estate and so on. The problem was formally studied as an online learning problem [Javanmard & Nazerzadeh, 2019] where a seller needs to propose prices on the fly for a sequence of $T$ products based on their features $x$ while having a small regret relative to the best ---"omniscient"--- pricing strategy she could have come up with in hindsight. We revisit this problem and provide two algorithms (EMLP and ONSP) for stochastic and adversarial feature settings, respectively, and prove the optimal $O(d\log{T})$ regret bounds for both. In comparison, the best existing results are $O\left(\min\left\{\frac{1}{\lambda_{\min}^2}\log{T}, \sqrt{T}\right\}\right)$ and $O(T^{2/3})$ respectively, with $\lambda_{\min}$ being the smallest eigenvalue of $\mathbb{E}[xx^T]$ that could be arbitrarily close to $0$.  We also prove an $\Omega(\sqrt{T})$ information-theoretic lower bound for a slightly more general setting, which demonstrates that "knowing-the-demand-curve" leads to an exponential improvement in feature-based dynamic pricing. 

Logarithmic Regret in Feature-based Dynamic Pricing
Jianyu Xu Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 93106 xu_jy15eucsb. edu
Yu-Xiang Wang
Department Computer Science University of California, Santa Barbara Santa Barbara, CA 93106 yuxiangu@cs ucsb edu
Abstract
Feature-based dynamic pricing is an increasingly popular model of setting prices for highly differentiated products with applications in digital marketing, online sales, real estate and so on. The problem was formally studied as an online learning problem [Javanmard and Nazerzadeh, 2019] where a seller needs propose prices on the fly for sequence of I products based on their features while having a small regret relative to the best "ommiscieett" -pricing strategy she could have come up with in hindsight. We revisit this problem and provide two algorithms (EMLP and ONSP) for stochastic and adversarial feature settings, respectively, and prove the optimal (d T') regret bounds for both. In comparison, the best existing results are O min
log T, vT) and O(T2/3) respectively, with Amin being the smallest eigenvalue of B[xx²" that could be arbitrarily close to O. We also prove an (2(T) information-thhoeeeee lower bound for slightly more general setting, which demonstrates that "knowing-the-demaan ree-demmandcuurve leads to an exponential improvement in feature-based dynamic pricing.
Introduction
The problem of pricing find [1897]. In order to locate the optimal price that maximizes the revenue, a firm may adjust their prices of products frequently, which inspires the dynamic pricing problem. Existing works [Kleinberg and Leighton, 2003, Broder and Rusmevichientong, 2012, Chen and Farias, 2013, Besbes and Zeevi, 2015] primarily focus on pricing a single product, which usually will not work well another setting when thousands of new products are being listed every day with no prior experience in selling them. Therefore, seek methods that approach an acceptable-and- and-profitable price with only observations on this single product and some historical selling records of other products.
price has been studied since Cournot
In this work, we consider a "feature- based dynamic pricing" problem, which was studied by Amin al. [2014]. Cohen et al. [2020], Javanmard and Nazerzadeh [2019]. In this problem setting, sales session (product, customer and other environmental variables) is described by a feature vector, and the customer's ' expected valuation is modeled as linear function of this feature vector.
Feature-bass dynamic pricing. For t = 1,2, ...,, ...,,"T" T:
1. A feature
2, Rd is revealed that describes sales session (product, customer and context). The customer valuates the product as w: = x 0" Ni.
3. The seller proposes a price U, 0 concurrently (according to æ; and historical sales records).
4. The transaction is successful if e, & w., ie.. the seller gets reward (payment) of r. e, 1 S wx).
Here T' is unknown to the seller (and thus can go to infinity), xy,' 's can be either stochastic (e.g.. each sales session is drawn i..d.) or adversarial (e.g.. the sessions arrive in a strategic sequence). 0" T is a fixed parameter for all time periods, N, a zero-mean noise, and 1, (v) wy) an indicator that equals if 04 I and otherwise. In this faline-fashioee setting, we only see
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table I: Related Works and Regret Bounds w.r.t. T
Algorihh
Work
Regret (upper)
Feature
Nosse
LEAP
[Amin 2014]
O(T+)
iid.
Noise-free
LllipsoiPPriiing
[Cohen et al., 2020)
O'ling 2'
adversaria
Noice-free
FXlipsoidEXP4
[Cohen et al., 2020)
O(T7)
adversarial
Gaussiann
PricingSearch
Leme und Schneiler, 2018]
O7log log: }]
adversarial
Nosse-Tree
RMLP
Uavanmard and Nazerzadhh, 2019]
Oiling C
iid..
Log concuee distribution
O(vT))
RMLP-2
Javanmand and Nazerzadhh, 2019]
OlyTT)
sid.
Known purametitc family of log concave.
Shallow Paccing
CorPY
[Krishaaurrly et al., 2021]
[Coben et 2020]
O(yoky(log
adversarial
Gaussian, known O( O(yrzzr)
Algorihhm 2 (MSPP)
[Liu 2021]
Oflog (")
adversarial
Noise-free
FMLP
paper
Ofloy,
Striclly log-concave, distrillation-kmoen
ONSP
This piper
O[logg]
adversurial
Stricily log-soncarve, distribution known
Cmin is the restricted eigenvalue condition. It reduces to the smallest eigenvalue of E/err' [in the
low-dimensional case we consider.
and sell one product at each time. Also, the feedback is Boolean Censored, which means we can only observe 1, instead of knowing w/ directly. The best pricing policy for this problem is the one that maximizes the expected reward, and the regrer of a pricing policy accordingly defined as the difference of expected rewards between this selected policy and the best policy.
Summary of Results. Our contributions are threefold.
1. When 24y3 's are independently and identically distributed (i.i..) from an unknown distribution, we propose an "Epoch-based Max-Likelihood Pricing (EMLP)" algorithm that guarantees regret bound at (d log 7'). The design of EMLP is similar to that of the RMLP algorithm in Javanmard and Nazerzadeh [2019], but our new analysis improves their regret bound at O(VT) when B[ax"" ] is near singular.
2. When F2 's are adversarial, we propose an Denline-Newton-to that achieves Od T) regret constant-level noises for the first time, which exponentially improves the best existing result of O(T2/3) [Cohen et al., 2020].1
Pricing (ONSP)" algorithm
3. Our methods that achieve logarithmic regret require knowing the exact distribution of N, in advance, as is also assumed in Javanmard and Nazerzadeh [2019]. We prove an ((VT) lower bound on the regret if N₂ _N(0, (?) where is unknown, even with Hr given and 2; fixed for all t.
The O(log T' regret of EMLP and ONSP meets the information-theoretie lower bound [Theorem 5, Javanmard and Nazerzadeh, 2019]. In fact, the bound is optimal even when wy is revealed to the learner [Mourtada, 2019]. From the perspective of characterizing the hardness of dynamic pricing problems, we generalize the classical results on "The Value of Knowing a Demand Curve" [Kleinberg and Leighton, 2003] by further dividing the random-valuation class with exponential separation of: (1) Ollog T) regret for knowing the demand curve exactly (even with adversarial features), and (2) ((VT) regret for almost knowing the demand curves (up to a one-parameter parametric family).
2 Related Works
In this section, we discuss our results relative to existing works on feature-based dynamic pricing, and highlight the connections and differences to the related settings of contextual bandits and contextual search (for broader discussion, see Appendix A).
Feature-based Dynamic Pricing. There is a growing body of work on dynamic pricing with linear features [Amin et al., 2014, Qiang and Bayati, 2016, Cohen et al., 2020, Javanmard and Nazerzadeh, 2019]. Table summarizes the differences the settings and results?. Among these work, our paper directly builds upon [Cohen et al., 2020] and [Javanmard and Nazerzadeh, 2019], as we share the same setting of online feature vectors, linear and noisy valuations and Boolean-censored feedback. Relative to the results in [Javanard and Nazerzadeh, 2019], we obtain Odd log T') regret under weaker assumptions on the sequence of input features- - in both distribution- stochastic feature
Previous works [Cohen et al.. 2020, Krishnamurthy et al.. 2021] did achieve polylog regrets, but only for negligible noise with O (log))
We only concem the dependence on I' since there are various different assumptions on d.

---

setting and the adversarial feature setting. It is to be noted that [Javanmard and Nazerzadeh, 2019] also covers the sparse nigh-dimensional setting, and handles a slightly broader class of demand curves. Relative to [Cohen et al., 2020], in which the adversarial feature-based dynamic pricing was first studied, our algorithm ONSP enjoys the optimal Oddlog 7) regret when the noise-level is a constant. In comparison, Cohen et al. [2020] reduces the problem to contextual bandits and applies the (computationally inefficient) "EXP-4" algorithm [Auer et al., 2002] to achieve a ((T2/$) regret. The "bisection" style-algorithm in both Cohen et al. [2020] and Krishnamurthy et al. [2021] could achieve ((poly(d)))p log( regrets but requires small-variance subgaussian noise satisfying
O TlogT
Lower Bounds. Most existing works focus on the lower regret bounds of non-feature-base models. Kleinberg and Leighton [2003] divides the problem setting as fixed, random, and adversarial valua- tions, and then proves each a (log log 7). ((VT), and (TT2/3) regret, respectively. Broder and Rusmevichientong [2012] further proves a ((VT) regret in general parametric valuation models. In this work, we generalize the methods of Broder and Rusmevichientong [2012] to our feature- based setting and further narrow it down to linear-feature Gaussian-noisy model. As a complement to Kleinherg and Leighton [2003], we further separate the exponential regret gap between: (1) O(log T) of the hardest (adversarial feature) paraly- model, and (2) (VVT) of the simplest (fixed known expectation) unknown-o Gaussian model.
Contextual Bandits. For readers familiar with the online learning literature, our problem can be reduced to contextual bandits problem [Langford and Zhang, 2007, Agarwal et al., 2014] by discretizing the prices. But this reduction only results in (TT233) regret, as does not capture the special structure of the feedback: an accepted price indicates the acceptance of all lower prices, and vise versa. Moreover, when comparing to linear bandits [Chu et al., 2011], it is the valuation instead of the expected reward that we assume to be linear.
Contextual Search. Feature-based dynamic pricing is also related to the contextual search problem [Lobel et al., 2018, Leme and Schneider, 2018, Liu et al., 2021, Krishnamurthy al., 2021], which often involves learning from Boolean feedbacks, sometimes with a "pricing loss" and "noisy" feedback. These shared jargons make this problem appearing very similar to our problem. However, except for the noiseless cases [Lobel et al., 2018, Leme and Schneider, 2018], contextual search algorithms, even with "pricing losses" and "Noisy Boolean feedback" [e.g.. Liu al., 2021], do not imply meaningful regret bounds in our problem setup due to several subtle but important differences in the problem settings. Specifically, the noisy-boolean feedback model of [Liu et al., 2021] is about randomly toggling the "purchase decision" determined by the noiseless valuation x "0" with probability 0.5 - e. This is incompatible to our problem setting where the purchasing decision is determined by a noisy valuation x 0" + Noise. Ultimately, in the setting of [Liu et al., 2021], the optimal policy alway plays x: T0", but our problem is harder in that we need to exploit the noise and the optimal price could be very different from x: f". Krishnamurthy et al. [2021] also discussed this issue explicitly and considered the more natural noisy Boolean feedback model studied in this paper. Their result, similar to Cohen et al. [2020], only achieves a logarithmic regret when the noise on the valuation is vanishing in an Ö(1/T) rate.
3 Problem Setup
Symbols and Notations. Now we introduce the mathematical symbols and notations involved in the following pages. The game consists of 7 rounds. Ie E Rd, E RR,, and N; E RR denote the feature vector, the proposed price and the noise respectively at round = 1, 2, ..., T- We denote the product We : ... 6" as an expected valuation. At each round, we receive a payoff (reward)
= 0. 1
where the binary variable 1, indicates whether the price is accepted or not, i.c., 1, = 1(v, S wv)) As
we may estimate 0* in our algorithms, we denote 0: as an estimator of 0", which we will formally denote some functions that are related to noise distribution:
define in the algorithms. Furthermore, F(w) and (w) denote the cumulative distribution function (CDF) and probability density function (PDF) sequentially. We know that F" F"(w)) = f(w) if we assume differentiability. denote all data observed up to round (i.c., feature, price and payoff of all past rounds), we define
To concisely
3 As an explicit example, suppose the valuation x T 6- = 0. then the optimal price must > in order to avoid zero return. In an epoch-design situation, subscript (k, indicates round t of epoch k.
3

---

hTst(T) [ ot, L,) for = 1,,, ",,,, hist(T) represents the transcript of all observed random variables before round (T + 1).
We define
(0) == - log (1 F(v. - xe 0)) - (1-1,) log (F(vz - xe 0))
(1)
negative log- likelihood function at round t. Also, define expected log- likelihood function (0)::
(O) E,, ([))))))))
Notice that we will later define (x( which is, however, not expectation.
Definitions of Key Quantities. We firstly define an expected reward function g(v, u).
F'v g(u u) == E'r, (0t = v, 2 u/ = v Pie I z + +N, = v. (1-F(v - u)). This indicates that if the expected valuation is and the proposed price is then the (conditionally) expected reward is g(v, u). Now we formally define the regret of policy (algorithm) A as is promised in Section
(3)
Definition (Regret), Lel A. : Rd x (R2, (0, 13) 11) + be a policy of pricing, i.e.
hist(i - 1)) = Uz. The regret of A is defined as follows.
RegA Emnx mmxxg(v, g(v, me 0-) -g(A(zi, hist(l - ()),x(0'))
max
(4)
Here hist(t- 1) is the historical records until (t - 1)th round.
Summary of Assumptions. We specify the problem settings by proposing three assumptions.
Assumption (Known, bounded, strictly log-concave distribution). The noise N₂ is independently and identically sampled from distribution whose CDF is F. Assume that F E C² is stricily increasing and that F and (1 11-17 F) are strictly log-concave. Also assume that and I are bounded, and denote By= == suPwER [ww), By == SuPWER [w(w) as two constants.
Assumption 2 (Bounded convex parameter space). The true parameter 0" E H. where H. C {0: |10||2 S } is a bounded convex set and B₁ is a constant. Assume IH is known to us (but 0* is not).
Assumption 3 (Bounded feature space). Assume E D C {x |||||2 S B2}, Vt = 1,2.....2 T.
Also, < x 0 < B, Vx E D, 4O E H., where = Bi B2 is constant.
Assumption 2 and 3 are mild as we can choose B₁ and B2 large enough. In Section 4.1, we may add further complement to Assumption to form a stochastic setting. Assumption stronger since we might not know the exact CDF in practice, but it is still acceptable from an information- theoretic perspective. There are at least three reasons that lead to this assumption: Primarily, this is necessary we hope to achieve an Ologg(T) regret. We will prove in Section 5.3 that an (vVT) is unavoidable if we cannot know parameter exactly. Moreover, the pioneering work of Javanmard and Nazerzadeh [2019] also assumes a known noise distribution with log- concave CDF, and many common distributions although we did not present a method to precisely estimate a in this work, it is reasonable algorithm replace with plug-in estimator estimated using historical offline data. As have shown, not knowing requires O(vT) regret in general, but the lower bound does not rule out the plug-in approach achieving a smaller regret for interesting subclasses of problems in practice.
actually strietly log-concave, such as Gaussian and logistic. Besides,
Finally, we state a lemma and define argmax function helpful for our algorithm design.
Lemma 2 (Uniqueness). For any 2 O, there exists a unique 2 O such that g(v", u) maxveR g(v, u). Thus, we can define greedily pricing function that maximizes the expected reward:
J(u)= == arg max gvv, u)
Please see the proof of Lemma 2 in Appendix B.1.
4 Algorithms
In this section, we propose two dynamic pricing algorithms: EMLP and ONSP, for stochastic and adversarial features respectively.
In fact, F' and (1 F') both log-concave if its PDF is conccve,, according Prekopa's Inequality.

---

Algorithm Epoch- max-likelihood pric- ing (EMLP)
Algorithm 2 Online Newton Step Pricing (ONSP)
Input: Convex and bounded set IHI Observe 21, randomly choose in and get r1-
Input: Convex and bounded set IH, 61, param-
eter 7, > 0
Solve 0, - arg mingga 1, (0);
Set Ao = 6 L7i for ( = 1 to T do
for k to llog2 T] + do
Set 7k- 2%-1;
Observe Zz;
for t= to Tı do
Set price v4- J (2x 02);
Observe 0kk.
Receive ra = 1t 1
Set price UkRt = ( {
Set surrogate loss function (c();
Calculate V. = (o)(
Receive rk,t = Ukk 11;
Rank-1 update: A, = A + V.V.
end for
Solve: 0x+1 arg mingen (f). where
Newton step: 0 = 0. A
Lx(0) = 1 E1 (0).
Projection: 0c+1 = I (0++1)-
end for
end for
4.1 Pricing with Distribution-Free Stochastic Features
Assumption 4 (Stochastic features). Assume ~ D C D are independently identically distributed (i.idd) from an unknown distribution, for any 1,2,...,
The first algorithm, Epoch-based Max-Likelihood Pricing (EMLP) algorithm, is suitable for stochastic setting defined by Assumption 4. EMLP proceeds in epochs with each stage doubling the length of the previous epoch. At the end of each epoch, we consolidate the observed data and solve a maximum likelihood estimation problem to learn A max likelihood estimator (MLE) obtained by minimizing (0) == +e ET= (o)) which is then used in the next epoch as if it is the true parameter vector. In the equation, k, Th denotes the index and length of epoch k. The estimator is computed using data in hist(k), which denotes the transcript for epoch 1 ~ k. The pseudo-code of EMLP is summarized in Algorithm 1. In the remainder of this section, we discuss the computational efficiency and prove the upper regret bound of O T))
Computational Efficiency. The calculations in EMLP are straightforward except for arg min La (0) and (u). As g(v, u) is proved unimodal in Lemma 2, we may efficiently calculate J(u) by binary search. We will prove that 4., is exp-concave (and thus also convex). Therefore, we may apply any off-the-shelf tools for solving convex optimization.
MLE and Probit Regression. A closer inspection reveals that this log- likeliiel function corre- sponds to a probit [Aldrich et al., 1984] or logit model [Wright, 1995] for Gaussian or logistic noises. See Appendix C.2.1.
Affine Invariance. Both optimization problems involved depend only on x: 8, so if we add any affine transformation to x into f = Ar. the agent can instead learn new parameter of 0 (AT) ) and achieve the same u, = _ 0- Also, the regret bound is not affected as the upper bound B over x 8 does not change 6 Therefore, it is only natural that the regret bound does not depend on the distribution r, nor the condition numbers of E[xx" "] (i.e., the ratio of Amax Amin).
4.2 Pricing with Adversarial Features
In this part, we propose an "Online Newton Step Pricing (ONSP)" algorithm that deals with adversarial } series and guarantees O ((dlog regret. The pseudo-code of ONSP is shown as Algorithm 2. In each round, uses the likelihood function as a surrogate loss and applies "Online Newton (ONS" method to update Q. the next round, it adopts the updated and sets price greedily. In the remainder of this section, we discuss some properties of ONSP and prove the regret bound.
The calculations of ONSP are straightforward. The time complexity of calculating the matrix inverse A, is O(d)), which fair as d is small. In nigh-dimensional cases, we may use Woodbury matrix identity? to reduce it to (dd²) as we could get A directly from the latest round.
Here A is assumed invertible, otherwise the mapping from 3; to us does not necessarily exist.
7 (A + xx ) A I+2 A A'xx(A -
5

---

Regret Analysis
In this section, we mainly prove the logarithmic regret bounds of EMLP and ONSP corresponding to stochastic and adversarial settings, respectively. Besides, we also prove an 52( ((vT) regret bound on fully parametric F with one parameter unknown.
5.1 Ogdlog T) Regret of EMLP
In this part, present the regret analysis of Algorithm 1. First of all, propose the following theorem as our main result on EMLP.
Theorem (Overall regret), With Assumptions 2, and 4, the expected regret of EMLP can be bounded by:
RegemuL S 2C,dlog
(6)
where C. is a constant that depends only on F(w) and is independent to D.
The proof of Theorem 3 sophisticated. For the sake of clarity, we next present an inequality system roadmap toward the proof. After this, we formally illustrate each line of it with lemmas.
Since EMLP proposes [( 0x) in every round of epoch we may denote the per-round regret as Reg. (0%), where:
Reg. (0) == (z] ),,,,, (T) xz)
Therefore, sufficient to prove the following Theorem:
Theorem (Expected per-round regret). For the per-round regret defined in Equation (7), we have:
E. ((eeg,, S C.
Tk
The proof roadmap of Theorem can be written as the following inequality system.
2C
2
((R) < C B( 0*) II, -
0²) s
((a) (=)()))) S
Cdown
C dowa
(8)
We explain Equation (8) in details. The first inequality comes from the following Lemma 5. Lemma 5 (Quadratic regret bound). We have:
Reg. (0) < (0-00) xN -0 0*), vO E H., Va, E D.
+ 2B, Here C = 2B,
J(0)) By-
The intuition that function (u), u) -rd-orrrr-mmooth at (J(u*), u²). A detailed proof of Lemma 5 is in Appendix B.2.1. Note that C is highly dependent on the distribution F. After this, we propose Lemma 6 that contributes the second inequality of Equation (8).
Lemma 6 (Quadratic likelihood bound). For the expected likelihood function Le(0) defined in Equation (2), we have:
L.(0) L.(0)) 2 Cdown (0 - 0-) &t -0) EL
(10)
d logg( - F(w))
of log(((())
where Cooun =
inf wE(-B.B+J(O))
min
>0. 0. (11)
dwv
dw
Proof. Since the true parameter always maximizes the expected likelihood function [Murphy, 2012],
by Taylor Expansion we have ((()) = O, and hence (0*) (0-0") V (00000)T" (0-0")
(0)
for some 0 at* (1 a)0. Therefore, only need to prove the following lemma:

---

Lemma 7 (Strong convexity and Exponential Concavity). Suppose (()) is the negative log- sig-likelihood function in epoch time For any E HH, Ht ~ D. we have:
(0) = C. = Cdown (l((0)VI((8) 20,
(12)
Cap
f(w) f(w)2
where Cap
sup =E|-B,BBJ(0)
max
F(w)? (1- F(w))
< +00.
(13)
Proof of Lemma is in Appendix B.2.2. With this lemma, see that Lemma 6 holds.
With Lemma 5 and Lemma 6, we can immediately get the following Lemma 8.
Lemma 8 (Surrogate Regret). The relationship between Reg(O) and likelihood function can be shown as follows:
C.C (L,(0) - ((()))
Reg (8) S Coown
(14)
40 E IHI, Vo ID, where C and Cownn are defined in Lemma 5 and respectively.
Lemma 8 enables us to choose the negative log- ligeeiild function as a surrogate loss. This is not only important insight of EMLP regret analysis, but also the foundation of ONSP design.
The last inequality Equation (8) comes from this lemma:
Lemma 9 (Per-epoch surrogate regret bound). Denoting OR as the estimator coming from epoch (k- 1) and being used in epoch k we have:
1)
EA (Lx( - (x - Cep
(15)
Cdown Tk + 1
Here Cesp is defined in Equation 13, and [-] [[-]hist((k
- 1)].
Proof of Lemma 9 is partly derived from the work Koren and Levy [2015], and here give a proof sketch without specific derivations. A detailed proof lies in Appendix B.2.3.
Proof sketch of Lemma 9. We list the four main points that contribute to the proof:
Notice that (0) is strongly convex w.r.t. seminorm Z2,1" we know L. (0) is also strongly convex w.r.t. Σ T
For two strongly convex functions 91 and 92, we can upper bound the distance between their arg- org-minimals (scaled by some norm |]) with the dual norm of V(g 92).
Since a seminorm has no dual norm, we apply two methods to convert it into a norm: (I) separation of parameters and likelihood functions with "leave-one-out" method (to separately take expectations), and (2) separation of the spinning space and the null space.
As the dual data-dependent norm offsets the sum of xx to constant, Lemma 9 holds. We have so far proved Inequality (8) after proving Lemma 5, 6, 9. Therefore, Theorem 4 holds.
5.2
Od T') Regret of ONSP
Here we present the regret analysis of Algorithm 2 (ONSP). Firstly, we state the main theorem.
Theorem 10. With Assumptions 2, 3, the regret of Algorithm 2 (ONSP) satisfies: RegoNsp < C. dlogT,
(16)
where C. is a function only dependent on
Proof. Proof of Theorem 10 here is more concise than Section 5.1, because the important Lemma 7 and have been proved there. From Lemma have:
C.C -x,14(0))-440000 400)).
((J(w)), ut) - g([(w,), ut) S
(17)
Caown
With Equation 17, we may reduce the regret of likelihood functions as surrogate regret of pricing. From Lemma we see that the log-likelihood function is Cazu Cass eexooeeniillllly concave.. This enables
Con
'A function f(x) a-exponnntiaally concave iff 2 f(n) = AV
7

---

an application of Online Newton Step method to achieve logarithmic regret. Therefore, by citing from the Online Convex Optimization [Hazan, 2016], we have the following Lemma.
Lemma 11 (Online Newton Step). With parameters 7 = min ( (GD. a) and = 52D2. and > 4 guarantees:
T min h())) (Ot))
1 a S
+GD) d log
sup {1x)
t=1
t=1
Here
Caiam
D 2- B1 and G v /Cep" B2.
Cup
With Equation 17 and Lemma 11, we have:
Reg = Σ (o(J(a)), No. (o (9 v
2.C Cdown
.5
(C+
dlog T. (18)
Therefore, we have proved Lemma 10.
5.3 Lower Bound for Unknown Distribution
In this part, we evaluate Assumption and prove that an (VVT)) lower regret bound is unavoidable with even slight relaxation: Gaussian noise with unknown Our proof is inspired by Broder and Rusmevichientong [2012] Theorem 3.1, while our lower bound relics on more specific assumptions (and thus applies to more general cases).
We firstly state Assumption 5 covering this part, and then state Theorem as a lower bound:
Assumption 5. The noise N₂ ~ (N,000 independently, where < a S is fxxe and unknown. Theorem 12 (Lower bound with unknown σ). Under Assumption 2, 3, 4 and 5, for any policy (algorithm) V/ Rdd x (R2, E. 13) 1-1)-111
I and any 2, there exists a Gaussian parameter E RR,, distribution IB features and fixed parameter 0", such that: Regy 2 24000 VT.
Remark: Here assume 2; to be ii.d., which also implies the applicability adversarial features. However, the minimax regret of the stochastic feature setting is (VVT) [Javanmard and Nazerzadeh, 2019], while existing results have not yet closed the gap in adversarial feature settings.
Here we assume a fixed valuation, i.e. u" = 2, 0", Vt = 2...... Equivalently, we assume a fixed feature. The main idea of proof is similar to that in Broder and Rusmevichientong [2012]: we assume 0 02 = 1 T- and we prove that: (1) an algorithm to perform well in both cases if the o is are different by a lot, and (2) it is costly for an algorithm to distinguish the two cases if a are close enough to each other. We put the detailed proof in Appendix B.3.
Proof sketch of Theorem 12.
costly for
6 Numerical Result
In this section, conduct numerical experiments validate EMLP and ONSP. In comparison with the existing work, we implement a discretized EXP-4 [Auer et al., 2002] algorithm for pricing. as is introduced in Cohen al. [2020] (in slightly different setting). We will test these three algorithms in both stochastic and adversarial settings.
Basically, we assume d = 2, B, B2 = B and N, ~ o0) with o = 0.25. In both settings, we conduct EMLP and ONSP for = 216 rounds. For ONSP, we empirically select y and that accelerates the convergence, instead of using the values specified in Lemma 11. Since EXP-4 consumes exponential time and requires the knowledge of T in advance discretize the policy and valuation spaces, execute EXP-4 for a series of T = 2 1,2, 12. We repeat every experiment times for each setting and then take an average.
Stochastic Setting. We implement and test EMLP, ONSP and EXP-4 with stochastic { The numerical results are shown in Figure la on a log-log diagram, with the regrets divided by log(t). shows cooverreeeeeeeeess on EMLP and ONSP, while EXP-4 is in t" rate with a = 0.699.
Ad Adversarial Setting. We implement the three algorithms and test them with an adversarial {2e} 's: for the k-th epoch, i.c. t 2 2 ..... 2* we let [1. O if A 1 mod 2) and
8

---

ONSP
ONSP
EXP-
EXP4
EXP4 Linar fit, shpp
EXLP Lirear Et, dope-0.912
EXM Unear
regret/log(t
regret/log(t)
2
2
23
2
2
2
24
round
round
(a) Stochastic feature
(b) Adversarial feature
Figure The regret of EMLP, ONSP and EXP-4 on simulated examples (we only conduct EXP-4 up to 2 due to its exponential time consuming), with Figure a for stochastic features and Figure b for adversarial ones. The plots are in log-log scales with all regrets divided by log(() factor to show the convergence. For EXP-4. we discretize the parameter space with T s-sze grids, which would incur Ö regret according to Cohen al. [2020]. We also plot linear fits for Besides, we draw error bars and bands with 0.95 coverage using Wald's test. The two diagrams reveal that (i) logarithmic regrets of EMLP and ONSP in the stochastic setting. (ii) nearly-linear regret of EMLP in the adversarial setting, and (iii) O(15)) regrets of EXP-4 in both settings.
regret curves, where slope-o line indicates O(7*) regret.
Iy = [0, 1] = 0( mod 2). The numerical results are shown in Figure 1b on a log-log diagram, with the regrets divided by log(t). The log-log plots of ONSP and EXP-4 are almost the same as those in Figure la However, EMLP shows an almost linear (t" rate with 0.912) regret this adversarial setting. This is because the adversarial series only trains one dimension of 0 in each epoch, while the other arbitrarily initialized and does not necessarily converge. However, in the next epoch, the incorrect dimension is exploited. Therefore, a linear regret originates.
7 Discussion
Here discuss the coefficients Appendix we will discuss more on algorithmic design, problem modeling, and ethic issues.
regret bounds as potential extension of future works. In
Coefficients on Regret Bounds. The exact regret bounds of both EMLP and ONSP contain constant
Goo that highly depends the noise CDF F and could be large. A detailed analysis in Appendix C.1 Came.
shows that Cap. is exponentially large w.r.t. B (see Equation 39 and Lemma 21) for Gaussian noise N(0,0 which implies that a smaller noise variance would lead to a (much) larger regret bound. larger noise usually leads to more sophisticated situation, but similar phenomenons also occur in existing algorithms that are suitable for constant variance noise, such RMLP in Javanmard and Nazerzadeh [2019] and OORMLP in Wang al. [2020]. In fact, it because a (constantly) large noise would help explore the unknown parameter 8" and smoothen the expected regret. In this work, this can be addressed by increasing T since mainly concern the asymptotic regrets as T oo with fixed noise distributions. However, we admit that it indeed a nontrivial issue for finite T and small situations. There exists "ShallowPricing" method in Cohen al. [2020] that deal with very-small-variane noise setting (when Ö(+) and achieve logarithmic regret. Specifically, its regret bound would decrease as the noise variance a decreases (but would still not reach O (log log T') the noise vanishes). We might also apply this method the parameter domain and decrease B within logarithmic trials (see Cohen et al. [2020] Thm. 3), but it is still open whether log(T) regret is achievable when @(T-a) for E (0, 1).
Cason
This is very counter-nntuiive
toasstant-vaiance
preprocess
8 Conclusion
In this work, we studied the problem of online feature-based dynamic pricing with noisy linear valuation both stochastic and adversarial settings. We proposed a max-likelihood-estee algorithm (EMLP) for stochastic features and an Online-Newton-stee-- -tasb- based algorithm (ONSP) for

---

adversarial features. Both of them enjoy a regret guarantee of O(d T), which also attains the information-theoretie limit up a constant factor. Compared with existing works, EMLP gets rid of strong assumptions on the distribution of the feature vectors in the stochastic setting, and ONSP improves the regret bound exponentially from O(T2/3) to ( I') in the adversarial setting. We also showed that knowing the noise distribution (or the demand curve) required to obtain logarithmic regret, where we prove a lower bound of f2( on the regret for the case when the noise is knowingly Gaussian but with an unknown o. In addition, we conducted numerical experiments to empirically validate the scaling of our algorithms. Finally, discussed the regret dependence on the noise variance, and proposed subtle open problem for further study.
Acknowledgments
The work is partially supported by the Adobe Data Science Award and start-up grant from the UCSB Department of Computer Science, We appreciate the input from anonymous reviewers and AC as well discussion with Akshay Krishnamurthy for clarifying some details of Krishnamurthy et al. [2021].
References
A. Agarwal, D. Hsu, S. Kale, J. Langford. L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning (ICML-14), pages 1638-1646, 2014.
Aldrich, F. Nelson, and E. S. Adler. Linear Probability, Logit, and Probit Models. Number 45. Sage, 1984.
K. Amin, A. Rostamizadeh, and U. Syed. Repeated contextual auctions with strategic buyers. In Advances in Neural Information Processing Systems (NIPS-14), pages 622 22-630, 2014.
V. F. Araman and R. Caldentey. Dynamic pricing for nonperishable products with demand learning. Operations Research, 169)):166-111111 2009.
Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
G. Aydin and Ziya. Personalized dynamic pricing of limited inventories. Operations Research, 57 (6):1523-1531, 2009.
D. Besanko, S. Gupta, and D. Jain. Logit demand estimation under competitive pricing behavior: An cquilibrium framework. Management Science, 44(1 I--art-I):1533---111 1998.
D. Besanko, J.-P. Dubé, and S. Gupta. Competitive price discrimination strategies in vertical channel using aggregate retail data. Management Science, 19(9))1121-1133) 2003.
O. Besbes and A. Zeevi. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science, (14)72233-73, 2015.
J. Broder and P. Rusmevichientong. Dynamic pricing under general parametric choice model. Operations Research, 60(4))965-98) 2012.
T. Chan, V. Kadiyali, and P. Xiao. Structural models of pricing. Handbook of pricing research in marketing, pages 108-131, 2009.
N. Chen and G. Gallego. A primal-duse learning algorithm for personalized dynamic pricing with an inventory constraint. Mathematics of Operations Research, 2021.
Y. Chen and V. F. Farias. Simple policies for dynamic pricing with imperfect forecasts. Operations Research, 61(3):612-624, 2013.
W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In International Conference on Artificial Intelligence and Statistics (AISTATS-/ /), pages 208-214, 2011.
10

---

M. C. Cohen, I. Lobel, and R. Paes Leme. Feature-based dynamic pricing. Management Science, 66 (11):4921-4943, 2020.
A. A. Cournot. Researches into the Mathematical Principles of the Theory of Wealth, Macmillan, 1897.
A. 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.
M. Draganska and D. Jain. Consumer preferences and product-line pricing strategies: An empirical analysis. Marketing science, 144441644177, 2006.
G. C. Evans. The dynamics of monopoly. The American Mathematical Monthly, 31(2):77-83, 1924.
E. Hazan, Introduction to online convex optimization. Foundations and Trends in Optimization, 13-4):157-325, 2016.
R. Iyengar, A. Ansari, and S. Gupta. A model of consumer learning for service quality and usage. Journal of Marketing Research, 44(4))529-544, 2007.
A. Javanmard and H. Nazerzadeh. Dynamic pricing in aig-ddmenssion. The Journal of Machine Learning Research, 20(1):315-363, 2019.
P. L. Joskow and C. D. Wolfram. Dynamic pricing of electricity. American Economic Review, 102 (3):381-85, 2012.
V. Kadiyali, N. J. Vilcassim, and P. K. Chintagunta, Empirical analysis of competitive product line pricing decisions: Lead, follow, move together? Journal of Business, pages 459-487, 1996.
N. B. Keskin and A. Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Operations Research,
2014.
W. Kincaid and D. Darling. An inventory pricing problem. Journal of Mathemutical Analysis and Applications, 7:183-208, 1963.
R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted- price auctions. In IEEE Symposium Foundations of Computer Science (FOCS-03), pages 904- IEEE, 2003.
Koren and K. Levy. Fast rates for exp-concave empirical risk minimization. Advances in Neural Information Processing Systems (NIPS-15), pages 1477-1485, 2015.
A. Krämer, M. Friesen, and T. Shelton. Are airline passengers ready for personalized dynamic pricing? a study of german consumers. Journal of Revenue and Pricing Management, 17(2): 115-120, 2018.
A. Krishnamurthy, T. Lykouris, C. Podimata, and R. Schapire. Contextual search in the presence of irrational agents. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC-21), pages 910 (00099911960011 2021.
A. Lambrecht, K. Seim, and B. Skiera. Does uncertainty matter? consumer behavior under three-pane tariffs. Marketing Science, 26(5)x698-710, 2007.
J. Langford and T. Zhang. The gpoch-greedy algorithm for contextual multi-arme's bandits. In Advances in Neural Information Processing Systems (NIPS-07), pages 817-824, 2007.
R. P. Leme and J. Schneider. Contextual search via intrinsic volumes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS-18), pages 268-282. IEEE, 2018.
A. Liu, R. P. Leme, and Schneider. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA-21), pages 1059-1078. SIAM, 2021.
I. Lobel, R. P. Leme, and A. Vladu. Multidimensional binary search for contextual decision-making. Operations Research, 136-1333,,,,,,, 2018.

---

T. Mazumdar, S. P. Raj. and I. Sinha. Reference price research: Review and propositions. Journal of Marketing, 69(4):84-102 2005.
J. Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. arXiv preprint arXiv:1912.10754. 2019.
K. P. Murphy. Machine Learning: a Probabilistic Perspective. MIT press, 2012.
Qiang and M. Bayati. Dynamic pricing with demand covariates, arXiv preprint urXiv:160..07450 2016.
H. Schultz et al. Theory and Measurement Demand. The University of Chicago Press, 1938.
C.-H. Wang. Z. Wang, W. W. Sun, and G. Cheng. Online regularization for high-dimensional dynamic pricing algorithms. arXiv preprint arXiv:2007.02470, 2020.
Whittle. Multi-armed bandits and the gittins index. Journal of the Royal Statistical Society: Series B (Methodological), 42(2):143-144 1980.
R. Wright. Logistic regression. 1995.
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 contribution in Section "Summary of Results" part. In order to support these results, we rigorously specified the problem settings, present corresponding algorithms and their theoretical analysis as well as numerical experiments.
(b) Did you describe the limitations of your work? [Yes] In Section 7, we carefully discussed number of problems that are still open after our results being present, including noises, modeling, coefficients, etc. In Appendix C, we further showed details of these issues.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Appendix C.5, we talked about some ethic issues including pricing discriminations and privacies. However, these are all naturally existing issues, and our algorithms would not worsen the cases. In fact, the online dynamic pricing problem we considered in this work also be viewed as an online auction problem, which would improve market efficiency and help both buyers and sellers to identify the right prices with less exploration.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] In the numerical experiments, we only used simulated data that has nothing to do with the natural sciences and do not include human subjects. The paper is theoretical in nature and the purpose of the numerical simulation is to validate the theoretical predictions.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of theoretical results? [Yes] We stated three basic assumptions in Section 3 "Summary of Assumptions". We later stated Assumptions 4 and 5 for specific theorems.
(b) Did you include complete proofs of all theoretical results? [Yes] We completely proved every claim we made. In fact, our paper and appendices are filled with proofs.
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 and data the supplementary material, along with "Readme" document as instructions of running the program and reproduce results.
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Actually we did not pre-train the algorithms as we considered online learning problems. However, we did specify the hyperparameters and the way they were chosen, in Section and Figure 1.
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We report all error bars and error bands with 0.95 coverage using Wald's test.
(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] We just ran all numerical experiments on laptop. We did mention that the experiment of EXP-4 is very time- consuming. However, this is because EXP-4 is actually an exponential time algorithm, and in fact EXP-4 is existing algorithm instead of our contributions.
If you are 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] 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 to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nFoz0a1Dc8N", "reviewer": "Reviewer_FNhv", "summary": "This paper studies the problem of feature-based dynamic pricing and offers strong new regret bounds. The headline result is the construction of Online Newton Step Pricing and the proof that it obtains regret $O(d \\log T)$ even with adversarial features. This had been proven before only by assuming either (1) small noise or (2) iid features plus a minimum-eigenvalue assumption.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThis paper studies the problem of feature-based (or contextual) dynamic pricing. There exists an unknown vector $\\theta$ that characterizes a consumer's preferences. At every period $t=1,...,T$, a new product is on offer with a set of characteristics described by $x_t$. The consumer's valuation for this product is given by $\\theta^\\top x_t + N_t$, where $N_t$ is some iid noise from a known distribution. The problem is how to set a price $v_t$ such that the product will be sold if and only if $v_t \\leq \\theta^\\top x_t + N_t$. \n\nThere are two different variations of this problem depending on whether the feature vectors are drawn iid or are generated adversarially. For the adversarial features problem, Cohen, Lobel and Paes Leme (EC 2016 and MS 2020) proved a $O(poly(\\log T))$ regret bound assuming the noise $N_t$ is small (of order $O(1/(T\\log T))$. For the noise-free case, Paes Leme and Schneider (FOCS 2018) proved a $O(\\log \\log T)$ regret bound. For the iid case, Javanmard and Nazerzadeh (JMLR 2019) proved a $O(\\log T)$ bound assuming the covariance matrix of the feature vectors has a smallest eigenvalue bounded away from zero. Note that, following the template of the discussion in the paper being evaluated, I am ignoring the dependance on the feature dimension $d$ in this paragraph.\n\nThis paper's main contribution is an algorithm called Online Newton Step Pricing (ONSP) that obtains $O(d\\log T)$ regret for the adversarial version of this problem, without the small noise assumption (noise is assumed to be $O(1)$). The idea is pretty simple (though the proof isn't): use the log-likelihood as a loss function and then use online Newton's method to optimize it. \n\nThe paper also presents a separate algorithm for the iid case, called the Epoch-based Max-Likelihood Pricing (EMLP) algorithm. This algorithm is the exact same as the one proposed by Javanmard and Nazerzadeh, except it replaces a Lasso regression with a standard one. They prove the same $O(d\\log T)$ regret as Javanmard and Nazerzadeh for the iid case using this algorithm, without invoking any sort of smallest-eigenvalue assumption. The paper further proves that if the noise distribution is unknown, no bound stronger than $O(\\sqrt T)$ is attainable.\n\nThis paper is impressive, and I support its publication at NeurIPS. I would say the paper is original, high-quality, clear and significant. Here is some feedback and questions:\n\n1. What is the point of EMLP? ONSP can obviously also be used with iid features. Does EMLP offer any advantages?\n\n2. The paper clearly dominates the earlier results of Javanmard and Nazerzadeh. They obtain the same regret bound without the eigenvalue assumption. They even do so with the same algorithm (EMLP). The main exception to the point is that the current paper does not have sparsity-related results, as it dropped the Lasso regression.\n\n3. The paper also solves an open question in this literature: is it possible to obtain $O(d\\log T)$ regret with $O(1)$ noise? They paper settles this issues affirmatively. In my opinion, this is an important result.\n\nTypo: \"vice versa\" not \"vise versa\" on page 3.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As for limitations, the paper  makes an intriguing point in Section 7: the regret bound of ONSP and EMLP becomes worse as the noise becomes smaller. Noise is helpful because it makes the regret smoother and induces exploration. Therefore, their analysis does not apply if the noise is $O(T^{-\\alpha})$ for $\\alpha > 0$. Interestingly, we now have logarithmic regret bounds for $\\alpha = 0$ from this paper and $\\alpha = 1$ from Cohen, Lobel and Paes Leme, but we do not have logarithmic regret bounds for $\\alpha \\in (0,1)$.\n\nAs for potential negative societal impacts, the same algorithms that are proposed here for pricing a large collection of products could alternatively be used for personalized pricing, which could potentially be problematic depending on the situation. This point is properly disclosed in the appendix.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "TLazO4Qhza6", "reviewer": "Reviewer_XCzw", "summary": "This paper considers the feature-based dynamic pricing setting. This setting is a sequential setting in which in each round a learner is to predict the price of a product based on a feature vector. Then, if the customer's private value exceeds the price predicted by the learner, the customer buys the product. The goal is to control the difference between the difference between the cumulative price of the sold products and the best offline pricing policy. \n\nOn of the main challenge in this setting lies in the feedback that the learner receives. Since the learner only sees whether or not a product is sold, he receives limited feedback about the customers private value for a product. To remediate this issue, the authors assume that the private value of the customer is the inner product between a unknown parameter vector and the feature vector plus some noise. Another important assumption is that the distribution of the the noise is known exactly and that both the cumulative distribution $F$ and $1-F$ are strictly log-concave. \n\nWith this set of assumptions (plus some additional standard assumptions) the authors provide two new algorithms, one for stochastic feature vectors and one for adversarial feature vectors. Both algorithms rely on the fact that as soon as both $F$ and $1-F$ are strictly log-concave and $F$ is known, one can derive a surrogate loss which is almost quadratic. Because of the nice properties of this surrogate loss functions to show that the regret is $O(d \\ln(T))$. \n\nThe paper also contains a lower bound, roughly stating that as soon as the distribution of the noise is not exactly known, the regret has a $O(\\sqrt{T})$ lower bound. \n\nFinally, the paper contains some experiments which compare the performance of the two new algorithms to EXP-4. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of using the log-concavity of the noise is nice and turns out to be quite effective in deriving small regret bounds. \n\nOne of the arguments for using the new methods over previous methods is that existing results have regret bounds that scale are $O(\\min\\{\\frac{1}{\\lambda^2_{min}}\\ln(T), \\sqrt{T}\\})$, where $\\lambda_{min}$ is the smallest eigenvalue of the second moment matrix of the feature vectors, which can be arbitrarily small depending on the distribution of the feature vectors. Since there are also constants that depend on a distribution in the new bounds it would be nice to have some idea of how big this constants are. While in appendix C there are some lower bounds for the constants I would like to seem an upper bound as well to get an idea of how the new regret bounds compare with the literature. Also, note that for the Newton algorithm to work one needs to know the exp-concavity parameter of the surrogate losses, which seem to be tied to the same constants. So for the algorithm to have any practical relevance it would be a good idea to provide the constants for some common distributions. \n\nOn a similar note, I think the statement in line 142-143 that the CDF might not be known is practice is acceptable is wrong. As demonstrated by the lower bound, even very small differences in between the assumed CDF and actual CDF may lead to $\\sqrt{T}$ regret. Since it is not clear how either new algorithm reacts to misspecification of the noise, I do not think that we can claim that not knowing the CDF is acceptable in practice. \n\nI also have a slightly more technical question. I have not seen the requirement that $1-F$ is log-concave before and I wonder if there is a relationship between $F$ being log-concave and $1-F$ being log-concave. If not, is there a straightforward manner in which I can verify that for example a gaussian distribution satisfies the requirement that $1-F$ is log-concave?\n\nOverall, the paper contains some interesting results. Although I doubt the practical relevance of the results I do appreciate the technique to use the log-concavity property to derive surrogate losses. I also appreciate the lower bound an it's implications. \n\nThe writing could be improved as there are some unclarities. For example, upon my first reading I read assumption 2 as if the true parameter was known to us. In the sentence starting on line 74 it is unclear to me what \"when we explain the results\" means. There are also bothersome inconsistencies in the use of big $O$ notation. For example, in line 44 $d$ is included in the big $O$ notation but in line 49 it is not. In line 16 it is not clear to me what an acceptable price is and to me it seems that finding the price that is the most profitable is the goal. The $C$ used in Lemma 8 does not appear to be defined in equation 11. \n\nMinor comments\n- I do not understand the \"|\" symbols in lines 295 and 294.\n- line 226: $C$ and $C_{down}$ is defined --> $C$ and $C_{down}$ are defined.\n- perhaps the greater than zero is unnecessary in equation (12) due to the definition of semi-positive definite matrices. \n- as a personal preference I try to avoid the use of obviously and clearly as whenever I do not understand statements which include either of these words immediately I always feel a little bit stupid. I do not think it would harm the paper if these words are removed so I suggest you remove them.\n- line 131: till is perhaps too informal --> until  \n- line 570: following --> follows\n- line 561: curve --> curves\n- line 536: In specific --> to be specific.\n- line 536: a \".\" before Define is missing.\n- line 537: there is a \".\" missing at the end of the sentence. \n\n\n----------------------------------\nIn the rebuttal the authors have adequately addressed my concerns and I have raised my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Ngrrx7XqWUH", "reviewer": "Reviewer_VSt3", "summary": "(Disclaimer: I have previously reviewed this paper for ICML 2021).\n\nThis paper develops algorithms for the problem of contextual dynamic pricing. This is an online learning problem that takes place over T rounds. There is a customer with a hidden value vector theta in R^d. Every round, the learner is given as context a feature vector x in R^d (both x and v are suitably bounded), representing the features of the current item. The customer is willing to pay up to v = <x, theta> + a Gaussian noise term for the item. The learner must set a price p for the item this round; if p > v the customer does not buy the item (and the learner receives 0 utility), otherwise the customer buys the item at price p and the learner receives p utility. The goal of the learner is to maximize their total learner (minimizing their regret compared to the optimal dynamic policy).\n\nThis paper presents two algorithms for two different settings. Their first algorithm (EMLP) applies when the feature vectors x_t are iid drawn from an unknown distribution. Their second algorithm (ONSP) applies when the feature vectors x_t are chosen adversarially. In both cases, they obtain O(d*log T) regret. Both algorithms require that the noise is Gaussian with a known variance sigma^2 (The authors show an O(sqrt(T)) lower bound if sigma is unknown). (In fact, this known variance sigma influences the constant in the O(d*log T) regret; see comments below). \n\nRoughly, both algorithms work by maintaining an estimate of theta, and submitting the expected-utility-maximizing price p (assuming the theta estimate is accurate) per round. The two algorithms differ in how they maintain their estimate of theta. EMLP divides the rounds into log T geometrically-sized epochs, and uses a MLE to recompute the value of theta at the end of each epoch. ONSP instead runs an online Newton step method each round to obtain an estimate of theta.\n\nThe authors additionally present some empirical simulations of their algorithms (on synthetic data), showing that they outperform EXP4.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am generally positive about this paper: I think contextual pricing is a pretty interesting and important question, and I think this paper makes concrete and novel progress in developing algorithms in a noisy setting.\n\nOne concern from the previous submission of this paper was that it was missing important citations in the literature (namely a line of a recent work on contextual pricing and contextual search). The paper now contains a good discussion of how this paper significantly differs from the models considered in these papers (and as far as I can tell, I agree).\n\nOne other concern was that the regret of the authors’ algorithms depended in a significant (and non-intuitive way) on sigma -- in particular, as sigma gets small (less noise), the regret of their algorithms blow up. This was not made very clear in the earlier submission, but in the current draft there is now some discussion of this in section 7. This phenomenon still somewhat bothers me; it feels in some sense that the algorithms the authors present are mostly taking advantage of how the noise smooths out the reward function rather than dealing with the core difficulties of dynamic pricing, but I admit that this is still an interesting regime. \n\nThe paper was well-written and easy to read. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "GF-XUSuN1G", "reviewer": "Reviewer_KZQd", "summary": "This paper studies the recently active problem of regret minimization in feature-based pricing.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In feature-based pricing, we have a buyer with a high-dimensional value theta that is held privately. Features x_t from the same dimension arrive online, and the value w_t for round t is <theta,x_t> + zero-mean-strictly-log-concave-noise. The noise is drawn i.i.d. from a known bounded strictly log-concave distribution (e.g., Gaussian noise). The buyer is posted a price p_t at round t, and buys when his value is at least the price, and rejects otherwise. The algorithm designer who posts the price gets to see only the features (before posting the price) and the binary decision of sale or no sale (after posting the price). The goal of the seller is to post a stream of prices that minimizes the revenue regret --- compare the obtained revenue with the optimal revenue obtainable had the seller known the hidden vector theta.\n\nThe paper studies two settings, one where the features are stochastic (drawn i.i.d. from an unknown distribution) and the other where the features are drawn adversarially. In both the settings, the paper gives algorithms that achieve O(d log T) regret.\n\nI generally like this line of work as it provides a neat playground to develop good theory and techniques. Achieving a regret bound of O(d log T) in this model is a nice/clean result. Knowing the noise is a reasonable assumption and there is anyway regret lower bound of \\sqrt{T} when not knowing the noise distribution.\n\nMy primary question is regarding the regret bound: what is the dependence on the level of noise in the regret bound of O(d log T)? To take a simple case, with Gaussian noise, when sigma approaches zero, can this paper get a O(d log T) bound? If not, is there a reason to expect that achieving O(d log T) regret is impossible when sigma is zero? A priori, it seems like getting O(d log T) is not impossible. The current writing conceals the dependence on the noise (or specifically sigma for the Gaussian case), and it is hard to figure out from the paper what the dependence on sigma is. Typically one would think that the less noise case is the easier one, and more the noise harder it is. But given the highly discontinuous nature of pricing loss, noise can help \"smooth out\". \n\nRegardless of the answer, there should be a clear discussion on the dependence on noise in the regret achieved. \n\nAnother subtlety to point out is the somewhat unusual notion of regret: usually we talk about E[max], but here we have max E. In other words, rather than compare with the expectation of the ex post optimal policy that posts a price of w_t, the comparison is w.r.t. the price offering the maximum expected reward. While understandably, comparison w.r.t. the former will lead to a \\sqrt{T} regret due to the variance induced by the noise, this is an important enough aspect that deserves to be discussed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agree on the importance of the contribution. It is also my view that obtaining logarithmic regret is an important open problem in contextual pricing without any assumption of small noise. I am aware of many papers that tried to establish similar results but failed. 

The only concern shared by the reviewers is that the regret bound is inversely proportional to noise, but this was  adequately addressed this in the rebuttal by saying that larger noise leads to more exploration. The authors are encouraged to make this more explicit in the revision.

The review team is confident that this should be one of the top papers in NeurIPS and enthusiastically recommends acceptance.
Decision: Accept (Spotlight)