Improved Algorithms for Contextual Dynamic Pricing
Authors: Matilde Tullii
Solenne Gaucher
Nadav Merlis
Vianney Perchet
Venue: NeurIPS 2024 poster (2024)
Keywords: Dynamic Pricing
Bandits
Primary area: bandits
TL;DR: We present a novel approach to dynamic pricing problems with covariates and prove improved regret bounds for both linear and non-parametric valuations.

Abstract: In contextual dynamic pricing,  a seller sequentially prices goods based on contextual information. Buyers will purchase products only if the prices are below their valuations.
The goal of the seller is to design a pricing strategy that collects as much revenue as possible. We focus on two different valuation models. The first assumes that valuations linearly depend on the context and are further distorted by noise. Under minor regularity assumptions, our algorithm achieves an optimal regret bound of $\tilde{\mathcal{O}}(T^{2/3})$, improving the existing results. The second model removes the linearity assumption, requiring only that the expected buyer valuation is $\beta$-H\"older in the context. For this model, our algorithm obtains a regret $\tilde{\mathcal{O}}(T^{d+2\beta/d+3\beta})$, where $d$ is the dimension of the context space.

Improved Algorithms for Contextual Dynamic Pricing
Matilde Tullii"
Solenne Gaucher' FairPlay Team, CREST, ENSAE
FairPlay Team, CREST, ENSAE
Nadav Merlis FairPlay Team, CREST, ENSAE
Vianney Perchet FairPlay Team, CREST, ENSAE Criteo Al Lab
Abstract
In contextual dynamic pricing, a seller sequentially prices goods based on contex- tual information. Buyers will purchase products only if the prices below their valuations. The goal the seller is to design a pricing strategy that collects as much revenue as possible. We focus two different valuation models. The first assumes that valuations linearly depend on the context and are further distorted by noise. Under minor regularity assumptions, bound of ( improving the existing results. The second model removes the linearity assumption, requiring only that the expected buyer valuation is B-Hölder in the context. For this model, our algorithm obtains a regret (7T4+23/d43)) where is the dimension of the context space.
algorithm achieves optimal regret
Introduction
Setting price and devising a strategy to dynamically adjust it poses a fundamental challenge in revenue management. This problem, known dynamic pricing online posted price auction, finds applications across various industries and has received significant attention from economists, operations researchers, statisticians, and machine learning communities. In this problem, seller sequentially offers goods to arriving buyers by presenting a one-time offer at a specified price. the offered price falls below the buyer's 's (unknown) valuation of the item, a transaction occurs, and the seller obtains the posted price as revenue, Conversely, the price exceeds the buyer's valuation, the transaction fails, resulting in zero gain for the seller. Crucially, the seller solely receives binary feedhack indicating whether the trade happened. Her objective is to learn from this limited feedback how to set prices that maximize her cumulative gains while ensuring that transactions take place. In this paper, we study the problem of designing an adaptive pricing strategy, when the seller can rely on contextual information, describing the product itself, the marketing environment, the buyer.
While this problem has been extensively studied, previous results either rely on strong assumptions on the structure of the problem, greatly limiting the applicability of such approaches, achieve sub-optimal regret bounds. In this work, we aim to improve both aspects aspects-achieving better regret bounds while making minimal assumptions about the problem. Specifically, we study two different models for the valuation of buyers as a function of the context: /) linear valuations, where the item valuation of buyers is unknown noisy linear function of the context; and 2) non-parametric valuations, where the valuation is given by an unknown Hölder-continuour function of the contextual information, perturbed by noise.
Equual contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Summary of existing regret bounds. g is the expected valuation function, F is the c.d.f. of the noise, and x (I. p) is the reward for price p and context 2, defined in Section 2.1
Model
Noise Assumption
Regret
F is known
O
F' is known or parametric, and log-concave
O
Linear
F has m-th order derivatives
O (T 4/4
F" is bounded
O OT V |0
0
01 [22]
O(T%)
14 21, (T*)) [this work)
F is Lipschitz
((T%/)
Bounded noise
(T7))
31
π π( -) is quadratic around its maximum for all æ, FF and 9 Lipschitz
0 OT
Non- parametric
is Lipschitz and g is Hölder
0 OT7'7174459
[this work]
1.1 Related Work
Dynamic pricing has been extensively studied for half century [9 26 on both theoretical and empirical fronts. For comprehensive surveys on the topic, we refer the
leading to rich research
readers to 6 12 While earlier works assumed that the buyer's valuations are i.i.d. 18 recent research has increasingly focused on reature-based (or contextual) pricing problems. In this scenario, product value and pricing strategy depend on covariates. Pioneering works considered valuations depending deterministically the covariates. Linear valuations have been the most studied
5
16 9
20). yet a few authors have also explored non-parametric valuations (24
Recent works have extended these methods to random valuations, mainly assuming that valuations are given by function of the covariate, distorted by an additive i.i.d. noise. As this poses more challenges, authors have mostly focused on the simplest case of linear valuation functions, under additional assumptions. Initial studies assumed knowledge of the noise distribution IT 15| 30)
This assumption was later relaxed, albeit with additional regularity requirements on the cumulative distribution function (c.d.f.) of the noise and/or the reward function 14 22,, and then again by [1]. that achieves regret bound of (TT))1) for linear valuations, while assuming only the boundedness of the noise. Closest to our work [14 21 also focus on the case in which the only regularity required the Lipschitzness of the CDF Their approaches show some similarities with our work but still achieve suboptimal regret rates. A more detailed comparison between ours an their algorithms is presented later on in the paper. Other parametric models have been explored, with, for example, generalized linear regression models (28), though they also require strong assumptions, including quadratic behavior of the reward function around each optimal price. Few works have considered non-deterministic valuations with non-parmettric valuation functions. Among those, [TO] consider Lipsehitz-continunn valuation functions of d-dimensional covariates. They achieve a regret of order "(*"), assuming again quadratic behaviour around optimal prices. We refer to Table for a comprehensive comparison between different previous works, their assumptions and regret bounds.
To improve on previous results, we design algorithms that share information on the noise distribution across different contexts. This idea relates to methods used in cross-learning, research direction stemming from online bandit problems with graph feedback 223 2. this framework, introduced by 4 and further studied in [27], when choosing take action i in context zz, the agent observes the reward ri (xx)) along with rewards ri (1r)) associated with other contexts we, Our algorithms leverage similar principles to learn information usable across different contexts. However, compared to the typical problems addressed by cross-learning methods (c.g., first-price auctions, siceping bandits, multi-armed bandits with exogenous costs), the contextual dynamic problem is more complex due to the intricate dependence of the reward on the unknown valuation function.
1.2 Outline and Contributions
In this work, we tackle the problem of dynamic pricing with contextual information. We consider two models for the expected valuations of the buyer, assuming respectively that they are given by

---

