Sample Complexity of Posted Pricing for a Single Item

Authors: billy  jin
thomas  kesselheim
will  ma
sahil  singla
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 18:30:02

Abstract: Selling a single item to $n$ self-interested bidders is a fundamental problem in economics, where the two  objectives  typically considered are welfare maximization and revenue maximization.   Since the optimal auctions are often impractical and do not work for sequential bidders, posted pricing auctions, where fixed prices are set for the item for different bidders, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from bidders' value distributions to find near-optimal posted prices, considering both independent and correlated bidder distributions, and welfare versus revenue maximization.  We obtain matching upper and lower bounds (up to logarithmic terms) on the sample complexity for all these settings.

Main paper: 
 introduction: 
 A fundamental problem in Economics is how to sell a single indivisible item to a set of n selfinterested buyers. This problem is challenging because the value associated to the item is private knowledge of each buyer and thus can be strategically misreported. The mechanism designer usually has one of two objectives: (a) welfare maximization where we want to maximize the value of the winning buyer, and (b) revenue maximization where we want to maximize the price paid by the winning buyer. The welfare maximization problem was resolved by Vickrey in 1961 [Vic61] and the revenue maximization problem was resolved (for independent distributions) by Myerson in 1981 [Mye81] , both of whom were awarded the Nobel prize in Economics for their contributions. In either case the optimal mechanism is a truthful auction, in which buyers report their values and have no incentive to misreport.Although we know optimal mechanisms for selling a single item, these auctions are often difficult/impossible to implement in practice. For instance, the buyer does not know exactly how much they will pay if they win the item and these auctions do not work for online settings where the buyers arrive one-by-one [AM + 06, HR09]. Thus, the last two decades has seen a lot of progress on understanding the power of simple but near-optimal mechanisms. In this regard, posted pricing mechanisms have been identified to be very successful (see books and surveys [Rou16, Har13, CFH + 19, Luc17]). Here, the mechanism designer puts a (carefully chosen) price π i on the item and then the i-th buyer takes the item if the item is not already sold and if they value it above π i . Posted pricing mechanisms have several advantages: they are truthful since π i does not depend on the i-th buyer's value; the buyer knows exactly how much they pay on winning an item; and they work even for online settings so the buyers do not have to be simultaneously present. Additionally, in the setting of Myerson's 1981 paper of independent buyer valuations, they are known to give a 2-approximation to both the optimal welfare (which is usually called Prophet Inequality) and the optimal revenue Learning problem. A learning algorithm takes as input samples V that are drawn independently and identically distributed (IID) from the unknown distribution D and an error parameter ε ∈ (0, 1), and seeks to return a policy π ∈ Π that satisfies π(D) ≥ Π(D) -ε, which is called an ε-approximation. Given a failure probability δ ∈ (0, 1), the sample complexity is the minimum number of samples required for there to exist a learning algorithm that, under any distribution D, returns an ε-additive approximation with probability at least 1 -δ, noting that the randomness is over both the samples and any random bits in the algorithm. The sample complexity and learning algorithm will depend on the problem variant, defined by the objective (welfare or revenue), any parameters of the policy class Π, and whether D is restricted to be a product distribution or not. The sample complexity will also depend on the parameters ε, δ > 0.The study of sample complexity for posted pricing goes back to at least the seminal work of Kleinberg and Leighton [KL03] who study revenue maximization for selling a single item to a single buyer (welfare maximization is trivial for single buyer since we just allocate the item by setting 0 price). For the general posted pricing problem with n buyers, the best known sample complexity bounds were due to Guo et al. [GHTZ21] , who showed that Õ(n/ε 2 ) samples suffice from each buyer's distribution for both welfare and revenue maximization objectives. Although there is a simple Ω(1/ε 2 ) lower bound for both welfare and revenue maximization settings, prior to our work it was unclear if polynomial dependency on the number of buyers n is necessary.Our first result for product distribution shows that for welfare maximization using posted pricing (a.k.a. prophet inequality), the sample complexity is independent of the number of buyers n.Theorem 1 (proved in Subsection 2.1). For product distributions, the sample complexity of welfaremaximization is O(1/ε 2 • log 2 (1/δ)).Proof sketch. We start by constructing the product empirical distribution using the samples, where for each i we take the uniform distribution on the Õ(1/ε 2 ) samples and then take the product distribution for different i. Our main result is that the optimal policy (dynamic programming solution) on this product empirical distribution is an ε-approximation with high probability. Although one could use standard concentration bounds to bound the gap between the learned and optimal thresholds, such arguments lose a poly(n) factor. This is because the difference between successive thresholds is bounded by 1, so naïvely the total variance of n thresholds could be Ω(n). Our main idea is to instead study a martingale that adds up the errors made in the dynamic programming solution. This way, too high values for one buyer and too low values for another buyer balance each other. On this martingale, we use Freedman's inequality (which is a martingale variant of Bernstein's inequality), which allows us to bound the total variance in terms of conditional variances. A careful application of another concentration bound allows us to bound these conditional variances in terms of the change in the optimal value, whose sum is always at most 1. This latter concentration bound is what causes the additional factor of log(1/δ) in the sample complexity.Our second result for product distribution shows a separation between welfare and revenue maximization using posted pricing, by proving that the Õ(n/ε 2 ) sample-complexity result of [GHTZ21] for revenue maximization is tight up to log factors.Theorem 2 (proved in Subsection 2.2). For revenue maximization on product distributions, any learning algorithm requires Ω( n ε 2 ) samples to return an ε-additive approximation with probability greater than 6/7. Proof sketch. We construct for each buyer i two possible value distributions that add the same amount (roughly 1 n ) to the value-to-go of the optimal dynamic program. However, these distributions have different optimal prices, and making a mistake (choosing an incorrect price) in isolation loses roughly ε n value. Although these mistakes accumulate in a non-linear fashion, we show that making M mistakes must lose in total Ω( εM 2 n 2 ). Finally, these value distributions have probabilities on the scale of 1±ε n with the same supports (essentially, only 1/n of samples provide information), which means that Ω( n ε 2 ) samples are needed to avoid making a constant fraction of mistakes.Independence among buyer valuations can be a strong modeling assumption for many applications.Although for arbitrary correlated distributions the optimal policy is not learnable, one could hope to learn the best policy in the class of all posted pricing policies. A recent work of Balcan et al.[BDD + 21] can be applied to this setting to show that Õ(n/ε 2 ) samples are sufficient to learn εoptimal posted pricing. As discussed in Theorem 2, this linear in n dependency is necessary for revenue maximization, even for product distributions. Our first observation is that for correlated distributions, we need to lose this factor even for welfare maximization.Theorem 3 (corollary of Theorem 5). For welfare maximization with correlated buyers, any learning algorithm requires Ω( n ε 2 ) samples to return an ε-additive approximation with constant probability.Given this lower bound, a natural next question is to consider the subclass of posted pricing policies where the algorithm is only allowed to change its threshold at a small number of given locations. Can we now remove the linear in n dependency from sample complexity? The motivation to study this class comes from posted pricing applications where it is not possible for the algorithm designer to update the prices at each time step, e.g., due to business constraints.Formally, for S ⊆ {2, . . . , n}, we say that posted pricing policy π respects change-points S if π i can differ from π i-1 only when i ∈ S. We let Π S denote the class of all policies that respect changepoints S, noting that policies in Π(∅) post a static price for all buyers, and Π({2, . . . , n}) = [0, 1] n . Our following result shows that one can obtain sample complexity that is independent of n, depending only on the size of S.Theorem 4 (proved in Subsection 3.1). For correlated distributions, the sample complexity of welfare or revenue maximization isO (1+|S|) log(1+|S|)+log(1/δ) ε 2when the policy is restricted to Π S , for any S ⊆ {2, . . . , n}.Proof sketch. By existing results in learning theory, it suffices to bound the pseudo-dimension of Π S . This will boil down to understanding the structure of "good sets", which are sets of the form {π ∈ Π S : π(v) ≥ z}, for some input v and some target z. We will show that for a natural parameterization of Π S , any good set can be expressed as the union and intersection of O(|S| + 1) halfspaces, which implies the pseudo-dimension of Π S is O((|S| + 1) log(|S| + 1)) by a result of [BDD + 21]. This bound on the pseudo-dimension translates to the above sample complexity bound.The learning algorithm which achieves the sample complexity bound in Theorem 4 is simply sample average approximation (SAA), which returns the policy in Π S with the highest objective value averaged over the samples. SAA can be computed in time O(T n(T n) 1+|S| ). This is because there are 1 + |S| prices to decide, each of which can take T n possible values (one for each realized value in the T samples of length n), and evaluating each combination of prices over each of the T samples takes runtime linear in n. We leave as an open question whether there is a more efficient algorithm.Finally, we complement our sample complexity upper bounds for correlated distributions by giving matching lower bounds (up to polylogs).Theorem 5 (proved in Appendix A.5). For welfare or revenue maximization on correlated distributions, a learning algorithm requires Ω( 1+|S| ε 2 ) samples to return an ε-additive approximation with constant probability, when restricted to the policy class Π S for any S ⊆ {2, . . . , n}.Proof sketch. In the construction for Theorem 5, on each trajectory exactly one of the 1 + |S| decision points (randomly selected) will be relevant, essentially diluting the samples by a factor of 1 + |S| and leading to a lower bound of Ω( 1+|S| ε 2 ).In 2007, Hajiaghayi et al. [HKS07] discovered connections between auction design and posted pricing via prophet inequalities. Since then, there is a long line of work on understanding the power of posted pricing for selling multiple items to combinatorial buyers [CMS10, FGL15, DKL20, AKS21, CC23].For single item revenue maximization with known distributions, Correa et al. [CFPV19] showed the equivalence of welfare and revenue maximization objectives for single item posted pricing.For background on sample complexity, we suggest Wainwright's excellent textbook [Wai19] . Sample complexity of auction design has been greatly studied; e.g., see [KL03, CR14, MR16] . We refer the readers to Guo et al. [GHZ19] , who recently resolved single item revenue maximization in the offline setting, for an overview of the literature. In [GHTZ21], Guo et al. generalized their techniques for revenue maximization over product distributions to all "strongly monotone" problems, which includes posted pricing for welfare and revenue maximization.Recently, there is also a lot interest in learning auctions in limited feedback models like bandit and pricing queries [GKSW24, SW24, LSTW23]. We should note that sample complexity of optimal stopping (equivalent to our welfare maximization problem) has been previously studied in [GM22] , who analyze linear stopping rules in a contextual setting. Our application of techniques from [BDD + 21] to online algorithms over correlated sequences is also similar in spirit to some results from [XMX24] , who study a different application of inventory optimization.Another related but tangential line of work focuses on prophet inequalities with samples [AKW14, RWW, CDFS22, CDF + 22, DKL + 24]. The key distinction in these works is that their benchmark is the expected hindsight optimum, rather than the optimal online policy. Notably, any online algorithm incurs at least a factor of 2 loss compared to the hindsight optimum, even in the case of single-item prophet inequalities. As a result, this line of research aims to achieve O(1)-approximation guarantees, rather than the sublinear regret guarantees pursued in the current paper. Furthermore, their techniques differ significantly, as they often assume unbounded distributions. Finally, there is also work that explores the (non-)robustness of algorithms for the prophet inequality problem to inaccuracies in the distributions [DK19] and to dependencies in distributions [ISW20, LPS24] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and the introduction clearly reflect our contributions.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
product distributions: 
 In this section we first prove our improved upper bound on the sample complexity of welfare for product distributions, and then prove a new lower bounds on the sample complexity of revenue for product distributions.The reward of the optimal policy is given by the following backward induction: r * n+1 = 0 andr * i = E max{r * i+1 , V i } = E (V i -r * i+1 ) + + r * i+1 . It sets π i = r * i+1 .When we do not know the distributions but only have T samples from each of them, we can consider the optimal policy on the product empirical distribution, which corresponds to replacing the expectations in the above definitions by the empirical average. That is, we will analyze the policy that sets π i = ri+1 , where ri is defined recursively by rn+1 = 0, ri = 1T T t=1 (V (t) i -ri+1 ) + + ri+1 .Let r i be the expected reward of this policy when starting with the i-th arrival. In order to prove the theorem, it is sufficient to show that with probability at least 1 -δ, we have r 1 ≥ r * 1 -ϵ if T ≥ (5 ln(2e/δ)/ϵ) 2 for any choices of ϵ, δ ∈ (0, 1).i = ri -E [max{r i+1 , V i }] or equivalently as η i = 1 T T t=1 (V (t) i -ri+1 ) + -E [(V i -ri+1 ) + ] .That is, η i denotes the error introduced by using the empirical distribution for buyer i instead of the actual one. Note that η i can both be positive and negative.The two key steps of our proof are as follows. We first show thatEQUATIONThis inequality holds point-wise, that is for any samples drawn. Then, we show that for T ≥ (5 ln(2e/δ)/ϵ) 2 samples, we have max j≥1 j i=1 η i ≤ ϵ with probability at least 1 -δ.In order to show (1), we first lower bound r 1 in terms of r1 .Lemma 1. r 1 ≥ r1 -max j∈{0,...,n} j i=1 η i .Proof. Let j ∈ {0, 1, . . . , n} be the smallest index for which r j+1 ≥ rj+1 , which exists because 0 = r n+1 ≥ rn+1 = 0. Note that we have r i < ri for all 1 ≤ i ≤ j. We rewrite r 1 asr 1 = Pr [V 1 < r2 ] r 2 + Pr [V 1 ≥ r2 ] E [V 1 | V 1 ≥ r2 ] = r 2 + E [(V 1 -r 2 )1 V1≥r2 ] .Repeating this argument,r 1 = j-1 i=1 E[(V i -r i+1 )1 Vi≥ri+1 ] + E[V j 1 Vj ≥rj+1 + r j+1 1 Vj <rj+1]. Inductively, we can also establish thatr1 = j-1 i=1 1 T t (V (t) i -ri+1 ) + + 1 T t max{V (t) j , rj+1 }. Combining these two equalities, r1 -r 1 = j-1 i=1 1 T T t=1 (V (t) i -ri+1 ) + -E[(V i -r i+1 <ri+1 )1 Vi≥ri+1 ] + 1 T T t=1 max{V (t) j , rj+1 } -E[V j 1 Vj ≥rj+1 + r j+1 ≥rj+1 1 Vj <rj+1 ] ≤ j-1 i=1 1 T T t=1 (V (t) i -ri+1 ) + -E[(V i -ri+1 ) + ] + 1 T T t=1 max{V (t) j , rj+1 } -E[max{V j , rj+1 }] = j i=1 η i .This implies r1 -r 1 ≤ max j∈{0,...,n} j i=1 η i , completing the proof.A similar proof allows us to prove the following lemma.Lemma 2. r1 ≥ r * 1 -max j∈{0,...,n} (-j i=1 η i ).Proof. Let j ∈ {0, 1, . . . , n} be the smallest index for which rj+1 ≥ r * j+1 , which exists because 0 = rn+1 ≥ r * n+1 = 0. Note that we have ri < r * i for all 1 ≤ i ≤ j, allowing us to deriver * 1 -r1 = j-1 i=1 E[(V i -r * i+1 >ri+1 ) + ] - 1 T T t=1 (V (t) i -ri+1 ) + + E[max{V j , r * j+1 ≤rj+1 }] - 1 T T t=1 max{V (t) j , rj+1 } ≤ j-1 i=1 E[(V i -ri+1 ) + ] - 1 T T t=1 (V (t) i -ri+1 ) + + E[max{V j , rj+1 }] - 1 T T t=1 max{V (t) j , rj+1 } = - j i=1 η i .This implies r * 1 -r1 ≤ max j∈{0,...,n} (-j i=1 η i ), completing the proof.The last two lemmas imply (1). Thus, we need to bound max j | j i=1 η i | to complete the proof. Lemma 3. For every ϵ, δ > 0, with probability at least 1 -δ, we have Lemma 4 (Freedman, Theorem 1.6 in [Fre75] ). Consider a real-valued sequence {X t } t≥0 such that X 0 = 0 and E [X t+1 | X t , X t-1 , . . . , X 0 ] = 0 for all t. Assume that the sequence is uniformly bounded, i.e., |X t | ≤ M almost surely for all t. Now define the predictable quadratic variation process of the martingale to be W t = t j=0 E X 2 j X j-1 , . . . , X 0 for all t ≥ 1. Then for all ℓ ≥ 0 and σ 2 ≥ 0, and any stopping time τ , we havemax j | j i=1 η i | ≤ ϵ if T ≥ (5 ln(2e/δ)/ϵ) 2 . Proof. Observe that j i=1 η i = n i=1 η i - n i=j+1 η i ≤ | n i=1 η i | + n i=j+1 η i ≤ 2 max τ | n i=τ η i | ,Pr τ j=0 X j ≥ ℓ and W τ ≤ σ 2 ≤ 2 exp -ℓ 2 /2 σ 2 +M ℓ/3 . A corollary of Freedman's inequality is that Pr τ j=0 X j ≥ ℓ ≤ 2 exp -ℓ 2 /2 σ 2 +M ℓ/3 + Pr W τ ≤ σ 2 .In order to use Freedman's inequality, we consider nT random variables X 1 , . . . , X nT , whereX iT +t = 1 T (V (t) n-i -rn-i-1 ) + -E (V (t)n-i -rn-i-1 ) + for i ∈ {0, . . . , n -1} and t ∈ {1, . . . , T }. By this definition,η i = T t=1 X (n-i)T +t because V (t)n-i and V n-i are identically distributed and independent of rn-i-1 . Moreover, for all j,E [X j | X 1 , . . . , X j-1 ] = 0 and |X j | ≤ 1 T .Let E be the event thatnT j=1 E X 2 j X 1 , . . . , X j-1 > σ 2 := e e+1 ln(2e/δ) T. By Freedman's inequality, using T ≥ (5 ln(2e/δ)/ϵ) 2 , we havePr max τ | n i=τ η i | ≥ ϵ 2 ≤ Pr max τ τ j=1 X j ≥ ϵ 2 ≤ 2 exp -ϵ 2 /8 σ 2 + ϵ 6T + Pr [E] ≤ 2 exp   - 5 ln(2e/δ) √ T 2 /8 e e+1 ln(2e/δ) T + 5 ln(2e/δ) 6T √ T    + Pr [E] = 2 exp - 25 8e e+1 + 40 6 √ T ln( 2e δ ) + Pr [E] ≤ 2 exp -(1) ln( 4 δ ) + Pr [E] = δ 2 + Pr [E] .It remains to show that Pr [E] ≤ δ 2 . To this end, we observe that for any i ∈ {0, . . . , n -1} and t ∈ {1, . . . , T }, with probability at most δ 2 . Therefore, we haveE X 2 iT +t X 1 , . . . , X iT +t-1 = 1 T 2 E (V (t) n-i -rn-i-1 ) + -E (V (t) n-i -rn-i-1 ) + 2 X 1 , . . . , X iT +t-1 ≤ 1 T 2 E (V (t) n-i -rn-i-1 ) + X 1 , . . . , X iT +t-1 = 1 T 3 T t ′ =1 E (V (t ′ ) n-i -rn-i-1 ) + X 1 , . . . , X iT = 1 T 2 E [r i -ri+1 | ri+1 , . . . , rn ] , where the inequality uses E [Y ] ≥ E Y 2 ≥ E Y 2 -(E [Y ]) 2 = E (Y -E [Y ]) 2 for any random variable Y with 0 ≤ Y ≤ 1 almost surely. In total, we have nT j=1 E X 2 j X 1 , . . . , X j-1 ≤ 1 T n i=1 E [r i -ri+1 | ri+1 , . . . , rn ] .Pr [E] ≤ Pr n i=1 E [r i -ri+1 | ri+1 , . . . , rn ] ≥ e e -1 ln 2e δ ≤ δ 2 . Lemma 5. Let Y 1 , Y 2 , . . . , Y n be a sequence of (not necessarily independent) random variables in [0, 1] such that n i=1 Y i ≤ 1 almost surely.Then, for any δ > 0, with probability at most δ, we haven i=1 E [Y i | Y 1 , . . . , Y i-1 ] ≥ e e-1 ln e δ .We defer the proof of Lemma 5 to the appendix.Each buyer i = 1, . . . , n has a marginal value distribution that could be D H i ("High") or D L i ("Low"):D H i =    1 2 + n-i 4n w.p. 1 2n 1 4 + n-i 4n w.p. 1 2n -16 ε n 0 w.p. 1 -1 n + 16 ε n D L i =    1 2 + n-i 4n w.p. 1 2n -8 ε n 1 4 + n-i 4n w.p. 1 2n + 8 ε n 0 w.p. 1 -1 nwhich are valid distributions as long as ε ≤ 1/32 and n ≥ 2. All 2 n configurations of whether each buyer has the High or Low distribution are possible.Optimal policy Fix any configuration of whether each buyer has the High or Low distribution. Let r * i denote the expected revenue to be earned under the optimal dynamic program, if buyer i is about to arrive and the item is not yet sold. We show inductively that r * i = n+1-i 4n . By definition r * n+1 = 0, establishing r * i = n+1-i 4n for i = n + 1. Now consider i = n, . . . , 1, and assume r * i+1 = n-i 4n . Note that it is better to offer one of the prices 1 2 + n-i 4n or 1 4 + n-i 4n than to reject the buyer by offering a price of 1, because both of these prices are greater than r * i (by the induction hypothesis). Thus, if buyer i has distribution D H i , thenr * i = max ( 1 2 + n-i 4n ) 1 2n + r * i+1 (1 -1 2n ), ( 1 4 + n-i 4n )( 1 n -16 ε n ) + r * i+1 (1 -1 n + 16 ε n ) = max 1 2 • 1 2n , 1 4 ( 1 n -16 ε n ) + n-i 4n = n+1-i 4n . Similarly, if buyer i instead has D L i , then r * i = max 1 2 ( 1 2n -8 ε n ), 1 4 • 1 n + n-i 4n = n+1-i 4n .In either case, we have r * i = n+1-i 4n , completing the induction. Note that r * 1 = 1/4.Bounding a policy's objective by its number of mistakes Now, consider an arbitrary policy π = (π 1 , . . . , π n ) decided by the learning algorithm. Let r i denote its expected revenue earned if buyer i is about to arrive and the item is not yet sold (under the true configuration of buyer distributions). We can without loss assume π to lie in { 1 2 + n-i 4n , 1 4 + n-i 4n } n , because both prices are higher than r i+1 , the expected revenue from rejecting (both prices are in fact higher than r * i+1 , an upper bound on r i+1 ). We say that the policy makes a mistake for buyer i if either π i = 1 4 + n-i 4n when i has the High distribution, or π i = 1 2 + n-i 4n when i has the Low distribution. If the policy makes a mistake for i, then we haver i -r i+1 ≤ max ( 1 4 + n-i 4n -r i+1 )( 1 n -16 ε n ), ( 1 2 + n-i 4n -r i+1 )( 1 2n -8 ε n ) = 1 4n -4 ε n + ( n-i 4n -r i+1 )( 1 n -16 ε n ); on the other hand, if the policy does not make a mistake for i, then we haver i -r i+1 ≤ max ( 1 2 + n-i 4n -r i+1 ) 1 2n , ( 1 4 + n-i 4n -r i+1 ) 1 n = 1 4n + ( n-i 4n -r i+1 ) 1 n .Hence, if the policy makes M mistakes for some M ∈ {1, . . . , n}, thenr 1 = n i=1 (r i -r i+1 ) ≤ 1 4 -M 4ε n + n i=1 ( n-i 4n -r i+1 ) 1 n . Now, observe that n-i 4n -r i+1 = r * i+1 -r i+1 ≤ 4εn min{n -i, M }, because the loss from making a mistake is at most 4 ε n , and starting from buyer i + 1, the number of mistakes can be at most n -(i + 1) + 1 = n -i and also at most M . Therefore,r 1 ≤ 1 4 -M 4ε n + (n -M ) 4ε n M + 4ε n (M -1) + • • • + 4ε n 1 n = 1 4 -M 4ε n (1 -n-M n -M -1 2n ) = 1 4 -2ε M n ( M +1 n ). Recalling that r * 1 = 1/4, this shows the additive error is Ω(ε) as long as the fraction of mistakes M/n is a constant.i , D L i ) between (a single observation of) D H i vs. D L i , which we note does not depend on the buyer i. The squared Hellinger distance can be bounded using1 -H 2 (D H i , D L i ) = 1 2n ( 1 2n -8 ε n ) + ( 1 2n + 8 ε n -24 ε n )( 1 2n + 8 ε n ) + (1 -1 n + 16 ε n )(1 -1 n ) ≥ 1 2n -4ε n - (8 ε n ) 2 1 2n + 1 2n -4ε n - ( 24ε n ) 2 1 2n + 8ε n + 1 -1 n + 8ε n - ( 16ε n ) 2 1-1 n = 1 -O( ε 2 n ),where the inequality applies Lemma 6 below to each square root. This shows thatH 2 (D H i , D L i ) = O( ε 2n ), and the squared Hellinger distance is additive across independent samples. Using the fact that the Total Variation distance is upper-bounded by √ 2 times the Hellinger distance [GS02] , we see that the Total Variation distance between T independent samples of D H i vs. T independent samples ofD L i is O( T n ε). The proof of Lemma 6 is deferred because it is elementary. Lemma 6. Suppose C ∈ (0, 1) and x ∈ [-3 4 C, 3 4 C]. Then C(C + x) ≥ C + x 2 -x 2 C .Completing the proof of Theorem 2 Suppose the distribution of each buyer is equally likely to be High or Low, independently across buyers. Fix any learning algorithm and the constant probability 1/2. By the computation of Hellinger distance above, if the number of samples T is less than C n ε 2for some constant C, then for any buyer i, the Total Variation distance between the samples observed under D H i vs. D L i is at most 1/2. (C depends on the choice of constant 1/2.) This means that w.p. at least 1 -1/2, the price π i decided by the learning algorithm cannot depend on whether buyer i had distribution D H i vs. D L i , which means that there exists an adversarial choice of D H i or D L i for each buyer i under which the probability of making a mistake for buyer i is at least (1 -1/2)/2 = 1/4.Let M denote the (random) number of mistakes, under this adversarial configuration of whether each buyer i has distribution D H i or D L i . We have that E[ M n ] ≥ 1/4. Although whether the algorithm makes a mistake could be arbitrarily correlated across buyers i, applying M n ≤ 1, we can employ Markov's inequality on the random variable 1 -M n to see thatP (1 -M n ) ≥ 7/8 ≤ 3/4 7/8 = 6 7 .The LHS equalsP[ M n ≤ 1 8 ] = 1 -P[ M n > 1 8 ], and hence 1 7 ≤ P[ M n > 1 8 ].We have shown that unless T = Ω( n ε 2 ), there is probability at least 1/7 of making a constant fraction of mistakes, in which case we showed above that the additive error would be Ω(ε). This completes the proof of Theorem 2.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss in the related work section topics that are not in this paper's scope.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
