Learning to Price Homogeneous Data

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.

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. (2) Lack of Numerical Validations: Since the problem is motivated by a practical pricing scenario, numerical experiments could help validate the efficiency of the algorithms, especially given the potentially large computational complexity.

Questions

1. In Theorems 4.1 and 5.1, can the discretization additive approximation $O(\frac{1}{\sqrt{T}})$ be replaced by $O(\frac{1}{\sqrt{t}})$ while maintaining the same order of regret (i.e., the discretization level changes across the periods)? The intuition is that when the estimations of $q$'s are inaccurate, we may only need an inaccurate discretization of the price curve, potentially reducing computational complexity. 2. How can the Upper Confidence Bound (UCB) on $q$'s facilitate exploration in learning $q$'s (i.e., more explorations)? My understanding is that to learn $q$'s (i.e., collecting samples of $q$'s), we need to encourage purchases by setting a price curve lower than the estimated optimal one. However, the UCB on $q$'s does not obviously encourage lower prices.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See weaknesses.

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.

Strengths

1. The topic related to marketplaces is very interesting. This paper is well-written and easy to follow. 2. 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. 3. 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. 2. You claim that your analysis when constructing the UCB in this way is non-trivial since the types are observed only if they make a purchase. However, this seems common. Could you elaborate on the additional difficulties for the UCB algorithms in your case? Additionally, in line 266, maintaining UCBs for the type distribution appears to be a standard approach, and I don't see this as a significant contribution. 3. Section 5 is a little confusing. Why is it necessary to add perturbation? Maybe you should give me some intuition. Moreover, in line 320, why is \( r_t(p) \) an upper bound on \( p(n_{i_t,p}) \)?

Questions

1. While I understand that Algorithm 1 is for price discretization, and the valuation space is discretized, it remains unclear how the price set \( \bar{\mathcal{P}} \) is determined. Could you provide more details on this process? 2. Although you have provided the regret bound, additional discussion on its tightness would be valuable. Can you elaborate on the tightness of the regret bound and compare it with existing results? 3. Sections 4-5 discuss the online learning algorithms. Could you highlight the specific difficulties you encountered in these sections? What new techniques did you develop? What are your unique contributions? Clarifying these points will help distinguish your work from standard techniques.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

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.

Summary

This paper considers a data pricing problem in which a seller has $N$ homogeneous data points they wish to sell access to. The seller sets a price curve $p(n)$ which specifies the price a buyer must pay for access to $n$ data points for each $n \in [N]$. Upon arrival, a buyer sees the price curve, and chooses an amount $n$ by maximizing their utility $u(n) = v(n) - p(n)$, where $v(n)$ is their valuation curve. The buyer leaves without making a purchase if their utility is negative for all $n$. It is assumed that there are $m$ buyer types, where all buyers of type $i$ have the same valuation curve $v_i$, and that there is a distribution $q$ over buyer types in which the arriving type is sampled i.i.d. from $q$ in each step. The objective is then to find a price curve which maximizes the expected revenue over this distribution. This paper focuses on online learning settings in which the distribution is unknown and must be learned or the arrival sequence is arbitrary and we want to compare to the best fixed price curve in hindsight, where now the goal is to minimize the regret. Due to the nature of this problem (a relation to revenue maximization with unit-demand buyers), computing the exact optimal is intractable, so approximations are considered. This is done by discretizing the space of valuation curves. The main result of this paper are new discretization schemes for this problem which can accommodate various further assumptions such as smoothness or diminishing returns in the valuation curves. These are then applied to develop algorithms with regret $\tilde{O}(m \sqrt{T})$ and $\tilde{O}(m^{3/2} \sqrt{T})$ in the stochastic and adversarial settings, respectively. ----------------------- Edit: following the rebuttal some of my questions have been answered and my score has been raised.

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: - Lack of tightness - it is not clear to what extent these results are tight as no lower bounds are given. - The finite type assumption - assuming both that the number of types is small (so that the complexity bounds are reasonable) and that all the types are known up front is somewhat limiting. Anything to address either of these comments is a significant improvement. - Once given the discretization scheme, the online learning methods utilize fairly standard techniques. It would be interesting if there are other approaches to this problem. - A lack of an experimental evaluation which might help to provide further evidence of the practicality of the proposed methods. As a minor comment, the organization in the appendix is poor as it does not follow the order in the main paper (appendix C gives proofs for section 5, while appendix D gives proofs for section 4). This leads to a confusion about notation, since the definition that $r(i, p ) = p(n_{i,p})$ isn't introduced until appendix D, but is used in appendix C.

Questions

- Can anything be done to remove the assumption that the types are known up front? - Can any tight lower bounds be given for the stochastic and adversarial settings (i.e., in terms of both $m$ and T$)? Minor comments: - In Eq. (22) in the appendix, it has $f_t(p^*)$ instead of $r_t(p^*)$.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors have made assumptions clear.

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.

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. 2. The construction of the confidence interval has room for improvement. The UCB in this paper is |q_i-q_{i,t}| \leq |log T/T_{i,t}|. Such an interval is typewise. I believe that using a joint confidence interval (for example, \sum T_{i,t} |q_i-q_{i,t}| \leq log T or similar form )or a similar form) could improve the dependency of the regret on $m$. 3. It is unclear whether Line 6 of Algorithm 3 is computationally efficient.

Questions

See the 'Weakness' part

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

See the 'Weakness' part