On Learning With Finite Memory
We consider an infinite collection of agents who make decisions, sequentially, about an unknown underlying binary state of the world. Each agent, prior to making a decision, receives an independent private signal whose distribution depends on the state of the world. Moreover, each agent also observe...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90491 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1811092652630736896 |
|---|---|
| author | Drakopoulos, Kimon Tsitsiklis, John N. Ozdaglar, Asuman E. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Drakopoulos, Kimon Tsitsiklis, John N. Ozdaglar, Asuman E. |
| author_sort | Drakopoulos, Kimon |
| collection | MIT |
| description | We consider an infinite collection of agents who make decisions, sequentially, about an unknown underlying binary state of the world. Each agent, prior to making a decision, receives an independent private signal whose distribution depends on the state of the world. Moreover, each agent also observes the decisions of its last K immediate predecessors. We study conditions under which the agent decisions converge to the correct value of the underlying state. We focus on the case where the private signals have bounded information content and investigate whether learning is possible, that is, whether there exist decision rules for the different agents that result in the convergence of their sequence of individual decisions to the correct state of the world. We first consider learning in the almost sure sense and show that it is impossible, for any value of K. We then explore the possibility of convergence in probability of the decisions to the correct state. Here, a distinction arises: if K=1, learning in probability is impossible under any decision rule, while for K ≥ 2, we design a decision rule that achieves it. We finally consider a new model, involving forward looking strategic agents, each of which maximizes the discounted sum (over all agents) of the probabilities of a correct decision. (The case, studied in the previous literature, of myopic agents who maximize the probability of their own decision being correct is an extreme special case.) We show that for any value of K, for any equilibrium of the associated Bayesian game, and under the assumption that each private signal has bounded information content, learning in probability fails to obtain. |
| first_indexed | 2024-09-23T15:21:29Z |
| format | Article |
| id | mit-1721.1/90491 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:21:29Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/904912022-10-02T02:25:18Z On Learning With Finite Memory Drakopoulos, Kimon Tsitsiklis, John N. Ozdaglar, Asuman E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Drakopoulos, Kimon Ozdaglar, Asuman E. Tsitsiklis, John N. We consider an infinite collection of agents who make decisions, sequentially, about an unknown underlying binary state of the world. Each agent, prior to making a decision, receives an independent private signal whose distribution depends on the state of the world. Moreover, each agent also observes the decisions of its last K immediate predecessors. We study conditions under which the agent decisions converge to the correct value of the underlying state. We focus on the case where the private signals have bounded information content and investigate whether learning is possible, that is, whether there exist decision rules for the different agents that result in the convergence of their sequence of individual decisions to the correct state of the world. We first consider learning in the almost sure sense and show that it is impossible, for any value of K. We then explore the possibility of convergence in probability of the decisions to the correct state. Here, a distinction arises: if K=1, learning in probability is impossible under any decision rule, while for K ≥ 2, we design a decision rule that achieves it. We finally consider a new model, involving forward looking strategic agents, each of which maximizes the discounted sum (over all agents) of the probabilities of a correct decision. (The case, studied in the previous literature, of myopic agents who maximize the probability of their own decision being correct is an extreme special case.) We show that for any value of K, for any equilibrium of the associated Bayesian game, and under the assumption that each private signal has bounded information content, learning in probability fails to obtain. Irwin Mark Jacobs and Joan Klein Jacobs Presidential Fellowship National Science Foundation (U.S.) (Grant CMMI-0856063) United States. Army Research Office (Grant W911NF-09-1-0556) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (FA9550-09-1-0538) 2014-09-30T18:25:32Z 2014-09-30T18:25:32Z 2013-10 2013-01 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/90491 Drakopoulos, Kimon, Asuman Ozdaglar, and John N. Tsitsiklis. “On Learning With Finite Memory.” IEEE Trans. Inform. Theory 59, no. 10 (October 2013): 6859–6872. https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/tit.2013.2262037 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Drakopoulos, Kimon Tsitsiklis, John N. Ozdaglar, Asuman E. On Learning With Finite Memory |
| title | On Learning With Finite Memory |
| title_full | On Learning With Finite Memory |
| title_fullStr | On Learning With Finite Memory |
| title_full_unstemmed | On Learning With Finite Memory |
| title_short | On Learning With Finite Memory |
| title_sort | on learning with finite memory |
| url | http://hdl.handle.net/1721.1/90491 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT drakopouloskimon onlearningwithfinitememory AT tsitsiklisjohnn onlearningwithfinitememory AT ozdaglarasumane onlearningwithfinitememory |