correlated distributions: 
 In this section we prove our upper bound on the sample complexity of welfare/revenue maximization for correlated buyer distributions. We show nearly matching lower bounds in Appendix A.5.To bound the sample complexity of posted pricing for correlated distributions, it suffices to bound the pseudo-dimension of the policy class Π S . We use the same approach for both the welfare and revenue objectives. By standard learning theory results [BBL03] , bounds on the pseudo-dimension translate to bounds on the sample complexity as follows. Theorem 6. Let PDim(Π S ) denote the pseudo-dimension of Π S . For any ϵ > 0, any δ ∈ (0, 1) and any distribution D over [0, 1] n , T = O( 1 ϵ 2 (PDim(Π S ) + log 1 δ )) samples are sufficient to ensure that with probability at least 1 -δ over the draw of samples (v 1 , . . . , v T ) ∼ D T , for all π ∈ Π S ,1 T T t=1 π(v t ) -π(D) ≤ ϵ.We will show that PDim(Π S ) = O(k log k), where k = |S| + 1. This together with the above theorem immediately implies that Theorem 4 holds for the sample average approximation algorithm.Let S = {i 1 , i 2 , i 3 , . . . , i k-1 }, where 1 < i 1 < i 2 < . . . < i k-1 . For each j = 1, 2, . . . , k, let I j = {i j-1 , . . . , i j -1}, with the convention that i 0 = 1 and i k = n + 1. In other words, I 1 , I 2 , . . . , I k are consecutive intervals that partition [n], and Π S is the class of policies that offers every customer in I j the same price. Note that every policy π ∈ Π S can be parameterized by k prices ρ = (ρ 1 , ρ 2 , . . . , ρ k ), where ρ j is the price offered to customers in I j . In the rest of this proof, we will use π ρ to denote the policy in Π S parameterized by ρ.EQUATIONwhereΠ S := {(v, z) → 1{π ρ (v) ≥ z} : ρ ∈ R k }. Let Π * S denote the dual class of Π S , so Π * S := {ρ → 1{π ρ (v) ≥ z} : v ∈ [0, 1] n , z ∈ R} .We will use a result from [BDD + 21] to bound the VC dimension of Π S . We state this result below in Definition 1 and Theorem 7. This result essentially says that the pseudo-dimension of the primal class is bounded if the dual class is well-structured. Here, "well-structured" essentially means that the domain can be partitioned into pieces defined by a small number of boundary functions, and the function is simple on each piece.Definition 1 (Definition 3.2 in [BDD + 21]). A function class H ⊆ R Y that maps a domain Y to R is (F, G, l)-piecewise decomposable for a class G ⊆ {0, 1} Y of boundary functions and a class F ⊆ R Y of piece functions if the following holds: for every h ∈ H, there are l boundary functions g (1) , . . . , g (l) ∈ G and a piece function f b ∈ F for each bit vector b ∈ {0, 1} l such that for all y ∈ Y, h(y) = f by (y) where b y = (g (1) (y), . . . , g (l) (y)) ∈ {0, 1} l .The main theorem in [BDD + 21] states that if the dual class is (F, G, l)-piecewise decomposable, then the pseudo-dimension of the primal class is bounded. Theorem 7 (Theorem 3.3 in [BDD + 21]). Suppose that the dual function class U * is (F, G, l)piecewise decomposable with boundary functions G ⊆ {0, 1} U and piece functions F ⊆ R U . The pseudo-dimension of U is bounded as follows:PDim(U) = O((PDim(F * ) + VCdim(G * )) ln(PDim(F * ) + VCdim(G * )) + VCdim(G * ) ln l).We now apply Theorem 7 to bound the VC dimension of Π S . 5 To do so we must show that the dual class Π * S is (F, G, l)-piecewise decomposable for "nice" classes F and G. We will show that for both the welfare and revenue objectives, we can take F to be the family of constant functions and G to be the family of axis-aligned halfspaces. This will follow from the below lemma, whose proof is deferred to the Appendix for space reasons.Lemma 7. Let v ∈ [0, 1] n and let z ∈ R. Let G(v, z) = {ρ ∈ R k : π ρ (v) ≥ z}.For both the welfare and revenue objectives, there arel 1 , u 1 , • • • , l k , u k ∈ R ∪ {±∞} such that G(v, z) = k j=1 (u 1 , ∞) × • • • × (u j-1 , ∞) × (l j , u j ] × R k-j .(3)Corollary 1. Π * S is (F, G, l)-piecewise decomposable, where F is the set of constant functions, G is the set of axis-aligned halfspaces, and l = 2(|S| + 1).h ∈ Π * S . By definition of Π * S , there exist v ∈ [0, 1] n and z ∈ R such that h(ρ) = 1{π ρ (v) ≥ z}. By Lemma 7, there are l 1 , u 1 , . . . , l k , u k such that {ρ ∈ R k : h(ρ) = 1} = k j=1 (u 1 , ∞) × • • • × (u j-1 , ∞) × (l j , u j ] × R k-j . For each j ∈ [k], let L j = {ρ ∈ R k : ρ j > l j } and U j = {ρ ∈ R k : ρ j ≤ u j }.Note that L j and U j are axis-aligned halfspaces, and{ρ ∈ R k : h(ρ) = 1} = k j=1 Ū1 ∩ Ū2 ∩ • • • ∩ Ūj-1 ∩ L j ∩ U j .Therefore, in the definition of (F, G, l)-piecewise decomposable, we may take the boundary functions to be the 2k functions corresponding to the halfspaces L 1 , U 1 , . . . , L k , U k . On any given piece defined by these boundary functions, h is a constant function (equal to either 0 or 1).For F the set of constant functions and G the set of axis-aligned halfspaces in R k , it is easy to check that PDim(F * ) = 0 and VCdim(G * ) = k. Combining Corollary 1 with Theorem 7, we get thatVCdim( Π S ) = O (k ln k + k ln 2k) = O(k ln k).This completes the proof of Theorem 4. In particular, the bound for welfare would grow with n. This dependence on n is in fact unavoidable if one works with Π S directly, because for instances like v = ( 1 n , 2 n , . . . , 1), the dual function corresponding to v is piecewise constant with Θ(n) pieces, even if k = 1. This is why our Corollary 1 focuses on the indicator functions Π * S instead. Regardless, both the bounds for welfare and revenue require our Lemma 7 that analyzes the problem-specific structure of the "good sets".A.1 Proof of Lemma 2 Proof. Now, consider the smallest j so that rj ≥ r * j . Again, we know such a j exists because 0 = rn+1 ≥ r * n+1 = 0. We claim that that r1 ≥ r * 1 + min{ j-1 i=1 η i , 0}. Observe that there is nothing to be shown if j = 1 because then r1 ≥ r * 1 . So, let's consider the case that j > 1. We can now write r1 as a telescoping sumEQUATION)Since rj ≥ r * j , we haverj-1 = rj + 1 T T t=1 (V (t) j-1 -rj ) + = rj + E [(V j-1 -rj ) + ] + η j-1 = E [max{V j-1 , rj }] + η j-1 ≥ E max{V j-1 , r * j } + η j-1 = r * j-1 + η j-1 .Observe that for i + 1 < j, we have ri+1 < r * i+1 . Thereforeri -r i+1 = 1 T T t=1 (V (t) i -r i+1 ) + = E [(V i -ri+1 ) + ]+η i ≥ E (V i -r * i+1 ) + +η i = r * i -r * i+1 +η i .So, in combination with (4),r1 ≥ r * j-1 + η j-1 + j-2 i=1 (r * i -r * i+1 + η i ) = r * 1 + j-1 i=1 η i .Ignoring constants, a slick proof of this lemma is via another application of Freedman's inequality, where we define a martingaleX i = Y i -E[Y i | Y 1 , . . . , Y i-1 ],and cut this martingale (stop) whenever the sum of conditional variances exceeds log(1/δ). This bounds the sum of conditional variances by log(1/δ), i.e. W τ ≤ σ 2 := log(1/δ) w.p. 1. Since the lemma is upper-bounding the probability of the event that i X i > log(1/δ), we can show that this probability is O(δ) by substituting ℓ = log(1/δ) into Freedman's inequality.Below we give another, elementary proof of this lemma.Proof. Let Z = 1 if n i=1 E [Y i | Y 1 , . . . , Y i-1] ≥ e e-1 ln e δ . By Markov's inequality, we havePr n i=1 Y i ≤ 1 and Z = 1 = Pr Ze -n i=1 Yi ≥ e -1 ≤ E Ze -n i=1 Yi • eNow, we haveE Ze -n i=1 Yi = E Z n i=1 e -Yi = E E [Z | Y 1 , . . . , Y n ] n i=1 E e -Yi Y 1 , . . . , Y i-1For every single conditional expectation, we obtain by convexityE e -Yi Y 1 , . . . , Y i-1 ≤ E Y i e -1 + (1 -Y i ) Y 1 , . . . , Y i-1 = E Y i (e -1 -1) Y 1 , . . . , Y i-1 + 1 ≤ exp E [Y i | Y 1 , . . . , Y i-1 ] (e -1 -1) .Now, consider a fixed realization of Y 1 , . . . , Y n . This realization fully determines Z. If Z = 0, thenE [Z | Y 1 , . . . , Y n ] n i=1 E e -Yi Y 1 , . . . , Y i-1 = 0 .Otherwise, with Z = 1, we haveE [Z | Y 1 , . . . , Y n ] n i=1 E e -Yi Y 1 , . . . , Y i-1 ≤ exp n i=1 E [Y i | Y 1 , . . . , Y i-1 ] (e -1 -1) ≤ δ e .So, we have an upper bound of δ e regardless of the realization. Taking an expectation, we getE E [Z | Y 1 , . . . , Y n ] n i=1 E e -Yi Y 1 , . . . , Y i-1 ≤ δ e , which implies Pr [ n i=1 Y i ≤ 1 and Z = 1] ≤ E Ze -n i=1Yi • e ≤ δ e e = δ, completing the proof.A.3 Proof of Lemma 6.Proof. Let f (x) = C(C + x) = (C 2 + Cx) 1/2 , which is a continuous function over x ∈ [-3 4 C, 3 4 C]. We have f ′ (x) = 1 2 (C 2 + Cx) -1/2 C and f ′′ (x) = -1 4 (C 2 + Cx) -3/2 C 2 , both of which exist over x ∈ [-3 4 C, 3 4 C].Applying Taylor's theorem around 0, we getf (x) = f (0) + f ′ (0)x + f ′′ (y) 2 x 2 = C + 1 2 x - 1 8 (C 2 + Cy) -3/2 C 2 x 2 ≥ C + x 2 -1 8 (C 2 + C(-3 4 C)) -3/2 C 2 x 2 = C + x 2 -x 2 C, where y lies between 0 and x and the inequality holds because y ≥ -3 4 C, completing the proof.If z ≤ 0 then G(v, z) = R k , so we may take any values of l 1 , u 1 , . . . , l k , u k such thatl 1 = l 2 = • • • = l k -∞ and u k = ∞.For the rest of the proof, assume z > 0. First, consider the welfare objective. We show the lemma holds for l j and u j as follows:Define l j to be -∞ if v(I j ) 1 ≥ z, and otherwise to be max{v(I j ) 1 , . . . , v(I j ) m-1 }, where m is the smallest index such that v(I j ) m ≥ z. (If v(I j ) m < z for all m, set l j = max(v(I j )).)Define u j to be max(v(I j )).Let G = {ρ ∈ R k : π ρ (v) ≥ z} and G ′ = k j=1 (u 1 , ∞) × • • • × (u j-1 , ∞) × (l j , u j ] × R k-j . To show that G = G ′ , we'll show G ⊆ G ′ and G ′ ⊆ G.Case 1 (G ⊆ G ′ ). If G = ∅ we are done, so assume otherwise. Let ρ ∈ G. Let j be the interval such that the algorithm (using thresholds ρ) accepts a value in v(I j ). Since a value in interval j was accepted, ρ j ≤ max(v(I j )) = u j . Also, since no value in the previous intervals were accepted, ρ i > u i for all i < j. Finally, we must have ρ j > l j , since otherwise the accepted value will be less than z.Thus ρ ∈ G ′ . Case 2 (G ′ ⊆ G). Let ρ ∈ G ′ . Then ρ ∈ (u 1 , ∞) × • • • × (u j-1 , ∞) × (l j , u j ] × R k-jfor some j. Since ρ i > u i for all i < j, the algorithm using thresholds ρ does not accept any value in the intervals i < j. Since ρ j ∈ (l j , u j ], the definitions of l j and u j imply that a value in v(I j ) is accepted, and this value is greater than or equal to z. Thus ρ ∈ G.For revenue, the only difference is that we define l j to be min(z, max(v(I j ))). (u j is still defined to be max(v(I j )).) With these definitions of l j and u j , a very similar analysis shows that G = G ′ in the revenue case as well.We let S ′ ⊆ {1} ∪ S be a subset of decision points such that price π i can be freely chosen for all i ∈ S ′ . For welfare maximization we require i + 1 ∈ {1, . . . , n} \ S ′ for all i ∈ S ′ , which can achieved while ensuring |S ′ | ≥ ⌊ 1+|S| 2 ⌋. Each decision point i ∈ S ′ has marginal value distribution(s) that could be "High" or "Low", separately for each decision point (i.e., all 2 |S ′ | combinations are possible). For welfare maximization, they are defined as • High: V i = 1/2 with probability (w.p.) 1, V i+1 = 1 w.p. 1/2 + ε, V i+1 = 0 w.p. 1/2 -ε;• Low: V i = 1/2 w.p. 1, V i+1 = 1 w.p. 1/2 -ε, V i+1 = 0 w.p. 1/2 + ε.For revenue maximization, they are defined as • High:V i = 1 w.p. 1/2 + ε, V i = 1/2 w.p. 1/2 -ε; • Low: V i = 1 w.p. 1/2 -ε, V i = 1/2 w.p. 1/2 + ε.The overall distribution over trajectories V is then correlated as follows. First, a decision point ĩ ∈ S ′ is drawn uniformly at random. Then, V ĩ (as well as V ĩ+1 in the case of welfare maximization) is drawn according to the distributions above, depending on whether decision point ĩ is High or Low. All other buyer values are 0 on this trajectory.Given this, only the prices for decision point ĩ are relevant, which can without loss be restricted to {1/2, 1}. The policy should optimize π i for each i ∈ S ′ as if ĩ = i. For either welfare or revenue maximization, the constructions above can be checked to satisfy the following properties:1. Setting π i (and π i+1 in the case of welfare maximization) to 1 is optimal for High and earns objective 1/2 + ε in expectation; setting to 1/2 is optimal for Low and earns objective 1/2; 2. Setting the wrong price earns expected objective 1/2 for High and 1/2 -ε for Low, incurring a loss of ε compared to optimal in both cases. 3. The High and Low distributions have the same support and probabilities that differ by 2ε.We note that for welfare maximization, it does not matter whether π i+1 ∈ S, because the decision is on whether to accept buyer i when V i = 1/2. Finally, a policy has additive error Ω(ε) as long as it has constant probability of setting the wrong price for a decision point. Due to property 3. above, the policy needs Ω( 1 ε 2 ) relevant observations for a given decision point to avoid setting the wrong price for it with constant probability. However, each sample contains a relevant observation for a given decision point only with probability 1/|S ′ |, so Ω( |S ′ | ε 2 ) samples are necessary for the number of relevant observations to be Ω( 1 ε 2 ) with high probability. Because |S ′ | ≥ ⌊ 1+|S| 2 ⌋, this completes the proof of Theorem 5.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: There is no societal impact of the work performed. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used toNote Theorem 7 is stated to bound the pseudo-dimension, but the pseudo-dimension coincides with the VC dimension for function classes consisting of {0, 1}-valued functions. 
 
 Appendix:  


