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.