Learning to Price Homogeneous Data

Authors: keran  chen
joon suk huh
kirthevasan  kandasamy
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 23:55:24

Abstract: We study a data pricing problem, where a seller has access to $N$ homogeneous data points (e.g. drawn i.i.d. from some distribution).
There are $m$ types of buyers in the market, where buyers of the same type $i$ have the same valuation curve $v_i:[N]\rightarrow [0,1]$, where $v_i(n)$ is the value for having $n$ data points.
*A priori*, the seller is unaware of the
distribution of buyers, but can repeat the market for $T$ rounds so as to learn the revenue-optimal pricing curve $p:[N] \rightarrow [0, 1]$.
To solve this online learning problem,
we first develop novel discretization schemes to approximate any pricing curve.
When compared to prior work,
the size of our discretization schemes scales gracefully with the approximation parameter, which translates to better regret in online learning.
Under assumptions like smoothness and diminishing returns which are satisfied by data, the discretization size can be reduced further.
We then turn to the online learning problem, 
both in the stochastic and adversarial settings.
On each round, the seller chooses an *anonymous* pricing curve $p_t$.
A new buyer appears and may choose to purchase some amount of data.
She then reveals her type *only if* she makes a purchase.
Our online algorithms build on classical algorithms such as UCB and FTPL, but require novel ideas to account for the asymmetric nature of this feedback and to deal with the vastness of the space of pricing curves.
Using the improved discretization schemes previously developed, we are able to achieve 
$\widetilde{O}(m\sqrt{T})$ regret in the stochastic setting and $\widetilde{\mathcal{O}}(m^{3/2}\sqrt{T})$ regret in the adversarial setting.

