# Dynamic Pricing with Finitely Many Unknown Valuations

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2018.

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

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Policy Optimization Using Semi-parametric Models for Dynamic Pricing](https://mlsanity.com/paper/2109.06368/) (2021)
- [Distribution-free Contextual Dynamic Pricing](https://mlsanity.com/paper/2109.07340/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [Dynamic Pricing in the Linear Valuation Model using Shape Constraints](https://mlsanity.com/paper/2502.05776/) (2025)
- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models](https://mlsanity.com/paper/2406.17184/) (2024)
- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning](https://mlsanity.com/paper/2310.07558/) (2023)
- [Mode Estimation with Partial Feedback](https://mlsanity.com/paper/2402.13079/) (2024)
- [Making the most of your day: online learning for optimal allocation of time](https://mlsanity.com/paper/2102.08087/) (2021)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)
- [Parameter-Adaptive Dynamic Pricing](https://mlsanity.com/paper/2503.00929/) (2025)
- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)
- [Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions](https://mlsanity.com/paper/2605.22438/) (2026)
- [Learning to Price and Stock Under Contextual and Censored Demand](https://mlsanity.com/paper/2609.06083/) (2026)

## Abstract (arXiv)

Motivated by posted price auctions where buyers are grouped in an unknown number of latent types characterized by their private values for the good on sale, we investigate revenue maximization in stochastic dynamic pricing when the distribution of buyers' private values is supported on an unknown set of points in [0,1] of unknown cardinality K. This setting can be viewed as an instance of a stochastic K-armed bandit problem where the location of the arms (the K unknown valuations) must be learned as well. In the distribution-free case, we prove that our setting is just as hard as K-armed stochastic bandits: no algorithm can achieve a regret significantly better than √KT, (where T is the time horizon); we present an efficient algorithm matching this lower bound up to logarithmic factors. In the distribution-dependent case, we show that for all K>2 our setting is strictly harder than K-armed stochastic bandits by proving that it is impossible to obtain regret bounds that grow logarithmically in time or slower. On the other hand, when a lower bound γ>0 on the smallest drop in the demand curve is known, we prove an upper bound on the regret of order (1/Delta+(log log T)/γ2)(Klog T). This is a significant improvement on previously known regret bounds for discontinuous demand curves, that are at best of order (K12/γ8)√T. When K=2 in the distribution-dependent case, the hardness of our setting reduces to that of a stochastic 2-armed bandit: we prove that an upper bound of order (log T)/Delta (up to loglog factors) on the regret can be achieved with no information on the demand curve. Finally, we show a O(√T) upper bound on the regret for the setting in which the buyers' decisions are nonstochastic, and the regret is measured with respect to the best between two fixed valuations one of which is known to the seller.