Decision: Executive Summary

The paper examines the sample complexity of posted-price mechanisms, for both independent (product) distributions and correlated distributions, and both welfare and revenue objectives. The authors assume bounded distributions (normalized in [0,1]), and seek additive approximations to the best posted-price policy. More precisely, they seek approximations of the form "at least OPT - eps with probability at least 1-delta". 

The paper shows that for product distributions, the sample complexity for welfare maximization is O(1/eps^2) (omitting the dependence of delta), matching a known lower bound. Importantly, this is independent of n, the number of buyers. At the same time, for the revenue objective, they establish a lower bound of OmegaTilde(n/eps^2), and thus establish a separation to the welfare case.

The paper also considers the correlated case. For the welfare objective they give a lower bound of OmegaTilde(n/eps^2), matching a upper bound from prior work (and establishing a formal separation from the corresponding independent case). They complement this with postive results for welfare and revenue maximization, when the algorithm is constrained to change prices only a few times.

Recommendation

Overall, this is a very strong NeurIPS submission, which I am very happy to recommend for acceptance (as a spotlight if possible). This positive view of the paper is also reflected in the comments and suggestions from the reviewers, which I encourage the authors to take into account when preparing the final version.

Additional Requests

It appears to me that there is a closely related literature, which would be a natural reference point in the discussion. Namely, prior work on sample-based prophet inequalities, such as the following two papers (and follow-up work). I think the paper would benefit from discussing the differences between the approach taken in this paper, and the approach taken in this prior work (e.g. bounded distributions vs general distributions, prophet benchmark vs optimal online policy, etc.)