Main paper: 
 introduction: 
 Due to the rise in popularity of machine learning, there is an increased demand for data. However, not all users of data have the wherewithal to collect data on their own, and have to rely on data marketplaces to acquire the data they need. For example, a materials data platform (e.g. [18] ), may have collected vast amounts of data from various proprietary sources. Materials scientists in smaller organizations and academia, who do not have large experimental apparatuses, may wish to purchase this data to aid in their research. Similarly, small businesses may wish to purchase customer data for advertising and product recommendations [4, 5] , while small technology companies may wish to purchase data about cloud operations to optimize their computing infrastructure [2, 3] .Model. Motivated by the emergence of such data marketplaces, we study the following online data pricing problem. A seller has access to N homogeneous data points, (e.g. drawn i.i.d. from some distribution). He wishes to sell the data to a sequence of distinct buyers over T rounds, and intends to achieve large revenue. There are m types of buyers in the data marketplace, with all buyers in type i having the same valuation curve v i : [N ] → [0, 1] for the data, where v i (n) represents the buyer's value for having n points. As data is homogeneous, we can treat an agent's value as a function of the amount of data n (we will illustrate this in the sequel). Valuation curves are monotone non-decreasing, as more data is better. At each round t, the seller chooses a price curve p t : [N ] → [0, 1], where p t (n) is the price for purchasing n data points. Then, a buyer with type i t arrives and purchases an amount of data that maximizes her utility (value minus price), provided that she can achieve non-negative utility. A buyer will reveal her type to the seller only if she makes a purchase, and only after she makes the purchase. The seller has knowledge of valuation curves of the m types, but does not know the distribution q over types (stochastic setting), or the buyer sequence (adversarial setting). Moreover, he cannot practice non-anonymous (discriminatory) pricing, as he needs to choose the pricing curve p t without knowledge of the buyer's type on that round.While there is extensive research on revenue-optimal pricing and learning to price, data marketplaces merit special attention, both due to their recent emergence and the unique characteristics of data. Typically the number of data N (number of goods) is very large, but data usually satisfies additional properties such as smoothness (an agent's value does not increase significantly with a small amount of additional data) and diminishing returns (additional data is more valuable when a buyer has less data). To illustrate further, note that two steps are essential to develop an effective online learning solution for data pricing. (1) First, we need to solve the planning problem, i.e. find a revenue-optimal pricing curve when the type distribution q is known. (2) Second, when q is unknown, we need to combine the algorithm in step (1) with estimates for q to maximize long-term revenue.Methods in the existing literature fall short in both steps. (1) When the type distribution q is known, the data pricing problem resembles an ordered item pricing problem, which is known to be NP-hard [13, 25] . Hence, prior work has aimed at approximating the optimal pricing curves via discretization schemes. Unfortunately, existing discretization schemes have poor, often exponential, dependence on the approximation parameter ϵ. However, achieving sublinear regret in online learning requires choosing ϵ that vanishes with longer time horizons, i.e. ϵ → 0 as T → ∞. Therefore, directly using existing discretization schemes in an online setting leads to poor statistical and computational properties of the associated online algorithm. This requires us to leverage the above properties of data to design discretization schemes with better dependence on ϵ. (2) While there is prior work on learning optimal prices [22, 27, 33] , these techniques either fall short of addressing the complexities in our setting, or fail to account for the properties of data, and hence do not scale gracefully when the amount of data N is very large. Moreover, in our online learning setup, the seller faces a trade-off between setting high prices to maximize instantaneous revenue versus setting low prices so as to guarantee a purchase, which results in the buyer revealing their type, which in turn can be helpful in future rounds. Prior work has studied this asymmetric feedback model only in single-item markets which is significantly simpler, and only in the stochastic setting [23, 47] .Our contributions in this work are threefold: (1) First, in §3, we develop discretization schemes for revenue-optimal data pricing under a variety of assumptions, which we will use later in our online learning schemes. (2) In §4, we study learning a revenue-optimal price in a stochastic setting, where the customer types on each round are drawn from a fixed but unknown distribution q. (3) Finally, in §5, we study online learning when the buyer types are chosen by an oblivious adversary.1. Discretization (approximation) schemes for revenue-optimal data pricing. Assuming only monotonicity, we show that there is a discretization of size O((N/ϵ) m ) which is an O(ϵ) additive approximation to any pricing curve. When compared to prior work [14, 25] , our discretization scheme has smaller dependence on ϵ -1 when the number of types m is small (see Table 1 ). This will be useful, both statistically and computationally, when we study the online setting, as we need to choose ϵ → 0 as T → ∞ to achieve sublinear regret. This is still quite large in real-world data marketplaces, where N may be very large. Hence, we also study two other assumptions. First, when valuations are smooth, satisfying an L-Lipschitz-like condition, we construct a discretization of size O (L/ϵ 2 ) m , which has no dependence on N . Next, under a diminishing returns condition, we construct a discretization of size O J m ϵ -3m log m (N ) , which only has polylogarithmic dependence on N . Key insights. We first show that when there are only m types, for any price function p : [N ] → [0, 1], there exists an "m-step" price function p ′ whose revenue is at least as much as that of p on any type distribution q. An m-step function is non-decreasing and changes values at most m times, allowing us to focus on this restricted class and thereby reduce the search space when m ≪ N . We then consider discretizations of the data space [N ] and valuations [0, 1] which allow us to obtain an O(ϵ)-approximation to any pricing curve, and then apply this insight to construct our discretizations. Finally, we show that with monotonicity and diminishing returns, similarly accurate approximations are attainable with substantially coarser discretizations.2. Learning to price in the stochastic setting. Next, we turn to the online learning problem described in the beginning in a stochastic setting. On each round, our algorithm computes an 3. Learning to price in the adversarial setting. We study learning in an adversarial setting where the types on each round may be chosen adversarially. Table 2 shows the regret and time complexity of our method when paired with various discretization schemes. In the adversarial setting, our discretization schemes offer both computational and statistical advantages compared to prior work. Key insights. Our algorithm builds on the Follow-the-Perturbed-Leader (FTPL) [31] , originally designed for full-information settings and not directly applicable here. To handle asymmetric feedback, we use the information we have about the valuation curves to keep track of which customers would not have made a purchase given a price curve. If a purchase is made and we observe feedback, we use the usual FTPL update, but if not, we reward each pricing curve with the sum of revenue of all types that would not purchase in that current round.Dynamic pricing. The online posted-price mechanism, also known as dynamic pricing, is a central research area in algorithmic market design [19, 33] . In the most classical setting [33] , the seller sets a price for an item in each round, and a buyer purchases the item only if their valuation exceeds the posted price. While several extensions of this setting have been explored for both parametric [12, 20, 28, 29, 32, 46] and non-parametric [11, 17, 39, 40, 44] demands, most focus on single-parameter demands, i.e., selling a single item to buyers. Our data pricing problem is multi-parameter, as demands are parameterized by multiple outcomes, i.e. the number of data points.Bayesian unit-demand pricing problem. Formally, our data pricing problem is a variant of the Bayesian Unit-demand Pricing Problem (BUPP) [13] . BUPP addresses the problem of (offline) revenue maximization over a known distribution of unit-demand buyers, meaning they want to buy atStochastic M, F O m √ T O N m m T m /2 M, F, S O ((LT ) m ) Theorem 4.1 M, F, D O(J m T 3m /2 ) Adversarial M, F O m 3 /2 √ T O N m m T m /2 M, F, S O ((LT ) m ) Theorem 5.1 M, F, D O J m T 3m /2Discretization method Assumptions Complexity per iteration Regret (Adversarial) 1 for a description of the assumptions. All methods, including [14, 25] achieve O(m √ T ) regret in the stochastic setting.[25] F O(2 N ϵ -N ) O(m √ T N ) Chawla et al. [14] M, F N O(ϵ -2 log ϵ -1 ) O mT 3 /4most one item from the inventory. In BUPP, a seller has N distinct items to sell to a unit-demand buyer whose valuations are v = (v 1 , . . . , v N ), where v i is the value of the ith item. Given prices p i , i ∈ [N ], the unit-demand buyer purchases a single item i ∈ [N ] that maximizes their utility: v i -p i . Assuming the valuation profile v follows a known distribution D, the goal of BUPP is to find the best prices {p i } i∈[N ] that maximize the seller's expected revenue.Our data pricing problem is a variant of BUPP in two ways: (1) We study the sequential setting where type distributions are unknown, while valuation profiles for each type are known, and (2) We assume monotonic values v 1 ≤ • • • ≤ v N , which is natural in data pricing. Unfortunately, BUPP is a computationally intractable problem, as is ours. BUPP is known to be NP-hard even when D is a product distribution [16] . Moreover, even assuming that values are monotonic (i.e.,v 1 ≤ • • • ≤ v N ),the problem remains (strongly) NP-hard [14] . Therefore, we aim to provide a reasonably efficient no-regret algorithm for our problem, especially when the number of types m is a fixed constant.The previous works most relevant to our paper are Hartline and Koltun [25] and Chawla et al. [14] , which study offline revenue maximization for unit-demand buyers. Buyers in our problem are also unitdemand, as each amount of data points can be seen as an individual item. Revenue maximization for unit-demand buyers is known to be computationally intractable [24] , even with ordered (monotonic) buyer values [14] , leading these works to focus on approximation algorithms. Hartline and Koltun [25] proposed an approximation algorithm with near-linear runtime in the number of buyers, given a fixed number of items. Chawla et al. [14] introduced a polynomial-time approximation scheme (PTAS) for unit-demand buyers with monotonic values. In this work, we extend the framework to the online setting with partial feedback, which has more practical implications.In addition, Balcan and Beyhaghi [10] provide new guarantees for learning revenue-maximizing menus of lotteries and two-part tariffs, demonstrating that their discretization technique yields efficient solutions for specific pricing models. Similar discretization methods could be investigated in future work to potentially improve our approach in more complex data pricing scenarios.Market design for data-sharing. In recent years, there has been a plethora of work devoted to algorithmic market design for data sharing [6, 7, 30, 43] . These works provide ingenious solutions to challenges unique to the data market, such as free replicability and the difficulty of valuation due to the combinatorial nature of data. Except for Agarwal et al. [6] , the above-cited solutions are inherently offline or single-shot. While we focus on a simplified yet relevant setting where data comes from a single source, resulting in monotonic valuations, in this work, we tackle the problem in a sequential, dynamic setting, which has practical importance. In contrast to our approach, Agarwal et al. [6] considered the price to be a constant (i.e., a scalar rather than a price vector) to address the inherent computational intractability of multi-dimensional pricing. Instead, we maintain the price as a vector (i.e., a price function) but focus on cases where the valuation function satisfies natural properties such as monotonicity, smoothness, and diminishing returns. (n) = v i (n) -p(n).If a buyer can achieve non-negative utility, i.e. v i (n) ≥ p(n) for some n ∈ [N ], she will purchase an amount of data to maximize her utility. To fully specify the buyer's purchase model, we will assume that when there are multiple n which maximizes her utility, she will choose the largest such n. Formally, for a given pricing curve p, a buyer of type i will purchase n i,p points where,n i,p ∆ = 0 if v i (n) < p(n) for all n ∈ [N ], max argmax n∈[N ] (v i (n) -p(n))otherwise.(EQUATIONOptimal revenue. It follows that the revenue from a buyer of type is p(n i,p ). Let q = (q 1 , . . . , q m ) be the distribution of the buyers. Under this distribution q, the expected revenue rev(p) for a price curve p, the optimal price p OPT , and the optimal revenue OPT as follows:EQUATIONWe have omitted the dependence on q in rev, p OPT , and OPT. There is no closed-form solution to finding the optimal pricing curve, even when q is known. Therefore, in §3, we explore discretization methods to approximate p OPT , which will then be used in §4 and §5 to develop online learning algorithms. Unfortunately, the size of this discretization can be very large in N and m without further assumptions. Therefore, we also consider two additional commonly satisfied conditions by data.Our first such assumption states that buyer valuation curves satisfy a Lipschitz-like smoothness condition with Lipschitz constant L/N . We use L/N instead of L since the number of data has a range [0, N ], while the valuations only have a range [0, 1]. This condition states that a buyer's valuation does not change significantly if she only purchases a few additional points. Assumption 1 (Smoothness, S). For all n, n ′ ∈ [N ], we havev i (n + n ′ ) -v i (n) ≤ L N n ′ .Our second condition is based on the fact that data typically exhibits diminishing returns [34, 35] . This means that an additional data point is more valuable when there is less data, i.e. v i (n + 1) -v i (n) is decreasing with n. We will in fact make a stronger assumption, and justify it below. Assumption 2 (Diminishing returns, D). There exists some J > 0 such that, for all types i ∈ [m], and for all n ∈ [N ], we havev i (n + 1) -v i (n) ≤ J n .Assumption 2 quantifies the rate of decrease of diminishing returns. Following Example 1, the valuation (accuracy) curves for many learning problems take the form v i (n) = α -βn -γ ; for instance, for binary classification in a VC class H, α may be the best accuracy in H, β ∈ O( √ d H ) where d H is the VC dimension, and γ = 1/2 [41] ; similarly, for nonparametric regression of a twice differentiable function, α and β are constants while γ = 2/5 [45] . In such cases, Assumption 2 is satisfied with J = βγ. Note that neither assumption subsumes the other: a non-concave Lipschitz function will not satisfy Assumption 2, while a suitable L for a function which satisfies Assumption 2 may need to be very large for Assumption 1 to hold for small n. 
learning to price in online settings: 
 In this work, we will also study how a seller may learn to maximize revenue. In our learning problem, the seller is aware of the valuation curves {v i } i of each type, but does not know the distribution of types (stochastic setting) or there may be no such distribution (adversarial setting).Setup. The seller repeats the data market for T rounds. At the beginning of each round, he chooses some price curve p t ∈ P. After the seller has chosen p t , a new buyer of type i t ∈ [m] appears and purchases n t = n it,pt amount of data (see (1) ). The buyer is aware of her own valuation curve. If she makes a purchase, that is if n t > 0, she pays p t (n t ) to the seller and reveals her type i t . Otherwise, the buyer will make no payment and not reveal her type.We have assumed that a priori, the seller is aware of the buyer valuation curves {v i } i∈[m] , and that buyers are aware of their own valuation curves. In Example 1, a seller can profile how different machine learning models perform with different amounts of data and publish them ahead of time. The buyers can also gauge their value from these curves, even though they do not have access to the data. Next, we have also assumed that buyers will reveal their type after the purchase. In modern machine learning as a service platforms [1, 4, 18] , buyers directly run their jobs in the seller's computing platform, so the seller can observe the buyers job type directly. Even if this is not the case, sellers can elicit this information via questionnaires and reviews from customers who have made a purchase [23] .Challenges. Despite these assumptions, the learning problem remains challenging for two main reasons. First, the space of price curves is vast: discretizing the valuations in [0, 1] into K bins, still leaves O(K N ) possible price curves, which is both statistically and computationally intractable, especially for large N . Second, in addition to the exploration-exploitation trade-off usually encountered in sequential decision-making, the seller faces a tension between high instantaneous revenue and information acquisition: setting high prices can yield high immediate revenue if a purchase occurs, but it also increases the risk of no purchase, resulting in no revenue and crucially no feedback about the buyer type which could help him in future rounds. This trade-off was recently studied for single-item markets in a stochastic setting [23, 47] , but is more complex in our multi-item problem. Moreover, to our knowledge, no existing work addresses this asymmetric feedback model in an adversarial setting, even for single-item markets. Next, we describe the buyer arrival model and define the regret for the learning problem in both stochastic and adversarial settings.Here, there is some fixed but unknown distribution of types q. On each round, a buyer of type i t ∼ q is drawn independently. The optimal expected revenue OPT under type distribution q is as defined in (2) . The regret R T is as defined below. We wish to design algorithms which have small expected regret E[R T ], where the expectation accounts for both the sampling of types i t ∼ q and any randomness in the algorithm. We have,EQUATIONAdversarial setting. Here, the types on each round {i t } T t=1 are chosen arbitrarily, possibly by an oblivious adversary, ahead of time. The type on round t is revealed to the seller only at the end of the round, and only if there is a purchase. In the adversarial setting, we define our regret R T with respect to the single best price in P in hindsight. We wish to design algorithms with small expected regret E[R T ], where the expectation is with respect to any randomness in the algorithm. We have,EQUATIONGiven: Approximation parameter ϵ > 0.Let W be discretization of the valuation space [0, 1] defined as follows,Z i ∆ = ϵ(1 + ϵ) i ; ∀ i ∈ 0, 1, . . . , log 1+ϵ 1 ϵ , W i ∆ = Z i-1 + Z i-1 • ϵk m ; ∀ k ∈ {1, 2, ..., ⌈(2 + ϵ)m⌉} , W ∆ = ⌈log 1+ϵ 1 ϵ ⌉ i=1 W i .Set P to be the class of all "m-step" functions mapping [N ] to W . 
efficient discretization of price curves with small errors: 
 We first study the revenue maximization problem in the offline setting, where the seller knows both the valuation curves v i , i ∈ [m], and the type distribution q. Our goal is to design a discretization so as to achieve revenue within a gap of O(ϵ) from OPT. Before discussing our discretization algorithms, we first show that the optimal pricing curve is "simple" when there are at most m types.Lemma 3.1. Assume there are m types with non-decreasing value curves{v i } i∈[m]. For any nondecreasing price curve p, there exists an "m-step" price curve p that yields expected revenue at least that of p with respect to any distribution over the m types. Here, m-step refers to non-decreasing functions f :[N ] → [0, 1] where f (n + 1) -f (n) > 0 in at most m points (i.e., at most m jumps).Lemma 3.1, proven in Appendix A.1, will be an important tool in all three discretization algorithms of this section. It will allow us to reduce the space of pricing curves as we only need to focus on m-step price curves. Next, we present our first discretization procedure in Algorithm 1, which only assumes the monotonicity of the valuation curves.Discretization scheme under monotonic valuations. Our discretization proecdure, outlined in Algorithm 1, adapts the method in Hartline and Koltun [25] using Lemma 3.1. For this, we will first construct a discretization W of the valuation space as follows. Let Z i = ϵ(1 + ϵ) i , i = 0, 1, . . . , log 1+ϵ 1 ϵ be the powers of (1 + ϵ) on price space [ϵ, 1]. For each i, we let W i be a uniform discretization of the interval[Z i-1 , Z i+1 ) uniformly with gap Z i-1 • ϵ m .Finally, let W be the union of all such W i . According to Lemma 3.1, every price function in P has the same revenue as an m-step function. We set P to be all choices of non-decreasing m-step functions that take value in W . We have the following theorem about Algorithm 1 which we prove in Appendix A.2. Theorem 3.1. Consider the discretization P as constructed in Algorithm 1. For any type distribution, there exists p ∈ P such that rev(p) ≥ OPT -O(ϵ). Moreover, we have |P| ≤e(N -1) m m e⌈(2 + ϵ)⌉ log 1+ϵ 1 ϵ m ∈ O N ϵ m .Discretization scheme for smooth monotonic valuations. Due to space constraints, we present our algorithm, under Assumption 1 in Appendix A.4. We have the following theorem about Algorithm 5.Theorem 3.2. Consider the discretization P as constructed in Algorithm 5. Under Assumption 1, for any type distribution, there exists p ∈ P such that rev(p) ≥ OPT -O(ϵ). Moreover, |P| ∈ O log m 1+ϵ (1/ϵ) • (L/ϵ) m ∈ O L ϵ 2 m .Discretization scheme for monotone valuations under diminishing returns. Finally, we study discretization schemes under the diminishing returns condition. Our procedure, outlined in Algorithm 2 proceeds as follows. We use the same discretization W of the valuation space from Algorithm 1.Next, we will discretize the dataspace [N ]. To exploit the structure in the diminishing returns condition, we will need to do so more densely when n is small. For this, letY i = 2Jm ϵ 2 (1 + ϵ 2 ) i , i = 0, . . . , ⌈log 1+ϵ 2 N ϵ 22Jm ⌉ be the powers of (1 + ϵ 2 ) on data space 2Jm ϵ 2 , N . For each i, the setQ i further partitions the interval [Y i , Y i+1 ) uniformly with gap Y i • ϵ 2 2Jm .For n smaller than 2Jm ϵ 2 , we do not discretize it as the valuations may change rapidly when n is small. Let N D be the union of Algorithm 2 Price discretization scheme monotonic valuations under diminishing returns Given: Diminishing returns constant J, approximation parameter ϵ.Let W ∆ = ⌈log 1+ϵ 1 ϵ ⌉ i=2 W i, were W i s are the same as in Algorithm 1.Let N D be discretization of the interval [0, N ] defined as follows,Y i ∆ = 2Jm ϵ 2 (1 + ϵ 2 ) i , i = 0, 1, . . . , log 1+ϵ 2 N ϵ 2 2Jm , Q i ∆ = Y i + Y i • ϵ 2 k 2Jm , k = 0, 1, . . . , ⌊2Jm⌋ , Q ∆ = log 1+ϵ 2 N ϵ 2 2Jm i=1 Q i , N D ∆ = 1, 2, . . . , 2Jm ϵ 2 ∪ Q.The discretization price set P is the class of all "m-step" price curves on function spaceN D → W . 1, 2, . . . , 2Jm ϵ 2and all the set Q i . Therefore, N D has a size of at most 2Jm ϵ 2 +2Jm⌈log 1+ϵ 2 N ϵ 2 2Jm ⌉. We have the following theorem about Algorithm 2 which we prove in Appendix A.5. Theorem 3.3. Consider the discretization P as constructed in Algorithm 2. Under Assumption 2, for any type distribution, there exists p ∈ P such that rev(p) ≥ OPT -O(ϵ). Moreover,|P| ∈ O J ϵ 2 m log m N ϵ 2 Jm • log m 1+ϵ 1/ϵ ∈ O J ϵ 3 m .Proof outline. By Lemma 3.1, we may assume the optimal price curve p⋆ = {(n ⋆ i , p ⋆ i )} m i=1is an m-step function, where p ⋆ i denote the value of p on step i. We generate an m-step price curve p = {(n i , p i )} m i=1 on space N D → W such that n i is obtained by rounding down n ⋆ i to the closest value in N D , and p i ≥ p ⋆ i /(1 + ϵ). We then show that if a buyer purchases at step i under price p ⋆ , she will not purchase at step j < i under new price p. Therefore, the revenue from this buyer is at leastp i ≥ p ⋆ i /(1 + ϵ) = p ⋆ i -O(ϵ), which ensures that rev(p) ≥ OPT -O(ϵ). 
online learning in the stochastic setting: 
 We now study the online learning problem outlined in §2.1 in the stochastic setting. Our Algorithm, outlined in Algorithm 3 is based on the classical upper confidence bound (UCB) algorithm for stochastic bandits [8, 38] . It takes a discretization P of the pricing curves as input, and on each round chooses a p t ∈ P which has the largest UCB on the revenue.The key challenge lies in constructing an UCB. As P is large, naively constructing UCB over prices in P will lead to a |P|T log T upper bound, leading to poor, exponential dependence on m. This is the bound if we only observe the reward for the prices that are actually pulled, but do not observe the types after purchase. Therefore, naively applying UCB is like bandit feedback. On the other extreme, had we been in an alternative setting where we observe the type regardless of purchase, this is like a full information feedback because once observe the type, we know the revenue for all prices. Then UCB gives us log(|P|)T log T upper bound. We are in an intermediate regime between bandit feedback and full information: The challenge in constructing the UCB arises because we only observe types upon purchase. As the key unknown is the type distribution, we maintain UCBs for it and translate them to UCBs for the revenue. In particular, our UCB depends on how many times a buyer could have purchased at a given round, which is a random quantity depending on the algorithm itself.Construction of UCB. We will now show how to construct the upper confidence bound rev t at the end of round t, which will be used in computing p t+1 . For τ ≤ t, let S τ , defined below in (5) , be the set of types who would have purchased in round τ at price p τ had they appeared in that round. Then, for any type i ∈ [m], we define T i,t to be the number of times that type i appears in set S τ for Algorithm 3 Online data pricing in the stochastic setting.Given: time horizon T , discretization P of price curves.Set p 1 to be the zero function.# Give data away for free on round 1.A buyer of type i 1 ∼ q arrives and purchases N data points at price 0. for t = 2 to T do Compute the UCB rev t-1 (p) on the revenue of p for each p ∈ P.# See ( 5), (6) , and (7) .Set p t = argmax p∈P rev t-1 (p).A buyer of type i t ∼ q arrives, purchases n it,pt points, and pays p t (n it,pt ). end for τ ∈ {1, . . . , t}. That is, T i,t measures the number of times a buyer of type i would have purchased during the first t rounds. We have,EQUATIONNote that as we use the 0 price function on round 1, i.e. p 1 (•) = 0, we have T i,t > 0 for all t > 1. Next, we estimate q i via the fraction of times that type i has appeared in the past t rounds, provided that i ∈ S τ for τ ∈ {1, . . . , t}. We have defined this quantity, q i,t below in (6) . Via a standard application of Hoeffding's inequality, we can show that q i -q i,t ≤ (log T )/T i,t with high probability. Using this, we can construct an upper confidence bound q i,t as follows,EQUATIONWe now translate the UCBs on q to the UCBs on the revenue. Recall from (1) that a buyer of type i will purchase n i,p points at price p and the revenue from this buyer will be p(n i,p ). Note that as the seller has access to the valuation curves, he can compute n i,p for any i and price curve p. Since rev(p) = E i∼q [p(n i,p )], we have the following natural UCB for rev(p) on round t:EQUATIONThis completes the description of our construction. The following theorem bounds the regret for Algorithm 3 when paired with any of the discretization schemes in §3. While the computational complexity of our method depends on |P|, there is no dependence on the regret because of the above construction of the UCB. The proof is given in Appendix C.Theorem 4.1. Suppose in Algorithm 3 we use a discretization P which is a O(1/ √ T ) additive approximation to any price curve. Then, the regret of Algorithm 3 satisfiesE[R T ] ∈ O(m √ T ).Proof challenges. When bounding the regret, we first observe that the subsets S ⊂ [m] induces a partitioning of the price curves, where p belongs to the partition of S, if all types in S would make a purchase at price p, and all types in S c would not make a purchase at price p. With this insight, we can view the action of a seller as not just choosing a price curve, but also choosing a setS t ⊂ [n].That is, S t can be viewed as a super-arm in a combinatorial semi-bandit problem [37] . 
online learning in the adversarial setting: 
 We now study the adversarial setting. Similar to the stochastic setting, our algorithm will use a discretization of the price curves from §3. We will control regret by bounding both the discretization error and the algorithm's regret relative to the best pricing curve in the discretization.Before proceeding, let us first contextualize our feedback model against prior work. If the buyers do not reveal their types, this becomes an adversarial bandit problem with |P| arms (pricing curves) [33] .Using an algorithm such as EXP-3 [9] results in large O(T 1 /2 |P| 1 /2 ) regret, which is not ideal due to |P|'s exponential dependence in m. Conversely, if buyers reveal their types regardless of purchase, Algorithm 4 Online data pricing in the adversarial setting.Given: time horizon T , discretization P, perturbation parameter θ.For each p ∈ P, sample θ p from an exponential distribution with pdf θe -θx for t = 1 to T do Set price curve for the current roundp t = argmax p∈P t-1 τ =1 r τ (p) + θ p .A buyer of type i t arrives, purchases n it,pt points, and pays p t (n it,pt ).if n it,pt > 0 then Set r t (p) = p(n it,p ) for all p ∈ P.# If there was a purchase else Set r t (p) = i∈S c t p(n i,p ) for all p ∈ P.# See (5) for St.this is equivalent to full information feedback, where algorithms such as Hedge or Follow-theperturbed-leader (FTPL) [31] yield O(T 1 /2 log 1 /2 |P|) regret, translating to O((mT ) 1 /2 ) with our discretization schemes in §3. In our intermediate regime, where feedback is only revealed upon purchase, we aim for a middle ground. We show our algorithm, outlined in Algorithm 4, achieves O(m 3/2 T 1 /2 ) regret, which is worse than full information, but still depends polynomially on m.Our algorithm takes a discretization P and a perturbation parameter θ as input. First, it samples a random perturbation θ p from an exponential distribution with pdf θe -θx for each pricing curve p in P. It maintains rewards {r t (p)} t,p for each round t and price curve p. On each round, it chooses the price curve that maximizes the perturbed cumulative reward t τ =1 r τ (p) + θ p . This scheme is similar to FTPL, but the key difference is in how we design the rewards {r t (p)} t,p . To describe this, let S t , defined exactly as in (5) , be the set of agents who would have purchased in round t at price p t . At the end of the round, if there was a purchase, for all prices p ∈ P, we set the reward to be r t (p) = p(n it,p ), i.e. the payment we would have received from the buyer at that round, had the price been p (see (1) ). If there was no purchase, we know that i t / ∈ S t , in which case we set r t (p) = i∈S c t p(n i,p ). In this case, r t (p) is an upper bound on p(n it,p ), and this upper bound is tight around prices similar to the chosen price p t ; in fact, r t (p t ) = 0 if there was no purchase. Intuitively, r t (p) deals with the uncertainty of not knowing the type on round t by providing a large reward (as we are taking the sum) to prices that could have resulted in a purchase, which encourages exploration of such prices in future rounds. This intuition will help us bound the regret. Theorem 5.1 provides a bound on the regret for Algorithm 4. Its proof is given in Appendix B. Combining this with the size of P under the various assumptions in §3, we obtain O(m 3 /2 √ T ) regret.Theorem 5.1. Suppose in Algorithm 4 we use a discretization P which is a O(1/ √ T ) additive approximation to any price curve. Let R T be as defined in (4). Then, for Algorithm 4, we haveE[R T ] ∈ O m 2 θT + θ -1 1 + log P . Setting θ = 1+log|P| m 2 T , we have E[R T ] ∈ O m T log P . 
conclusion and discussion: 
 We designed revenue-optimal learning algorithms for pricing data. First, we leveraged properties like smoothness and diminishing returns to create novel discretization schemes for approximating any pricing curve. These schemes were then used in our learning algorithms to improve their statistical and computational properties. Our algorithms build on classical methods like UCB and FTPL but required significant adaptations to handle the vast space of pricing curves and the asymmetric feedback. An interesting future direction would be to relax the assumption that the seller knows the valuation curves v i .Computational complexity. Our algorithm is designed to achieve polynomial computational complexity with respect to the number of data points when the number of types is fixed, making it suitable for practical data pricing scenarios where the type count is typically small or bounded. While the overall computational cost grows exponentially with the number of types due to the problem's strong NP-hardness (see [14] ), this design choice ensures computational feasibility in settings with large datasets and a limited number of types. 
 
 Appendix: A.1 Proof of Lemma 3.1 Lemma 3.1. Assume there are m types with non-decreasing value curves {v i } i∈ [m] . For any nondecreasing price curve p, there exists an "m-step" price curve p that yields expected revenue at least that of p with respect to any distribution over the m types. Here, m-step refers to non-decreasing functions f : [N ] → [0, 1] where f (n + 1) -f (n) > 0 in at most m points (i.e., at most m jumps).Proof of Lemma 3.1. Fix a price curve p. Let n i,p be the amount of data type i purchase at price curve p, that isn i,p ∆ = max argmax n∈[N ] (v i (n) -p(n)) . For {n i,p } i∈[m] , let π : [m] → [m] be a permutation such that n π(1),p ≤ n π(2),p ≤ • • • ≤ n π(m),p . Let n (i) ∆ = n π(i),p . Then, define a function p : [N ] → [0, 1] as follows, p(n) ∆ =                p n (1) , n ≤ n (1) , p n (2) , n (1) < n ≤ n (2) , . . . p n (m-1) , n (m-2) < n ≤ n (m-1) , p n (m) , n (m-1) < n ≤ N,so that p has at most m steps. Then, p has following properties,p(n) = p(n), when n ∈ n (1) , n (2) , . . . , n (m) , p(n) ≤ p(n), when n ∈ [N ] \ n (1), n (2) , . . . , n (m) .We next prove that for any i ∈ [m], after changing the price function from p to p, the type i buyer either purchases at (n i,p , p(n i,p )) or at (N, p(n (m) )).For any type i and any amount of data n ≤ n (m) , there exists k such that n (k-1) < n ≤ n (k) (let n (0) = 0), we then havev i (n) -p(n) ≤ v i n (k) -p n (k)(as v i is non-decreasing and p is a step function.)= v i n (k) -p n (k) (as p n (k) = p n (k) ) ≤ v i (n i,p ) -p(n i,p )(as n i,p maximizes the buyer's utility.) = v i (n i,p ) -p(n i,p ).(as p(n i,p ) = p(n i,p ))As shown in the above, type i still prefers purchasing n i,p data over all n ≤ n (m) under price p.For n ∈ n (m) + 1, . . . , N , by the monotonicity of value curves, we haveN = max    arg max n∈{n (m) +1,...,N } (v i (n) -p(n))    .Therefore, for any i ∈ [m], type i either purchases at (n i,p , p(n i,p )), or purchases at (N, p(N )) = (N, p(n (m) )) under price p. No matter in which case, type i contributes no less revenue under p than p. It then follows that, for any type distribution q, rev(p) ≥ rev(p).In this subsection, we prove Theorem 3.1 by decomposing it into three technical lemmas (Lemma A.1, A.2 and A.3). In Lemma A.1 and A.2, we prove the approximation guarantee of our discretization scheme and, in Lemma A.3 we provide an upper bound on the size of the discretization. Lemma A.1. For any type distribution, there exists a pricing function p :[N ] → [ϵ, 1] such that rev( p) ≥ OPT -ϵ.Proof of Lemma A.1. Consider the optimal pricing function p⋆ : [N ] → [0, 1], i.e., OPT = rev(p ⋆ ). Consider price curve p : [N ] → [ϵ, 1] where p(n) = max (ϵ, p ⋆ (n)). Let J ∆ = {n ∈ [N ] : p(n) = p ⋆ (n)}be the set of data quantities whose price under p are the same as those under p. Any buyer type who would have purchased n ∈ J amount of data under p ⋆ will purchase the same amount of data under p. On the other hand, for buyer types who would have purchased n / ∈ J amount of data under p ⋆ , since p(n) = ϵ > p ⋆ (n) for n / ∈ J, the expected revenue contribution from such buyers under p ⋆ is at most ϵ, hence no matter they purchase or not under p, we have rev( p) ≥ OPT -ϵ.N there exists p ′ ∈ P such that rev(p ′ ) ≥ rev( p)/(1 + ϵ), for any type distribution q.Proof of Lemma A.2. For m buyer types, by Lemma 3.1, there exists a non-decreasing step function p ∈ [ϵ, 1] N with at most m steps, whose expected revenue is at least rev( p). Assume p has k steps, k ≤ m. To simplify the notation, for 1 ≤ j ≤ k, let pj denote the price p on jth step. That is,p(n) =          p1 , n ∈ (0, i 1 ] ∩ Z, p2 , n ∈ (i 1 , i 2 ] ∩ Z, . . . pk , n ∈ (i k-1 , N ] ∩ Z.Where i 1 , . . . , i k-1 ∈ [N ] are discontinuities in p.Recall the definitions of Z and W as stated in Algorithm 1,Z i ∆ = ϵ(1 + ϵ) i : ∀ i ∈ 0, 1, . . . , log 1+ϵ 1 ϵ , Z = i Z i . W i ∆ = Z i-1 + Z i-1 • ϵk m : ∀ k ∈ {1, 2, ..., ⌈(2 + ϵ)m⌉} , W ∆ = ⌈log 1+ϵ 1 ϵ ⌉ i=1 W i .Let i k = N and for each j ∈ [k], let Z ij be the price obtained by rounding pj down to the nearest value in Z. By constructions of Z and W above, W ij is a partition of interval (Z ij -1 , Z ij +1 ). Let w j be the price obtained by rounding pj down to the nearest value in W ij . Set d j ∆ = ϵ m • Z ij -1 and consider k-step function p defined by whose price at jth step (denotedp j ) is w j -(j -1)d j ∈ W ij , that is p(n) =          p 1 = w 1 , for n ∈ (0, i 1 ] ∩ Z, p 2 = w 2 -d 2 ,for n ∈ (i 1 , i 2 ] ∩ Z, . . .p k = w k -(k -1)d k , for n ∈ (i k-1 , N ] ∩ Z.By the tie-breaking rule and the monotonicity of valuation curves, buyers only purchase among 0, i 1 , i 1 , . . . , i k number of data under p and p.Subclaim. Then, p and p satisfies the followingEQUATIONwith respect to any type distribution.Proof of the Subclaim. We prove the above subclaim with two steps.Step 1: No buyer who prefers to purchase i j data under p would prefer i j ′ data for some j ′ < j under p (i.e., one with a less price). This is because, when going from price p to p, the increase in the buyer's utility for i j data is pj -p j , which is higher than the increase pj ′ -p j ′ for i j ′ data. Formally, this can be seen as follows: For any j ′ < j we have,pj -p j ≥ w j -p j = (j -1)d j ,as pj ≥ w j and p j = w j -(j -1)d j . Moreover,EQUATIONThe inequality pj ′ < w j ′ + d j ′ holds because w j ′ is the result of rounding down pj to the nearest value in W ij .By constructions of sets Z and W , we have d j ≥ d j ′ which implies (j -1)d j ≥ j ′ d j ′ . Then, by combining the above inequalities, we obtainEQUATIONConsider a buyer with value curve v who prefers to purchase at i j under price p, then it must beEQUATIONThen, by combining ( 10) and ( 11), we havev(i j ) -p j > v(i j ′ ) -p j ′ ,therefore the buyer would not purchase at i j ′ < i j under p.Step 2: Next, we claim that p j ≥ pj /(1 + ϵ) for all step j ∈ [k]. Since Z ij is obtained by rounding pj down to the nearest value in Z, we haveEQUATIONBy ( 9) and the above, we havep j ≥ pj -jd j ≥ Z ij -1 + (m -j)d j ≥ Z ij -1 ,where the first inequality is by ( 9), the second is by (12) , and the third is because m ≤ j.Then, it follows thatpj ′ -p j ≤ j • d j = ϵ • j m • Z ij -1 ≤ ϵ • Z ij -1 ≤ ϵ • p j =⇒ p j ≥ pj /(1 + ϵ).So far we have proved p j ≥ pj /(1 + ϵ) and no type wants to change their preference to a smaller amount of data under p. If one type purchase at pi under p and p k under p for k ≥ i, then p k ≥ p i ≥ pi /(1 + ϵ). Therefore, we haverev(p) ≥ rev(p)/(1 + ϵ) ≥ rev(p)/(1 + ϵ).Since the construction of price p is not relevant to type distribution, the above holds for any type distribution q, which proves the subclaim.Note that p constructed in the above subclaim is not necessarily non-decreasing as a larger amount of data surfers more price deduction when going from p to p. In this case, we can directly construct a non-decreasing price curve p ′ ∈ P from p such thatrev(p ′ ) ≥ rev(p)/(1 + ϵ). Let S ∆ = {i ∈ [k] : ∃j < i, s.t. p j > p i }.If S is empty, this implies that p is non-decreasing, hence setting p ′ = p. If S is not empty, we define p ′ as follows: Let p ′ be a k-step function with the same jump points i 1 , . . . , i k as p. Let p ′ i be the value of p ′ on ith step. Then, for i / ∈ S, let p ′ i = p i ; and for i ∈ S, let p ′ i = max j / ∈S,j<i p j . By construction, p ′ is non-decreasing. Moreover, p ′ = p on set S c and p ′ > p on set S.Next, we claim that pj -p ′ j is non-decreasing for all j ∈ [k]. Both (p j -p j ) j∈[k] and p are non-decreasing with respect to j by the previous results. Hence,pj -p ′ j < pj -p ′ j ≤ pj+1 -p j+1 = pj+1 -p ′ j+1 , if j ∈ S, j + 1 / ∈ S, pj -p ′ j = pj -p ′ j ≤ pj+1 -p j+1 = pj+1 -p ′ j+1 , if j / ∈ S, j + 1 / ∈ S, pj -p ′ j = pj -p ′ j+1 ≤ pj+1 -p ′ j+1 , if j / ∈ S, j + 1 ∈ S, (as p ′ j+1 = p ′ j ) pj -p ′ j = pj -p ′ j+1 ≤ pj+1 -p ′ j+1 , if j ∈ S, j + 1 ∈ S. (as p ′ j+1 = p ′ j )Therefore, any type that prefers to purchase at jth step under p would not prefer purchasing at any step j ′ < j under p ′ , and since p ′ j ≥ p j ≥ pj /(1 + ϵ), we haverev(p ′ ) ≥ rev(p)/(1 + ϵ) ≥ rev( p)/(1 + ϵ). Lemma A.3. When n > m, P ≤ eN m m e⌈(2 + ϵ)⌉ log 1+ϵ 1 ϵ m .Proof of Lemma A.3. For any integer i ≤ m, the number of non-decreasing i-step price function isN -1 i |W |i , hence we have Finally, Theorem 3.1 follows directly from the above lemmas. Proof of Theorem 3.1. Combining Lemma A.1 and Lemma A.2 together, we conclude that there exists price curve p ′ ∈ P such thatEQUATIONrev(p ′ ) ≥ rev(p) 1 + ϵ ≥ OPT -ϵ 1 + ϵ ≥ OPT - 2ϵ 1 + ϵ = OPT -O(ϵ).The size of P follows from Lemma A.3.We study discretization schemes to approximate monotone valuations under the smoothness condition in Assumption 1. Our procedure is outlined in Algorithm 5. The discretization W of the valuation space follows Algorithm 1. Additionally, we uniformly split the data space into multiples of ϵN mL , denoting them as the set N S . We then set the discretization P to be the class of all "m-step" price curves on the function space N S → W . The following theorem, proven in Appendix A.4, outlines the main properties of this discretization scheme: the size of the discretization has no dependence on the number of data N .Given: Smoothness constant L, approximation parameter ϵ > 0.Let W be discretization of the valuation space [0, 1] given in Algorithm 1.Let N S be the following discretization of the interval [0, N ],δ ∆ = ϵN mL , N S ∆ = δk : k ∈ N δ .Set P to be the class of all "m-step" functions mapping N S → W .A.4 Proof of Theorem 3.2 Theorem 3.2. Consider the discretization P as constructed in Algorithm 5. Under Assumption 1, for any type distribution, there exists p ∈ P such that rev(p) ≥ OPT -O(ϵ). Moreover, |P| ∈ O log m 1+ϵ (1/ϵ) • (L/ϵ) m ∈ O L ϵ 2 m .Proof of Theorem 3.2. By Lemma 3.1, there is a revenue optimal price curve p⋆ : [N ] → [0, 1] which is a k-step function, for some k ∈ [m].Where p ⋆ can be compactly represented as the following set of tuples:{(n ⋆ 1 , p ⋆ 1 ), (n ⋆ 2 , p ⋆ 2 ), . . . , (n ⋆ k , p ⋆ k )} , where n ⋆ 1 , . . . , n ⋆ k denote the locations of jumps and p ⋆ i denote the value of p ⋆ on step i ∈ [k] (i.e. p ⋆ (n) = p ⋆ i for n ∈ (n ⋆ i-1 , n ⋆ i ]). Let ε := ϵ m .Next, we generate a price p ′ using Algorithm 6, which ensures that the price curve p generated in the following step ( 13) is non-decreasing. We demonstrate that in each round of Algorithm 6, we incur a revenue loss of at most ε. If p ′ i > p ′ i-1 + ε, everything remains the same and thus does not affect the expected revenue. If not, we combine the price of step i with step i -1, let p′ j ∆ = p ′ j -p ′ i -p ′ i-1 for j = i, .. . , k. During this process, buyers either make purchases at the same step, or switch to purchase at a higher step. Note that p ′ i -p ′ i-1 < ε, so the revenue loss of each type is at most ε. This implies that the revenue loss in each round is at most ε. As there are k rounds, we lose expected revenue of at most mε. We conclude that rev(p ′ ) is within a gap of ϵ from OPT, i.e., rev(p ′ ) ≥ OPT -ϵ.Input: Optimal price curve p ⋆ . Let p ′ = p ⋆ . for i = 2, . . . , k do if p ′ i < p ′ i-1 + ε then for j = i, . . . , k do p ′ j = p ′ j -p ′ i -p ′ i-1 . end for end if end for Output: Price curve p ′ .After combining some steps in Algorithm 6, Assume that p ′ is a k-step function ( k ≤ k) represented by(n ′ 1 , p ′ 1 ), (n ′ 2 , p ′ 2 ), . . . , (n ′ k, p ′ k) .Then, we define a new price curve p ∈ P as follows: let δ := εN L , then p is a k-step function represented by {(n 1 , p 1 ), (n 2 , p 2 ), . . . , (nk, pk)} , whereEQUATIONFirst, we show that no buyer who purchases at step i under p ′ would purchase at step j < i under p.Let the buyer's valuation be v. First, we prove that the buyer's utility is non-negative at n i :v(n i ) -p i ≥ v(n ′ i ) -δ • L N -p i (by L/N -Smoothness of v.) = v(n ′ i ) -δ • L N -p ′ i + iε ≥ v(n ′ i ) -ε -p ′ i + iε (as δ • L N ≤ L N • εN L = ε.) = v(n ′ i ) -p ′ i + (i -1)ε ≥ v(n ′ i ) -p ′ i ≥ 0.Then, we prove that the buyer's utility at n i is larger than that of n j for j < i, therefore, the buyer would not prefer buying at step j < i under price p.v(n i ) -p i -(v(n j ) -p j ) ≥ v(n ′ i ) -δ • L N -v(n ′ j ) -(p i -p j ) (by L/N -Smoothness of v.) = v(n ′ i ) -δ • L N -v(n ′ j ) -(p ′ i -p ′ j -(i -j)ε) ≥ v(n ′ i ) -ε -v(n ′ j ) -(p ′ i -p ′ j -(i -j)ε) (as δ • L N ≤ L N • εN L = ε) = (v(n ′ i ) -p ′ i ) -(v(n ′ j ) -p ′ j ) + (i -j -1)ε ≥ (v(n ′ i ) -p ′ i ) -(v(n ′ j ) -p ′ j ) (as i > j) ≥ 0.(as the buyer prefers n i than n k under p ′ .)Finally, fix the type distribution (q 1 , . . . , q m ), then we haverev(p ′ ) -rev(p) ≤ m h=1 q h k i=1 (p ′ i -p i ) • I(Type j purchase at p ′ i under price p ′ ) ≤ mε = ϵ. (as ϵ = mε.)Hence, rev(p) is within a gap of 2ϵ from OPT.We then apply Theorem 3.1 to price p. Therefore, it is enough to consider price functions from the setN S ∆ = kδ : k = 1, . . . , N δ ⊆ [N ] to W to approximate the revenue within O(ϵ) gap. Moreover, this discretization is of the size N δ |W | ∈ O log 1+ϵ 1 ϵ m L ϵ m as N δ ∈ O Lm ϵ .A.5 Proof of Theorem 3.3 Theorem 3.3. Consider the discretization P as constructed in Algorithm 2. Under Assumption 2, for any type distribution, there exists p ∈ P such that rev(p) ≥ OPT -O(ϵ). Moreover,|P| ∈ O J ϵ 2 m log m N ϵ 2 Jm • log m 1+ϵ 1/ϵ ∈ O J ϵ 3 m .Proof of Theorem 3.3.For each i = 0, 1, . . . , log 1+ϵ 2 N ϵ 2 2Jm , let Y i ∆ = 2Jm ϵ 2 (1 + ϵ 2 ) i , and Q i be the set Y i + Yiϵ 2 2Jm k : k = 1, . . . , ⌊2Jm⌋ , i.e., Q i splits the interval [Y i , Y i+1 ] equally into 2mJ parts.The union of Q i s and the set 1, 2, . . . , 2Jm ϵ 2 form a set of grids on [0, N ], denoted by N D . There are at most 2Jm ϵ 2 + 2Jm log 1+ϵ 2 N ϵ 2 2Jm grids in total.By Lemma 3.1, there is a revenue optimal price curve p⋆ : [N ] → [0, 1] which is a k-step function, for some k ∈ [m].Where p ⋆ can be compactly represented as the following set of tuples:{(n ⋆ 1 , p ⋆ 1 ), (n ⋆ 2 , p ⋆ 2 ), . . . , (n ⋆ k , p ⋆ k )}, where n ⋆ 1 , . . . , n ⋆ k denote the locations of jumps and p ⋆ i denote the value of p ⋆ on step i ∈[k] (i.e. p ⋆ (n) = p ⋆ i for n ∈ (n ⋆ i-1 , n ⋆ i ]). Then, define a new k-step price curve p via {(n 1 , p 1 ), (n 2 , p 2 ), . . . , (n k , p k )} ,where n i is given by n i ← round down n ⋆ i to the closest grid in N D . Then we define p i below. If p ⋆ i < ϵ(1 + ϵ), let p i = ϵ(1 + ϵ); otherwise, let Z n ⋆ i be the price obtained by rounding p ⋆ i down to the nearest value in Z. By constructions of Z and W above,W n ⋆ i is a partition of interval (Z n ⋆ i -1 , Z n ⋆ i +1). Let w i be the price obtained by roundingp ⋆ i down to the nearest value in W n ⋆ i . Set d i ∆ = ϵ m • Z n ⋆ i -1 . Then define p i ∆ = w i -i • d i ∈ W n ⋆ i . First, we prove for i satisfying p ⋆ i > ϵ(1 + ϵ), if a buyer purchases at n i under price p ⋆ , she will not purchase at n j , j < i under new price p. We prove this property separately when n i ≤ 2Jm ϵ 2 andEQUATIONLetδ i ∆ = v(n ⋆ i ) -v(n i ).Then δ i is upper bounded by,EQUATIONwhere the third inequality is due to Lemma A.4.By the construction of p, we haveEQUATIONTherefore, by (14) , v(n i ) -p i ≥ v(n ⋆ i ) -p ⋆ i ≥ 0, buyer's utility at n i under price p is non-negative.Next, we claim that v(n i ) -p i -(v(n j ) -p j ) ≥ 0. To prove this, for any j < i, let δ j∆ = v(n ⋆ j ) -v(n j ), then we have v(n i ) -p i -(v(n j ) -p j ) = v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j ) + (p ⋆ i -p i -δ i ) -(p ⋆ j -p j -δ j ) Where v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j )≥ 0 because the buyer prefers n ⋆ i over n ⋆ j under price p ⋆ . Recall that we have δ j ≥ 0, then we bound δ i -δ j as follows,EQUATIONBy the construction of p i , we have,EQUATIONTherefore, combining (17) and ( 18) together, we havev(n i ) -p i -(v(n j ) -p j ) ≥ v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j ) ≥ 0.We conclude that under price p, the buyer prefers n i over n j , for any j < i.(ii) When n i ≤ 2Jm ϵ 2 . In this case, n i = n ⋆ i , and for any j < i, we still have n j = n ⋆ j . First, we prove the buyer's utility atn ′ i under p is non-negative: v(n i ) -p i = v(n ⋆ i ) -p i = v(n ⋆ i ) -p ⋆ i + (p ⋆ i -p i ) ≥ v(n ⋆ i ) -p ⋆ i ≥ 0.Then, we show that the buyer prefers n i over n j under p:v(n i ) -p i -(v(n j ) -p j ) = v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j ) + (p ⋆ i -p i -δ i ) -(p ⋆ j -p j -δ j ) = v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j ) + (p ⋆ i -p i ) -(p ⋆ j -p j ) ≥ v(n ⋆ i ) -p ⋆ i -(v(n ⋆ j ) -p ⋆ j ) ≥ 0,where the first inequality is due to (18) , and the second is because the buyer prefers n ⋆ i over n ⋆ j under p ⋆ . So far we have completed the proof that for i satisfying p ⋆ i > ϵ(1 + ϵ), if a buyer purchases at n i under price p ⋆ , she will not purchase at n j , j < i under new price p.Then, similar to Step 2 in the proof of Lemma A.2, we have p ≥ p ⋆ 1+ϵ pointwise. We then conclude the proof by observingrev(p) ≥ rev(p ⋆ ) -O(ϵ) 1 + ϵ = OPT -O(ϵ). Lemma A.4. When n i > 2Jm ϵ 2 , we have n ⋆ j -n i ≤ n i • ϵ 2 2Jm + 1.Proof of Lemma A. 4 . By the construction of discretization set, n i must have the following form,Y i ′ + Y i ′ • ϵ 2 k ′ 2Jm, whereY i ′ = 2Jm ϵ 2 (1 + ϵ 2 ) i ′ for some i ′ , k ′ ∈ Z.Since n ′ j is obtained by rounding down n j to the nearest grid in N D , n j satisfies the following inequality,n j ≤ n ⋆ j ≤ Y i ′ + Y i ′ • ϵ 2 (k ′ + 1) 2Jm .Therefore, we haven ⋆ i -n i ≤ Y i ′ + Y i ′ • ϵ 2 (k ′ + 1) 2Jm -n i = Y i ′ + Y i ′ • ϵ 2 (k ′ + 1) 2Jm -Y i ′ + Y i ′ • ϵ 2 k ′ 2Jm ≤ Y i ′ + Y i ′ • ϵ 2 (k ′ + 1) 2Jm -Y i ′ + Y i ′ • ϵ 2 k ′ 2Jm + 1 = Y i ′ • ϵ 2 2Jm + 1 ≤ n i • ϵ 2 2Jm + 1.Where in the last inequality, since Y i ′ is an integer, and we haven ′ i = Y i ′ + Y i ′ • ϵ 2 k ′ 2Jm ≥ Y i ′ , for k ′ ≥ 0.B Proof of Theorem 5.1 We decompose R T into two regrets. The first term is the sacrifice of revenue on discretization. The second term is the algorithm regret when competing against the optimal price within the discretization set P.According to Theorem 3.1, our discretization scheme approaches optimal revenue within a gap of 2ϵ 1+ϵ :EQUATIONTherefore, the first term can be bounded by 2ϵT .According to Theorem B.1, the second term discretization regret is upper bounded byEQUATIONCombining ( 20) and ( 21) together, we have,E[R T ] ≤ 2ϵT + 3m T log P = O m T log P . (as ϵ = 1 √ T )Plug in the size of discretization set in Section 3, we have,E[R T ] = O m 3 /2 √ T .Theorem Then, we decompose the regret as follows,EQUATIONWe bound three terms in (22) separately.The first term. For any price p and any round t, we have r t (p) ≥ r(i t , p) by definition. Hence,EQUATIONThe second term. Since p ⋆ = argmax p∈P T t=1 r(i t , p). We apply Lemma B.1 to p ⋆ ,T t=1 r t (p ⋆ ) - T t=1 r t (p t+1 ) ≤ θ p1 -θ p ⋆ .Note that both θ p1 and θ p ⋆ are drawn i.i.d. from exponential distribution,E[θ p1 ] ≤ E max p∈P θ p ≤ 1 + log P θ , E[θ p ⋆ ] ≤ E max p∈P θ p ≤ 1 + log P θ .We haveEQUATIONThe third term. Note that for any price p ∈ P and any round t, r t (p) ≤ m. Therefore we have,E [r t (p t+1 ) -r t (p t )] = P (p t+1 ̸ = p t ) E [r t (p t+1 ) -r t (p t ) | p t+1 ̸ = p t ] ≤ m • P (p t+1 ̸ = p t ) .The price curve on round t is p t , then by the price updation rule,p t = argmax p∈P t-1 τ =1 r τ (p) + θ p ,which is equivalent to,θ pt ≥ θ p + t-1 τ =1 r τ (p) - t-1 τ =1 r τ (p t ), ∀p ∈ P.For all p ′ ∈ P, let c t-1,p ′ denoteEQUATIONthen p t = p ′ is equivalent toEQUATION)Subclaim. If θ pt also satisfies the following condition (27) ,EQUATIONthen p t+1 = p t .Proof of the Subclaim. If ( 27) holds for all p ∈ P,θ pt ≥ θ p + t-1 τ =1 r τ (p) - t-1 τ =1 r τ (p t ) + m ≥ θ p + t τ =1 r τ (p) - t τ =1 r τ (p t ). (because ∀p ∈ P, r t (p) ∈ [0, m])Hence,p t = argmax p∈P t τ =1 r τ (p) + θ p = p t+1 .Therefore, ( 27) is a sufficient condition for p t+1 = p t . We then bound the probability of p t+1 = p t by computing the probability of ( 27 Set θ = log|P| m 2 T . Combining the upper bounds for three terms ( 23), ( 24) and ( 28) together, we haveE[R T ] ≤ 1 + log P θ + m 2 θT ∈ O m T log P .Plugging in the size of the discretization set (Theorem 3.1), we have,E[R T ] ∈ O m 3 /2 √ T .Lemma B.1. For any p ∈ P, Proof of Lemma B.1. We prove this by induction. For T = 0, the inequality θ p1 ≥ θ p holds by definition p 1 = argmax p∈P θ p . Assume that the inequality holds for some T . Then for any p ∈ P,T +1 t=1 r t (p t+1 ) + θ p1 = T t=1 r t (p t+1 ) + θ p1 + r T +1 (p T +2 ) ≥ T t=1 r t (p T +2 ) + θ p T +2 + r T +1 (p T +2 ) = T +1 t=1 r t (p T +2 ) + θ p T +2 ≥ T +1 t=1 r t (p) + θ p .Where the first inequality is by the induction hypothesis, and the second inequality is byp T +2 = arg max p∈P T +1 t=1 r t (p) + θ p .By the induction, the inequality (29) holds for any T ≥ 0.In this section, we prove, Theorem 4.1, our regret upper bound of Algorithm 3. We prove the theorem by first decomposing the regret into two parts: Regret with respect to the best price in a discretized set (called "discretization regret") and the residual error due to discretization. The residual error is controlled by the approximation guarantees developed in Section 3. Then, the key lemma in this appendix is Lemma C.1 which controls the discretization. We prove Lemma C.1 using a technique adapted from Chen et al. [15] . Proof of Theorem 4.1. For the sake of simplicity, we define r(i, p) as the revenue under type i and price p, i.e, r(i, p) ∆ = p(n i,p ). Therefore, on every round, we have r(i t , p t ) = p t (n it,pt ).Recall that the regret R T isR T ∆ = T • OPT - T t=1 p t (n it,pt ) = T • OPT - T t=1 r(i t , p t ) = T • OPT -T • max p∈P rev(p)Loss of revenue due to discretizationEQUATIONWe decompose R T into two parts. The first term is the sacrifice of revenue on discretization. The second term is the algorithm regret when competing against the optimal price within the discretization set P.According to Theorem 3.1, our discretization scheme approaches OPT within a gap of 2ϵ 1+ϵ ,OPT -max p∈P rev(p) ≤ 2ϵ 1 + ϵ ≤ 2ϵ.Therefore, the first term can be bounded as,EQUATIONBy Lemma C.1, the second term, discretization regret, is upper bounded byEQUATIONCombining ( 31) and ( 32) together, we have,EQUATIONWe can further decomposeE[R T ] into T t=1 E [δ pt • I(A t )] and T t=1 E [δ pt • I(A c t )].Where for any round t, we define the good event A t as follows, ∀i ∈ [m] , q i ≤ q i,t ≤ q i + 2 log T T i,t .Define q i,t∆ = t τ =1 I(i∈Sτ ,iτ =i) Ti,t = t s=1 I(i∈Sτ )•I(iτ =i) t τ =1 I(i∈Sτ ). Note that I(i τ = i) is a random variable that follows Bernoulli distribution Ber(q i ), and one can only observe I(i τ = i) when i ∈ S τ , let x i,j denote the mean value of first j i.i.d. observations of I(i s = i). Then, we haveP q i,t -q i > log T T i,t = t j=0 P q i,t -q i > log T T i,t , T i,t = j ≤ t j=0 P |x i,j -q i | > log T j ≤ t j=0 2 exp(-2 log T ) ≤ 2 T .Where in the first inequality, the event q i,t -q i > log T Ti,t , T i,t = j indicates |x i,j -q i | > log T j , and the second inequality follows from Hoeffding's inequality.We then bound the second term in (33)T t=1 E [δ pt I(A c t )] ≤ T t=1 E [I(A c t )] ≤ T t=1 m i=1 P q i,t -q i > log T T i,t ≤ T t=1 m i=1 2 T ≤ 2m. Define event H t ∆ = 0 < δ pt < 2 i∈St log T Ti,t-1. By Lemma C.3, we know thatI(A t-1 , δ pt > 0) =⇒ I 0 < δ pt < i∈St 2 log T T i,t-1 = I(H T ).It remains to prove the upper bound forEQUATIONA k,t ∆ = {i ∈ S t : T i,t-1 ≤ m k,t } .Then, we define an eventG k,t ∆ = {|A k,t | ≥ β k m} ,which means "In the t-th round, at least β k m types in S t has been observed at most m k,t times".Then, by Lemma C.5, we haveT t=1 I(H t ) • δ pt ≤ ∞ k=1 T t=1 I (G k,t , δ pt > 0) • δ pt . For i ∈ [m], k ∈ Z + , t ∈ [T ], define an event G i,k,t ∆ = G k,t ∩ {i ∈ S t , T i,t-1 ≤ m k,t } .Then by the definitions of G k,t and G i,k,t we haveI (G k,t , δ pt > 0) ≤ 1 β k m i∈EB I (G i,k,t , δ pt > 0) . Therefore, T t=1 I(H t ) • δ pt ≤ i∈EB ∞ k=1 T t=1 I (G i,k,t , δ pt > 0) • δ pt β k m .For any price function p, define δ p ∆ = rev(p ⋆ ) -rev(p). If δ p > 0, we call it a "bad" price. LetE B ∆ = {i ∈ [m]: type i would make a purchase at least one bad price}.For each typei ∈ E B , suppose i is contained in N i bad prices p B i,1 , p B i,2 , . . . , p B i,Ni . Let δ i,l ∆ = δ p B i,l (l ∈ [N i ]). Without loss of generality, we assume δ i,1 ≥ δ i,2 ≥ • • • ≥ δ i,Ni . Let δ i,min ∆ = δ i,Ni .For convenience, we also define δ i,0 = +∞, i.e., α k 2m δi,0 2 = 0. Then, we have (δ i,j -δ i,j+1 )T t=1 I (H t ) δ pt ≤ i∈EB ∞ k=1 T t=1 I (G i,k,t , δ pt > 0) δ pt β k m = i∈EB ∞ k=1 T t=1 Ni l=1 I G i,k,t , p t = p B i,l δ pt β k m = i∈EB ∞ k=1 T t=1 Ni l=1 I G i,k,t , p t = p B i,l δ i,l β k m ≤ i∈EB ∞ k=1 T t=1 Ni l=1 I T i,t-1 ≤ m k,t , p t = p B i,l δ i,l β k m = i∈EB ∞ k=1 T t=1 Ni l=1 I T i,t-1 ≤ α k 2m δ i,l 2 log T, p t = p B i,l δ i,l β k m = i∈EB ∞ k=1 T t=1 Ni l=1 l j=1 I α k 2m δ i,j-1 2 log T < T i,t-1 ≤ α k 2m δ i,j≤ 1 δ i,Ni + δi,1 δ i,N i 1 x 2 dx = 2 δ i,Ni - 1 δ i,1 ≤ 2 δ i,min.It follows that = |S t | √ m 1,t + ∞ k=1 |A k,t | 1 √ m k+1,t - 1 √ m k,t < m √ m 1,t + ∞ k=1 β k m 1 √ m k+1,t - 1 √ m k,t = ∞ k=1 (β k-1 -β k ) m √ m k,t .Under event H t , we haveδ pt ≤ i∈St 2 log T T i,t-1 = 2 log T • i∈St 1 T i,t-1 < 2 log T • ∞ k=1 (β k-1 -β k ) m √ m k,t = 2 ∞ k=1 β k-1 -β k √ α k • δ pt ≤ δ pt ,where the last inequality is due to Lemma C.4. We reach a contradiction here, hence the lemma follows.The following table contains the notations used in this paper.The total amount of data.The number of data.mThe number of types. The revenue from type i ∈ [m] under price curve p. q = (q 1 , q 2 , . . . , q m ) The type distribution.The expected revenue under price p.i t ∈ [m]The type of buyer on round t ∈ [T ].p t : [N ] → [0, 1]The price curve on round t ∈ [T ].The set of types that would make a purchase at price p t .The set of types that would make a purchase at price p. 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: This paper on learning prices received positive grades from all the reviewers, yet none of them were that thrilled about the paper.

