  Feature-based dynamic pricing is an increasingly popular model of setting
prices for highly differentiated products with applications in digital
marketing, online sales, real estate and so on. The problem was formally
studied as an online learning problem (Cohen et al., 2016; Javanmard &
Nazerzadeh, 2019) where a seller needs to propose prices on the fly for a
sequence of $T$ products based on their features $x$ while having a small
regret relative to the best -- "omniscient" -- pricing strategy she could have
come up with in hindsight. We revisit this problem and provide two algorithms
(EMLP and ONSP) for stochastic and adversarial feature settings, respectively,
and prove the optimal $O(d\log{T})$ regret bounds for both. In comparison, the
best existing results are $O\left(\min\left\{\frac{1}{\lambda_{\min}^2}\log{T},
\sqrt{T}\right\}\right)$ and $O(T^{2/3})$ respectively, with $\lambda_{\min}$
being the smallest eigenvalue of $\mathbb{E}[xx^T]$ that could be arbitrarily
close to $0$. We also prove an $\Omega(\sqrt{T})$ information-theoretic lower
bound for a slightly more general setting, which demonstrates that
"knowing-the-demand-curve" leads to an exponential improvement in feature-based
dynamic pricing.