Correa, Duetting, Fischer, Schewior. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. EC'19
https://dblp.org/rec/conf/ec/CorreaDFS19.html?view=bibtex

Rubinstein, Weinberg, Wang. Optimal Single-Choice Prophet Inequalities from Samples. ITCS'20
https://dblp.org/rec/conf/innovations/RubinsteinWW20.html?view=bibtex

Another stream of related work that I feel deserves discussion is the one explored in the following paper, which explores the (non-)robustness of algorithms for the prophet inequality problem to inaccuracies in the distributions.

Duetting and Kesselheim. Prophet Inequalities with Inaccurate Priors. EC'19
https://dblp.org/rec/conf/ec/DuttingK19.html?view=bibtex

Reviews: review: paper_summary: paper_summary: The paper considers the problem of statistically estimating the optimal posted price mechanism for selling one item to multiple buyers. Here, it is assumed that the buyers appear sequentially, a price is presented to each of them and the sale is completed if the price posted to them is lower than their valuation. The mechanism aims to optimize one of two targets -- the welfare, defined here as the value of the bidder who wins the auction and revenue of the auctioneer which is the price paid by the winning bidder. It is assumed that the valuations of the bidders are drawn from a distribution and the paper aims to analyze the sample complexity of determining near-optimal posted prices for each of these settings where it is assumed that the learner receives iid samples from the bid distributions. Depending on the degree of dependence between the valuations of the bidders, the paper considers two settings -- firstly, the independent setting where the values are determined independently for each bidder and the dependent setting where the valuations are correlated across the bidders. 

