# Dynamic social learning under graph constraints

arXiv: https://arxiv.org/abs/2007.03983 · HTML: https://mlsanity.com/paper/2007.03983/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2020.

## Built on by (most cited first, 2 of 2)

- [Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains](https://mlsanity.com/paper/2305.05097/) (2023)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)

## Abstract (arXiv)

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∞ slowly.