Dynamic Non-Bayesian Decision Making

Dov Monderer and Moshe Tennenholtz
Additional contact information
Dov Monderer: Technion, Israel Institute of Technology
Moshe Tennenholtz: Technion

Game Theory and Information from University Library of Munich, Germany

Abstract: The model of a non-Bayesian agent who faces a repeated game with incomplete informationagainst Nature is an appropriate tool for modeling general agent- environment interactions. In such a modelthe environment state (controlled by Nature) may change arbitrarily and the reward function is initially unknown. The agent is non-bayesian, that is he does not form a prior probability neither on the state selection strategy of Nature, nor on his reward function. Two basic feedback structure are considered. In one of them- the perfect mopnitoring case- the agent is able to observe the previous environment state as part of his feedback, while in the other - the imperfect monitoring case- all that is available to the agent is the reward obtained. Both of these setting refer to partially observable processes, where the current environment state is unknown. Our main result refers to the competitive ratio criterion in the perfect monitoring case; We prove the existence of an efficient stochastic policy which ensures that the competitive ratio is obtained at almost all stages with an arbitrary high probability, where efficiency is measured in term of rate of convergence. It is further shown that such an optimal strategy does not exist in the imperfect monitoring case. Moreover, it is proved that in the perfect monitoring case there does not exist a deterministic policy that satisfy our long run optimality criterion. In addition we discuss the maxmin criterion and prove that a deterministic efficient optimal strategy does exist in the imperfect monitoring case under this criterion. Finally we show that our approach to long-run optimality can be vied as qualitative, which distinguishes it from previous work in this area.

Keywords: Learning; Artificial Intelegence (search for similar items in EconPapers)
JEL-codes: C7 D8 (search for similar items in EconPapers)
Pages: 15 pages
Date: 1997-03-17
Note: Type of Document - Postscript file; prepared on amsTex; to print on PostScript; pages: 15
References: Add references at CitEc
Citations:

Downloads: (external link)
https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/9703/9703003.pdf (application/pdf)
https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/9703/9703003.ps.gz (application/postscript)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wpa:wuwpga:9703003

Access Statistics for this paper

More papers in Game Theory and Information from University Library of Munich, Germany
Bibliographic data for series maintained by EconWPA ( this e-mail address is bad, please contact ).