Dynamic Social Learning Under Graph Constraints

doi:10.1109/TCNS.2021.3114377

Dynamic Social Learning Under Graph Constraints

2022-09-01

3

OA

AI

K

Konstantin Avrachenkov

DOI：10.1109/TCNS.2021.3114377

Original

Original request for help

Save

Abstract

En 中文

We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively alpha-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 alpha > 0, the asymptotic out- come concentrates around the optimum in a certain limiting sense when annealed by letting alpha up arrow infinity slowly.

Keywords:

Annealed dynamics

dynamic choice with reinforcement

graphical constraints

optimal choice

vertex reinforced random walk

Dynamic Social Learning Under Graph Constraints

Abstract

Journal

Organization