# Phase Transitions in Learning and Earning under Price Protection Guarantee

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 3 Nov 2022.

## Builds on (most cited first, 10 of 10)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://mlsanity.com/paper/1902.10918/) (2019)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (2016)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Online Pricing with Offline Data: Phase Transition and Inverse Square Law](https://mlsanity.com/paper/1910.08693/) (2019)
- [Online Learning and Optimization for Revenue Management Problems with Add-on Discounts](https://mlsanity.com/paper/2005.00947/) (2020)

## Abstract (arXiv)

Motivated by the prevalence of ``price protection guarantee", which allows a customer who purchased a product in the past to receive a refund from the seller during the so-called price protection period (typically defined as a certain time window after the purchase date) in case the seller decides to lower the price, we study the impact of such policy on the design of online learning algorithm for data-driven dynamic pricing with initially unknown customer demand. We consider a setting where a firm sells a product over a horizon of T time steps. For this setting, we characterize how the value of M, the length of price protection period, can affect the optimal regret of the learning process. We show that the optimal regret is tildeTheta(√T+minM,,T2/3) by first establishing a fundamental impossible regime with novel regret lower bound instances. Then, we propose LEAP, a phased exploration type algorithm for underlineLearning and underlineEArning under underlinePrice Protection to match this lower bound up to logarithmic factors or even doubly logarithmic factors (when there are only two prices available to the seller). Our results reveal the surprising phase transitions of the optimal regret with respect to M. Specifically, when M is not too large, the optimal regret has no major difference when compared to that of the classic setting with no price protection guarantee. We also show that there exists an upper limit on how much the optimal regret can deteriorate when M grows large. Finally, we conduct extensive numerical experiments to show the benefit of LEAP over other heuristic methods for this problem.