On étudie un processus d’apprentissage par renforcement, inspiré par les fourmis, qui communiquent à l’aide de phéromones. On considère un graphe G, avec deux nids (des sommets, N1 et N2) et une source de nourriture (un autre sommet, F). À chaque étape, une fourmi : 1) part d’un nid (aléatoire, N1 ou N2) et réalise une marche aléatoire (pondérée par les poids des arêtes) jusqu’à une source de nourriture F ; puis 2) à son retour, elle dépose des phéromones, c’est-à-dire renforce les arêtes (en ajoutant 1 à leur poids) appartenant au chemin aller auquel on a enlevé les boucles inutiles.
Pour des raisons techniques, nous étudions le cas des graphes séries-parallèles en triangle, c’est à dire des graphes obtenus en remplaçant chaque arête du triangle N1 N2 F par un graphe série-parallèle. On montre que les poids des arêtes (normalisés) convergent, vers des variables aléatoires nulles si les arêtes associées n’appartiennent pas à un plus court chemin d’un sommet de {N1, N2, F} à un autre.
Nous présenterons plusieurs outils utiles pour prouver cette convergence, notamment la comparaison avec des processus d’urnes, des techniques d’approximations stochastiques et des arguments combinatoires.
La présentation se basera sur un travail en commun avec Cécile Mailler.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne