ED Mathématiques et Informatique
Discrete and continuous random dispersion models in dimension 1, analysis of a reinforcement learning algorithm.
by Zoé VARIN (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
The defense will take place at 10h00 - Amphi LaBRI, Bâtiment A30, Domaine universitaire, 351, cours de la Libération, 33405 Talence
in front of the jury composed of
- Jean-François MARCKERT - Directeur de recherche - Université de Bordeaux - Directeur de these
- Marie ALBENQUE - Directrice de recherche - Université Paris Cité - Rapporteur
- Arvind SINGH - Chargé de recherche - Université Paris-Saclay - Rapporteur
- Mireille BOUSQUET-MéLOU - Directrice de recherche - Université de Bordeaux - Examinateur
- Nicolas BROUTIN - Professeur des universités - Sorbonne université - Examinateur
- Valentin FéRAY - Directeur de recherche - Université de Lorraine - Examinateur
This thesis lies at the intersection of probabilities, combinatorics, and interacting particle systems. We study several random models, with, in particular, a focus on their asymptotic behavior. In the first part, we study two families of models: the golf model and a new family of models that we introduce, the continuous dispersion models. Although different at first sight, they exhibit similar properties. The golf model is a discrete model in which particles move on Z/nZ until they find “free holes” and stop. This model is related to the parking model, but is more general due to its particle movement rules. The continuous dispersion models, on the other hand, have a continuous nature: mass is progressively spread on the unit circle, resulting in occupied and free components. In both settings, we obtain universality properties: the distribution of the occupied and free components turns out to be independent of the dispersion policy of the particles/masses, under relatively light assumptions on these dispersion policies. This enables us to derive precise results, in particular asymptotic ones, concerning the distribution of these models. In the second part of this thesis, we study a reinforcement learning process, inspired by biological models in which ants, by depositing pheromones along their paths, are able to find shortest paths between their nests and a source of food. We focus more specifically on a loop-erased model, where ants reinforce only self-avoiding paths. We prove the convergence of this model on a family of graphs called the triangle-series-parallel graphs, and show that in this setting the ants indeed find optimal paths.