Self-interaction and learning in random structures
Abstract
I will discuss self-interacting processes, and in particular the learning features that arise from that interaction. I will start with the reinforced random walk, introduced by Coppersmith and Diaconis in 1986, a nearest-neighbor walk on a discrete graph which reinforces on the number of times a vertex or an edge has been visited. The vertex-reinforced random walk displays strong localisation in the sense that it eventually gets stuck on a finite subset of vertices: I showed for instance in 2004 that on the integers it will eventually visit only five consecutive vertices infinitely often almost surely. On the other hand the edge-reinforced random walk surprisingly shows strikingly different behavior, and is explicitly linked to a supersymmetric hyperbolic sigma model in quantum field theory (Sabot and Tarrès, 2015), to a random Schr?dinger operator (Sabot, Tarrès and Zeng, 2017) and Dynkin's isomorphism (Sabot and Tarrès, 2016). It shows in particular a recurrence/transience phase transition in dimension 3 and higher (Disertori, Sabot and Tarrès, 2015), which settles a conjecture of Diaconis in 1986. I will also present some other related processes, in particular the strongly edge-reinforced random walk on which I proved with Limic in 2007 a conjecture of Sellke (1994) of eventual localisation on a single edge, and the so-called Brownian polymers, on which I proved two conjectures of Durrett and Rogers (1992), respectively with Mountford in 2008 and with Tóth and Valkó in 2012. Finally I will discuss applications in papers in collaboration on evolutionary biology questions, on the multi-armed bandit problem, on optimal bounds for online learning algorithms, and on reinforcement learning algorithms in game theory for language and network formation.