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. 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..
    3. Tilman Börgers & Antonio J. Morales & Rajiv Sarin, 2004. "Expedient and Monotone Learning Rules," Econometrica, Econometric Society, vol. 72(2), pages 383-405, March.
    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. Karl Schlag, 2006. "ELEVEN - Tests needed for a Recommendation," Economics Working Papers ECO2006/2, European University Institute.
    6. 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.
    7. Jörg Stoye, 2011. "Statistical decisions under ambiguity," Theory and Decision, Springer, vol. 70(2), pages 129-148, February.
    8. 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.
    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. Eftichios S. Sartzetakis & Anastasios Xepapadeas & Athanasios Yannacopoulos, 2015. "Regulating the Environmental Consequences of Preferences for Social Status within an Evolutionary Framework," Working Papers 2015.34, Fondazione Eni Enrico Mattei.
    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. 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.
    12. repec:awi:wpaper:0419 is not listed on IDEAS
    13. Antonio J. Morales Siles, 2002. "Absolute Expediency and Imitative Behaviour," Economic Working Papers at Centro de Estudios Andaluces E2002/03, Centro de Estudios Andaluces.
    14. Mertikopoulos, Panayotis & Sandholm, William H., 2018. "Riemannian game dynamics," Journal of Economic Theory, Elsevier, vol. 177(C), pages 315-364.
    15. Cartwright, Edward, 2003. "Imitation and the Emergence of Nash Equilibrium Play in Games with Many Players," The Warwick Economics Research Paper Series (TWERPS) 684, University of Warwick, Department of Economics.
    16. 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.
    17. Agastya, Murali & Slinko, Arkadii, 2015. "Dynamic choice in a complex world," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 232-258.
    18. Edward Cartwright, 2002. "Learning to play approximate Nash equilibria in games with many players," Levine's Working Paper Archive 506439000000000070, David K. Levine.
    19. Zhang, Huanren, 2018. "Errors can increase cooperation in finite populations," Games and Economic Behavior, Elsevier, vol. 107(C), pages 203-219.
    20. Edgar J. Sanchez Carrera, 2019. "Evolutionary dynamics of poverty traps," Journal of Evolutionary Economics, Springer, vol. 29(2), pages 611-630, April.
    21. Elvio Accinelli & Laura Policardo & Edgar J. Sánchez Carrera, 2012. "On the Dynamics and Effects of Corruption on Environmental Protection," Documentos de Trabajo (working papers) 1312, Department of Economics - dECON.

    More about this item

    Keywords

    fictitious play; nonparametric; finite sample; matched pairs; foregone payoffs; minimax risk; ex-ante improving; selection procedure;
    All these 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.