In the independent setting, it is shown that there exists a separation between the sample complexities of welfare and revenue maximization. They show that essentially $1 / \epsilon^2$ samples suffice for welfare maximization whereas revenue maximization necessarily \emph{requires} $\Omega (n / \epsilon^2)$ samples where $n$ is the number of bidders and $\epsilon$ an additive error parameter. In this case, they obtain near-optimal characterization of the sample complexity while the upper and lower bounds from prior work are $n / \epsilon^2$ and $1 / \epsilon^2$ respectively. In contrast, when the bids are correlated, the paper shows that $\Omega (n / \epsilon^2)$ is \emph{required} for both revenue and welfare maximization. To partially address this pessimistic bound, the paper also considers the setting where the class of possible posted prices is restricted. The particular restriction considered in the paper is by restricting the change points of the price schedule; that is, the price is only allowed to change at $k$ points in the sequence of prices. Here, it is shown that sample complexities independent of $n$ are obtainable and instead only depend on $k$. 

The proof of the upper bound independent of $n$ for welfare maximization in the independent valuation setting is quite interesting. Essentially, the paper analyzes the dynamic programming algorithm for welfare maximization. Observing that the (welfare of the) posted prices have a closed-form solution in terms of the welfare of the next step, the paper proves that the sub-optimality of the posted prices may be bounded by a sum of error terms which satisfy a backwards martingale structure. The use of standard Martingale concentration bounds then yield the required bound. This proof is elegant and appears to be novel. Unfortunately, such martingale structure does not hold in the presence of dependencies between the valuations. Instead, they adopt a classical uniform convergence based approach and show that the statistical complexity may be controlled by the pseudo-dimension of the policy class.

