IDEAS home Printed from https://ideas.repec.org/p/eui/euiwps/eco2007-01.html
   My bibliography  Save this paper

Distribution-Free Learning

Author

Listed:
  • Karl H. Schlag

Abstract

We select among rules for learning which of two actions in a stationary decision problem achieves a higher expected payo¤when payoffs realized by both actions are known in previous instances. Only a bounded set containing all possible payoffs is known. Rules are evaluated using maximum risk with maximin utility, minimax regret, competitive ratio and selection procedures being special cases. A randomized variant of fictitious play attains minimax risk for all risk functions with ex-ante expected payoffs increasing in the number of observations. Fictitious play itself has neither of these two properties. Tight bounds on maximal regret and probability of selecting the best action are included.

Suggested Citation

  • Karl H. Schlag, 2007. "Distribution-Free Learning," Economics Working Papers ECO2007/01, European University Institute.
    • Handle: RePEc:eui:euiwps:eco2007/01
    as

    Download full text from publisher

    File URL: http://cadmus.iue.it/dspace/bitstream/1814/6689/3/ECO-2007-01.pdf
    File Function: main text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Schlag, Karl H., 1999. "Which one should I imitate?," Journal of Mathematical Economics, Elsevier, vol. 31(4), pages 493-522, May.
    2. Tilman Börgers & Antonio J. Morales & Rajiv Sarin, 2004. "Expedient and Monotone Learning Rules," Econometrica, Econometric Society, vol. 72(2), pages 383-405, March.
    3. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    4. Rustichini, Aldo, 1999. "Optimal Properties of Stimulus--Response Learning Models," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 244-273, October.
    5. Schlag, Karl H., 1998. "Why Imitate, and If So, How?, : A Boundedly Rational Approach to Multi-armed Bandits," Journal of Economic Theory, Elsevier, vol. 78(1), pages 130-156, January.
    6. Karl Schlag, 2006. "ELEVEN - Tests needed for a Recommendation," Economics Working Papers ECO2006/2, European University Institute.
    7. Jörg Stoye, 2011. "Statistical decisions under ambiguity," Theory and Decision, Springer, vol. 70(2), pages 129-148, February.
    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. Jonathan Newton, 2018. "Evolutionary Game Theory: A Renaissance," Games, MDPI, vol. 9(2), pages 1-67, May.
    2. Rivas, Javier, 2013. "Cooperation, imitation and partial rematching," Games and Economic Behavior, Elsevier, vol. 79(C), pages 148-162.
    3. Offerman, Theo & Schotter, Andrew, 2009. "Imitation and luck: An experimental study on social sampling," Games and Economic Behavior, Elsevier, vol. 65(2), pages 461-502, March.
    4. Erik Mohlin & Robert Ostling & Joseph Tao-yi Wang, 2014. "Learning by Imitation in Games: Theory, Field, and Laboratory," Economics Series Working Papers 734, University of Oxford, Department of Economics.
    5. Carlos Oyarzun & Johannes Ruf, 2009. "Monotone imitation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 41(3), pages 411-441, December.
    6. Jonas Hedlund & Carlos Oyarzun, 2018. "Imitation in heterogeneous populations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(4), pages 937-973, June.
    7. Michael Kosfeld, 2002. "Stochastic strategy adjustment in coordination games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 20(2), pages 321-339.
    8. Basov, S., 2001. "An Evolutionary Model of Reciprocity," Department of Economics - Working Papers Series 812, The University of Melbourne.
    9. Sartzetakis, Eftichios S. & Xepapadeas, Anastasios & Yannacopoulos, Athanasios, "undated". "Regulating the Environmental Consequences of Preferences for Social Status within an Evolutionary Framework," Climate Change and Sustainable Development 202440, Fondazione Eni Enrico Mattei (FEEM).
    10. Apesteguia, Jose & Huck, Steffen & Oechssler, Jorg, 2007. "Imitation--theory and experimental evidence," Journal of Economic Theory, Elsevier, vol. 136(1), pages 217-235, September.
    11. Arthur Charpentier & Romuald Élie & Carl Remlinger, 2023. "Reinforcement Learning in Economics and Finance," Computational Economics, Springer;Society for Computational Economics, vol. 62(1), pages 425-462, June.
    12. Funai, Naoki, 2022. "Reinforcement learning with foregone payoff information in normal form games," Journal of Economic Behavior & Organization, Elsevier, vol. 200(C), pages 638-660.
    13. Beggs, A.W., 2005. "On the convergence of reinforcement learning," Journal of Economic Theory, Elsevier, vol. 122(1), pages 1-36, May.
    14. Hopkins, Ed, 2007. "Adaptive learning models of consumer behavior," Journal of Economic Behavior & Organization, Elsevier, vol. 64(3-4), pages 348-368.
    15. Mengel Friederike & Rivas Javier, 2012. "An Axiomatization of Learning Rules when Counterfactuals are not Observed," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 12(1), pages 1-19, July.
    16. Naoki Funai, 2019. "Convergence results on stochastic adaptive learning," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(4), pages 907-934, November.
    17. repec:awi:wpaper:0419 is not listed on IDEAS
    18. Antonio J. Morales Siles, 2002. "Absolute Expediency and Imitative Behaviour," Economic Working Papers at Centro de Estudios Andaluces E2002/03, Centro de Estudios Andaluces.
    19. Mertikopoulos, Panayotis & Sandholm, William H., 2018. "Riemannian game dynamics," Journal of Economic Theory, Elsevier, vol. 177(C), pages 315-364.
    20. Cartwright, Edward, "undated". "Imitation and the emergence of Nash equilibrium play in games with many players," Economic Research Papers 269568, University of Warwick - Department of Economics.
    21. Selten, Reinhard & Apesteguia, Jose, 2005. "Experimentally observed imitation and cooperation in price competition on the circle," Games and Economic Behavior, Elsevier, vol. 51(1), pages 171-192, April.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness
    • D81 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Criteria for Decision-Making under Risk and Uncertainty
    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:eui:euiwps:eco2007/01. 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: Cécile Brière (email available below). General contact details of provider: https://edirc.repec.org/data/deiueit.html .

    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.