Improved Algorithms for Contextual Dynamic Pricing

Authors: matilde  tullii
solenne  gaucher
nadav  merlis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 11:03:25

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.

Main paper: 
 introduction: 
 Setting a price and devising a strategy to dynamically adjust it poses a fundamental challenge in revenue management. This problem, known as dynamic pricing or 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, a seller sequentially offers goods to arriving buyers by presenting a one-time offer at a specified price. If the offered price falls below the buyer's (unknown) valuation of the item, a transaction occurs, and the seller obtains the posted price as revenue. Conversely, if the price exceeds the buyer's valuation, the transaction fails, resulting in zero gain for the seller. Crucially, the seller solely receives binary feedback 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, or 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, or achieve sub-optimal regret bounds. In this work, we aim to improve both 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: 1) linear valuations, where the item valuation of buyers is an unknown noisy linear function of the context; and 2) non-parametric valuations, where the valuation is given by an unknown Hölder-continuous function of the contextual information, perturbed by noise. linear function, or by a non-parametric function. For both models, we present a general algorithmic scheme called VALUATION APPROXIMATION -PRICE ELIMINATION (VAPE), and provide bounds on its regret in both models:• In the linear model, we obtain a regret of Õ(T 2 /3 ), 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 it is attainable under minimal assumptions.• In the non-parametric model, we obtain a regret rate of Õ(T d+2β /d+3β ), assuming only the Lipschitz-continuity 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 as 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. In 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 3, we present our algorithmic scheme, VAPE, and provide an initial informal result bounding its regret. Then, in Section 4, we apply this algorithmic scheme to linear valuations and provide a bound on its regret. Finally, in Section 5, we extend this algorithm to non-parametric valuations.2 PreliminariesQuestion: 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 a novel approach to dynamic pricing that enjoys improved regret bounds. We clearly state the approach and explain its 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 in 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. 
