En poursuivant votre navigation sur ce site, vous acceptez le dépôt de cookies dans votre navigateur. (En savoir plus)

Thèse sur l'exploration efficace dans les bandits structurés (H/F)

Cette offre est disponible dans les langues suivantes :
Français - Anglais

Assurez-vous que votre profil candidat soit correctement renseigné avant de postuler. Les informations de votre profil complètent celles associées à chaque candidature. Afin d’augmenter votre visibilité sur notre Portail Emploi et ainsi permettre aux recruteurs de consulter votre profil candidat, vous avez la possibilité de déposer votre CV dans notre CVThèque en un clic !

Faites connaître cette offre !

Informations générales

Référence : UMR9189-EMIKAU-001
Lieu de travail : VILLENEUVE D ASCQ
Date de publication : mardi 30 juillet 2019
Nom du responsable scientifique : Emilie Kaufmann
Type de contrat : CDD Doctorant/Contrat doctoral
Durée du contrat : 36 mois
Date de début de la thèse : 1 novembre 2019
Quotité de travail : Temps complet
Rémunération : 2 135,00 € brut mensuel

Description du sujet de thèse

L'objectif de cette thèse est de proposer de nouveaux algorithmes pour des problèmes complexes de prise de décisions séquentielle, d'implémentation efficace, assortis de garanties théoriques satisfaisantes, et qui utilisent la bonne quantité d'exploration.

La prise de décision dans un envrionnement aléatoire est au coeur de nombreuses applications, telles les systèmes de recommendation, les essais cliniques adaptatifs, le contrôle de systèmes complexes type smart grids, ou la robotique. De bonnes décisions nécessitent en particulier de réaliser un compris entre exploration de l'environnement et exploitation des actions qui semblent les plus prometteuses d'après les connaissances aquises, dans le but de maximiser des récompenses (apprentissage dit par renforcement). Dans des cas simples, où il s'agit d'effectuer un choix répété parmi différentes actions sans avoir d'information extérieures sur celles-ci (problème capturé par le modèle statistique dit de bandit à plusieurs bras), des algorithmes réalisant ce compris exploration/exploitation de manière optimale sont bien connus. Plus récemment, de tels algorithmes ont été proposé dans des modèles dits de bandit structurés, où l'on peut exploiter des informations sur les différentes actions (par exemple une stucture linéaire, ou une structure de rang faible qui sont courantes dans les problèmes de recommandation) [1]. Ces agorithmes, peu efficaces en pratique en dépit des garanties théoriques (asymptotiques) proposées, sont basés la connaissance de l'allocation “oracle” entre les différentes actions et utilisent un méchanisme dit de “Tracking” qui en ajoutant de l'exploration forcée assure que les proportion d'essais des différentes action à converger vers cette allocation optimale. Ce méchanisme de Tracking a par ailleurs émergé dans d'autres type de problèmes, dits de test adaptatif, où sans nécessité de maximiser des récompenses il s'agit d'aquérir de l'information à propos du système le plus efficacement possible (par exemple identifier l'action conduisant à la récompense moyenne la plus élevée [2] ou la meilleure action selon la position courante dans un jeu [3]).

Dans cette thèse, nous investiguerons l'utilisation de méthodes alternatives à l'exploration forcée mentionnée ci-dessus, qui conduit souvent à de mauvaises performances pratiques. En particulier, nous revisiterons l'utilisation d'algorithmes optimistes (algorithmes basés sur des intervalles de confiance prenant en compte la structure) ou de l'échantillonnage de Thompson (Thompson Sampling [4]) pour les bandits structurés ou les problèmes de test adaptatifs. Nous nous attacherons à proposer une analyse en temps fini des nouveaux algorithmes proposés. Plus généralement, nous souhaitons nous intéresser à la quantité d'exploration minimale nécessaire au delà de ces variantes du problème de bandit ne comprenant qu'un nombre fini d'action (bien qu'exploitant leur structure). Par exemple pour les bandits linéaires contextuels, il a été récement montré que sous une hypothèse de diversité des contextes (utilisateurs à qui on présente du contenu par exemple, ou des contenus eux-même), un algorithme “glouton” qui sélectionnerait la meilleure action basée sur les estimation courante peut avoir de très bonnes performances [5]. Nous souhaitons comprendre si d'autres problèmes d'apprentissage par renforcement partagent cette propriété très intéressante. Les mécanismes d'exploration utilisés jusqu'alors en apprentissage par renforcement sont assez heuristiques (“epsilon-greedy”), et nous nous attacherons à en obtenir une meilleure compréhension théorique.

[1] Minimal Exploration in Structured Stochastic Bandits. Combes et al. NIPS 2017
[2] Optimal Best Arm Identification with Fixed Confidence. Garivier and Kaufmann. COLT 2016
[3] Monte-Carlo Tree Search by Best Arm Identification. Kaufmann and Koolen. NIPS 2017
[4] Analysis of Thompson Sampling for the Multi-armed Bandit Problem. Agrawal and Goyal. COLT 2012
[5] Mostly exploration-free algorithms for contextual bandits. Bastani et al. ArXiv:1704.09011, 2018.

Contexte de travail

La thèse se déroulera au sein de l'équipe SequeL du laboratoire CRIStAL dans les locaux de l'Inria Lille Nord-Europe (40 avenue de Halley). L'équipe compte une 15aine de membres, dont 3 permantents. Elle sera dirigée par Emilie Kaufmann (CR CNRS, bientôt HDR) et Odalric-Ambrym Maillard (CR INRIA, HDR).

Contraintes et risques

Pas de contraintes particulières.

On en parle sur Twitter !