Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Learning without recall by random walks on directed graphs

Rahimian, MA and Shahrampour, S and Jadbabaie, A (2015) Learning without recall by random walks on directed graphs. In: UNSPECIFIED.

Available under License : See the attached license file.

Download (194kB) | Preview
[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)


We consider a network of agents that aim to learn some unknown state of the world using private observations and exchange of beliefs. At each time, agents observe private signals generated based on the true unknown state. Each agent might not be able to distinguish the true state based only on her private observations. This occurs when some other states are observationally equivalent to the true state from the agent's perspective. To overcome this shortcoming, agents must communicate with each other to benefit from local observations. We propose a model where each agent selects one of her neighbors randomly at each time. Then, she refines her opinion using her private signal and the prior of that particular neighbor. The proposed rule can be thought of as a Bayesian agent who cannot recall the priors based on which other agents make inferences. This learning without recall approach preserves some aspects of the Bayesian inference while being computationally tractable. By establishing a correspondence with a random walk on the network graph, we prove that under the described protocol, agents learn the truth exponentially fast in the almost sure sense. The asymptotic rate is expressed as the sum of the relative entropies between the signal structures of every agent weighted by the stationary distribution of the random walk.


Social Networking:
Share |


Item Type: Conference or Workshop Item (UNSPECIFIED)
Status: Published
CreatorsEmailPitt UsernameORCID
Rahimian, MARAHIMIAN@pitt.eduRAHIMIAN0000-0001-9384-1041
Shahrampour, S
Jadbabaie, A
Date: 8 February 2015
Date Type: Publication
Journal or Publication Title: Proceedings of the IEEE Conference on Decision and Control
Volume: 54rd I
Page Range: 5538 - 5543
Event Type: Conference
DOI or Unique Handle: 10.1109/cdc.2015.7403087
Schools and Programs: Swanson School of Engineering > Industrial Engineering
Refereed: Yes
ISBN: 9781479978861
ISSN: 0743-1546
Date Deposited: 17 Aug 2020 14:37
Last Modified: 17 Nov 2022 20:55


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item