arXiv 11 Oct 2023 · Statistics — Machine Learning
arXiv:2310.07558 · PDF · DOI · OpenAlex · Extracted main text
We study the dynamic pricing problem where the demand function is nonparametric and H\"older smooth, and we focus on adaptivity to the unknown H\"older smoothness parameter $\beta$ of the demand function. Traditionally the optimal dynamic pricing algorithm heavily relies on the knowledge of $\beta$ to achieve a minimax optimal regret of $\widetilde{O}(T^{\frac{\beta+1}{2\beta+1}})$. However, we highlight the challenge of adaptivity in this dynamic pricing problem by proving that no pricing policy can adaptively achieve this minimax optimal regret without knowledge of $\beta$. Motivated by the impossibility result, we propose a self-similarity condition to enable adaptivity. Importantly, we show that the self-similarity condition does not compromise the problem's inherent complexity since it preserves the regret lower bound $\Omega(T^{\frac{\beta+1}{2\beta+1}})$. Furthermore, we develop a smoothness-adaptive dynamic pricing algorithm and theoretically prove that the algorithm achieves this minimax optimal regret bound without the prior knowledge $\beta$.
appendix boundary found by none_found · 100% 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 | Gur, Y., Momeni, A., and Wager, S (2022) Smoothness-adaptive contextual bandits | 0.928 | 4 | 3 | 100% |
| 2 | Wang, Y., Chen, B., and Simchi-Levi, D (2021) Multimodal dynamic pricing | 0.928 | 4 | 3 | 100% |
| 3 | Bu, J., Simchi-Levi, D., and Wang, C (2022) Context-based dynamic pricing with partially linear demand model | 0.644 | 2 | 2 | 100% |
| 4 | Kleinberg, R. and Leighton, T (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions | 0.644 | 2 | 2 | 100% |
| 5 | Cai, T. T. and Pu, H (2022) Stochastic continuum-armed bandits with additive models: Minimax regrets and adaptive algorithm | 0.511 | 2 | 1 | 100% |
| 6 | Tropp, J. A (2012) User-friendly tail bounds for sums of random matrices | 0.511 | 2 | 1 | 100% |
| 7 | Abbasi-Yadkori, Y., Pal, D., and Szepesvari, C (2012) Online-to-confidence-set conversions and application to sparse stochastic bandits | 0.405 | 1 | 1 | 100% |
| 8 | Ban, G.-Y. and Keskin, N. B (2021) Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity | 0.405 | 1 | 1 | 100% |
| 9 | Besbes, O. and Zeevi, A (2009) Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms | 0.405 | 1 | 1 | 100% |
| 10 | Besbes, O. and Zeevi, A (2012) Blind network revenue management | 0.405 | 1 | 1 | 100% |
Showing the top 10 of 27 scored citations.