Dynamic social learning under graph constraints
This work addresses theoretical challenges in social learning and reinforcement processes on networks, but appears incremental as it builds on existing models like vertex reinforced random walks.
The paper tackles the problem of modeling dynamic social learning under graph constraints with reinforcement from positively homogeneous rewards, showing that the empirical process concentrates around the optimum in a limiting sense when a parameter is slowly increased to infinity.
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 $α\uparrow\infty$ slowly.