Groupe d’études et de recherche en analyse des décisions

# Graph-constrained dynamic choice

## Vivek Borkar – Département de génie électrique, Indian Institute of Technology Bombay, Inde

Présentation sur YouTube

In this talk, I introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively $$\alpha$$-homogeneous rewards. 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. Thus the limiting differential equation that it tracks coincides with the forward Kolmogorov equation for the latter, which in turn is a scaled version of a special instance of replicator dynamics with potential. This equivalence is exploited to show that for $$\alpha > 0$$, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting $$\alpha \uparrow \infty$$ slowly. (Joint work with Konstantin Avrachenkov, Sharayu Moharir and Suhail Mohmad Shah.)