  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
$\tilde{\Theta}(\sqrt{T}+\min\{M,\,T^{2/3}\})$ by first establishing a
fundamental impossible regime with novel regret lower bound instances. Then, we
propose LEAP, a phased exploration type algorithm for \underline{L}earning and
\underline{EA}rning under \underline{P}rice 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.