Overall, this is a nice paper that obtains nearly optimal statistical characterizations in several fundamental settings, making several interesting contributions. The proofs of the results, the welfare maximization for independent valuations in particular, are elegant and well-presented. My main concerns are with the assumptions underlying the learning problem. The paper assumes that one obtains independent samples from the \emph{valuations} of the bidders. It is not clear how such samples are obtained -- it is not clear how one may obtain such samples in practice. More exposition on this point would be helpful. Furthermore, it would be helpful if the authors could comment on alternative settings circumventing the $\Omega (n / \epsilon^2)$ sample complexities incurred by the paper -- perhaps, by bounding the degree of dependence between the bidders?
strength_weakness: strength_weakness: See main review
questions: questions: See main review
limitations: limitations: See main review
paper_summary: paper_summary: The paper studies a setup of a series posted-price auctions that tries to sell a single item up to the first price acceptance. The authors seeking for the number of samples from buyer value distributions (sample complexity) to be able to setup near-optimal posted-price in the auctions. They consider two objectives (social welfare and revenue maximization) and different dependencies of buyer distributions (independent and correlated). The paper contributes proven both upper and lower on the sample complexity for the all four settings: the bounds are close up to logarithmic factors.
strength_weakness: strength_weakness: -	No conclusions: the paper does not have a concluding discussion

