Session S04 - Random Walks and Related Topics

Friday, July 16, 11:00 UTC-3

Finding geodesics on graphs using reinforcement learning

Daniel Kious

University of Bath, United Kingdom   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

The premise of our talk will be the fact that ants are believed to be able to find shortest paths between their nest and the sources of food by successive random explorations, without any mean of communication other than the pheromones they leave behind them.

We will discuss a work in collaboration with Bruno Schapira and C\'ecile Mailler in which we introduce a general probabilistic model for this phenomenon, based on reinforcement-learning. We will present various variants of the model, with slightly different reinforcement mechanisms, and show that these small differences in the rules yield significantly different large-time behaviors. In the version called the loop-erased ant process, we are able to prove that the ants manage to find the shortest paths on all series-parallel graphs.

Joint work with Cecile Mailler (Bath, UK), Bruno Schapira (Marseille, France).

View abstract PDF