Dynamic social learning under graph constraints

Konstantin Avrachenkov (1) , Vivek S Borkar (2) , Sharayu Moharir (2) , Suhail Mohmad Shah (3)

1 NEO - Network Engineering and Operations
2 EE-IIT - Department of Electrical Engineering [IIT-Bombay]
3 HKUST - Hong Kong University of Science and Technology

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 outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting $\alpha \to \infty$ slowly.

Mots clés: dynamic choice with reinforcement; optimal choice; graphical constraints; annealed dynamics; vertex reinforced random walk

Domaines: Optimisation et contrôle [math.OC]; Probabilités [math.PR]; Apprentissage [cs.LG]; Réseaux et télécommunications [cs.NI]

Konstantin Avrachenkov, Vivek S Borkar, Sharayu Moharir, Suhail Mohmad Shah. Dynamic social learning under graph constraints. IEEE Transactions on Control of Network Systems, 2022, 9 (3), pp.1435-1446. ⟨10.1109/TCNS.2021.3114377⟩. ⟨hal-03462479⟩