Dynamic Social Learning Under Graph Constraints

Konstantin E. Avrachenkov; Vivek S. Borkar; Sharayu Moharir; Suhail Shah

doi:10.1109/TCNS.2021.3114377

Dynamic Social Learning Under Graph Constraints

Konstantin E. Avrachenkov, Vivek S. Borkar^*, Sharayu Moharir, Suhail Shah

^*Corresponding author for this work

Research output: Contribution to journal › Journal Article › peer-review

3 Citations (Scopus)

Abstract

We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively α-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. We use this equivalence to show that for α > 0, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting α ↑ ∞ slowly.

Original language	English
Pages (from-to)	1435-1446
Number of pages	12
Journal	IEEE Transactions on Control of Network Systems
Volume	9
Issue number	3
DOIs	https://doi.org/10.1109/TCNS.2021.3114377
Publication status	Published - 1 Sept 2022
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

Annealed dynamics
dynamic choice with reinforcement
graphical constraints
optimal choice
vertex reinforced random walk

Access to Document

10.1109/TCNS.2021.3114377

Cite this

@article{7c1ab75bbd10457989a33d47de278e74,

title = "Dynamic Social Learning Under Graph Constraints",

abstract = "We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively α-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. We use this equivalence to show that for α > 0, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting α ↑ ∞ slowly.",

keywords = "Annealed dynamics, dynamic choice with reinforcement, graphical constraints, optimal choice, vertex reinforced random walk",

author = "Avrachenkov, \{Konstantin E.\} and Borkar, \{Vivek S.\} and Sharayu Moharir and Suhail Shah",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.",

year = "2022",

month = sep,

day = "1",

doi = "10.1109/TCNS.2021.3114377",

language = "English",

volume = "9",

pages = "1435--1446",

journal = "IEEE Transactions on Control of Network Systems",

issn = "2325-5870",

publisher = "IEEE CONTROL SYSTEMS SOCIETY",

number = "3",

}

TY - JOUR

T1 - Dynamic Social Learning Under Graph Constraints

AU - Avrachenkov, Konstantin E.

AU - Borkar, Vivek S.

AU - Moharir, Sharayu

AU - Shah, Suhail

PY - 2022/9/1

Y1 - 2022/9/1

N2 - We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively α-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. We use this equivalence to show that for α > 0, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting α ↑ ∞ slowly.

AB - We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively α-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. We use this equivalence to show that for α > 0, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting α ↑ ∞ slowly.

KW - Annealed dynamics

KW - dynamic choice with reinforcement

KW - graphical constraints

KW - optimal choice

KW - vertex reinforced random walk

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000856122100036

UR - https://openalex.org/W3199360645

UR - https://www.scopus.com/pages/publications/85115673896

U2 - 10.1109/TCNS.2021.3114377

DO - 10.1109/TCNS.2021.3114377

M3 - Journal Article

SN - 2325-5870

VL - 9

SP - 1435

EP - 1446

JO - IEEE Transactions on Control of Network Systems

JF - IEEE Transactions on Control of Network Systems

IS - 3

ER -

Dynamic Social Learning Under Graph Constraints

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this