I went through it myself, and I must concur with them. This is a good and interesting paper (even though it's not mind-blowing, but not all papers have to be, thankfully).

So we decided to recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper addresses the problem of exploration in pricing strategy. It proposes an algorithm and proves that it has lower regret compared to previous algorithms.
strength_weakness: strength_weakness: 1. One of the contributions of this paper is a better discretization scheme. An introduction to the insights that allowed you to design this improved discretization method would make the contribution clearer.

2. The construction of the confidence interval has room for improvement. The UCB in this paper is |q_i-q_{i,t}| \leq |log T/T_{i,t}|. Such an interval is typewise. I believe that using a joint confidence interval (for example, \sum T_{i,t} |q_i-q_{i,t}| \leq log T or similar form )or a similar form) could improve the dependency of the regret on $m$.

3. It is unclear whether Line 6 of Algorithm 3 is computationally efficient.
questions: questions: See the 'Weakness' part
limitations: limitations: See the 'Weakness' part
paper_summary: paper_summary: This paper considers a data pricing problem in which a seller has $N$ homogeneous data points they wish to sell access to.  The seller sets a price curve $p(n)$ which specifies the price a buyer must pay for access to $n$ data points for each $n \in [N]$.  Upon arrival, a buyer sees the price curve, and chooses an amount $n$ by maximizing their utility $u(n) = v(n) - p(n)$, where $v(n)$ is their valuation curve.  The buyer leaves without making a purchase if their utility is negative for all $n$.  It is assumed that there are $m$ buyer types, where all buyers of type $i$ have the same valuation curve $v_i$, and that there is a distribution $q$ over buyer types in which the arriving type is sampled i.i.d. from $q$ in each step.  The objective is then to find a price curve which maximizes the expected revenue over this distribution.  This paper focuses on online learning settings in which the distribution is unknown and must be learned or the arrival sequence is arbitrary and we want to compare to the best fixed price curve in hindsight, where now the goal is to minimize the regret.

Due to the nature of this problem (a relation to revenue maximization with unit-demand buyers), computing the exact optimal is intractable, so approximations are considered.  This is done by discretizing the space of valuation curves.  The main result of this paper are new discretization schemes for this problem which can accommodate various further assumptions such as smoothness or diminishing returns in the valuation curves.  These are then applied to develop algorithms with regret $\tilde{O}(m \sqrt{T})$ and $\tilde{O}(m^{3/2} \sqrt{T})$ in the stochastic and adversarial settings, respectively.

-----------------------

Edit: following the rebuttal some of my questions have been answered and my score has been raised.
strength_weakness: strength_weakness: There are a few concerns:
 - Lack of tightness - it is not clear to what extent these results are tight as no lower bounds are given.
 - The finite type assumption - assuming both that the number of types is small (so that the complexity bounds are reasonable) and that all the types are known up front is somewhat limiting.  Anything to address either of these comments is a significant improvement.
 - Once given the discretization scheme, the online learning methods utilize fairly standard techniques.  It would be interesting if there are other approaches to this problem.
 - A lack of an experimental evaluation which might help to provide further evidence of the practicality of the proposed methods.

As a minor comment, the organization in the appendix is poor as it does not follow the order in the main paper (appendix C gives proofs for section 5, while appendix D gives proofs for section 4).  This leads to a confusion about notation, since the definition that $r(i, p ) = p(n_{i,p})$ isn't introduced until appendix D, but is used in appendix C.
questions: questions: - Can anything be done to remove the assumption that the types are known up front?
 - Can any tight lower bounds be given for the stochastic and adversarial settings (i.e., in terms of both $m$ and T$)?

