Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach

Abstract:We study a ranking and selection problem of learning from choice-based feedback with dynamic assortments. In this problem, a company sequentially displays a set of items to a population of customers and collects their choices as feedback. The only information available about the underlying choice model is that the choice probabilities are consistent with some unknown true strict ranking over the items. The objective is to identify, with the fewest samples, the most preferred item or the full ranking over the items at a high confidence level. We propose novel and simple algorithms for both learning goals through a nested approach. For best-item identification, we introduce Nested Elimination (NE), and for full-ranking identification, we introduce Nested Partition (NP). Both algorithms are fast to run and admit instance-specific, non-asymptotic sample-complexity guarantees. By comparing these guarantees with information-theoretic lower bounds, we establish that both algorithms are asymptotically worst-case optimal. Our analysis is based on an analytical framework that characterizes the system dynamics through analyzing a sequence of multi-dimensional random walks. We further extend the problem to incorporate capacity-constrained displays. Numerical experiments on synthetic and real data corroborate our theory.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2307.09295 [cs.LG]

(or arXiv:2307.09295v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2307.09295 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.