Post-Doctorant F/H Recherche locale pour les problèmes de bandits-manchots combinatoires

Le centre Inria de l'Université de Rennes est l'un des neuf centres d’Inria et compte plus d'une trentaine d’équipes de recherche. Le centre Inria est un acteur majeur et reconnu dans le domaine des sciences numériques. Il est au cœur d'un riche écosystème de R&D et d’innovation : PME fortement innovantes, grands groupes industriels, pôles de compétitivité, acteurs de la recherche et de l’enseignement supérieur, laboratoires d'excellence, institut de recherche technologique.

La personne sera recrutée au sein de l'équipe LACODAM du centre Inria de Rennes. Ce centre de recherche se distingue par son excellence en recherche numérique et innovation technologique, propulsant des avancées majeures dans des domaines tels que l'intelligence artificielle, la cybersécurité et la santé numérique, tout en collaborant étroitement avec des acteurs industriels et académiques pour façonner les technologies de demain.

La personne recrutée sera encadrée par Élisa Fromont et Romaric Gaudel, et travaillera en collaboration avec Paul Viallard. Tous trois sont des chercheuses et chercheurs en Machine Learning avec des publications dans les confeerences de premier plan sur les aspects théoriques du Machine Learning et notamment les problèmes de bandits manchots. 

L'objectif du projet est de résoudre une classe de problèmes d'optimisation combinatoire en présence de retours de type bandit-manchot par le biais d'approches s'appuyant sur des recherches locales. L'approche envisagée s'inscrit dans les approches d'apprentissage par renforcement et réduit fortement à la fois le regret et le coût de calcul liés à la recherche d'une politique optimale.

Le problème applicatif considéré est le choix d'un sous-graphe connexe recouvrant dans le but de
maximiser le flot. Dans le détail, on est face à un ensemble de noeuds qui désirent communiquer et un
ensemble de connexions possibles entre ces noeuds. On désire maximiser le flot de communication, tout
en minimisant le nombre d'arrêtes entre les noeuds. On cherche donc à identifier les arêtes à conserver
dans ce but.

Ce projet de recherche est financé dans le cadre d'une convention de partenariat entre Inria et l'agence de l'inovation de défense du ministère des armées français.

Ce problème d'optimisation fait parti de la famille des problèmes de conception de réseau de survie (CRS,
ou Survivable Network Design) [1]. Nos travaux sur le sujet se distinguent par le fait que

• (i) les paramètres du problème d'optimisation sous-jacent ne sont pas connus
• (ii) à chaque pas de temps l'algorithme choisit un sous-réseau et observe le flot sur ce
  sous-réseau ;
• et (iii) l'objectif de l'algorithme est de maximiser le flot moyen observé.

Dans ce contexte, l'algorithme estime les paramètres du problème d'optimisation sous-jacent à partir du comportement du flot observé à chaque pas de temps. Mais comme les informations récoltées se limitent aux arêtes du sous-réseau choisi, on se retrouve confronté à deux options antagonistes : choisir à chaque pas de temps un sous-réseau qui est efficace d'après les données récoltées jusqu'à présent, ou "jouer" (i.e. sélectionner) un sous-réseau qui couvre des arêtes qui ont été peu testées pour vérifier leurs propriétés. Cela correspond au cadre des problèmes de bandits-manchots à bras multiples [2] sur un espace combinatoire.

Le problème des bandits-manchots à bras multiples est fondamental en apprentissage par renforcement. Ils modélisent un grand nombre d'applications dans lesquelles un agent artificiel choisit une action à chaque pas de temps et reçoit une récompense aléatoire qui dépend de cette action. La distribution de ces récompenses n'est pas connue et l'agent doit l'apprendre à partir uniquement des récompenses qu'il reçoit. Ce cadre couvre, par exemple, le choix des informations à afficher sur une page web, ou la recommandation de vidéos.

La résolution de problèmes combinatoires tels que le problème du voyageur de commerce et les problèmes de logistique (en présence d'incertitude sur les paramètres du problème) rentre parfaitement dans ce cadre. Mais ces problèmes sont moins traités par l'état de l'art car ils sont plus difficiles à résoudre, en raison notamment du très grand nombre d'options à considérer. Le projet proposera donc des algorithmes de bandit-manchots dédiés au  problème CRS.

Références

• [1] Lap Chi Lau, Joseph (Seffi) Naor, Mohammad R. Salavatipour, Mohit Singh. Survivable Network
  Design with Degree or Order Constraints. STOC’07.
• [2] Auer, P.; Cesa-Bianchi, N.; and Fischer, P. 2002. Finite-time Analysis of the Multiarmed Bandit
  Problem. Machine Learning 47(2): 235–256.
• [3] Camille-Sovanneary Gauthier, Romaric Gaudel, Elisa Fromont, Aser-Boammani Lompo.
  Parametric Graph for Unimodal Ranking Bandit. ICML'21
• [4] Camille-Sovanneary Gauthier, Romaric Gaudel, Elisa Fromont. UniRank: Unimodal Bandit
  Algorithm for Online Ranking. ICML'22
• [5] Richard Combes and Alexandre Proutière. Unimodal bandits: Regret lower bounds and optimal
  algorithms. ICML'14

Le projet proposera tout d'abord un algorithme de bandit-manchots s'appuyant sur une méthode
d'optimisation approchée du problème CRS.
Le projet étudiera par la suite un algorithme s'appuyant sur une recherche locale.

Les algorithmes seront conçus, prouvés, implémentés et testés.

Compétences requises :

• avoir déjà une expérience en apprentissage automatique,
• être une bonne programmeuse ou un bon programmeur,
• être à l'aise avec le formalisme mathématique,
• et ne pas avoir peur des démonstrations mathématiques.

Des connaissances en bandits-manchots ou en apprentissage par renforcement sont appréciées.

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement)
• Possibilité de télétravail (après 6 mois d'ancienneté) et aménagement du temps de travail
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
• Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d'Inria)
• Accès à la formation professionnelle
• Sécurité sociale

Salaire mensuel brut de 2788€