IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00124679.html
   My bibliography  Save this paper

Strategies for prediction under imperfect monitoring

Author

Listed:
  • Gabor Lugosi

    (ICREA - Institució Catalana de Recerca i Estudis Avançats)

  • Shie Mannor

    (McGill University = Université McGill [Montréal, Canada])

  • Gilles Stoltz

    (DMA - Département de Mathématiques et Applications - ENS Paris - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris sciences et lettres - CNRS - Centre National de la Recherche Scientifique, GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC - HEC Paris - Ecole des Hautes Etudes Commerciales - CNRS - Centre National de la Recherche Scientifique)

Abstract

We propose simple randomized strategies for sequential prediction under imperfect monitoring, that is, when the forecaster does not have access to the past outcomes but rather to a feedback signal. The proposed strategies are consistent in the sense that they achieve, asymptotically, the best possible average reward. It was Rustichini (1999) who first proved the existence of such consistent predictors. The forecasters presented here offer the first constructive proof of consistency. Moreover, the proposed algorithms are computationally efficient. We also establish upper bounds for the rates of convergence. In the case of deterministic feedback, these rates are optimal up to logarithmic terms.

Suggested Citation

  • Gabor Lugosi & Shie Mannor & Gilles Stoltz, 2008. "Strategies for prediction under imperfect monitoring," Post-Print hal-00124679, HAL.
    • Handle: RePEc:hal:journl:hal-00124679
    Note: View the original document on HAL open archive server: https://hal.science/hal-00124679v4
    as

    Download full text from publisher

    File URL: https://hal.science/hal-00124679v4/document
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. MERTENS , Jean-François & SORIN , Sylvain & ZAMIR , Shmuel, 1994. "Repeated Games. Part B : The Central Results," LIDAM Discussion Papers CORE 1994021, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Nicolò Cesa-Bianchi & Gábor Lugosi & Gilles Stoltz, 2006. "Regret Minimization Under Partial Monitoring," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 562-580, August.
    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. Nicolo Cesa Bianchi & Gábor Lugosi, 1998. "On prediction of individual sequences," Economics Working Papers 324, Department of Economics and Business, Universitat Pompeu Fabra.
    5. Rustichini, Aldo, 1999. "Minimizing Regret: The General Case," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 224-243, October.
    6. Sergiu Hart & Andreu Mas-Colell, 2013. "A Reinforcement Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 4, pages 77-98, World Scientific Publishing Co. Pte. Ltd..
    7. MERTENS , Jean-François & SORIN , Sylvain & ZAMIR , Shmuel, 1994. "Repeated Games. Part A : Background Material," LIDAM Discussion Papers CORE 1994020, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Chen, Xiaohong & White, Halbert, 1996. "Laws of Large Numbers for Hilbert Space-Valued Mixingales with Applications," Econometric Theory, Cambridge University Press, vol. 12(2), pages 284-304, June.
    9. Nimrod Megiddo, 1979. "On Repeated Games with Incomplete Information Played by Non-Bayesian Players," Discussion Papers 373, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    10. MERTENS, Jean-François & SORIN , Sylvain & ZAMIR , Shmuel, 1994. "Repeated Games. Part C : Further Developments," LIDAM Discussion Papers CORE 1994022, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vianney Perchet & Marc Quincampoix, 2015. "On a Unified Framework for Approachability with Full or Partial Monitoring," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 596-610, March.
    2. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    3. Ehud Lehrer & Eilon Solan, 2016. "A General Internal Regret-Free Strategy," Dynamic Games and Applications, Springer, vol. 6(1), pages 112-138, March.
    4. Gábor Bartók & Dean P. Foster & Dávid Pál & Alexander Rakhlin & Csaba Szepesvári, 2014. "Partial Monitoring---Classification, Regret Bounds, and Algorithms," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 967-997, November.

    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. Gábor Lugosi & Shie Mannor & Gilles Stoltz, 2008. "Strategies for Prediction Under Imperfect Monitoring," Mathematics of Operations Research, INFORMS, vol. 33(3), pages 513-528, August.
    2. Rustichini, A., 1998. "Minimizing Regret : The General Case," Discussion Paper 1998-41, Tilburg University, Center for Economic Research.
    3. Jacquemet, Nicolas & Koessler, Frédéric, 2013. "Using or hiding private information? An experimental study of zero-sum repeated games with incomplete information," Games and Economic Behavior, Elsevier, vol. 78(C), pages 103-120.
    4. Nicolò Cesa-Bianchi & Gábor Lugosi & Gilles Stoltz, 2006. "Regret Minimization Under Partial Monitoring," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 562-580, August.
    5. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    6. Pintér, Miklós & Udvari, Zsolt, 2011. "Generalized type spaces," MPRA Paper 34107, University Library of Munich, Germany.
    7. Sylvain Sorin, 2011. "Zero-Sum Repeated Games: Recent Advances and New Links with Differential Games," Dynamic Games and Applications, Springer, vol. 1(1), pages 172-207, March.
    8. Laraki, Rida & Sorin, Sylvain, 2015. "Advances in Zero-Sum Dynamic Games," Handbook of Game Theory with Economic Applications,, Elsevier.
    9. Domansky, V. & Kreps, V., 2011. "Game Theoretic Bidding Model: Strategic Aspects of Price Formation at Stock Markets," Journal of the New Economic Association, New Economic Association, issue 11, pages 39-62.
    10. Ehud Lehrer & Eilon Solan, 2016. "A General Internal Regret-Free Strategy," Dynamic Games and Applications, Springer, vol. 6(1), pages 112-138, March.
    11. Pintér, Miklós, 2011. "Common priors for generalized type spaces," MPRA Paper 44818, University Library of Munich, Germany.
    12. Adlakha, Sachin & Johari, Ramesh & Weintraub, Gabriel Y., 2015. "Equilibria of dynamic games with many players: Existence, approximation, and market structure," Journal of Economic Theory, Elsevier, vol. 156(C), pages 269-316.
    13. Jonathan Shalev, 1998. "Loss Aversion in Repeated Games," Game Theory and Information 9802005, University Library of Munich, Germany.
    14. Matthijs van Veelen, 2002. "Altruism, Fairness and Evolution: the Case for Repeated Stochastic Games," Tinbergen Institute Discussion Papers 02-111/1, Tinbergen Institute.
    15. Fedor Sandomirskiy, 2014. "Repeated games of incomplete information with large sets of states," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 767-789, November.
    16. Elias Tsakas, 2014. "Universally Rational Belief Hierarchies," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 16(01), pages 1-12.
    17. Heifetz, Aviad & Samet, Dov, 1998. "Knowledge Spaces with Arbitrarily High Rank," Games and Economic Behavior, Elsevier, vol. 22(2), pages 260-273, February.
    18. Pintér, Miklós, 2011. "Invariance under type morphisms: the bayesian Nash equilibrium," MPRA Paper 38499, University Library of Munich, Germany.
    19. Deb, Joyee & González-Díaz, Julio & Renault, Jérôme, 2016. "Uniform folk theorems in repeated anonymous random matching games," Games and Economic Behavior, Elsevier, vol. 100(C), pages 1-23.
    20. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2005. "Stochastic Approximations and Differential Inclusions; Part II: Applications," Working Papers hal-00242974, HAL.

    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:hal:journl:hal-00124679. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.