linear function, or by non--onnnaann -on-maaaettiic function. For both models, we present general algorithmic scheme called VALUATION APPROXIMATION PRICE ELIMINATION (VAPE), and provide bounds on its regret in both models:
In the linear model, obtain regret of OTT%)), assuming only that the c.d.f. of the noise is Lipschitz. This concludes an extensive series of papers on the topic, as it establishes the minimax optimal regret rate and proves is attainable under minimal assumptions.
In the non -onppaaacttric model, we obtain a regret rate of ((T**=3//+55)) assuming only the Lipschitz-coninuity of the noise and the Hölder one of the valuation function. This result is the first of its kind under such minimal assumptions.
The rest of the paper is organized follows. We begin by presenting the model and summarizing the notations used throughout the paper in Section 2.1 Section 2.2 outlines our assumptions and compares them with those in previous works. Section 2.3 we discuss the main sources of difficulty of the problem and highlight the importance of information sharing in contextual dynamic pricing. In Section we present our algorithmic scheme, VAPE, and provide an initial informal result bounding its regret. Then, in Section we apply this algorithmic scheme to linear valuations and provide bound on its regret. Finally, in Section 5 we extend this algorithm to non non-parametric valuations.
Preliminaries
2.1 Model and Notations
The problem of dynamic pricing with contextual information is formalized as follows. At each step t t T, context Φ, E IR describing a sale session (product, customer, and context) is revealed. The customer assigns hidden valuation to the product, and the seller proposes price pt, based on æt and on historical sales records. If Pt I Yes the trade is successful, and the seller receives a reward ye otherwise the trade fails. The seller's only feedback is the binary outcome = 1 (p: S ye We assume that the seller's valuation is given by
y1 g(x)) + &c.
where Rd + R is the valuation function, and &, is centered, bounded, i.i.d. noise term, independent of x, and of (Ie, Ps. Ee) the present paper, we consider successively linear and non non-poram non-parametric valuation functions in Sections 4 and The seller's objective is to maximize the sum of her cumulative earnings. We denote by (p, 2²,) the expected reward of the seller if she posts price for product described by covariate Zz:
T(z,,)) p) = (p S y v.).
Adopting the terminology of the literature on multi-armed bandits, we measure the performance of our algorithm and the difficulty of the problem through the regret Rr, defined
RT Σ max गt (Z,, p)
Σ x (Ze, pt).
PER
Notations Throughout this paper, we make use of the following notation. We denote by ||-]] the Euclidean norm. For all A, B I. denote by [A, B]] the (A, (A,A+1,.. 1,..., B}. Ry Br (resp. Rr- Ö(Br) means that there exists a (possibly problem-dependent) constant C such that Ri < CBr (resp. Rr = (log((T) Br)). Finally, f and F denote the p.d.f. and c.d.f. of the noise, respectively.
Assumptions
For both valuation models, we make the following assumptions on the context and noise distribution. Assumption 1. Contexts and expected valuations are bounded: ||æe||| S Bg and gg(x;) I B, a.s.
This assumption is classical contextual dynamic pricing problems. We underline that contexts do not need to be random. In particular, they can be chosen by an adaptive ad adversary, aware of the

---

seller's strategy, and based on past realizations of (Zs, Eo) Assumption I is milder than the i..d. context assumption appearing in [14 28
Dynamic pricing strategies mostly assume that the buyer's valuations are bounded. To enforce this, assume that the noise is bounded; moreover, assume that its c.d.f. Lipschitz continuous.
Assumption 2. The noise & is bounded: [El V Bg a.s. Moreover, its c.d.f. F is Le-Lispchitz
continuous: for all (6, (6) E RR, F(6) - F(8') S Lg 18 81
2 is weaker than most of the assumptions in related works. For example, 15 require both F and
Assumption
be log-concave. [4] assume that F has m-th derivative, and that 1-1- (8)
is greater than some positive constant for all 8, achieving a regret of order O(T2mt)/mm-)) In the case m = 1, they propose a different algorithm, reaching a regret O(T%))) 12 consider Lipschitz- continuous noise, under the additional assumption that, for every 2., p" (2) arg max, ग (x) is unique, and that F" is bounded.
(10) assume quadratic behaviour around every maxima: for every x, p" px(x) E arg max, т (2., p). p" (z) is unique, and for all p. C'p" (x) pp)² I x p=(()) - <x S C"(p" (x) p)² for some constants C, C². The only work considering non-Lipschitz c.d.f. is [3];: however, they achieve higher regret bound of O(T%)).
2.3 Information Sharing in Contextual Dynamic Pricing
For ó E I. we denote D66) P (E: 2 8) = F()). the demand function associated with the noise &. Note that, under Assumption that, for any price increment 5 E R, the expected reward corresponding to the price p g(xx)) 5 in the context Ft is given by
2 D is Lę- -Lpiiscciitz continuous. Straightforward computations show
(2) Equation 2 highlights the intricate roles played by the expected valuation g(x,)) and the price increment p ((xz) in the reward. An immediate consequence is that the optimal price increment ô depends on the value of g(xz). Intuitively, if g(x) is large, the seller should choose to be small to ensure high probability D(6) to perform a trade. However, for smaller values of g(a2), the seller might prefer a larger to ensure significant rewards when a trade occurs. Importantly, there is no explicit relationship between the optimal increments 5 for different valuations g(zx), so knowing the optimal price for a value g(x²) does not allow optimal pricing for a different value g(rr).
tI ((z,g((z)) + d) = (g(xz) + D)))
This reasoning suggests that the optimal price increment may span wide range of values as the necessary
expected valuation g(x;)) varies. Unfortunately, as is typical in bandit problems, to estimate the reward function around the optimal price with high precision to ensure low regret. Consequently, solving the dynamic pricing problem may entail estimating the demand function precisely across broad range of price increments. This marks a significant departure from non- contextual dynamic pricing and non non-parametric bandit problems, where precise estimation of the reward function is often only necessary around its (single) maximum. Thus, the contextual dynamic pricing problem might be more challenging than its non-contextual counterpart, potentially leading to higher regret. This intuition is supported by the fact that straightforward application of basic bandit algorithms, even in the most simple linear model, leads to regret higher than the rate of order (TT%)) encountered in non-contextual dynamic pricing problems, as we show in the following discussion.
Naïve bandit algorithms for contextual dynamic pricing. As first attempt, one might apply simple explore-then-eee -hneetttte-cmmtt algorithm. Such algorithms start with an exploration phase to obtain uniformly good estimates of both and of the demand function D over a finite grid of price increments (ōx hee.. Then, in a second exploitation phase, prices are set greedily to maximize the estimated reward. To bound the regret of this approach, note that uniform estimation of D over the grid {ōr hee with precision e requires e 2|K] estimation rounds. Moreover, the Lipschitz continuity of the reward function implies discretization error of order kg. Classical arguments suggest that the regret would be at least T(c + 1/IK1) |AC|e- which is minimized for 1/KK| T 111/ Thus, this approach would lead to a regret of order ((T%))).
Another approach, akin to that used in 10, involves partitioning the covariate space into bins and running independent algorithms for non- non--onnna parametric bandits (such as CABI (17) within each bin. Let us assume, for simplicity, contexts in [0, 1]. and that we partition this segment into K bins. Then,
the discretization error is I/K. Classical results show that the regret in one bin is Ö(T ), where

---

Tk = T/K is the number of rounds in each bin. Consequently, the regret is Ö(T/K + K x (T/K)))), which is minimized for K = T'/4, resulting in regret O(T%))).
Thus, both approaches using either independent bandit algorithms over binned contexts or common exploration rounds followed by am exploitation phase suffer regret of order T in the linear model. This raises the question of whether this rate is optimal for the linear model, and if the contextual dynamic pricing problem is indeed more difficult than the non-contextual one. Strikingly, we show that this is not the case. We rely on an intermediate approach, based on regret-minimizing algorithms for each valuation level g(35e) that share information across different values of g(xz). We show that it achieves an optimal regret rate of order ((7%)) in the linear valuation model. Moreover, it achieves a rate of order O(TT(119/a 88) in the non-parametric valuation model under minimal assumptions.
3 Algorithmic Approach
In this section, present the general algorithmic approach that we use tackle dynamic pricing with covariates, called VALUATION APPROXIMATION PRICE ELIMINATION (VAPE). Before presenting the full scheme, described in Algorithm[[ we start with some intuition that leads to its design. Then, we provide a first analysis of the regret of this algorithm.
3.1 Outline of the Algorithm
highlights how the reward is influenced by the expected valuation gxzz) and by the demand at the price increment 8 = Pt g(z)). To separate the effect of these terms, we estimate and D independently. Hereafter, we assume that the valuations y/2 are bounded, in [-By. By).
Equation
(2)
Estimation of g. To estimate g(x,)) we rely on the following observation: when prices p, are uniformly chosen from the interval [-By: By]. the random variable 2B, (or 1/22) can serve as an unbiased estimate of g(xx) conditioned on Tt. Given that 2B, (or - 1/22 is bounded, classical concentration results can be employed to bound the error of our estimates for g(xx). Thus, in each round, we test whether our estimate of g(zz) is precise enough to ensure that the error g(xx) ((x) small. If this is not the case, we conduct a VALUATION APPROXIMATION round by setting a uniform price. In the next sections, we consider linear and pon-paracctric valuation functions, and we discuss how to ensure sufficient precision
limited number of valuation approximation rounds.
Previous approaches for estimating valuation functions in the linear model include the regularized Kikiimum--ikellhooe estimator [13 30, which requires knowledge of the noise distribution. Another approach used in [22] relies on the relation between estimating a linear valuation function from binary feedback and the classical linear classification problem. The authors propose recovering the linear parameters 0 through logistic regression; however, they do not provide an explicit estimation rate for 0. (20) use the EXP-4 algorithm to aggregate policies corresponding different values of and F. thus circumventing the necessity to estimate them. In similar vein, in the -orraammet valuation model, [10) avoid the need estimate g(æx) by employing independent bandit algorithms for each (binned) value of zt. Closer to our method are the works of [14 and (2I) who also set uniform prices to obtain unbiased estimates of the valuations. Nonetheless, their algorithms are significantly different from ours. First, they propose two-phased algorithms for which the phase length is set beforehand. Such an approach necessitates additional assumptions on how contexts are drawn; specifically, contexts are assumed to be i.i.d. from a distribution with a lower bound on the eigenvalues of the covariance matrix. This is needed to ensure that contexts observed in the first phase can represent the context distribution well. By contrast, our phases are adaptive, allowing our algorithm also to handle adversarial contexts and render these assumptions superfluous. Second, obtain better regret rates by using piccewise-constant estimators, fitted in a regret- miiimi-mmnii sub-routine, as detailed in the next paragraph. On the other hand, [14] performs a phase of pure exploitation, relying
estimate of the CDF F' that is constructed using Kernel methods. (2I]. instead, re-frames the problem as a perturbed linear bandit, which exhibits a regret linear in the dimension. However, this dimension depends on the size of the discretization grid which is horizon dependent leading to worse rates.
Estimation of D. If the expected valuation g(zz) is known with sufficient precision, we can use it to estimate the demand function over a set of candidate price increments {6x ReK. More precisely, assume we set price Pt Õ(æ,) + òg. and that (x(x)) g(xx)) S e. Then, the observation o, can
5

---

Algorithm VALUATION APPROXIMATION PRICE ELIMINATION (VAPE): General scheme
Price increments (ōk) expected valuation precision err, (x), reward confidence intervals (k), (K), parameters
Input:
2:
while S do
3:
if (rre((a)) then
Valuation Approximation
4:
Post price Pt ~ U[[BBy, Byl) Use or to improve the valuation estimator 3(x+)
5:
6:
else
> Price Elimination
7:
A tKEK: D. 6N 0, B,l
8:
K + E :E:AAUCTE (k) 2 maxvea, LCB,(k)}
9:
Choose Kt E arg gin,ex, N² and post a price ps = gt + S%.
Update Dii1 Not
be used as an almost unbiased estimate of the demand at level og. since
[ioo] (1]x))) 5 S g(x+) + t = D(o + [(xs) g(x))).
Under Assumption D is Le-Lipschitz, the bias is of order Lge. Then, relying classical bandit techniques, we show that with high probability (for a small enough), [D()s) - D of order Tgge /log(L/o)/NT, where D. is the average of the observations when setting a price = ((x,) + 5g, and N² is the number of rounds in which we chose the price increment 6 up round i. Importantly, to estimate DJ we share information collected during all rounds chose the increment 6% across all values of T(xx); this is necessary to obtain better regret rates. Then, using pt Dj as estimate of the reward n ( Pt) given the price pt g(x+) du the error (T(, - D. is of order By /lo(()/a//Nt)
The PRICE ELIMINATION subroutine relies on the previous remark to select price increment. For each increment oR. we build a confidence bound (6&) (6+) = (p. + By (2LgE /2logt1/a)/N, ] for the reward of price Pt f(x,) + 6g. Then, we
successive elimination algorithm 13 25 to select a good increment. More precisely, we consider increments 6G such that (O,) > max; (&r), and we choose among these increments the increment 82, that has been selected the least frequently. By doing so, we ensure to only select potentially optimal prices and gradually climinate sub-optimal increments.
3.2 A First Bound on the Regret
Before discussing the application of the algorithmic scheme VAPE to linear and non-parametric valuation functions, provide some intuition regret bounds achievable through this scheme.
Claim (Informal) Let 8 ke for k K. & Il-B,-l/eJ, [B,+//]] Assume that, on a high- probability event, (r(x,) g(xx)l S for every round where PRICE ELIMINATION is conducted. Then, on a probbbbbbbbiitty event, the regret of VAPE verifies
RT S TV) Te log(1/a)e
where (E) is a bound on the length of the VALUATION APPROXIMATION phase.
Claim is proved in the Appendix by combining Equations and and Lemmal4 4 We provide sketch of proof below. To bound on regret of VAPE using Claim I it will suffice to bound the length of the VALUATION APPROXIMATION phase, and prove probbbbbbayility error bounds on g(xz).
Sketch of proof. Note that the regret in the VALUATION APPROXIMATION phase scales at most linearly with its length. Then, to prove Claim I it enough to bound the regret during the PRICE ELIMINATION phase. We begin by bounding the sub-optimality gap of the price chosen round t, showing that it is of order e /og(1/a)//NT..
To so, for p E TR, we define A,( maxp' π (xr,p') T(2,, p) the sub-optimality gap corresponding price Recall that ò,, is the increment chosen round t, i.c that Pt Ō(x,) + dz,

---

Classical arguments from the bandit literature show that with high probability, for all & E K, the upper and lower confidence bounds on ((zzg((z) + 6x.) given by (CB,(6k) and LCB, are valid. Then, the optimal increment òx; defined by k- arg maX x (I,, (xx) + 6x) belongs to the set of non-eliminated increments. Now, on the one hand, since (OB), 2 L ((x;), and since the confidence interval are valid, the gap T(Z,, + 5x;) - (Zt. pt) is of order
++ /llog(//a)// + /2log(1/a)/xx/
Our round-robin sampling scheme ensures that N 2 N
so this bound is of order + /oo(1//l/// On the other hand, our choice of grid {6 together with the Lipschitz-continuity of the reward in Assumption 2 imply that the cost A, (xr, I(xe + 61;) of considering a discrete price grid is of order Ly Thus, at each round, the gap A (Ze, ((x,) +
is most of order + /lug (up to problem-dependedd constants).
Now, let decompose the regret of the PRICE ELIMINATION phase follows:
Σ
A(xr,Pe) Σ A(re.().
PEPRICE ELIMINATION phase
REK. E:A,
In order bound Eddee (xr,, Pt) for k E K. we begin by introducing further notations. Let us denote Tf. ....... T the rounds in the PRICE ELIMINATION phase where we choose k, = k. We also define A. 2- and such that Ag R e. For all S T we also define t, such that the bound e /log1//al/t is of order Aa. Then, our previous reasoning implies that if 2 la for some E {I, must be that (1 prt) S A.. Moreover, for a 2 I, each phase {la..... k4+1 } is of
length approximately
-2
3) Thus,
log(1/a)
log log(1/a)
log(1/a)
Σ (t), t
Σ A. x a=1
+ A.
A
A2 a+1
A
Using the definitions of A. and a. find that this sum is of order log(1/a))e eNH. We conclude by summing over the values of K, using EkEK No < T and the fact that [K] is of order e m
4 Linear Valuation Functions
In this section, we consider the linear valuation model, given by
g(z) = TT,
(3)
where 0 E Rd is an unknown parameter. To ensure that the valuations are bounded, we assume the boundedness of the parameter f.
Assumption 3. The parameter 0 is bounded: |10| < Bo
Note that under Assumptions I and 3 the expected valuations g(xx) verify [g(xz)) I B, for By = BB x Bg. Moreover, the random valuations verify a.s. |yel S By for By = By + Bç.
We apply the VAPE algorithmic scheme to the problem of dynamic pricing with linear valuations. To estimate the valuation function, we use a ridge estimator for the parameter 9. Moreover, we distinguish between phases by setting 4, 1 if / belongs to the VALUATION APPROXIMATION phase and 4 = 0 if belongs to the PRICE ELIMINATION one. The details are presented in Algorithm 2
Theorem 1. Assume that the valuations follow the model given by Equations ① and ( Under 12 and3 the regret of Algorithm VAPE for Linear Valuations with parameters
Assumptions 7
( log (T) p /==
Bry /By/alloe dlog
11.22T
Bo
and
(3 (3+(B4+1))taa) verifies
RT S CB. Bo. Le %/ (T)
with probability 1 T-1, where BB, Bu is a constant that polynomially depends on Bg, Ba, Be, and Lg.
Sketch of proof. [See Appendix B for the full proof] Using Claim I we see that it is enough to prove that the VALUATION APPROXIMATION phase allows to estimate g(rz) up precision (d log(Tr)3/1) in most 4/ 1og(T))/3) rounds.
7

---

Algorithm 2 VALUATION APPROXIMATION PRICE ELIMINATION (VAPE) for Linear Valuations
1: Input: bounds By and Lg. parameters M4,
K,K K]. 2: Initialize: 01 = Od V1 = Ia, K = -B II-K,,
and for k E K. No D1 =
3: while / < do
4: if [xellv; > μ then
B Valuation Approximation
5:
Post price Pt [1[ By: Byl)
6: 4 1. V++1 t Σ 1g + Id, 8111 -2 V E. (o, 2) 2 3St
7:
else
b Price Elimination
8:
0, gt t _ Oc. As + ( Dr + ke E [0, Byll
9:
for E A do
10:
UCB((K) +- (ği kt) (D) / /2log(
+ 2Tge)
N
11:
(k) (k) - G+ + ke) (n+- 2log(1/a)
2Ieet)
N
12:
KG (k A UCB, (k) 2 m (CB,(k))
13:
Choose k E arg ceK, No and post price pz Dt + kec
Update D NM t N No +1
To prove the first part of the claim, note that for all rounds in the PRICE ELIMINATION phase, Then,
| lyy μ o/ By (loddoo((+=2770)))
- -(xe)) - 10 0. lv. I S -.-0.llv. x (
Classical result on ridge regression in bandit framework ( show that on a large probability event, |10 0ellv. < / (1+ (1+ (TTa) + Bo)) [ī(x)) g(x)] S...
To prove the second part of the claim, we rely on the elliptical potential lemma to bound the number of rounds where ||sellly. 2 μ. This Lemma states that Σ
DEl || ||vا S V log (1o1+d/a),
[6]
where 4; is the i-th round of the VALUATION APPROXIMATION phase, and [ is its length. Using
the fact that || Iv= 2 μs we conclude that g < n²
d'lo(T+4//a) which implies the result.
Theorem 1 provides a regret bound of order O(T%)), showing that VAPE for Linear Valuations is minimax optimal, possibly up to sub-logarithmic terms and to sub-linear dependence in the dimension. Indeed, it matches the 7 lower bound established in [31] for linear valuation functions and Lipschitz-continuuut demand functions. This result represents clear improvement over the existing regret bounds for the same problem. Indeed, VAPE achieves the regret bound conjectured in (22 while at the same time removing their regularity assumption on the revenue function. On the other hand, we improve on the regret rate (TT%)) achieved respectively in [1 under assumptions slightly milder than ours, and in 14 under stronger assumptions.
5 Non-Parametric Valuation Functions
In this Section, we consider the non-parametric valuation model. As usual in dynamic pricing, we assume that the valuation function g bounded. Furthermore, assume that it is (Iag H)-Hölder continuous for some constants L, > 0 and 0 < 3 < 1.
Assumption 4. The valuation funuation,function g is (Lg- H)-Hölder: for all (I, E Rd, [g(x) g(2)) Ly || - z' 2'1"".
Under Assumptions andd] the random valuations y, verify |yx| < B, for B, Bg Bg. Next, we apply the VAPE algorithmic scheme to the non-parametric valuation model. To estimate the function g, finite grid of points, which this function is evaluated. More precisely,

---

Algorithm VALUATION APPROXIMATION PRICE ELIMINATION (VAPE) for Non-Parametric Valuations
1: Input: bounds By and Lg. finite set X C Rd parameters a, T.
2: Initialize: GT 0 for all x E X, K [ K. [-K, K, K], and for k E K. Nf = D4 = 0.
3: while < do .7 < arg min.'' ||, F
4: if |5,, < r then
D Price Elimination
5: Post price Pt ~ -yy Byl)
6:
gz, gz, U [t), O(x)) t
28, Σ (0--2)
7:
else
Run Successive Elimination
8:
9: - [ ) A₁ + (k K:: It + KE E [0, Byl
9:
for k E A, do
UCB, (k) -- (0t + kt) (D) +
/ /2log(/o)
+ 2l.rr)
No
11:
LCB, + (+r + ke) (D}- 20oR(//))
21(et)
No
K2 + (K A. (k) 2 maxx E.A. LCB,(K))
Choose E arg min No and post price pt Gt + ligE
Update D t
No D. +o, N < N + N1
14:
consider a minimal (s/sz,)) // (tt))///-cvvvme covering X of the ball of radius Bg Rd i.c. finite of points, of minimal cardinality, such that for any context æ such that ||~ S B2, there exists point in X' at distance at most (s/ar,) from
At each round, round the context 2, the closest context T in X by setting arg ming || - = ||. and acting as if we observed the context Ty. this context has not been conduct round of VALUATION APPROXIMATION: we sample price uniformly at random and use it to update our estimate of gTTe); otherwise, we proceed with the PRICE ELIMINATION phase. To distinguish between the VALUATION APPROXIMATION steps corresponding to contexts I E X, we collect their indices in sets Gz. The algorithm is presented in Algorithm
observed sufficiently,
Theorem 2. Assume that the valuations follow the model given by Equation ① Under Assumptions and 4 with probability T the regret of Algorithm VAPE for non non-parametric Valuations
i 2
with parameters covering of the ball of radius BN verifies
(T/log(T)) 2=38, -T -4, 188, log (1)/)))))22 and X a minimal (e/
Rr S CB, d. log (T) JF33
where CB., By Be, Be, J. J.,, A,B is a constant that polynomially depends on Br. Bg Be, Ly LE, d, and B.
Sketch of proof. [See Appendix for the full proof] Using Claim 1 only need to show that the length of the VALUATION APPROXIMATION phase is most of order T=433//048 log(TY"/<+ss 7/0+38 and that w.h.p., it allows estimating g uniformly on a ball of radius B2 with precision == (f/1og(T))-9/4--3)
To prove the first part of the claim, note that classical results imply that the size of minimal covering of precision ee of ball in dimension d scales as <///, Then, the total length of the VALUATION APPROXIMATION phase is of order - xe 71d226/6-a8 log(T) To prove the second part of the lemma, note that the Hölder-continuity of and the definition of the (s/3L,) covering G ensure that (g(x²) - g( I < 9/3. Then, standard concentration arguments reveal that 7 s log((X)/a))/ samples are sufficient to estimate g(x,) with precision e with high probability.
Theorem 2 shows that the Algorithm VALUATION APPROXIMATION - PRICE ELIMINATION for non-parametric valuations enjoys O(7=428/2430) regret bound when the noise c.d.f. is Lipschitz and the valuation function Hölder-continuous, This result the first of its kind under such minimal assumptions. In particular, previous work by [10] assumes quadratic behavior around the optimal price for all values of g(z)- very strong assumption. However, this rate is higher than the O(1=+8//110)

---

rates that are usually encountered in 3-Hölder non con-paametric bandits 77 Thus, the question of optimality of the VAPE algorithmic scheme in the non non-parametric valuation problem remains open.
6 Conclusions
In this paper, we studied the problem of dynamic pricing with covariates. We first presented a novel algorithmic approach called VAPE, which adaptively alternates between improving the valuation approximation and learning to set prices through successive elimination. We then applied VAPE under two valuation models when the buyer's valuation corresponds to noisy linear function and when expected valuations follow a smooth non con-paametrric model. In the linear case, our regret bounds are order-optimal, while in the non-parane con-parametric setting, improve existing results. All our results are proven under regularity assumptions that are either milder or match existing assumptions.
Our results on the linear valuation model are the first to match the existing lower bound rate of O(T%)) under our assumptions. However, the optimal dependence of this rate on the dimension of the context remains unknown. Additionally, there are no similar lower bounds for non non-parametric valuations. We conjecture that our results are also tight in this setting but leave this for future work. Future research directions also include exploring other valuation models. and further relaxing our assumptions, as Lipsshitz-continnigg of the noise (Assumption 2). Without this, even minor increases the price could lead to major drop in revenue, magnifying the impact of valuation approximation errors. Another limiting assumption is that the noise is independent and identically distributed, such that its distribution can be learned across different contexts. is great interest to study problems where the noise distribution can change between rounds, or depends the context.
Broader Impacts
As all pricing problems, dynamic pricing can have both positive and negative impacts - offering prices that more suited to the buyers the one hand, while increasing the seller's revenue the expense of buyers on the other hand. In addition, as with many contextual problems, there might be biases and challenges involving fairness one should make sure that similar customers are offered similar prices. While acknowledging these issues, our work was meant to focus only on the theoretical analysis of what is considered well-established problem in literature, leaving the study of these related topics as future work.
Acknowledgments
This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska- Cursie grant agreement No 101034255. Solenne Gaucher gratefully acknowledges funding from the Fondation Mathématique Jacques Hadamard. Vianney Perchet acknowledges support from the French National Research Agency (ANR) under grant number (ANR-19-CE23-002 as well as the support grant, as well as from the grant "Investissements d' Avenir" (LabEx Ecodec/ANR-1 1--LAB--0047). This research was supported in part by the French National Research Ageney (ANR) in the framework of the PEPR IA FOUNDRY project and through the grant DOOM ANR-23-CER 22---233--30000 It was also funded by the European Union (ERC, Ocean, 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference Learning Theory, pages 23-35. PMLR, 2015.
[3] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014.
10

---

[4] Santiago Balseiro, Negin Golrezaei. Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross cross-learning. Advances in Neural Information Processing Systems, 32, 2019.
[5] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations research, 57(6): 407--4220, 2009.
[6] Gabriel Bitran and René Caldentey. An overview of pricing models for revenue management. Manufacturing & Service Operations Management, 5()):203-229, 2003.
[7] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. <i>x</i> bandits. Journal of Machine Learning Research, 12(46))1655-1695, 2011. URL /ttp:///// org/ aiteass/v22buubeccie 11.. html
[8] Alexandra Carpentier, Claire Vernade, and Yasin Yadkor. The elliptical potential lemma revisited. arXiv preprini arXiv:2010. 10182, 2020.
[9] Nicolo Cesa- Bianchi, Tommaso Cesari, and Vianney Perchet. Dynamic pricing with finitely many unknown valuations. In Algorithmic Learning Theory, pages 247-273. PMLR, 2019.
[10] Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covari- ates. Operations Research, 69(3):974-984, 2021.
[11] Maxime C Cohen, Ilan Lobel, and Renato Paes Lome. Feature-based dynamic pricing, Manage- ment Science, 66 (6(11):92114444 2020.
[12] Arnodd Den Boer. Dynamic pricing and learning: historical origins, current research, and 2015.
new directions. Surveys in operations research and management science,
[13] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[14) Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association, 119(545):522-564, 2024.
[15] Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9):1-49, 2019.
[16] N Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptoti- cally optimal semi-myopic policies. Operations research, (2(5):1122-116, 2014.
[17] Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17, 2004.
(18) Robert Kleinberg and Tom Leighton. The value of knowing demand curve: Bounds regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages
IEEE, 2003.
[19] Kenneth Littlewood. Forecasting and control of passenger bookings. The Airline Group of the International Federation of Operational Research Societies, 12:95-117, 1972.
[20] Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1078. SIAM, 2021.
[21] Yiyun Luo, Will Wei Sun, and Yufeng Liu. Contextual dynamic pricing with unknown noise: Explore-then then-uch strategy and improved regrets. Advances in Neural Information Processing Systems, 35: 2022.
[22] Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution freee contextual dynamic pricing. Mathematics of Operations Research, 49(1):599-61) 2024.
[23] Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. Advances in Neural Information Processing Systems, 24, 2011.
11

---

[24] Jieming Mao, Renato Leme, and Jon Schneider. Contextual pricing for lipschitz buyers. Advances Neural Information Processing Systems, 31, 2018.
[25] Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693-721, 2013.
[26] Marvin Rothstein. Hotel overbooking markovian sequential decision process. Decision Sciences, 5(3):389 404, 1974.
[27] Jon Schneider and Julian Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. Advances in Neural Information Processing Systems, 36, 2024.
[28] Virag Shah, Ramesh Johari, and Jose Blanchet. Semi- cemi-parametric dynamic contextual pricing. Advances in Neural Information Processing Systems, 32, 2019.
[29] Roman Vershynin. /ligh-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
[30] Chi-Hua Wang, Zhanyu Wang, Will Wei Sun, and Guang Cheng. Online regularization toward always-valid nigh-dimensional dynamic pricing. Journal of the American Statistical Association, pages 1-13, 2023.
[31] Jianyu Xu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. International Conference on Artificial Intelligence and Statistics, pages 9643-9662. PMLR, 2022.
12

---

A Simulations
1.
20"
0.2
Figure 1: The plots here show the regrets rate of VAPE for linear evaluations, both in the standard and logarithmic scale (left and right respectively). The solid lines represent the average of the performance over 15 repetitions of the routine. The faded red area shows the standard error, while in the right subplot the dotted line corresponds the theoretical regret bound.
Compar son Stochastic Care
Comparsinn ADversaTi Case
10
5.0
The two subplots show a comparison between VAPE and the algorithm in 14 in the stochastic and adversarial case, where the time horizons used are T E [1000, 1700, 3000, 5000] (left subplot), and T E [1000, 1400, 9000] (right subplot). In both cases the solid lines represent the average of the regret rates across the 15 repetitions of the simulations, while the faded area the standard error. In the subplot on the right, due to the specificity of the setting, the variance across runs is minimal, hence the faded results invisible. The regret graph is in both cases plotted in logaritmic scale.
Figure 2:
In this section, illustrate some numerical simulations that aim show the empirical per- formance of our VAPE algorithm for Linear Valuations. Moreover we present compari- son with the algorithm proposed in [14] in the case in which the only regularity assumed on the CDF of the noise distribution is Lipschitzness. The code implemented for these simulations is publicly available in the repository: https://githus: cottt//////aiiileeeiii//// Improved-Alge Algori howpa/ss-ooo-ooototu-a-a-a--eeee
VAPE In order to test our algorithm, we built dataset of 5 contexts belonging to R² generated by canonical gaussian distribution and subsequently normalized. Throughout the run the contexts are chosen from this set uniformly at random, while the noise term is picked from gaussian distribution truncated between - and with mean 0 and variance 0.1. Similarly, also the parameter 0 is normalized vector initially drawn from gaussian distribution. The algorithm has been tested on time horizons T [1000, 10000, 50000, 200000, 500000, 800000], and the hyperparameters a, μr, are set as in the statement of Theorem [ Figure [ shows the results of this implementation. The empirical regret rates of VAPE respect the theoretical upper-bound expressed in the paper, moreover it shows optimal computational times that can handle big time horizons.
13

---

Next we compare our algorithm with the algorithm proposed in Appendix F of [14], in which they propose a routine tackle the dynamic pricing problem with linear valuation in the case in which the CDF F is Lipschitz. The comparison is carried out in two different settings: a stochastic and an adversarial one, and to make more fair both algorithm receive as input the time horizon T.
Comparison with [14]
In the stochastic case, similarly as before we consider set of possible contexts in R drawn uniformly at random and then normalised. During the routine, each time step one of these is randomly selected. This method of receiving contexts meets the assumption included in [4), making sure that no eigenvalue of the covariance matrix of the distribution of contexts is too small. As for the contexts, the parameter 0 is selected ex-novo with every new run of the algorithm. We chose to implement& comparison with this specific algorithms since it was among the closest with our work, as discussed in the main paper, but its prohibitive computational costs make difficult to see the good behaviour of VAPE which, being based on bandit approach, requires bigger time horizons converge.
The adversarial case, instead is toy example which is purposely designed to badly interfere with the algorithm proposed by [14]. In this case the set of contexts is made of only two samples of orthogonal vectors, specifically in the form [x,, 0, contexts is not invalidated by the parameter 0, this is considered to be fixed as [0.3, 0.3, 0.3). The algorithm receives the first context during the exploration phase and the second during the exploitation one, such that the information gathered initially result meaningless in the latter subroutine. As before the computational costs of [14 limited the time horizons on which we were able run this simulation, still it can be noted how VAPE, exposed to the same contexts in the same order, does not suffer from such choice, since the phases are defined adaptively, thus its regret rates remain consistent with the stochastic case. The results of this comparison are shown in Figure 2
z] and [0, 1, 0]. To make sure that the effect of this choice of
B Proof of Theorem
We state several lemmas before proving Theorem T We begin by bounding the length of the exploration phase corresponding to lines 5 and 6 of Algorithm
Lemma 1. Let 9 {1 T = 1}. Almost surely, the length of exploration phase is bounded as d log T+d)
G
The following lemma bounds the error of our estimates for and D, for the values of μ prescribed in Before stating the Lemma, we define the event
Theorem |
vt 19: g(x.)) s c, and DJ -D(Ke) s (20g(11/a) 8=
N + -ICJ. )
Lemma 2. The event E happens with probability at least (a + (Ta)))
Finally, we bound the number of times sub-optimal price increment he can selected. For p E R, E Rdd we define
A p) = sup x(x,p') - T TI,
B'E
Lemma 3. On the event for all t & G. if kt = k. then k must be such that
2 (lg(1/a)
A(T + kc) By
(4
+9gee
N
We are now ready to bound the regret of Algorithm VAPE for Linear Valuations. We begin by rewriting the regret as
max T(.. p)) T (()),P)) pE(D,,,)
RT
1=1
Σ
max T(xx:P) - T(t,, (pE().B,)
+ Σ
max x(F,,P) -a (((..P))
(4)
tgg
14

---

Under Assumptions 1 and 3 both the optimal price and Pt are in [0, Byl, we know that the instantaneous regret is bounded by By. Then,
Σ tEg
max T(..P) - (((x, - By PE|o.B,)
(5)
Using Lemma together with the definition of 14, we find that
2
By log (Ta=e
By y dlog (B.T-11 + By
Σ max (T( π (xt,, S EE9 pE(o.B,]
(6)
62
We rely on the following Lemma to bound Engg (maxpejo. (z..)) T (Z)), Lemma 4. On the event E,
max x(F,,)) - T(x.. $ |AC] 512B, log + By log(1/a)
LT
pE|u,Byl
Lie
tgg
Combining Equations 4p. 16, and Lemma 4 we find that
Bydlog T+d)
By dlog [.T+1]
Bo
+ | 512B, (og(1/a) + 22 By log
R& S
Lege + 3,3BBT.6 TLee.
22
Using the definition of K, and a allows us to conclude the proof.
C Proof of Theorem
The proof of Theorem 2 follows closely the proof of Theorem 1 The following two Lemmas analogues Lemmas| and
Lemma Let X be an (zf,) V -covering of B a of minimal cardinality, and G UG.
xEA
Almost surely, the length of exploration phase G is bounded as
3Lg
4/
| S
2B,
+1) (T (T+
Recall that we defined the event
2log(1/a) + LEE
E = Vt & G. l3: g(x,)) s e, and Dt D(ke) -
No.
The following lemma shows that & happens with large probability. Lemma 6. The event & happens with probability at least + 2T
The rest of the proof holds follows the proof Theorem
In particular, on the event E, we still have
Rr Σ
max T(Z,P) - T(Ft.Pt) pc)
Σ
max T(Fr,)) - T(Et, (E(
tgg
Bg log(l////// (og(1/a))
< ByIgi + |C]
512B, log(1/a) + 22
36 TLee..
Lee
where we used the fact that the instantancous regret is bounded by B, along with Lemma 4 Using Lemma we obtain
31.g
V/8
512B, log(1/a) + 22 By log(1/a)
Ro 5 By
2B
+1
(++1)+
+ 36B, Lge.
Lge
Using the definition of K,, and allows us to conclude the proof.
15

---

D Proof of Auxilliary Lemmas
D.1 Proof of Lemmal
We use the elliptical potential Lemma (see, e.g., Proposition in [8] to bound the total number of rounds used estimate 6. Formally, denote the estimation indices {fi (f1...,t() } and notice that
= 1 only for these indices. Thus, for all i [[9]], we can write V,, = Ek= Lz, Rt + La and
4-11 In particular, the elliptical potential lemma implies that
10
| + d
Σ 2L bly
Ta llv $
gldlog
Since for all such that = 1, V 2t 2 this implies that
[9] + d d
1 S
gld
Now, almost surely, |g] < T. Using this bound and reorganizing the inequality leads to the desired result
d log
(+d)
| S
2
D.2 Proof of Lemma 2
Lemma 2 is obtained by combining the following two results.
Lemma 7. Let us define the event
& = (vt $ g (9(x)) Tel s
Then, the event & happens with probability least
The remainder the proof follows from the following lemma. Lemma 8. Let us define the event
llg(11/a) No.
+ Lge J
E=
E ( DJ D(ke) S
Assume that event & holds with probability a. Then, the event happens with probability at least 1 (a + 2T KCla).
D.3 Proof of Lemma 3
We assume that & G. that k; = and that No 0 (otherwise the statement trivial). We begin by stating an auxiliary result, which follows immediately from Lemma 2 Lemma 9, On the event E, we have that for all & G. and all l A,;
LCB,(K) S ( 9. ke) I (k).
Moreover. kt Kr, where
k arg max π (Iz, ÿr + ke). kEA:
On the event E, Lemma implies that
π ( Dr ke) 2 LCB(k)
UCB(A) - (UCB(K) - LCB(k)).
Since kiz Ar, we have
UCB;(k) (k)).
16

---

This implies
T gt + kε) 2 (C])(k)] (UCB, LCBB(())
=KCB((k)) - (UCB,(K) - LCB,(K)) (UCB,(K)) (kE)
2 ( Ir -kfe) (KCCB.(K) - (LCB,) (UCB)) -LCC((
(kB,
Thus,
(x. Dt + k) - π (2 It + ke)
< (UCB,(k) (k), + (UCB,(K)) - LCB,(
Now,
(1 (8l08(1/a)
UCB LCB,(k) = (0t + kc)
ALge
No
8log(1/a) No
S By
+ 4T.e
since & AA. Moreover, since h k. and since Kn Kr by Lemma This implics that
we know that N S N.:..
(N
(8log(1/a)
UCB (k) = (ōe + kgc)
+ 4Lge
N"i
I By (v
8log(1//))
+ ALęE
No
Thus,
(v
(log(1/o)
n (xc, 0e k, T02, Øe ke) S 2B
+ 4T-ge N
Next, we bound the discretization enror using the following Lemma. Lemma 10. On the event E, we have that
sup Bel
T(E,,P) - T T. + k)e) S ByLee.
By Lemma
Equation
implies that on the event E,
2 2lo((1/a)
A A(xx T. + ke) S By (4
+ 9bge
No
D.4
Proof of Lemma 4
Note that
max T(E,,p) (((eP))) pE]
MΣ Σ
A A To ke)
(8)
tg
KEK tEG:k.=k
We bound this term on the high-probability event E. For & K,, we define t <
tk
the rounds where t & G and k; = k. We split these rounds into episodes as follows. We define -- loga (18Lge)]. For a E [1,a]] a). also define
128 log(1/a)
2 2a
17

---

With these notations, we have
Σ
A Dt + kc) =
Σ
Det + ké) + Σ Σ
A Dc: - kc)
reStk==k
iStiAN
LAN Si
Σ
( Det + kt)
bAA 741 <igN
On the one hand, (ar. S By for all s0
Σ
A Dct kc) S Byb
iSHANT
On the other hand, using Lemma
we see that on the event E, if 2 la and a E [1,
log(11/)
Aiy + ke) s By
ta
-
S By
+ 9
2
Since 2 2 18Lge, this implies that
(Z Det + kc) S 2- BB
Then,
Σ
Σ
Alz Fet + ke) < B,
(la+1 [ta] + +1)2
a=1
LAN <15to+1AN441
e=1
S B 7-1
(fa+1 - 12)2 a + B
By definition of ta, this implies that
Σ
Σ
A 9e ke) < 128B, log(1/a)
(22++2 220) 2- By
LAN +1 SiSte41AN T41
< log(1/a)
1+ Σ 2a
a=1
384B, log(1/a)2
$ 22 By log (1/a)
Lge
where we used that 2 < 184ge
Similarly,
Σ
A Fot + kc) 22),
GAN <igNE
$ N Ige.
Combining these results, we find that
B, log(1/a)
Σ A(ri, + kc) 512B, log(1/o) + 22
No..,N Igg.
(9)
Lge
=k
We conclude the proof by summing over & K, and using the fact that Ntex S.
18

---

D.5 Proof of Lemma 5
We note that
| - [+
We conclude by using classical results covering number of the ball (see, e.g., Corollary 4.2.13 in (2)),, stating that there exists an (3--V\--overinn of the ball of radius Bg in dimension d of
32g
1/8
d
cardinality at most 2BB
3hg
+1
D.6 Proof of Lemma 6
The proof of Gemma/6relies on the following Lemma.
Lemma 11. Let us define the event
E (vt g (g(x)) ((T:)) s c)
Then, the event & happens with probability at least 1-a.
Note that Lemma 8 still holds for non-parametric valuations. This concludes the proof of Lemma 6
D.7 Proof of Lemma
We introduce the variables
8. = 4 and Úr 2By4 - 2
2
and the o-algebra F; ((I,)s<44)) (0.).5t). Since Vi-1 and xa Feer-uuuurrall. then does 4, and thus both ž1+1 and 8/ are F-mmesuraale. Moreover, for any round where 4 = 1, the price is chosen uniformly at random and we have
du 2B
[i 4
2
P [ < ye Fr-1]
By
By
By
Be
1 Ifu S x.7 0 {} f(E) de du By
Bg
Bg
E+a
duf(E) dI By
Be
1
T 0
+
ES(E) de
Be
where in the last equality used that Dr {.({E) dg E [&]]] 0. The same relation also trivially
holds when & 0. Thus, conditionally Ft-1, 1. ÿt $.. 0 is centered and in [ -B By), which implies that it is Byy-subgaussian. Now, for all f I T, we have
0. = =B
Σ sct
1 +Id
Σ
O,
SEG
-1
Σ SC1
J +
Ia
Σ JoE..
sct
Using the fact that for all t 2 1, || < Bz, and that ||0|| S Bp, and applying Theorem 2 in (1, we find that for all 2 0, with probability a,
1 B2T
00 0 0 (E.e ",5,+t, +1)) & By dlog
+ Ba.
19

---

Note that our definitions of 2, and D ensure that ||6: for all t,
5,57 a = 116, - -8llv. Moreover,
| (Ō. 0)1 s | llv, 110 0llv.
In particular, i & G, [ (((.))- 14,
+ 137
| (0. 0)1 S Boy dlog
+ Bo
The conclusion follows from the choice μ BB (By/dloo
1+
+ Bo) and the fact that
gt 2, O,.
D.8 Proof of Lemma
We rely on the following well-known result (we provide proof in the appendix for the sake of completeness).
Lemma 12. Let (We)121 be a sequence of random variables adapted for a filtration Fo such that E [Bte Fr-1] (m, M). Assume that for E N.. E {0,1} is Fim-mmeauurable, and define
3/
Nr Eoselo and Phe Exse (.,. if No 2 1. Then, for any t E N, and a E (0, 1),
N.
log(1/a) 2N
N oor p S (M- -mmm m)/
2 2ta.
Moreover, for any 1 > 0 and (0, 1).
1og(1/a)
P N₂ I and piel 2 (M- -m)
$ 2a.
2N
Note Lemma 8 holds trivially for all t such that N 0. Therefore assume w.l.o.g. that N 2 1 (otherwise the statement trivial). For any such given E [T). we control the error |F F [ uniformly for & E K. To do so, we rely Lemma 12 we define i, = 1 f4 0 and k k}. and note that for F; = ((x1, ..., I1t1), (o (o....., 0z)), - -i---uaaaurblle, and oe is F, adapted. Moreover,
TE [o = úp (g(2,) + + 2 9t + ke)
= - (āe g(xz) + kc),
and directly by definition, it holds that D E.s, uo probability 1 - 2at, No-- = or
Using Lemma
we find that with
N:
EssitD (Tr - g(xz) + kε)
E.s T.
2 2lo((1/))
D
N
N
Moreover, on the event E,, which happens w.p. at least 1 - a, for all t $ G, l9. g(xx)l S e. Using the fact that D is Lg-Lipschitz, we find that for all $ G,
D (0: g(xx)) + ke) D (kc) s Le g(xx)) s Lge.
Thus, with probability 2nt,
log(1/a) No
DJ (9-D(ke)) S
+ Lge.
Using a union bound over all & E K. and E [T] and then intersecting with E, using another union bound yields the desired result.
20

---

D.9 Proof of Lemma
For any & 9, denoting Pb(k) = - + ke, we first rewrite
x(Fe, (k)) (lp)( (p: & s (H)))
(r (p: s g(()) (k).
((p -x(x))
(Ā) + ke) g(xr) +kt)
( + kc) + (ā: + kc) [D() g(xz) + ke) D
Since the event & holds, the following hold for all and Ar:
2log(1/a) N
Th g(x+)) e, and
D (Dke) -
+ Lge.
In particular, we have that:
D( g(xe) ke) Dt s |D( g(xx) + kε) D(ke) [(ke) DP
Lg - g(xxe) + D(ke) D
Lee + 2log(1/a) LGe
No
log(1/a) No.
2Lee
Relation (1) holds since D is Lę-Lipschitz and (2) under the event for all & E. As the set A is chosen such that De + kee for all Ar, implies that
(ee + +kee (v 2log(1/a)
T (Tr. ke) (et ke) Dt
2T
No
Reorganizing, get for all k E Ar and $ G
(k) S π (π D. + kc) < (k).
which proves the first part of the statement.
Now let kj E arg max Tt T( Øt + ke). By the first part of the claim, it holds that
UCB)(k)) 2 T فe + kT = max (It. T. + ke)
max LCB,
REA:
REA:
where relations (x) are due the first part of the lemma; this proves that k E Kr.
D.10 Proof of Lemma 10
The proof follows by noticing that, on the one hand, K. ensures that for all E [0, Bgl, there exists à E K. such that Ør + kc [0, By) and [ ke pl I On the other hand, the prices considered are bounded by By, and the demand function Lg Lipschitn,,, so the reward function m Lipschii..
D.11 Proof of Lemma
For ह E X. let us define recursively the variables of = 1 [ = Z). and for > 1, o
{ T. = E, and Ener 1% < <)) and define the variables
Ot - 2 ge = = ((())) and Te = 2B
21

---

and the o-algebra Fi = (oo))ss+11(o))sst Note that o is Fi-1 Fe-u-measurable, and thus both
Tt-1 and Y/ are F:-meauurable Moreover, for any round where o = 1, the price is chosen uniformly random and we have
du
E
F
x
2B
PP uu S Fr
By
B
2B,
a x
{u S g(xz)) + + f(5) de du By
Bg
{tg(z))
dus(E) de - By
Bg
B.
L -Bc
Bt
1 g(xr)) +
Ef(5) de
9t
where in the last equality we used that D.p Ef(E) do = E [c:] = 0. The same relation also trivially
holds when of = O. Thus, conditionally on 1, Dt DE is centered and in [ By Byl- We denote
No =ooct t we note that if $ G", then N [T] a.s. Using Lemma 12 we find that for all
I $ g a.s., No [T]. Then,
Eeeg a<t Vf
Ft
(og(2
P
38 g=:
2 2By
No
2[T]
ExEgE set D7
1og(2[{{/a))
S
N
[r]and and
2 2
N7
2[
X
Moreover, since is (gg, HolHdr continuous, and 1+
xzll
5
1/0
a.s., we have
32g
1/57
(r(T,)) Fel 5 Lig
3T.
3
Then, with probability at least 1 a//3/,,, for all & g
log (
(0(Z,) - -((t))((TT) < 2B,
2[T]
2c
<
3
where we used 7 = 18B; (PP)))))
Using a union bound over X, we find that with probability at
least 1 - a, for all & gr,
2e 3
[0(x.) g(xx))=
Similarly, for all & G. (1((x)) g(x+))l S L.gai Then, we have that with probability a, for all t $ g".
(T(T.) g(xz)) S e.
22

---

D.12 Proof of Lemma 12
Let us define Ze = Exst Lv E [l and for I E R, M, exp (IZ, 2² (1MMm))MM
We begin by showing that M, a super-martingale. Indeed, we have that
E c Teeauloo-Buulleeee Blull- Ft-1 = Elv + (1-4) (4) Fr-
(M (1 - 4))
S e
where the fact that (yt E lye F(-1)) is bounded in [m, M] together with the conditional version of Hoeffding's Lemma. Noticing that
M, Me Elp./Fr-11) (2)-
this proves that M, is super-martingale, and so E [M]] < [MM]] = 1.
Now, for all > 0 and all E N, and all
O, by
argument,
(Zz 2 e and N₂ 1) P. (1 (N- 1} e 2 e(a))
S e E (e (e (NV =1})
e crt PP(
(z -2
(N₂ =1}
Using the previous result, we have that
E
22,
Prar
1t
I =1} -E 22, 32
(N. = =13
2 1am--m)3 N
S e
[(MM)
s E(Mo) = 1.
SO
(Z, 2 and N: S e cea+ 2 m1)
In particular, for (M m) (1/a) and TMM-m22
4r
log
P Z (M- m)
and N₂ = Sa.
2
This proves the first part of the Lemma. Summing over the values of | from 1 to t, we find that Similar arguments can be used to prove that
N₁ log(1/a)
P Z, 2 (M m)
and N, 2 1 s la.
2
No log(//) and N, 22 to.
P 7, 2 (M m)y
Noting that N. and normalizing by N, (and since adding the case only increase the probability) concludes the proof of the Lemma.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction. we claim to present novel approach to dynamic pricing that enjoys improved regret bounds. We clearly state the approach and explain is novelty, while proving all stated bounds in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The main limitations our papers due to the assumptions the setting. While we follow minimal set of assumptions that is standard in the dynamic pricing literature, we discuss how to alleviate them in the conclusion section. The computational complexity of our algorithm is comparable to previous work on the topic: the complexity of the price elimination polylog (d, T), while the complexity of the valuation estimation depends on the valuation model. For linear valuations, it is polynomial, while for non- parametric ones, is exponential as standard the non-parametric bandit literature.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
24

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We clearly state our assumptions and prove the results the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification:
The information needed reproduce the experiment detailed in Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
25

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code reproduce the experiments is publicly // in the repository /ttps://githhe com/ Matildefulea1)
available
Improved- Algortthns for -ww.-onottttaaayyaanio------e-e
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cr cc/
cublic/guides/Cee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
sww.iioiiciiicicooooooooooa for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details of the implementations of the simulations detailed in Appendix A.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All the information relative to the statistical significance of the algorithm contained in Appendix A.
26

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All the simulation be (and were) on laptop without gpus.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://nuuiippp hwt.c///bbbc.c.ciccciiiiiieeeeee
Answer: [Yes]
Justification: The paper theoretically studies well-established theoretical problem; as such, it does not have any direct ethical implications.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
27

---

Answer: [Yes]
Justification: The paper theoretically studies a well-established theoretical problem and the broader impact of our work is only due the potential impact of advancements in this problem. As all pricing problems, dynamic pricing can have both positive and negative cennacts-offeriee prices that more suited to the buyers on the one hand, while increasing the seller's revenue at the expense of buyers on the other hand. In addition, as with many contextual problems, there might be biases and challenges involving fairness one should make sure that similar customers are offered similar prices. This study is orthogonal to ours, and we leave future work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deg.lymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
28

---

Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssiip thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
29

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
30


Reviews:
[{"review_id": "9wFivBnTk6", "reviewer": "Reviewer_beqc", "summary": "This paper studies the problem of online contextual pricing under a linear noisy valuation model, with the noise distribution **unknown** to the seller. This work proposes an \"exploration-then-elimination\" algorithm that achieves $O(T^{2/3})$ **optimal** regret under the assumptions of (1) stochastic feature sequence, (2) Lipschitz noise CDF, and (3) bounded feature norm and noise range. Besides, this work also studies the non-parametric $\\beta$-Holder valuation model, and propose an algorithm that achieves $O(T^{d+2\\beta/d+3\\beta})$ regret.", "questions": "The authors are encouraged to respond to the following questions at a secondary priority (i.e. after kindly answering my questions in \"Weaknesses\").\n\n1, Regarding Weakness 1, is there any necessity to apply a policy eliminiation strategy in stage 2 of VAPE? Can it be replaced by a (version of) UCB without impairing the regret rate?\n\n2, On Page 5 Line 196, Please kindly explain the difference between your work and Fan et al. (2024) for valuation estimation methods in details.", "limitations": "The authors have discussed the limitations in their Conclusions. Overall, this is a theoretic work and there are not much societal impact involved. However, the authors are encouraged to discuss more on the societal aspect of the work, e.g. personalized pricing and unfairnesses.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1, The problem of contextual pricing problem has been extensively studied over the past few years. However, the minimax regret of linear noisy valuation model with unknown noise distribution is a long-existing open problem. Existing works leave a gap between $O(T^{3/4})$ and $\\Omega(T^{2/3})$ under the assumption of Lipschitz noise CDF. This work closes the gap by showing that $O(T^{2/3})$ is the correct minimax regret, under certain assumptions.\n\n2, This work also considers the non-parametric $\\beta$-Holder valuation model, and propose an algorithm that achieves $O(T^{d+2\\beta/d+3\\beta})$ regret. This problem is relatively new to the community but it is important as well. In most of the cases, we cannot rely on the correctness of a linear model (although it is causally sound), and therefore this non-parametric model is of significance.", "weaknesses": "1, The algorithm, VAPE, proposed in this work is quite similar to the \"Explore-then-UCB\" algorithm in Luo et al. (2022, Neurips). Seems like the authors are unaware of this work at all. The only difference is that VAPE adopts a policy-elimination design in the second stage after uniformly pure exploration, while Luo et al. (2022) uses a UCB-style strategy. From the perspective of regret analysis, I do not think there are much difference between those two methods. I then went back to the previous work and looked into their regret analysis, and noticed that they were using a linear bandit model instead of a multi-armed bandit (which is also applicable), which brings an extra $\\sqrt{\\frac1{\\Delta}}$ multiplier on the regret of the second stage, where $\\Delta$ is the discretization grid size. In other words, by slightly modifying the \"Explore-then-UCB\" algorithm, it is able to achieve $O(T^{2/3})$ regret instead of $O(T^{3/4})$ as they claimed. Since both of your works share the same idea of uniformly-pure-exploration stage for an unbiased estimate of $x^\\top\\theta^*$, which actually originates from Fan et al. (2024, JASA), I am skeptical to the novelty of this work, especially from the perspective of methodology.\n\nThe authors are encouraged to discuss how their methods and analysis are different from Luo et al. (2022) in the rebuttal. This is the major concern that I (and other reviewers as I expect) would have.\n\n2, The authors claim that it is required to assume Lipschitzness on the noise CDF, which is commonly applied except for Xu and Wang (2022, Aistats). It is worth noting that Xu and Wang (2022) have proposed an insight on the \"Half-Lipschitz\" nature of a pricing problem, indicating that the regret rate would not be different with or without Lipschitz assumption. \n\nIf this is not applicable, the authors are encouraged to explain in the rebuttal how the \"Half-Lipschitz\" nature does not work.\n\n\n\nReferences:\n\nXu, Jianyu, and Yu-Xiang Wang. \"Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n\nLuo, Yiyun, Will Wei Sun, and Yufeng Liu. \"Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets.\" Advances in Neural Information Processing Systems 35 (2022): 37445-37457.\n\nFan, Jianqing, Yongyi Guo, and Mengxin Yu. \"Policy optimization using semiparametric models for dynamic pricing.\" Journal of the American Statistical Association 119.545 (2024): 552-564.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful analysis.\n\n### Weaknesses\n1/ We thank the reviewer for providing us with this relevant reference.  As noted by the reviewer, both our work and that of [1] use the idea of sharing knowledge across contexts to improve the estimation of the c.d.f. $F$. However, our algorithm diverges significantly from theirs in three main aspects.\n \nFirst, our algorithm achieves the optimal regret rate, in contrast to [1]. [1] recast the problem as a perturbed linear bandit problem, which results in a **sub-optimal regret rate**, not merely as a proof artifact: the algorithm for perturbed linear bandits inherently exhibits regret that is linear in the dimension, here, the size of the discretization.\n \nSecondly, we believe that our algorithm is conceptually simpler. Instead of recasting the problem as a perturbed linear bandit in large dimensions, we phrase it as a simple, multi-arm bandit problem. Our expressions of the confidence intervals for the rewards are arguably more intuitive than the UCB in [1]. This simple formulation clarifies the sources of difficulty instead of obscuring them by reducing them to other intermediate problems, thereby helping the reader's understanding. We show that the problem is no more difficult than its non-contextual counterpart due to information sharing across contexts (highlighted in the proof of Claim 1), an idea absent from [1]: in contrast, the higher regret rate in [1] suggests that the contextual problem leads to higher regret. Additionally, our formulation helps generalizing our approach to other valuation models, as demonstrated with $\\beta$-Hölder valuations.\n\nAs a third point, we point out that [1] assumes i.i.d. contexts, with bounded eigenvalues of the covariance matrix. This assumption is removed in our work, and our algorithm can handle adversarial contexts.\n \n2/ [2] rely on a black-box, expert aggregation algorithm, where each expert represents a possible value of the pair ($\\theta$, $F$) on a discretized grid. They control the discretization error by noticing that posting a price slightly lower than the optimum price can only decrease the reward by the difference between the optimal price and this price. Thus, this half-Lipschitzness of the problem leads them to design an algorithm that essentially “rounds down” prices.\n \nBy contrast, our algorithm first estimates the parameters, before running a bandit algorithm across the grid of prices that learns and shares information across contexts. This is only possible if the error made in the first phase in estimating $\\theta$ implies a small error in the second phase in estimating $F(\\delta)$ for values of $\\delta$ over a grid. More precisely, if we knew exactly the value of  $x_t^{\\top}\\theta$, we could learn the value of $F(\\delta)$ by posting a price $x_t^{\\top}\\theta + \\delta$ without assuming Lipschitness of $F$. However, since we only know $x_t^{\\top}\\theta$ up to a small error $\\epsilon$, we must assume that $F(\\delta) \\approx F(\\delta \\pm \\epsilon)$ to learn $F(\\delta)$.\n \nWhile our assumptions are stronger than that of [2], our regret rates are lower (and match the lower bound established for Lipschitz-continuous c.d.f.). Whether the rate of $T^{2/3}$ can be achieved without this assumption, or whether the minimax optimal rate differs when $F$ is not Lipschitz continuous, is an interesting question.\n \n### Questions \n1/ We agree that a UCB-type algorithm could be used instead of a Successive Elimination algorithm in the second phase of VAPE, provided that the expression for the Upper Confidence Bound for the rewards of the different prices be similar to that of Line 10 in Algorithm 2 or Algorithm 3. In this sense, there is no necessity to apply a successive elimination approach; however elimination-based methods are not conceptually more complex than a UCB-type of approach.\n\n2/ We agree that our claim in Lines 185-186 is misleading. Indeed, some previous works have used the same method to estimate $g$, as noted by the reviewer. We sincerely apologize for conveying the wrong message.\n\nWhat we meant was that the remark that $g$ can be estimated using $1$-bit feedback allows us to decouple the estimation of $g$ and $F$ and estimate them in a straightforward manner, which seems to have been overlooked by previous works (that we were aware of). Closest to our method is probably [3]: the authors use the same method for estimating $g$, however, their estimation of $F$ strongly differs: they do it in an **explore-exploit fashion**, using **kernel estimators** that are fitted **on the samples already used to estimate $g$**. By contrast, we use piecewise-constant estimators, fitted in a regret-minimization sub-routine. We argue that our estimators are easier to interpret and that the assumptions necessary to establish our result are milder and less cumbersome than those of [3]. Moreover, explore-exploit approaches require i.i.d. contexts with strictly positive definite covariance matrices, while ours can handle adversarial contexts.\n \nHowever, as the reviewer pointed out, our approach for estimating the pair ($g$, $F$) is close to that of [1]. We therefore propose to remove this sentence altogether, and to add further detail on the distinction between our work, that of Luo et al (2022), and that of [3].\n\n**Limitations:** We acknowledge that the nature of the problem could raise fairness issues. We addressed some of these in the checklist under the “Broader Impacts” section. We are willing to move the paragraph to the main paper.\n \n----\n\n[1] Luo, Yiyun, Will Wei Sun, and Yufeng Liu. \"Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets.\" NeurIPS, 2022\n\n[2] Xu, Jianyu, and Yu-Xiang Wang. \"Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.\" ICAIS, 2022.\n\n[3] Fan, Jianqing, Yongyi Guo, and Mengxin Yu. \"Policy optimization using semiparametric models for dynamic pricing.\" JASA, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sU8DGlcqXn", "reviewer": "Reviewer_EQLG", "summary": "The paper addresses the problem of dynamic pricing using contextual information, aiming to maximize a seller's revenue by setting prices based on the context and buyer valuations. Buyers purchase products if the prices are lower than their valuations. The authors propose an algorithm called VALUATION APPROXIMATION - PRICE ELIMINATION (VAPE) and analyze its performance under two valuation models: the linear valuation model and the non-parametric valuation model.", "questions": "- In the definition of regret (between lines 96 and 97), it seems that the optimal price (i.e., the one in the max) is unique for every product. I expect that every context presents an optimal price. Do the authors agree?\n\n- Lines 277-278: can the authors provide some more comments on the results and compare the assumptions of the other works to the one in this paper?", "limitations": "No limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow.\n\n- The work is well-motivated from the practical perspective.\n\n- The theoretical results seem to be correct, even if I did not check the proofs carefully.\n\n- The related works are properly discussed.", "weaknesses": "- A paper with such practical motivation would benefit greatly from being accompanied by a thorough experimental campaign.\n\n- See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comment.\n\n### Weaknesses\n\n**Experiments:** We agree with the reviewer that it would be beneficial to further demonstrate the advantages of our approach over previously suggested algorithms through empirical evaluation. We started implementing our algorithm and the various baselines, but sadly, due to the short time, we did not complete the implementation in time for the rebuttal deadline. In particular, some baselines are extremely computationally demanding, and we would require additional time to perform statistically valid evaluations. We will update the final version of the paper with the results of this empirical evaluation.\n\n### Questions\n\n1/ This is indeed the case:  the optimal price depends on the context and varies with it. This is reflected in our expression of the regret as the optimal price is defined as the maximizer of the function $\\pi(x_t, p)$, which depends on the context $x_t$.\n\n2/ Concerning what is written in lines 277-278: both the papers directly mentioned in these lines share with us the assumptions of bounded context domain, parameter $\\theta$, and noise, as those are the standard assumptions in the literature. \n- [1] make assumptions milder than ours, as they do not assume the c.d.f. $F$ to be Lipschitz. Instead, they rely on the half-Lipschitz nature of the reward function, which gives a worse rate $T^{3/4}$ overall. To understand why we need to assume Lispchitzness of $F$, we kindly refer to the answer 2 of the weaknesses in the response to reviewer Beqc.\n- [2] relies on estimating the parameter $\\theta$ and $F$ in an explore-exploit fashion. They either achieve better regret rates under stronger assumptions, or worse rates under more similar assumptions. More precisely, their assumptions are stronger for the following reasons:\n\n    a/ To prove that the error from approximating the parameter $\\theta$ is small they need to assume both the contexts to be i.i.d. and a lower bound on the eigenvalues of the covariance matrix of their variance. Our estimator for $\\theta$ is built using a similar regression technique, but it does not require these assumptions (the contexts in our case can even be chosen adversarially), hence making the result more general.\n\n    b/ Furthermore, they assume the density of the noise to be lower-bounded by a constant $c$. The inverse of this quantity plays a role in the rate of the bound for the approximation of the CDF $F$, making it vacuous when $c$ is too small, and limiting the applicability of the result. Our estimate of the demand function relies on different tools, instead of the kernels estimators used in [2], hence does not require such an assumption.\n\n    c/ Another limiting assumption [2] introduce for their main algorithm is the strict monotonicity of the virtual value function (Assumption 2.1). This is necessary for them to ensure the uniqueness of the optimal price, which is needed to obtain small regret in their explore-exploit algorithm. Note how this is equivalent to asking the expected reward function $\\pi$ to be unimodal, which, again, is a more restrictive setting than the one we consider. This last assumption is relaxed in Appendix F, however at the cost of sub-optimal regret rates of order $T^{3/4}$.\n\t\nIn general, other rates can be obtained with stronger assumptions on the regularity of the distribution of the noise or the reward function, as summarized in Table 1. The algorithm we present is the one that achieves the best regret rates, especially optimal ones in the case of linear valuations, while at the same time requiring minimal assumptions on the noise distribution  (with the exception of the one in [1]) and allowing for adversarial contexts.\n\n----\n\n[1] Xu, Jianyu, and Yu-Xiang Wang. \"Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.\" ICAIS, 2022.\n[2] Fan, Jianqing, Yongyi Guo, and Mengxin Yu. \"Policy optimization using semiparametric models for dynamic pricing.\" JASA, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xAsyYQ5jNC", "reviewer": "Reviewer_B94q", "summary": "The paper studies the contextual dynamic pricing problem with binary demands and an unknown noise distribution. It presents a general framework for a pricing algorithm and proves its regret bounds for two specific types of valuation functions: linear and non-parametric. In the linear case, its results improve existing results and match the lower bound.", "questions": "Please check point (1) in weaknesses. Additionally, compared to [1], why do the proposed algorithms achieve better regret bounds with milder assumptions (e.g., Assumption 1 does not require i.i.d. contexts as in [1])? Is this improvement due to using bandit techniques (e.g., price/action eliminations) or other reasons? More explanation would be appreciated.", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and introduces a novel framework for solving and analyzing the contextual dynamic pricing problem with unknown noise distribution. This new framework can be applied in various settings and leads to algorithms with improved regret upper bounds in the linear case.", "weaknesses": "One potential concern is the paper's similarity with [1] in the exploration part and its contribution in this part. Line 186 mentions, “this method (using random pricing to construct unbiased estimates of $g(x_t)$) appears to have never been used in dynamic pricing” but as mentioned in line 195, if I understand correctly, [1] (where $g(x_t)$ is a linear function) also uses random pricing to construct such unbiased estimates. Although this paper’s main algorithm and analyses are different from [1]’s, a detailed discussion on the difference in using random prices as an exploration policy would be helpful to better understand its contribution.\n\nAnother minor weakness is the lack of experimental results. Numerical experiments could help validate the efficiency of the algorithms and demonstrate their potential advantages over existing methods.\n\n[1]Fan, Jianqing, Yongyi Guo, and Mengxin Yu. \"Policy optimization using semiparametric models for dynamic pricing.\" Journal of the American Statistical Association119.545 (2024): 552-564.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback.\n\n### Weaknesses: \n\nRegarding the statement made in line 186  and the differences with the work in [1] we kindly refer the reviewer to the second question in the response to reviewer Beqc, where we provide more explanation regarding what we meant by this statement and we propose to remove it, having acknowledged how it might appear misleading. Nonetheless, the two methods are not identical and, in particular, ours requires fewer assumptions as we will further explain below (for a more detailed comparison of the assumptions between our papers and [1], please refer to the second question in the response to reviewer EQLG).\n\nExperiments: we will add experiments to the final version of the paper (as we elaborate in the response to reviewer EQLG).\n\n### Question:\n\nAlthough our algorithm and the one proposed in [1] look similar, they present some fundamental differences that cannot be reconducted to mere technical details.\nWhat they propose is, in fact, an explore-exploit kind of strategy where in the first phase they gather information, by posting prices uniformly at random to build an estimate of the parameter $\\theta$ and the c.d.f. $F$, which are later on used to find the optimal price. Since their exploration phase is concentrated all at once in the initial part of their algorithm, they need to make sure to receive diverse context samples to estimate the parameter $\\theta$ with good precision, hence the reason for their more limiting assumption on the i.i.d. nature of the contexts, as well as the lower bound on the eigenvalues of the covariance matrix.\n\nOur strategy instead works adaptively, alternating between the value-approximation subroutine and the price-elimination one depending on the contexts received. On one side, this allows us to handle adversarial contexts, making our result more general; on the other, this minimizes the time spent in the exploration phase, and consequently, the regret accumulated.\nAs mentioned initially, the second phase of the algorithm in [1] consists of an exploitation of the information gathered before, which simply posts the optimal price with respect to the approximation of the expected reward function. To estimate this reward function, the authors estimate as an intermediate step the virtual value function. By contrast, our algorithm bypasses this intermediate step altogether, making it simpler.\nTo ensure convergence of the greedy price to the best price, the authors rely on assumption 2.1, which states the unimodality of the expected reward function. This assumption strongly limits the class of distributions for which this result is applicable. Without the unimodality assumption, their explore-exploit approach leads to $T^{3/4}$ regret, as discussed in Section 2.3 of our paper. In our price-elimination phase, we apply a multi-armed-bandit algorithm, which performs an extensive exploration across the possible price increments, mitigating the harmful effects that such exploration might have on the regret by allowing for the sharing of information among different contexts. This allows us to recover optimal regret rates while removing the unimodality assumption.\n\n----\n\n[1] Fan, Jianqing, Yongyi Guo, and Mengxin Yu. \"Policy optimization using semiparametric models for dynamic pricing.\" JASA, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UqyaqknuWE", "reviewer": "Reviewer_iWzp", "summary": "This paper expands the line of work on contextual dynamic pricing where the buyer's valuation may be noisy. The authors give a simple way to obtain an unbiased estimate for the true valuation function, and propose an exploration - exploitation type algorithm that learn simultaneously the true valuation function and the noise distribution. Based on this observation, algorithms are proposed for when the valuation function is a linear model or when it is Holder continuous.", "questions": "In assumption 2, it is assumed the noise is bounded. Do all prior work assume that the noise is bounded? Is there any work that does not? \n\nThis is minor, but I am not sure what the green / red color signify in table 1. Also you made the assumption that the noise is bounded, but this did not seem reflected in the rows where you presented your results. The table also has margin issues.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and I found it easy to follow. The necessary intuitions are adequately given. The main idea behind the algorithm is conceptually simple. \n\nThe results in this work expands the line of work on contextual dynamic pricing, though I did not check the proof, I believe the results are new and correct.", "weaknesses": "I think for me, the most limiting assumption is that the noise is i.i.d. across all contexts, which the authors also mentioned. \n\nIt may not be possible to add experiments now, but I think it will be helpful for this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comment.\n\n### Weaknesses\n\n**i.i.d noise:** This assumption is standard in the literature investigating the problem of dynamic pricing. For instance, all the papers mentioned in Table 1 share such noise structure. Nevertheless, as we mentioned in the conclusion, it could be of great interest to explore other assumptions, including a framework in which it depends on the context observed. The main reason that this assumption is needed is that the distribution itself determines the optimal price (and not only, say, its median or its mean), and therefore it has to be learned. If the distribution changes between contexts, all context-dependent distributions need to be learned, making the problem significantly more difficult in terms of regret.\n\n**Experiments:** We will add experiments to the final version of the paper (as we elaborate in the response to reviewer EQLG).\n\n### Questions\n\n**Bounded noise:** Indeed, having bounded noise is standard in the dynamic-pricing literature. Usually it is well-motivated by real-life applications - it is reasonable to consider that valuations for certain goods are bounded, which implies boundedness of the noise. Again referring to Table 1, all works make this assumption, with the exception of Cohen et al. 2019. However, their results are obtained either under the assumption that the noise is subgaussian with a very small variance factor (typically, $1/T$, so that the noise is supported on a very small interval with large probability, and the valuations are “almost deterministic”), or that the distribution of the noise is known. Both these assumptions are stronger than ours. In other works (eg. [14], [15], [21], [30]), as in ours, boundedness of the noise is necessary to ensure that the buyers’ evaluations live in a bounded interval.\n\n**Table:** The colors in the table on the left column are meant to highlight the assumption on the noise distribution and/or the reward function that are either more restrictive, marked in red, or match, in green, the one required for our algorithm. In the right column, our rates are in green, while worse rates obtained under the same assumptions are in red. We will make sure to add a sentence in the caption of the table to make this clear. We will also address the margin issues, and we thank the reviewer for bringing them to our attention.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Executive Summary

The paper studies online contextual pricing. The model is that at each time step a context x_t \in R^d arrives. The algorithm sets a price o_t. The buyer's valuation is y_t = g(x_t) + \eta_t and the buyer buys if y_t >= p_t. The paper generally assumes that the noise is Lipschitz, and that the feature norm and noise range are bounded. It then presents results for two settings. The first setting is when g is linear, for this setting the paper gives a O(T^2/3) regret bound (improving the state of the art O(T^3/4) and matching a lower bound of Omega(T^2/3) shown in prior work ([30], AISTATS 2022).  The second setting is a non-parametric onw, which assumes that g is \beta-Holder, for which the authors show a O(T^{d+2\beta/d+3\beta) regret bound.  This non-parametric model is less-studied but of significance, as it provides some additional robustification. As far as I can tell the paper does not provide evidence of the tightness/non-tightness of the regret guarantees in the \beta-Holder valuation model. 

Recommendation

I think this paper makes for a very nice NeurIPS paper, and closes the gap between upper and lower bound of the regret for a natural model of contextual pricing. I would therefore like to recommend it for acceptance (as a poster). 
This recommendation is in line with the reviewers who were unanimously positive about the paper (8,7,6,6 ). I would ask the authors to keep the comments and suggestion from the reviewers in mind when preparing the final version.
Decision: Accept (poster)