提出新算法，显著降低非光滑需求下的动态定价误差。
Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand
- 结合随机参数估计与保守探测，实现精准价格调整。
- 达到理论最优的 × T^{2/3} 误差率，优于此前的 × T^{3/4}。
- 适用于需求突变场景，适合研究动态定价的学者使用。
我们研究线性估值下具有有界支持的未知噪声的上下文动态定价问题，其需求曲线可能为非利普希茨，存在任意跳跃和原子点。此类不连续性破坏了平滑需求算法依赖的跨上下文插值逻辑，而此前最优方法仅能实现 × T^{3/4} 的遗憾。本文提出 Conservative-Markdown Redirect-UCB 定价算法，结合随机参数估计、保守残差网格探测与基于置信度的一步重定向，可在多项式时间内实现 × T^{2/3} 的最优遗憾，与 Kleinberg 与 Leighton（2003）已知的下界在对数因子内一致，优于 Xu 与 Wang（2022）的上界。在随机良好条件的上下文假设下，该结果解决了线性估值上下文定价中长期存在的遗憾差距问题。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。