# Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

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

## 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 (most cited first, 25 of 25)

- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Dynamic Pricing with Finitely Many Unknown Valuations](https://mlsanity.com/paper/1807.03288/) (2018)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [Policy Optimization Using Semi-parametric Models for Dynamic Pricing](https://mlsanity.com/paper/2109.06368/) (2021)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Distribution-free Contextual Dynamic Pricing](https://mlsanity.com/paper/2109.07340/) (2021)
- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Perishability of Data: Dynamic Pricing under Varying-Coefficient Models](https://mlsanity.com/paper/1701.03537/) (2017)
- [Semi-parametric dynamic contextual pricing](https://mlsanity.com/paper/1901.02045/) (2019)
- [Online Pricing with Offline Data: Phase Transition and Inverse Square Law](https://mlsanity.com/paper/1910.08693/) (2019)
- [Multi-Product Dynamic Pricing in High-Dimensions with Heterogeneous Price Sensitivity](https://mlsanity.com/paper/1901.01030/) (2019)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Uncertainty Quantification for Demand Prediction in Contextual Dynamic Pricing](https://mlsanity.com/paper/2003.07017/) (2020)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [Pricing with Contextual Elasticity and Heteroscedastic Valuation](https://mlsanity.com/paper/2312.15999/) (2023)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (2025)
- [Dynamic Pricing in the Linear Valuation Model using Shape Constraints](https://mlsanity.com/paper/2502.05776/) (2025)
- [Dynamic Pricing with Adversarially-Censored Demands](https://mlsanity.com/paper/2502.06168/) (2025)
- [Online Decision Making with Generative Action Sets](https://mlsanity.com/paper/2509.25777/) (2025)
- [Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models](https://mlsanity.com/paper/2406.17184/) (2024)

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

- [Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenue](https://mlsanity.com/paper/2608.03142/) (2026)
- [When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregation](https://mlsanity.com/paper/2609.36704/) (2026)

## 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.