Proposer des séquences adaptatives d'exercices dans un Environnement informatique pour l'Apprentissage Humain (EIAH) nécessite de caractériser les lacunes de l'élève et d'utiliser cette caractérisation dans une stratégie pédagogique adaptée. Puisque les élèves ne font que quelques dizaines de questions dans une session de révision, ces deux objectifs sont en compétition. L'apprentissage automatique appelle emph {problème de bandits} ces dilemmes d'exploration-exploitation dans les prises de décisions séquentielles. Dans cette thèse, nous étudions plusieurs problèmes de bandits pour une application dans les systèmes éducatifs adaptatifs. Les bandits décroissants au repos sont un problème de décision séquentiel dans lequel la récompense associée à une action décroît lorsque celle-ci est sélectionnée. Cela modélise le cas où un élève progresse quand il travaille et l'EIAH cherche à sélectionner le sujet le moins maîtrisé pour combler les plus fortes lacunes. Nous présentons de nouveaux algorithmes et nous montrons que pour un horizon inconnu $T$ et sans aucune connaissance sur la décroissance des $K$ bras, ces algorithmes atteignent une borne de regret dépendante du problème $mathcal{O}(log{T}),$ et une borne indépendante du problème $widetilde{mathcal{O}}(sqrt{KT})$. Nos résultats améliorent substantiellement l'état de l'art, ou seule une borne minimax $widetilde{mathcal{O}}(K^{1/3}T^{2/3})$ avait été atteinte. Ces nouvelles bornes sont à des facteurs polylog des bornes optimales sur le problème stationnaire, donc nous concluons: les bandits décroissants ne sont pas plus durs que les bandits stationnaires. Dans les bandits décroissants sans repos, la récompense peut décroître à chaque tour pour toutes les actions. Cela modélise des situations différentes telles que le vieillissement du contenu dans un système de recommandation. On montre que les algorithmes conçus pour le problème "au repos" atteignent les bornes inférieures agnostiques au problème et une borne dépendante du problème $mathcal{O}(log{T})$. Cette dernière est inatteignable dans le cas général ou la récompense peut croître. Nous concluons : l'hypothèse de décroissance simplifie l'apprentissage des bandits sans repos. Viser le sujet le moins connu peut être intéressant avant un examen, mais pendant le cursus - quand tous les sujets ne sont pas bien compris - cela peut mener à l'échec de l'apprentissage de l'étudiant. On étudie un Processus de Décision Markovien Partiellement Observable (POMDP, selon l'acronyme anglais) dans lequel on cherche à maîtriser le plus de sujets le plus rapidement possible. On montre que sous des hypothèses raisonnables sur l'apprentissage de l'étudiant, la meilleure stratégie oracle sélectionne le sujet le plus connu sous le seuil de maîtrise. Puisque cet oracle optimal n'a pas besoin de connaitre la dynamique de transition du POMDP, nous sommes capable de proposer une stratégie apprenante avec des outils "bandits" classiques, en évitant ainsi les méthodes gourmandes en données de l'apprentissage de POMDP.
M. Michal VALKO Université de Lille Directeur de thèse M. Aurélien GARIVIER Ecole Normale Supérieure Rapporteur M. Gilles STOLTZ CNRS - Université Paris Sud Rapporteur Mme Mathilde MOUGEOT ENSIEE - ENS Paris Saclay Examinatrice M. Manuel LOPES Instituto Superior Tecnico Examinateur M. Steffen GRUNEWALDER Lancaster University Examinateur M. Jonathan BANON Lelivrescolaire.fr Invité M. Alessandro LAZARIC Inria Lille - Nord Europe Invité
Thèse de l'équipe SCOOL soutenue le 15/12/2020
français
English