Learning to Price Homogeneous Data
Authors: Keran Chen
Joon Suk Huh
Kirthevasan Kandasamy
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning to price
Revenue maximization
Data marketplaces
Primary area: online_learning

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.

Learning to Price Homogeneous Data
Keran Chen UW-Madison kchen429@visc.com edu
Joon Suk Huh UW-Madison jhuh23@visc.ede edu
Kirthevasan Kandasamy UW-Madison
kandasamy@cs wisc edu
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 have the same valuation curve Us [A] + [0, 1J. where (n(n) the value for having data points. priori, the seller is unaware of the distribution of buyers, but can repeat the market for T rounds so to learn the revenue-optimal pricing curve p [N] + [o. 1]. To solve this online learning problem, we first develop novel discretization schemes approximate any pricing curve. When compared to prior work, the size of our discretization schemes scales gracefully with the approximation parameter, which translates 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 the stochastic and adversarial settings. On each round, the seller chooses anonymous pricing curve pr. new buyer appears and may choose to purchase some amount of data. She then reveals her type only if she makes 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. Our algorithms achieve O(m/T) regret in the stochastic setting and Ö( 1/2 VT) regret in the adversarial setting.
1 Introduction
Due to the rise popularity machine learning, there an increased demand 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 sequence of distinct buyers over rounds, and intends to achieve large revenue. There are types of buyers in the data marketplace, with all buyers in type i having the same valuation curve V2 [N] > (0, 1] for the data, where v, (n) represents the buyer's value for having points. As data homogeneous, amount of data n (we will illustrate this in the sequel). Valuation curves are monotone non-decreasing, more data is better. At each round f, the seller chooses price curve Pe [N] + [0, 1J. where pr (n) the price for purchasing n data points. Then, a buyer with type é arrives and purchases an amount of data that maximizes her utility (value minus price), provided that she achieve non-negative utility. buyer will reveal her type to the seller only if she makes purchase, and only after she
treat agent's 's value a function of the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 pt without knowledge of the buyer's type on that round.
While there is extensive research on revenue-optimat pricing and learning to price, data marketplaces merit special attention, both due 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 is value does not increase significantly with 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.c. find revenue-optime 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 g 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 approximating the optimal pricing curves via discretization schemes. Unfortunately, existing discretization schemes have poor, often exponential, dependence on the approximation parameter c. However, achieving sublinear regret in online learning requires choosing e that vamishes with longer time horizons, i.e. - 0 as T + cc. 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 c. (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 trade-off between setting high prices to maximize instantaneous revenue versus setting low prices so as to guarantee 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-iten -engl-ittm markets which is significantly simpler, and only in the stochastic setting [23, 47].
1.1 Summary of our contributions
Our contributions in this work are threefold: (I) 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 each round are drawn from fixed but unknown distribution g. (3) Finally, in $5, we study online learning when the buyer types are chosen by an oblivious adversary.
1. Discretization (approximation) schemes for revenuc-optimal data pricing. Assuming only monotonicity, we show that there is discretization of size ((N/)emm)) which is an O(e) additive approximation to any pricing curve. When compared to prior work [14, 25], our discretization scheme has smaller dependence e- when the number of types is small (see Table 1). This will be useful, both statistically and computationally. when we study the online setting, as we need to choose e + O as T + oo 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 Ô ((I/2)m), which has no dependence on N. Next, under a diminishing returns condition, we construct a discretization of size O (JmM 3m (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 [[]] + [o, 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 OCc) approximaaann 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 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
2

---

Algorithm
Assumptions
Size of discretization
Reference
Hartline and Koltun [25]
O(2NE-N) v0(c~1ogge
Chawla et al. [14]
M
Algorithm (ours)
M, F
O(NT
Theorem 3.1
Algorithm (ours)
M. F.S.
ÓL'
Theorem 3.2
Algorithm (ours)
M. F.F.D
δ (J 3m log" N)
Theorem 3.3
Table I: Comparison of discretization (approximation) schemes of prior work and our methods under various assumptions. All methods achieve a ( additive approximation to any pricing curve. Here, M means Monotonicity, F means that there are Finite (m)) number of types, means that the valuation curves satisfy a L-Lipschitzzlike Smoothness condition (Assumption 1), and D means that they satisfy Diminishing returns condition (A (Assumption 2). The Ô notation suppresses log dependencies when there already a polynomial dependence on parameter. Prior work has exponential dependence in either N E - We wish to do better since (i) typically, the number of data N very large and (ii) we need + 0 as T + oo to achieve sublinear regret.
upper confidence bound (UCB) [8. 38] on the revenue for each price curve in the discretization previously developed; we then choose the price curve with the highest UCB. As summarized in Table 2, this algorithm achieves (m)/T) bound on the regret for any discretization scheme, including those from prior work. In the stochastic setting, the key advantage of our discretization schemes is computational.
Key insights. Both the design and the anlaysis of an algorithm is challenging in this setting due to two reasons: (i) the large size of the discretization and (i) the asymmetric nature of feedback. First, naively maintaining UCBs for each price leads to large confidence intervals, and hence large regret as the size of the discretization is large; instead, we construct confidence intervals on estimates of the type distribution, and translate them to UCBs for the revenue. Second, the asymmetric nature of the feedback places between bandit and full-information settings. Treating this like a bandit setting would lead to poor, exponential dependence on m in the regret. However, we are unable to treat this as full information since the type distribution is revealed only if there is purchase. Handling this asymmetry requires delicate construction of the UCB.
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 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 hwwpw-ttee-eeuurbed---ee designed for full-information settings and not directly applicable here. To handle asymmetric feedback, we use the information we have about the valuation curves would not have made a purchase given a price curve. a purchase made and 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.
(FTPL) [31], originally
to keep track of which customers
1.2 Related work
Dynamic pricing. The online posted-price mechanism, also known as dynamic pricing, 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 single-pant parammer demands, i.c., selling single item to buyers. Our data pricing problem is multi malti--arramtte, 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 variant of the Bayesian Unit-demand Pricing Problem (BUPP) [13]. BUPP addresses the problem of (offline) revenue maximization over known distribution of unit-demand buyers, meaning they want to buy at
3

---

Setting
Assumptions
Regret bound
Complexity per iteration
Reference
M, F
ō N m
T/2 T
Ö (mVT)
Stochastic
M. F.
Ô
((LT))))
Theorem 4.1
M. F.
Ö(JmTam//))
((()) ( ""
M. F
3 (
Adversarial
M. F, S
(LTT)")
Theorem 5.1
M, F. D
Ô (Jmmpammaa
Discretization method
Assumptions
Complexity per iteration
Regret (Adversarial)
Hartline and Koltun [25]
F
E(2NE-N)
Ö(mvTN)
Chawla et al. [14]
M,
Ô (m12%
Table 2: Comparison of regret and time complexity of our online learning methods when paired with our discretization schemes and schemes from prior work. See Table for a description of the assumptions. All methods, including [14, 25] achieve ((my/) regret in the stochastic setting,
most one item from the inventory. In BUPP, a seller has distinct items to sell to a unit-demand buyer whose valuations
(#1, ..... UN), where is the value of the ith item. Given prices Ps. i E [N], the unit-demand buyer purchases a single item i E [N] that maximizes their utility: W - Pt. Assuming the valuation profile follows a known distribution D, the goal of BUPP is find the best prices {pi [E]] that maximize the seller's expected revenue.
Our data pricing problem is 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 U1 I ... I uN, which is natural in data pricing. Unfortunately. BUPP is computationally intractable problem, as ours. BUPP is known to be NP-hard even when D is a product distribution [16]. Moreover,
assuming that values 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 is fixed constant.
monotonic (i.e., U1 S... S ww),
The previous works most relevant to our paper are Hartline and Koltun [25] and Chawla al. [14), which study offline revenue maximization for unit-demaane buyers. Buyers in our problem are also unit- demand, as each amount of data points can seen as an individual item. Revenue maxinization 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 items. Chawla et al. [14] introduced a polynomial-tine
approximation scheme (PTAS) for unit-demand buyers with monotonic values. In this work, extend the framework the online setting with partial feedback, which has more practical implications.
In addition, Balcan and Beyhaghi [10] provide new guarantees for learning evenue-maximize 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 the combinatorial nature of data. Except for Agarwal al. [6], the above-cited solutions are inherently offline single-shot. While we focus on simplified yet relevant setting where data comes from a single source, resulting monotonie valuations, this work, we tackle the problem in a sequential, dynamic setting, which has practical importance. In contrast to our approach, Agarwal al. [6] considered the price to constant (i.e., a scalar rather than a price vector) to address the inherent computational intractability of multi--dimensionll 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.
Problem setting, assumptions, and challenges
seller has N homogeneous data points. There types of buyers who wish to purchase this data.
A buyer of type i E [m]] has a valuation curve n : [N] - [0, 1], where v; (n) is her value for n data points. We will assume (y(n) is non-decreasing as more data is valuable, and further that vy(()) 0.
Example 1. To motivate this model, consider seller with NN ordered data points { 2N J. drawn i.i.d. from a distribution D. If a buyer purchases n points, she receives the first n points, J. Her ex-post value ü5 (Xx, may represent the accuracy of her ML model trained with Xn, However, as the buyer has not seen the data before the purchase, she does not know which specifie points she will receive, and hence her (ex-ante) value (n) = Ex. [,,
X, =
is the expected model accuracy when n i.i.d points are drawn from D. The different types could be buyers who use the data for different tasks or models. For instance, with ImageNet's [21]. N 1.4 million data points, different types of buyers could perform different learning tasks such as object detection, identification, and segmentation, and/or train different models such as AlexNet [36], ResNet [26], and GoogLeNet [42]. Both empirically and theoretically, for many learning tasks, (n) is non non- non-decreasing. and satisfies additional characteristies such as smoothness and/or diminishing returns.
Pricing curves, buyer utility, and buyer purchase model. Let [N] + [0, 1] be a pricing curve
chosen by the seller. Let p _ {p= [ + [0.1]: p(0) 0} denote the set of all pricing curves. If a buyer purchases n points, her utility uy un(n) = 15 (n()) - p(n). If buyer can achieve non-negative utility, i.c. v. (n) 2 p(n) for some n E [NV, 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 given pricing curve a buyer of type! will purchase nt,p points where,
0
if (n) < p(n) for all n E [N], otherwise.
nip
max argmax (v:(n) p(n)))
(I)
Optimal revenue. It follows that the revenue from a buyer of type is p(ns.p). Let q = (q...... 9m) be the distribution of the buyers. Under this distribution q. the expected revenue rev(p) for price curve the optimal price poeT, and the optimal revenue OPT as follows:
m
rev(p)=
q: p(nsp),
p OPT A
argmaxrev(p)) PEP
OPT - rev(
(2)
We have omitted the dependence on g in rev, TOT 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 paPT, which will then be used in $4 and $5 to develop online learning algorithms. Unfortunately, the size of this discretization assumptions. Therefore, we also consider two additional commonly satisfied conditions by data.
be very large in N and without further
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 range [0, N]. while the valuations only have a range [0, 1J. This condition states that a buyer's valuation does not change significantly she only purchases a few additional points.
Assumption (Smoothness, S). For all n, n' E [N], we have vn(n + n') c;(n) S nn'.
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.
is decreasing with n. We will in fact make stronger assumption, and justify it below.
Assumption 2 (Diminishing returns, D). There exists some J > 0 such that, for all rypes i E [m], for all n E [N], we have (n + 1) - (n) < J
Assumption 2 quantifies the rate of decrease of diminishing returns. Following Example 1, the valuation (accuracy) curves for many learning problems take the form (n) Bn=;; for
5

---

instance, for binary classification in VC class H. a may be the best accuracy in H. 3 E (vvdn) where dæ is the VC dimension, and y == 1/2 [41]: similarly, for nonparametric regression of a twice differentiable function, and [ are constants while y 2/5 [45]. In such cases, Assumption 2 is satisfied with J = fy. Note that neither assumption subsumes the other: a non-concave Lipschitz function will not satisfy Assumption 2, while a suitable I. for function which satisfies Assumption 2 may need to be very large for Assumption to hold for small n.
2.1 Learning to price in online settings
In this work, we will also study how seller may learn to maximize revenue. In learning problem, the seller is aware of the valuation curves {wt J of each type, but does not know the distribution of types (stochastic setting) there may be such distribution (adversarial setting).
Setup. The seller repeats the data market for rounds. At the beginning of each round, he chooses some price curve pt E P. Afler the seller has chosen Pt. new buyer of type i, [ml] appears and purchases ni = Pi amount of data (see (1)). The buyer is aware of her own valuation curve. she makes purchase, that is if n4 0, she pays py (nt) to the seller and reveals her type iN Otherwise, the buyer will make no payment and not reveal her type.
We have assumed that priori, the seller is aware of the buyer valuation curves {Vi heemm. and that buyers are aware of their own valuation curves. Example 1, 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 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 clicit 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*) possible price curves, which is both statistically and computationally intractable, especially for large N. Second, in addition to the tered in sequential recision-making the seller faces 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 both stochastic and adversarial settings.
trade-off usually encoun-
Stochastic setting. Here, there is some fixed but unknown distribution of types On each round, a buyer of type i, ~ q is drawn independently. The optimal expected revenue OPT under type distribution y is as defined in (2). The regret Rt is as defined below. We wish to design algorithms which have small expected regret IE (.). where the expectation accounts for both the sampling of types i, g and any randomness in the algorithm. We have,
T po(ma) = T OPT Σ po
T
RT A TP
Σ
Ad Adversarial setting. Here, the types on each round {1e)==1 are chosen arbitrarily, possibly by an oblivious adversary, ahead of time. The type on round is revealed to the seller only at the end the round, and only if there is purchase. In the adversarial setting, define our regret Ry with respect to the single best price in P in hindsight. We wish to design algorithms with small expected regret R[r)), where the expectation is with respect to any randomness in the algorithm. We have,
T
RT
max PEP
p(nie.))
Σ (e tm1
(4)

---

Algorithm 1 Price discretization scheme under monotonicity
Given: Approximation parameter > O.
Let W be discretization of the valuation space [0, 1] defined as follows,
Z, c(1+ vie 0,
logite 1
1}
[oggic #1
W; - Zi-1 Zi-1
ek m
vk E (1,2, [(2 ()m++)
w
W
i=1
Set P to be the class of all "m-step" functions mapping [N] to W.
3 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 E [m], and the type distribution q. Our goal is to design discretization so as achieve revenue within gap of (e) from OPT. Before discussing our discretization algorithms, we first show that the optimal pricing curve is "simple" when there are at most types.
types with non-decreasing value curves [ti)ie[m) For any non- decreasing price curve p. there exists an "m-step" " price curve p that yields expected revenue at least that of p with respect any distribution over the m rypes. Here, m-step refers to non-decreasing functions f [M] - [0, where {(n 11
Lemma 3.1. Assume there
> f(f))
in at most m points (i.e., at most m. jumps). f(n)
Lemma 3.1, proven in Appendix A.I, will be an important tool in all three discretization algorithms of this section. It will allow to reduce the space of pricing curves we only need to focus on m-step price curves. Next, we present our first discretization procedure Algorithm 1, which only assumes the monotonicity of the valuation curves.
Discretization scheme under monotonic valuations. Our discretization proeedure, outlined in Algorithm/ 1, adapts the method in Hartline and Koltun [25] using Lemma 1. For this, we will first construct a discretization W of the valuation space as follows. Let Z, <(1 + c)', = 0, 1,.,....... l.... llogte 11 be the powers of (1 +1+6 c) on price space [c, 1]. For each i, we let W; be uniform discretization of the interval [Z Zi41) uniformly with gap Zi-1 <. Finally, let W be the union of all such W. According to Lemma 3.1, every price function in P has the same revenue as an m-step function. We set to be all choices of non-decreasing m-step functions that take value in W. We have the following theorem about Algorithm I which prove in Appendix A.2.
Theorem 3.1. Consider the discretization P as constructed in Algorithm 1. For any type dis- tribution, there exists p- P such that rev(p) OPT O(c). Moreover, we have P S [e(N-)) m (c[(2 m
c)] c)1 [logi+e mm)mm ((
(N
Discretization scheme for smooth monotonic valuations. Due to space constraints, we present algorithm, under Assumption I in Appendix A.4. We have the following theorem about Algorithm 5.
Theorem 3.2. Consider the discretization P constructed in Algorithm 5. Under Assumption I, for any lype distribution, there exists p E P such that (p)(p) 2 OPT - O(e). Moreover, [P] E
O (logT++ (1/e) (o/e))-L////) (L/e)")) E (($) m
Discretization seheme for monotone valuations under diminishing returns. Finally, we study dis- cretization schemes under the diminishing returns condition. Our procedure, outlined in Algorithm 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, will need to do more densely when is small. For this, let Y, 2/m (1 E?)s, Ne² i= 0, 0..., [log++ 20ml be the powers of (1 + e?) on data space [2 .V.. For each i, the set Q: further partitions the interval [Y, Y(+1) uniformly with gap Y, 2/m For a smaller than 2// 2t we do not discretize it as the valuations may change rapidly when n is small. Let Np be the union of
7

---

Algorithm 2 Price discretization scheme monotonic valuations under diminishing returns
Given: Diminishing returns constant J, approximation parameter 6.
Let W - Dog1++ W, were W,s are the same in Algorithm 1.
Let ND be discretization of the interval [0, .] defined as follows,
Y
-
2Jm (1 (1+
i= ,.=0 0,
logi+22 Ne²
2Jm )
10g
Nx2 25m
Q A/ {
2h
[25m] }. Q
Yi+ Yi
h == ==0,1, 1.......
Qi.
2Jm
t=1
ND -
1,2,
2Jm
UQ
e²
The discretization price set P is the class of all "m-step" price eurves on function space ND - W.
[1, ..... 2J } and the set Qi Therefore, ND has a size of at most - + mm llgg+e2 2.m We have the following theorem about Algorithm 2 which we prove in Appendix A.S.
No2
Theorem 3.3. Consider the discretization P as constructed in Algorithm 2. Under Assumption 2, for any type distribution, there exists E such that rev(p) > OPT - -O(). Moreover,
P E O ((2
m
(Ne Jm
(logit 1/e) =0 [0(()))
log. m
Proof outline. By Lemma 3.1, may assume the optimal price curve p" {(n pi) is an m-step function, where p. denote the value of p on step i. We generate an m-step price curve p (:)) on space Np
W such that n; is obtained by rounding down nł the closest value ND. and pt 2 p /(1 + <). We then show that if buyer purchases at step i under price p", she will not purchase step j < i under new price p. Therefore, the revenue from this buyer is at least p; 2 p (1 +) p. Oc)), which ensures that rev(p) 2 OPT O(c).
4 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. which has the largest UCB on the revenue.
The key challenge lies in constructing UCB. As P is large, naively constructing UCB over prices
in P will lead to P 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 an alternative setting where we observe the type regardless of purchase, this like a full information feedback because observe the type, we know the revenue for all prices. Then
UCB gives us / log(( (PIT log 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 given round, which is random quantity depending the algorithm itself.
Construction of UCB. We will now show how to construct the upper confidence bound rev, at the end of round I, which will be used in computing Pt+ For S I, let S,, defined below in (5), be the set of types who would have purchased in round 7 at price pr had they appeared that round. Then, for any type E [m]] we define T,, to be the number of times that type appears in set S, for
8

---

Algorithm 3 Online data pricing in the stochastic setting.
Given: time horizon T, discretization P of price curves.
Set P1 to be the zero function.
# Give data away for free on round 1.
A buyer of type i1 q arrives and purchases N data points at price for t = 2 to T do
Compute the UCB rev;-1(p) on the revenue of p for each p P.
# See (5), (6), and (7).
Set Pt argmaxpe7 rp)
A buyer of type q arrives, purchases ni,,p points, and pays pt (P)
end for
T E (l,..., .......,, l). That is, T3, measures the number of times a buyer of type i would have purchased during the first t rounds. We have.
S, - E [m] En E [N], v;() - pr( 2 0},
Tre Σ T(i E S,) 7=1
(5)
Note that as we use the price function on round 1, i.c. p1(-) = O, we have Tū, > 0 for all t > 1. Next, estimate 9, via the fraction of times that type i has appeared in the past rounds, provided that S, for t E tt.. We have defined this quantity, Tr below in (6). Via standard application of Hoeffding's s incquality, can show that T.,1 (log T)/Ta, with high probability. Using this, we can construct an upper confidence bound B. as follows,
log Tre
T
I(i IiiES,,i =),
Th +
(6)
T
T=1
We now translate the UCBs on q to the UCBs on the revenue. Recall from (1) that buyer of type i will purchase Ri,p points at price and the revenue from this buyer will be p(n.,p). Note that as the seller has access the valuation curves, he can compute ni.p for any and price curve p. Since rev(p) (p) = (E:.)p((nap))) we have the following natural UCB for rev(p) on round t:
m
(p)
Fia p(n..p).
This 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 we use a discretization P which O(1/TT) additive approximation to any price curve. Then, the regret of Algorithm 3 satisfies E[RT]] E ((mVT).
Proof challenges. When bounding the regret, first observe that the subsets S [m]] induces partitioning of the price curves, where belongs to the partition of S, if all types in S would make a purchase at price p. and all types in S would not make purchase at price p. With this insight, can view the action of a seller as not just choosing a price curve, but also choosing a set S, C [m]. That is. St can be viewed as a super-arm combinatorial semi-bandit problem [37].
5 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 algorithm such EXP-3 [9] results in large ((T7) 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 0.
For each p E P. sample 0g from exponential distribution with pdf de -02 for t = 1 to T do
Set price curve for the current round Pt = argmax Σ (r)
+ 0z.
PEP ==1
A buyer of type is arrives, purchases a. points, and pays pe(mie.p.). if Pi > 0 then Set rp() p(m ) for all p E P. else Set (p) Eiesy p(map) for all p E P. end if end for
# If there was purchase
# See (5) for Se-
this equivalent to full information feedback, where algorithms such as Hedge or Follow-the- perturbed-leades (FTPL) [31] yield O(T' log"> (P)) regret, translating to ((mTT)Va) 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 (mm3/21"/)) 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 8, from an exponential distribution with pdf 0e Orr for each pricing curve p in P. It maintains rewards (re(p) htp for each round and price curve p. On each round, it chooses the price curve that maximizes the perturbed cumulative reward Σ (p( + 0p.
This scheme is similar to FTPL., but the key difference in how we design the rewards (rr(p) (..p To describe this, let Sc, defined exactly as in (5), be the of agents who would have purchased in round at price Pt. At the end of the round, if there was a purchase, for all prices p P, we set the reward to be rz (p) = pp)...p) i.e. the payment we would have received from the buyer at that round, purchase,
know that & St, in which case set re (p) = Eies; p(n..p). ). In this case, Te (p) is an upper bound on p(ns.pp). and this upper bound is tight around prices similar to the chosen price pr; in fact, (p() = 0 if there was no purchase. Intuitively, re(p) deals with the uncertainty of not knowing the type on round t by providing large reward (as we are taking the sum) 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.
had the price been (see (1)). If there
Theorem 5.1 provides 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 Õ (Tm)/VT) VT) regret.
Theorem 5.1. Suppose in Algorithm 4 we use a discretization P which is O1/ /T) additive ap- proximation to any price curve. Lei Por be as defined in (4), Then, for Algorithm 4, we have E[[T]] e
O (m2 BT + 8-1 (1 (1+ log P))). Setting =
1+ log P
we have TE| Rr] E Om fim/Tloon Tlog (P).
6 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 propertics. 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:
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 typically small or bounded. While the overall computational cost grows exponentially with the number of types due to the problem's s strong NP-hardness (see [14]), this design choice ensures computational feasibility in settings with large datasets and limited number of types.
10

---

References
[1] AWS Forecast. https://aws. amazon. www.:aaaaaan..mooooaaaoooaaaa com/forecstto///ooooooooo Accessed: 2024-05-12.
Accessdd
[2] AWS Data Hub. https://ass amazon. http:///waaaaaa.a.ooo/////aaaaaa Accessss 2024-05-11.
[3] Azure Data Share. http:////aaa..aaaooooooooo/oo//r Ac- cessed: 2024-05-10.
[4] Delta Sharing. cessed: 2024-05-11.
www.ddaaaa...oo///ooo...... http:///ww....tattttt..../////aa html.
[5] Ads Data Hub. cessed: 2022-05-10.
Ac-
[6] A. Agarwal, M. Dahleh, and T. Sarkar. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference Economics and Computation, pages 701-726, 2019.
[7] A. Agarwal, M. Dahleh, Horel, and M. Rui. Towards data auctions with externalities. arXiv preprint arXiv:2003.08835, 2020.
[8] P. Auer. Using confidence bounds for exploitation-exploratio trade-offs. Journal of Machine Learning Research, 3NNov):397-422 2002.
[9] Auer, N. Cesa-Bianchi, Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77 2002.
[10] M. F. Balcan and H. Beyhaghi. New guarantees for learning revenue maximizing menus of lotteries and two-part tariffs. Transactions on Machine Learning Research, 2024.
[11] O. Besbes A. Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6))1407-144 1407-142,, 2009.
[12] O. Besbes and A. Zeevi. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science, 614)7723,,73, 2015.
[13] Chawla, J. Hartline, and R. Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference Electronic Commerce, pages 243-251, 2007.
[14] S. Chawla, R. Rezvan, Y. Teng, and C. Tzamos. Pricing ordered items. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 722-735, 2022.
[15] W. Chen, W. Hu, F. Li, J. Li, Y. Liu, and Lu. Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29, 2016.
[16] X. Chen, I. Diakonikolas, D. Paparas, X. Sun, and M. Yannakakis. The complexity of optimal multidimensional pricing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,, pages 1319-1328. SIAM, 2014.
[17) W. C. Cheung. D. Simchi-Levi, and H. Wang. Dynamic pricing and demand learning with limited price experimentation. Operations Research, 6526): 2017.
[18) Citrine Informatics. Citrine Informatics Accelerating Materials Innovation. URL: https:
// //citrine. io/, 2024. Accessed: March 2024.
[19] A. V. Den Boer. Dynamic pricing and learning: Historical origins, current research, and new
directions. Surveys in Operations Research and Management Science, 20(1):1-18, 2015.
[20] A. den Boer and Zwart. Simultaneously learning and optimizing using controlled variance pricing. Management Science, 60(3):770-783, 2014.
[21] J. Deng, W. Dong, R. Socher, Li, K. Li, and Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255 Icee, 2009.
11

---

[22] M. Dudík, N. Haghtalab, H. Luo, R. E. Schapire, V. Syrgkanis, and J. W. Vaughan. Oracle- efficient online learning and auction design. Journal of the ACM (JACM), 67(5):1-57, 2020.
[23] W. Guo, N. Haghtalab, K. Kandasamy, and E. Vitercik. Leveraging reviews: Learning to price with buyer and seller uncertainty. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 816 (16686,,22 2023.
[24] V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximzzing envy-free pricing. In SODA, volume 5, pages 1 1164-1173, 2005.
[25] J. D. Hartline and V. Koltun. Near-optimal pricing in near-linear time. In Proceedings of the 9th International Conference on Algorithms and Data Structures, WADS' 05, page Berlin, Heidelberg, 2005. Springer- Verlag. ISBN 3540281010. doi: 10. 10.1007/115342733 37. URL https: /doi. http://ooooooo..//.// 1007/11534278_93
[26] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[27] M. Jagadeesan, A. Wei, Wang. M. Jordan, and Steinhardt. Learning equilibria matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34:3323- 3335, 2021.
[28] A. Javanmard. Perishability of data: dynamic pricing under varying-coefficient models. The Journal of Machine Learning Research, 18(1):1714-174, 2017.
[29] A. Javanmard and H. Nazerzadeh. Dynamic pricing in high-dimensions. The Journal of Machine Learning Research, 20(1):315-363, 2019.
[30] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based on the Shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[31] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
[32] N. B. Keskin and A. Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal mymiic policies. Operations Research, 62(5):1142-1167, 2014.
[33] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594-605. IEEE, 2003.
[34] A. Krause and C. Guestrin. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology (TiST), 2(4): 2011.
[35] A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9(12), 2008
[36] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
[37] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combina- torial cani-tandits. In Artificial Intelligence and Statisties, pages 535-543. PMLR, 2015.
[38] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[39] K. Misra, E. M. Schwartz, and J. Abernethy. Dynamic online pricing with incomplete informa- tion using multiarmed bandit experiments. Marketing Science, 38(2)226 2019.
[40] G. Perakis and Singhvi. Dynamic pricing with unknown nonparametric demand and limited price changes. Operations Research, 2023.
12

---

[41] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[42] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and
A. Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 1-9, 2015.
[43] Wang, J. Rausch, C. Z.Zaang R. Jia, and D. Song. A principled approach to data valuation for federated learning. Federated Learning: Privacy and Incentive, pages 153- 2020.
[44] Y. Wang, B. Chen, and D. Simchi-Levi. Multimodal dynamic pricing. Management Science, 67 (10):6136-6152, 2021.
[45] L. Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
[46] J. Xu and Y.-X. Wang. Logarithmic regret in feature-based based dynamic pricing. Advances in Neural Information Processing Systems, 34:13898 13910, 2021.
[47] H. Zhao and W. Chen. Stochastic one-sided full-information bandit. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 150-166. Springer, 2019.
A Omitted Details from Section 3
A.1 Proof of Lemma 3.1
Lemma 3.1. Assume there are rypes with non-decreasing value curves (té)ie(m) For any non- decreasing price curve p. there exists an "m-step" price curve p that yields expected revenue at least that of p with respect any distribution over the m rypes. Here, m-step refers to non-decreasing functions f [N] + [0, 1] where f(n + (n) > in at most m points (i.e., at most m jumps).
Proof of Lemma 3.1. Fix price curve p. Let nipp be the amount of data type purchase price curve that is
nip max (nggax((((n))p(((( -
=E[N]
For (eemm) let [m]] + [m]] be permutation such that (x(1) S 12(2),p S... S #x(m).p 2 nx(1). Then, define a function p [N] - [0, 1] as follows,
Let (())
p (na)) (n(2))
n S n()))
n(1) < n S n(2))
p(n)= a
(m(m-1)),
mmm 2) < n2 S Ri(m-1)>
(n(m)
(mm-1) < n < N,
so that has most m steps. Then, has following properties,
p(n) = p(n), when n E {m(a) R(2). ..., (mm)) f(n) < p(n), when [N] (ma), (()) ................................ (1m))
We next prove that for any i [m/] after changing the price function from the type buyer either purchases at (nt.p- p(n.,p) or at (N, p(m(m))).
For any type and any amount of data I n(m). there exists & such that n(k-1) < n S ((()) (let (o0)) = 0), we then have
(n) - p(n) S va (n(E)) - p (T(())
(as is non-decreasing and 5 is step function.)
ia (R()) P (R(R)
(as (T()) p (n()))
13

---

S (m(pp))) - p(n..p)
(as ntp maximizes the buyer's 's utility.)
((i.p) p(ni.p).
(as p(n..p) = p(ms,p))
As shown in the above, type i still prefers purchasing nip data over all n S R(m) under price y-
For n E (m(m) + 1. +1....,N? N,,,,,J.. by the monotonicity of value curves, we have
N max
nE (E(( + (u:(n) ((10)-p(())) =(n))
arg max
Therefore, for any i E [m]) type i either purchases at (ni.p. p(D:.p)), or purchases at ((N) = (N, (m)())) under price p. No matter which case, type contributes no less revenue under p than It then follows that, for any type distribution q.
rev(p) 2 rev(p).
A.2 Proof of Theorem 3.1
In this subsection, we prove Theorem 3.1 by decomposing it into three technical lemmas (Lemma A. 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 discretiza- tion.
Lemma A.1. For any type distribution, there exists pricing function p: [N] - [c, 1] such that
rcv (p) 2 OPT
Proof of Lemma A.I. Consider the optimal pricing function p" [N] - 10.11,ie, OPT = rev(p"). Consider price curve p [N] + [e, 1] where j(()) = max (n)).
Let {n E [N]: F(n) p" [n:) } be the set of data quantities whose price under ÿ are the same as those under p. Any buyer type who would have purchased 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) = e > ("(n for n & J, the expected revenue contribution from such buyers under p" is at most e, hence no matter they purchase or not under we have rev(p) 2 OPT
amount of data under pd will
Lemma A.2. For any P. E (c, 1) there exists p' P such that rev(p') rev(f)/(1 c), for any type distribution
Proof of Lemma A.2. For buyer types, by Lemma 3.1, there exists a non-decreasing step function p E (e, 1| with at most m steps, whose expected revenue is at least rev(ğ). Assume p has k steps, l < To simplify the notation, for 1 I j < k, let Py denote the price p jth step. That is,
Pi, n E (0, (0,i]nz.
P2, ne 72,
p(n)
Pk. n E (ia-1, nz.
Where i1,..., 11 [N] are discontinuities in Recall the definitions of and W as stated in Algorithm 1,
{ 0, ..... logi+e 2 (13 7 = =
7, ((1+))):Vic
Jogio #e
w, 2 Zi-1 + Zi-1 ck Ak E f1,2. [2 +)mmc (22
w $
W
14

---

Let is N and for each E [k], let Zi, be the price obtained by rounding P, down to the nearest
value Z. By constructions of Z and W above, Wi, is a partition of interval (Z,,-1: 2 +1 1). Let
wj be the price obtained by rounding Pj down to the nearest value in Wi, Set d _ = Zi,- -1 and
consider k-step function p defined by whose price at jth step (denoted pj) is wj (j - 1)d, E W that is
P1 W1.
for n E (0, nz, for E (i1, n 2
p2 W2
d2,
p(n)
Pk wk
(k: 1)dk. for n E (i
By the tie-breaking rule and the monotonicity of valuation curves, buyers only purchase among 0, 1,41, d...,, it number of data under p and p.
Subclaim. Then, p and p satisfies the following
rev(p) 2 rev(p)((1 +c),
(8)
with 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 data under would prefer iy 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 the buyer's utility for i, data is Pj- Pj- which is higher than the increase py Py for 2 data. Formally, this can be seen as follows: For any j' < j we have,
Pj Pj 2 wj Pp
-
P== (j 11),
Pj 2 wj and pj wjj 1)dj- Moreover,
Dj < wy dy Py Pj < wy + +d,- Pj = j''d..
(9)
The inequality Py < wy + dy holds because my is the result of rounding down po to the nearest value in W...
By constructions of sets Z and W, we have d, 2 d, which implies (j - 1)d1 2 j'dy. Then, by combining the above inequalities, we obtain
Pj P. (j 1)d 2 j'dz 2 py. Py-
(10)
Consider buyer with value curve v who prefers to purchase at i, under price p. then it must be v(i,) - P3 > v((y)) - Dz--
(11)
Then, by combining (10) and (II), we have
o(is) Pj > v(iy) Pj
therefore the buyer would not purchase at ig < is under p.
Step 2: Next, we claim that pj 2 p,/(11 + +e) for all step j E [k]. Since Zı, is obtained by rounding
D, down to the nearest value in Z, we have
p 2 Z, Zi -1 + eZi,-1 Zi mdy.
(12)
By (9) and the above, we have
Pj 2 P, - jd, 2 -1 (m j)d 2 Zi,-1,
where the first inequality is by (9), the second is by (12), and the third is because $ j.
Then, follows that
py - Sj dg =e 3. -. Zz,-1 S c Z. = Pp p12pp/(1+e)
15

---

So far we have proved Pj 2 p,/(1++ e) and no type wants to change their preference to smaller amount of data under p. If one type purchase pe under p and Pa under p for 2 then Ph 2 p: 2 p1 + 6). Therefore, we have
rev(p) 2 rev(i)(11+ rev(0)(1++))
Since the construction of price p not relevant to type distribution, the above holds for any type distribution 4, which proves the subclaim. L
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 non-decreasing price curve p' E P from such that
rev(p') 2 rev(p)((1+c),
Let S - fi E [k] 3j s., p.}. If is empty, this implies that p is non-decreasing. hence setting p' p. If S is not empty, define p' follows: Let p be k-step function with the same jump points .,,..., in as p. Let pl be the value of p' on ith step. Then, for i $ S, let p! = pr; and for i S, let p maxx$$5s<i>> By construction, p' is non-decreasing. Moreover, p' p on set S and p' > on set S.
Next, claim that Pj ply is non-decreasing for all j [k]. Both (Ø, PP))jEN and are non-decreasing with respect to j by the previous results. Hence,
Pj - 1/ < 14,5,,5 pT-1 Pj+1 = PJ+1 P/+1,
Dj - = P - Pj+1 = =Pj+1 - -P/+1
if $ S,
Pj 1 Pj - 1/41 f/tt1 - P2/+1s
if E SJ$+1eEss
(as p'J+1 = pt)) (as p'j+1 p'y)
pj P p/ p, 1/+1 $ P5+1 -P5+1
if S,j+1e S.
Therefore, any type that prefers purchase at jth step under p would not prefer purchasing at any step j' <j under p', and since // Pj 2 P e), we have
rev(p') 2 rev (p) (1 + ++) 2 rev rev(0)((1+e)
Lemma A.3. When n > m. P
ENN m (e + c)1 m
[ogi+e 1
Proof of Lemma A.3. For any integer i m, the number of non-decreasing i-step price function is (N-1) (W)), hence we have
m
N
[W]
P
i
m
m
[
i
m
1=0
e(N
1)
e W
m
e(N - 1)
logite 1 1)
e[(2 + c)
m
è
In the last inequality, use the fact that Finally, Theorem 3.1 follows directly from the above lemmas.
W < [(2 c)ml [og 27.
16

---

Theorem 3.1. Consider the discretization P as constructed in Algorithm 1. For any type dis- tribution, there exists p such that rev(p) OPT -(e). Moreover, we have [P] -
c(N- m
m (e + c)1 [logite 11)m (()))
Proof of Theorem 3.1. Combining Lemma A.I and Lemma A.2 together, we conclude that there exists price curve p' E such that
rev OPT 2 OPT
2e
(ev())
OPT O(e).
1+6
1
1
The size of d follows from Lemma A.3.
A.3 Price discretization scheme for smooth monotonic valuations
We study discretization schemes approximate monotone valuations under the smoothness condition in Assumption 1. Our procedure is outlined Algorithm 5. The discretization W of the valuation space follows Algorithm Additionally,
uniformly split the data space into multiples of cN I denoting them as the set Ns- We then set the discretization to be the class of "m-step" price curves on the function space Ns - 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.
Algorithm 5 Price discretization scheme for smooth monotonic valuations
Given: Smoothness constant L, approximation parameter >> O. Let W be discretization the valuation space [0, 1] given in Algorithm 1.
Let Ns be the following discretization of the interval j0, N1.
5
A
e
Ns A 8k: le E
N
mL
5
Set P to be the class of all "m-step" functions mapping Nss W.
A.4 Proof of Theorem 3.2
Theorem 3.2. Consider the discretization P constructed in Algorithm 5. Under Assumption for any type distribution, there exists p E P such that rev(p) 2 OPT - -(e). Moreover, [P] E O (logT (1/c) (L/e)")) E δ ((1)
Proof of Theorem 3.2. By Lemma 3.1, there is revenue optimal price curve p* [N] - [0, 1] which a k-step function, for some l E [m]. Where p can be compactly represented as the following set of tuples:
{(n (n2 p)), (nk. pt)}
where ....... , denote the locations of jumps and pt denote the value of p* on step E [k] (i.e. p² (n) = p for E (zt)
Next, generate a price p' using Algorithm 6, which ensures that the price p generated in the following step (13) is non-decreasing. We demonstrate that each round of Algorithm 6, we incur revenue loss of most ट. If pl; > p/-1 + č, everything remains the same and thus does not affect the expected revenue. If not, we combine the price of step i with step - 1, let
Let
P/ A p/1 - (p/ P) for = i....,R. During this process, buyers either make purchases at the same step, or switch to purchase at a higher step. Note that p - -Pi-1 E, so the revenue loss of each type is at most e. This implies that the revenue loss in each round is at most e. As there are k rounds, we lose expected revenue of at most mé. We conclude that rev(p") is within gap of from OPT, i.c., rev(p') 2 OPT
17

---

Algorithm 6 Auxiliary Price Adjustment
Input: Optimal price curve p".
Let p' =p"
for i = 2, : do
< p 1 + then
for j = i..... k do
p/ = p (pl 11-)).
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 (E: < k) represented by
((n) p1), (n/2 P2) .... (n))
Then, we define new price curve E P follows: let 5 == represented by
2N T.
J. then p is k-step function
((11,P)), .... (ng, Pk))
where
T4 8,
74
pi p4 ic.
(13)
First, we show that no buyer who purchases at step under p' would purchase 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.
u(n;) - Ps 2 v(n4) - 5 Ps
(by L/N L/N-Smoothness of u.)
N
L
r(()) 5
p1 +
N
2 v(n() - E pl + iE
(as 8
1 N N L
< L EN E.)
= v(n)) - b, + (i - 1)E
> v((() - p
0.
Then, we prove that the buyer's 's utility at n, is larger than that of ny for j < i, therefore, the buyer would not prefer buying step j < under price p.
L
v(n.) P: (u(n,) p,) 2 v(n)) - 8
v(n)) - (p. pj) (by L/N m/o-hheoth of v.)
N
L
v(n)) - 5 v(n)) - (p) - p/J - (i (5-00 j)c)
N
2 v(n() v(n() (p) - P/ (i-j)E) (as 8 N 2N
(v(n)) pd) (w(n)) - p/)) + (i (i-j 1)E
> (w(n() p²) (w(n') - pt))
(as i > j)
2 0.
(as the buyer prefers n; than nę under p'.)
Finally, fix the type distribution (g1, ........ 9.). then we have
m
J:
rev(p') rev(p) S
9h
Σ
(pl
p.) I(Type j purchase at ps under price p')
18

---

S mé
C.
(as c mé.)
Hence, rev(p) is within gap of 2e from OPT.
We then apply Theorem 3.1 to price p. Therefore, is enough consider price functions from the set W to approximate the revenue within ((e) gap. Moreover,
Ns _ {kó k .,.... 1
[N]
this discretization is of the size
N
e ((1811e (2)) m (5) m
N E TEOL (m
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 such that rev(p) Z OPT O(c). Moreover,
Pl E (
Ne
(logi+e 1/e) E ε <0((
log" m
Jmn
Proof of Theorem 3.3. For earcechh i = 0, ..... logi+ +-22
N 2.m
let Y, 2Jm + 2y and Q:
be the set {[ Yx
Yie2 2Jm
k k I..... [2Jm] i.c. Qi splits the interval [Y, Y++1l equally into
2mJ parts.
The union of Qis and the set {1, {
2Jm form set of grids [0, N), denoted by Np. There
are most 2. 2Jm logi+22
2
grids in total.
2m
By Lemma 3.1, there is revenue optimal price curve p² [N] + [0, 1] which is step function, for some [m]. Where p* can be compactly represented as the following set of tuples:
{(n], pi), (nă, ps)..... (nt. pt))
where ni..... n denote the locations of jumps and p denote the value of p" on step [k] (i.e. p" (n) = P, for E (m])
Then, define new k-step price curve via ((1.)P)) (mx.Pk))
where is given by
+- round down n. to the closest grid in ND.
Then we define pæ below. If p; < e(1 +e), let = e(1 +e); otherwise, let Zn; be the price obtained by rounding P down the nearest value Z. By constructions of Z and W above, Wn; is partition of interval (Zn;-1, 7n;++ +1). Let w; be the price obtained by rounding P. down to the nearest
value in WnG. Set _ c m
Z1 -1. Then define pt - w; d, Wa;-
First, prove for satisfying P; c(1 + c), if buyer purchases n, under price p", she will not purchase at ng, j i under price p. We prove this property separately when 2/m and n, 2Jm
2
(i) When n; 2
The buyer's utility at n, under price p is,
v(n)) - P; = v(n)) pt + (2t - pt - (v(nt) - v(n))))
(14)
Let 6; A v(n)) - v(n.). Then o; is upper bounded by,
n -1
8,
Σ
uh))
(n² nz)
n;
19

---

J
2²
J
E"
62
e
Ti
2mJ
+ 1
2m
14
2m
2m
m
(15)
where the third inequality is due to Lemma A.4. By the construction of p, we have
21
P p== 7n
8,-
(16)
m
m
Therefore, by (14), vn.)) Pi v(n)) - - 2 0, buyer's utility at n, under price p is non-negative.
Next, we claim that v(ns) - (w(ng) p₃) 2 0. To prove this, for any j < i, let 8, -
v(n;) - v(ny), then we have
v(n4)= - p: (v(ny) - Pp)
= =vn2)) - - - (v(nz) pJ) + (pt p - 6.) - (v] - - 65)
Where v(n;)= - p2_ - (v(nz) - pj) 2 0 because the buyer prefers nę over ni under price p". Recall that we have 6, 2 0, then we bound 6g as follows,
2
6, 6-85 8, S
(17)
m
By the construction of pi, we have,
cj
p - Ps (D} pi) = Zn
Zn 11
m
Ei
Ej
2 Zn.-11
(as Znn-1 2 Zng-1)
2 Zny
E
(as i >> -)
(18)
m
Therefore, combining (17) and (18) together, we have
v(n:)) ps (u(n,) pj) v(nt) rt (v(nz) -P5) 0.
We conclude that under price p, the buyer prefers n, over nj. for any j < i.
(ii) When n2 - 2Jm
In this case, n; nt. and for any j < i, we still have n, = nz. First, we prove the buyer's utility at ni under is non-negative:
u(n;) - pt = v(nt) - Pi
v(n)) pp + (pi pi)
2 v(n() P.
2 0.
Then, we show that the buyer prefers n; over ny under p:
u(n.) Pr (w((n) pj) v(n)) p (v(n)) pÿ) + (pi Pi 5,) [p) Pj 5,)
v(n)) p (w(n)) pÿ) + (pi p.) (p) pT)
> v(nt) P. - -(u(n)) Pÿ)
2 0,
where the first inequality is due to (18), and the second is because the buyer prefers n over n under p"
So far we have completed the proof that for satisfying p > 6(1 + e), if buyer purchases at n;
under price p", she will not purchase at nj, j under price p.
20

---

Then, similar to Step 2 in the proof of Lemma A.2, we have 2 the proof by observing
p
pointwise. We then conclude
Itc
rev(p) 2 rev(p") -(())
OPT -
1 1+c
Lemma A.4. When n4 >
2Jm we have nz. n4 S n4
23m +
Proof of Lemma A.4. By the construction of discretization set, n, must have the following form,
Ye Ye
e2
where Ye 2m
2 (1 + 2)r
some i', E Z. 23
2Jm
Since n is obtained by rounding down nj to the nearest grid in ND. n, satisfies the following inequality,
2K +1
"j S mn S Yv + Yv
2Jm
Therefore, we have
n2 - S Y2 + Yv (K' + +1)
14
2Jm
2 (K' +1)
E²K
= Yr + Yr
Yp + Yv
2Jm
2Jm
(K +1)
E2k
S, + Yu
Y2 + Yv
+
2Jm
2Jm
2²
Yy 2Jm
+1
e²
S ny 2Jm
Where in the last inequality, since Yr is an integer, and we have
2
n1 Yv + Yv
2 Ye, for k' 2 0.
2Jm
B Proof of Theorem 5.1
Theorem 5.1. Suppose in Algorithm 4 we use a discretization P which is O(IVVT) additive ap- proximation any price curve. Let Ry be as defined in (4). Then, for Algorithm 4, we have E[Rr]
O (m²0T 0- (1 log (P)). Setting =
14
have TE. [T]] E 0(m Tlog P)).
m
Proof of Theorem 5.1. Recall that the regret Ry for the adversarial setting is
Rr
p(),
Σ ((s,p)))
PEP
max pEP
Σ ((),,))
max PEP
Σ (((n,p)
+ max PEP
Σ r((,,)) Σ P((
(19)
Loss of revenue due to discretization
Ter (discretization regret)
We decompose Ry into two regrets. The first term the sacrifice of revenue on discretization. The second term is the algorithm regret when competing against the optimal price within the discretization set P.
21

---

According to Theorem 3.1, our discretization scheme approaches optimal revenue within gap of
2
1+e*
max PEP
Σ
p(s..p)
max PEP
r(r, 2
2xT
< 2cT.
(20)
1
Therefore, the first term can be bounded by 2c...
According to Theorem B. the second term discretization regret is upper bounded by
E Rrl - 3m Tlog P
(21)
Combining (20) and (21) together, we have,
E E| & 2eT + 3m T log P = m Tlog P)
(as E
V
Plug in the size of discretization set in Section 3, we have,
B(Rr)= = Ō m VT/
Theorem B.1. The discretization regret Ry defined in (19) has upper bound O ( (mm/Too (P]
Proof of Theorem B. We first claim that re(pt) = r(i,, Pt) all L. If the buyer make a purchase at round (, rr (p(e = r(,,, Pc) holds by definition. But if the buyer does not purchase price pt on
round 1, r(t, Pe) = 0. Since St contains all the types that would not make a purchase at Pt, we have
r(i, = 0, Vi ST. and
r(u.
Σ r((.p)) = r 0. iESE
Therefore, re(pt) = r(tt, Pt) holds for every round t E [T]. Denote p" as,
argmax p'
(i,,p))
PEP
Then, we decompose the regret as follows.
T
T
E Rr]
r(c.p") - E
rit,
T
(1c.p") - EE
Σ re(pt)
1=1
T
E
+
Σ rr(p)) - Σ (p(+)) + E
Σ 1
(22)
We bound three terms in (22) separately.
The first term. For any price p and any round I, we have (p) 2 r(ee p) by definition. Hence,
T
(r(i,,p)) - rx()))) S.
(23)
The second term. Since p argmax
Σt p(),,p) We apply Lemma B. to to,"
PEP
T
T
re(p")
Σ
re(pe+1) S 50p - Opp.
[=1
1=1
22

---

Note that both 8p, and 8p. are drawn i.idd from exponential distribution,
+ log (P]
max
0p
- 0
PEP
1 + log [Pl
E00p- S E.
max 0p. pEP
We have
T
T
S EE0pp - 0p- 1 log P
E
r((p)) - Σ re(pet1) 1=1
(24)
0
The third term. Note that for any price p E P and any round re(p) S m. Therefore we have, E (p<+1) (p:)) P (pr-1 + pt) E (re(pe))) re(p)) Pt-1 # pe] S IP (pe+1 # pt). The price curve on round / is pr, then by the price updation rule.
Σ rp) + 0p.
Pt argmax
PEP
which is equivalent to,
pp. 2 0p + Σ r (p)
Σ r (pt). Vp E P.
For all p' E P,, let 1- denote
max
0p + Σ (p)
Σ r+(00) r=1
& a-1p'
(25)
PEP
r=1
then P: = p/ is equivalent to
0 2 4-1.p'
(26)
Subclaim. If f,, also satisfies the following condition (27),
0p. 2 0p +
(p)
(p:) m, Ap P.
(27)
T=1
T=1
then Pt+1 Pt- Proof of the Subclaim. If (27) holds for all E P.
1-1 (-1
0p. 2 8p +
(p)
r + m
==1
2 0p +
rp(p)
r- (px).
(because Vp Ppe r:(p) E m))
1=1
r=1
Hence,
Pt argmax
(T(p) + 0p -P+11
PEP
Therefore, (27) is sufficient condition for p++1 = Pt. We then bound the probability of P.+1 Pt by computing the probability of (27) happening.
23

---

P P(p Pt+1) = Σ
P Ppi p) P(pt+1 = p Pt p)
PEP
Σ
P (pi p) PP (pi+1 = p p1l. c-1pp)
( (by (26))
PEP
2
Σ
P (p: = p) P (0p 20-1, + + 1, 2 2-1pp)
PEP
P (pt p) e m
PET
E -m0
2 1 m8
Therefore. P (pc + Pc-1) S ml. Hence, the third term can be bounded
T
- S m2
Σ E(r((0e11) - re(p)) S m 0T.
(28)
Set 0 log P "T
Combining the upper bounds for three terms (23), (24) and (28) together, we have
E < + log P + m m2OT E m / Tlog (P)
Plugging in the size of the discretization set (Theorem 3.1), we have, B[Rr] E Ô (m
Lemma B.1. For any E P.
re(pe+)) + 0p, 2 Σ re(p) + 0p-
(29)
Proof of Lemma B.I. We prove this by induction. For T = 0, the inequality O,, 2 O, holds by definition P1 = argmax 8p. Assume that the inequality holds for some T. Then for any E P.
pEp
T+1
I
re(p++1) + 6p,
re(p-1) + 0p, + +T+1(PT42)
re(P++2) + +Ppr42 + (141((p4+2
re(p)+2) +0pr42
Te(p) + 0
Where the first inequality is by the induction hypothesis, and the second inequality by
T+1 re(p) + 0p-
PT+2 = arg max
PEP
1
By the induction, the inequality (29) holds for any T > 0.
24

---

C Proof of Theorem 4.1
In this section, we prove, Theorem 4. our regret upper bound Algorithm We prove the theorem by first decomposing the regret into two parts: Regret with respect to the best price in discretized (called "discretization regret") and the residual error due discretization. The residual error controlled by the approximation guarantees developed in Section 3. Then, the key lemma in this appendix is Lemma C.1 which controls the discretization. prove Lemma C. using a technique adapted from Chen et al. [15].
Theorem 4.1. Suppose in Algorithm we use discretization P which O(1/VT) additive approximation to any price curve. Then, the regret of Algorithm satisfies [[ E ((mVT).
Proof of Theorem 4.1. For the sake of simplicity, we define r(i,p) p) as the revenue under type and price p. i.e, r(i,p) p(m..)) Therefore, on every round, we have r(i.: Pt) Pt pr
Recall that the regret Rr
RT OPT
Σ
Pe pe
OPO
Σ t=1
r(e,, Pt)
OPT T max (p) + T max rev(p)
Σ rie..ee)
(30)
pEP
pEP
Loss of revenue due to discretization
Ry (discretization regret)
We decompose RT into two parts. The first term is the sacrifice of revenue on discretization. The second term 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 gap of 2c
2
OPT
max rev(p) S
< 2e.
PEP
1
Therefore, the first term can be bounded
T T - T max (p) S T.T.
(31)
PEP
By Lemma C. the second term, discretization regret, is upper bounded by
E ERr] < 93m 93m/TTogg
(32)
Combining (31) and (32) together, have,
[r]] s 2cT + 93m 38mmTloo" Ō(mTT)
(as E
VT
Lemma C.1. The discretization regret Ri defined in (30) is at most ÕmmTT).
Proof of Lemma C.I. The discretization regret Riy
ER
E
T maxrrv(p)))
Σ p((e.P))
PEP
=E
Σ (r(p", it) - r())
25

---

T
E [r(p",") it) - r(pr, i)]
E [rev(p") - rev(pi)l
E [[re(pp)) rev(pe)) I(A,)] +
Σ
E [(rev(p") - rev(pi)) I[(A))
1=1
1=1
E [0p. I(A.)I
B Bpp I(A))I
(33)
We can further decompose [[[TT] into Et= E 60p, I(A,)] and Ei. E [6,, [[A5)). Where for any round i, we define the good event A, follows,
log T Tie
Vi [
qi S q. S q: +2
Σi= 1(iESr.)==))
unEs.) ) Note that I( = i) is random variable
Define Fi.t
Ti. that follows Bernoulli distribution (e)( and one can only observe I( i) when i E Sr, let F. denote the mean value first j i..d. observations of II(i, i). Then, we have
Σ l(EES.)
'logT'
log T Ti,
IP T1.
9i
>
/
Ti,t
TH,t - qi
V
Tú, =
1=0
1log T
Σ P
[Ti 9: > V
j
j=0
2 2exp(-2lopp logogT)
(-2
1=0
2
T
Where the first inequality, the event [Tay
{IT... - al
The T===a)
indicates
The
qel
log T
and the second inequality follows from Hoeffding's inequality.
We then bound the second term in (33)
E 6p. I(19) S
E [[A)]
1=1
m
log T Ti
| - 9b
V
T
2
T
1=1 t=1
< 2m.
Define event H₂ 10 <pp 8p, <2 v
log To.-1
By Lemma C.3, we know that
log T T I(Hr).
II I[A,-1, 8p, > 0)
I
0 8p. Σ 2
ieS,
26

---

It remains to prove the upper bound for Σ(= E
10 (Ar)]-
For & (I,...,7) 7) and k E 2,,, let
A
log T,
6p. > 0, 8p. 0,
mRR
ppe
+00,
and
Ag, = {i E St: Ta,-1 S mp,))
Then, we define an event
GR. - -|Ak,1 2 6xm}.
which means "In the i-th round, at least 3am types in St. has been observed at most ma, times".
Then, by Lemma C.5, we have
Σ (HH) 8p. S ΣΣ
(G Sp. 0) 6pp
k=1t=1
For [m], & Zt,t (T), define event
Gi - Ge n ni St, Tia-1 mp,e)
Then by the definitions of GR.t and gi,k,t we have
(G 5p. > 0) S
(G 6p. > 0).
3mm
VE EB
Therefore,
T I(H,). 8p. < Σ iEEp
T
8p.
I (G 6p, >0)
3mm
k=
For any price function p. define óp A rev(p") rev(p). dp we call it "bad" price. Let EB A (i E [m] type would make purchase at least one bad price).
For each type E EB, suppose i is contained in N₂ bad prices pha pl....... P..N. Let de, A 5pp, (1 [N.]). Without loss of generality, we assume 6ú,1 6ú,2
oG, Let di A di.
For convenience, we also define 5,,0 = -00, i.e., ag
2m
= 0. Then, we have
6:.0
Σ (Ha) 6p.
T
8p.
11 kG 6p, > 00
Bym
NE Ep k=1 1=1
5pc 3mm
(Gr.. Pt ===10 p1.)) p.:)
EE
8
(Gr.. Pt p..)
8.m
ie t=l
27

---

N
51.1
(Ti--1 S ma,er Pt = =P..)
3am
En N= l=
2m
2
8111
Th--1 Saa ar
log T, Pt. = p..
81,1
Bem
2m
2m
OKk
Ōigj-1
log T < <Ti,e-1 S cu
Ōig
log T, Pt pii
Bum
Ep k=
T
2m
2m
2
OKk
log I' < <Tie-1 S 50k
log T, Pi.
13
ووg
Brn
EE k= j=
ΣΣΣΣΣ
00
M;
N
OFK
2m
2
log < <Tic-1 S akk
2m
2
log T, Pt = pi.l
ōi-j11
ōig
Bam
EEEn
ΣΣΣΣ
OCk
2m
2
log T < Tip--1 S ax
1m
2
log Tú i E Se
dir 3am
Ói,
j=1
2m
2m
Ōijj
log T
OAk
log T
Ōi.j
84.5
3rm
En k=
j=1
N;
=4m
log T
Oi.5
8²
iE En j=1
N:
<1068m log T
82,5
PR
j=1 j=1
i.j
1.j
where the last inequality is due Lemma C.4. Finally, for each i EB have
N.
-
1
8
+
(ōt.
81s+1)
òg,N,
==1
1.
1=1
1
<
+
dx
Ot.N,
B..N,
x22
2
Ng,N,
,1,1
2
di,iin
It follows that
T
2
2136
IIH)) 5p. < 1068m log T
m
log
(34)
8ymiin
8,min
16 Ep
SE
E
So far, the distribution regret bound is proven. To prove the distribution--nddeeennntt bound, we decompose Σ I(Hl)) Sp, into parts:
T
I(Ha) 6p.
1 (He, 8p. (e). Σ t=1
Σ 1 [He, 6p. > -
< <T I 8p, =)) 8p.
where e > constant be determined. The second term can be bounded in the same way as in the proof of the distributionndependeen regret bound, except that we only consider the case
28

---

Sp. > e. (For each type i E EB, suppose is contained in N; bad prices P., Pi.1. Pi.......... PL,N. Let
81,1 - 6p,, (1 E (Ni)) satisfies di,1 ò1,2 ... 2 òi,N, 6. Also let ói,min N;-) Thus,
replace (34) by
T (H,, Sp. >c) m.. m. E
2136 ii 8i,i
2136m log T v
log T.
6
follows that
T
2136m² 2
Σ
[(H)) ds. +
log T.
Finally, letting
2136m² log T
we get
T
I(H) ōs. S 2122 & 9 T T.
Lemma C.2. Under good event At, for any price function p. let Sp denote the set of types who would purchase at price p. then we have
log T Tít
VE E [T], rev(p) réve(p) rev(p) +
Σ 2
iESp
Proof of Lemma C.2. When A, happens,
log Ti,
q: S Ti. S q: + 2
for all E [m]. Therefore, we have
m
rev)(p) Tut r(.p) 2 >
4 r(i, = rev(p)
and
log T Ti,
log T Ti,
(e), = Σ Raa r(.,p)
qi 2
r(i,p) rev(p) + Σ 2
iEs
The last inequality is by r(i, p) $
Lemma C.3. For each E [T) under good event A,-1, the following inequality holds,
log T Ti,-1
8p. - rev(p"))revee -re(p)) 2 Σ
Proof of Lemma C.3, When A happens, by Lemma C.2, rev(p") S rev:-1(p"),
rev(p:) 2 fév - Σ
log T Tr,-11"
iES.
29

---

It then follows that,
log T Ti,-1
6p, = rev(p") - -rev(ps) I <rvv-1(p") 1pp) -2 >
kES:
Since pr argmax, PEp reve- (p)), we have
revi-1(pr) 2 2eve-1(p").
Lemma C.4 (Theorem 4 of Kveton et [37]). can choose {ax T and {Bt b22 which satisfy the following properties: {ak)220 and {Bx) are positive and
01 02 ... and 8 B1 B2 .....
such that limg-too
lim 8 = 0. Moreover,
3k-12 Bk
04k
S 1, and
< 267.
Va
3R
Lemma C.5. On round t, if event H4 happens, then at least one event Gk.tr k E E4 happens, where
Gk.l
(|Ar,l 2 Bym}, where As, A fi T2,-1 ma,t)
and mg,t Olk
log T when 8p. and otherwise.
Proof of Lemma C.5. Assume that H. happens and that none of G2......... happens. Then |AR,t < 3.m for all & E Z4. Let Ao, = S. and Ag., SA,Ae, for h: E Z, U (0}. Thus Ap-1. C Ag,t for all E Z4. Note that lim mag = 0. Thus there exists E Z4such that Ap, = St for all & 2 N, and then we have S = UR (Ax,e Ab-11)). Finally, note that for all
i Âg,t, we have T > mA,1- Therefore
8
Σ
Σ
Σ
T1,011
Vhe-11
M
JES
k= ic AE, AAR AA-
k=
An.t's Ac-
A AAI
A A Vmkket
Vi
|SA1
Akte
Vm1.1
VmL+1e
Vmiga
m
BLm
M1,1
mk++1
V m
k=1
(B
3x) m
v mkge
1=
Under event He, we have
8pc
2
log
2og E
1
T
Vii1-1 VES,
JES.
(3
Bk) m
00
8k-1 3x
<2
8p, S 5pm
Vok
where the last inequality is due to Lemma C.4. We reach contradiction here, hence the lemma follows.
30

---

D Miscellaneous
D.1 Notations
The following table contains the notations used in this paper.
Notation
Meaning
The total amount of data.
n E [N]
The number of data.
m
The number of types.
p: [M] + J0, 1]
A price curve.
A of discretized price curves.
U; [N] + [0.
The valuation curve for type E [m]]
V {u; i E [m]]
The set of all valuation curves.
ni.p
The amount of data type E [m)] purchases at price curve p.
r(i,p) = p((i.p)
The revenue from type E [m]] under price curve
== (91, 02........ .m))
The type distribution.
rev(p)
The expected revenue under price p. The type of buyer round E [7]- The price curve on round t [2].
i [m]]
Pr [M] + [0, 1]
St
The set of types that would make purchase at price Pt.
Sp
The set of types that would make purchase price p. The number of times that type i appears in set S, for T E {1....,t)
Tv. A Σ1= I[i E S₁)
P= {p [N] [0, 1] p(0) 0}
The set of all pricing curves.
Smoothness constant valuation curves.
Diminishing return constant of valuation eurves.
Table 3: Table of notations.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We fully included paper's contributions and scope in the appendix. See $ $1.1 for the summary of our contributions.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See $6 for future works relaxing one of key assumptions of the paper.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provided the full set of assumptions. Moreover, we provided the full proofs of each Lemma and Theorem in this paper both in main text and Appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper does not include experiments requiring code.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
7. Experiment Statistical Significance
32

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurip:: http::pp./ccppblececiciiccoodddd
Answer: [Yes]
Justification: Our research conforms, in every respect, with the NeurIPS Code of Ethics.
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is theoretical and have societal impact in foreseeable future.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Licenses for existing assets
Question: Are the creators 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]
Justification: This paper does not use existing assets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
33

---

Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
34


Reviews:
[{"review_id": "lW26MArFiV", "reviewer": "Reviewer_oHSK", "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.", "questions": "See the 'Weakness' part", "limitations": "See the 'Weakness' part", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The setting is interesting, and the results in this paper seem to show improvement over previous algorithms.", "weaknesses": "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.\n\n2. 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$.\n\n3. It is unclear whether Line 6 of Algorithm 3 is computationally efficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### ***Weakness 1. Insights for discretization scheme.***\nFirst note that in order to get a discretization that approximates any price curve within $\\epsilon$, the size of such a discretization should be $\\tilde{O}\\left( 2^N\\epsilon^{-N} \\right)$, which is clearly very large.\nOur first insight is that when there are only $m$ types and the valuations are monotone, we can reduce this to\n$m$ step functions (see Line 216-223), which reduces discretization size to $\\tilde{O}\\left(N^m\\epsilon^{-m}\\right)$.\nWhile this is better, it can still be quite bad.\nHence, we explore two other assumptions satisfied by data.\nFirst, under smoothness, we are able to reduce the discretization size to \n$\\tilde{O}\\left(L^m \\epsilon^{-2m}\\right)$ by discretizing the data space $[0,N]$ uniformly ($L$ is the smoothness constant, see line 158). \nSecond, under diminishing returns, we are able to reduce this to $\\tilde{O}\\left(J^m \\epsilon^{-3m}\\log^m N\\right)$ ($J$ is the diminishing return constant, see line 162-163); in this case, we design a non-uniform discretization method to the data space $[0,N]$. The discretization needs to be denser near 0 to account for the diminishing returns structure.\n\n### ***Weakness 2. Construction of confidence interval.***\nHere is the reason why we need a confidence interval for each of the $q_i$, where $q_i$ denotes the probability of type $i$. We first construct a confidence interval for type distribution $q = (q_1,\\dots,q_m)$, then translate them to UCBs for the revenue (see line 760, Lemma D.2). Subsequently, these UCBs for the revenue are used to bound the regret (see equation 32 and Lemma D.3 in line 768). \n\nHowever, we are not aware of any union bounds which can improve the dependence on $m$. Could you please give us a concrete example of a union bound? That will help us give a better answer. \n\n### ***Weakness 3. Computational complexity.***\nSee the common response above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9S5dTctiqy", "reviewer": "Reviewer_kUrw", "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.\n\nDue 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.\n\n-----------------------\n\nEdit: following the rebuttal some of my questions have been answered and my score has been raised.", "questions": "- Can anything be done to remove the assumption that the types are known up front?\n - Can any tight lower bounds be given for the stochastic and adversarial settings (i.e., in terms of both $m$ and T$)?\n\nMinor comments:\n - In Eq. (22) in the appendix, it has $f_t(p^*)$ instead of $r_t(p^*)$.", "limitations": "The authors have made assumptions clear.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall, this is a well-written paper which introduces a very interesting and relevant problem and gives a clean description of the proposed solutions.  While the techniques for online learning are based on fairly standard ideas (UCB and FTPL), they still require some small tricks that are particular to the new setting in this paper.", "weaknesses": "There are a few concerns:\n - Lack of tightness - it is not clear to what extent these results are tight as no lower bounds are given.\n - 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.\n - 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.\n - A lack of an experimental evaluation which might help to provide further evidence of the practicality of the proposed methods.\n\nAs 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### ***Weakness 1, Question 2. Lower bounds and lack of tightness.***\nSee the common response above.\n\n### ***Weakness 2, Question 1. The finite type assumption. Can we remove the assumption that the types are known up front?***\nThis is an interesting question. We did attempt to solve this problem, but it appears to be quite challenging, and we believe it is best left for future work. The setting we study here is novel and nontrivial, even if it is less general than assuming finite types and their valuation curves are unknown. Moreover, as we have explained in lines 133-138 (Example 1) and 164-168, it is also motivated by some practical use cases.\n\n### ***Weakness 3. Once given the discretization scheme, our method uses fairly standard techniques.***\nSee the common response above, Novelty in Sections 4, 5.\n\n### ***Weakness 4. A lack of an experimental evaluation.***\nSee the common response above.\n\n### ***Organization of the appendix.***\nYes, we agree that the appendix could be organized better and will reorganize it in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5oda74FAOi", "reviewer": "Reviewer_3dYq", "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.", "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? \n2. 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? \n3. 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": "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The topic related to marketplaces is very interesting. This paper is well-written and easy to follow.\n\n2. The authors propose three types of price discretization schemes under different assumptions: monotonic valuations, smooth monotonic valuations, and monotonic valuations under diminishing returns. These schemes, based on Algorithm 1, significantly reduce the discretization size. While Algorithm 1 is an existing technique, the proposed price discretization schemes are non-trivial and add substantial value.\n\n3. The proof provided is rigorous, and the theoretical results demonstrate sublinear regret with respect to $T$.", "weaknesses": "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.\n\n2. 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.\n\n3. 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}) \\)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### ***Weakness 1. Main contribution of our paper lies in Section 3, as the techniques in Sections 4-5 seem to be standard.***\nSee the common response above, Novelty in Sections 4, 5.\n\n### ***Weakness 2. Contribution in Section 4.***\nSee the common response above.\n\n### ***Weakness 3. Why is it necessary to add perturbation.***\nAdding perturbation is standard in the FTPL method as it ensures robustness against adversaries and helps bound the regret. For a classic introduction to FTPL, please refer to the following paper:\n\n- Kalai *et. al.*, Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 2005.\n\nHowever, for reasons explained in the common response, the vanilla FTPL does not work under asymmetric feedback. Especially, in line 320, $r_t(p)\\geq p(n_{i_t,p})$ is by definition (see lines 6-7 of Algorithm 4). When the buyer makes a purchase, $r_t(p)=p(n_{i_t,p})$; otherwise, since $i_t\\in S_t^c$, we have $r_t(p)=\\sum_{i\\in S_t^c}p(n_{i,p})\\geq p(n_{i_t,p})$. For specific difficulties and new techniques, please refer to our common response above.\n\n### ***Question 1. Construction of the discretization set.***\nFirst, in Lemma 3.1, we prove that for any non-decreasing price curve $p $, there exists an $m $-step price that yields at least the same revenue as $ p $. Here, an $m$-step function is a non-decreasing function where $ p(n+1) $ and $p(n) $ differ at most $m $ times, i.e., at most $m $ jumps. See lines 216-223.\n\nThen in Algorithm 1, let $W$ be the discretization of the valuation space $[0,1]$. We define the discretization set $ \\overline{\\mathcal{P}} $ to be the class of all $m $-step functions mapping $[N]$ to $ W $. This means that we select all possible $m $-step functions that have a domain in $[N]$ and take values in $ W $.\n\n### ***Question 2. Tightness of the regret bound and compare it with existing results.***\nSee the common response above.\n\n### ***Question 3. Unique contributions in Sections 4 and 5.***\nSee the common response above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f5TAXEJq2x", "reviewer": "Reviewer_oJtn", "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.", "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.\n2. 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": "See weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and introduces an interesting online learning problem in data pricing. It explores the unique structure of the optimal pricing curve in this problem and provides algorithms to solve this task under both stochastic and adversarial settings with theoretical regret bounds. The paper also discusses its technical contributions in deriving theoretical results.", "weaknesses": "(1) Computational Complexity: The provided algorithms (Algorithm 3 and 4) have computational complexity depending on the horizon $T$, which can be large in practice.\n\n(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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### ***Weakness 1. Computational complexity depending on the horizon $T$.***\nAs mentioned in line 58, achieving sublinear regret in online learning requires choosing $\\epsilon$ that vanishes with longer time horizons, i.e., $\\epsilon \\to 0$ as $T \\to \\infty$. In Theorems 4.1 and 5.1, we choose $\\epsilon = 1/\\sqrt{T}$ to achieve regret upper bounds $\\tilde{O}(m\\sqrt{T})$ and $\\tilde{O}(m^{3/2}\\sqrt{T})$, respectively. However, if one does not want the per-round complexity to scale with $T$, one can fix the error as a constant $\\epsilon$. Then the discretization size $|\\overline{\\mathcal{P}}|$ would be $\\left(\\frac{N}{\\epsilon}\\right)^m$, which is no longer dependent on $T$. With a slight sacrifice of the seller's revenue, the regret bound in Theorem 4.1 would be $2\\epsilon T + 93m\\sqrt{T \\log T}$, and the regret bound in Theorem 5.1 would be $2\\epsilon T + 3m\\sqrt{T \\log |\\overline{\\mathcal{P}}|}$.\n\nThis is standard in continuous bandit, we choose the discretization size to scale with $T$ to achieve the lowest possible regret bound, which causes large computation complexity at the same time (for a classic example, see [1]).\n\n### ***Weakness 2. Lack of Numerical Validations.***\nSee the common response above.\n\n### ***Question 1. Can we reduce discretization additive approximation?***\nYes, it is possible to replace the size of the discretization from $O\\left(1/\\sqrt{T}\\right)$ with $O\\left(1/\\sqrt{t} \\right)$ in the stochastic setting. This will reduce the computational complexity, but only by a constant factor, so it does not give a fundamentally different result. See the common response as to why we think large computational complexity is unavoidable for this setting.\n\nIn the adversarial setting, we believe that it is not possible to reduce $O\\left(1/\\sqrt{T}\\right)$ to $O\\left(1/\\sqrt{t}\\right)$.\n\n### ***Question 2. How can the Upper Confidence Bound (UCB) on type distribution $q$ facilitate exploration in learning $q$?***\n\nIf type $i$ has not been explored enough before, then $T_{i,t}$ is small, and the upper confidence bound for $q_i$ is large. We let $S_p$ denote the set of types that would make a purchase under price $p$. Then for all prices $p$ such that $i\\in S_p$, their UCBs for revenue (defined in Eq. 7) are large. Therefore, the algorithm tends to choose $p$ satisfying $i\\in S_p$ in the following rounds, leading to an increase in $T_{i,t}$. This encourages exploration of type $i$.\n\n### ***Reference***\n\n[1] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online\nposted-price auctions. FOCS 2003.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their feedback. First, we would like to address common concerns raised by reviewers.

### ***On technical novelties***
While all reviewers agree on the novelty of our discretization scheme, there is a perception that Sections 4 and 5 simply apply UCB/FTPL to this discretization. However, there are nontrivial adaptations in the algorithm and the analysis to account for the asymmetric nature of the feedback. Specifically, the type is revealed only if a purchase is made, and feedback under one price curve can be shared across all prices.

- **Stochastic setting (Sec. 4)** If we naively apply UCB by only accounting for feedback for the chosen price curve, we get a $\sqrt{|\overline{\mathcal{P}}|T\log T}$ upper bound, where $|\overline{\mathcal{P}}|$ is the size of the price set, leading to poor, often exponential dependence on the number of types $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. In this full information setting, UCB gives us $\sqrt{T\log|\overline{\mathcal{P}}|\log T}$ $\in \tilde{O}(\sqrt{mT})$ upper bound. We are in an intermediate regime between bandit feedback and full information: if a type purchases at one price curve, we know what they would have purchased at other price curves. However, if there is no purchase, we do not know the type of the buyer.  

    We account for this asymmetric nature by noting that the key unknown is the type distribution. In the full information setting, we use the sample average of each type to estimate the type distribution and then translate this to confidence intervals on the revenue. In our setting, as the type is unknown if there was no purchase, we only count the types in $S_t$ if a particular type would have made a purchase anyway (Eq. 5, 6). The key challenge is in showing that the confidence intervals we have designed are valid, which requires a delicate analysis.

- **Adversarial setting (Sec. 5)** In the adversarial setting, we adapt the FTPL algorithm, which is for full information and does not apply to our setting directly. When there is a purchase, we set the reward similarly, but when there is no purchase, we do not observe $i_t$. Our approach in line 7 of Algorithm 4 is to set $r_t(p)=\sum_{i\in S_t^c}p(n_{i,p})$ for $p\in\overline{\mathcal{P}}$, where $S_t$ contains types who would have purchased in round $t$ had they appeared in that round.

    When the buyer does not purchase on round $t$, the seller knows that $i_t\in S_t^c$. We define the reward for each price function as $r_t(p)=\sum_{i\in S_t^c}p(n_{i,p})$, an upper bound on the true revenue $p(n_{i_t,p})$. For prices possessing the same set $S_p$ with $S_t$, this upper bound is tight, i.e., $r_t(p)=p(n_{i_t,p})=0$. As mentioned in lines 321-324, $r_t(p)$ deals with the uncertainty of not knowing the type on round $t$ by providing a large reward to prices that could have resulted in a purchase, encouraging exploration of such prices in future rounds.

### ***Lower bound***
Indeed, we were able to prove a $\Omega(\sqrt{T})$ lower bound in our setting. This is tight in $T$ but not in $m$, but we decided not to include it because one does not expect to do better than $\tilde{O}(\sqrt{T})$ anyway. (In hindsight, we think it might be better to include this, as the proof required some slightly different techniques to standard hypothesis testing arguments)

To get a tight dependence on $m$, we need to account for the asymmetric feedback in the proof of the lower bound. This appears to be challenging, and we are unaware of techniques to handle such feedback. The closest we could find is [2], who provide a $\sqrt{T\log K}$ lower bound for a $K$ armed bandit setting with one-sided feedback, but their techniques are not applicable here.

### ***Computational complexity***
Yes, our algorithm is computationally expensive (i.e., the running time depends exponentially on the number of types $m$), but this is inevitable as even the offline version of our problem is strongly NP-hard (see [1] and lines 449-463 in our paper). Our goal was to develop an algorithm that is efficient in the number of data points $N$ given that the number of types $m$ is a fixed constant, which is relevant in practical scenarios.

An interesting question is developing an online PTAS (Polynomial Time Approximation Scheme), an algorithm that guarantees sublinear regret with respect to an approximately optimal price with a fixed approximation factor. While this was not a focus of our paper, the offline PTAS from [1] can be generalized into our online setting using our online algorithms in Sections 4 and 5. In future revisions, we will address the issue of computational complexity more explicitly as shown in this rebuttal.

### ***Numerical evaluation***
While we agree that empirical evaluations would be helpful, we believe our theoretical contributions are valuable on their own. Furthermore, it is common and acceptable for theoretical papers at NeurIPS to not have empirical evaluations.

### ***Reference***

[1] Chawla et al., Pricing ordered items. STOC 2022.

[2] Zhao et al., Stochastic One-Sided Full-Information Bandit. ECML PKDD 2019.

Meta-review: 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.
Decision: Accept (poster)