IDEAS home Printed from https://ideas.repec.org/a/bla/ijethy/v21y2025i4p494-526.html

Learning in random utility models via online decision problems

Author

Listed:
  • Emerson Melo

Abstract

This paper examines the Random Utility Model (RUM) in repeated stochastic choice settings where decision‐makers lack full information about payoffs. We propose a gradient‐based learning algorithm that embeds RUM into an online decision‐making framework. Our analysis establishes Hannan consistency for a broad class of RUMs, meaning the average regret relative to the best fixed action in hindsight vanishes over time. We also show that our algorithm is equivalent to the Follow‐The‐Regularized‐Leader method, offering an economically grounded approach to online optimization. Applications include modeling recency bias and characterizing coarse correlated equilibria in normal‐form games.

Suggested Citation

  • Emerson Melo, 2025. "Learning in random utility models via online decision problems," International Journal of Economic Theory, The International Society for Economic Theory, vol. 21(4), pages 494-526, December.
    • Handle: RePEc:bla:ijethy:v:21:y:2025:i:4:p:494-526
    DOI: 10.1111/ijet.70006
    as

    Download full text from publisher

    File URL: https://doi.org/10.1111/ijet.70006
    Download Restriction: no
    File URL: https://libkey.io/10.1111/ijet.70006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Mogens Fosgerau & Emerson Melo & André de Palma & Matthew Shum, 2020. "Discrete Choice And Rational Inattention: A General Equivalence Result," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 61(4), pages 1569-1589, November.
    2. Marina Agranov & Pietro Ortoleva, 2017. "Stochastic Choice and Preferences for Randomization," Journal of Political Economy, University of Chicago Press, vol. 125(1), pages 40-68.
    3. Fudenberg, Drew & Levine, David K., 1995. "Consistency and cautious fictitious play," Journal of Economic Dynamics and Control, Elsevier, vol. 19(5-7), pages 1065-1089.
    4. David E. Bell, 1982. "Regret in Decision Making under Uncertainty," Operations Research, INFORMS, vol. 30(5), pages 961-981, October.
    5. Wen, Chieh-Hua & Koppelman, Frank S., 2001. "The generalized nested logit model," Transportation Research Part B: Methodological, Elsevier, vol. 35(7), pages 627-641, August.
    6. Robert J. Aumann, 2025. "Subjectivity and Correlation in Randomized Strategies," World Scientific Book Chapters, in: SELECTED CONTRIBUTIONS TO GAME THEORY, chapter 4, pages 73-113, World Scientific Publishing Co. Pte. Ltd..
    7. Guiyun Feng & Xiaobo Li & Zizhuo Wang, 2017. "Technical Note—On the Relation Between Several Discrete Choice Models," Operations Research, INFORMS, vol. 65(6), pages 1516-1525, December.
    8. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October.
    9. Hayashi, Takashi, 2008. "Regret aversion and opportunity dependence," Journal of Economic Theory, Elsevier, vol. 139(1), pages 242-268, March.
    10. Train,Kenneth E., 2009. "Discrete Choice Methods with Simulation," Cambridge Books, Cambridge University Press, number 9780521766555.
    11. Gualdani, Cristina & Sinha, Shruti, 2024. "Identification in discrete choice models with imperfect information," Journal of Econometrics, Elsevier, vol. 244(1).
    12. repec:cup:cbooks:9781316779309 is not listed on IDEAS
    13. Filip Matêjka & Alisdair McKay, 2015. "Rational Inattention to Discrete Choices: A New Foundation for the Multinomial Logit Model," American Economic Review, American Economic Association, vol. 105(1), pages 272-298, January.
    14. S. Cerreia-Vioglio & F. Maccheroni & M. Marinacci & A. Rustichini, 2017. "Multinomial logit processes and preference discovery: inside and outside the black box," Working Papers 615, IGIER (Innocenzo Gasparini Institute for Economic Research), Bocconi University.
    15. Sergiu Hart & Andreu Mas-Colell, 2013. "Regret-Based Continuous-Time Dynamics," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 5, pages 99-124, World Scientific Publishing Co. Pte. Ltd..
    16. Andrew Caplin & Mark Dean, 2015. "Revealed Preference, Rational Inattention, and Costly Information Acquisition," American Economic Review, American Economic Association, vol. 105(7), pages 2183-2203, July.
    17. Han Bleichrodt & Peter P. Wakker, 2015. "Regret Theory: A Bold Alternative to the Alternatives," Economic Journal, Royal Economic Society, vol. 0(583), pages 493-532, March.
    18. Roughgarden,Tim, 2016. "Twenty Lectures on Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9781316624791.
    19. Drew Fudenberg & Ryota Iijima & Tomasz Strzalecki, 2015. "Stochastic Choice and Revealed Perturbed Utility," Econometrica, Econometric Society, vol. 83, pages 2371-2409, November.
    20. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, December.
    21. Roughgarden,Tim, 2016. "Twenty Lectures on Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9781107172661.
    22. Sergiu Hart & Andreu Mas-Colell, 2013. "A General Class Of Adaptive Strategies," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 3, pages 47-76, World Scientific Publishing Co. Pte. Ltd..
    23. Paulo Natenzon, 2019. "Random Choice and Learning," Journal of Political Economy, University of Chicago Press, vol. 127(1), pages 419-457.
    24. Panayotis Mertikopoulos & William H. Sandholm, 2016. "Learning in Games via Reinforcement and Regularization," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1297-1324, November.
    25. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    26. Loomes, Graham & Sugden, Robert, 1982. "Regret Theory: An Alternative Theory of Rational Choice under Uncertainty," Economic Journal, Royal Economic Society, vol. 92(368), pages 805-824, December.
    27. Josef Hofbauer & William H. Sandholm, 2002. "On the Global Convergence of Stochastic Fictitious Play," Econometrica, Econometric Society, vol. 70(6), pages 2265-2294, November.
    28. Todd Sarver, 2008. "Anticipating Regret: Why Fewer Options May Be Better," Econometrica, Econometric Society, vol. 76(2), pages 263-305, March.
    29. Ryan Webb, 2019. "The (Neural) Dynamics of Stochastic Choice," Management Science, INFORMS, vol. 65(1), pages 230-255, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    2. Emerson Melo, 2021. "Learning In Random Utility Models Via Online Decision Problems," CAEPR Working Papers 2022-003 Classification-D, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    3. Emerson Melo, 2025. "Learning in Random Utility Models Via Online Decision Problems," Papers 2506.16030, arXiv.org.
    4. Emerson Melo, 2022. "On the uniqueness of quantal response equilibria and its application to network games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 74(3), pages 681-725, October.
    5. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    6. Sean Duffy & John Smith, 2025. "An economist and a psychologist form a line: What can imperfect perception of length tell us about stochastic choice?," Theory and Decision, Springer, vol. 99(3), pages 701-734, November.
    7. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    8. Heydari, Pedram, 2024. "Regret, responsibility, and randomization: A theory of stochastic choice," Journal of Economic Theory, Elsevier, vol. 217(C).
    9. Tommaso Denti & Doron Ravid, 2023. "Robust Predictions in Games with Rational Inattention," Papers 2306.09964, arXiv.org.
    10. Germano, Fabrizio & Lugosi, Gabor, 2007. "Global Nash convergence of Foster and Young's regret testing," Games and Economic Behavior, Elsevier, vol. 60(1), pages 135-154, July.
    11. Simone Cerreia-Vioglio & Fabio Maccheroni & Massimo Marinacci, 2020. "Multinomial logit processes and preference discovery: outside and inside the black box," Working Papers 663, IGIER (Innocenzo Gasparini Institute for Economic Research), Bocconi University.
    12. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    13. Qin, Jie, 2020. "Regret-based capital asset pricing model," Journal of Banking & Finance, Elsevier, vol. 114(C).
    14. Duffy, Sean & Gussman, Steven & Smith, John, 2021. "Visual judgments of length in the economics laboratory: Are there brains in stochastic choice?," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 93(C).
    15. S. Cerreia-Vioglio & F. Maccheroni & M. Marinacci & A. Rustichini, 2017. "Multinomial logit processes and preference discovery: inside and outside the black box," Working Papers 615, IGIER (Innocenzo Gasparini Institute for Economic Research), Bocconi University.
    16. Claudia Cerrone & Francesco Feri & Philip R. Neary, 2019. "Ignorance is bliss: a game of regret," Discussion Paper Series of the Max Planck Institute for Behavioral Economics 2019_10, Max Planck Institute for Behavioral Economics.
    17. Julien Monardo, 2025. "Functional Form and Shape Restrictions in Discrete Choice Models," Bristol Economics Discussion Papers 25/813, School of Economics, University of Bristol, UK.
    18. Diecidue, Enrico & Somasundaram, Jeeva, 2017. "Regret theory: A new foundation," Journal of Economic Theory, Elsevier, vol. 172(C), pages 88-119.
    19. Mogens Fosgerau & John Rehbeck, 2023. "Nontransitive Preferences and Stochastic Rationalizability: A Behavioral Equivalence," Papers 2304.14631, arXiv.org.
    20. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Jun 2026.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:bla:ijethy:v:21:y:2025:i:4:p:494-526. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: http://www.blackwellpublishing.com/journal.asp?ref=1742-7355 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.