Learning in Random Utility Models Via Online Decision Problems

This paper studies the Random Utility Model (RUM) in a repeated stochastic choice situation, in which the decision maker is imperfectly informed about the payoffs associated to each of the available alternatives. By embedding the RUM into an online decision problem, we develop a gradient-based learning algorithm and establish that a large class of RUMs are Hannan consistent (\citet{Hahn1957}); that is, the average difference between the expected payoffs generated by a RUM and that of the best fixed policy in hindsight goes to zero as the number of periods increase. We show that the class of Generalized Extreme Value (GEV) models can be implemented with our learning algorithm. Examples in the GEV class include the Generalized Nested Logit, Ordered GEV, and Product Differentiation models among many others. In addition, we show that our gradient-based algorithm is equivalent to the Follow the Regularized Leader (FTRL) algorithm, which is widely used in the Machine Learning literature to model learning in repeated stochastic choice problems. Thus the FTRL algorithm can be understood in an economically grounded optimization framework. Finally, we discuss how our approach can incorporate the recency bias effect and be used to implement prediction markets in general environments