# Pricing Query Complexity of Multiplicative Revenue Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 43 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 30 of 33)

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Making the Most of Your Samples](https://mlsanity.com/paper/1407.2479/) (2014)
- [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [A Sample Complexity Measure with Applications to Learning Optimal Auctions](https://mlsanity.com/paper/1704.02598/) (2017)
- [Sample Complexity of Posted Pricing for a Single Item](https://mlsanity.com/paper/2406.00819/) (2024)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Combinatorial Auctions via Posted Prices](https://mlsanity.com/paper/1411.4916/) (2014)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Randomization beats Second Price as a Prior-Independent Auction](https://mlsanity.com/paper/1507.08042/) (2015)
- [Optimal Pricing with a Single Point](https://mlsanity.com/paper/2103.05611/) (2021)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization](https://mlsanity.com/paper/1802.08037/) (2018)
- [Learning Reserve Prices in Second-Price Auctions](https://mlsanity.com/paper/1912.10069/) (2019)
- [Strong Revenue (Non-)Monotonicity of Single-parameter Auctions](https://mlsanity.com/paper/2205.08062/) (2022)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Secretary Problems: The Power of a Single Sample](https://mlsanity.com/paper/2208.09159/) (2022)
- [Single-Sample Prophet Inequalities Revisited](https://mlsanity.com/paper/2103.13089/) (2021)
- [Static Pricing for Single Sample Multi-unit Prophet Inequalities](https://mlsanity.com/paper/2409.07719/) (2024)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)

## Abstract (arXiv)

We study the pricing query complexity of revenue maximization for a single buyer whose private valuation is drawn from an unknown distribution. In this setting, the seller must learn the optimal monopoly price by posting prices and observing only binary purchase decisions, rather than the realized valuations. Prior work has established tight query complexity bounds for learning a near-optimal price with additive error varepsilon when the valuation distribution is supported on [0,1]. However, our understanding of how to learn a near-optimal price that achieves at least a (1-varepsilon) fraction of the optimal revenue remains limited. In this paper, we study the pricing query complexity of the single-buyer revenue maximization problem under such multiplicative error guarantees in several settings. Observe that when pricing queries are the only source of information about the buyer's distribution, no algorithm can achieve a non-trivial approximation, since the scale of the distribution cannot be learned from pricing queries alone. Motivated by this fundamental impossibility, we consider two natural and well-motivated models that provide "scale hints": (i) a one-sample hint, in which the algorithm observes a single realized valuation before making pricing queries; and (ii) a value-range hint, in which the valuation support is known to lie within [1, H]. For each type of hint, we establish pricing query complexity guarantees that are tight up to polylogarithmic factors for several classes of distributions, including monotone hazard rate (MHR) distributions, regular distributions, and general distributions.