Minor comments:
 - In Eq. (22) in the appendix, it has $f_t(p^*)$ instead of $r_t(p^*)$.
limitations: limitations: The authors have made assumptions clear.
paper_summary: paper_summary: Motivated by the emergence of data marketplaces, this paper studies an online data pricing problem involving $ N $ homogeneous data points and $ m $ types of buyers in the market. Specifically, it assumes that each type of buyer has a specific value function $ v_i: [N] \rightarrow [0, 1] $. While the sellers know all the value curves $ v_i $, they do not know the distribution of buyers. The sellers need to choose a pricing curve $ p \in \mathcal{P}: [N] \rightarrow [0, 1] $ at each time period. To address this online pricing problem, the authors develop novel discretization schemes to approximate any pricing curve. To minimize the discretization size, they propose assumptions such as smoothness and diminishing returns. To solve the online learning problem, they build on classical algorithms like UCB (Upper Confidence Bound) and FTPL (Follow-The-Perturbed-Leader), providing corresponding regret bounds. These advancements contribute to more effective and efficient online data pricing strategies.
strength_weakness: strength_weakness: 1. I think Sections 3 and 4-5 are independent. Section 3 primarily introduces the price discretization schemes, while Sections 4-5 discuss online learning algorithms for both settings. In my opinion, the main contribution of your paper lies in Section 3, as the techniques in Sections 4-5 seem to be standard.

