Algorithmes collectifs pour l'exploration et la prise de décision

Cette thèse porte sur la prise de décision séquentielle, dite 'en ligne', c’est-à-dire sur la conception d’algorithmes capables de traiter des données révélées progressivement. Un problème central qui motive cette étude est l’exploration collective d’un arbre, dans lequel une équipe d’agents mobiles doit explorer un arbre inconnu en partant de sa racine, aussi rapidement que possible. À tout moment, les déplacements des agents doivent être décidés uniquement sur la base des informations déjà recueillies. Ce problème modélise une question fondamentale : l’exploration d’un labyrinthe est-elle parallélisable ? Cette thèse propose de nouvelles perspectives, de nouveaux algorithmes, ainsi que des garanties théoriques améliorées pour l’exploration collective des arbres. Nous mettons également en lumière des liens profonds avec des problèmes en ligne classiques, tels que la traversée de graphes, conduisant à de nouvelles questions et de nouveaux résultats pour ce problème également. Un thème récurrent dans la prise de décision en ligne est que les algorithmes aléatoires surpassent souvent les algorithmes déterministes. Nous proposons de réexaminer ce fait à travers le prisme des algorithmes collectifs, avec l’idée qu’une équipe d’agents simples (e.g., déterministes) peut collectivement obtenir de meilleures performances qu’un agent seul. Cette approche s’inscrit dans le cadre des algorithmes faiblement randomisés, qui utilisent seulement un nombre fini de bits aléatoires. Nous introduisons des algorithmes collectifs pour deux problèmes classiques : les systèmes de tâches métriques et le problème des k-serveurs. Cela offre une nouvelle perspective sur la complexité avec indices de ces problèmes, c’est-à-dire sur la manière dont la connaissance partielle de la donnée d’entrée peut améliorer les performances. La thèse aborde également d’autres aspects de la prise de décision en ligne, tels que l’analyse en moyenne, la complexité de communication, la complexité en espace, et la complexité computationnelle.