-	No experimental evidence: asymptotic bounds are clear measures for growing (shrinking) parameters, but, for practice, constant factors are more important. It would be nice to understand how they work in practical cases.
questions: questions: -	What are the factors (multiplicative constants) in the upper and lower bounds in Theorems 1-4?  What is behind O(...) and \Omega(...)?
limitations: limitations: the authors adequately addressed the limitations
paper_summary: paper_summary: This paper studies the problem of learning approximately revenue (welfare) optimal posted-prices single-item auctions from samples. The authors consider the setting where the valuation distributions of the agents are independent and the setting where the distributions are correlated. For both settings and both objectives they derive (almost) matching lower and upper bounds on the sample complexity of the learning task. All the results restrict the valuation distributions to be bounded in $[0,1]$ and consider additive approximations of the optimal posted-prices auctions.
strength_weakness: strength_weakness: -The conceptual ideas of the work feel a bit incremental, given the long line of work in the setting of learning optimal auctions. 

-The results are limited to a very simple setting of single item auctions.

-The running time of the algorithm for correlated distributions is exponential. 

-The presentation could be improved a bit. For example, I found the use of the word "policy" a bit confusing. Usually, this would imply some dynamic decision process, whereas here there is only a single-shot setting. It would be good to use different symbols for the revenue/welfare objectives. Line 61: instead of $V$ use something that denotes a set of samples. Line 104: what is the value-to-go? The proof sketch of Theorem 5 is a bit confusing. Lines 157-158 "single item" is repeated. The notation $r_i, \hat{r}_i, r^*_i$ in Section 2.1 is a bit confusing. In Section 2.2 you can add a quick comment that choosing a price randomly will not help. In Line 23 "know" appears twice. In Line 173 drop "a". It might be useful to include the definition of the pseudo-dimension at least in the appendix.
questions: questions: -What settings other than single-item auctions can the results be extended to?

-For other types of distributions such as regular/MHR, can you derive optimal bounds?

-For the bound on the pseudo-dimension, can't you use a direct argument like Morgenstern and Roughgarden (2016) for $t$-level auctions? I am not sure I understand the need to go through the dual class.

-Can you comment a bit on the differences of your results/approach and [GHTZ'21]?
limitations: limitations: Addressed.
paper_summary: paper_summary: This paper studies the sample complexity of posted pricing problems. In such problems, a sequence of $n$ buyers arrive with valuations drawn from fixed distributions, and the goal is to post prices that maximize either the revenue or the welfare. In particular, the item is sold to the first buyer who accepts its proposed price. Notably, in the welfare maximizing case, this is the prophet inequality problem. 

Given access to the distributions of the buyers’ valuations, it is possible to find the optimal online strategy via dynamic programming. This paper studies this problem when the access to the distribution is given via samples. The authors provide matching sample complexity bounds for the revenue and welfare maximization tasks, and for both the independent and correlated setting.
strength_weakness: strength_weakness: The paper is a strong NeurIPS submission
questions: questions: None
limitations: limitations: No potential negative societal impact of this work

Comments: comment: I would like to thank the authors for their thorough response. After reading their comments and the rest of the reviews, I've decided to increase my score to 6.
Thank you for the response! It would be great if the authors could include the above discussion in subsequent versions of the paper. I will retain my current evaluation.