model and notations: 
 The problem of dynamic pricing with contextual information is formalized as follows. At each step t ≤ T , a context x t ∈ R d , describing a sale session (product, customer, and context) is revealed. The customer assigns a hidden valuation y t to the product, and the seller proposes a price p t , based on x t and on historical sales records. If p t ≤ y t , the trade is successful, and the seller receives a reward y t ; otherwise the trade fails. The seller's only feedback is the binary outcome o t = 1{p t ≤ y t }. We assume that the seller's valuation is given byEQUATIONwhere g : R d → R is the valuation function, and ξ t is a centered, bounded, i.i.d. noise term, independent of x t and of (x s , p s , ξ s ) s<t . In the present paper, we consider successively linear and non-parametric valuation functions g in Sections 4 and 5. The seller's objective is to maximize the sum of her cumulative earnings. We denote by π(p, x t ) the expected reward of the seller if she posts a price p for a product described by covariate x t :π(x t , p) = E[p1{p ≤ y t }|p, x t ].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 R T , defined asR T = T t=1 max p∈R π(x t , p) - T t=1 π(x t , p t ).Notations Throughout this paper, we make use of the following notation. We denote by ∥•∥ the Euclidean norm. For all A, B ∈ R, we denote by A, B the set {A, A + 1, . . . , B}. R T ≲ B T (resp. R T = Õ(B T )) means that there exists a (possibly problem-dependent) constant C such that R T ≤ CB T (resp. R T = O(log(T ) C B T )). Finally, f and F denote the p.d.f. and c.d.f. of the noise, respectively.For both valuation models, we make the following assumptions on the context and noise distribution. Assumption 1. Contexts and expected valuations are bounded: ∥x t ∥ 2 ≤ B x and |g(x t )| ≤ B g a.s.This assumption is classical in contextual dynamic pricing problems. We underline that contexts do not need to be random. In particular, they can be chosen by an adaptive adversary, aware of the seller's strategy, and based on past realizations of (x s , p s , ξ s ) s<t . Assumption 1 is milder than the i.i.d. context assumption appearing in [14, 28, 10] .Dynamic pricing strategies mostly assume that the buyer's valuations are bounded. To enforce this, we assume that the noise is bounded; moreover, we assume that its c.d.f. Lipschitz continuous. Assumption 2. The noise ξ t is bounded:|ξ t | ≤ B ξ a.s. Moreover, its c.d.f. F is L ξ -Lispchitz continuous: for all (δ, δ ′ ) ∈ R d , |F (δ) -F (δ ′ )| ≤ L ξ |δ -δ ′ | .Assumption 2 is weaker than most of the assumptions in related works. For example, [15] require both F and 1 -F to be log-concave. [14] assume that F has m-th derivative, and that δ -1-F (δ) /F ′ (δ) is greater than some positive constant for all δ, achieving a regret of order Õ(T 2m+1 /4m-1 ). In the case m = 1, they propose a different algorithm, reaching a regret Õ(T 3 /4 ). [22] consider Lipschitzcontinuous noise, under the additional assumption that, for every x, p * (x) ∈ arg max p π(x, p) is unique, and that F ′′ is bounded. [10] assume quadratic behaviour around every maxima: for every x, p * (x) ∈ arg max p π(x, p), p * (x) is unique, and for all p, C(p 2 for some constants C, C ′ . The only work considering non-Lipschitz c.d.f. is [31] ; however, they achieve a higher regret bound of Õ(T 3 /4 ).* (x) -p) 2 ≤ π(x, p * (x)) -π(x, p) ≤ C ′ (p * (x) -p)For δ ∈ R, we denote D(δ) = P (ξ t ≥ δ) = 1 -F (δ), the demand function associated with the noise ξ t . Note that, under Assumption 2, D is L ξ -Lipschitz continuous. Straightforward computations show that, for any price increment δ ∈ R, the expected reward corresponding to the price p = g(x t ) + δ in the context x t is given by πEQUATIONEquation ( 2) highlights the intricate roles played by the expected valuation g(x t ) and the price increment δ = p -g(x t ) in the reward. An immediate consequence is that the optimal price increment δ depends on the value of g(x t ). Intuitively, if g(x t ) is large, the seller should choose δ to be small to ensure a high probability D(δ) to perform a trade. However, for smaller values of g(x t ), the seller might prefer a larger δ to ensure significant rewards when a trade occurs. Importantly, there is no explicit relationship between the optimal increments δ for different valuations g(x t ), so knowing the optimal price for a value g(x t ) does not allow optimal pricing for a different value g(x t ′ ).This reasoning suggests that the optimal price increment may span a wide range of values as the expected valuation g(x t ) varies. Unfortunately, as is typical in bandit problems, it is necessary 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 a broad range of price increments. This marks a significant departure from noncontextual dynamic pricing and 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 Õ(T 2 /3 ) encountered in non-contextual dynamic pricing problems, as we show in the following discussion.Naïve bandit algorithms for contextual dynamic pricing. As a first attempt, one might apply a simple explore-then-commit algorithm. Such algorithms start with an exploration phase to obtain uniformly good estimates of both g and of the demand function D over a finite grid of price increments {δ k } k∈K . 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 {δ k } k∈K with precision ϵ requires ϵ -2 |K| estimation rounds. Moreover, the Lipschitz continuity of the reward function implies a discretization error of order 1 /|K|. Classical arguments suggest that the regret would be at leastT (ϵ + 1 /|K|) + |K|ϵ -2 , which is minimized for ϵ = 1 /|K| = T -1 /4. Thus, this approach would lead to a regret of order Õ(T 3 /4 ).Another approach, akin to that used in [10] , involves partitioning the covariate space into bins and running independent algorithms for non-parametric bandits (such as CAB1 [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 1 /K. Classical results show that the regret in one bin is Õ(T T K = T /K is the number of rounds in each bin. Consequently, the regret is Õ( T /K + K × ( T /K) 2 /3 ), which is minimized for K = T 1 /4 , resulting in a regret Õ(T 3 /4 ).Thus, both approaches -using either independent bandit algorithms over binned contexts or common exploration rounds followed by an exploitation phase -suffer a regret of order T 3 /4 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(x t ) that share information across different values of g(x t ). We show that it achieves an optimal regret rate of order Õ(T 2 /3 ) in the linear valuation model. Moreover, it achieves a rate of order Õ(T d+2β /d+3β ) in the non-parametric valuation model under minimal assumptions.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The main limitations of our papers are due to the assumptions on the setting. While we follow a 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 is polylog(d, T ), while the complexity of the valuation estimation depends on the valuation model. For linear valuations, it is polynomial, while for nonparametric ones, it is exponential -as standard in the non-parametric bandit literature.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithmic approach: 
 In this section, we present the general algorithmic approach that we use to tackle dynamic pricing with covariates, called VALUATION APPROXIMATION -PRICE ELIMINATION (VAPE). Before presenting the full scheme, described in Algorithm 1, we start with some intuition that leads to its design. Then, we provide a first analysis of the regret of this algorithm.Equation (2) highlights how the reward is influenced by the expected valuation g(x t ) and by the demand at the price increment δ = p t -g(x t ). To separate the effect of these terms, we estimate g and D independently. Hereafter, we assume that the valuationsy t are bounded, in [-B y , B y ].Estimation of g. To estimate g(x t ), we rely on the following observation: when prices p t are uniformly chosen from the interval [-B y , B y ], the random variable 2B y (o t -1/2) can serve as an unbiased estimate of g(x t ) conditioned on x t . Given that 2B y (o t -1/2) is bounded, classical concentration results can be employed to bound the error of our estimates for g(x t ). Thus, in each round, we test whether our estimate of g(x t ) is precise enough to ensure that the error g(x t ) -g(x t ) is 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 non-parametric valuation functions, and we discuss how to ensure sufficient precision in a limited number of valuation approximation rounds.Previous approaches for estimating valuation functions in the linear model include the regularized maximum-likelihood estimator [15, 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 θ through logistic regression; however, they do not provide an explicit estimation rate for θ. [20] use the EXP-4 algorithm to aggregate policies corresponding to different values of θ and F , thus circumventing the necessity to estimate them. In a similar vein, in the non-parametric valuation model, [10] avoid the need to estimate g(x t ) by employing independent bandit algorithms for each (binned) value of x t . Closer to our method are the works of [14] and [21] , 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, we obtain better regret rates by using piecewise-constant estimators, fitted in a regret-minimization sub-routine, as detailed in the next paragraph. On the other hand, [14] performs a phase of pure exploitation, relying on an estimate of the CDF F that is constructed using Kernel methods. [21] , 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. A t ← {k ∈ K : g t + δ k ∈ [0, B y ]} 8: K t ← {k ∈ A t : UCB t (k) ≥ max k ′ ∈At LCB t (k ′ )} 9:Choose k t ∈ arg min k∈Kt N k t and post a price p t = g t + δ kt 10:Update D kt t+1 , N kt t+1 be used as an almost unbiased estimate of the demand at level δ k , sinceE[o t ] = E [1{ g(x t ) + δ k ≤ g(x t ) + ξ t }] = D(δ k + g(x t ) -g(x t )).Under Assumption 2, D is L ξ -Lipschitz, so the bias is of order L ξ ϵ. Then, relying on classical bandit techniques, we show that with high probability (for α small enough),|D(δ k ) -D k t | is of order L ξ ϵ + log(1/α) /N k t ,where D k t is the average of the observations o t when setting a price p t = g(x t ) + δ k , and N k t is the number of rounds in which we chose the price increment δ k up to round t. Importantly, to estimate D k t , we share information collected during all rounds we chose the increment δ k across all values of g(x t ); this is necessary to obtain better regret rates. Then, using p t D k t as an estimate of the reward π(x t , p t ) given the pricep t = g(x t ) + δ k , the error |π(x t , p t ) -p t D k t | is of order B y (L ξ ϵ + log(1/α) /N k t ).The PRICE ELIMINATION subroutine relies on the previous remark to select a price increment. For each increment δ k , we build a confidence bound[LCB t (δ k ), UCB t (δ k )] = [p t D k t ± B y (2L ξ ϵ + 2 log(1/α) /N k t )] for the reward of price p t = g(x t ) + δ k . Then, we use a successive elimination algorithm [13, 25] to select a good increment. More precisely, we consider increments δ k such that UCB t (δ k ) ≥ max l LCB t (δ l ), and we choose among these increments the increment δ kt that has been selected the least frequently. By doing so, we ensure to only select potentially optimal prices and gradually eliminate sub-optimal increments.Before discussing the application of the algorithmic scheme VAPE to linear and non-parametric valuation functions, we provide some intuition on regret bounds achievable through this scheme.Claim 1. (Informal) Let δ k = kϵ for k ∈ K ≜ ⌊ -By-1 /ϵ⌋, ⌈ By+1 /ϵ⌉ . Assume that, on a high- probability event, | g(x t ) -g(x t )| ≤ ϵ for every round t where PRICE ELIMINATION is conducted.Then, on a high-probability event, the regret of VAPE verifiesR T ≲ T VA (ϵ) + T ϵ + log(1/α)ϵ -2 .where T VA (ϵ) is a bound on the length of the VALUATION APPROXIMATION phase.Claim 1 is proved in the Appendix by combining Equations ( 4) and ( 5), and Lemma 4. We provide a sketch of proof below. To bound on regret of VAPE using Claim 1, it will suffice to bound the length of the VALUATION APPROXIMATION phase, and prove high-probability error bounds on g(x t ). Sketch of proof. Note that the regret in the VALUATION APPROXIMATION phase scales at most linearly with its length. Then, to prove Claim 1, it is enough to bound the regret during the PRICE ELIMINATION phase. We begin by bounding the sub-optimality gap of the price chosen at round t, showing that it is of order ϵ + log(1/α) /N k t t . To do so, for p ∈ R, we define ∆ t (x t , p) = max p ′ π(x t , p ′ ) -π(x t , p) the sub-optimality gap corresponding to price p. Recall that δ kt is the increment chosen at round t, i.e. that p t = g(x t ) + δ kt .Classical arguments from the bandit literature show that with high probability, for all k ∈ K, the upper and lower confidence bounds on π(x t , g(x t ) + δ k ) given by UCB t (δ k ) and LCB t (δ k ) are valid. Then, the optimal increment δ k * t defined by k * = arg max k∈At π(x t , g(x t ) + δ k ) belongs to the set of non-eliminated increments. Now, on the one hand, since UCB t (δ kt ) ≥ LCB t (δ k * t ), and since the confidence interval are valid, the gap π(x t , g(x t ) + δ k * t ) -π(x t , p t ) is of order ϵ + 2 log(1/α) /N k t t + 2 log(1/α) /N k * t t . Our round-robin sampling scheme ensures that N k * t t ≥ N kt t , so this bound is of order ϵ + log(1/α) /N k t t .On the other hand, our choice of grid {δ k } k∈K , together with the Lipschitz-continuity of the reward in Assumption 2, imply that the cost ∆ t (x t , g(x t ) + δ k * t ) of considering a discrete price grid is of order B y L ξ ϵ. Thus, at each round, the gap ∆ t (x t , g(x t )+δ kt ) is at most of order ϵ + log(1/α) /N k t t (up to problem-dependent constants). Now, let us decompose the regret of the PRICE ELIMINATION phase as follows:t∈PRICE ELIMINATION phase ∆(x t , p t ) = k∈K t:kt=k ∆(x t , p t ).In order to bound t:kt=k ∆(x t , p t ) for k ∈ K, we begin by introducing further notations. Let us denote τ k 1 , . . . , τ k T the rounds in the PRICE ELIMINATION phase where we choose k t = k. We also define ∆ a = 2 -a and a such that ∆ a ≈ ϵ. For all a ≤ a, we also define t a such that the bound ϵ + log(1/α) /ta is of order ∆ a . Then, our previous reasoning implies that if i ≥ t a for some a ∈ {1, a}, it must be that∆ t (x t , p τ k i ) ≤ ∆ a . Moreover, for a ≥ 1, each phase {t a , . . . , t a+1 } is of length approximately log(1/α)(∆ -2 a+1 -∆ -2 a ). Thus, t:kt=k ∆(x t , p t ) ≲ log(1/α) ∆ 1 + a-1 a=1 ∆ a × log(1/α) ∆ 2 a+1 - log(1/α) ∆ 2 a + ∆ a N k T .Using the definitions of ∆ a and a, we find that this sum is of order log(1/α)/ϵ + ϵN k T . We conclude by summing over the values of k ∈ K, using k∈K N k T ≤ T and the fact that |K| is of order ϵ -1 .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 in 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 crossreferenced. • 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 to 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. 
linear valuation functions: 
 In this section, we consider the linear valuation model, given byEQUATIONwhere θ ∈ R d is an unknown parameter. To ensure that the valuations are bounded, we assume the boundedness of the parameter θ. Assumption 3. The parameter θ is bounded: ∥θ∥ ≤ B θ Note that under Assumptions 1 and 3, the expected valuations g(x t ) verify |g(x t )| ≤ B g for B g = B x × B θ . Moreover, the random valuations verify a.s.|y t | ≤ B y for B y = B g + 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 θ. Moreover, we distinguish between phases by setting ι t = 1 if t belongs to the VALUATION APPROXIMATION phase and ι t = 0 if t 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 (1) and (3). Under Assumptions 1, 2, and 3, the regret of Algorithm VAPE for Linear Valuations with parametersϵ = ( d 2 log(T ) 2 /T ) 1 /3 , µ = ϵ / By d log 1+B 2 x T α +B θ , and α = 1 / T +2T 2 3+(B ξ +1)T 1 /3 verifies R T ≤ C B ξ ,Bx,B θ ,L ξ d 2 /3 T 2 /3 log(T ) 2 /3with probability 1 -T -1 , where C B ξ ,Bx,B θ ,L ξ is a constant that polynomially depends on B ξ , B x , B θ , and L ξ .[See Appendix B for the full proof] Using Claim 1, we see that it is enough to prove that the VALUATION APPROXIMATION phase allows to estimate g(x t ) up to precision ϵ = (d 2 log(T ) 2 /T ) 1 /3 in at most O(d 2 /3 T 2 /3 log(T ) 2 /3 ) rounds.Algorithm 2 VALUATION APPROXIMATION -PRICE ELIMINATION (VAPE) for Linear Valuations 1: Input: bounds B y and L ξ , parameters α, µ, ϵ.2: Initialize:θ 1 = 0 d , V 1 = I d , K = ⌈ (By+1) /ϵ⌉, K = -K, K , and for k ∈ K, N k 1 = D k 1 = 0. 3: while t ≤ T do 4: if ∥x t ∥ V -1 t > µ then ▷ Valuation Approximation 5:Post a price p t ∼ U([-B y , B y ])6:ι t ← 1, V t+1 ← s≤t ι s x s x ⊤ s + I d , θ t+1 ← 2B y V -1 t+1 s≤t ι s o s -1 2 x s 7:else ▷ Price Elimination 8:ι t ← 0, g t ← x ⊤ t θ t , A t ← {k ∈ K : g t + kϵ ∈ [0, B y ]} 9:for k ∈ A t do 10:UCB t (k) ← ( g t + kϵ) ( D k t + 2 log( 1 /α) N k t + 2L ξ ϵ) 11: LCB t (k) ← ( g t + kϵ) ( D k t -2 log( 1 /α) N k t -2L ξ ϵ) 12: K t ← {k ∈ A t : UCB t (k) ≥ max k ′ ∈At LCB t (k ′ )} 13:Choose k t ∈ arg min k∈Kt N k t and post a pricep t = g t + k t ϵ 14: Update D kt t+1 ← N k t t D k t t +ot N k t t +1 , N kt t+1 ← N kt t + 1.To prove the first part of the claim, note that for all rounds in the PRICE ELIMINATION phase,∥x t ∥ V -1 t ≤ µ = ϵ / By d log( 1+B 2 x T /α)+B θ . Then, | g(x t ) -g(x t )| ≤ ∥θ -θ t ∥ Vt ∥x t ∥ V -1 t ≤ ∥θ -θ t ∥ Vt × ϵ / By d log( 1+B 2 x T /α)+B θ .Classical result on ridge regression in bandit framework [1] show that on a large probability event,∥θ -θ t ∥ Vt ≤ B y d log 1+B 2 x T /α + B θ , so | g(x t ) -g(x t )| ≤ ϵ.To prove the second part of the claim, we rely on the elliptical potential lemma to bound the number of rounds where ∥x t ∥ V -1 t ≥ µ. This Lemma states that|G| i=1 ∥x ti ∥ V -1 t i -1 ≤ |G|d log ( |G|+d /d),where t i is the i-th round of the VALUATION APPROXIMATION phase, and |G| is its length. Using the fact that ∥x ti ∥ V -1t i -1 ≥ µ, we conclude that |G| ≤ d log( T +d /d) µ 2, which implies the result.Theorem 1 provides a regret bound of order Õ(T 2 /3 ), 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 T 2 /3 lower bound established in [31] for linear valuation functions and Lipschitz-continuous demand functions. This result represents a 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 Õ(T 3 /4 ) achieved respectively in [31] under assumptions slightly milder than ours, and in [14] under stronger assumptions.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 or not)?Answer: [Yes] Justification: The information needed to reproduce the experiment is detailed in Appendix A. 
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 is bounded. Furthermore, we assume that it is (L g , β)-Hölder continuous for some constants L g > 0 and 0 < β ≤ 1.Assumption 4. The valuation function g is (L g , β)-Hölder: for all(x, x ′ ) ∈ R d , |g(x) -g(x ′ )| ≤ L g ∥x -x ′ ∥ β .Under G x = ∅ for all x ∈ X , K = ⌈ By+1 /ϵ⌉, K = -K, K , and for k ∈ K, N k 1 = D k 1 = 0. 3: while t ≤ T do x t ← arg min x ′ ∈X ∥x t -x ′ ∥ 4: if |G xt | < τ then ▷ Price Elimination 5:Post a price p t ∼ U([-B y , B y ])6:G xt ← G xt ∪ {t}, g(x t ) ← 2By |Gx t | s∈Gx t o s -1 2 7:else ▷ Run Successive Elimination 8:g t ← g(x t ), A t ← {k ∈ K : g t + kϵ ∈ [0, B y ]} 9:for k ∈ A t do 10:UCB t (k) ← ( g t + kϵ) ( D k t + 2 log( 1 /α) N k t + 2L ξ ϵ) 11: LCB t (k) ← ( g t + kϵ) ( D k t -2 log( 1 /α) N k t -2L ξ ϵ) 12: K t ← {k ∈ A t : UCB t (k) ≥ max k ′ ∈At LCB t (k ′ )} 13:Choose k t ∈ arg min k∈Kt N k t and post a pricep t = g t + k t ϵ 14: Update D kt t+1 ← N k t t D k t t +ot N k t t +1 , N kt t+1 ← N kt t + 1.consider a minimal ( ϵ /3Lg) 1 /β -covering X of the ball of radius B x in R d , i.e. a finite set of points, of minimal cardinality, such that for any context x such that ∥x∥ ≤ B x , there exists a point in X at a distance at most ( ϵ /3Lg) 1 /β from x.At each round, we round the context x t to the closest context x in X by setting x t = arg min x ′ ∈X ∥x t -x ′ ∥, and acting as if we observed the context x t . If this context has not been observed sufficiently, we conduct a round of VALUATION APPROXIMATION: we sample a price uniformly at random and use it to update our estimate of g(x t ); otherwise, we proceed with the PRICE ELIMINATION phase. To distinguish between the VALUATION APPROXIMATION steps corresponding to contexts x ∈ X , we collect their indices in sets G x . The algorithm is presented in Algorithm 3. Theorem 2. Assume that the valuations follow the model given by Equation (1). Under Assumptions 1, 2, and 4, with probability 1 -T -1 the regret of Algorithm VAPE for non-parametric Valuations with parameters ϵ = ( T /log(T ))-β d+3β , α = T -4 , τ = 18B 2 y log( 2|X | /α) /ϵ 2, and X a minimal ( ϵ /3Lg) 1 /βcovering of the ball of radius B x verifiesR T ≤ C Bx,Bg,B ξ ,Lg,L ξ ,d,β T d+2β d+3β log(T ) β d+3β ,where C Bx,Bg,B ξ ,Lg,L ξ ,d,β is a constant that polynomially depends on B x , B g , B ξ , L g , L ξ , d, and β.[See Appendix C for the full proof] Using Claim 1, we only need to show that the length of the VALUATION APPROXIMATION phase is at most of order T d+2β /d+3β log(T ) β /d+3β and that w.h.p., it allows estimating g uniformly on a ball of radius B x with precision ϵ = ( T /log(T )) -β /d+3β .To prove the first part of the claim, we note that classical results imply that the size of a minimal covering of precision ϵ 1 /β of a ball in dimension d scales as ϵ -d /β . Then, the total length of the VALUATION APPROXIMATION phase is of order ϵ -d /β τ ≈ T d+2β /d+3β log(T ) β /d+3β . To prove the second part of the lemma, note that the Hölder-continuity of g and the definition of the ( ϵ /3Lg) 1 /βcovering G ensure that |g(x t ) -g(x t )| ≤ ϵ /3. Then, standard concentration arguments reveal that τ ≈ log(|X |/α)/ϵ 2 samples are sufficient to estimate g(x t ) with precision ϵ with high probability.Theorem 2 shows that the Algorithm VALUATION APPROXIMATION -PRICE ELIMINATION for non-parametric valuations enjoys a Õ(T d+2β /d+3β ) regret bound when the noise c.d.f. is Lipschitz and the valuation function Hölder-continuous. This result is 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(x) -a very strong assumption. However, this rate is higher than the Õ(T d+β /d+2β ) rates that are usually encountered in β-Hölder non-parametric bandits [7] . Thus, the question of optimality of the VAPE algorithmic scheme in the non-parametric valuation problem remains open. 
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 a noisy linear function and when expected valuations follow a smooth non-parametric model. In the linear case, our regret bounds are order-optimal, while in the non-parametric setting, we 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 Ω T 2 /3 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-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 Lipschitz-continuity of the noise (Assumption 2). Without this, even minor increases in the price could lead to a 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. It is of great interest to study problems where the noise distribution can change between rounds, or depends on the context. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: All the simulation can be (and were) run on a 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 or 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 as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The paper theoretically studies a 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The paper theoretically studies a well-established theoretical problem and the broader impact of our work is only due to the potential impact of advancements in this problem. As all pricing problems, dynamic pricing can have both positive and negative impacts -offering prices that are 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 it for 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., deployment 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 or unintentional) misuse of the technology. • If there are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 a 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 a 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]  
 
 Appendix: As all pricing problems, dynamic pricing can have both positive and negative impacts -offering prices that are 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. While acknowledging these issues, our work was meant to focus only on the theoretical analysis of what is considered a well-established problem in literature, leaving the study of these related topics as future work. Figure 2: 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 ∈ [1000, 1700, 3000, 5000] (left subplot), and T ∈ [1000, 1400, 4200, 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 area results invisible. The regret graph is in both cases plotted in logaritmic scale.In this section, we illustrate some numerical simulations that aim to show the empirical performance of our VAPE algorithm for Linear Valuations. Moreover we present a comparison 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://github.com/MatildeTulii1/ Improved-Algorithms-for-Contextual-Dynamic-Pricing VAPE In order to test our algorithm, we built a dataset of 5 contexts belonging to R 3 generated by a 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 a gaussian distribution truncated between -1 and 1 with mean 0 and variance 0.1. Similarly, also the parameter θ is a normalized vector initially drawn from a gaussian distribution. The algorithm has been tested on time horizons T ∈ [1000, 10000, 50000, 200000, 500000, 800000], and the hyperparameters α, µ, ϵ are set as in the statement of Theorem 1. Figure 1 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.Comparison with [14] Next we compare our algorithm with the algorithm proposed in Appendix F of [14] , in which they propose a routine to 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 it more fair both algorithm receive as input the time horizon T . In the stochastic case, similarly as before we consider a set of possible contexts in R 3 drawn uniformly at random and then normalised. During the routine, at each time step one of these is randomly selected. This method of receiving contexts meets the assumption included in [14] , making sure that no eigenvalue of the covariance matrix of the distribution of contexts is too small. As for the contexts, the parameter θ is selected ex-novo with every new run of the algorithm. We chose to implement a 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 a bandit approach, requires bigger time horizons to converge. The adversarial case, instead is a 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, z] and [0, 1, 0]. To make sure that the effect of this choice of contexts is not invalidated by the parameter θ, 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 to 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 .We state several lemmas before proving Theorem 1. We begin by bounding the length of the exploration phase corresponding to lines 5 and 6 of Algorithm 2. Lemma 1. Let G = {t ≤ T : ι t = 1}. Almost surely, the length of exploration phase G is bounded as|G| ≤ d log T +d d µ 2 .The following lemma bounds the error of our estimates for θ and D, for the values of µ prescribed in Theorem 1. Before stating the Lemma, we define the eventE = ∀t / ∈ G, | g t -g(x t )| ≤ ϵ, and D k t -D(kϵ) ≤ 2 log(1/α) N k t + L ξ ϵ .Lemma 2. The event E happens with probability at least 1 -(α + 2T 2 |K|α).Finally, we bound the number of times a sub-optimal price increment kϵ can be selected. For p ∈ R,x ∈ R d , we define ∆(x, p) = sup p ′ ∈[0,By] π(x, p ′ ) -π(x, p).Lemma 3. On the event E, for all t / ∈ G, if k t = k, then k must be such that∆(x t , g t + kϵ) ≤ B y 4 2 log(1/α) N k t + 9L ξ ϵ .We are now ready to bound the regret of Algorithm VAPE for Linear Valuations. We begin by rewriting the regret as R T = T t=1 max p∈[0,π(x t , p) -π(x t , p t ) ≤ |K| 512B y log(1/α) + 22 B y log(1/α) L ξ ϵ + 36B y T L ξ ϵ.Combining Equations ( 4), ( 6), and Lemma 4, we find thatR T ≤ B y d log T +d d B y d log BxT +1 α + B θ 2 ϵ 2 + |K| 512B y log(1/α) + 22 B y log(1/α) L ξ ϵ + 36B y T L ξ ϵ.Using the definition of K, ϵ and α allows us to conclude the proof.The proof of Theorem 2 follows closely the proof of Theorem 1. The following two Lemmas are analogues of Lemmas 1 and 2. Lemma 5. Let X be an ( ϵ 3Lg ) 1 /β -covering of B Bx,d of minimal cardinality, and letG = x∈X G x .Almost surely, the length of exploration phase G is bounded as|G| ≤ 2B x 3L g ϵ 1 /β + 1 d (τ + 1).Recall that we defined the event E asE = ∀t / ∈ G, | g t -g(x t )| ≤ ϵ, and D k t -D(kϵ) ≤ 2 log(1/α) N k t + L ξ ϵ .The following lemma shows that E happens with large probability. Lemma 6. The event E happens with probability at least 1 -(α + 2T 2 |K|α).The rest of the proof holds follows the proof of Theorem 1. In particular, on the event E, we still haveR T = t∈G max p∈[0,By] π(x t , p) -π(x t , p t ) + t / ∈G max p∈[0,By] π(x t , p) -π(x t , p t ) ≤ B y |G| + |K| 512B y log(1/α) + 22 B y log(1/α) L ξ ϵ + 36B y T L ξ ϵ.where we used the fact that the instantaneous regret is bounded by B y along with Lemma 4. Using Lemma 5, we obtainR T ≤ B y 2B x 3L g ϵ 1 /β + 1 d (τ + 1) + |K| 512B y log(1/α) + 22 B y log(1/α) L ξ ϵ + 36B y T L ξ ϵ.Using the definition of K, ϵ, τ and α allows us to conclude the proof.We use the elliptical potential Lemma (see, e.g., Proposition 1 in [8] ) to bound the total number of rounds used to estimate θ. Formally, denote the estimation indices G = t 1 . . . , t |G| and notice that ι t = 1 only for these indices. Thus, for all i ∈ [|G|], we can writeV ti = i k=1 x t k x ⊤ t k + I d and V ti-1 = V ti-1 .In particular, the elliptical potential lemma implies that|G| i=1 ∥x ti ∥ V -1 t i -1 = |G| i=1 ∥x ti ∥ V -1 t i-1 ≤ |G|d log |G| + d d .Since for all t such that ι t = 1,x ⊤ t V -1 ti-1 x t ≥ µ, this implies that |G|µ ≤ |G|d log |G| + d d .Now, almost surely, |G| ≤ T . Using this bound and reorganizing the inequality leads to the desired result|G| ≤ d log T +d d µ 2 .Lemma 2 is obtained by combining the following two results. Lemma 7. Let us define the eventE 1 = {∀t / ∈ G : |g(x t ) -g t | ≤ ϵ}Then, the event E 1 happens with probability at least 1 -α.The remainder of the proof follows from the following lemma. Lemma 8. Let us define the eventE = ∀t ∈ [T ], k ∈ K, D k t -D(kϵ) ≤ 2 log(1/α) N k t + L ξ ϵ ∩ E 1Assume that event E 1 holds with probability 1 -α. Then, the event E happens with probability at least 1 -(α + 2T 2 |K|α).We assume that t / ∈ G, that k t = k, and that N k t > 0 (otherwise the statement is 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 t / ∈ G, and all k ∈ A t ;LCB t (k) ≤ π(x t , g t + kϵ) ≤ UCB t (k). Moreover, k * t ∈ K t , where k * t ∈ arg max k∈At π(x t , g t + kϵ).On the event E, Lemma 9 implies thatπ(x t , g t + kϵ) ≥ LCB(k) = UCB(k) -(UCB(k) -LCB(k)). Since k * t ∈ A t , we have UCB t (k) ≥ LCB t (k * t ).This impliesπ(x t , g t + kϵ) ≥ LCB t (k * t ) -(UCB t (k) -LCB t (k)) = UCB t (k * t ) -(UCB t (k) -LCB t (k)) -(UCB t (k * t ) -LCB t (k * t )) ≥ π(x t , g t + k * t ϵ) -(UCB t (k) -LCB t (k)) -(UCB t (k * t ) -LCB t (k * t )) Thus, π(x t , g t + k * t ϵ) -π(x t , g t + kϵ) ≤ (UCB t (k) -LCB t (k)) + (UCB t (k * t ) -LCB t (k * t )) . Now, UCB t (k) -LCB t (k) = ( g t + kϵ) 8 log(1/α) N k t + 4L ξ ϵ ≤ B y 8 log(1/α) N k t + 4L ξ ϵ since k ∈ A t .Moreover, since k t = k, and since k * t ∈ K t by Lemma 9, we know thatEQUATIONNext, we bound the discretization error using the following Lemma. Lemma 10. On the event E, we have thatsup p∈[0,By] π(x t , p) -π(x t , g t + k * t ϵ) ≤ B y L ξ ϵ.By Lemma 10, Equation (7) implies that on the event E,∆(x t , g t + kϵ) ≤ B y 4 2 log(1/α) N k t + 9L ξ ϵ .Note thatEQUATIONWe bound this term on the high-probability event E. For k ∈ K, we definet k 1 < • • • < t k N k T +1the rounds where t / ∈ G and k t = k. We split these rounds into episodes as follows. We define a = ⌊-log 2 (18L ξ ϵ)⌋. For a ∈ 1, a , we also definet a = 128 log(1/α) 2 -2a .With these notations, we havet / ∈G:kt=k ∆(x t , g t + kϵ) = i≤t1∧N k T +1 ∆(x t k i , g t k i + kϵ) + a-1 a=1 ta∧N k T +1 <i≤ta+1∧N k T +1 ∆(x t k i , g t k i + kϵ) + ta∧N k T +1 <i≤N k T +1 ∆(x t k i , g t k i + kϵ)On the one hand, ∆(x t , p t ) ≤ B y for all t ≤ T , soi≤t1∧N k T +1 ∆(x t k i , g t k i + kϵ) ≤ B y t 1On the other hand, using Lemma 3, we see that on the event E, if i ≥ t a and a ∈ 1, a ,∆(x t k i , g t k i + kϵ) ≤ B y   4 2 log(1/α) t a + 9L ξ ϵ   ≤ B y 2 -a 2 + 9L ξ ϵ Since 2 -a ≥ 18L ξ ϵ, this implies that ∆(x t k i , g t k i + kϵ) ≤ 2 -a B y . Then, a-1 a=1 ta∧N k T +1 <i≤ta+1∧N k T +1 ∆(x t k i , g t k i + kϵ) ≤ B y a-1 a=1 (t a+1 -⌈t a ⌉ + 1) 2 -a ≤ B y a-1 a=1 (t a+1 -t a ) 2 -a + B yBy definition of t a , this implies thata-1 a=1 ta∧N k T +1 <i≤ta+1∧N k T +1 ∆(x t k i , g t k i + kϵ) ≤ 128B y log(1/α) a-1 a=1 2 2a+2 -2 2a 2 -a + B y ≤ 384B y log(1/α) 1 + a-1 a=1 2 a ≤ 384B y log(1/α)2 a ≤ 22 B y log(1/α) L ξ ϵwhere we used that 2 a ≤ 1 18L ξ ϵ . Similarly,ta∧N k T +1 <i≤N k T +1 ∆(x t k i , g t k i + kϵ) ≤ 2 -a B y N k T +1 ≤ 36B y N k T +1 L ξ ϵ.Combining these results, we find that t / ∈G:kt=kEQUATIONWe conclude the proof by summing over k ∈ K, and using the fact that k∈K N k T +1 ≤ T .We note that |G| ≤ |X |(τ + 1).We conclude by using classical results on covering number of the ball (see, e.g., Corollary 4.2.13 in [29] ), stating that there exists an ( ϵ 3Lg ) 1 /β -covering of the ball of radius B x in dimension d of cardinality at most 2B x 3Lg ϵ1 /β + 1 d .The proof of Lemma 6 relies on the following Lemma. Lemma 11. Let us define the eventE 1 = {∀t / ∈ G : |g(x t ) -g(x t )| ≤ ϵ}Then, the event E 1 happens with probability at least 1 -α.Note that Lemma 8 still holds for non-parametric valuations. This concludes the proof of Lemma 6.We introduce the variablesxt = ι t x t and ỹt = 2B y ι t o t - 1 2and the σ-algebra F t = σ ((x s ) s≤t+1 , (o s ) s≤t ) . Since V t-1 and x t are F t-1 -measurable, then so does ι t , and thus both xt+1 and ỹt are F t -measurable. Moreover, for any round where ι t = 1, the price is chosen uniformly at random and we haveE [ỹ t |F t-1 ] = ι t × 2B y By -By P [u ≤ y t |F t-1 ] du 2B y -B y = ι t × By -By B ξ -B ξ 1 u ≤ x ⊤ t θ + ξ f (ξ) dξ du -B y = ι t × B ξ -B ξ ξ+x ⊤ t θ -By duf (ξ) dξ -B y = ι t × x ⊤ t θ + B ξ -B ξ ξf (ξ) dξ = ι t × x ⊤ t θwhere in the last equality we used thatB ξ -B ξ ξf (ξ) dξ = E [ξ t ] = 0.The same relation also trivially holds when ι t = 0. Thus, conditionally on F t-1 , ỹt -x⊤ t θ is centered and in [-B y , B y ], which implies that it is B y -subgaussian. Now, for all t ≤ T , we haveθ t = 2B y s<t ι s x s x ⊤ s + I d -1 s∈G o s - 1 2 x s = s<t xs x⊤ s + I d -1 s<t ỹs xs .Using the fact that for all t ≥ 1, ∥x t ∥ ≤ B x , and that ∥θ∥ ≤ B θ , and applying Theorem 2 in [1] , we find that for all t ≥ 0, with probability 1 -α,∥ θ t -θ∥ ( s<t xl x⊤ l +I d ) ≤ B y d log 1 + B 2 x T α + B θ .Note that our definitions of xt and ỹt ensure that∥ θ t -θ∥ ( s<t xl x⊤ l +I d ) = ∥ θ t -θ∥ Vt . Moreover, for all t, |x ⊤ t ( θ t -θ)| ≤ ∥x ⊤ t ∥ V -1 t ∥ θ t -θ∥ Vt . In particular, if t / ∈ G, ∥x ⊤ t ∥ (Vt) -1 ≤ µ, so |x ⊤ t ( θ t -θ)| ≤ µ B y d log 1 + B 2 x T α + B θ .The conclusion follows from the choice ϵ = µ B y d log1+B 2x T α + B θ , and the fact thatg t = x ⊤ t θ t .We rely on the following well-known result (we provide proof in the appendix for the sake of completeness). Lemma 12. Let (y t ) t≥1 be a sequence of random variables adapted for a filtration F t , such thaty t -E [y t |F t-1 ] ∈ [m, M ]. Assume that for t ∈ N * , ι t ∈ {0, 1} is F t-1-measurable, and defineN t = s≤t ι s , and µ t = s≤t ιs(ys-E[ys|Fs-1]) Nt if N t ≥ 1.Then, for any t ∈ N * and α ∈ (0, 1),P   N t = 0 or | µ t | ≤ (M -m) log(1/α) 2N t   ≥ 1 -2tα.Moreover, for any l > 0 and α ∈ (0, 1),P   N t = l and | µ t | ≥ (M -m) log(1/α) 2N t   ≤ 2α.Note Lemma 8 holds trivially for all t such that N k t = 0. Therefore we assume w.l.o.g. that N k t ≥ 1 (otherwise the statement is trivial). For any such given t ∈ [T ], we control the error | F k t -F (kϵ)| uniformly for k ∈ K. To do so, we rely on Lemma 12; we define ιt = 1 {ι t = 0 and k t = k}, and note that forF t = σ ((x 1 , . . . , x t+1 ), (o 1 , . . . , o t )), ιt is F t-1 -measurable, and o t is F t adapted. Moreover, ιt E [o t |F t-1 ] = ιt P (g(x t ) + ξ t ≥ g t + kϵ) = ιt D ( g t -g(x t ) + kϵ) ,and directly by definition, it holds that D k t = s≤t ιtot. Using Lemma 12, we find that with probability 1 -2αt, N k t = 0 orD k t - s≤t ιt D ( g t -g(x t ) + kϵ) N k t ≤ 2 log(1/α) N k t .Moreover, on the event E 1 , which happens w.p. at least 1 -α, for all t / ∈ G, | g t -g(x t )| ≤ ϵ. Using the fact that D is L ξ -Lipschitz, we find that for all t / ∈ G,|D ( g t -g(x t ) + kϵ) -D (kϵ) | ≤ L ξ | g t -g(x t )| ≤ L ξ ϵ.Thus, with probability 1 -2αt,D k t -D(kϵ) ≤ 2 log(1/α) N k t + L ξ ϵ.Using a union bound over all k ∈ K and t ∈ [T ] and then intersecting with E 1 using another union bound yields the desired result.For any t / ∈ G, denoting p t (k) = g t + kϵ, we first rewriteπ(x t , p t (k)) = E[p t (k)1{p t (k) ≤ y t }|p t (k), x t ] = p t (k)E[1{p t (k) ≤ g(x t ) + ξ t }|p t (k), x t ] = p t (k)D(p t (k) -g(x t )) = ( g t + kϵ)D( g t -g(x t ) + kϵ) = ( g t + kϵ) D k t + ( g t + kϵ) D( g t -g(x t ) + kϵ) -D k t .Since the event E holds, the following hold for all t / ∈ G and k ∈ A t :EQUATIOND k t -D(kϵ) ≤ 2 log(1/α) N k t + L ξ ϵ.In particular, we have that:D( g t -g(x t ) + kϵ) -D k t ≤ |D( g t -g(x t ) + kϵ) -D(kϵ)| + D(kϵ) -D k t (1) ≤ L ξ | g t -g(x t )| + D(kϵ) -D k t ≤ L ξ ϵ + 2 log(1/α) N k t + L ξ ϵ = 2 log(1/α) N k t + 2L ξ ϵ Relation (1) holds since D is L ξ -Lipschitz and (2) is under the event E for all t / ∈ E. As the set A t is chosen such that g t + kϵ ≥ 0 for all k ∈ A t , it implies that π(x t , g t + kϵ) -( g t + kϵ) D k t ≤ ( g t + kϵ) 2 log(1/α) N k t + 2L ξ ϵ .Reorganizing, we get for all k ∈ A t and t / ∈ GLCB t (k) ≤ π(x t , g t + kϵ) ≤ UCB t (k).which proves the first part of the statement. Now let k * t ∈ arg max k∈At π(x t , g t + kϵ). By the first part of the claim, it holds thatUCB t (k * t ) ( * ) ≥ π(x t , g t + k * t ϵ) = max k∈At π(x t , g t + kϵ) ( * ) ≥ max k∈At LCB t (k),where relations ( * ) are due to the first part of the lemma; this proves that k * t ∈ K t .The proof follows by noticing that, on the one hand, K ensures that for all p ∈ [0, B y ], there exists k ∈ K such that g t + kϵ ∈ [0, B y ] and | g t + kϵ -p| ≤ ϵ. On the other hand, the prices considered are bounded by B y , and the demand function D is L ξ -Lipschitz, so the reward function π is B y L ξ -Lipschitz.For x ∈ X , let us define recursively the variables ι x 1 = 1 {x 1 = x}, and for t > 1, ι x t = 1 x t = x, and s<t ι x s < τ , and define the variablesgx t = ι x t g(x t ) and ỹx t = 2B y ι x t o t - 1 2and the σ-algebra F t = σ ((x s ) s≤t+1 , (o s ) s≤t ) . Note that ι x t is F t-1 -measurable, and thus both xt+1 and ỹt are F t -measurable. Moreover, for any round where ι x t = 1, the price is chosen uniformly at random and we have EQUATIONP   ∃t / ∈ G x : s∈G x ,s<t ỹx t -gx t N x t ≥ 2B y log(2|X |/α) 2⌈τ ⌉   ≤ P   N x t = ⌈τ ⌉ and s∈G x ,s<t ỹx t -gx t N x t ≥ 2B y log(2|X |/α) 2⌈τ ⌉   ≤ α |X | .Moreover, since g is (L g , β)-Holdercontinuous, and ∥x t -x t ∥ ≤ ( ϵ 3Lg ) 1 /β a.s., we have|g(x t ) -gx t | ≤ L g • ϵ 3L g 1 /β β = ϵ 3 .Then, with probability at least 1-α /|X |, for all t / ∈ G x , | g(x t ) -g(x t )| ≤ 2B y log(2|X |/α) 2⌈τ ⌉ + ϵ 3 ≤ 2ϵ 3 .where we used τ = . Using a union bound over X , we find that with probability at least 1 -α, for all t / ∈ G x ,| g(x t ) -g(x t )| ≤ 2ϵ 3 .Similarly, for all t / ∈ G, ∥g(x t ) -g(x t )∥ ≤ L g ϵ 3Lg . Then, we have that with probability 1 -α, for all t / ∈ G x , | g(x t ) -g(x t )| ≤ ϵ.Let us define Z t = s≤t ι s (y s -E [y s |F s-1 ]), and for x ∈ R, M t = exp xZ t -x 2 (M -m) 2 Nt. We begin by showing that M t is a super-martingale. Indeed, we have thatE e xιt(yt-E[yt|Ft-1]) F t-1 = E ι t e x(yt-E[yt|Ft-1]) + (1 -ι t ) F t-1 ≤ ι t e x 2 (M -m) 2 8 + (1 -ι t )≤ ex 2 (M -m) 2 ι t 8.where we use the fact that (y t -E [y t |F t-1 ]) is bounded in [m, M ] together with the conditional version of Hoeffding's Lemma. Noticing thatM t = M t-1 e xιt(yt-E[yt|Ft-1])-x 2 (M -m) 2 ι t 8 ,this proves that M t is a super-martingale, and soE [M t ] ≤ E [M 0 ] = 1.Now, for all ϵ > 0 and all l ∈ N, and all x > 0, by a Markov-Chernoff argument,P (Z t ≥ ϵ and N t = l) = P 1 {N t = l} e xZt ≥ e ϵx ≤ e -ϵx E e xZt 1 {N t = l} = e -ϵx+ x 2 (M -m) 2 l 8 E e xZt-x 2 (M -m) 2 l 8 1 {N t = l} .Using the previous result, we have thatE e xZt-x 2 (M -m) 2 l 8 1 {N t = l} = E e xZt-x 2 (M -m) 2 N t 8 1 {N t = l} ≤ E e xZt-x 2 (M -m) 2 N t 8 = E(M t ) ≤ E(M 0 ) = 1. so P (Z t ≥ ϵ and N t = l) ≤ e -ϵx+ x 2 (M -m) 2 l 8 .In particular, for ϵ = (M -m) l•log(1/α)2 and x = 4ϵ l(M -m) 2 , P Z t ≥ (M -m) l • log(1/α) 2 and N t = l ≤ α.This proves the first part of the Lemma. Summing over the values of l from 1 to t, we find thatP Z t ≥ (M -m) N t log(1/α) 2 and N t ≥ 1 ≤ tα.Similar arguments can be used to prove thatP -Z t ≥ (M -m) N t log(1/α) 2 and N t ≥ 1 ≤ tα.Noting that Z t = μt N t and normalizing by N t (and since adding the case N t = 0 can only increase the probability) concludes the proof of the Lemma.NeurIPS Paper Checklist• 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 a 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 a specific model and empirical evaluation, it may be necessary to either make it 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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./3 K ), where 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The 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.

2, 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. 

If this is not applicable, the authors are encouraged to explain in the rebuttal how the "Half-Lipschitz" nature does not work.



References:

Xu, 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.

Luo, 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.

Fan, 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.
questions: questions: The authors are encouraged to respond to the following questions at a secondary priority (i.e. after kindly answering my questions in "Weaknesses").

1, 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?

2, 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - A paper with such practical motivation would benefit greatly from being accompanied by a thorough experimental campaign.

- See questions below.
questions: 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?

- 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: limitations: No limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Another 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.

[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.
questions: 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: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: I think for me, the most limiting assumption is that the noise is i.i.d. across all contexts, which the authors also mentioned. 

It may not be possible to add experiments now, but I think it will be helpful for this paper.
questions: 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? 

This 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: limitations: Yes.

Comments: title: Thanks for your response
Thank you for the clarifications
comment: The reviewer thanks the authors for your insightful and exhaustive reply. For the comparison with [1], I somewhat agree that it is suboptimal to have a linear bandit algorithm, while yours are optimal. However, as I asked in Q1, by replacing your policy-elimination stage with a UCB, the algorithm is on the one hand optimal enough and on the other hand closer to their algorithmic design. However, since you are anyways the first to achieve optimal, and given that [1] had been accepted for Neurips 2022, I would like to support the acceptance of your paper.

For the difference of assumptions comparing to [2], I am still skeptical if their half-lipschitzness is not applicable. In other words, I am not sure whether you really need $F(\delta) \approx F(\delta \pm \epsilon)$ which is stronger than it appears for a $T^{2/3}$ regret bound. For the estimates of $F$ and its difference with [3], I tend to believe that there are no substantial difference between (poly) kernels and discretizations. But I am happy to leave them for discussions beyond this paper.
Thank you for your response. It addresses my concerns and I have raised the score.
Thank you for the clarifications. I have no further questions. I increased my score to 6.