Learning Optimal Posted Prices for a Unit-Demand Buyer

We study the problem of learning the optimal item pricing for a unit-demand buyer with independent item values, and we have query access to the underlying value distributions. We consider two common query model in the literature: the “sample complexity” model where we can obtain a sample of each item value, and the “pricing query complexity” model where we can set a price to each item and obtain a binary signal on whether the sampled value of the item is greater than our proposed price. In this work we give nearly tight sample complexity and pricing query complexity of the problem.