Contextual Dynamic Pricing with Heterogeneous Buyers
Thodoris Lykouris, Sloan Nietert, Princewill Okoroafor, Chara Podimata, Julian Zimmert
We initiate the study of contextual dynamic pricing with a heterogeneous population of buyers, where a seller repeatedly (over $T$ rounds) posts prices that depend on the observable $d$ dimensional context and receives binary purchase feedback. Unlike prior work assuming homogeneous buyer types, in our setting the buyer's valuation type is drawn from an unknown distribution with finite support $K_{\star}$. We develop a contextual pricing algorithm based on Optimistic Posterior Sampling with regret $\tilde{O}(K_{\star}\sqrt{dT})$, which we prove to be tight in $d, T$ up to logarithmic terms. Finally, we refine our analysis for the non-contextual pricing case, proposing a variance-aware Zooming algorithm that achieves the optimal dependence on $K_{\star}$.