Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

• URL: http://arxiv.org/abs/2605.05609v1
• Date: Thu, 07 May 2026 02:57:14 GMT
• Title: Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand
• Abstract summary: We study contextual dynamic pricing with linear valuations and bounded-support noise, whose induced demand curve may be non-Lipschitz with arbitrary jumps and atoms.<n>We propose Conservative-Markdown Redirect-UCB Pricing, a time algorithm that combines randomized parameter estimation, conservative residualgrid probing, and confidence-based one-step redirection.
• Score: 24.75795278671755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenue [6.201103695201767]
  We study contextual dynamic pricing withBounded, possibly nonbinary purchase quantities.<n>We impose neither concavity nor strongmodality on revenue and allow uniunique optimal prices.
  arXiv  Detail & Related papers  (2026-08-04T05:14:26Z)
• Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
  We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses.<n>We establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction.
  arXiv  Detail & Related papers  (2026-06-06T07:40:55Z)
• A Perturbation Approach to Unconstrained Linear Bandits [48.45987210959519]
  We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO)<n>We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem.
  arXiv  Detail & Related papers  (2026-03-30T09:17:46Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes.<n>We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds.<n>This is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards.
  arXiv  Detail & Related papers  (2026-03-29T21:51:33Z)
• Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits [1.2010968598596632]
  We study the linear bandit problem with multiple arms over $T$ rounds.<n>We show that Lasso estimators are provably suboptimal in the sequential setting.<n>We propose a three-stage arm selection algorithm that uses thresholded Lasso as the main estimation method.
  arXiv  Detail & Related papers  (2025-05-23T02:20:00Z)
• Dynamic Pricing in the Linear Valuation Model using Shape Constraints [21.319339643047826]
  We propose a shape-constrained approach to dynamic pricing for censored data in the linear valuation model.<n>Our method attains lower empirical regret in comparison to several existing methods in the literature.
  arXiv  Detail & Related papers  (2025-02-09T04:58:33Z)
• Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models [8.981637739384674]
  We study contextual dynamic pricing, where a decision maker posts personalized prices based on observable contexts.<n>Each valuation is modeled as an unknown latent function of the context, corrupted by independent and identically distributed market noise.
  arXiv  Detail & Related papers  (2024-06-24T23:43:56Z)
• Contextual Dynamic Pricing: Algorithms, Optimality, and Local Differential Privacy Constraints [10.057344315478709]
  We study contextual dynamic pricing problems where a firm sells products to $T$ sequentially-arriving consumers.<n>We first show the optimal regret is of order $sqrtdT$, up to logarithmic factors.<n>We extend our study to dynamic pricing under mixed privacy constraints, improving the privacy-utility tradeoff by leveraging public data.
  arXiv  Detail & Related papers  (2024-06-04T15:44:10Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinitehorizon discounted decision process (MDP) We show that given any estimate for the optimal quality function $Q*$, the regret of the policy it defines converges at a rate given by the exponentiation of the $Q*$-estimate's pointwise convergence rate.
  arXiv  Detail & Related papers  (2021-01-31T16:17:56Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.