arXiv 7 May 2026 · Machine Learning
arXiv:2605.05609 · PDF · DOI · OpenAlex · Extracted main text
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 $\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 $\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.
appendix boundary found by appendix_command · 52% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Jianyu Xu and Yu-Xiang Wang (2022) Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise self | 0.920 | 9 | 6 | 78% |
| 2 | Robert Kleinberg and Tom Leighton (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions | 0.874 | 6 | 5 | 67% |
| 3 | Gah-Yi Ban and N Bora Keskin (2021) Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity | 0.737 | 3 | 3 | 67% |
| 4 | Jianqing Fan, Yongyi Guo, and Mengxin Yu (2024) Policy optimization using semiparametric models for dynamic pricing | 0.737 | 3 | 3 | 67% |
| 5 | Adel Javanmard and Hamid Nazerzadeh (2019) Dynamic pricing in high-dimensions | 0.737 | 3 | 3 | 67% |
| 6 | Yiyun Luo, Will Wei Sun, and Yufeng Liu (2022) Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets | 0.644 | 2 | 2 | 100% |
| 7 | Matilde Tullii, Solenne Gaucher, Nadav Merlis, and Vianney Perchet (2024) Improved algorithms for contextual dynamic pricing | 0.644 | 2 | 2 | 100% |
| 8 | Maxime C Cohen, Ilan Lobel, and Renato Paes Leme (2020) Feature-based dynamic pricing | 0.511 | 2 | 2 | 50% |
| 9 | Renato Paes Leme and Jon Schneider (2018) Contextual search via intrinsic volumes | 0.000 | 2 | 1 | 0% |
| 10 | Renato Paes Leme, Chara Podimata, and Jon Schneider (2022) Corruption-robust contextual search through density updates | 0.000 | 2 | 1 | 0% |
Showing the top 10 of 52 scored citations.