Dynamic assortment personalization in high dimensions

DOI10.1287/OPRE.2019.1948zbMATH Open1451.90077arXiv1610.05604OpenAlexW3024987513MaRDI QIDQ3387950FDOQ3387950

Authors: Nathan Kallus, Madeleine Udell 

Publication date: 8 January 2021

Published in: Operations Research (Search for Journal in Brave)

Abstract: We study the problem of dynamic assortment personalization with large, heterogeneous populations and wide arrays of products, and demonstrate the importance of structural priors for effective, efficient large-scale personalization. Assortment personalization is the problem of choosing, for each individual (type), a best assortment of products, ads, or other offerings (items) so as to maximize revenue. This problem is central to revenue management in e-commerce and online advertising where both items and types can number in the millions. We formulate the dynamic assortment personalization problem as a discrete-contextual bandit with $m$ contexts (types) and exponentially many arms (assortments of the $n$ items). We assume that each type's preferences follow a simple parametric model with $n$ parameters. In all, there are $mn$ parameters, and existing literature suggests that order optimal regret scales as $mn$. However, the data required to estimate so many parameters is orders of magnitude larger than the data available in most revenue management applications; and the optimal regret under these models is unacceptably high. In this paper, we impose a natural structure on the problem -- a small latent dimension, or low rank. In the static setting, we show that this model can be efficiently learned from surprisingly few interactions, using a time- and memory-efficient optimization algorithm that converges globally whenever the model is learnable. In the dynamic setting, we show that structure-aware dynamic assortment personalization can have regret that is an order of magnitude smaller than structure-ignorant approaches. We validate our theoretical results empirically.

Full work available at URL: https://arxiv.org/abs/1610.05604

Recommendations

• MNL-bandit: a dynamic learning approach to assortment selection
• Optimal policy for dynamic assortment planning under multinomial logit models
• Optimizing revenue while showing relevant assortments at scale
• Dynamic assortment optimization with a multinomial logit choice model and capacity constraint
• Approximation algorithms for dynamic assortment optimization models

zbMATH Keywords

high-dimensional statisticsmatrix completionrecommender systemsdiscrete choicecontextual banditpersonalizationassortment planningfirst-order optimization

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Consumer behavior, demand theory (91B42)

Cites Work

• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
• Generalized low rank models
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• A Singular Value Thresholding Algorithm for Matrix Completion
• Title not available (Why is that?)
• 1-bit matrix completion
• Exact matrix completion via convex optimization
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• User-friendly tail bounds for sums of random matrices
• Asymptotically efficient adaptive allocation rules
• Matrix Completion From a Few Entries
• Assortment optimization under variants of the nested logit model
• Dynamic assortment optimization with a multinomial logit choice model and capacity constraint
• Prospect Theory: An Analysis of Decision under Risk
• Sparse Approximate Solutions to Semidefinite Programs
• The multi-armed bandit problem with covariates
• Combinatorial Optimization with Rational Objective Functions
• Low-rank matrix completion using alternating minimization
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Dynamic assortment with demand learning for seasonal consumer goods
• Contextual bandits with similarity information
• The \(d\)-level nested logit model: assortment and price optimization problems
• A Markov chain approximation to choice modeling
• Online decision making with high-dimensional covariates
• A linear response bandit problem
• Designing choice sets for stated preference methods: The effects of complexity on choice consistency
• MNL-bandit: a dynamic learning approach to assortment selection

Cited In (12)

• Stochastic approximation for uncapacitated assortment optimization under the multinomial logit model
• Personalized retail promotions through a directed acyclic graph-based representation of customer preferences
• A review of revenue management: recent generalizations and advances in industry applications
• Dynamic pricing in high-dimensions
• Transfer learning for contextual multi-armed bandits
• A regret lower bound for assortment optimization under the capacitated MNL model with arbitrary revenue parameters
• Asymptotically Optimal Sequential Design for Rank Aggregation
• Smoothness-Adaptive Contextual Bandits
• Assortment optimization: a systematic literature review
• MNL-bandit: a dynamic learning approach to assortment selection
• Optimizing revenue while showing relevant assortments at scale
• Assortment optimization in omni-channel retailing

Uses Software

• LowRankModels
• Pyglrm
• HOGWILD

This page was built for publication: Dynamic assortment personalization in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387950)