2. You claim that your analysis when constructing the UCB in this way is non-trivial since the types are observed only if they make a purchase. However, this seems common. Could you elaborate on the additional difficulties for the UCB algorithms in your case? Additionally, in line 266, maintaining UCBs for the type distribution appears to be a standard approach, and I don't see this as a significant contribution.

3. Section 5 is a little confusing. Why is it necessary to add perturbation?  Maybe you should give me some intuition. Moreover, in line 320, why is \( r_t(p) \) an upper bound on \( p(n_{i_t,p}) \)?
questions: questions: 1. While I understand that Algorithm 1 is for price discretization, and the valuation space is discretized, it remains unclear how the price set \( \bar{\mathcal{P}} \) is determined. Could you provide more details on this process? 
2. Although you have provided the regret bound, additional discussion on its tightness would be valuable. Can you elaborate on the tightness of the regret bound and compare it with existing results? 
3. Sections 4-5 discuss the online learning algorithms. Could you highlight the specific difficulties you encountered in these sections? What new techniques did you develop? What are your unique contributions? Clarifying these points will help distinguish your work from standard techniques.
limitations: limitations: As mentioned above, the studied topic is very interesting. However, I am eager to see more detailed statements regarding the unique contributions, particularly in Sections 4-5.
paper_summary: paper_summary: The paper studies an online learning problem for pricing homogeneous data, where the seller needs to offer a price function/curve based on the data size and learn the arrival probabilities of different customer types to maximize cumulative revenue. The paper first analyzes the structure of the optimal price function when there is a finite number of customer types with known arrival probabilities. It introduces new discretization schemes to achieve better dependence on the approximation error compared to existing methods. When the arrival probabilities are unknown (i.e., in the online learning setting), the paper develops algorithms for both stochastic and adversarial settings with theoretically bounded regret.
strength_weakness: strength_weakness: (1) Computational Complexity: The provided algorithms (Algorithm 3 and 4) have computational complexity depending on the horizon $T$, which can be large in practice.

(2) Lack of Numerical Validations: Since the problem is motivated by a practical pricing scenario, numerical experiments could help validate the efficiency of the algorithms, especially given the potentially large computational complexity.
questions: questions: 1. In Theorems 4.1 and 5.1, can  the discretization additive approximation $O(\frac{1}{\sqrt{T}})$ be replaced by $O(\frac{1}{\sqrt{t}})$ while maintaining the same order of regret (i.e., the discretization level changes across the periods)? The intuition is that when the estimations of $q$'s  are inaccurate, we may only need an inaccurate discretization of the price curve, potentially reducing computational complexity.
2. How can the Upper Confidence Bound (UCB) on $q$'s facilitate exploration in learning $q$'s (i.e., more explorations)? My understanding is that to learn $q$'s (i.e., collecting samples of $q$'s), we need to encourage purchases by setting a price curve lower than the estimated optimal one. However, the UCB on $q$'s does not obviously encourage lower prices.
limitations: limitations: See weaknesses.

Comments: title: Official Comment by Reviewer oHSK
Sincerely looking forward to your reply
Sincerely looking forward to your reply
Sincerely looking forward to your reply
comment: Thank you again for your comments. Based on your comments, we will clarify our contributions and techniques in future revisions.
Thank you for the response here and the discussion above. I have raised my score.
Thank you again for your comments. Based on your comments, we will clarify our contributions and techniques in future revisions.
Thank you for your response. It addresses my concerns and I have raised the score.
Thank you again for your feedback. With the discussion period ending in two days, we would appreciate knowing if our response has adequately addressed your key questions and concerns.
Thank you again for your feedback. With the discussion period ending in two days, we would appreciate knowing if our response has adequately addressed your key questions and concerns.
Thank you again for your feedback. With the discussion period ending in two days, we would appreciate knowing if our response has adequately addressed your key questions and concerns.
Thank you so much! We will make the contributions clearer in the revision.
Thank you for the response here and the discussion above.  I agree that there is more subtlety to the techniques in this paper than I originally let on.  I have raised my score.