cs.GTNov 7, 2026

The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-Wise

Authors: Yan Dai, Tao Lin, Aleksandrs Slivkins

Organizations: Operations Research Center, Massachusetts Institute of Technology. · School of Data Science, The Chinese University of Hong Kong, Shenzhen. · Microsoft Research NYC.

Abstract

We study the dynamic pricing problem, where a firm sells a product to TT myopic customers and their values are independent samples from an unknown value distribution FF. With posted prices, the firm only sees whether each customer buys, and the minimax regret is Θ~(T2/3)\widetilde Θ(T^{2/3}) [KL03]. A menu instead offers several options, each selling the product with some probability at some expected payment. Infinitely many menu options allow the seller to fully reveal customer values, reducing the regret to Θ(T)Θ(\sqrt T). How many options are needed? Perhaps surprisingly, a second menu option suffices, achieving the same regret as infinite menus (up to log⁡\log factors). This holds broadly: without knowing any property of FF, our algorithm with two menu options attains O~(T)\tilde O(\sqrt T) regret in general, O~(T1/3)\tilde O(T^{1/3}) regret for monotone-hazard-rate distributions, and O~(Td/(d+1))\tilde O(T^{d/(d+1)}) instance-dependent regret when d∈(0,1)d\in(0,1) is a suitable notion of "dimension". All are optimal even with infinite menus. Moreover, we argue, via a novel lower-bound construction, that our algorithm is near-optimal for each problem instance. Along the way, we study the query complexity of revenue maximization, where an algorithm issues a query to each customer to learn the property of interest (either the best price or the CDF) up to some precision. We show that interval queries suffice to achieve the same query complexity as value queries (up to log⁡\log factors) for both properties and across several classes of value distributions. We provide a new interval-query algorithm for each property. The best-price-estimation algorithm is the key ingredient in our main dynamic pricing algorithm, and the CDF-estimation algorithm underpins a simpler algorithm attaining O~(T)\tilde O(\sqrt T) regret with three menu options.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. On Non-Stationary Dynamic Pricing: Adaptivity and Optimality

    Jul 27, 2026Feiyu Jiang, Zifeng ZhaoNon-Stationary BanditsContextual Dynamic Pricing

  2. Optimal Contextual Pricing in Non-Stationary Environments

    Oct 29, 2026Yiding Feng, Alireza RezaeimoghadamContextual Dynamic PricingDynamic Pricing

  3. Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

    May 7, 2026Jianyu Xu, Yu-Xiang WangContextual Dynamic PricingContextual Bandits