Best-item Learning in Random Utility Models with Subset Choices

Random utility models (RUMs) are a popular and well-established framework for studying behavioral choices by individuals and groups Thurstone [1927]. In a RUM with finite alternatives or items, a distribution on the preferred alternative(s) is assumed to arise from a random utility drawn from a distribution for each item, followed by rank ordering the items according to their utilities. Perhaps the most widely known RUM is the Plackett-Luce or multinomial logit model Plackett [1975], Luce [2012] which results when each item's utility is sampled from an additive model with a Gumbel-distributed perturbation. It is unique in the sense of enjoying the property of independence of irrelevant attributes (IIA), which is often key in permitting efficient inference of Plackett-Luce models from data Khetan and Oh [2016]. Other well-known RUMs include the probit model Bliss [1934] featuring random Gaussian perturbations to the intrinsic utilities, mixed logit, nested logit, etc. A long line of work in statistics and machine learning focuses on estimating RUM properties from observed data Soufiani et al. [2014], Zhao et al. [2018], Soufiani et al. [2013].