mlsanityData to 14 Oct 2026

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

arXiv 2605.05609 ↗First posted 7 May 2026cs.LG econ.EM stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

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(T3/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(T2/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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 25 of its 52 references that are in the map. First posted on arXiv 7 May 2026.

Builds on

25 of 52 references.

References · 25

  1. 2016Dynamic Pricing in High-dimensionscited by 55
  2. 2020Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctionscited by 34
  3. 2021Bilateral Trade: A Regret Minimization Perspectivecited by 29
  4. 2016Multidimensional Binary Search for Contextual Decision-Makingcited by 27
  5. 2018Contextual Search via Intrinsic Volumescited by 26
  6. 2018Dynamic Pricing with Finitely Many Unknown Valuationscited by 23
  7. 2020Privacy-Preserving Dynamic Personalized Pricing with Demand Learningcited by 23
  8. 2021Policy Optimization Using Semi-parametric Models for Dynamic Pricingcited by 23
  9. 2021Logarithmic Regret in Feature-based Dynamic Pricingcited by 22
  10. 2021Distribution-free Contextual Dynamic Pricingcited by 22
  11. 2022Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noisecited by 21
  12. 2017Perishability of Data: Dynamic Pricing under Varying-Coefficient Modelscited by 19
13 more
  1. 2019Semi-parametric dynamic contextual pricingcited by 17
  2. 2019Online Pricing with Offline Data: Phase Transition and Inverse Square Lawcited by 13
  3. 2019Multi-Product Dynamic Pricing in High-Dimensions with Heterogeneous Price Sensitivitycited by 12
  4. 2024Improved Algorithms for Contextual Dynamic Pricingcited by 11
  5. 2022Doubly Fair Dynamic Pricingcited by 8
  6. 2020Uncertainty Quantification for Demand Prediction in Contextual Dynamic Pricingcited by 7
  7. 2021Fairness-aware Online Price Discrimination with Nonparametric Demand Modelscited by 7
  8. 2023Pricing with Contextual Elasticity and Heteroscedastic Valuationcited by 5
  9. 2025Online Pricing and Allocation with Demand Learning and Fulfillment Costcited by 4
  10. 2025Dynamic Pricing in the Linear Valuation Model using Shape Constraintscited by 4
  11. 2025Dynamic Pricing with Adversarially-Censored Demandscited by 4
  12. 2025Online Decision Making with Generative Action Setscited by 3
  13. 2024Minimax Optimality in Contextual Dynamic Pricing with General Valuation Modelscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenuecited by 0
  2. 2026When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregationcited by 0