Doctorant (F/H) Thèse de Doctorat / Algorithmes de

**Type de contrat **:CDD

**Niveau de diplôme exigé **:Bac + 5 ou équivalent

**Autre diplôme apprécié **:Master

**Fonction **:Doctorant

**Contexte et atouts du poste**:
**Equipe**

**Contacts**

**Mission confiée**:
Ces dernières années, le succès d'AlphaZero dans la maîtrise de jeux complexes tels que les échecs et le Go a démontré la puissance de l'apprentissage par renforcement couplé à des algorithmes de recherche dans les arbres (de type MCTS) et des approximateurs de fonction puissants (réseaux de neurones profonds). Cependant, même avec ces réalisations remarquables, il reste des questions théoriques intrigantes insuffisamment inexplorées. Cette thèse concerne l'étude des fondements théoriques des algorithmes de jeu, en se concentrant spécifiquement sur les jeux déterministes à deux joueurs. Les principaux objectifs comprennent l'amélioration des algorithmes existants de recherche dans les arbres, le développement de modèles probabilistes de jeux déterministes plus sophistiqués que l'état de l'art, les algorithmes d'inférence pour ces modèles, et le développement de benchmarks pour ces problèmes.

**Principales activités**:
La première voie d'exploration consiste à faire progresser les algorithmes de recherche dans les arbres en particulier ceux concernant des arbres MIN-MAX adaptés aux jeux déterministes à deux joueurs. En s'appuyant sur des algorithmes établis comme [14], AlphaBeta [7] et MTD(f) [13], cette recherche vise à proposer des algorithmes de recherche nouveaux. Les améliorations potentielles peuvent inclure des stratégies d'élagage optimisées et des approches innovantes de l'exploration de l'espace de recherche comme l'utilisation d'hypothèses de régularité de l'approche optimiste (algorithmes DOO/SOO [10,11,2], SEQUOOL [1]). L'analyse théorique se penchera sur les propriétés mathématiques des algorithmes proposés, en établissant leurs forces et leurs limites.

Le deuxième axe de recherche se concentre sur le fait d'identifier et analyser des modèles probabilistes de jeux déterministes, qui soient moins triviaux que le modèle de Pearl [12]. En développant des modèles plus sophistiqués, l'objectif est de fournir une représentation plus riche de la complexité inhérente aux jeux déterministes. Cela inclut l'incorporation d'éléments tels que la dépendance par le biais d'ancêtres d'arbres communs [3,6,4] afin de mieux refléter les scénarios du monde réel. L'analyse théorique examinera les algorithmes d'inférence pour mettre à jour les paramètres du modèle en fonction des observations acquises pendant la recherche et leur qualité de modélisation pour un ensemble varié de jeux déterministes.

Sur la base de ces modèles probabilistes, un troisième objectif est d'étudier la complexité moyenne correspondante de plusieurs algorithmes de pointe, d'explorer des stratégies alternatives pour la prise de décision dans les jeux déterministes. Les connaissances théoriques acquises contribueront à une meilleure compréhension de la manière dont les modèles probabilistes peuvent guider les processus de décision dans le contexte des jeux (pour l'instant, la plupart de ces algorithmes sont comparés sur le modèle de Pearl [12] et sont essentiellement indifférentiables... étant tous optimaux dans ce cadre).

Une dernière dimension de cette recherche, qui est transversale à toutes les dimensions précédentes, implique la constitution d'une base benchmark de fonctions et jeux (dans un esprit similaire aux bases [9,5] pour l'optimisation de fonctions). On pourra s'appuyer sur la base [8]. Des problèmes de référence soigneusement sélectionnés fourniront une évaluation complète des méthodes proposées. Pour les jeux, on s'attachera à identifier les faiblesses potentielles d'AlphaZero et comment les algorithmes que nous proposerons peuvent exploiter ces vulnérabilités.

Enfin, selon l'avancement sur les dimensions ci-dessus, des perspectives du travail pourront inclure le cas de problèmes avec information partielle, ou la mise en œuvre dans un schéma de programmation dynamique approchée similaire à AlphaZero.

**Références**:

- 1- P. L. Bartlett, V. Gabillon, and M. Valko.
- A simple parameter-free and adaptive approach to optimization under a mínimal local smoothness assumption.
- In A. Garivier and S. Kale, editors, _Algorithmic Learning Theory, ALT 2019, 22-24 March 2019, Chicago, Illinois, USA_, volume 98 of _Proceedings of Machine Learning Research_, pages 184-206. PMLR, 2019.- 2- L. Busoniu, R. Munos, and E. Páll.
- An analysis of optimistic, best-first search for mínimax sequential decision making.
- In _Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), 2014 IEEE Symposium on_, page 1-8. IEEE, IEEE, 2014.- 3- L. Devroye and O. Kamoun.
- Random mínimax game trees.
- In D. Aldous and R. Pemantle, editors, _Random Discrete Structures_, pages 55-80, New York, NY, 1996. Spr