Learning to Price Homogeneous Data

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.

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.

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

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

Edit: following the rebuttal some of my questions have been answered and my score has been raised.

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.

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.

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.