# Pricing Query Complexity of Revenue Maximization

arXiv: https://arxiv.org/abs/2111.03158 · HTML: https://mlsanity.com/paper/2111.03158/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2021.

## Built on by (most cited first, 12 of 12)

- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Non-Stochastic CDF Estimation Using Threshold Queries](https://mlsanity.com/paper/2301.05682/) (2023)
- [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026)
- [Generalization Error Bounds for Learning under Censored Feedback](https://mlsanity.com/paper/2404.09247/) (2024)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price pt; then for a fresh sample vt ~ D we learn the sign st = sign(pt - vt) ∈ -1,+1. How many pricing queries are needed to estimate a given parameter of the underlying distribution? We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them. All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of ε in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called relative flatness to quickly zoom into the right region of the distribution to get the optimal pricing query complexity.