Timezone: »

 
Poster
Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing
Jonas Mueller · Vasilis Syrgkanis · Matt Taddy

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #3
in Algorithms -- Bandit Algorithms »

We consider dynamic pricing with many products under an evolving but low-dimensional demand model. Assuming the temporal variation in cross-elasticities exhibits low-rank structure based on fixed (latent) features of the products, we show that the revenue maximization problem reduces to an online bandit convex optimization with side information given by the observed demands. We design dynamic pricing algorithms whose revenue approaches that of the best fixed price vector in hindsight, at a rate that only depends on the intrinsic rank of the demand model and not the number of products. Our approach applies a bandit convex optimization algorithm in a projected low-dimensional space spanned by the latent product features, while simultaneously learning this span via online singular value decomposition of a carefully-crafted matrix containing the observed demands.

Keywords: Bandit Algorithms · Algorithms · Algorithms -> Components Analysis (e.g., CCA, ICA, LDA, PCA); Algorithms -> Online Learning; Algorithms · Spectral Methods; Ap
[ Paper]  [ Poster] 

Author Information

Jonas Mueller (Amazon Web Services)
Vasilis Syrgkanis (Microsoft Research)
Matt Taddy (Chicago Booth)

More from the Same Authors