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

Jul 27, 2026

On Non-Stationary Dynamic Pricing: Adaptivity and Optimality

We study the contextual dynamic pricing problem under non-stationarity, where a firm sells products to TT sequentially arriving consumers that behave according to an unknown demand model that can change over time. The demand model is assumed to be a generalized linear model (GLM), allowing for a feature vector in Rd\mathbb{R}^d that encodes products and consumer information. To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes. We propose a multiscale change-point detection based algorithm that achieves a regret of order O~(sTdT∧{VT1/3d1/3T2/3+dT})\widetilde{O}(\sqrt{s_TdT}\wedge\{V_T^{1/3}d^{1/3}T^{2/3}+\sqrt{dT}\}), where sTs_T is the number of piecewise stationary segments and VTV_T is a newly defined notion of design-adjusted variation budget of model parameters. Our algorithm is adaptive and does not require knowing sTs_T or VTV_T. Moreover, to our knowledge, this is the first dynamic pricing algorithm that is adaptive to the nature of changes and achieves the best-of-both-worlds rate, thus closing a long-standing gap in the literature. We remark that, due to the varying contexts, existing works in the adaptive non-stationary bandit literature cannot be applied to achieve optimality for contextual dynamic pricing. The regret is further accompanied with a newly constructed minimax lower bound, confirming the optimality of our algorithm (up to logarithmic factors). Extensive numerical experiments are conducted to illustrate the efficiency and robustness of the proposed algorithm in non-stationary dynamic pricing.
Oct 29, 2026

Optimal Contextual Pricing in Non-Stationary Environments

We study contextual dynamic pricing in a non-stationary environment. In each round, a seller observes a buyer's context, posts a price, and receives only binary purchase feedback. The buyer's value is linear in the context and an unobserved feature vector that may change over time, subject to a known total variation budget VV. We measure dynamic regret against the first-best benchmark that extracts each buyer's full value. For identical contexts, we develop a deterministic algorithm that combines binary-search exploration, lower-envelope pricing, and periodic and inconsistency-triggered restarts. It achieves regret O((TV+1)log⁡T)O((\sqrt{TV}+1)\log T). With heterogeneous contexts, a new geometric difficulty arises: small feature changes can leave a relaxed feasible set narrow but far from the current feature vector. We address this difficulty through a multiscale shallow-pricing algorithm that maintains relaxed feasible sets and enclosing ellipsoids at several variation scales. Larger scales provide reliable localization certificates, while the smallest active scale determines the exploitation price. The algorithm achieves dynamic regret O((d2+d3/2TV)log⁡2T)O((d^2+d^{3/2}\sqrt{TV})\log^2 T), where dd is the context dimension. For fixed dd, both guarantees match the lower bound Ω(TV+log⁡log⁡T)Ω(\sqrt{TV}+\log\log T) up to logarithmic factors in TT, establishing near-optimality among deterministic algorithms for every V∈[0,T]V\in[0,T], including the stationary case.
May 7, 2026

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

We study contextual dynamic pricing with linear valuations and bounded-support agnostic noise, whose induced demand curve may be non-Lipschitz with arbitrary jumps and atoms. Such discontinuities break the cross-context interpolation arguments used by smooth-demand pricing algorithms, while the best previous method achieved only O~(T3/4)\tilde O(T^{3/4}) regret. We propose Conservative-Markdown Redirect-UCB Pricing, a polynomial-time algorithm that combines randomized parameter estimation, conservative residual-grid probing, and confidence-based one-step redirection. Our algorithm achieves O~(T2/3)\tilde O(T^{2/3}) optimal regret, matching the known lower bounds of Kleinberg and Leighton (2003) up to logarithmic factors and improving over the previous upper bound of Xu and Wang (2022). Under stochastic well-conditioned contexts, this closes the long-existing open regret gap in linear-valuation contextual pricing under agnostic non-Lipschitz noise distribution.