Timezone: »

 
Spotlight
Logarithmic Regret in Feature-based Dynamic Pricing
Jianyu Xu · Yu-Xiang Wang

@
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 [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.

Author Information

Jianyu Xu (University of California, Santa Barbara)

Jianyu Xu is a third-year Ph.D. student in Computer Science at UC Santa Barbara. He has a broad research interest in theoretical problems, including statistical machine learning, bandits, and tensor calculus. Currently he is working with Prof. Yu-Xiang Wang on online dynamic pricing problems. Before joining UCSB, Jianyu received his B.S. of Engineering at Tsinghua University, China, where his research mainly focused on the computational complexity of tensor network contractions.

Yu-Xiang Wang (UC Santa Barbara)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors