Online Pricing with Offline Data: Phase Transition and Inverse Square
  Law
  This paper investigates the impact of pre-existing offline data on online
learning, in the context of dynamic pricing. We study a single-product dynamic
pricing problem over a selling horizon of $T$ periods. The demand in each
period is determined by the price of the product according to a linear demand
model with unknown parameters. We assume that before the start of the selling
horizon, the seller already has some pre-existing offline data. The offline
data set contains $n$ samples, each of which is an input-output pair consisting
of a historical price and an associated demand observation. The seller wants to
utilize both the pre-existing offline data and the sequential online data to
minimize the regret of the online learning process.
  We characterize the joint effect of the size, location and dispersion of the
offline data on the optimal regret of the online learning process.
Specifically, the size, location and dispersion of the offline data are
measured by the number of historical samples $n$, the distance between the
average historical price and the optimal price $\delta$, and the standard
deviation of the historical prices $\sigma$, respectively. We show that the
optimal regret is $\widetilde \Theta\left(\sqrt{T}\wedge \frac{T}{(n\wedge
T)\delta^2+n\sigma^2}\right)$, and design a learning algorithm based on the
"optimism in the face of uncertainty" principle, whose regret is optimal up to
a logarithmic factor. Our results reveal surprising transformations of the
optimal regret rate with respect to the size of the offline data, which we
refer to as phase transitions. In addition, our results demonstrate that the
location and dispersion of the offline data also have an intrinsic effect on
the optimal regret, and we quantify this effect via the inverse-square law.
